《线性表顺序表》PPT课件

《《线性表顺序表》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表线性表的逻辑结构线性表的顺序存储及实现线性表的链接存储及实现顺序表和单链表的比较线性表的其他存储及实现本章的基本内容是：学生成绩登记表2.1线性表的逻辑结构姓名英语数据结构高数学号丁一9678870101李二8790780102张三6786860103孙红6981960104王冬8774660105每行是一个数据元素数据元素之间的关系是1:1的线性关系职工工资登记表2.1线性表的逻辑结构姓名岗位津贴基本工资奖金职工号丁一6002782000101李二3001901000102张三3001861000103孙红5002182000104王冬30019010

2、00105每行是一个数据元素数据元素之间的关系是1:1的线性关系线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有序（前后次序）序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)2.1线性表的逻辑结构线性表的定义其中，ai（1≤i≤n）称为数据元素；下角标i表示该元素在线性表中的位置或序号。a1a3a4ana22.1线性表的逻辑结构线性表的图形表示线性表（a1,a2,…,ai-1,ai,…,an)的图形表示如下：a1a3a4ana22.1线性表的逻辑结构线性表的特

3、性1.有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系，即ai-1是ai的直接前驱，ai是ai-1的直接后继；a1无前驱，an无后继，其它每个元素有且仅有一个直接前驱和一个直接后继。线性表的抽象数据类型定义ADTList{Data线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系OperationInitList前置条件：表不存在输入：无功能：表的初始化输出：无后置条件：建一个空表2.1线性表的逻辑结构DestroyList前置条件：表已存在

4、输入：无功能：销毁表输出：无后置条件：释放表所占用的存储空间Length前置条件：表已存在输入：无功能：求表的长度输出：表中数据元素的个数后置条件：表不变2.1线性表的逻辑结构线性表的抽象数据类型定义（续）Get前置条件：表已存在输入：元素的序号i功能：在表中取序号为i的数据元素输出：若i合法，返回序号为i的元素值，否则抛出异常后置条件：表不变Locate前置条件：表已存在输入：数据元素x功能：在线性表中查找值等于x的元素输出：若查找成功，返回x在表中的序号，否则返回0后置条件：表不变2.1线性表的逻辑结构线性表的抽象数据类型定义Insert前置条件：表已存在输入：

5、插入i；待插x功能：在表的第i个位置处插入一个新元素x输出：若插入不成功，抛出异常后置条件：若插入成功，表中增加一个新元素Delete前置条件：表已存在输入：删除位置i功能：删除表中的第i个元素输出：若删除成功，返回被删元素，否则抛出异常后置条件：若删除成功，表中减少一个元素2.1线性表的逻辑结构线性表的抽象数据类型定义Empty前置条件：表已存在输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0后置条件：表不变}ADTList进一步说明:（1）线性表的基本操作根据实际应用而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口

6、可能不同。2.1线性表的逻辑结构线性表的抽象数据类型定义2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储要点用一段地址连续的存储单元依次存储线性表中的数据元素2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储空间10用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度42.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）3423674310如何实现顺序表的内存分配？顺序表一维数组和两个整型变

7、量4如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)Loc(ai)表示数据元素ai的地址0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度Loc(ai)=Loc(a1)+(i-1)×c随机存取：在O(1)时间内存取数据元素2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)数据元素ai