Python数据结构与算法（二）—线性表

  1 """
  2 链表程序实现
  3 重点代码
  4 
  5 思路分析
  6 1. 创建节点类，生成节点对象
  7 　　包含数据和下一个节点的引用
  8 2. 链表类，生成链表对象
  9 　　可以对链表进行数据操作
 10 """
 11 
 12 # 节点类
 13 class Node:
 14   def __init__(self, data, next=None):
 15     self.data = data
 16     self.next = next
 17 
 18 
 19 # 链表类
 20 class Linklist:
 21   """
 22   建立链表模型
 23   进行链表操作
 24   """
 25 
 26   def __init__(self):
 27     """
 28     初始化链表,生成一个头节点,表示链表开始节点
 29     """
 30     self.head = Node(None)
 31 
 32   # 初始添加一组链表节点
 33   def init_list(self, list_):
 34     p = self.head  # ｐ为移动变量
 35     for i in list_:
 36       p.next = Node(i)
 37       p = p.next  # ｐ向后移动一个节点
 38 
 39   # 遍历链表
 40   def show(self):
 41     p = self.head.next  # 第一个有效节点
 42     while p is not None:
 43       print(p.data, end=‘ ‘)
 44       p = p.next
 45     print()  # 换行
 46 
 47   # 获取链表长度
 48   def get_length(self):
 49     n = 0
 50     p = self.head
 51     while p.next is not None:
 52       n += 1
 53       p = p.next
 54     return n
 55 
 56   # 判断链表是否为空
 57   def is_empty(self):
 58     if self.get_length() == 0:
 59       return True
 60     else:
 61       return False
 62 
 63   # 清空链表
 64   def clear(self):
 65     self.head.next = None
 66 
 67   #　尾部插入节点
 68   def append(self,data):
 69     node = Node(data)  #　生成新节点
 70     p = self.head
 71     while p.next is not None:
 72       p = p.next
 73     p.next = node
 74 
 75   #　选择位置插入节点
 76   def insert(self,index,data):
 77     if index < 0 or index > self.get_length():
 78       raise IndexError("index out of range")
 79 
 80     # 定义ｐ移动到插入位置的前一个
 81     p = self.head
 82     for i in range(index):
 83       p = p.next
 84 
 85     node = Node(data) #　生成节点
 86 
 87     # 插入
 88     node.next = p.next
 89     p.next = node
 90 
 91   # 删除节点
 92   def delete(self,data):
 93     p = self.head
 94     while p.next and p.next.data != data:
 95       p = p.next
 96     #　判断ｗｈｉｌｅ循环结束原因
 97     if p.next is None:
 98       raise ValueError("value is error")
 99     else:
100       p.next = p.next.next
101 
102   # 获取节点值
103   def get_item(self,index):
104     if index < 0 or index >= self.get_length():
105       raise IndexError("index out of range")
106     p = self.head.next
107     for i in range(index):
108       p = p.next
109     return p.data
110 
111 
112 if __name__ == "__main__":
113   # 链表对象　　
114   # link-->head
115   # link.head --> data == None
116   # link.head --> next == None
117   link = Linklist()
118   l = [1, 2, 3, 4, 5]
119   link.init_list(l)
120   link.show()  #　遍历数据
121   print("Link length:",link.get_length())
122   link.append(6)
123   link.insert(4,100)
124   link.show()
125   link.delete(3)
126   link.show()
127   print(link.get_item(3))