数据结构第03讲_链表.pptVIP

两个单循环链表（用尾指针表示）的链接: P= A-next; A-next=B-next -next; free(B-next); B-next =p; A=B; A B A P 小结 (1)顺序是用数组实现的，而链表是用指针或“游标”来实现的。 (2)当线性表的长度变化较大，难以估计其存储规模时，益采用动态链表作为存储结构为佳；当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。（基于空间的考虑） (3)顺序表是一种随机存取结构，对表中任一结点都可在O(1)时间内直接存取。而链表中的结点则需用从头指针开始顺链扫描。 因此： 若线性表的主要操作是查找，很少涉及插入、删除时，可采用顺序表结构；若要频繁进行插入和删除，宜采用链表结构；若表的插入、删除操作主要发生在表的两端，则宜采用有尾指针的单循环链表。 小结 * * 显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null. * 显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null. * * * 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 线性表的链式存储结构，也称为链表。 2.3 线性表的链式表示和实现 存储方式： 用一组地址任意的存储单元存放线性表中的数据元素。 链表中数据元素的物理次序和逻辑次序不一定相同。 链表中如何表示数据元素之间的关系？ 数据元素之间的关系就需要附加指针信息来表示。 元素(数据元素的映象) 结点(表示数据元素) = + 指针(指示元素之间的关系) “结点的序列” 表示线性表——称链表。 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 2.3.1 线性链表 用一组任意的存储单元存放线性表中的数据元素，以元素(数据元素的信息) + 指针(指示后继元素的存储位置) = 结点(表示数据元素) info next 信息域 指针域 结点的结构 由于上述链表的每一个结点只包含一个指针域，故将这种链表称为线性链表或单链表。 以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。 a1 a2 ... an ^ 头指针 空指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。 a1 ... an ^ 头指针 头结点 地址 存储空间 … … … 110 H 200 … … … 130 C 135 135 E 170 … … … 160 M NULL 165 B 130 170 F 110 … … … 200 J 205 205 L 160 … … … 例1： 线性表（B，C，E，F，H ，J，L，M）的单链表示 意图见右： 头指针 head （165） 线性表的单链表存储结构 Typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList; LinkList L； // L 为单链表的头指针 注意：指针变量和结点变量是两个不同的概念。 2.单链表在抽象类型中的操作举例 GetElem(L,i,e) // 取第i个数据元素 ListInsert(L,i,e) // 插入数据元素 ListDelete(L,i,e) // 删除数据元素 ClearList(L) // 重置线性表为空表 CreateList(L,n) // 生成含n个数据元素的链表 例1：单链表中 GetElem(L,i,e) 的实现。 L 21 18 30 75 42 56 ∧ p p p j 1 2 3 则，查找第 i 个数据元素的基本操作为：移动指针；比较 j 和 i 单链表