代码：
class Node:
def __init__(self, data):
self.data = data
self.next = None
def create_list():
seq = input("Enter the sequence of integers: ").split()
int_seq = [int(i) for i in seq]
head = None
tail = None
for number in int_seq:
if number == -1:
break
node = Node(number)
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head, tail
def count_no_of_elements(head):
if head is None:
return 0
curr = head
counter = 0
while curr:
curr = curr.next
counter += 1
return counter
def insert_element(head, tail, elem, posn):
no_of_elem = count_no_of_elements(head)
if posn <= 0 or posn > no_of_elem + 1:
return -1, -1
if posn == 1: # Insert at the beginning
element = Node(elem)
element.next = head
head = element
return head, tail
else:
counter = 1
curr = head
while counter != (posn - 1):
curr = curr.next
counter += 1
element = Node(elem)
if curr.next is not None: # Insert in between
element.next = curr.next
curr.next = element
else: # Insert at the end
curr.next = element
tail = element
return head, tail
def traverse_list(head):
if head is None:
return -1
curr = head
while curr:
print(curr.data)
curr = curr.next
return head
使用序列创建列表后：1 3 5 7 9 2 4 8 6 0 -1，
我正在尝试连续 3 次在开头插入0。
驱动程序代码：
list_head, list_tail = create_list()
# 1 3 5 7 9 2 4 8 6 0 -1
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
if ins_hd != -1:
trav = count_no_of_elements(ins_hd)
print(trav)
print('nn')
else:
print(ins_hd)
if ins_hd != 1:
trav = traverse_list(ins_hd)
print(in_tl.data)
插入代码在第二次开始不起作用。
实际输出：
11
0
1
3
5
7
9
2
4
8
6
0
0
我在这里错过了什么？
当您从函数中获取返回值时，必须停止使用头和尾的旧值。您需要继续使用从插入中返回的新值。目前您不这样做：
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
# ...
将其更改为使用相同的变量：
list_head, list_tail = insert_element(list_head, list_tail, 0, 1)
list_head, list_tail = insert_element(list_head, list_tail, 0, 1)
# ...
并且在这些语句后面的代码中也使用list_head和list_tail。
使其更加面向对象
我还建议为您的链表创建一个类，以便它保持其头部和尾部的变化值作为其状态的一部分。这使得代码更干净，当然当你开始在同一代码中使用多个链表时：
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, int_seq=[]):
self.head = None
self.tail = None
for number in int_seq:
node = Node(number)
if self.head is None:
self.head = node
else:
self.tail.next = node
self.tail = node
def size(self):
if self.head is None:
return 0
curr = self.head
count = 0
while curr:
curr = curr.next
count += 1
return count
def insert(self, elem, posn=1):
if posn == 1: # Insert before head
node = Node(elem)
node.next = self.head
self.head = node
return
curr = self.head
while curr.next is not None and posn > 2:
curr = curr.next
posn -= 1
if posn != 2:
raise ValueError("Invalid position")
node = Node(elem)
node.next = curr.next
curr.next = node
if curr == self.tail: # Insert after tail
self.tail = node
else: # Insert in between
curr.next = node
def values(self):
curr = self.head
while curr is not None:
yield curr.data
curr = curr.next
seq = input("Enter the sequence of integers: ").split()
llist = LinkedList([int(i) for i in seq])
# 1 3 5 7 9 2 4 8 6 0
llist.insert(0, 1)
print("size: {}".format(llist.size()))
print("values: {}".format(list(llist.values())))
llist.insert(10, 12)
print("size: {}".format(llist.size()))
print("values: {}".format(list(llist.values())))
llist.insert(11, 5)
print("size: {}".format(llist.size()))
print("values: {}".format(list(llist.values())))
在上面的代码中，我保留了相同的posn概念，因此在位置 1 插入意味着插入将在头节点之前发生。许多人会发现将其实际定义为位置 0 更自然，但我保持原样。
我不认为以不同的方式处理输入值 -1 有什么意义，因为您可以读取和插入所有值，所以我删除了该逻辑。
当给定的插入位置超出范围时，我认为提出异常更合适。
此外，计算元素数量以确定位置是否在范围内是矫枉过正的，因为您需要以任何方式迭代列表。因此，您可以确定该迭代中仓位的有效性。