要求将算法7~13设计为3. 4. 1节定义的带头结点
要求将算法7~13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。
13·设计算法，在有序单链表中插入值为x的元素，并保持表的有序性。
答案
class LNode: def __init__(self, data=None): self.data = data self.next = None class LinkedList: def __init__(self): self.head = LNode() # 头结点，不存数据 def insert_order(self, x): """有序单链表插入x，保持递增有序""" # 新建结点 new_node = LNode(x) pre = self.head # 找插入位置：pre后面结点的值小于x就继续后移 while pre.next is not None and pre.next.data < x: pre = pre.next # 插入到pre之后 new_node.next = pre.next pre.next = new_node def print_list(self): cur = self.head.next res = [] while cur: res.append(cur.data) cur = cur.next print(res) # 测试 lst = LinkedList() # 原有序链表：2 →4 →6 lst.insert_order(2) lst.insert_order(4) lst.insert_order(6) lst.print_list() # [2, 4, 6] lst.insert_order(5) #插入5 lst.print_list() # [2, 4, 5, 6] lst.insert_order(1) #插表头 lst.print_list() # [1, 2, 4, 5, 6] lst.insert_order(8) #插表尾 lst.print_list() # [1, 2, 4, 5, 6, 8]