第二章线性表2011.ppt

《第二章线性表2011.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例退出2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4线性表的应用举例2.1线性表的定义和基本操作2.1.1线性表的定义线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。举例La=（3

2、4，89，765，12，90，-34，22）数据元素类型为int。Ls=(Hello,World,China,Welcome)数据元素类型为string。Lb=(book1,book2,...,book100)数据元素类型为下列所示的结构类型：structbookinfo{intNo;//图书编号char*name;//图书名称char*auther;//作者名称...;}2.1.2线性表的基本操作1.初始化线性表LInitList(L)2.销毁线性表LDestoryList(L)3.清空线性表LClearList(L)4.求线性表L的长度ListLength(L)5

3、.判断线性表L是否为空IsEmpty(L)6.获取线性表L中的某个数据元素内容GetElem(L,i,e)7.检索值为e的数据元素LocateELem(L,e)8.返回线性表L中e的直接前驱元素PriorElem(L,e)9.返回线性表L中e的直接后继元素NextElem(L,e)10.在线性表L中插入一个数据元素ListInsert(L,i,e)删除线性表L中第i个数据元素ListDelete(L,i,e)设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下

4、面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。012345678k=9123456789第5人出局,i=4k=8123467895第1人出局,i=0k=7234678915第7人出局,i=4k=6234689715第4人出局,i=2k=5236894715第3人出局,i=1k=4268934715第6人出局,i=1k=3289634715第9人出局,i=2k=2289634715第2人出局,i=0829634715第8人出局,i=0逆置517436928最终出局顺序

5、2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：图2-1线性表顺序存储结构示意图其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出

6、任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。在C语言中，实现线性表的顺序存储结构的类型定义#defineLIST_MAX_LENGTH100//线性表的最大长度typedefstruct{EntryType*item;//指向存放线性表中数据元素的基地址intlength;//线性表的当前长度}SQ_LIST；2.2.2典型操作的算法实现1.初始化线性表LintInitList(SQ_LIST*L){L->item=(EntryType*)malloc(LIS

7、T_MAX_LENGTH*sizeof(EntryType));//分配空间if(L->item==NULL)returnERROR;//若分配空间不成功，返回ERRORL->length=0;//将当前线性表长度置0returnOK;//成功返回OK}2.销毁线性表LvoidDestroyList(SQ_LIST*L){if(L->item)free(L->item);//释放线性表占据的所有存储空间}3.清空线性表LvoidClearList(SQ_L