《线性表_顺序表ppt讲解讲解》由会员分享，可在线阅读，更多相关《线性表_顺序表ppt讲解讲解（33页珍藏版）》请在金锄头文库上搜索。
1、思考题：抽象其数据模型 学生成绩登记表 职工工资登记表 抽 象 第二章 线性表 线性表是一种最基本、最简 单、最常用的线性结构 线性结构 是一个数据元素的有序（次序、位序）集 线性结构的基本特征为: 1集合中必存在唯一的一个“第一元素”； 2集合中必存在唯一的一个 “最后元素” ； 3除最后元素在外，均有 唯一的后继； 4除第一元素之外，均有 唯一的前驱。 线性结构 现实生活中线性结构的实例？ 2.1 线性表的类型定义 2.3 线性表类型的实现 链式映象 2.4 一元多项式的表示 2.2 线性表类型的实现 顺序映象 （a1, a2, ai-1，ai, ai1 ，, an） 一、线性表的逻辑结构
2、 线性表：是n个数据元素的有限序列 n=0时称为 数据元素 线性起点ai的直接前趋 ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总个 数，即表长 空表 线性终点 2.1 线性表的类型定义 二、抽象数据类型线性表的定义 ADT List 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 i 为 ai 在线性表中的位序。 数据关系： R1 |ai-1 ,aiD, i=2,.,n /设线性表为 (a1，a2, . . . ，ai，. . . ，an), 2.1 线性表的类型定义 基本操作： 引用型操作 加工型操作 A
3、DT List 接上 Init_List( 2依值在线性表LA中进行查访; 3若不存在，则插入之。 Get_Elem(LB, i)e Locate_Elem(LA, e, equal( ) List_Insert(LA, n+1, e) 操作步骤（进行List La, Lb 定义并赋值后) ： Get_Elem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!Locate_Elem(La, e, equal( ) ) List_Insert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之 void union(List / 求线性表的长度
4、Lb_len = List_Length(Lb); for (i = 1; i MaxSize) throw”参数非法”； for(i=0; i=MaxSize) throw “溢出”； if(ilength+1) throw “位置溢出”; for(j=length; j=i; j-) /j为元素序号 dataj=dataj-1;/ 后移 datai-1=x; / /插入 length+; O( n )算法的时间复杂度为： 首先分析： 删除元素时， 线性表的逻辑结构发生什么变化？ 三、顺序表操作的实现删除 T Delete( int i)； (a1, , ai-1, ai, ai+1, ,
5、an) 改变为 (a1, , ai-1, ai+1, , an) ai+1 an , 表的长度减少 a1 a2 ai-1 ai ai+1 an a1 a2 ai-1 三、顺序表操作的实现插入 T Delete( int i)； 算法分析: 三、顺序表操作的实现删除 T Delete( int i)； 算法实现: template T SeqList: Delete(int i) /i为第i位置 if(length=0) throw “溢出”； if(ilength) throw “位置异常”; x=datai-1 ; for(j=i; jlength; j+) /j为元素序号 dataj-1=dataj;/前移 length -; return x; O( n )算法的时间复杂度为： 总 结 线性表顺序存储结构特点：逻辑关系上相邻的 两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素O(1)；存储 空间使用紧凑 缺点：在插入，删除某一元素时，需要移动大 量元素O(n);预先分配空间需按最大空 间分配，利用不充分;表容量难以扩充 为克服这一缺点，我们引入另一种存储形式。
