资源描述：
《数据结构 第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)1第2章线性表2.1线性表的基本概念2.2线性表的顺序存储结构及其算法2.3线性表的链式存储结构及其算法2.4算法应用举例22.1线性表的基本概念１、线性表它是一种最简单的线
2、性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由n（n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。3（a0,a1,…ai-1，ai,ai＋1，…,an-1）线性表的逻辑结构：n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点4（A,B,C,D,……,Z）学号姓名性别成绩年龄001张东女7023002赵玉凤女8020003王泽男9019004薛荃男8121005王春男8822：：：：：例2分析学生档案表是什么结构。分析：数据元素都是同类型（记录），元素
3、间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。5２、线性表抽象数据类型它包括两个方面：数据集合：｛a0,a1,…,an-1｝ai的数据类型为DataType操作集合：(1)InitList(List)初始化线性表,建一空线性表List(2)ListLength(L)求当前数据元素个数(3)GetElement(List,i)取线性表中第i个元素（1，n）(4)ListInsert(L,i,x)插入数据元素(5)ListDelete(L,i,x)删除数据元素(
4、6)ListGet(L,i,x)取数据元素等63、线性表的存储结构(1)顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点：(任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素，物理上也相邻。(2)链式存储结构:它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的。72.2线性表的顺序存储结构及其算法一、顺序表的存储结构二、顺序表的实现三、顺序表的运算效率分析
5、8一、顺序表的存储结构表示1、顺序表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]9(1)逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a0的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)
6、+LLOC(ai)=LOC(a0)+L*i对上述公式的解释如图所示2、线性表顺序存储特点：10a0a1……aiai+1……an-1地址内容元素在表中的位序0i1n-1空闲区i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai)=LOC(a0)+L*i3、线性表的顺序存储结构示意图114、用C语言描述typedefstruct{DateTypelist[MaxSize];intsize;}SeqList;/*MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足
7、size≤MaxSize，SeqList是该结构体的名字。*/12设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？113LOC(M[3])=98+5×3=113解：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例113charV[30];voidbuild()/*字母线性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)V[i]=V[i-1]+1;}核心语句：方法1V[i]=
