Python 實(shí)現(xiàn)鏈表實(shí)例代碼
更新時(shí)間：2017年04月07日 09:30:48 投稿：lqh
這篇文章主要介紹了Python 實(shí)現(xiàn)鏈表實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下
Python 實(shí)現(xiàn)鏈表實(shí)例代碼
前言
算法和數(shù)據(jù)結(jié)構(gòu)是一個(gè)亙古不變的話題，作為一個(gè)程序員，掌握常用的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)是非常非常的有必要的。
實(shí)現(xiàn)清單
實(shí)現(xiàn)鏈表，本質(zhì)上和語(yǔ)言是無(wú)關(guān)的。但是靈活度卻和實(shí)現(xiàn)它的語(yǔ)言密切相關(guān)。今天用Python來(lái)實(shí)現(xiàn)一下，包含如下操作：
['addNode(self, data)'] ['append(self, value)'] ['prepend(self, value)'] ['insert(self, index, value)'] ['delNode(self, index)'] ['delValue(self, value)'] ['isempty(self)'] ['truncate(self)'] ['getvalue(self, index)'] ['peek(self)'] ['pop(self)'] ['reverse(self)'] ['delDuplecate(self)'] ['updateNode(self, index, value)'] ['size(self)'] ['print(self)']
生成這樣的一個(gè)方法清單肯定是不能手動(dòng)寫(xiě)了，要不然得多麻煩啊，于是我寫(xiě)了個(gè)程序，來(lái)匹配這些自己實(shí)現(xiàn)的方法。代碼比較簡(jiǎn)單，核心思路就是匹配源文件的每一行，找到符合匹配規(guī)則的內(nèi)容，并添加到總的結(jié)果集中。
代碼如下：
# coding: utf8
# @Author: 郭 璞
# @File: getmethods.py
# @Time: 2017/4/5
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 獲取一個(gè)模塊或者類(lèi)中的所有方法及參數(shù)列表
import re
def parse(filepath, repattern):
with open(filepath, 'rb') as f:
lines = f.readlines()
# 預(yù)解析正則
rep = re.compile(repattern)
# 創(chuàng)建保存方法和參數(shù)列表的結(jié)果集列表
result = []
# 開(kāi)始正式的匹配實(shí)現(xiàn)
for line in lines:
res = re.findall(rep, str(line))
print("{}的匹配結(jié)果{}".format(str(line), res))
if len(res)!=0 or res is not None:
result.append(res)
else:
continue
return [item for item in result if item !=[]]
if __name__ == '__main__':
repattern = "def (.[^_0-9]+\(.*?\)):"
filepath = './SingleChain.py'
result = parse(filepath, repattern)
for item in result:
print(str(item))
鏈表實(shí)現(xiàn)
# coding: utf8
# @Author: 郭 璞
# @File: SingleChain.py
# @Time: 2017/4/5
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 單鏈表實(shí)現(xiàn)
class Node(object):
def __init__(self, data, next):
self.data = data
self.next = next
class LianBiao(object):
def __init__(self):
self.root = None
# 給單鏈表添加元素節(jié)點(diǎn)
def addNode(self, data):
if self.root==None:
self.root = Node(data=data, next=None)
return self.root
else:
# 有頭結(jié)點(diǎn)，則需要遍歷到尾部節(jié)點(diǎn)，進(jìn)行鏈表增加操作
cursor = self.root
while cursor.next!= None:
cursor = cursor.next
cursor.next = Node(data=data, next=None)
return self.root
# 在鏈表的尾部添加新節(jié)點(diǎn)，底層調(diào)用addNode方法即可
def append(self, value):
self.addNode(data=value)
# 在鏈表首部添加節(jié)點(diǎn)
def prepend(self, value):
if self.root == None:
self.root = Node(value, None)
else:
newroot = Node(value, None)
# 更新root索引
newroot.next = self.root
self.root = newroot
# 在鏈表的指定位置添加節(jié)點(diǎn)
def insert(self, index, value):
if self.root == None:
return
if index<=0 or index >self.size():
print('index %d 非法， 應(yīng)該審視一下您的插入節(jié)點(diǎn)在整個(gè)鏈表的位置！')
return
elif index==1:
# 如果index==1， 則在鏈表首部添加即可
self.prepend(value)
elif index == self.size()+1:
# 如果index正好比當(dāng)前鏈表長(zhǎng)度大一，則添加在尾部即可
self.append(value)
else:
# 如此，在鏈表中部添加新節(jié)點(diǎn)，直接進(jìn)行添加即可。需要使用計(jì)數(shù)器來(lái)維護(hù)插入未知
counter = 2
pre = self.root
cursor = self.root.next
while cursor!=None:
if counter == index:
temp = Node(value, None)
pre.next = temp
temp.next = cursor
break
else:
counter += 1
pre = cursor
cursor = cursor.next
# 刪除指定位置上的節(jié)點(diǎn)
def delNode(self, index):
if self.root == None:
return
if index<=0 or index > self.size():
return
# 對(duì)第一個(gè)位置需要小心處理
if index == 1:
self.root = self.root.next
else:
pre = self.root
cursor = pre.next
counter = 2
while cursor!= None:
if index == counter:
print('can be here!')
pre.next = cursor.next
break
else:
pre = cursor
cursor = cursor.next
counter += 1
# 刪除值為value的鏈表節(jié)點(diǎn)元素
def delValue(self, value):
if self.root == None:
return
# 對(duì)第一個(gè)位置需要小心處理
if self.root.data == value:
self.root = self.root.next
else:
pre = self.root
cursor = pre.next
while cursor!=None:
if cursor.data == value:
pre.next = cursor.next
# 千萬(wàn)記得更新這個(gè)節(jié)點(diǎn)，否則會(huì)出現(xiàn)死循環(huán)。。。
cursor = cursor.next
continue
else:
pre = cursor
cursor = cursor.next
# 判斷鏈表是否為空
def isempty(self):
if self.root == None or self.size()==0:
return True
else:
return False
# 刪除鏈表及其內(nèi)部所有元素
def truncate(self):
if self.root == None or self.size()==0:
return
else:
cursor = self.root
while cursor!= None:
cursor.data = None
cursor = cursor.next
self.root = None
cursor = None
# 獲取指定位置的節(jié)點(diǎn)的值
def getvalue(self, index):
if self.root is None or self.size()==0:
print('當(dāng)前鏈表為空！')
return None
if index<=0 or index>self.size():
print("index %d不合法！"%index)
return None
else:
counter = 1
cursor = self.root
while cursor is not None:
if index == counter:
return cursor.data
else:
counter += 1
cursor = cursor.next
# 獲取鏈表尾部的值，且不刪除該尾部節(jié)點(diǎn)
def peek(self):
return self.getvalue(self.size())
# 獲取鏈表尾部節(jié)點(diǎn)的值，并刪除該尾部節(jié)點(diǎn)
def pop(self):
if self.root is None or self.size()==0:
print('當(dāng)前鏈表已經(jīng)為空！')
return None
elif self.size()==1:
top = self.root.data
self.root = None
return top
else:
pre = self.root
cursor = pre.next
while cursor.next is not None:
pre = cursor
cursor = cursor.next
top = cursor.data
cursor = None
pre.next = None
return top
# 單鏈表逆序?qū)崿F(xiàn)
def reverse(self):
if self.root is None:
return
if self.size()==1:
return
else:
# post = None
pre = None
cursor = self.root
while cursor is not None:
# print('逆序操作逆序操作')
post = cursor.next
cursor.next = pre
pre = cursor
cursor = post
# 千萬(wàn)不要忘記了把逆序后的頭結(jié)點(diǎn)賦值給root，否則無(wú)法正確顯示
self.root = pre
# 刪除鏈表中的重復(fù)元素
def delDuplecate(self):
# 使用一個(gè)map來(lái)存放即可，類(lèi)似于變形的“桶排序”
dic = {}
if self.root == None:
return
if self.size() == 1:
return
pre = self.root
cursor = pre.next
dic = {}
# 為字典賦值
temp = self.root
while temp!=None:
dic[str(temp.data)] = 0
temp = temp.next
temp = None
# 開(kāi)始實(shí)施刪除重復(fù)元素的操作
while cursor!=None:
if dic[str(cursor.data)] == 1:
pre.next = cursor.next
cursor = cursor.next
else:
dic[str(cursor.data)] += 1
pre = cursor
cursor = cursor.next
# 修改指定位置節(jié)點(diǎn)的值
def updateNode(self, index, value):
if self.root == None:
return
if index<0 or index>self.size():
return
if index == 1:
self.root.data = value
return
else:
cursor = self.root.next
counter = 2
while cursor!=None:
if counter == index:
cursor.data = value
break
cursor = cursor.next
counter += 1
# 獲取單鏈表的大小
def size(self):
counter = 0
if self.root == None:
return counter
else:
cursor = self.root
while cursor!=None:
counter +=1
cursor = cursor.next
return counter
# 打印鏈表自身元素
def print(self):
if(self.root==None):
return
else:
cursor = self.root
while cursor!=None:
print(cursor.data, end='\t')
cursor = cursor.next
print()
if __name__ == '__main__':
# 創(chuàng)建一個(gè)鏈表對(duì)象
lianbiao = LianBiao()
# 判斷當(dāng)前鏈表是否為空
print("鏈表為空%d"%lianbiao.isempty())
# 判斷當(dāng)前鏈表是否為空
lianbiao.addNode(1)
print("鏈表為空%d"%lianbiao.isempty())
# 添加一些節(jié)點(diǎn)，方便操作
lianbiao.addNode(2)
lianbiao.addNode(3)
lianbiao.addNode(4)
lianbiao.addNode(6)
lianbiao.addNode(5)
lianbiao.addNode(6)
lianbiao.addNode(7)
lianbiao.addNode(3)
# 打印當(dāng)前鏈表所有值
print('打印當(dāng)前鏈表所有值')
lianbiao.print()
# 測(cè)試對(duì)鏈表求size的操作
print("鏈表的size: "+str(lianbiao.size()))
# 測(cè)試指定位置節(jié)點(diǎn)值的獲取
print('測(cè)試指定位置節(jié)點(diǎn)值的獲取')
print(lianbiao.getvalue(1))
print(lianbiao.getvalue(lianbiao.size()))
print(lianbiao.getvalue(7))
# 測(cè)試刪除鏈表中指定值， 可重復(fù)性刪除
print('測(cè)試刪除鏈表中指定值， 可重復(fù)性刪除')
lianbiao.delNode(4)
lianbiao.print()
lianbiao.delValue(3)
lianbiao.print()
# 去除鏈表中的重復(fù)元素
print('去除鏈表中的重復(fù)元素')
lianbiao.delDuplecate()
lianbiao.print()
# 指定位置的鏈表元素的更新測(cè)試
print('指定位置的鏈表元素的更新測(cè)試')
lianbiao.updateNode(6, 99)
lianbiao.print()
# 測(cè)試在鏈表首部添加節(jié)點(diǎn)
print('測(cè)試在鏈表首部添加節(jié)點(diǎn)')
lianbiao.prepend(77)
lianbiao.prepend(108)
lianbiao.print()
# 測(cè)試在鏈表尾部添加節(jié)點(diǎn)
print('測(cè)試在鏈表尾部添加節(jié)點(diǎn)')
lianbiao.append(99)
lianbiao.append(100)
lianbiao.print()
# 測(cè)試指定下標(biāo)的插入操作
print('測(cè)試指定下標(biāo)的插入操作')
lianbiao.insert(1, 10010)
lianbiao.insert(3, 333)
lianbiao.insert(lianbiao.size(), 99999)
lianbiao.print()
# 測(cè)試peek 操作
print('測(cè)試peek 操作')
print(lianbiao.peek())
lianbiao.print()
# 測(cè)試pop 操作
print('測(cè)試pop 操作')
print(lianbiao.pop())
lianbiao.print()
# 測(cè)試單鏈表的逆序輸出
print('測(cè)試單鏈表的逆序輸出')
lianbiao.reverse()
lianbiao.print()
# 測(cè)試鏈表的truncate操作
print('測(cè)試鏈表的truncate操作')
lianbiao.truncate()
lianbiao.print()
代碼運(yùn)行的結(jié)果如何呢？是否能滿足我們的需求，且看打印的結(jié)果:
D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py 鏈表為空1 鏈表為空0 打印當(dāng)前鏈表所有值 1 2 3 4 6 5 6 7 3 鏈表的size: 9 測(cè)試指定位置節(jié)點(diǎn)值的獲取 1 3 6 測(cè)試刪除鏈表中指定值， 可重復(fù)性刪除 can be here! 1 2 3 6 5 6 7 3 1 2 6 5 6 7 去除鏈表中的重復(fù)元素 1 2 6 5 7 指定位置的鏈表元素的更新測(cè)試 1 2 6 5 7 測(cè)試在鏈表首部添加節(jié)點(diǎn) 108 77 1 2 6 5 7 測(cè)試在鏈表尾部添加節(jié)點(diǎn) 108 77 1 2 6 5 7 99 100 測(cè)試指定下標(biāo)的插入操作 10010 108 333 77 1 2 6 5 7 99 99999 100 測(cè)試peek 操作 100 10010 108 333 77 1 2 6 5 7 99 99999 100 測(cè)試pop 操作 100 10010 108 333 77 1 2 6 5 7 99 99999 測(cè)試單鏈表的逆序輸出 99999 99 7 5 6 2 1 77 333 108 10010 測(cè)試鏈表的truncate操作 Process finished with exit code 0
剛好實(shí)現(xiàn)了目標(biāo)需求。
總結(jié)
今天的內(nèi)容還是比較基礎(chǔ)，也沒(méi)什么難點(diǎn)。但是看懂和會(huì)寫(xiě)還是兩碼事，沒(méi)事的時(shí)候?qū)憣?xiě)這樣的代碼還是很有收獲的。
您可能感興趣的文章:
- Python3實(shí)現(xiàn)的判斷環(huán)形鏈表算法示例
- 使用python實(shí)現(xiàn)鏈表操作
- python單鏈表實(shí)現(xiàn)代碼實(shí)例
- Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之鏈表詳解
- 淺談Python單向鏈表的實(shí)現(xiàn)
- Python單鏈表的簡(jiǎn)單實(shí)現(xiàn)方法
- Python數(shù)據(jù)結(jié)構(gòu)與算法之列表（鏈表，linked list）簡(jiǎn)單實(shí)現(xiàn)
- Python實(shí)現(xiàn)針對(duì)給定單鏈表刪除指定節(jié)點(diǎn)的方法
- python雙向鏈表實(shí)現(xiàn)實(shí)例代碼
- Python實(shí)現(xiàn)環(huán)形鏈表
相關(guān)文章
這篇文章主要介紹了詳解python tkinter 圖片插入問(wèn)題，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
Python爬蟲(chóng)實(shí)戰(zhàn)項(xiàng)目掌握酷狗音樂(lè)的加密過(guò)程
在常見(jiàn)的幾個(gè)音樂(lè)網(wǎng)站里，酷狗可以說(shuō)是最好爬取的啦，什么彎都沒(méi)有，所以最適合小白入門(mén)爬蟲(chóng)，本篇針對(duì)爬蟲(chóng)零基礎(chǔ)的小白，所以每一步驟我都截圖并詳細(xì)解釋了，其實(shí)我自己看著都啰嗦，歸根到底就是兩個(gè)步驟的請(qǐng)求，還請(qǐng)大佬繞路勿噴2021-09-09
python interpret庫(kù)訓(xùn)練模型助力機(jī)器學(xué)習(xí)
這篇文章主要為大家介紹了python interpret庫(kù)訓(xùn)練模型功能特性,為你的機(jī)器學(xué)習(xí)提供便捷的路徑,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01
利用python清除移動(dòng)硬盤(pán)中的臨時(shí)文件
本篇文章的目的是在移動(dòng)硬盤(pán)插入到電腦的同時(shí)，利用Python自動(dòng)化和Windows服務(wù)刪除掉這些臨時(shí)文件。感興趣的朋友可以了解下2020-10-10
Python使用xlrd和xlwt實(shí)現(xiàn)自動(dòng)化操作Excel
這篇文章主要介紹了Python使用xlrd和xlwt實(shí)現(xiàn)自動(dòng)化操作Excel，xlwt只能對(duì)Excel進(jìn)行寫(xiě)操作。xlwt和xlrd不光名字像，連很多函數(shù)和操作格式也是完全相2022-08-08
這篇文章主要介紹了Python守護(hù)線程用法,結(jié)合具體實(shí)例形式分析了Python守護(hù)線程的功能、使用方法與相關(guān)操作技巧,需要的朋友可以參考下2017-06-06
使用wxPython和ECharts實(shí)現(xiàn)生成和保存HTML圖表
wxPython是一個(gè)基于wxWidgets的Python?GUI庫(kù)，ECharts是一個(gè)用于數(shù)據(jù)可視化的JavaScript庫(kù)，本文主要為大家介紹了如何使用wxPython和ECharts庫(kù)來(lái)生成和保存HTML圖表，感興趣的可以學(xué)習(xí)一下2023-08-08
Python解決N階臺(tái)階走法問(wèn)題的方法分析
這篇文章主要介紹了Python解決N階臺(tái)階走法問(wèn)題的方法,簡(jiǎn)單描述了走臺(tái)階問(wèn)題,并結(jié)合實(shí)例形式分析了Python使用遞歸與遞推算法解決走臺(tái)階問(wèn)題的相關(guān)操作技巧,需要的朋友可以參考下2017-12-12
Python中的random函數(shù)實(shí)例詳解
random模塊提供生成偽隨機(jī)數(shù)的函數(shù)，在使用時(shí)需要導(dǎo)入random模塊，這篇文章主要介紹了Python中的random函數(shù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-02-02
Python數(shù)據(jù)可視化:冪律分布實(shí)例詳解
今天小編就為大家分享一篇Python數(shù)據(jù)可視化:冪律分布實(shí)例詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12