Q3:整数序列保存在双向链表中,实现如下操作:(20分) (1)创建; (2)遍历输出; (3)按值查找; (4)按位序插入; (5)按位序删除;
时间: 2023-05-31 08:02:57 浏览: 99
以下是Python代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def create(self, values):
for value in values:
self.append(value)
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.length += 1
def traverse(self):
curr_node = self.head
while curr_node is not None:
print(curr_node.value, end=' ')
curr_node = curr_node.next
print()
def search(self, value):
curr_node = self.head
while curr_node is not None:
if curr_node.value == value:
return curr_node
curr_node = curr_node.next
return None
def insert(self, pos, value):
if pos < 0 or pos > self.length:
print('Invalid position')
return
new_node = Node(value)
if pos == 0:
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
elif pos == self.length:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
else:
curr_node = self.head
for i in range(pos-1):
curr_node = curr_node.next
new_node.prev = curr_node
new_node.next = curr_node.next
curr_node.next.prev = new_node
curr_node.next = new_node
self.length += 1
def delete(self, pos):
if pos < 0 or pos >= self.length:
print('Invalid position')
return
if pos == 0:
if self.head.next is None:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
elif pos == self.length-1:
self.tail = self.tail.prev
self.tail.next = None
else:
curr_node = self.head
for i in range(pos):
curr_node = curr_node.next
curr_node.prev.next = curr_node.next
curr_node.next.prev = curr_node.prev
self.length -= 1
```
使用样例:
```python
ll = LinkedList()
ll.create([1, 2, 3, 4, 5])
ll.traverse() # 1 2 3 4 5
print(ll.search(3).value) # 3
ll.insert(2, 6)
ll.traverse() # 1 2 6 3 4 5
ll.delete(4)
ll.traverse() # 1 2 6 3 5
```