(
课件网) 2.2 链表（第二课时） 单击此处添加副标题 链表的创建 可以使用如下Python代码创建一个空链表： head = -1 #头指针指向-1，表示链表为空 #创建一个空链表Item 头指针变量head：存储链表第一个节点在列表中的索引 Item = [ ] 链表的创建 节点 列表模拟单向链表的节点： data next 根据实际问题的特点规划好节点的数据区域和指针区域 列表 [data,next] Item.append([data,next]) 通过列表的append( )函数将节点保存到列表中 #索引：len(Item)-1 单向链表的创建 Item = [ [“张强”, ] , [“杜刚”, ] ] head = _____ #存储第一个节点在列表中的索引 1 -1 索引0 索引1 张强 head 杜刚 0 单向链表节点的访问 链表中访问指定节点只能通过头指针指向的第一个节点开始访问，其他节点通过节点间的指针依次访问。 data1 data2 data3 head data4 访问变量 访问变量 访问变量 访问变量 访问变量== -1 ：访问完最后一个节点 访问变量：当前访问节点在列表中的索引 Item = [ [“杜刚”, 2 ] , [“杜强”, 3 ]， [“李彤”, -1 ] , [“李丰”, 0 ]] head = 1 #依次访问并输出链表各节点数据 p=head #访问变量，表示当前访问节点的索引 print(Item[p][0],end=” ”) #输出当前节点数据 p=Item[p][1] #访问变量迭代更新为后继的 #按照p的功能： 当前访问节点的数据区域为： 当前访问节点的后继指针为： Item[p][0] Item[p][1] Item = [ [“杜刚”, 2 ] , [“杜强”, 3 ]， [“李彤”, -1 ] , [“李丰”, 0 ]] head = 1 #依次访问并输出链表各节点数据 p=head #访问变量，表示当前访问节点的索引 #按照p的功能： 当前访问节点的数据区域为： 当前访问节点的后继指针为： Item[p][0] while p!=-1: print(Item[p][0],end=” ”) #输出当前节点数据 p=Item[p][1] #访问变量迭代更新为后继的 Item[p][1] 杜强 李丰 杜刚 李彤 Item = [ [“杜刚”, 2 ] , [“杜强”, 3 ]， [“李彤”, -1 ] , [“李丰”, 0 ]] head = 1 #依次访问并输出链表各节点数据 p=head #访问变量，表示当前访问节点的索引 #按照p的功能： 当前访问节点的数据区域为： 当前访问节点的后继指针为： Item[p][1] while p!=-1 : print(Item[p][0],end=” ”) #输出当前节点数据 p=Item[p][1] #访问变量迭代更新为后继的 p!= -1 and Item[p][0]!=”杜刚” ： 杜强 李丰 Item[p][0] 单向链表节点的插入 data1 next1 data3 next3 head data1 next1 data2 next2 data3 next3 插入到链表最前面 data2 -1 data3 next3 -1 next2 插入到相邻两个节点之间 插入到链表最后面 单向链表节点的插入 data1 next1 data3 next3 head 插入到链表最前面 #新节点 Item[r][1] = head #头指针 head = r 已知链表的第一个节点的索引保存在head变量上，新节点在列表中的索引是r 索引r 单向链表节点的插入 插入到链表相邻两个节点之间 data1 next1 data2 next2 data3 next3 某相邻两个节点在列表中索引分别为pre和p，在其之间插入一个新节点；新节点在列表中索引为r #新节点 Item[r][1] = p #前驱节点 Item[pre][1] = r 索引pre 索引r 索引p 单向链表节点的插入 插入到链表最后面 #新节点 Item[r][1] = -1 #前驱节点 Item[p][1] = r 已知链表的最后一个节点的索引为p，新节点在列表中的索引是r data2 -1 data3 -1 -1 索引r r 单向链表节点的删除 data1 next data2 next data3 next data2 next data3 -1 data1 next data2 next 删除第一个节点 head 删除中间节点 删除最后一个节点 单向链表节点的删除 变量head保存了第一个节点在列表中索引 #头指针 head = Item [head] [1] 删除第一个节点 data1 next data2 next head 单向链表节点的删除 ... ...
