资源简介

#创建空链表
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)

展开更多......

收起↑