(基本实验)设计一组整数,完成链表(带表头结点)的基本操作。建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。 其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点、销毁等
时间: 2023-09-25 15:12:15 浏览: 93
以下是实现链表基本操作的代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = ListNode()
def insert(self, val):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = ListNode(val)
def delete(self, val):
cur = self.head
while cur.next is not None:
if cur.next.val == val:
cur.next = cur.next.next
return
cur = cur.next
def search(self, val):
cur = self.head
while cur.next is not None:
if cur.next.val == val:
return cur.next
cur = cur.next
return None
def print(self):
cur = self.head.next
while cur is not None:
print(cur.val, end=" ")
cur = cur.next
print()
def length(self):
cur = self.head.next
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def get_node(self, index):
cur = self.head.next
for i in range(index):
if cur is None:
return None
cur = cur.next
return cur
def predecessor(self, val):
cur = self.head
while cur.next is not None:
if cur.next.val == val:
return cur
cur = cur.next
return None
def successor(self, val):
cur = self.head.next
while cur.next is not None:
if cur.val == val:
return cur.next
cur = cur.next
return None
def merge(self, other):
result = LinkedList()
cur1 = self.head.next
cur2 = other.head.next
while cur1 is not None and cur2 is not None:
if cur1.val < cur2.val:
result.insert(cur1.val)
cur1 = cur1.next
else:
result.insert(cur2.val)
cur2 = cur2.next
while cur1 is not None:
result.insert(cur1.val)
cur1 = cur1.next
while cur2 is not None:
result.insert(cur2.val)
cur2 = cur2.next
return result
def destroy(self):
self.head.next = None
def clear(self):
self.head.next = None
```
下面是使用样例:
```python
# 创建链表,插入元素
lst = LinkedList()
lst.insert(1)
lst.insert(2)
lst.insert(4)
lst.insert(5)
lst.insert(7)
# 输出链表
lst.print() # 1 2 4 5 7
# 删除元素
lst.delete(4)
lst.print() # 1 2 5 7
# 查找元素
node = lst.search(5)
print(node.val) # 5
# 求前驱和后继
pre = lst.predecessor(2)
print(pre.val) # 1
suc = lst.successor(5)
print(suc.val) # 7
# 合并两个有序链表
lst2 = LinkedList()
lst2.insert(3)
lst2.insert(4)
lst2.insert(6)
lst2.insert(8)
merged = lst.merge(lst2)
merged.print() # 1 2 3 4 5 6 7 8
# 销毁链表
lst.destroy()
lst.print() # 什么都不输出
# 将链表置为空表
lst.clear()
lst.print() # 什么都不输出
# 获取链表长度和某位置结点的内容
lst.insert(1)
lst.insert(2)
lst.insert(3)
print(lst.length()) # 3
node = lst.get_node(1)
print(node.val) # 2
# 搜索结点并删除
node = lst.search(2)
lst.delete(node.val)
lst.print() # 1 3
```