2.2 链表 教学课件.pptxVIP

2.2链表（第二课时）单击此处添加副标题

链表的创建可以使用如下Python代码创建一个空链表：head=-1#头指针指向-1，表示链表为空#创建一个空链表Item头指针变量head：存储链表第一个节点在列表中的索引Item=[]

链表的创建节点列表模拟单向链表的节点：datanext根据实际问题的特点规划好节点的数据区域和指针区域列表[data,next]Item.append([data,next])通过列表的append()函数将节点保存到列表中#索引：len(Item)-1

单向链表的创建Item=[[“张强”,],[“杜刚”,]]head=_______#存储第一个节点在列表中的索引1-1索引0索引1张强head杜刚0

单向链表节点的访问链表中访问指定节点只能通过头指针指向的第一个节点开始访问，其他节点通过节点间的指针依次访问。data1data2data3headdata4访问变量访问变量访问变量访问变量访问变量==-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]whilep!=-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]whilep!=-1:print(Item[p][0],end=””)#输出当前节点数据p=Item[p][1]#访问变量迭代更新为后继的p!=-1andItem[p][0]!=”杜刚”：杜强李丰Item[p][0]

单向链表节点的插入data1next1data3next3headdata1next1data2next2data3next3插入到链表最前面data2-1data3next3-1next2插入到相邻两个节点之间插入到链表最后面

单向链表节点的插入data1next1data3next3head插入到链表最前面#新节点Item[r][1]=head#头指针head=r已知链表的第一个节点的索引保存在head变量上，新节点在列表中的索引是r索引r

单向链表节点的插入插入到链表相邻两个节点之间data1next1data2next2data3next3某相邻两个节点在列表中索引分别为pre和p，在其之间插入一个新节点；新节点在列表中索引为r#新节点Item[r][1]=p#前驱节点Item[pre][1]=r索引pre索引r索引p

单向链表节点的插入插入到链表最后面#新节点Item[r][1]=-1#前驱节点Item[p][1]=r已知链表的最后一个节点的索引为p，新节点在列表中的索引是rdata2-1data3-1-1索引rr

单向链表节点的删除data1nextdata2nextdata3nextdata2nextdata3-1data1nextdata2next删除第一个节点head删除中间节点删除最后一个节点

单向链表节点的删除变量head保存了第一个节点在列表中索引#头指针head=Item[head][1]删除第一个节点data1