2.2.1 链表的概念、特性、基本操作 ppt课件 数据 与数据结构-新浙教版（2019）《高中信息技术》选择性必修第一册.pptx

1、选择性必修1数据与数据结构第二章 数组与链表 2.2.1链表的概念、特性、基本操作情境导入排队与插队情境导入排队与插队数组的缺点：插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费链表基本概念整队前的位置和链接关系链表指的是将需要处理的数据对象以结点的形式，通过指针串联在一起的一种数据结构。链表结点结构保存数据元素 保存相邻结点的存储地址链表基本概念：头指针（head）作用：一是链表的入口，只有通过头指针才能进入链表二是为循环链表设立一个边界，便于数据处理时的边界判断和处理链表基本概念链表的基本概念根据每个结点中指针的数量分

2、为：单向链表：双向链表：循环链表：第一个结点和最后一个结点使用指针链接，这样就形成了循环链表。next吴坚黄刚王林李丰headnextnextnext链表基本概念 单向链表中各个结点在内存中可以随意存储，每个结点使用指针指向其后继结点的存储地址。进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。链表的特性（1）同一链表中每个结点的结构均相同数据类型相同指针数量和功能相同（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理head（3）链表占用的空间不固定链表的基本操作链表的创建Item=Head=-1其中head值

3、为1，表示头指针指向为空，该链表为空链表。创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。链表的基本操作链表的访问 链表只能通过头指针（head）进行访问，其他结点通过结点间的指针依次访问。如图，当想访问单向链表中data3所在的结点时，需通过头指针进入链表，再分别按照各个结点的指针指向经过data1和data2所在结点，最后通过data2所在结点的指针才能访问data3所在的结点。链表的基本操作链表结点的插入与删除New datanextdata1nextdata2nextdata3-1

4、headNew datanextdata1nextdata2nextdata3-1headnext在单向链表data1和data2所处结点的中间位置插入一个新结点1.在单向链表中插入新结点时，指针指向的修改是否必须有先后？如果将其顺序逆转，能否完成新结点的插入？为什么？链表的基本操作链表结点的插入与删除在列表模拟实现的链表中插入新结点的过程data81=data11data11=8实现语句：参考上图，描述出在有8个结点的单向链表中删除第一个结点、中间结点及尾结点的过程。链表的基本操作数据合并 （1）算法设计 初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链

5、表的头指针，其中data_a作为存储结果的链表。使用随机函数randint(start,end)模拟生成两个降序序列数据，生成新的结点在尾部插入。链表的基本操作数据合并 （1）算法设计 使用变量k_a与k_b指向两个链表中未合并的数据序列中最前面（值最大）的结点，初始化k_a=head_a，k_b=head_b，由于在链表data_a中需要进行插入结点的操作，必须记录插入位置的前驱结点，使用变量q_a，初始化q_a=head。重复以下操作，直到k_a或k_b指向空（即某个链表元素全部处理完）：比较data_ak_a0和data_bk_b0的大小。若data_ak_a0data_bk_b0，则修

6、改q_a与k_a相等，再将k_a指向下一个结点；否则将链表data_b中k_b指向的结点插入到链表data_a中，作为q_a指向结点的后继结点，再将k_b指向链表data_b中的下一个结点。若k_b未指向空，则将链表data_b剩余结点按顺序插入链表data_a的尾部。输出链表data_a中每个结点的数据区域的值。链表的基本操作数据合并程序实现程序测试结果from random import randintdata_a=head_a=-1data_b=head_b=-1tmp=randint(95,100)data_a.append(tmp,head_a)head_a=0for i in ra

7、nge(1,20):tmp=data_ai-10-randint(1,5)data_a.append(tmp,data_ai-11)data_ai-11=iprint(链表结构的原始数据序列一)print(data_a)链表结构的原始数据序列一99,1,98,2,94,3,93,4,91,5,89,6,85,7,84,8,79,9,75,10,72,11,71,12,66,13,64,14,59,15,54,16,52,17,48,18,44,19,43,-1链表的基本操作数据合并程序实现程序测试结果tmp=randint(95,100)data_b.append(tmp,head_b)hea

8、d_b=0for i in range(1,25):tmp=data_bi-10-randint(1,5)data_b.append(tmp,data_bi-11)data_bi-11=iprint(链表结构的原始数据序列二)print(data_b)#初始化列表索引k_a=head_aq_a=head_ak_b=head_b链表结构的原始数据序列二98,1,95,2,93,3,91,4,90,5,89,6,84,7,80,8,79,9,75,10,71,11,69,12,68,13,63,14,58,15,56,16,52,17,47,18,42,19,41,20,38,21,34,22,3

9、2,23,29,24,24,1链表的基本操作数据合并程序实现程序测试结果while(k_a!=-1 and k_b!=-1):if data_ak_a0=data_bk_b0:q_a=k_a k_a=data_ak_a1 else:if k_a=head_a:#在链表 data_a 的头部插入结点 data_a.append(data_bk_b0,head_a)head_a=len(data_a)-1 q_a=head_a k_b=data_bk_b1 else:data_a.append(data_bk_b0,k_a)data_aq_a1=len(data_a)-1 q_a=data_aq_

10、a1 k_b=data_bk_b1链表结构的合并后数据序列99,1,98,20,94,3,93,22,91,23,89,25,85,7,84,26,79,28,75,29,72,11,71,30,66,13,64,33,59,34,54,16,52,36,48,37,44,19,43,-1,98,21,95,2,93,4,91,24,90,5,89,6,84,27,80,8,79,9,75,10,71,31,69,32,68,12,63,14,58,35,56,15,52,17,47,18链表的基本操作数据合并程序实现程序测试结果while k_b!=-1:data_a.append(data

11、_bk_b0,-1)data_aq_a1=len(data_a)-1 q_a=data_aq_a1 k_b=data_bk_b1print(链表结构的合并后数据序列)print(data_a)print(按链表链接顺序输出数据序列)tmp=head_awhile data_atmp1!=-1:print(data_atmp0,end=)tmp=data_atmp1print(data_atmp0)链表结构的合并后数据序列99,1,98,20,94,3,93,22,91,23,89,25,85,7,84,26,79,28,75,29,72,11,71,30,66,13,64,33,59,34,5

12、4,16,52,36,48,37,44,19,43,38,98,21,95,2,93,4,91,24,90,5,89,6,84,27,80,8,79,9,75,10,71,31,69,32,68,12,63,14,58,35,56,15,52,17,47,18,42,39,41,40,38,41,34,42,32,43,29,44,24,1按链表链接顺序输出数据序列99 98 98 95 94 93 93 91 91 90 89 89 85 84 84 80 79 79 75 75 72 71 71 69 68 66 64 63 59 58 56 54 52 52 48 47 44 43 42

13、 41 38 34 32 29 24链表的基本操作链表结点的访问与遍历（1）抽象与建模 该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下人员的初始编号。链表的基本操作链表结点的访问与遍历（2）设计数据结构与算法 该问题中数据规模在初始时可以确定（最大为n），但是在数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据

14、规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：链表的基本操作链表结点的访问与遍历算法如下：创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰

15、数m时，将对应的链表结点删除，若删除的结点为头结点，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数器i的值为1。将链表中唯一结点，也就是头指针指向的结点中的数据（即初始编号）输出。链表的基本操作链表结点的访问与遍历程序测试结果llist=n=int(input(请输入参与人数（N）:)m=int(input(请输入淘汰数（M）:)for i in range(n-1):llist.append(i+1,i+1)llist.append(n,0)#将尾结点的指针指向头结点，构成循环单向链表 初始化约瑟夫环链表的基本操作链表结点的访问与遍历程序测试结果head=0long=nk=he

16、adi=1while long1:i=i+1 if i=m:t=llistk1 llistk1=llistt1 if t=head:#删除结点为头指针指向的结点 head=llistk1 i=1 long=long-1 k=llistk1print(llisthead0)测试效果 1：请输入参与人数(N)：400请输入淘汰数(M)：2最后一人的起始编号是：289测试效果 2：请输入参与人数(N)：5000请输入淘汰数(M)：15最后一人的起始编号是：152课堂小结学习评价对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）

17、评分项自我评价同学互评能理解链表的概念、组织结构及其特性。5 4 3 2 15 4 3 2 1了解链表的基本操作5 4 3 2 15 4 3 2 1能合理利用链表解决相应的简单问题并编程实现5 4 3 2 15 4 3 2 1课堂作业思考与练习1.在单向链表在内存中的存储模式图（图2.2.2）基础上，请根据双向链表和循环链表的特性，画出它们在内存中的存储模式图。2.参考图2.2.3，描述出在有3个结点的单向链表中删除第1个、第2个及第3个结点的过程。3.数组与链表作为存储相同类型数据的两种数据结构，拥有各自的应用场景、组织结构和操作特性，请根据教学内容进行简要概括并完善以下表格：数组数组链表链表应用场景应用场景适合数据规模确定且在处理过程中保持数据规模稳定的问题组织结构组织结构由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接操作特性操作特性优点：数据访问效率较高缺点：使用前需限定最大空间，容易造成空间资源的浪费