资源描述：
《第2章+线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章线性表2.1线性表的定义2.1.1线性表的逻辑结构线性表是有限元素（e0,e1,...,ei,...,en-1）的有序序列的集合。其中n是有穷自然数，表中的每个元素ei具有相同的特性，表中元素占用空间大小相同,记为：size，n是表的长度。当n=0时，表为空；当n>0时，e0是第一个元素，en-1是最后一个元素。“有序”是指线性元素间的相互位置关系。ei-1是ei的直接前驱元素，而元素ei一定在元素ei+1之前，称ei+1是ei的直接后继元素。而且，每个元素只有一个直接前驱元素（除第一个元素），也仅有一个直接后继元素（除最后一个元素）。2.1线性表的定义学生信息学号姓名性别年龄
2、籍贯2003050712肖象男18河北2003050713李明女17湖北2003050714刘辉男18宁夏··········2.1线性表的定义2.1.2线性表的抽象数据类型ADT2.1.1线性表的抽象数据类型ADTLinearList｛Dset：有限元素（e0,e1,...,ei,...,en-1）的有序序列的集合。Rset：ei-1是ei的直接前驱元素，ei一定在元素ei+1之前，ei+1是ei的直接后继元素。而且，每个元素只有一个直接前驱元素，也仅有一个直接后继元素。OPSet：Creat()构造空线性表Output()将线性表中的数据元素进行输出GetElem(k,x)在线性
3、表中取第k个元素到x中Search(x)在线性表中查找元素xInsert(k,x)在线性表中第k个数据元素之后中插入元素xDelete(k)在线性表中删除第k个数据元素PreElem(k,x)在线性表中求第k个元素的前驱，存入x中PreElem(k,x)在线性表中求第k个元素的后继，存入x中IsEmpty()判断线性表中有无元素｝2.1线性表的定义２.２线性表的顺序存储及操作2.2.1线性表顺序存储1.线性表顺序存储概念线性表顺序存储方式，是将线性表中的数据元素连续顺序地存放于存储器中相邻的单元。线性表占用的第一个存储单元的地址，就是线性表的首地址，也是线性表中第一个数据元素（e0）
4、的首地址。“首地址”有两种理解：一是相对于线性表本身，是线性表的始点，即“0号地址”，这就是通常所说的“相对地址”；二是相对于计算机的物理存储空间，线性表的始点相对于计算机物理存储空间则是一个“物理地址”，一般记为：location(e0)，通常称为“绝对地址”或“基地址”。2.2线性表的顺序存储及操作线性表中每个数据元素占用size字节空间，length（length=n）表示线性表中元素的个数,MaxSize表示线性表可以存储元素的最大空间。*element→Length=nMaxSizee001…i…n-1…MaxSizee1eien-1图线性表顺序存储元素ei的地址则可以立即
5、由下面公式求出。location(ei)=location(e0)+i×size请注意：这个公式是元素序号由0到n-1安排，若元素序号是由j开始安排，则上面公式应改为：location(ei)=location(ej)+(i-j)×size2.2线性表的顺序存储及操作2.线性表顺序存储结构定义线性表结构：typedefstruct{EType*element;intlength;intMaxSize;}LinearList；LinearListL，L1，L2；2.2线性表的顺序存储及操作学生信息的情况数据元素结构类型（EType）及线性表typedefstruct{unsignedn
6、umber[10];charname[8];charsex[2];intage;charplace[20];}student;typedefstruct{student*element;intlength;intMaxSize;}LinearList；LinearListstud1,stud2;2.2线性表的顺序存储及操作2.2.2线性表顺序存储结构下的操作1.构造空线性表L空线性表是指表中没有一个数据元素，但数据元素的空间和线性表结构存在构造空线性表L算法（Creat）viodCreat(LinearList&L,int&MaxListSize){//构造一个最大容量为MaxLis
7、tSize的线性表LL.MaxSize=MaxListSize;L.element=newEType[L.MaxSize];L.length=0;}算法的时间复杂性是O(1)。2.2线性表的顺序存储及操作2.2线性表的顺序存储及操作*element→Length=0MaxSize01…i…n-1…MaxSize图线性表顺序存储空表2.输出线性表L中的所有数据元素输出线性表L中所有数据元素（Output）viodOutput(LinearList&L){//
