Python 實現(xiàn)靜態(tài)鏈表案例詳解
靜態(tài)鏈表和動態(tài)鏈表區(qū)別
靜態(tài)鏈表和動態(tài)鏈表的共同點是，數(shù)據(jù)之間"一對一"的邏輯關(guān)系都是依靠指針（靜態(tài)鏈表中稱"游標"）來維持。
靜態(tài)鏈表
使用靜態(tài)鏈表存儲數(shù)據(jù)，需要預先申請足夠大的一整塊內(nèi)存空間，也就是說，靜態(tài)鏈表存儲數(shù)據(jù)元素的個數(shù)從其創(chuàng)建的那一刻就已經(jīng)確定，后期無法更改。
不僅如此，靜態(tài)鏈表是在固定大小的存儲空間內(nèi)隨機存儲各個數(shù)據(jù)元素，這就造成了靜態(tài)鏈表中需要使用另一條鏈表（通常稱為"備用鏈表"）來記錄空間存儲空間的位置，以便后期分配給新添加元素使用。
這意味著，如果你選擇使用靜態(tài)鏈表存儲數(shù)據(jù)，你需要通過操控兩條鏈表，一條是存儲數(shù)據(jù)，另一條是記錄空閑空間的位置。
動態(tài)鏈表
使用動態(tài)鏈表存儲數(shù)據(jù)，不需要預先申請內(nèi)存空間，而是在需要的時候才向內(nèi)存申請。也就是說，動態(tài)鏈表存儲數(shù)據(jù)元素的個數(shù)是不限的，想存多少就存多少。
同時，使用動態(tài)鏈表的整個過程，你也只需操控一條存儲數(shù)據(jù)的鏈表。當表中添加或刪除數(shù)據(jù)元素時，你只需要通過 malloc 或 free 函數(shù)來申請或釋放空間即可，實現(xiàn)起來比較簡單。
python 實現(xiàn)的靜態(tài)鏈表
靜態(tài)鏈表的設(shè)計思維非常巧妙，通過索引、游標完成單向鏈表結(jié)構(gòu)，相對于順序結(jié)構(gòu)的列表而言，節(jié)省了數(shù)據(jù)移位、內(nèi)存碎片的開支。
python 實現(xiàn)的靜態(tài)鏈表代碼，靜態(tài)鏈表采用的 list 結(jié)構(gòu)存儲。
class Node:
def __init__(self, next, val=None):
self.val = val # 值
self.next = next # 游標。最后一個元素的游標必須是 0
class SLinkList:
# 分配線性表長度、定義線性表
def __init__(self, size=7):
self.size = size
self.link = [Node((i + 1) % self.size) for i in range(self.size)]
# 線性表清空
def clearSLL(self):
self.__init__()
# 線性表是否為空
def isEmpty(self):
return False if self.link[self.size - 1].next else True
# 查找空位置
def findEmpty(self):
ind = self.size
for i in range(1, self.size - 1):
if self.link[i].val is None:
ind = i
break
return ind
# 指定位置插入元素
def insert(self, ind, ele):
sua = -1
# 前一個元素
pre = self.size - 1
# 插入元素的位置（第一個空位置）
insertLoc = self.link[0].next
# 條件判斷
if ind < 1 or ind >= pre or insertLoc >= self.size:
return 0
# 第一個元素的索引
for i in range(1, self.size - 1):
index = self.link[pre].next
if i == ind:
self.link[pre].next = insertLoc
# 元素插入
self.link[insertLoc].val = ele
self.link[insertLoc].next = index
# 首位元素
self.link[0].next = self.findEmpty()
sua = 1
break
if self.link[index].val is None:
break
pre = index
return sua
# 查找線性表某位置的元素
def getByIndex(self, ind):
if ind < 1 or ind >= self.size - 1:
return -1
index = self.link[self.size - 1].next
if index == 0:
return -1
for i in range(1, ind):
index = self.link[index].next
return self.link[index].val
# 查找線性表的元素所在位置
def locateElement(self, ele):
index = self.link[self.size - 1].next
ind = -1
if index == 0:
return ind
for i in range(1, self.size - 1):
if self.link[index].val == ele:
ind = i
break
if self.link[index].val is None:
break
index = self.link[index].next
return ind
# 刪除線性表指定位置的元素
def deleteElement(self, ind):
sua = -1
# 前一個索引
pre = self.size - 1
for i in range(1, self.size - 1):
index = self.link[pre].next
# 當前位置是個空位置
if self.link[index].val is None:
break
# 已經(jīng)遍歷到第i個位置
if i == ind:
self.link[pre].next = self.link[index].next
self.link[index].val = None
# 刪除元素的游標指向備用鏈表
self.link[index].next = self.link[0].next
# 首位元素
self.link[0].next = index
sua = 1
break
pre = index
return sua
# 按照線性表排序線性表遍歷
def travelLink(self):
print("*" * 50)
index = self.link[self.size - 1].next
while self.link[index].val:
print(
f"value = {self.link[index].val} next = {self.link[index].next}"
)
index = self.link[index].next
print("*" * 50)
# 按照索引遍歷
def traversingByIndex(self):
print("*" * 50)
for i in range(self.size):
print(
f"index = {i}, value = {self.link[i].val} next = {self.link[i].next}"
)
print("*" * 50)
if __name__ == '__main__':
ll = SLinkList()
ll.traversingByIndex()
print(ll.isEmpty())
print(ll.insert(1, 'A'))
ll.travelLink()
print(ll.insert(2, 'B'))
ll.travelLink()
print(ll.insert(1, 'C'))
print(ll.insert(4, 'D'))
ll.travelLink()
ll.traversingByIndex()
print(ll.deleteElement(3))
ll.traversingByIndex()
ll.travelLink()
print(ll.isEmpty())
print(ll.getByIndex(2))
print(ll.locateElement('BcA'))
print(ll.clearSLL())
到此這篇關(guān)于Python 實現(xiàn)靜態(tài)鏈表案例詳解的文章就介紹到這了,更多相關(guān)Python 實現(xiàn)靜態(tài)鏈表內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學習參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信