线性表中数据元素的个数被称为线性表的长度教学课件

第2章线性表本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例请单鼠标左键换页!退出2.1线性表的定义和基本操作2.2线性表的版序存值结构2.3线性表的链式存结构2.4线性表的应用举例请单鼠标左键换页!2.,1线性表的定义和基本操作21.1线性表的定义线性表是由n(n≥0)个类型相同的数据元素组成的有限序列。通常表示成下列形式L=(a,a2y…,al1,a,a1+1y…,an)其中:L为线性表名称,习惯用大写书写为组成该线性表的数据元素,习惯用小写书写;线性表中数据元素的个数被称为线性表的长度,当n=0时,线性表为空,又称为空线性表请单鼠标左键换页!举例La=(34,89,765,12,90,-34,22)数据元素类型为int。LS=(Hello","World","China","Welcome")数据元素类型为string。Lb=(bo0k1book2…,book10)0数据元素类型为下列所示的结构类型structbookinfolintNo图书编号charname图书名称char=auther∥作者名称请单鼠标左键换页!1.2线性表的基本操作初始化线性表LInitlist(L)销毁线性表LDestorylist(L)3.清空线性表LClearlist)求线性表L的长度Listlength①L)判断线性表L是否为空IsEmpty(L)6.获取线性表L中的某个数据元素内容GetElem(,i,e)7.检索值为e的数据元素LocateELem(L,e)8.返回线性表L中e的直接前驱元素Priorelem(L,e)9返回线性表L中e的直接后继元素ExteEm(,e)0.在线性表L中插入一个数据元素ListInsert(Le)11.删除线性表L中第个数据元素ListDelete(L,i,e)请单鼠标左键换页!2.2线性表的序存信结构221线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示请单鼠标左键换页!存储地址内存单元ad+Ld+2Ld+(i-1)Ld+(n-1)a图2-1线性表顺序存储结构示意图请单鼠标左键换页!其中,L为每个数据元素所占据的存储单元数目相邻两个数据元素的存储位置计算公式LOC(ai+1=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为:LOC(a+1=LOC(a1)+(i-1)"L顺序存储结构的特点(1)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系,即线性表的逻辑结构与存储结构(物理结构)一致;请单鼠标左键换页!(2)随机存取法在访问线性表时,可以利用上述给出的数学公式快速地计算出任何一个数据元素的存储地址。因此,我们可以粗略地认为,访问每个数据元素所花费的时间相等。使用这种存取方法的存储结构被称为随机存储结构。顺序存储结构的类型定义:#defineLISTMAXLENGTh100∥线性表的最大长度typedefstructiEntryTypesiten;∥指向存放线性表中数据元素的基地址intlength;∥线性表的当前长度ISQLIST请单鼠标左键换页!2.22典型操作的算法实现初始化线性表LintInitList(SQ_LISTNL)LL->item=(EntryType*)mallOcLIST_MAX_LENGTHsizeof(EntryType);∥分配空间if(L->item==NULL)r