第2章 线性表.ppt

1、、第二章线性表、线性表的定义线性表的顺序存储及实现线性表的链接存储及实现顺序表与单链接表的比较线性表的其他存储及实现，本章的基本内容为，学生成绩登记表、2.1线性表的定义、姓氏、英语、数据结构、高数、学号、丁一86，86，0103，孙红，69，69 87，74，66，0105，员工工资登记表，2.1线性表的逻辑结构、姓氏、姓氏、线性表：简称表是具有n(n0 )个相同类型数据要素的有限序列。 线性表长度：线性表中数据元素的数量。 空表：长度为零的线性表，标记为L=()。 非空标记是L(a1，a2，ai-1，ai，an )，2.1线性表的逻辑结构和线性表的定义。 在此，ai(1in )被称为数据要

2、素。 下角I表示该元素在线性表中的位置或编号。2.1线性表的逻辑结构、线性表的图表表示、线性表(a1、a2、ai-1、ai、an )的图表表示、2.1线性表的逻辑结构、线性表的特性、1 .有限、2 .同一性：线性表的数据元素类型相同。 3 .顺序性：线性表中相邻数据元素ai-1和ai之间的顺序偶关系(ai-1，ai )，即ai-1是ai的前体，而ai是ai-1的后继。 a1没有前体，an没有后继者，其他各元素只有一个前体和一个后继者。线性表的抽象数据类型定义、ADT List Data线性表的数据元素具有相同的类型，相邻元素具有前驱和后继的关系Operation InitList前置条件：表没

3、有输入：没有功能：表的初始化输出：没有后置条件：制作空表， 2.1线性表的逻辑结构DestroyList前置条件：表现有输入：无功能：表输出放弃：无后置条件：表占有的记忆空间Length前置条件释放：表现有输入：无功能：求表的长度输出：表中数据要素的个数后置条件：表不变， 2.1线性表的逻辑结构Get前置条件：表现有输入：要素的序号I功能：取表中序号I的数据要素输出：如果I有效则返回序号I的要素值，否则抛出异常后置条件：表不变Locate前置条件：表现有输入：数据要素x功能：在线性表中查找值x的要素输出，除此以外的情况下为0 表不变。 2.1线性表的逻辑结构、线性表的抽象数据类型定义、Inse

4、rt前置条件：表中有输入。 插入I。 等待插入x功能：在表的第I个位置插入新元素x输出：插入失败时抛出异常后置条件：插入成功时在表中添加新元素Delete前置条件：在表中有输入：删除位置I功能：删除表的第I个元素输出：删除成功时返回被删除的元素。 否则，抛出异常后置条件的2.1线性表的逻辑结构，线性表的抽象数据类型定义，Empty前置条件：表现存在输入：判断表是否为空输出：如果是空表则返回1，否则返回0后置条件：表不变ADT，再说明： (1)线性表的基本操作复杂的操作可以通过基本操作的组合来实现(3)根据应用程序的不同，操作界面也会不同。、2.1线性列表的逻辑结构、线性列表的抽象数据类型定义、

5、2.2线性列表的顺序存储结构和实现、顺序列表的顺序存储结构，例如(34、23、67、43 )、34、23、67、43、2.2线性表的顺序存储结构和实现、顺序表的顺序存储结构，例如(34、23、43 ) 如何获得任何元素的存储地址？ 0 i-2 i-1 n-1 Max-1，a1，ai-1，ai，an，空闲，长度，2.2线性表的顺序记忆结构以及ai，an，空闲，长度，Loc(ai)=Loc(a1) (i -1)l，随机存取： O(1) 、存储结构和访问结构，“序列表是随机访问的存储结构”意味着在如序列表的存储结构上执行的查找操作的时间性能为O(1)。 声明序列表类，const int MaxSize=100； 模板类class seq list公用： seq list ()； /构造函数列表(t a，int n )； SeqList ()； /析构函数int Length ()； 获得(进入)； 不定位(tx )； 语音插入(int I，T x )； 删除(入口)； 隐私3360 t数据最大化； 英寸长度； 2.2线性表的顺序存储器结构和实现、操作接口： SeqList ()、算法描述： seq list :3360 seq list () length=0；2.2线性表的顺序存储结构和实现，