2.2 链表（教学课件）信息技术浙教版2019选择性必修1

第2节 链表（3课时） 第2章 数组与链表 浙教版（2019） 选修一 链表的概念与特性 01 链表的基本操作 02 学习目录 初步理解数据结构的概念及其作用。 01 能运用链表编程解决实际问题。 03 掌握链表的基本操作。 02 学习目标 PART 01 链表的概念与特性 新课导入 排队 与插队 新课导入 排在这里 数组的缺点: ※插入和删除元素操作需要移动大量的元素 ※频繁增、删数据导致数据规模不稳，形成存储空间“碎片” ※需要限定最大空间，造成资源浪费 新课导入 链表是一种存储空间利用率高的数据结 构， 适用于数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致 数据规模不稳定的问题。 链表 链表的概念与特性 一 1 2 指针区域 数据区域 概念：将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 一个链表的节点 保存数据元素 保存相邻结点的存储地址 两部分组成 链表的概念与特性 一 01 STEP 02 STEP 03 STEP 每个结点使用指针指向其后继结点的存储地址 单向链表中各个结点在内存中可以非顺序存储 进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。 链表的组成 ※头节点:用于进入链表和边界判断 ※前驱节点:某个节点前面的相邻节点 ※后继节点:某个节点后面的相邻节点 ※尾节点:最后一个节点，指针指向空 前驱节点 某节点 后继节点 链表的概念与特性 一 单向链表在内存中的存储模式 单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。 进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。 链表的概念与特性 一 吴坚 王林 黄刚 李丰 ∧ head 链表内存存放方式： head头节点 数据域 指针域 tail None 头指针的作用 01 02 链表的入口，只有通过头指针才能进入链表。 为循环链表设立一个边界，便于数据处理时的边界判断和处理。 链表的概念与特性 一 链表的特性 同一链表中每个节点的结构均相同 ① 链表节点中包含数据区域和指针区域。不管是单向链表还是双向链表，每个节点的数据区域中的数据类型是相同的，指针区域中的指针数量和功能是相同的。 数据区域 指针区域 数据类型相同 指针数量和功能相同 链表的概念与特性 一 链表的特性 每个链表必定有一个头指针，以实现对链表的引用和边界处理 ② 链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。 一个头指针 对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。 head 链表的概念与特性 一 链表的特性 链表占用的空间不固定 ③ 链表的节点间通过指针相连，相邻节点存储时不需要连续空间，充分利用了内存的零散空间，提高了存储空间利用率。由于链表的存储空间由节点数决定，增加或减少节点都会改变链表占用的存储空间，因此链表占用的空间不固定。 链表的概念与特性 一 只需知道数据之间相互链接的顺序 探讨与讨论 1.以下有关链表的描述,不正确的是( ） A.插入、删除操作无须移动数据元素 B.增加或减少节点会改变链表占用的存储空间 C.可随机快速访问任何一个数据元素 D.同一链表中每个节点的结构均相同 C 链表的基本操作 PART 02 链表的基本操作 二 节点访问 节点插入 删除 基本操作 空链表的创建 链表的基本操作 链表的基本操作 二 Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。 实现单向链表时，列表中的每个数据项作为链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，另一个作为指针域存储后继节点在列表中的指针。 用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。 165 2 162 1 172 0 160 -1 head 头节点 尾节点 b=[[165,2],[160,-1],[162,1],[172,0]] 链表的基本操作 二 链表的创建 创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。 item=[ ] head=-1 其中head值为-1，表示头指针指向为空，该链表为空链表。 使用列表模拟链表 例如: a =[[ 99, 1 ],[ 95, 2 ],[ 88, -1] ] 列表a中有3个元素:[99,1]、[95, 2] 、[88,-1] 数据元素(a[0])的第一个元素(99)为数据域。 数据元素(a[0])的第二个元素(1)为指针域，是列表a的第二元素的索引。 头指针=0为开始节点 尾指针=-1 为尾节点，表示指向为空。 链表的基本操作 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a: a=[[“hello”,1],[“china”,3],[“Olympics”,-1],[“winter”,2]] head=0 ①a[1][1]的值为:（ ） A.1 B.2 C.0 D.3 ②a[1][1]的含义是什么? D china后面指向的下一个节点是[“winter”,2] 链表的基本操作 二 链表节点的访问 链表只能通过头指针(head)进行访问，其他节点通过节点间的指针依次访问。如图，当想访问单向链表中data3所在的节点时，需通过头指针进入链表，再分别按照各个节点的指针指向经过data1和data2所在节点，最后通过data2所在节点的指针才能访问data3所在的节点。 链表的基本操作 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.有如下python程序段： a = [[3, 2], [2, 3], [7, 1], [1, 0]] head = 0 p = head while a[p][1] != head: print(a[p][0], end="->") p = a[p][1] print(a[p][0]) 执行上述语句后，程序输出的结果为（ ） 3->7->2->1 链表的基本操作 二 链表节点的插入与删除 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的指针，将新节点插入到链表的正确位置。链表节点的删除，则通过将需要删除的节点的前驱节点和其后继节点直接相连的方式实现。 链表的插入 以单向链表插入新节点为例，在空单向链表中插入第一个节点或在非空单向链表中插入第一个节点时，需要先修改新节点的指针指向与头指针一致，再修改头指针指向新节点;在非空单向链表两个节点中间插入新节点时，需要先修改新节点指针指向与前一节点的指针指向一致，再将前一节点的指针指向新节点。 单向链表中插入新节点的过程 链表的基本操作 二 现有链表a=[[“t”,2],[“y”,0],[“o”,-1]]，要实现分别在头部（插入p），中间（在t后面插入h）和尾部（插入n）插入新节点，最终形成链表a=[[“t”,4],[“y”,0],[“o”,5],[“p”,1],[“h”,2],[“n”,-1]]，请思考形成过程，并尝试用代码实现。 0 t 2 1 y 0 2 o -1 head 0 t 4 1 y 0 2 o 5 3 p 1 4 h 2 5 n -1 head 链表的插入 链表的基本操作 二 链表的插入 一般先在列表尾部插入新节点，再寻找其前驱节点在列表中的索引，然后修改相关节点的指针区域的值。 从头部插入新节点 0 t 2 1 y 0 2 o -1 head→ 0 t 2 1 y 0 2 o -1 head→ 3 p 1 a=[["t",2],["y",0],[“o",-1]] head=1 new_data="p" a.append([new_data,head]) head=len(a)-1 print(head,a) 运行结果 3 [['t', 2], ['y', 0], ['o', -1], ['p', 1]] 链表的基本操作 二 链表的插入 从中间插入新节点 0 t 2 1 y 0 2 o -1 3 p 1 head→ 4 h 2 a=[["t",2],["y",0],["o",-1],["p",1]] head=3 new_data="h" p=0 a.append([new_data,a[p][1]]) a[p][1]=len(a)-1 print(head,a) 0 t 2 1 y 0 2 o -1 3 p 1 4 运行结果 3 [['t', 4], ['y', 0], ['o', -1], ['p', 1], ['h', 2]] head→ 链表的基本操作 二 链表的插入 从尾部插入新节点 0 t 4 1 y 0 2 o -1 3 p 1 4 h 2 0 t 4 1 y 0 2 o -1 3 p 1 4 h 2 head→ 5 n -1 a=[["t",4],["y",0],["o",-1],["p",1],["h",2]] head=3 new_data="n" p=head while a[p][1]!=-1: p=a[p][1] a.append([new_data,a[p][1]]) a[p][1]=len(a)-1 print(head,a) 5 运行结果： 3 [['t', 4], ['y', 0], ['o', 5], ['p', 1], ['h', 2], ['n', -1]] head→ 运行结果 3 [['t', 4], ['y', 0], ['o', 5], ['p', 1], ['h', 2], ['n', -1]] 链表的基本操作 二 链表元素的插入 0 t 2 1 y 0 2 o -1 head→ 0 t 2 1 y 0 2 o -1 head→ 3 p 1 4 h 2 0 t 2 1 y 0 2 o -1 3 p 1 head→ 4 0 t 4 1 y 0 2 o -1 3 p 1 4 h 2 5 n -1 5 head→ ①从头部插入p ②从中间插入h ③从尾部插入n 链表的基本操作 二 链表元素的插入 ①从头部插入 ②从中间插入 ③从尾部插入 a=[["t",2],["y",0],[“o",-1],["p",1]] head=1 new_data="x" a.append([new_data,head]) head=len(a)-1 print(head,a) a=[["t",2],["y",0],["o",-1],["p",1]] head=3 new_data="x" p=0 a.append([new_data,a[p][1]]) a[p][1]=len(a)-1 print(head,a) a=[["t",4],["y",0],["o",-1],["p",1]] head=3 new_data="x" p=head while a[p][1]!=-1: p=a[p][1] a.append([new_data,a[p][1]]) a[p][1]=len(a)-1 print(head,a) 链表的基本操作 二 链表元素的删除 删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。 链表节点的删除，并没有将元素从列表中删除，而仅仅是修改了节点指针域的值，通过将被删除节点的前驱节点和其后继节点直接相连的方式实现。 尾节点可以直接删除，若删除了头节点，则需要修改头指针。 0 t 2 1 y 0 2 o -1 head→ 链表的基本操作 二 删除结点 list[s][1] =list[p][1] next[s] = next[p] 两个一维列表放数据和地址 一个二维列表放数据和地址 链表的基本操作 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.有如下python程序段： a=[[7,1],[8,2],[9,-1],[6,0]] head=3 head=a[head][1] 则程序执行后，链表a有几个节点（ ） A.1 B.2 C.3 D.4 程序实现了什么功能？ 程序执行后链表a变为 ： C 删除了头部节点[6,0] a=[[7,1],[8,2],[9,-1],[6,0]] 链表的基本操作 二 链表节点的访问与遍历 由于链表中的节点通过指针相互链接，当需要访问某个位置的节点元素时，只能通过头指针进入链表并通过节点间的链接关系一个一个往下访问，直到找到指定位置的节点。 与数组相比，其节点的访问效率较低。 实现链表及其基本操作后，可以使用其存储和处理数据，帮助人们解决问题。 链表的基本操作 二 约瑟夫问题 n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m（m＞1）的人退出圈子。 这样不断循环下去，圈子里的人数将不断减少。由于人数是有限的（n个），因此最终会只剩下1个人。 试问：最后剩下的人的初始编号是多少? 链表的基本操作 二 抽象与建模 1 该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数， 每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从 1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而 将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下 人员的初始编号。 链表的基本操作 二 设计数据结构与算法 2 01 STEP 02 STEP 03 STEP 重复执行下列处理，直到链表中只剩下一个节点。 创建一个由n个节点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个节点。 将链表中唯一节点，也就是头指针指向的节点中的数据（即初始编号）输出。 链表的基本操作 二 编写程序 3 程序： llist=[] n=int(input("请输入参与人数(N):")) m=int(input("请输入淘汰数(M):")) for i in range(n–1): llist.append([i+1,i+1]) 测试结果： 测试结果1： 请输入参与人数(N)：400 请输入淘汰数(M)：2 最后一人的起始编号是： 289 链表的基本操作 二 llist.append([n,0]) #将尾节点的指针指向头节点，构成循环单向链表 head=0 long=n k=head i=1 while long>1: i=i+1 if i==m: t=llist[k][1] llist[k][1]=llist[t][1] if t==head: #删除节点为头指针指向的节点 head=llist[k][1] i=1 long=long–1 k=llist[k][1] print(llist[head][0]) 测试结果2： 请输入参与人数(N)：5000 请输入淘汰数(M)：15 最后一人的起始编号是： 152 拓展链接 三 链表的类实现 在Python中，链表除了可以使用列表来实现，还可以使用“类”来实现。“类”是一种抽 象的数据结构，它将数据及其操作封装在一起。 自定义单向链表的节点类，代码如下： 1 只需知道数据之间相互链接的顺序 class LinkNode: #定义节点类LinkNode def __init__(self,data,next_=None): #初始化节点包含两个区域self.data、self.next_ self.data=data #self.data区域保存数据 self.next_=next_ #self.next_区域保存指针 拓展链接 三 链表的类实现 有了以上类的构造，就可以创建单向链表并进行空表判断、增删节点等基本操作。使用自定义类的方式建立的单向链表可以充分体现链表的特性。 构造单向链表类，代码如下： 2 只需知道数据之间相互链接的顺序 class LinkList: #定义单向链表类LinkList def __init__(self): #初始化空链表 self._head=None #空链表头指针指向为空 链表 四 小 结 一、链表的概念与特性 1. 链表的概念 2. 链表的特性 （1）同一链表中每个节点的结构均相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 二、链表的基本操作 1. 链表的创建 2. 链表节点的访问 3. 链表节点的插入与删除 4. 链表节点的访问与遍历 谢谢观看 第2节 链表 浙教版（2019） 选修一 $$