Python 實現連結串列例項程式碼

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

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: [email protected]
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 獲取一個模組或者類中的所有方法及引數列表
import re
def 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: [email protected]
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 單連結串列實現
class Node(object):
def __init__(self, data, next):
self.data = data
self.next = next
class 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()

程式碼執行的結果如何呢?是否能滿足我們的需求,且看列印的結果:


D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py
連結串列為空1
連結串列為空0
列印當前連結串列所有值
1  2  3  4  6  5  6  7  3  
連結串列的size: 9
測試指定位置節點值的獲取
1
3
6
測試刪除連結串列中指定值, 可重複性刪除
can be here!
1  2  3  6  5  6  7  3  
1  2  6  5  6  7  
去除連結串列中的重複元素
1  2  6  5  7  
指定位置的連結串列元素的更新測試
1  2  6  5  7  
測試在連結串列首部新增節點
108 77 1  2  6  5  7  
測試在連結串列尾部新增節點
108 77 1  2  6  5  7  99 100 
測試指定下標的插入操作
10010  108 333 77 1  2  6  5  7  99 99999  100 
測試peek 操作
100
10010  108 333 77 1  2  6  5  7  99 99999  100 
測試pop 操作
100
10010  108 333 77 1  2  6  5  7  99 99999  
測試單連結串列的逆序輸出
99999  99 7  5  6  2  1  77 333 108 10010  
測試連結串列的truncate操作
Process finished with exit code 0

剛好實現了目標需求。

總結

今天的內容還是比較基礎,也沒什麼難點。但是看懂和會寫還是兩碼事,沒事的時候寫寫這樣的程式碼還是很有收穫的。

您可能感興趣的文章:

Python實現的單向迴圈連結串列功能示例Python程式設計實現雙連結串列,棧,佇列及二叉樹的方法示例Python資料結構與演算法之列表(連結串列,linked list)簡單實現Python資料結構與演算法之連結串列定義與用法例項詳解【單連結串列、迴圈連結串列】python資料結構之連結串列詳解python資料結構連結串列之單向連結串列(例項講解)python實現單向連結串列詳解

相關文章

程式語言 最新文章