• • 前言
  • 實(shí)現(xiàn)清單
  • 鏈表實(shí)現(xiàn)
  • 總結(jié)

前言

算法和數(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)寫了，要不然得多麻煩啊，于是我寫了個(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è)模塊或者類中的所有方法及參數(shù)列表import redef 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:continuereturn [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 = dataself.next = nextclass 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.rootelse:# 有頭結(jié)點(diǎn)，則需要遍歷到尾部節(jié)點(diǎn)，進(jìn)行鏈表增加操作cursor = self.rootwhile cursor.next!= None:cursor = cursor.nextcursor.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.rootself.root = newroot# 在鏈表的指定位置添加節(jié)點(diǎn)def insert(self, index, value):if self.root == None:returnif index<=0 or index >self.size():print('index %d 非法， 應(yīng)該審視一下您的插入節(jié)點(diǎn)在整個(gè)鏈表的位置！')returnelif 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 = 2pre = self.rootcursor = self.root.nextwhile cursor!=None:if counter == index:temp = Node(value, None)pre.next = temptemp.next = cursorbreakelse:counter += 1pre = cursorcursor = cursor.next# 刪除指定位置上的節(jié)點(diǎn)def delNode(self, index):if self.root == None:returnif index<=0 or index > self.size():return# 對(duì)第一個(gè)位置需要小心處理if index == 1:self.root = self.root.nextelse:pre = self.rootcursor = pre.nextcounter = 2while cursor!= None:if index == counter:print('can be here!')pre.next = cursor.nextbreakelse:pre = cursorcursor = cursor.nextcounter += 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.nextelse:pre = self.rootcursor = pre.nextwhile cursor!=None:if cursor.data == value:pre.next = cursor.next# 千萬(wàn)記得更新這個(gè)節(jié)點(diǎn)，否則會(huì)出現(xiàn)死循環(huán)。。。cursor = cursor.nextcontinueelse:pre = cursorcursor = cursor.next# 判斷鏈表是否為空def isempty(self):if self.root == None or self.size()==0:return Trueelse:return False# 刪除鏈表及其內(nèi)部所有元素def truncate(self):if self.root == None or self.size()==0:returnelse:cursor = self.rootwhile cursor!= None:cursor.data = Nonecursor = cursor.nextself.root = Nonecursor = None# 獲取指定位置的節(jié)點(diǎn)的值def getvalue(self, index):if self.root is None or self.size()==0:print('當(dāng)前鏈表為空！')return Noneif index<=0 or index>self.size():print("index %d不合法！"%index)return Noneelse:counter = 1cursor = self.rootwhile cursor is not None:if index == counter:return cursor.dataelse:counter += 1cursor = 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 Noneelif self.size()==1:top = self.root.dataself.root = Nonereturn topelse:pre = self.rootcursor = pre.nextwhile cursor.next is not None:pre = cursorcursor = cursor.nexttop = cursor.datacursor = Nonepre.next = Nonereturn top# 單鏈表逆序?qū)崿F(xiàn)def reverse(self):if self.root is None:returnif self.size()==1:returnelse:# post = Nonepre = Nonecursor = self.rootwhile cursor is not None:# print('逆序操作逆序操作')post = cursor.nextcursor.next = prepre = cursorcursor = post# 千萬(wàn)不要忘記了把逆序后的頭結(jié)點(diǎn)賦值給root，否則無(wú)法正確顯示self.root = pre# 刪除鏈表中的重復(fù)元素def delDuplecate(self):# 使用一個(gè)map來(lái)存放即可，類似于變形的“桶排序”dic = {}if self.root == None:returnif self.size() == 1:returnpre = self.rootcursor = pre.nextdic = {}# 為字典賦值temp = self.rootwhile temp!=None:dic[str(temp.data)] = 0temp = temp.nexttemp = None# 開(kāi)始實(shí)施刪除重復(fù)元素的操作while cursor!=None:if dic[str(cursor.data)] == 1:pre.next = cursor.nextcursor = cursor.nextelse:dic[str(cursor.data)] += 1pre = cursorcursor = cursor.next# 修改指定位置節(jié)點(diǎn)的值def updateNode(self, index, value):if self.root == None:returnif index<0 or index>self.size():returnif index == 1:self.root.data = valuereturnelse:cursor = self.root.nextcounter = 2while cursor!=None:if counter == index:cursor.data = valuebreakcursor = cursor.nextcounter += 1# 獲取單鏈表的大小def size(self):counter = 0if self.root == None:return counterelse:cursor = self.rootwhile cursor!=None:counter +=1cursor = cursor.nextreturn counter# 打印鏈表自身元素def print(self):if(self.root==None):returnelse:cursor = self.rootwhile cursor!=None:print(cursor.data, end='\t')cursor = cursor.nextprint()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ì)寫還是兩碼事，沒(méi)事的時(shí)候?qū)憣戇@樣的代碼還是很有收獲的。

總結(jié)

以上是生活随笔為你收集整理的Python 实现一个全面的单链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。