双向链表 课件 【考点打靶+定向训练】 高中信息技术选修1

2.2链表双向链表什么是双向链表？双向链表（又称双链表）每个节点有两个指针prev和next，分别指向其前驱节点和后继节点，这样可以提供方便的双向查找功能。双向链表的表示？Dui=[[“吴坚”，-1，1],[“王林”,0，2],[“黄刚”,1，3],[“李丰”,2，-1]]节点（由数据区域和前驱节点指针、后继节点指针构成）我前面没人我后面没人我后面是黄刚双向链表的特性双向链表中当节点中prev指向为-1（即指向为空）时，表示该节点为链表中的首个节点；相对的，当节点中next指向为-1时，表示该节点为链表中的最后一个节点。下图所示为用二维列表表示一个长度为6的双向链表data1^data2data3data4data5data6列表名data列表索引数据域prev指针next指针0data64-11data4542data1-133data2254data5105data331head双向链表的基本操作一、双向链表的创建Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来表示每一个节点，其中第一个元素存储数据，第二、三个元素分别存储前驱指针prev和后继指针next。创建一个拥有2个节点的双向链表dblinklist的代码如下：dblinklist=[[6,-1,1],[8,0,-1],]head=0创建一个空链表dblinklist的代码如下：dblinklist=[]head=-1二、双向链表节点的访问链表节点只能通过头指针（head）进行访问，其他节点通过节点间的next指针依次访问。可以设计如下自定义函数输出链表的所有节点：defshuchu(a,head):p=headwhilea[p][2]!=-1print(a[p][0],end=“---->”)p=a[p][2]print(a[p][0])三、双向链表节点的插入链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱与后继节点的指针，将新节点插入到链表的正确位置。从链表头部插入一个新节点（头插法）：例如，在双向链表a的头部插入一个新节点node的代码如下：node=[random.randint(1,10),-1,head]a.append(node)ifhead!=-1:a[head][1]=len(a)-1head=len(a)-1在链表a的索引p之后插入一个新节点，可以设计自定义函数如下：:Definsert_behind(a,p,data):node=[data,p,a[p][2]]a.append(node)ifa[p][2]!=-1:a[a[p][2]][1]=len(a)-1a[p][2]=len(a)-1四、双向链表节点的删除双向链表节点的删除操作比单向链表要简单，它无需查找前驱节点，只需判断被删除的节点是否有前驱节点或后继节点，然后修改相关指针即可。尾结点可以直接删除，若删除了头节点，则需要修改头指针。可设计自定义函数删除索引为p的节点，代码如下：Defdelete(a,head,p):ifa[p][1]!=-1:a[a[p][1]][2]=a[p][2]ifa[p][2]!=-1:a[a[p][2]][1]=a[p][1]ifhead==p:head=a[head][2]returnhead1.Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来表示每一个节点，其中第一个元素存储数据，第二、三个元素分别存储前驱指针prev和后继指针next。下列代码创建了一个拥有4个节点的双链表a：a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]head=2则其头节点和尾结点数据域的值分别为：A.2和4B.0和8C.8和0D.3和-1B练习2.Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来表示每一个节点，其中第1个元素存储数据，第二、三个元素分别存储前驱指针prev和后继指针next；同时双向链表使用头指针head指向第一个节点在列表中的索引。下列代码创建了一个双向链表a:a=[[2,2,5],[8,0,5],[0,-1,0],[1,-1,2],[5,5,-1],[3,0,-1]]head=2则该双向链表a的节点数量为：A.3B.4C.5D.6A3.有如下python程序段：a=[[1,-1,1],[2,0,2],[3,1,3],[4,2,-1]]head=0whilea[head][2]!=-1:a[head][1],a[head][2]=a[head][2],a[head][1]head=a[head][1]a[head][1],a[head][2]=a[head][2],a[head][1]则程序执行后，链表各节点数据值依次为：CA.1234B.1324C.4321D.4231例：廿四节气被列入农历，称为农历的一个重要部分。按照时间顺序，上半年主要包括立春、雨水、惊蛰、春分、清明、谷雨和立夏这几个节气。小刚创建了一个双向链表，每个节点存储一个节气名称，可是他不小心漏掉了清明这个节气。编写程序，实现功能：将清明插入到链表的正确位置。请在划线处填入合适的代码。#输出链表a的所有节点defdisplay(a,head):p=headwhilea[p][2]!=-1:print(a[p][0],end=“”)p=a[p][2]print(a[p][0])#主函数部分a=[“立春”,-1,1],[“雨水”,0,2],[“惊蛰”,1,3],[“春分”,2,4],[“谷雨”,3,5],[“立夏”,4,-1]]head=0display(a,head)#先找到春分，再将清明插入到春分后面p=headwhilep!=-1anda[p][0]!=“春分”: