第三讲顺序表.ppt

滨州学院计算机科学技术系 第二章 线性表 线性表概述 顺序表的存储及基本操作 本讲内容 一、线性表的逻辑结构特点 二、线性表的ADT定义 三、线性表的顺序存储 ---- 顺序表 顺序表的基本形态 定义：SqList L; 空表 L.length=0 可插入不可删除 表满 L.length=L.listsize 可删除不可插入 (空间需再分配) 表不空不满 0L.lengthL.listsize 可删除可插入 根据元素位置查询值 if( i0 i=L.length ) { e = L.elem[i-1]; return OK; } else return ERROR; 需考虑的问题（步骤） 当前表是否已满？ 输入（插入位置）是否有效？ 移动元素并插入 顺序表操作的效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，而移动元素的个数取决于插入或删除元素的位置。 以插入为例分析： 若插入在尾元素之后，则根本无需移动（特别快）； 若插入在首元素之前，则表中元素全部要后移（特别慢）； 推导： 假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均 若在首元素前插入，需要后移n次； 若在a1后面插入，要后移n-1个元素； …… 若在an-1后面插入，要后移1个元素； 若在尾元素an之后插入，则后移0个元素； 所有可能的元素移动次数合计： 0+1+…+n = n(n+1)/2 共有多少种插入形式? ——连头带尾有n+1种! 故插入时的平均移动次数为： n(n+1)/2÷（n+1）＝n/2 顺序表插入操作的时间复杂度为T(n)= O(n)  顺序表---- 算法分析 小结： 线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点:可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素;需要预先确定数据元素的最大个数。 解决问题的思路：改用另一种线性存储方式 复习内容 线性表的逻辑结构特点 顺序表的存储实现 顺序表的基本操作实现及性能分析 下节课我们将要学习： 顺序表的简单应用 单链表的存储实现 单链表的基本操作实现及特点 单链表与顺序表的区别 Status ListDelete_Sq (SqList L, int i, ElemType e) { if (i1 || iL.length) return ERROR; //i值不合法 e = L.elem[i-1]; for(j=i; j=L.length-1; j++) L.elem[j-1]=L.elem[j]; //元素前移 --L.length; return OK; } // ListDelete_Sq 算法时间复杂度为: O( n) 同理可证： 顺序表删除一元素的时间效率为: f(n)=(n-1)/2  T(n)=O(n) 即插入、删除算法的时间复杂度为 O(n) 在n+1处插入，不需移动 O(n) 移动元素 插入 删除第n个，不需移动 O(n) 移动元素 删除 最好情况 时间复杂度 平均移动次数 基本 操作 算法 链式存储结构 设计以下算法，用类C语言描述 ： 在非递减有序的顺序表L中插入元素e，使其仍保持有序。 书面作业 思考 1 编写一算法，从一顺序表中删除自第 i 个元素开始的 k 个元素 数据结构 * 信息工程系 信息工程系 线性结构的基本特征为: 1．集合中必存在唯一的一个“第一元素”； 2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素之外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 是一个数据元素的有序(次序)集 线性表是一种最简单的线性结构 一、线性表的逻辑结构 线性表的基本术语 定义： n（n=0）个具有相同特性的数据元素 组成的有限序列； 表示：L={ a1 ,…, ai-1, ai, ai+1, …, an } ai必须具有相同特性，即属于同一数据对象 ai-1是ai的直接前驱，ai+1是ai的直接后继 数据元素ai在线