第二章 线性表.ppt

文档介绍：第二章线性表
[内容提要]
1、线性表的定义、逻辑结构特点及基本运算
2、线性表的顺序存储结构及基本运算
3、线性表的链式存储结构及基本运算
4、数组的逻辑结构定义及其存储方式
5、线性表的应用示例
1
线性表:n(n≥0)个具有相同特性的数据元素的有限序列。
其中:n表示线性表的长度,即数据元素的个数。n=0时表为空表。n>0时表通常记为:
线性表的定义
2
线性表的特点
当1<i<n时
ai的直接前驱是ai-1 , a1无直接前驱
ai的直接后继是ai+1 ,an无直接后继
元素同构,且不能出现缺项
3
线性表的特点
在线性表中的元素之间存在一对一的关系。所以,线性表的逻辑结构是线性结构。
4
线性表的元素的含义
每个数据元素的具体含义,在不同线性表中各不相同,它可以是一个数、或一个符号,也可以是一个记录,甚至是其它更复杂的信息。
5
线性表的元素的含义(续)
如右图所示的学生成绩表也是一个线性表,其中数据元素是每一个学生所对应的一行信息,即包括学号、姓名、成绩共三个数据项。
数据元素
6
线性表上常用的的运算
⑴初始化线性表
⑵判空线性表的长度,
⑷读取表是否为空
⑶求线性表中第i个元素
⑸查找满足给定条件的数据元素
⑹在线性表的第i个位置之前插入一个新的数据元素
7
⑺删除线性表中的第i个数据元素
⑻表置空
⑼查找表中第i个元素的前驱
⑽查找表中第i个元素的后继
⑾按一个或多个数据项值的递增或递减次序重新排列线性表中的数据元素
线性表上常用的运算(续)
8
利用以上的基本运算可以实现线性表的其他运算。如将两个线性表合并成一个线性表或将一个线性表拆分成多个线性表等运算,在实际应用中,可根据不同的要求选择适当的基本运算解决具体问题。
线性表上常用的运算(续)
9
在内存中开辟一片连续的存储空间,用一组连续的存储单元依次存放线性表的数据元素,这种存储方式叫做线性表的顺序存储结构,简称顺序表。
线性表的顺序存储结构
10