ds——第2章 线性表2-链式表示和实现.ppt

第2章 线性表 2.3 线性表的链式表示和实现 2.3 .1 链表的表示 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 与链式存储有关的术语： 何谓头指针、头结点和首元结点？ 例： 结点类型的C语言表示法 介绍三个有用的库函数（都在 中）： sizeof x ——计算变量x的长度； malloc m —开辟m字节长度的地址空间，并返回这段空间的首地址； free p ——释放指针p所指变量的存储空间，即彻底删除一个变量。 链表的实现 1. 单链表的插入 2. 单链表的删除 3. 链表的合并 1. 单链表的插入 2. 单链表的删除 3. 两个链表的归并（教材P31） 用链表可表示为： 算法分析： 其它链表形式 讨论2： 单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？ 链表的运算效率分析 1. 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O n 。 算法要求： 已知：线性表 A、B，分别由单链表 LA , LB 存储， 其中数据元素按值非递减有序排列， 要求：将 A ，B 归并为一个新的线性表C , C 的数据 元素仍按值非递减排列。设线性表 C 由单链表 LC 存储。 假设：A （3，5，8，11），B （2，6，8，9，11） 预测：合并后 C （ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ） 3 5 11 /\ 8 La 2 6 11 /\ 8 Lb 9 2 3 6 5 Lc 8 头结点 算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表； 比较：比较结点数据域中数据的大小； 插入：将两个结点中数据小的结点插入新链表。 La 3 5 8 11 ^ Lb 2 6 8 11 ^ 9 Pa Pb Pa Pb Pa、Pb用于搜索La和Lb， Pc指向新链表当前结点 Lc … Pa 3 Pc Pa 5 Pc 11 ^ Pc 2 Pb Pc Pa 算法实现： Void MergeList_L LinkList La, LinkList Lb, LinkList Lc //按值排序的单链表La、Lb，归并为Lc后也按值排序 free Lb ; //释放Lb的头结点 //MergeList_L pc- next pa?pa:pb ; //插入剩余段 while papb //将pa 、pb结点按大小依次插入C中 if pa- data pb- data pc- next pa; pc pa; pa pa- next; else pc- next pb; pc pb; pb pb- next pa La-- next; pb Lb-- next; Lc pc La； //初始化 * 2.3 线性表的链式表示和实现 2.3.1 单向线性链表 ★动态表示 ★静态表示 2.3.2 循环链表 2.3.3 双向链表 * 单向线性链表静态存储结构 #define MAXSIZE 1000 / /链表的最大长度 tpyedef struct ElemType data；//数据域  int cur； //指针域（存储数组下标） component, SLinkList[MAXSIZE]； * 静态链表的插入和删除操作示例 0 1 2 3 4 5 6 7 8 9 10 h 0 头结点 需要建立空闲结点链表 记录所有的空闲结点 * 小结 熟练掌握线性表的链式表示和基本操作 了解静态链表的结构 * 本章内容回顾 I. 线性表的概念 II. 线性表ADT III. 线性表的顺序表示和实现 IV. 线性表的链式表示和实现 答：能。只要将表中最后一个结点的指针域指向头结点即可 P- next head; 。这种形成环路的链表称为循环链表。 特别：带头结点的空循环链表样式 H 参见教材P35 特点： 1、从任一结点出发均可找到表中其他结点。 2、操作仅有 一 点与单链表不同：循环条件 单链表 ----- p NULL 或 p - next NULL 循环链表----- p head 或 p- next head 讨论1： 链表能不能首尾相连？怎样实现？ 答：能。只要把单链表再多开一个指针域即可 例如用*next和*prior; 。 双向链表在非线性结构（如树结构）中将大量使用。 next dat