资源描述：
《九江学院《数据结构》第02章 线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4顺序表与链表的比较线性表(LinearList)：由n(n≧)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)。记作：(a1，a2，…an)这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。2.1线性表的类型定义例1、26个英文字母组成的字母表（A，B，C,…,Z）例2、某校从19
2、78年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）2.1线性表的类型定义例3、学生健康情况登记表如下：2.1线性表的类型定义姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）2.1线性表的类型定义从以上例子可看出线性表的逻辑特征是：在非空的线性表中，有且仅有一个开始结点a1，它没有直接
3、前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。线性表的特点同一性：线性表中所有元素的性质相同有序性：除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继有穷性：数据元素在表中的位置只取决于它自身
4、的序号，序号不可能无穷，故元素个数不可能无穷2.1线性表的类型定义抽象数据类型（ADT）的表示ADT{数据对象：<数据对象的定义>结构关系：<结构关系的定义>基本操作：<基本操作的定义>}ADT//<操作名称>（参数表）操作前提：<操作前提描述>操作结果：<操作结果描述>2.1线性表的类型定义线性表的抽象数据类型定义ADTLinearList{数据元素:D={ai
5、ai∈D0,i=1,2,…,n,n≥0,D0为某一数据对象}结构关系:S={
6、ai,ai+1
7、∈D0,I=1,2,…,n-1}基本操作:(1)InitList(L)//初始化操作前提:L为未初始化线性表操作结果:将L初始化为空表(2)DestroyList(L)//删除表操作前提:线性表L已存在操作结果:将L销毁(3)ClearList(L)//内容清空操作前提:线性表L已存在操作结果:将表L置为空表(4)EmptyList(L)//判空操作前提:线性表L已存在操作结果:如果L为空表则返回真,否则返回假(5)ListLength(L)//求长度操作前提:线性表L已存在操作结果:如果L为空表
8、则返回0,否则返回表中的元素个数(6)Locate(L,e)//检索操作前提:表L已存在,e为合法元素值操作结果:如果L中存在元素e,则将“当前指针”指向e所在位置并返回真,否则返回假(7)GetData(L,i)//取元素操作前提:表L已存在,且i值合法,即1≤i≤ListLength(L)操作结果:返回线性表L中第i个元素的值线性表的抽象数据类型定义(8)InsList(L,i,e)//插入(前插)操作前提:表L已存在,e为合法元素值且1≤i≤ListLength(L)+1操作结果:将表L中第
9、i个位置插入新的数据元素e,L的长度加1(9)DelList(L,i,&e)//删除操作前提:表L已存在且非空,1≤i≤ListLength(L)操作结果:删除表L的第i个数据元素,并用e返回其值,L的长度减1}ADTLinearList线性表的抽象数据类型定义2.2.1顺序表存储结构把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素
10、的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l2.2线性表的顺序表示和实现元素an……..元素ai……..元素a2元素a1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址内存状态Loc(元素i)=b+（i-1)*m首地址起始地址基地址每个元素所占用的存储单元个数顺序存储结构示意图(顺序表)：2.2.1顺序表
