2.2链表课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第二章（2019）

导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。 杭州 上海 苏州 南京 济南 石家庄 北京 青岛 导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。 杭州 上海 苏州 南京 济南 石家庄 北京 青岛 数组的缺点： 插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片” 需要限定最大空间，造成资源浪费 链表适用于当数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。 单向链表的概念与基本操作 信息技术 选考课程 一、链表的概念与特性 1、概念：链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构 2、节点结构 保存数据元素 保存相邻结点的存储地址 一个链表的节点 一、链表的概念与特性 杭州 next 上海 next 苏州 next 南京 -1 head （头指针） 单向链表 head称为 ，data1节点称为data2节点的 ，data3节点称为data2节点的 。 头指针（表头） 前驱节点 后继节点 3、头指针作用 tail (1)链表的入口，只有通过头指针才能进入链表。 (2)为循环链表设立一个边界，便于数据处理时的边界判断和处理。 一、链表的概念与特性 4、分类？？ 杭州 next 上海 next 苏州 -1 head ①单向链表：当只有一个指针用来指向其后继节点。 pre 杭州 next head ②双向链表：有两个指针分别用于指向其前驱节点和后继节点。 pre 上海 next pre 苏州 -1 一、链表的概念与特性 4、分类？？ 杭州 next 上海 next 苏州 -1 head ③循环链表：把第一节点和最后一个节点使用指针连接（约瑟夫环）。 pre 杭州 next head pre 上海 next pre 苏州 -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]=0 data next 杭州 1 上海 3 苏州 -1 南京 2 嘉兴 0 0 1 2 3 4 head→ 二、链表的基本操作（创建/访问/插入/删除） #输出链表的所有节点数据 data = [["杭州",1],["上海",3],["苏州",-1],["南京",2],["嘉兴",0]] head = 4 display(data,head) 链表的访问（遍历） 嘉兴杭州上海南京苏州 data next 杭州 1 上海 3 苏州 -1 南京 2 嘉兴 0 0 1 2 3 4 head→ 10 二、链表的基本操作（创建/访问/插入/删除） #输出链表的所有节点数据 data = [["杭州",1],["上海",3],["苏州",-1],["南京",2],["嘉兴",0]] head = 4 display(data,head) 链表的访问（遍历） 嘉兴杭州上海南京苏州 def display(data,head): p = head while data[p][1] != -1: print(data[p][0],end =“->") p = data[p][1] print(data[p][0]) data next 杭州 1 上海 3 苏州 -1 南京 2 嘉兴 0 0 1 2 3 4 head→ 11 二、链表的基本操作（创建/访问/插入/删除） 在链表头部插入一个新节点 索引 data next 0 杭州 1 1 上海 3 2 苏州 -1 3 南京 2 4 嘉兴 0 head 5 温州 4 温州嘉兴杭州上海南京苏州 嘉兴 next 杭州 next 上海 next head 温州 next 南京 next 苏州 next 12 二、链表的基本操作（创建/访问/插入/删除） 在链表的索引p=3之后插入一个新节点 索引 data next 0 杭州 1 1 上海 3 2 苏州 -1 3 南京 2 4 嘉兴 0 head 5 温州 2 5 data1 next data2 next data3 -1 head new next 嘉兴杭州上海南京温州苏州 二、链表的基本操作（创建/访问/插入/删除） 在链表的索引p=3之前插入一个新节点 data = [[6,1],[9,3],[10,-1],[8,2],[7,0]] pre_p=head = 4 p,newdata = 3,5 while data[pre_p][1] != p: pre_p = data[pre_p][1] data.append([newdata,data[pre_p][1]]) data[pre_p][1] = len(data)-1 索引 data next 0 6 1 1 9 3 2 10 -1 3 8 2 4 7 0 head 5 5 3 7695810 5 data1 next data2 next data3 -1 head new next p pre_p 二、链表的基本操作（创建/访问/插入/删除） 在链表的尾部插入一个新节点 索引 data next 0 杭州 1 1 上海 3 2 苏州 -1 3 南京 2 4 嘉兴 0 head 5 温州 -1 7698105 5 data1 next data2 next data3 -1 head new -1 next 二、链表的基本操作（创建/访问/插入/删除） 删除链表中索引为p的节点 data1 next data2 next data3 -1 head 索引 data next 0 6 1 1 9 3 2 10 -1 3 8 2 4 7 0 head 76910 2 删除的位置： 头结点 中间节点 尾结点 #删除索引为p的节点，返回链表新的头指针head def del_node(data,p): global head if p == head: #删除头结点,修改头指针 head=data[head][1] else: pre = head #pre为节点p的前驱节点 while data[pre][1] != p and data[pre][1] != -1: pre=data[pre][1] if data[pre][1] == p: data[pre][1]=data[p][1] else: print("该节点不存在！") return head 三、链表的应用 – 数据合并 97 1 93 2 87 3 67 -1 98 1 95 2 92 3 88 4 60 -1 链表data_a 链表data_b 思考：两个链表的数据合并需要和数组的方法一样吗？ 数组访问快，插入慢 链表访问慢，插入快 三、链表的应用 – 数据合并 97 1 93 2 87 3 67 -1 98 1 95 2 92 3 88 4 60 -1 head_a head_b k_a k_b 情况1：插入到链表a的表头位置。 情况2：插入到链表a的中间位置。那如何知道当前节点的前驱节点？ 情况3：链表b还有数据剩余。 pre_a #初始化 head_a = head_b = 0 k_a,k_b = head_a,head_b pre_a = head_a #链表a当前节点的前驱节点 97 1 93 2 87 3 67 -1 98 1 95 2 92 3 88 4 60 -1 head_a head_b k_a k_b pre_a while k_a != -1 and k_b != -1: if data_a[k_a][0] >= data_b[k_b][0]: pre_a = k_a k_a = data_a[k_a][1] else: if k_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)-1 pre_a = data_a[pre_a][1] k_b = data_b[k_b][1] while k_b != -1: #链表b还有剩余数据未插入 data_a.append([data_b[k_b][0],-1]) data_a[pre_a][1] = len(data_a)-1 pre_a = data_a[pre_a][1] k_b = data_b[k_b][1] #输出显示合并后的链表 print(data_a) tmp = head_a while data_a[tmp][1] != -1: print(data_a[tmp][0],end="->") tmp = data_a[tmp][1] print(data_a[tmp][0]) $$