浙教版 (2019)选修1 数据与数据结构2.2 链表说课ppt课件

这是一份浙教版 (2019)选修1 数据与数据结构2.2 链表说课ppt课件，共26页。PPT课件主要包含了head等内容，欢迎下载使用。

情境导入——排队与插队
数组的缺点：插入和删除元素操作需要移动大量的元素频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费
整队前的位置和链接关系
链表指的是将需要处理的数据对象以结点的形式，通过指针串联在一起的一种数据结构。
保存相邻结点的存储地址
头指针（head）作用：
一是链表的入口，只有通过头指针才能进入链表
二是为循环链表设立一个边界，便于数据处理时的边界判断和处理
根据每个结点中指针的数量分为：
第一个结点和最后一个结点使用指针链接，这样就形成了循环链表。
单向链表中各个结点在内存中可以随意存储，每个结点使用指针指向其后继结点的存储地址。进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。
（1）同一链表中每个结点的结构均相同
（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理
（3）链表占用的空间不固定
链表的基本操作——链表的创建
Item=[]Head=-1
其中head值为–1，表示头指针指向为空，该链表为空链表。
创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。
链表的基本操作——链表的访问
链表只能通过头指针（head）进行访问，其他结点通过结点间的指针依次访问。如图，当想访问单向链表中data3所在的结点时，需通过头指针进入链表，再分别按照各个结点的指针指向经过data1和data2所在结点，最后通过data2所在结点的指针才能访问data3所在的结点。
链表的基本操作——链表结点的插入与删除
在单向链表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中每个结点的数据区域的值。
链表的基本操作——数据合并程序实现
链表的基本操作——链表结点的访问与遍历
（1）抽象与建模 该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下人员的初始编号。
（2）设计数据结构与算法 该问题中数据规模在初始时可以确定（最大为n），但是在数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。 由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：
算法如下： ①创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。 ②重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数m时，将对应的链表结点删除，若删除的结点为头结点，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数器i的值为1。 ③将链表中唯一结点，也就是头指针指向的结点中的数据（即初始编号）输出。
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）