單向循環鍊錶
將所有的連結在一起,每個節點分為資料儲存區和連結區,資料區儲存數據,連結區連結下一個節點
item: 儲存資料的地方
next: 連結下一個節點
注意: 單向循環鍊錶是首位鏈接,即尾部的節點要和頭部的節點連結
單向鍊錶運算
1、鍊錶是否為空
2、鍊錶的長度
3、遍歷鍊錶
4、鍊錶頭部新增元素
5、鍊錶尾部新增元素
6、鍊錶指定位置新增元素
7、鍊錶刪除節點
8、尋找節點是否存在
程式碼實現
# Functions 函数声明 class Node(): """实例化节点类""" def __init__(self, item): self.item = item self.next = None class Linklist(): """ 存放节点类 """ def __init__(self): self.head = None # 1. 链表是否为空 def is_empty(self): return self.head == None # 2. 链表的长度 def length(self): """ 返回链表的长度 遍历所有的节点,使用计数器计数 1、链表为空情况 """ # 实例化节点 cur = self.head if self.is_empty(): return 0 else: # 计数 count = 1 # 遍历链表 while cur.next != self.head: count+=1 cur = cur.next return count # 3. 遍历链表 def travel(self): """ 遍历链表,获取所有的数据 实例游标,遍历数据,输出数据 1、 空链表情况 2、 只有头部节点情况 3、 只有尾部节点情况 """ # 实例化游标 cur = self.head if self.is_empty(): return None else: # 遍历数据 while cur.next != self.head: print(cur.item, end=' ') cur = cur.next # 最后一个节点要单独输出 print(cur.item) # 4. 链表头部添加元素 def add(self, item): """ 往链表头部添加数据 分析 链表为空 self.head 直接指向node, 再讲node指向自己 链表不为空 node.next = self.head """ # 实例化游标 cur = self.head # 实例化节点 node = Node(item) # 判断是否为空 if self.is_empty(): self.head = node node.next = node else: # 不为空的情况 # 要将最后一个节点指向node while cur.next != self.head: cur = cur.next node.next = self.head self.head = node cur.next = node # 5. 链表尾部添加元素 def append(self, item): """ 往尾部添加数据 分析 实例化节点,再实例化游标先指向最后一个节点 调换指向 1、空链表情况 2、只有一个链表情况 """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): self.add(item) else: # 不为空的情况,移动游标指向最后一个节点 while cur.next != self.head: cur = cur.next node.next = self.head cur.next = node pass # 6. 链表指定位置添加元素 def insert(self, index, item): """ 指定位置添加数据 实例化节点, 实例化游标指向索引的数据,更改指向 位置大小 链表是否为空 """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head if index <=0: self.add(item) elif index > (self.length()-1): self.append(item) else: # 判断链表是否为空 if self.is_empty(): self.add(item) else: # 移动游标,指向指定的索引位置 count = 0 while count < index-1: count+=1 cur = cur.next node.next = cur.next cur.next = node pass # 7. 链表删除节点 def remove(self, item): """ 删除指定的节点 实例化游标,遍历链表插件这个节点是否存在,存在则更改指向 不存在,则不修改 空链表情况 头节点情况 尾结点情况 """ # 实例化游标 cur = self.head if self.is_empty(): return None else: # 不为空,遍历链表,对比数据是否相等 # 如果头节点是要删除的数据 if cur.item == item: self.head=cur.next # 找出最后的节点,将最后的节点指向,删除后面的那个节点 while cur.next != self.head: cur = cur.next cur.next = cur.next else: pro = None while cur.next != self.head: if cur.item == item: if cur.item == item: pro.next = cur.next return True else: pro = cur cur = cur.next if cur.item == item: pro.next = self.head pass # 8. 查找节点是否存在 def search(self, item): """ 查找该节点是否存在 实例化游标,遍历所有的节点 查看当前节点的数据是否和item 相等 空链表 头节点 尾结点 """ # 实例化游标 cur = self.head # 判断空链表 if self.is_empty(): return None else: # 不为空遍历整个链表 if cur.item == item: return True else: while cur.next != self.head: if cur.item == item: return True else: cur = cur.next if cur.item == item: return True pass
測試運行
# 程序的入口 if __name__ == "__main__": a = Linklist() a.add(400) a.add(300) a.add(200) a.add(100) # a.append(10) a.insert(4,6) # a.remove(6) print(a.length()) # 5 a.travel() # 100 200 300 400 6 print(a.search(100)) # True pass
以上是python單向循環鍊錶怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!