22链表课件高二上学期选择性必修1《数据与数据结构》第二章

导入小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。杭州上海苏州南京济南石家庄北京青岛导入小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。杭州上海苏州南京济南石家庄北京青岛数组的缺点：插入和删除元素操作需要移动大量的元素频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费链表适用于当数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。单向链表的概念与基本操作信息技术选考课程一、链表的概念与特性1、概念：链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构2、节点结构保存数据元素保存相邻结点的存储地址一个链表的节点一、链表的概念与特性杭州next上海next苏州next南京-1head（头指针）单向链表head称为

，data1节点称为data2节点的

，data3节点称为data2节点的

。头指针（表头）前驱节点后继节点3、头指针作用tail(1)链表的入口，只有通过头指针才能进入链表。(2)为循环链表设立一个边界，便于数据处理时的边界判断和处理。一、链表的概念与特性4、分类？？杭州next上海next苏州-1head①单向链表：当只有一个指针用来指向其后继节点。pre杭州nexthead②双向链表：有两个指针分别用于指向其前驱节点和后继节点。pre上海nextpre苏州-1一、链表的概念与特性4、分类？？杭州next上海next苏州-1head③循环链表：把第一节点和最后一个节点使用指针连接（约瑟夫环）。pre杭州nextheadpre上海nextpre苏州-1基于单链的循环链表基于双链的循环链表一、链表特性同一链表中每个节点的结构均相同每个节点的数据区域的数据类型相同，指针区域中的指针数量和功能是相同的。每个链表必定有一个头指针，以实现对链表的引用和边界处理链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能像数组那样使用下标直接引用。

对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。链表占用的空间不固定

链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。二、链表的基本操作（创建/访问/插入/删除）单向链表的创建（用python二维列表模拟）a=[]head=-1#head值为-1，表示头指针指向为空，该链表为空链表a=[["杭州",1],["上海",3],["苏州",-1],["南京",2],["嘉兴",0]]head=4#创建一个拥有5个节点的单向链表列表中有5个元素：

["杭州",1]、["上海",3]、["苏州",-1]、["南京",2]、["嘉兴",0]a[p]表示一个节点

如：a[4]=[“嘉兴”,0]a[p][0]表示该节点的数据域

如：a[4][0]=“嘉兴”a[p][1]表示该节点的指针（即索引）

如：a[4][1]=0datanext杭州1上海3苏州-1南京2嘉兴001234head→二、链表的基本操作（创建/访问/插入/删除）#输出链表的所有节点数据data=[["杭州",1],["上海",3],["苏州",-1],["南京",2],["嘉兴",0]]head=4display(data,head)链表的访问（遍历）嘉兴

杭州

上海

南京

苏州datanext杭州1上海3苏州-1南京2嘉兴001234head→二、链表的基本操作（创建/访问/插入/删除）#输出链表的所有节点数据data=[["杭州",1],["上海",3],["苏州",-1],["南京",2],["嘉兴",0]]head=4display(data,head)链表的访问（遍历）嘉兴

杭州

上海

南京

苏州defdisplay(data,head):p=headwhiledata[p][1]!=-1:print(data[p][0],end=“->")

p=data[p][1]print(data[p][0])datanext杭州1上海3苏州-1南京2嘉兴001234head→二、链表的基本操作（创建/访问/插入/删除）在链表头部插入一个新节点索引datanext0杭州11上海32苏州-13南京24嘉兴0head5温州4温州

嘉兴

杭州

上海

南京

苏州嘉兴next杭州next上海nexthead温州next南京next苏州next二、链表的基本操作（创建/访问/插入/删除）在链表的索引p=3之后插入一个新节点索引datanext0杭州11上海32苏州-13南京24嘉兴0head5温州25data1nextdata2nextdata3-1headnewnext嘉兴

杭州

上海

南京

温州

苏州二、链表的基本操作（创建/访问/插入/删除）在链表的索引p=3之前插入一个新节点data=[[6,1],[9,3],[10,-1],[8,2],[7,0]]pre_p=head=4p,newdata=3,5whiledata[pre_p][1]!=p:pre_p=data[pre_p][1]data.append([newdata,data[pre_p][1]])data[pre_p][1]=len(data)-1索引datanext061193210-1382470head55376958105data1nextdata2nextdata3-1headnewnextppre_p二、链表的基本操作（创建/访问/插入/删除）在链表的尾部插入一个新节点索引datanext0杭州11上海

32苏州-13南京24嘉兴0head5温州-176981055data1nextdata2nextdata3-1headnew-1next二、链表的基本操作（创建/访问/插入/删除）删除链表中索引为p的节点data1nextdata2nextdata3-1head索引datanext061193210-1382470head769102删除的位置：头结点中间节点尾结点#删除索引为p的节点，返回链表新的头指针headdefdel_node(data,p):globalheadifp==head: #删除头结点,修改头指针head=data[head][1]else:pre=head #pre为节点p的前驱节点whiledata[pre][1]!=panddata[pre][1]!=-1:pre=data[pre][1]ifdata[pre][1]==p:data[pre][1]=data[p][1]else:print("该节点不存在！")returnhead三、链表的应用–数据合并97193287367-198195292388460-1链表data_a链表data_b思考：两个链表的数据合并需要和数组的方法一样吗？数组访问快，插入慢链表访问慢，插入快三、链表的应用–数据合并97193287367-198195292388460-1head_ahead_bk_ak_b情况1：插入到链表a的表头位置。情况2：插入到链表a的中间位置。那如何知道当前节点的前驱节点？情况3：链表b还有数据剩余。pre_a#初始化head_a=head_b=0k_a,k_b=head_a,head_bpre_a=head_a #链表a当前节点的前驱节点97193287367-198195292388460-1head_ahead_bk_ak_bpre_awhilek_a!=-1andk_b!=-1:ifdata_a[k_a][0]>=data_b[k_b][0]:pre_a=k_ak_a=data_a[k_a][1]else:ifk_a==head_a:#头部插入

data_a.append([data_b[k_b][0],head_a]) #将数据添加到列表尾head_a=len(data_a)–1 #更新头指针pre_a=head_a #更新前驱节点k_b=data_b[k_b][1] #链表b指针指向下一个节点else: #中间插入

data_a.append([data_b[k_b][0],data_a[pre_a][1]])data_a[pre_a][1]=len(data_a)-1pre_a=data_a[pre_a][1] k_b=data_b[k_b][1]whilek_b!=-1: #链表b还有剩余数据未插入data_a.append(