python單向鏈表實例詳解
使用python實現(xiàn)單向鏈表,供大家參考,具體內(nèi)容如下
單向鏈表:是將所有的數(shù)據(jù)作為一個個節(jié)點,將所有的節(jié)點鏈接在一起。每一個節(jié)點中又分為: 存儲數(shù)據(jù)區(qū),鏈接區(qū)
存儲數(shù)據(jù)區(qū): 存儲具體的數(shù)據(jù)
鏈接區(qū): 指向下一個節(jié)點
分析實現(xiàn):
1、 分析:根據(jù)鏈表的特性,首先要存放有數(shù)據(jù)的容器,還要有存放節(jié)點的容器
2、 節(jié)點類中:要有數(shù)據(jù)區(qū)和next區(qū)
3、 鏈表類中:存放所有節(jié)點
單鏈表操作
1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節(jié)點
8、查找節(jié)點是否存在
代碼實現(xiàn)
# Functions ?函數(shù)聲明 class Node(): ? ? """ ? ? 存放節(jié)點類 ? ? 每次調(diào)用該類,實例化一個節(jié)點 ? ? 默認每個節(jié)點中有數(shù)據(jù)區(qū),next區(qū)。 ? ? 數(shù)據(jù)區(qū)為該數(shù)據(jù),next區(qū)為空 ? ? """ ? ? def __init__(self, item,next=None): ? ? ? ? self.item = item ? ? ? ? self.next = next ? ? ? ? pass class Linklist(): ? ? """ ? ? 存放數(shù)據(jù)類 ? ? 將所有的節(jié)點存放起來的容器 ? ? 首先,默認鏈表為空,在這里需要有一個頭節(jié)點,默認頭節(jié)點為空 ? ? """ ? ? def __init__(self, head=None): ? ? ? ? self.head = head ? ? def is_empty(self): ? ? ? ? return self.head == None ? ? def append(self, item): ? ? ? ? """ ? ? ? ? 往鏈表尾部添加數(shù)據(jù) ? ? ? ? 1、實例化游標:使用游標指向每一個數(shù)據(jù),檢索數(shù)據(jù)和判斷數(shù)據(jù)next是否為空 ? ? ? ? 2、移動游標,從頭節(jié)點開始,每次使用self.next移動,以為next指向的就是下一個數(shù)據(jù) ? ? ? ? 3、添加數(shù)據(jù),首先判斷鏈表是否為空,為空的情況下,直接將頭節(jié)點等于node數(shù)據(jù) ? ? ? ? 4、如果不為空,需要從頭節(jié)點開始,移動游標,判斷游標指向的next是否為空 ? ? ? ? 5、使用循環(huán)不停的移動節(jié)點,當遇到節(jié)點中的next為空的情況下停止移動 ? ? ? ? 6、循環(huán)條件: 當 條件 != None, 進入循環(huán)獲取,當cur為空時就不會進入循環(huán),所以在這里要使用 cur != None ? ? ? ? """ ? ? ? ? # 首先要實例化一個節(jié)點 ? ? ? ? node = Node(item) ? ? ? ? # 如果鏈表為空 ? ? ? ? if self.is_empty(): ? ? ? ? ? ? # 直接將頭節(jié)點的next添加node ? ? ? ? ? ? self.head = node ? ? ? ? else: ? ? ? ? ? ? # 實例化一個游標 ? ? ? ? ? ? cur = self.head ? ? ? ? ? ? while cur.next != None: ? ? ? ? ? ? ? ? # 移動游標,得到最后一個游標的數(shù)據(jù) ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? # 將移動后的數(shù)據(jù)的下一個next添加上 node ? ? ? ? ? ? cur.next=node ? ? ? ? ? ? pass ? ? def travel(self): ? ? ? ? """遍歷數(shù)據(jù)""" ? ? ? ? # 實例化一個游標 ? ? ? ? cur = self.head ? ? ? ? # 數(shù)據(jù)鏈為空的情況 ? ? ? ? if self.is_empty(): ? ? ? ? ? ? print('') ? ? ? ? else: ? ? ? ? ? ? # 獲取每個數(shù)據(jù)區(qū)中的數(shù)據(jù) ? ? ? ? ? ? # 移動游標,每移動一次,輸出一次數(shù)據(jù)區(qū)內(nèi)的數(shù)據(jù) ? ? ? ? ? ? while cur != None: ? ? ? ? ? ? ? ? print(cur.item, end=' ') ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? print() ? ? def length(self): ? ? ? ? """返回鏈表的長度""" ? ? ? ? # 實例化游標 ? ? ? ? cur = self.head ? ? ? ? # 計數(shù),這里對空鏈表進行判斷,如果是鏈表,則不會進入循環(huán),直接輸出 0 ? ? ? ? count = 0 ? ? ? ? # 移動游標,獲取下一個數(shù)據(jù),然后讓count +=1 ? ? ? ? while cur != None: ? ? ? ? ? ? # 計數(shù) ? ? ? ? ? ? count+=1 ? ? ? ? ? ? # 移動游標 ? ? ? ? ? ? cur = cur.next ? ? ? ? return count ? ? def add(self, item): ? ? ? ? """ ? ? ? ? 頭部添加數(shù)據(jù) ? ? ? ? 分析: 將數(shù)據(jù)添加到第一個節(jié)點當中 ? ? ? ? 1、 需要先將node的next指向 原第一個節(jié)點,這原第一個節(jié)點就是self.head ? ? ? ? 2、 再講self.head指向node進行連接 ? ? ? ? """ ? ? ? ? # 先實例化節(jié)點 ? ? ? ? node = Node(item) ? ? ? ? # 將數(shù)據(jù)添加到頭部當中 ? ? ? ? node.next=self.head ? ? ? ? self.head=node ? ? def insert(self, index, item): ? ? ? ? """ ? ? ? ? 指定位置添加數(shù)據(jù) ? ? ? ? 分析: ? ? ? ? 1、首先要找到,該位置的數(shù)據(jù) ? ? ? ? 2、將要添加的數(shù)據(jù)next等于 原位置的next數(shù)據(jù) ? ? ? ? 3、原數(shù)據(jù)的 next等于node新數(shù)據(jù) ? ? ? ? """ ? ? ? ? if index<=0: ? ? ? ? ? ? # 如果輸入的索引小于或者等于O,默認使用頭插發(fā) ? ? ? ? ? ? self.add(item) ? ? ? ? elif index>self.length(): ? ? ? ? ? ? # 如果輸入的索引大于鏈表的長度,使用尾插法 ? ? ? ? ? ? self.append(item) ? ? ? ? else: ? ? ? ? ? ? # 實例化數(shù)據(jù)節(jié)點 ? ? ? ? ? ? node = Node(item) ? ? ? ? ? ? # 找到該數(shù)據(jù)的位置 ? ? ? ? ? ? # 實例化一個游標 ? ? ? ? ? ? cur = self.head ? ? ? ? ? ? # 計數(shù) ? ? ? ? ? ? conent = 0 ? ? ? ? ? ? while conent<(index-1): ? ? ? ? ? ? ? ? conent+=1 ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? node.next=cur.next ? ? ? ? ? ? cur.next=node ? ? def search(self, item): ? ? ? ? """ ? ? ? ? 查詢指定的數(shù)據(jù)是否存在 ? ? ? ? 分析: 查詢指定的數(shù)據(jù),需要對整個鏈表掃描,判斷這個數(shù)據(jù)是否等的該節(jié)點中的數(shù)據(jù) ? ? ? ? """ ? ? ? ? # 實例化一個游標 ? ? ? ? cur = self.head ? ? ? ? # 進行判斷是否相等 ? ? ? ? while cur != None: ? ? ? ? ? ? # 判斷 ? ? ? ? ? ? if cur.item == item: ? ? ? ? ? ? ? ? return True ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? pass ? ? ? ? # 否則返回False ? ? ? ? return False ? ? def remove(self, item): ? ? ? ? """ ? ? ? ? 移除指定的數(shù)據(jù) ? ? ? ? 分析: ? ? ? ? 1、刪除數(shù)據(jù),需要首先判斷數(shù)據(jù)是否存在 ? ? ? ? 2、找到該數(shù)據(jù)所在的位置,將該數(shù)據(jù)的上一個數(shù)據(jù)的next指向自己的next ? ? ? ? 3、如何獲取該數(shù)據(jù)的指向,和上一個數(shù)據(jù)的指向 ? ? ? ? 4、需要定義兩個指針 ? ? ? ? 5、先將兩個指針相等,再講一個指針先移動一次,再同時移動 ? ? ? ? """ ? ? ? ? # 先找到該數(shù)據(jù) ? ? ? ? cur = self.head ? ? ? ? por = None ? ? ? ? while cur != None: ? ? ? ? ? ? if cur.item==item: ? ? ? ? ? ? ? ? # 要判斷是否為第一個節(jié)點 ? ? ? ? ? ? ? ? if cur == self.head: ? ? ? ? ? ? ? ? ? ? self.head = cur.next ? ? ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? ? ? por.next = cur.next ? ? ? ? ? ? ? ? break ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? # 如果在當前節(jié)點中沒有相等的,將節(jié)點進行移動 ? ? ? ? ? ? ? ? # 移動要注意,現(xiàn)將兩個游標相等,再講另一個游標移動一次 ? ? ? ? ? ? ? ? por = cur ? ? ? ? ? ? ? ? cur = cur.next
測試運行
# 程序的入口 if __name__ == "__main__": ? ? s = Linklist() ? ? s.append(100) ? ? s.append(200) ? ? s.append(300) ? ? s.add(1) ? ? s.add(12) ? ? s.insert(-1,6) ? ?? ? ? s.travel() ? ? ? # ?6 12 1 100 200 300? ? ? print(s.length()) ?# 6 ? ? print(s.search(11)) # False ? ? s.remove(12) ? ? s.travel() ? ? ? # 6 1 100 200 300? ? ? print(s.length()) ?# 5 ? ? print(s.search(11)) # False ? ? pass
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
Django實現(xiàn)將views.py中的數(shù)據(jù)傳遞到前端html頁面,并展示
這篇文章主要介紹了Django實現(xiàn)將views.py中的數(shù)據(jù)傳遞到前端html頁面并展示,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-03-03python實現(xiàn)的系統(tǒng)實用log類實例
這篇文章主要介紹了python實現(xiàn)的系統(tǒng)實用log類,實例分析了Python基于logging模塊實現(xiàn)日志類的相關(guān)技巧,需要的朋友可以參考下2015-06-06python中自定義異常/raise關(guān)鍵字拋出異常的案例解析
在編程過程中合理的使用異??梢允沟贸绦蛘5膱?zhí)行,本篇文章給大家介紹python中自定義異常/raise關(guān)鍵字拋出異常案例解析,需要的朋友可以參考下2024-01-01Python圖形化界面基礎(chǔ)篇之如何使用彈出窗口和對話框
對于Python程序員來說,處理彈出窗口似乎并不是一個常見的任務,這篇文章主要給大家介紹了關(guān)于Python圖形化界面基礎(chǔ)篇之如何使用彈出窗口和對話框的相關(guān)資料,需要的朋友可以參考下2024-03-03