(
课件网) 选择性必修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 ... ...
