数据结构-链表

1、第二章 线性表 （一）讲授内容：（一）讲授内容： 1、线性表的类型定义。 2、线性表的顺序表示和实现。 3、线性表的链式表示和实现。 4、一元多项式的表示及相加。 (二二) 教学要求：教学要求： 1、了解线性表的逻辑结构特性（数据元素之间存在着线性关系）， 在计算机中表示线性表数据元素关系的两种方法：顺序存储结构 和链式存储结构，以及由两种关系表示得到的顺序表、链表。 2、熟练掌握这两种存储结构的描述方法。 3、熟练掌握线性表在顺序存储结构上的各种基本操作：查找、插 入和删除的算法。 4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在 实际应用中选用适当的链表结构。了解静态链表的定义及

2、实现方 法。 5、能够从时间和空间复杂度的角度综合比较线性表两种存储结构 的不同特点、各种操作的算法复杂度分析及其适用场合。 （三）教学重难点：（三）教学重难点： 教学重点：教学重点： 线性表的基本概念、顺序表 的实现及应用；单链表、循环链表以及 双向链表的定义、实现及应用。 教学难点：教学难点： 实现链表删除与插入操作时 指针的变化以及特殊情况处理。 学时分配：学时分配：本章共讲授12学时。 线性结构的特点 在数据元素的非空有限集中 存在唯一的一个被称作“第一个第一个”的数据元素 存在唯一的一个被称作“最后一个最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱前驱 除最后一

3、个外，集合中的每个数据元素均只有一个后继后继 2.1 线性表的类型定义 线性表(Linear List) ：由n(n0)个数据元素组成的有限 序列，这里的数据元素只是一个抽象的符号，其具体 含义在不同的情况下可以不同：数据元素可以是原子 类型，也可以是结构类型。 线性表举例 例 英文字母表（A,B,C,.Z)是一个线性表 例 计算机拥有量（6，17，28，50，92，188） 复杂线性表中的一个数据元素可由若干数据项数据项组成（结构类型）， 此时又把数据元素称作记录记录，把含有大量记录的线性表称作文件文件。 例 学号姓名年龄 001张三18 002李四19 数据元素 文件文件 数据项数据项 线

4、性表特征 线性表中的元素具有相同属性， 相邻元素之间存在序偶关系，1i0时通 常表示成下列形式： ),.,.,( 121nii aaaaaL 线性表的ADT 讲解：P19 注意：数据结构的基本运算，不是它的全部运 算。每一个基本运算在实现时可根据不同的存 储结构派生出一系列相关的运算来。 例：线性表的查找在链式存储结构中还会有按 序号查找 例：插入运算，可以是将新元素插入到适当 位置上 建议：掌握了某一数据结构上的基本运算后， 其它的运算可以通过基本运算来实现，也可以 直接去实现。 线性表的高级操作 合并 分拆 复制 P20 例子2.1 线性表的合并 利用两个线性表LA和LB分别表示两个集合A

5、和 B，现要求一个新的集合A=AB。 集合的合并运算说明： 1、 LB中与LA中相同的元素不予合并。 2 、不另建新线性表，只需扩大表LA，将LB中需要并入的元素插入 到LA中。 3 、LB中需要并入的元素作为LA的尾元素插入。 算法2.1 void union(List Lb_len=ListLength(Lb);/求线形表的长度 for(i=1; i =lb_len; i +) GetElem(Lb， i ，e);/取Lb中第 i个数据元素赋给e if(!LocateElem(La,e,equal) ListInsert(La，+La-len，e); / La中不存在和e相同的元素，则插入

6、之 并集运算算法时间复杂度分析 查找一个元素LB（i）是否在表LA中，需要扫 描 整 个 表 L A ， 即 进 行 比 较 的 时 间 为 O(ListLenth(LA)；每插入一个元素所需时间为 常数时间O(1)；共调用ListLenth(LB)次元素查 找过程，插入元素的个数不会大于LB的长度 ListLenth(LB) ，所需查找时间的复杂度为 O(ListLenth(LA) * ListLenth(LB)。 例子2.2 线性表的归并 例2-2 巳知线性表LA和线性表LB中的数据元 素按值非递减有序排列，现要求将LA和LB归 并为一个新的线性表LC，且LC中的元素仍按 值非递减有序排列

7、。 例子2.2 线性表的归并 算法的思想： 从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是 LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素逐个 插入到LC即可。 为了使得LC中的元素按值非递减有序排列，可分别设两个指针i和j分 别指向LA和LB中的某个元素，若设i当前所指的元素为a，j当前所指的元 素为b，则当前应插入到LC中的元素c为: 显然，指针i和j的初值均为1，在所指元素插入到LC之后，在LA或LB 中顺序后移。 bawhenb bawhena c 例2.2 线性表的归并 例如，设 LA=（3，5，8，11） LB=（2，6，8，9，11，15，20）

8、 则 LC=（2，3，5，6，8，8，9，11，15， 20） 算法2.2 void Merge List( List La, List Lb, List i = j = 1; k = 0; La_len = ListLength( La ); Lb_len = ListLength( Lb ); while( ( i= La_len ) GetElem( Lb, j, bj ); if ( ai = bj ) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; /当其中一个线形表的数据元素均已插入到线形表Lc中后，只要将另外一个线形 表中的剩余元素依次插入即可。 while ( i= la_len ) GetElem( La, I+, ai ); ListInsert( Lc, +k, ai ); while ( j= lb_len ) GetElem( La, j+, bj); ListInsert( Lc, +k, ai ); / Merge List 归并算法时间复杂度分析 归并算法的时间复杂度为： O(ListLenth(A)+ListLenth(B)。 虽然归并算法中含3个(while)循环语句，但 只