(C语言详细版)第二章线性表讲述.ppt

重点：顺序表和链表上各种基本算法的实现及相关的时间性能分析 难点：线性表应用的算法设计;第二章 线性表;第二章 线性表;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2线性表的顺序表示和实现 --顺序表的存储;2.2线性表的顺序表示和实现 --类型定义与基本操作实现;2.2线性表的顺序表示和实现 --类型定义与基本操作实现;2.2线性表的顺序表示和实现 --类型定义与基本操作实现;2.2线性表的顺序表示和实现 --类型定义与基本操作实现;2.2线性表的顺序表示和实现 --类型定义与基本操作实现;2.2 –插入操作的实现;2.2 –插入操作的实现;2.2 –插入操作的实现;2.2 –插入操作的实现;2.2 –插入操作的实现;2.2 –删除操作的实现;2.2 –算法设计;单链表 静态链表 循环链表 双向链表 其他 ;单链表 顺序映像的弱点 空间利用率不高（预先按最大空间分配） 表的容量不可扩充（针对顺序表的方案一） 即使表的容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销，也不允许它频繁地使用 插入或删除时需移动大量元素 链表定义 特点 逻辑上相邻的元素，物理上未必相邻；非随机存取;链表定义 结点-数据元素的存储映像，包括数据域和指针域（其信息称为指针或链） 头指针-链表存取的开始 ；空(NULL)-最后一个结点的指针 ;2.3.1 线性链表–单链表;链表定义typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //后向指针域}LNode, *LinkList;;2.3.1 线性链表–单链表;2.3.1 线性链表–单链表;基本操作的实现 演示 删除操作ListDelete_L(LinkList L, int i, ElemType e) 创建单链表CreateList_L(LinkList L) 头插法 尾插法;基于单链表的算法设计 不能简单地用基本操作的实现来替换 要结合问题的处理特征和存储结构的特征进行适当的整合！;静态链表 问题：若语言不支持指针类型，能有链式存储吗？可以借用一维数组来表示链表-静??链表 数组元素(数据元素的值、指示器)-结点 类型定义#define MAXSIZE 1000typedef struct{ ElemType data; int cur; //替代动态链表结点中的指针域}component, SLinkList[MAXSIZE];;循环链表 问题1如何从一个结点出发，访问到链表中的全部结点？——循环链表 问题2如何在O(1)时间内由链表指针访问到第一个结点和最后一个结点？——头指针表示/尾指针表示 与单链表在基本操作的实现上的差异如链表的创建循环结束条件的判断:p==NULL = p==L;双向链表 问题如何在O(1)时间内找到一个结点的直接前驱和后继？——双向链表 类型定义typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next;}DuLNode, *DuLinkList; 基本操作：插入、删除;存储结构的具体设计结合实际问题操作的特征以及环境进行选取如单链表的另一种结构 有序表 ——一种特殊的线性表 有序顺序表、有序链表 插入操作的特殊性;难点：基于链表的应用 应用问题的分类：合并/分解 算法的基本框架 几个典型的例子 例2-1, 例2-2—合并 简单的单表分解释放 *双向循环链表的自身变换;第二章 习题;FAQ