資源簡介

#創建空鏈表
item=[] #存儲空間
head=-1 #頭指針
#單向鏈表元素的遍歷
head = 4
item = [[5,2],[7,3],[9,5],[2,-1],[1,0],[3,1]]
p = head
str1 = ''
while p != -1:
str1 += str(item[p][0])+"->"
p = item[p][1] #切換到下一節點
print(str1[:-2]) #清除最后的"->"
#運行結果
1->5->9->3->7->2
#在單向鏈表中插入數據
head = 0
item = [[99,1],[98,2],[97,3],[95,4],[94,-1]]
num = 96 #被插入數據
p = head
while p != -1: #未到尾部
if item[p][0] < num:
if p==head:
item.append([num,p]) #插入并復制前序next值
head = len(item)-1 #更新head值
break
else:
item.append([num,item[q][1]]) #插入并復制前序next值
item[q][1] = len(item)-1 #更新前序next值
break
q = p #存儲前序節點
p = item[p][1] #切換到下一節點
if p == -1: #在鏈表尾部插入
item.append([num,-1])
item[q][1] = len(item)-1
print(head,item)
#運行結果
num = 96 #中間插入
head=0 item=[[99, 1], [98, 2], [97, 5], [95, 4], [94, -1], [96, 3]]
num = 100 #頭部插入
head = 5 item = [[99, 1], [98, 2], [97, 3], [95, 4], [94, -1], [100, 0]]
num = 93 #尾部插入
head = 0 item = [[99, 1], [98, 2], [97, 3], [95, 4], [94, 5], [93, -1]]
#在單向鏈表中刪除數據
head = 0
item = [[99,1],[98,2],[97,3],[96,-1]]
num = 99 #被刪除數據
p = head
while p != -1: #未到尾部
if item[p][0] == num:
if p==head:
head = item[p][1] #更新頭指針位置
else:
item[q][1] = item[p][1] #更新前序節點next值
q = p #存儲前序節點
p = item[p][1] #切換到下一節點
print(head,item)
#運行結果
num = 97 #刪除中間
head = 0 item = [[99, 1], [98, 3], [97, 3], [96, -1]]
num = 99 #刪除頭部
head = 1 item = [[99, 1], [98, 2], [97, 3], [96, -1]]
num = 96 #刪除尾部
head = 0 item = [[99, 1], [98, 2], [97, -1], [96, -1]]
#雙向鏈表節點格式[num,prev,next]
#雙向鏈表的插入
head = 0
item = [[99,-1,1],[98,0,2],[97,1,3],[95,2,4],[94,3,-1]]
num = 96 #被插入數據
p = head
while p != -1:
if item[p][0] < num:
if p==head:
item.append([num,-1,head]) #item.append([num,-1,p])
head = len(item)-1
item[p][1]=len(item)-1
break
else:
item.append([num,item[p][1],p])
item[item[p][1]][2] = len(item)-1 #注意先后順序
item[p][1] = len(item)-1 #注意先后順序
break
p = item[p][2]
if item[p][2] == -1: #判斷是否為最后一個節點
if item[p][0] > num: #判斷是不是在尾部插入
item.append([num,p,-1])
item[p][2] = len(item)-1
break
print(head,item)
#運行結果
num = 96 #中間插入
head = 0 item = [[99, -1, 1], [98, 0, 2], [97, 1, 5], [95, 5, 4], [94, 3, -1], [96, 2, 3]]
num = 100 #頭部插入
head = 5 item = [[99, 5, 1], [98, 0, 2], [97, 1, 3], [95, 2, 4], [94, 3, -1], [100, -1, 0]]
num = 93 #尾部插入
head = 0 item = [[99, -1, 1], [98, 0, 2], [97, 1, 3], [95, 2, 4], [94, 3, 5], [93, 4, -1]]
#雙向鏈表的刪除
head = 0
item = [[99,-1,1],[98,0,2],[97,1,3],[95,2,4],[94,3,-1]]
num = 94 #被刪除入數據
p = head
while p != -1:
if item[p][0] == num:
if p==head:
head = item[p][2] #更新頭指針
item[item[p][2]][1]=-1 #更新下一跳的前向指針
else:
item[item[p][1]][2] = item[p][2]
if item[p][2] != -1:
item[item[p][2]][1] = item[p][1]
#item[item[p][2]][1] = item[p][1] #運行這句話其實并沒有報錯
p = item[p][2]
print(head,item)
#運行結果
num = 97 #中間刪除
head = 0 item = [[99, -1, 1], [98, 0, 3], [97, 1, 3], [95, 1, 4], [94, 3, -1]]
num = 99 #頭部刪除
head = 1 item = [[99, -1, 1], [98, -1, 2], [97, 1, 3], [95, 2, 4], [94, 3, -1]]
num = 94 #尾部刪除
head = 0 item = [[99, -1, 1], [98, 0, 2], [97, 1, 3], [95, 2, -1], [94, 3, -1]]
#鏈表類
class LinkNode: #定義單節點類
def __init__(self,data_,next_=None): #注意默認值的使用
self.data = data_
self.next = next_

class LinkList: #定義單鏈表類
def __init__(self): #生成實例初始化設置
self.head=None
def __str__(self): #類實例字符串格式輸出設置
s = ""
cur=self.head
while cur is not None:
s += f"{cur.data}->" #format方法變種,與等價"{}->".format(cur.data)
cur=cur.next
return s[:-2] #刪除多余的“->”
def len(self):
num = 0
cur = self.head
while cur is not None:
num += 1
cur = cur.next
return num
def perpend(self,data_): #頭插法
if self.head is None:
self.head=LinkNode(data_)
else:
self.head=LinkNode(data_,self.head)
def append(self,data_): #尾插法
if self.head is None:
self.head = LinkNode(data_)
else:
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = LinkNode(data_)
def insert(self,index,data_): #指定位置插入節點
if index<0 or index>=self.len(): #位置不存在
self.append(data_) #用尾插法插入
else:
cur = self.head
while index>1:
cur = cur.next
index -= 1
cur.next = LinkNode(data_,cur.next)

def pop(self,index=-1): #指定位置刪除
if index<0 or index>=self.len(): #越界則默認刪除最后一個
index = self.len()
if index == 0:
self.head = self.head.next
else:
cur = self.head
while index>2:
cur = cur.next
index -= 1
print(cur.data)
cur.next = cur.next.next
a = LinkList()
for i in range(5):
a.perpend(i)
b = LinkList()
for i in range(5):
b.append(i)
print(a,b)
a.insert(1,10)
print(a)
a.pop(10)
print(a)

展開更多......

收起↑