数据结构讲义第2章新1.ppt

* * 线性结构的基本特征为: 1．集合中必存在唯一的一个“第一元素”； 2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 线性结构 是 一个数据元素的有序（次序）集 线性表是一种最简单的线性结构 2.1 线性表的类型定义 2.3 线性表类型的实现 ? 链式存储 2.4 一元多项式的表示 2.2 线性表类型的实现 ? 顺序存储 2.1 线性表的类型定义 最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。 顺序映象 —— 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系x,y。 用一组地址连续的存储单元 依次存放线性表中的数据元素 a1 a2 … ai-1 ai … an 线性表的起始地址 称作线性表的基地址 以“存储位置相邻”表示有序对ai-1，ai 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量↑ 所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址 例如：顺序表 23 75 41 38 54 62 17 L.elem L.length L.listsize e = 38 p p p p p i 1 2 3 4 1 8 50 p 可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。 线性表操作 ListInsert(L, i, e)的实现： 首先分析: 插入元素时， 线性表的逻辑结构发生什么变化？ (a1, …, ai-1, ai, …, an) 改变为 (a1, …, ai-1, e, ai, …, an) a1 a2 … ai-1 ai … an a1 a2 … ai-1 … ai e an ai-1, ai ai-1, e, e, ai 表的长度增加 考虑移动元素的平均情况: 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为： 若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为： 21 18 30 75 42 56 87 21 18 30 75 例如：ListInsert_Sq(L, 5, 66) L.length-1 0 p p p q 87 56 42 66 q = (L.elem[i-1]); // q 指示插入位置 for (p = (L.elem[L.length-1]); p = q; --p) *(p+1) = *p; p 线性表操作 ListDelete(L, i, e)的实现： 首先分析： 删除元素时， 线性表的逻辑结构发生什么变化？ (a1, …, ai-1, ai, ai+1, …, an) 改变为 (a1, …, ai-1, ai+1, …, an) ai+1 … an ai-1, ai, ai, ai+1 ai-1, ai+1 表的长度减少 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 考虑移动元素的平均情况: 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为： 若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为： 一、单链表 二、结点和单链表的 C 语言描述 三、线性表的操作在单链表中的实现 四、一个带头结点的单链表类型 五、其它形式的链表 用一组地址任意的存储单元存放线性表中的数据元素。 一、单链表 以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象) 以“结点的序列”表示线性表 ?? 称作链表 以线性表中第一个数据元素 的存储地