标签 链表 下的文章 - 叁零零肆零肆

链表 1.创建空链表item=[] #存储空间 head=-1 #头指针2.单向链表元素的遍历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->23.在单向链表中插入数据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]]4.在单向链表中删除数据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]]5.双向链表的插入#双向链表节点格式[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]]6.双向链表的删除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] 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]]7.拓展：链表类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"->" #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)