资源描述：
《数据结构 教学课件 作者 叶乃文 郑晓红 第二章.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=（34，89，
2、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.判断线性表L是否为
3、空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)11.删除线性表L中第i个数据元素ListDelete(L,i,e)2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：图2-1线性表顺序存储结构示意图其中，L为每个数据元
4、素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。在C语言中，实现线性表的顺序存储结构的类型
5、定义#defineLIST_MAX_LENGTH100//线性表的最大长度typedefstruct{EntryType*item;//指向存放线性表中数据元素的基地址intlength;//线性表的当前长度}SQ_LIST；2.2.2典型操作的算法实现1.初始化线性表LintInitList(SQ_LIST*L){L->item=(EntryType*)malloc(LIST_MAX_LENGTH*sizeof(EntryType));//分配空间if(L->item==NULL)returnERROR;//若分配空间不成功，返回ERRORL->length=0;//将当前线性表长度置0re
6、turnOK;//成功返回OK}2.销毁线性表LvoidDestroyList(SQ_LIST*L){if(L->item)free(L->item);//释放线性表占据的所有存储空间}3.清空线性表LvoidClearList(SQ_LIST*L){L->length=0;//将线性表的长度置为0}4.求线性表L的长度intGetLength(SQ_LISTL){return(L.length);}5.判断线性表L是否为空intIsEmpty(SQ_LISTL){if(L.length==0)returnTRUE;elsereturnFALSE;}6.获取线性表L中的某个数据元素的内容int
7、GetElem(SQ_LISTL,inti,EntryType*e){if(i<1
8、
9、i>L.length)returnERROR;//判断i值是否合理，若不合理，返回ERROR*e=L.item[i-1];//数组中第i-1的单元存储着线性表中第i个数据元素的内容returnOK;}7.在线性表L中检索值为e的数据元素intLocateELem(SQ_LISTL,EntryTypee){for(
