(共26张PPT)
选择性必修1《数据与数据结构》
第二章 数组与链表
2.2.1链表的概念、特性、基本操作
情境导入——排队与插队
情境导入——排队与插队
数组的缺点：
插入和删除元素操作需要移动大量的元素
频繁增、删数据导致数据规模不稳，形成存储空间“碎片”
需要限定最大空间，造成资源浪费
链表基本概念
整队前的位置和链接关系
链表指的是将需要处理的数据对象以结点的形式，通过指针串联在一起的一种数据结构。
链表结点结构
保存数据元素
保存相邻结点的存储地址
链表基本概念：
头指针（head）作用：
一是链表的入口，只有通过头指针才能进入链表
二是为循环链表设立一个边界，便于数据处理时的边界判断和处理
链表基本概念
链表的基本概念
根据每个结点中指针的数量分为：
单向链表：
双向链表：
循环链表：
第一个结点和最后一个结点使用指针链接，这样就形成了循环链表。
next
吴坚
黄刚
王林
李丰
head
next
next
next
链表基本概念
单向链表中各个结点在内存中可以随意存储，每个结点使用指针指向其后继结点的存储地址。进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。
链表的特性
（1）同一链表中每个结点的结构均相同
数据类型相同
指针数量和功能相同
（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理
head
（3）链表占用的空间不固定
链表的基本操作——链表的创建
Item=[]
Head=-1
其中head值为–1，表示头指针指向为空，该链表为空链表。
创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。
链表的基本操作——链表的访问
链表只能通过头指针（head）进行访问，其他结点通过结点间的指针依次访问。如图，当想访问单向链表中data3所在的结点时，需通过头指针进入链表，再分别按照各个结点的指针指向经过data1和data2所在结点，最后通过data2所在结点的指针才能访问
data3所在的结点。
链表的基本操作——链表结点的插入与删除
New data next
data1 next
data2 next
data3 -1
head
New data next
data1 next
data2 next
data3 -1
head
next
在单向链表data1和data2所处结点的中间位置插入一个新结点
1. 在单向链表中插入新结点时，指针指向的修改是否必须有先后？如果将其顺序逆转，能否完成新结点的插入？为什么？
链表的基本操作——链表结点的插入与删除
在列表模拟实现的链表中插入新结点的过程
data[8][1]=data[1][1]
data[1][1]=8
实现语句：
参考上图，描述出在有8个结点的单向链表中删除第一个结点、中间结点及尾结点的过程。
链表的基本操作——数据合并
（1）算法设计
①初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链表的头指针，其中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_a[k_a][0]和data_b[k_b][0]的大小。若data_a[k_a][0]≥data_b[k_b][0]，则修改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 randint data_a=[] head_a=-1 data_b=[] head_b=-1 tmp=randint(95,100) data_a.append([tmp,head_a]) head_a=0 for i in range(1,20): tmp=data_a[i-1][0]-randint(1,5) data_a.append([tmp,data_a[i-1][1]]) data_a[i-1][1]=i print(" 链表结构的原始数据序列一 ") 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]) head_b=0 for i in range(1,25): tmp=data_b[i-1][0]-randint(1,5) data_b.append([tmp,data_b[i-1][1]]) data_b[i-1][1]=i print(" 链表结构的原始数据序列二 ") print(data_b) #初始化列表索引 k_a=head_a q_a=head_a k_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],
[32, 23], [29, 24], [24, –1]]
链表的基本操作——数据合并程序实现
程序 测试结果
while(k_a!=-1 and k_b!=-1): if data_a[k_a][0]>=data_b[k_b][0]: q_a=k_a k_a=data_a[k_a][1] else: if k_a==head_a: # 在链表 data_a 的头部插入结点 data_a.append([data_b[k_b][0],head_a]) head_a=len(data_a)-1 q_a=head_a k_b=data_b[k_b][1] else: data_a.append([data_b[k_b][0],k_a]) data_a[q_a][1]=len(data_a)-1 q_a=data_a[q_a][1] k_b=data_b[k_b][1] 链表结构的合并后数据序列
[[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_b[k_b][0],-1]) data_a[q_a][1]=len(data_a)-1 q_a=data_a[q_a][1] k_b=data_b[k_b][1] print(" 链表结构的合并后数据序列 ") print(data_a) print(" 按链表链接顺序输出数据序列 ") 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]) 链表结构的合并后数据序列
[[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,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 41 38 34 32 29 24
链表的基本操作——链表结点的访问与遍历
（1）抽象与建模
该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下人员的初始编号。
链表的基本操作——链表结点的访问与遍历
（2）设计数据结构与算法
该问题中数据规模在初始时可以确定（最大为n），但是在数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。
由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：
链表的基本操作——链表结点的访问与遍历
算法如下：
①创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。
②重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数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=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]) 测试效果 1 ：
请输入参与人数 (N) ： 400
请输入淘汰数 (M) ： 2
最后一人的起始编号是： 289
测试效果 2 ：
请输入参与人数 (N) ： 5000
请输入淘汰数 (M) ： 15
最后一人的起始编号是： 152
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能理解链表的概念、组织结构及其特性。 5 4 3 2 1 5 4 3 2 1
了解链表的基本操作 5 4 3 2 1 5 4 3 2 1
能合理利用链表解决相应的简单问题并编程实现 5 4 3 2 1 5 4 3 2 1
课堂作业
思考与练习
1. 在单向链表在内存中的存储模式图（图2.2.2）基础上，请根据双向链表和循环链表的特性，画出它们在内存中的存储模式图。
2. 参考图2.2.3，描述出在有3个结点的单向链表中删除第1个、第2个及第3个结点的过程。
3. 数组与链表作为存储相同类型数据的两种数据结构，拥有各自的应用场景、组织结构和操作特性，请根据教学内容进行简要概括并完善以下表格：
数组 链表
应用场景 适合数据规模确定且在处理过程中保持数据规模稳定的问题
组织结构 由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
操作特性 优点：数据访问效率较高 缺点：使用前需限定最大空间，容易造成空间资源的浪费
