python單向循環(huán)鏈表實例詳解
使用python實現(xiàn)單向循環(huán)鏈表,供大家參考,具體內(nèi)容如下
單向循環(huán)鏈表
將所有的鏈接在一起,每一個節(jié)點分為數(shù)據(jù)存儲區(qū)和鏈接區(qū),數(shù)據(jù)區(qū)存儲數(shù)據(jù),鏈接區(qū)鏈接下一個節(jié)點
item: 存儲數(shù)據(jù)的地方
next: 鏈接下一個節(jié)點
注意: 單向循環(huán)鏈表是首位鏈接,即尾部的節(jié)點要和頭部的節(jié)點鏈接
單向鏈表操作
1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節(jié)點
8、查找節(jié)點是否存在
代碼實現(xiàn)
# Functions ?函數(shù)聲明 class Node(): ? ? """實例化節(jié)點類""" ? ? def __init__(self, item): ? ? ? ? self.item = item ? ? ? ? self.next = None class Linklist(): ? ? """ ? ? 存放節(jié)點類 ? ? """ ? ? def __init__(self): ? ? ? ? self.head = None ? ? # 1. 鏈表是否為空 ? ? def is_empty(self): ? ? ? ? return self.head == None ? ? # 2. 鏈表的長度 ? ? def length(self): ? ? ? ? """ ? ? ? ? 返回鏈表的長度 ? ? ? ? 遍歷所有的節(jié)點,使用計數(shù)器計數(shù) ? ? ? ? 1、鏈表為空情況 ? ? ? ? """ ? ? ? ? # 實例化節(jié)點 ? ? ? ? cur = self.head ? ? ? ? if self.is_empty(): ? ? ? ? ? ? return 0 ? ? ? ? else: ? ? ? ? ? ? # 計數(shù) ? ? ? ? ? ? count = 1 ? ? ? ? ? ? # 遍歷鏈表 ? ? ? ? ? ? while cur.next != self.head: ? ? ? ? ? ? ? ? count+=1 ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? return count ? ? # 3. 遍歷鏈表 ? ? def travel(self): ? ? ? ? """ ? ? ? ? 遍歷鏈表,獲取所有的數(shù)據(jù) ? ? ? ? 實例游標(biāo),遍歷數(shù)據(jù),輸出數(shù)據(jù) ? ? ? ? 1、 空鏈表情況 ? ? ? ? 2、 只有頭部節(jié)點情況 ? ? ? ? 3、 只有尾部節(jié)點情況 ? ? ? ? """ ? ? ? ? # 實例化游標(biāo) ? ? ? ? cur = self.head ? ? ? ? if self.is_empty(): ? ? ? ? ? ? return None ? ? ? ? else: ? ? ? ? ? ? # 遍歷數(shù)據(jù) ? ? ? ? ? ? while cur.next != self.head: ? ? ? ? ? ? ? ? print(cur.item, end=' ') ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? # 最后一個節(jié)點要單獨輸出 ? ? ? ? ? ? print(cur.item) ? ? # 4. 鏈表頭部添加元素 ? ? def add(self, item): ? ? ? ? """ ? ? ? ? 往鏈表頭部添加數(shù)據(jù) ? ? ? ? 分析 ? ? ? ? 鏈表為空 ? ? ? ? ? ? self.head 直接指向node, 再講node指向自己 ? ? ? ? 鏈表不為空 ? ? ? ? ? ? node.next = self.head ? ? ? ? """ ? ? ? ? # 實例化游標(biāo) ? ? ? ? cur = self.head ? ? ? ? # 實例化節(jié)點 ? ? ? ? node = Node(item) ? ? ? ? # 判斷是否為空 ? ? ? ? if self.is_empty(): ? ? ? ? ? ? self.head = node ? ? ? ? ? ? node.next = node ? ? ? ? else: ? ? ? ? ? ? # 不為空的情況 ? ? ? ? ? ? # 要將最后一個節(jié)點指向node ? ? ? ? ? ? while cur.next != self.head: ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? node.next = self.head ? ? ? ? ? ? self.head = node ? ? ? ? ? ? cur.next = node ? ? # 5. 鏈表尾部添加元素 ? ? def append(self, item): ? ? ? ? """ ? ? ? ? 往尾部添加數(shù)據(jù) ? ? ? ? 分析 ? ? ? ? 實例化節(jié)點,再實例化游標(biāo)先指向最后一個節(jié)點 ? ? ? ? 調(diào)換指向 ? ? ? ? 1、空鏈表情況 ? ? ? ? 2、只有一個鏈表情況 ? ? ? ? """ ? ? ? ? # 實例化節(jié)點 ? ? ? ? node = Node(item) ? ? ? ? # 實例化游標(biāo) ? ? ? ? cur = self.head ? ? ? ? # 判斷是否為空 ? ? ? ? if self.is_empty(): ? ? ? ? ? ? self.add(item) ? ? ? ? else: ? ? ? ? ? ? # 不為空的情況,移動游標(biāo)指向最后一個節(jié)點 ? ? ? ? ? ? while cur.next != self.head: ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? node.next = self.head ? ? ? ? ? ? cur.next = node ? ? ? ? ? ? pass ? ? # 6. 鏈表指定位置添加元素 ? ? def insert(self, index, item): ? ? ? ? """ ? ? ? ? 指定位置添加數(shù)據(jù) ? ? ? ? 實例化節(jié)點, 實例化游標(biāo)指向索引的數(shù)據(jù),更改指向 ? ? ? ? 位置大小 ? ? ? ? 鏈表是否為空 ? ? ? ? """ ? ? ? ? # 實例化節(jié)點 ? ? ? ? node = Node(item) ? ? ? ? # 實例化游標(biāo) ? ? ? ? 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: ? ? ? ? ? ? ? ? # 移動游標(biāo),指向指定的索引位置 ? ? ? ? ? ? ? ? count = 0 ? ? ? ? ? ? ? ? while count < index-1: ? ? ? ? ? ? ? ? ? ? count+=1 ? ? ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? ? ? node.next = cur.next ? ? ? ? ? ? ? ? cur.next = node ? ? ? ? ? ? pass ? ? # 7. 鏈表刪除節(jié)點 ? ? def remove(self, item): ? ? ? ? """ ? ? ? ? 刪除指定的節(jié)點 ? ? ? ? 實例化游標(biāo),遍歷鏈表插件這個節(jié)點是否存在,存在則更改指向 ? ? ? ? 不存在,則不修改 ? ? ? ? 空鏈表情況 ? ? ? ? 頭節(jié)點情況 ? ? ? ? 尾結(jié)點情況 ? ? ? ? """ ? ? ? ? # 實例化游標(biāo) ? ? ? ? cur = self.head ? ? ? ? if self.is_empty(): ? ? ? ? ? ? return None ? ? ? ? else: ? ? ? ? ? ? # 不為空,遍歷鏈表,對比數(shù)據(jù)是否相等 ? ? ? ? ? ? # 如果頭節(jié)點是要刪除的數(shù)據(jù) ? ? ? ? ? ? if cur.item == item: ? ? ? ? ? ? ? ? self.head=cur.next ? ? ? ? ? ? ? ? # 找出最后的節(jié)點,將最后的節(jié)點指向,刪除后面的那個節(jié)點 ? ? ? ? ? ? ? ? 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. 查找節(jié)點是否存在 ? ? def search(self, item): ? ? ? ? """ ? ? ? ? 查找該節(jié)點是否存在 ? ? ? ? 實例化游標(biāo),遍歷所有的節(jié)點 ? ? ? ? 查看當(dāng)前節(jié)點的數(shù)據(jù)是否和item 相等 ? ? ? ? 空鏈表 ? ? ? ? 頭節(jié)點 ? ? ? ? 尾結(jié)點 ? ? ? ? """ ? ? ? ? # 實例化游標(biāo) ? ? ? ? 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
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- Python數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表詳解
- python實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中雙向循環(huán)鏈表操作的示例
- python/golang實現(xiàn)循環(huán)鏈表的示例代碼
- python單向循環(huán)鏈表原理與實現(xiàn)方法示例
- Python雙向循環(huán)鏈表實現(xiàn)方法分析
- Python實現(xiàn)的單向循環(huán)鏈表功能示例
- Python數(shù)據(jù)結(jié)構(gòu)與算法之鏈表定義與用法實例詳解【單鏈表、循環(huán)鏈表】
- python雙向鏈表實例詳解
- Python實現(xiàn)雙向鏈表基本操作
- python雙向循環(huán)鏈表實例詳解
相關(guān)文章
python Django編寫接口并用Jmeter測試的方法
這篇文章主要介紹了python Django編寫接口并用Jmeter測試,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07Python列表常見操作詳解(獲取,增加,刪除,修改,排序等)
這篇文章主要介紹了Python列表常見操作,結(jié)合實例形式總結(jié)分析了Python列表常見的獲取、增加、刪除、修改、排序、計算等相關(guān)操作技巧,需要的朋友可以參考下2019-02-02Python實現(xiàn)的序列化和反序列化二叉樹算法示例
這篇文章主要介紹了Python實現(xiàn)的序列化和反序列化二叉樹算法,結(jié)合實例形式分析了Python二叉樹的構(gòu)造、遍歷、序列化、反序列化等相關(guān)操作技巧,需要的朋友可以參考下2019-03-03使用Python+Matplotlib制作時序動態(tài)圖
時序圖是一個二維圖,橫軸表示對象,縱軸表示時間,消息在各對象之間橫向傳遞,依照時間順序縱向排列,可以直觀的描述并發(fā)進(jìn)程,所以本文就使用Python和Matplotlib制作一個簡單的時許動態(tài)圖,感興趣的跟著小編一起來看看吧2023-07-07