数据结构二版杨枨数据结构：第三章：线性表幻灯片.ppt

* 第 * 页 第三章 线性表 3.1 线性表的定义 3.2 线性表的顺序存贮及其运算 3.3 线性表的链式存储结构及其运算 3.4 串 3.5 线性表的应用 3.6 小结 * 第 * 页 3.1 线性表的定义 定义： 线性表是由n个数据元素所构成的一个有限序列， 表中的每一个数据元素都具有相同的数据类型，可记为（a1, a2, ... ai, ... an-1, an）， 其中的每个ai就是一个数据元素，也称之为结点， a1为表中的第一个结点，而an为表中的最后一个结点。 结点与结点之间具有一定的前后次序关系，亦即除了第一个结点以外，每一个结点都有一个前驱，ai的前驱就是ai-1，除了最后一个结点以外，每一个结点都有一个后继，ai的后继就是 ai+1。 * 第 * 页 3.1 线性表的定义 定义 线性表中数据元素的个数n就是线性表的长度， 当n=0时，该线性表就是一张空表。 对于表中的每一个数据元素，它都有确定的位置，也就是该数据元素在表中的序号，比如结点ai是线性表中的第i个数据元素，因此，它的位置就是i。 组成节点的数据项称为结点中的数据域。 可以唯一地标识结点的数据域，称为结点的关键字。 * 第 * 页 3.1 线性表的定义 基本操作： 1. ? 初始化：构造一张空的线性表。 2. ? 销毁：销毁一张已存在的线性表。 3. ? 求长度：求出线性表中数据元素的个数。 4. ? 定位：找出线性表中满足特定条件的元素的位置。 5. ? 插入元素：在线性表中的特定位置之前插入新的数据元素。 6. ? 删除元素：删除线性表中特定位置的数据元素。 7. ? 取元素：根据数据元素的位置，从线性表中取出该元素。 8. ? 求前驱：求出线性表中特定数据元素的前驱。 9. ? 求后继：求出线性表中特定数据元素的后继。 10. 遍历：顺序访问线性表中的每个数据元素， * 第 * 页 3.2 线性表的顺序存贮及其运算 顺序表： 表中的结点依次存储在一组地址连续的存储单元中， 结点的逻辑顺序与它在存储器中的物理顺序一致 。 表中第i个结点的存储地址为：Loc(ai) = Loc(a1) + (i - 1) * m 图3-2-1顺序表的存储结构示意图 1 a1 2 a2 . . . . . . i ai . . . . . . 表中的逻辑位置 结点 Loc(a1) a1 Loc(a1) + m a2 . . . . . . Loc(a1) + (i -1) * m ai . . . . . . 存储地址 结点 ? * 第 * 页 3.2 线性表的顺序存贮及其运算 顺序表的特性 只要知道了表中第一个结点的存储位置，就可以得到表中任意结点的存储位置。 通常采用一维数组来表示顺序表的存储结构。 定义模式： typedef struct slist_st { ELEMENT *element; int size; int length; } SLIST; 其中element指向描述顺序表的数组的起始地址，代表线性表的头， 线性表所需的空间--size，亦即线性表的容量， length表示线性表的当前长度。 ELEMENT是顺序表中结点的数据类型，例如，它可以为如下的一个结构类型： typedef struct element_st { int data; ... }ELEMENT; * 第 * 页 3.2 线性表的顺序存贮及其运算 顺序表的具体操作实现： 1. 初始化 2. 销毁 3. 求长度 4. 定位 5. 插入元素 6. 删除元素 7. 取元素 8. 求前驱 9. 求后继 10. 遍历 * 第 * 页 3.3 线性表的链式存储结构及其运算 顺序存储也有明显的缺点 ： 占据较大的连续存储空间，不利于零碎内存空间的利用。 在数据元素的插入和删除时，为了保证逻辑关系与物理位置的对应，必须要移动元素。 线性表的链式存储结构 ： 线性链表 双向链表 循环链表 * 第 * 页 3.3.1 线性链表 数据元素的逻辑关系是通过指针来表示的 结点除了要有存储数据元素的数据域外，还要有存储指示其与其它元素的逻辑关系的指针。 结点的一般形式： data next a1 ? a2 ? an ^ 图3-3-1线性链表的结构 ? ? * 第 * 页 3.3.1 线性链表 存储结构定义： /* 链表中结点的数据域内容的结构类型 */ typedef struct element_st { int data; ... } ELEMENT; /* 结点的结构类型 */ struct node_st { ELEMENT