Python 實現鏈表實例代碼
前言
算法和數據結構是一個亙古不變的話題，作為一個程序員，掌握常用的數據結構實現是非常非常的有必要的。
實現清單
實現鏈表，本質上和語言是無關的。但是靈活度卻和實現它的語言密切相關。今天用Python來實現一下，包含如下操作：
['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)']
生成這樣的一個方法清單肯定是不能手動寫了，要不然得多麻煩啊，于是我寫了個程序，來匹配這些自己實現的方法。代碼比較簡單，核心思路就是匹配源文件的每一行，找到符合匹配規則的內容，并添加到總的結果集中。
代碼如下：
# coding: utf8# @Author: 郭 璞# @File: getmethods.py # @Time: 2017/4/5 # @Contact: 1064319632@qq.com# @blog: http://blog.csdn.net/marksinoberg# @Description: 獲取一個模塊或者類中的所有方法及參數列表import redef parse(filepath, repattern): with open(filepath, 'rb') as f: lines = f.readlines() # 預解析正則 rep = re.compile(repattern) # 創建保存方法和參數列表的結果集列表 result = [] # 開始正式的匹配實現 for line in lines: res = re.findall(rep, str(line)) print("{}的匹配結果{}".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))鏈表實現
# coding: utf8# @Author: 郭 璞# @File: SingleChain.py # @Time: 2017/4/5 # @Contact: 1064319632@qq.com# @blog: http://blog.csdn.net/marksinoberg# @Description: 單鏈表實現class Node(object): def __init__(self, data, next): self.data = data self.next = nextclass LianBiao(object): def __init__(self): self.root = None # 給單鏈表添加元素節點 def addNode(self, data): if self.root==None: self.root = Node(data=data, next=None) return self.root else: # 有頭結點，則需要遍歷到尾部節點，進行鏈表增加操作 cursor = self.root while cursor.next!= None: cursor = cursor.next cursor.next = Node(data=data, next=None) return self.root # 在鏈表的尾部添加新節點，底層調用addNode方法即可 def append(self, value): self.addNode(data=value) # 在鏈表首部添加節點 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 # 在鏈表的指定位置添加節點 def insert(self, index, value): if self.root == None: return if index<=0 or index >self.size(): print('index %d 非法， 應該審視一下您的插入節點在整個鏈表的位置！') return elif index==1: # 如果index==1， 則在鏈表首部添加即可 self.prepend(value) elif index == self.size()+1: # 如果index正好比當前鏈表長度大一，則添加在尾部即可 self.append(value) else: # 如此，在鏈表中部添加新節點，直接進行添加即可。需要使用計數器來維護插入未知 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 # 刪除指定位置上的節點 def delNode(self, index): if self.root == None: return if index<=0 or index > self.size(): return # 對第一個位置需要小心處理 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的鏈表節點元素 def delValue(self, value): if self.root == None: return # 對第一個位置需要小心處理 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 # 千萬記得更新這個節點，否則會出現死循環。。。 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 # 刪除鏈表及其內部所有元素 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 # 獲取指定位置的節點的值 def getvalue(self, index): if self.root is None or self.size()==0: print('當前鏈表為空！') 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 # 獲取鏈表尾部的值，且不刪除該尾部節點 def peek(self): return self.getvalue(self.size()) # 獲取鏈表尾部節點的值，并刪除該尾部節點 def pop(self): if self.root is None or self.size()==0: print('當前鏈表已經為空！') 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 # 單鏈表逆序實現 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 # 千萬不要忘記了把逆序后的頭結點賦值給root，否則無法正確顯示 self.root = pre # 刪除鏈表中的重復元素 def delDuplecate(self): # 使用一個map來存放即可，類似于變形的“桶排序” 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 # 開始實施刪除重復元素的操作 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 # 修改指定位置節點的值 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__': # 創建一個鏈表對象 lianbiao = LianBiao() # 判斷當前鏈表是否為空 print("鏈表為空%d"%lianbiao.isempty()) # 判斷當前鏈表是否為空 lianbiao.addNode(1) print("鏈表為空%d"%lianbiao.isempty()) # 添加一些節點，方便操作 lianbiao.addNode(2) lianbiao.addNode(3) lianbiao.addNode(4) lianbiao.addNode(6) lianbiao.addNode(5) lianbiao.addNode(6) lianbiao.addNode(7) lianbiao.addNode(3) # 打印當前鏈表所有值 print('打印當前鏈表所有值') lianbiao.print() # 測試對鏈表求size的操作 print("鏈表的size: "+str(lianbiao.size())) # 測試指定位置節點值的獲取 print('測試指定位置節點值的獲取') print(lianbiao.getvalue(1)) print(lianbiao.getvalue(lianbiao.size())) print(lianbiao.getvalue(7)) # 測試刪除鏈表中指定值， 可重復性刪除 print('測試刪除鏈表中指定值， 可重復性刪除') lianbiao.delNode(4) lianbiao.print() lianbiao.delValue(3) lianbiao.print() # 去除鏈表中的重復元素 print('去除鏈表中的重復元素') lianbiao.delDuplecate() lianbiao.print() # 指定位置的鏈表元素的更新測試 print('指定位置的鏈表元素的更新測試') lianbiao.updateNode(6, 99) lianbiao.print() # 測試在鏈表首部添加節點 print('測試在鏈表首部添加節點') lianbiao.prepend(77) lianbiao.prepend(108) lianbiao.print() # 測試在鏈表尾部添加節點 print('測試在鏈表尾部添加節點') lianbiao.append(99) lianbiao.append(100) lianbiao.print() # 測試指定下標的插入操作 print('測試指定下標的插入操作') lianbiao.insert(1, 10010) lianbiao.insert(3, 333) lianbiao.insert(lianbiao.size(), 99999) lianbiao.print() # 測試peek 操作 print('測試peek 操作') print(lianbiao.peek()) lianbiao.print() # 測試pop 操作 print('測試pop 操作') print(lianbiao.pop()) lianbiao.print() # 測試單鏈表的逆序輸出 print('測試單鏈表的逆序輸出') lianbiao.reverse() lianbiao.print() # 測試鏈表的truncate操作 print('測試鏈表的truncate操作') lianbiao.truncate() lianbiao.print()
新聞熱點
疑難解答
