《1.1 线性表.ppt》由会员分享，可在线阅读，更多相关《1.1 线性表.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性表线性结构的定义：线性结构的定义：若若结结构构是是非非空空有有限限集集,则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点,并并且且所所有有结结点点都都最最多多只只有有一一个个直直接接前前驱驱和一个直接后继和一个直接后继.可表示为可表示为:(a1,a2,an）简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是一对一一对一(1:1)的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特特点点 除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个个直直接接后继。后继。线性结构包括：线性结构包括：线性表
2、、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-线性表线性表1.线性表定义线性表是n个具有相同类型元素的有限序列,是最常用最简单的数据结构,长度可增长或缩短。它们之间的关系可以排成一个线性序列：（a1,a2,ai-1，ai,ai1，,an）n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前驱的直接前驱ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线性终点1.线性表定义线性结构特点特点：在数据元
3、素的非空有限集中存在唯一唯一的一个被称作“第一个第一个”的数据元素存在唯一唯一的一个被称作“最后一个最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个只有一个前驱前驱除最后一个外，集合中的每个数据元素均只有一只有一个后继个后继线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。（A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012002009524刘禹圻刘禹圻男男182002级通信级通信0201班班012002009613武武锐锐男男182002级通信级通信0202班班012002009710彭彭隽
4、隽男男172002级通信级通信0203班班012002009801郭郭芳芳女女182002级通信级通信0204班班012002009904张珍珍女18182002级通信级通信0205班班：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文
5、表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。1.线性表定义线性表作为一种数据结构类型，其抽象数据类型可以定义为：抽象数据类型是指一个数学模型以及定义在该模型上抽象数据类型是指一个数学模型以及定义在该模型上的一组操作；其定义仅取决于它的逻辑特性，而与其在计的一组操作；其定义仅取决于它的逻辑特性，而与其在计算机内部的表示和实现无关。算机内部的表示和实现无关。抽象数据类型的定义由一个值域和定义在该值域上的一抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。组操作组成。线性表的相关操作(1)针对线性表的抽象数据类型
6、List,使得一个线性表L属于类型List,则针对L其相关的操作有:(1)结构初始化构初始化操作操作:InitList(&L)操作操作结果：构造一个空的果：构造一个空的线性表性表L。(2)销毁结构构操作操作:DestroyList(&L)初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：果：销毁线性表性表L。(3)判空操作判空操作:ListEmpty(L)初始条件初始条件:线性表性表L已存在。已存在。操作操作结果果:若若L为空表空表,则返回返回TRUE,否否则返回返回FALSE.(4)求线性表长度求线性表长度:ListLength(L)初始条件：初始条件：线性表性表L已存在。已存在
7、。操作操作结果：返回果：返回L中元素个数。中元素个数。(5)查找前驱操作查找前驱操作:PriorElem(L,cur_e,&pre_e)初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：若果：若cur_e是是L中的数据元素中的数据元素,则用用pre_e返回它的返回它的前前驱,否否则操作失操作失败,pre_e无定无定义。(6)查找后继操作查找后继操作:NextElem(L,cur_e,&next_e)初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：若果：若cur_e是是L中的数据元素中的数据元素,则用用next_e返回它的返回它的后后继,否否则操作失操作失败,next_
8、e无定无定义.(7)取线性表元素值取线性表元素值:GetElem(L,i,&e)初始条件：初始条件：线性表性表L已存在，已存在，1iLengthList(L)。操作操作结果：用果：用e返回返回L中第中第i个元素的个元素的值。(8)定位操作定位操作:LocateElem(L,e,compare()初始条件：初始条件：线性表性表L已存在已存在,compare()是元素判定函数。是元素判定函数。操作操作结果：返回果：返回L中第中第1个与个与e满足关系足关系compare()的元素的位序。的元素的位序。若若这样的元素不存在，的元素不存在，则返回返回值为0。线性表的相关操作(3)(9)输出操作输出操作:
9、ListTraverse(L,visit()初始条件初始条件:线性表性表L已存在已存在,visit()为元素的元素的访问函数。函数。操作操作结果果:依次依次对L的每个元素的每个元素调用函数用函数visit(),一旦一旦visit()失失败,则操作失操作失败.(10)线性表置空操作线性表置空操作:ClearList(&L)初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：将果：将L重置重置为空表空表。(11)元素赋值操作元素赋值操作:PutElem(&L,i,&e)初始条件：初始条件：线性表性表L已存在，已存在，1iLengthList(L)。操作操作结果：果：L中第中第i个元素个元
10、素赋值同同e 的的值。线性表的相关操作(4)(12)插入操作插入操作:ListInsert(&L,i,e)初始条件：初始条件：线性表性表L已存在，已存在，1iLengthList(L)+1。操作操作结果：在果：在L的第的第i个元素之前插入新的元素个元素之前插入新的元素e,L的的长度增度增1.(13)删除操作删除操作:ListDelete(&L,i,&e)初始条件：初始条件：线性表性表L已存在且非空，已存在且非空，1iLengthList(L)。操作操作结果：果：删除除L的第的第i个元素个元素,并用并用e返回其返回其值,L的的长度减度减1。由于上述各操作的定义仅对由于上述各操作的定义仅对抽象抽象
11、的线性表而言的线性表而言,还还无法在程序设计中加以引用无法在程序设计中加以引用,但可以利用它进行算法的但可以利用它进行算法的研究研究,并由此可以看出以上对线性表类型的定义是否并由此可以看出以上对线性表类型的定义是否“完整完整”,即能否利用线性表的操作实现应用问题的算法即能否利用线性表的操作实现应用问题的算法设计。如果已经实现了线性表类型设计。如果已经实现了线性表类型List的的定义定义,则在应则在应用问题的求解中就可以利用用问题的求解中就可以利用List中定义的各种操作。中定义的各种操作。线性表的相关操作(5)例例3:已知集合已知集合A和和B,求两个集合的并集求两个集合的并集,使使AAB,且且
12、B不再单独存在不再单独存在.现现假设以线性表假设以线性表LA和和LB分别表示集合分别表示集合A和和B,即构造两个线性表即构造两个线性表LA和和LB,它们的数据元素分别为集合它们的数据元素分别为集合A和和B中的成员。中的成员。由此由此,上述集合求并的问题便可演绎为：要求对线性表作如下上述集合求并的问题便可演绎为：要求对线性表作如下操作：扩大线性表操作：扩大线性表LA,将存在于线性表将存在于线性表LB中而不存在于线性表中而不存在于线性表LA中的数据元素插入到线性表中的数据元素插入到线性表LA中去。中去。现现具体操作步骤为：具体操作步骤为：1从线性表从线性表LB中中取出取出一个数据元素；一个数据元素
13、；2依值在线性表依值在线性表LA中进行中进行查询查询；3若不存在，则将它若不存在，则将它插入插入到到LA中。中。重复上述三步直至重复上述三步直至LB为空表止为空表止.那么那么,其中的每一步能否利用上述线性表类型中定其中的每一步能否利用上述线性表类型中定义的义的基本操作基本操作来完成呢？来完成呢？线性表的相关操作(6)容易看出，上述的每一步恰好对应线性表的一个基本操容易看出，上述的每一步恰好对应线性表的一个基本操作：作：1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal();3.ListInsert(LA,n+1,e)。现现equal()为判定元素值是否相等
14、的函数。为判定元素值是否相等的函数。n表示线性表中当前所含元素个数，由于在集表示线性表中当前所含元素个数，由于在集合论中，元素之间是没有次序关系的，因此为操作合论中，元素之间是没有次序关系的，因此为操作方便，仅需将新的数据元素插入在线性表的表尾即方便，仅需将新的数据元素插入在线性表的表尾即可。这样得到的算法表示为：可。这样得到的算法表示为：线性表的相关操作(7)voidunion(List&LA,List&LB)/将所有在线性表将所有在线性表LB中但不在中但不在LA中的数据元素插入到中的数据元素插入到LA中中,/算法执行之后，线性表算法执行之后，线性表LB不再存在。不再存在。La_len=Li
15、stLength(LA);while(!ListEmpty(LB)ListDelete(LB,1,e);if(!LocateElem(LA,e,equal()ListInsert(LA,+La_len,e);/whileDestroyList(LB);/unionListInsert(La,+La_len,e)表示先将参数表示先将参数La_Len增增1然后然后将将e插入到插入到La中第中第La_len个元素之前。个元素之前。2.线性表的顺序存储表示顺序表顺序表是线性表的顺序存储表示的简称，它指的是“用一组用一组地址连续地址连续的存储单元的存储单元依次存放依次存放线性表中的线性表中的数据元素数据
16、元素”，即以“存储位置相邻存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系”，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址线性表的基地址。假设每个数据元素占据的存储量是一个常量C，则后继元素的存储地址和其前驱元素相隔一个常量,LOC(ai+1)=LOC(ai)+C所有数据元素的存储位置均可由第一个数据元素的存储位置得到:LOC(LOC(a ai i )=LOC()=LOC(a a1 1 )+C*)+C*（i-1i-1）设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每，每个数组元素用相邻的个数组元素用相邻的个字节存储。存储器按字个字节存储。存储
17、器按字节编址，设存储数组元素节编址，设存储数组元素 的第一个字节的的第一个字节的地址是地址是，则，则 的第一个字节的地址是多的第一个字节的地址是多少？少？但此题要注意下标起点略有不同：但此题要注意下标起点略有不同：LOC(M3)=98+5(3-0)=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a1)+C*（i-1）例例4顺序表的特点把线性表中数据元素依次存放到一组连续的存储单元中，每个数据元素对应一个存储单元。线性表中数据元素类型一致，占用相同大小的存储单元。便于随机存取数据，适用于频繁查找。做插入、删除时需移动大量元素。顺序存储结构是静态分配的。空间估计不明
18、时，按最大空间分配。用用C语言描述的语言描述的顺序表顺序表类型如下所示类型如下所示:顺序表的定义和操作顺序表的定义和操作(1)/存储结构存储结构constintMAXLISTSIZE=80;/预设的存储空间最大容量预设的存储空间最大容量typedefstructElemType*elem;/存储空间基址存储空间基址intlength;/当前长度当前长度intlistsize;/允许的最大存储容量允许的最大存储容量(以以sizeof(ElemType)为单位为单位)SqList;/俗称俗称顺序表顺序表在在这种确定的存储表示下这种确定的存储表示下,就可以得到定义中指出就可以得到定义中指出的各种操作
19、实现接口的各种操作实现接口:bool GetElem(SqList L,int pos,ElemType&e)/若若1posLengthList(L),则用则用e带回顺序表带回顺序表L中第中第pos个元素个元素的值且返回函数值为的值且返回函数值为TRUE，否则返回函数值为否则返回函数值为FALSE顺序表的定义和操作顺序表的定义和操作(2)bool ListInsert(SqList&L,int pos,ElemType e)/若存储空间未满且若存储空间未满且1posLengthList(L)+1,则在顺序表则在顺序表L的的第第pos个元素之前插入新的元素个元素之前插入新的元素e,L的长度增的长
20、度增1，且返回函数值为，且返回函数值为TRUE，否则不改变顺序表且返回函数值为否则不改变顺序表且返回函数值为FALSE。bool ListDelete(SqList&L,int pos,ElemType&e)/若若1posLengthList(L)，则删除顺序表则删除顺序表L的第的第pos个元素个元素e,L的长度增的长度增1，且返回函数值为，且返回函数值为TRUE，否则不改变顺序表且返否则不改变顺序表且返回函数值为回函数值为FALSE。象上面定义的函数可以在程序设计中引用。当然，象上面定义的函数可以在程序设计中引用。当然，在调用前还需要对元素类型在调用前还需要对元素类型 ElemType 和作
21、为参数的一和作为参数的一些函数象些函数象equal()等加以明确定义。等加以明确定义。例5已知一个“非纯集合”B，试构造一个集合A,使A中只包含B中所有值各不相同的数据元素。如果以线性表如果以线性表LB和和LA分别表示分别表示“集合集合”B 和和A，那么此问题求解的算法应该如何写呢？那么此问题求解的算法应该如何写呢？容易看出容易看出,应对线性表作与应对线性表作与例例3相同的操作相同的操作,具体的三具体的三步也都相同步也都相同,所所不同之处仅仅在于两点不同之处仅仅在于两点：一是例：一是例3的算的算法中法中LA是已知的是已知的,而在此例算法中的而在此例算法中的LA是是待新建待新建的；的；二是例二是
22、例3在求得并集之后在求得并集之后,原来的两个集合不再保留原来的两个集合不再保留,而而在此例中构建新的集合在此例中构建新的集合A的同时的同时,原来的集合原来的集合B不变不变.根据前面给出的各种操作函数定义根据前面给出的各种操作函数定义,可以给出具体的可以给出具体的算法实现函数算法实现函数,供在供在主函数主函数中调用中调用:例5void purge(SqList&La,SqList Lb)bool b;int Lb_len=Listlength(Lb);/求线性表求线性表 Lb 的长度的长度 InitList(La,Lb_len);/创建一个空的线性表创建一个空的线性表 Laint La_len=
23、0;for(i=1;i=Lb_len;i+)/依次处理依次处理 Lb 中每个元素中每个元素b=GetElem(Lb,i,e);/取取Lb中第中第i个数据元素赋给个数据元素赋给eif(!LocateElem(La,e,equal()+La_len;b=ListInsert(La,La_len,e);/当当La中不存在和中不存在和 e 值值 /相同的数据元素时，进行插入相同的数据元素时，进行插入 /for/purge La La 中元素个数不超过中元素个数不超过 Lb Lb 中的元素个数，故设中的元素个数，故设 La La 的最大空间和的最大空间和 Lb Lb 相同相同.线性表基本操作定义(1)一
24、、初始化操作一、初始化操作“初始化初始化”的实质是为它分配一个“足够应用足够应用”的元素存储空间,由用户根据它对线性表的使用要求定义一个最大存储容量maxsize,并约定当用户没有提出需求(maxsize=0)时,按予设的最大存储量 MAXLISTSIZE 进行分配：voidInitList(SqList&L,intmaxsize)/构造一个空的线性表构造一个空的线性表Lif(maxsize=0)maxsize=MAXLISTSIZE;L.elem=(ElemType*)malloc(maxsize*sizeof(ElemType);if(!L.elem)exit(1);/存储分配失败L.le
25、ngth=0;/顺序表的初始长度为0L.listsize=maxsize;/顺序表可以存储元素的最大容量/InitList二、元素定位操作二、元素定位操作在顺序表中“查询”是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个依次取出结构中的每个元素和给定值进行比较元素和给定值进行比较。intLocateElem(SqListL,ElemTypee,void(*compare)(ElemType,ElemType)/在顺序表在顺序表L中查找第中查找第1个值与个值与 e 满足判定条件满足判定条件compare()的元的元素素,若找到，则返回其在若找到，则返回其在 L 中的位
26、序，否则返回中的位序，否则返回0。i=1;/i的初值为第1元素的位序p=L.elem;/p的初值为第1元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;/依次进行判定if(i=L.length)returni;/找到满足判定条件的数据元素为第i个元素elsereturn0;/该线性表中不存在满足判定的数据元素/LocateElem三、插入元素操作三、插入元素操作首先分析,“插入元素”使线性表的逻辑结构发生什么变化？假设在线性表的第i个元素之前插入一个元素e,使得线性表(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,e,ai,ai+1,an
27、)即即:(1)改变了表中元素之间的关系,使改变为和.(2)表长增1由于顺序表是以存储位置相邻存储位置相邻表示元素之间的前元素之间的前驱和后继关系驱和后继关系，则必须移动元素移动元素来体现元素之间发元素之间发生的变化生的变化。三、插入元素操作三、插入元素操作boolListInsert(SqList&L,intpos,ElemTypee)/若存储空间不满且若存储空间不满且1posListlength(L)+1,则在顺序表则在顺序表L的的第第pos个元素之前插入新的元素个元素之前插入新的元素e且返回且返回TRUE,否则返回否则返回FALSEif(posL.length+1)return FALSE
28、;/插入位置不合法if(L.length=L.listsize)return FALSE;/当前存储空间已满，无法插入for(j=L.length-1;j=pos-1;-j)L.elemj+1=L.elemj;/插入位置及之后的元素右移L.elempos-1=e;/插入e+L.length;/表长增1return TRUE;/ListInsert四、删除元素操作四、删除元素操作boolListDelete(SqList&L,intpos,ElemType&e)/若若1posListlength(L),则以则以e带回从顺序表带回从顺序表L中删除的第中删除的第pos个元素且返回个元素且返回TRUE
29、，否则返回否则返回FALSEif(posL.length)return FALSE;/删除位置不合法for(j=pos;jL.length;+j)L.elemj-1=L.elemj;/被删除元素之后的元素左移-L.length;/表长减1return TRUE;/ListDelete(,)改变为(,e,)“删除元素”与插入元素一样,同样改变了线性表元素间结构,但是它使表长减一,同样要进行元素移动.线性表操作示例(1)例：试编写算法例：试编写算法“比较比较”两个顺序表的大小。两个顺序表的大小。算法的算法的基本思想基本思想为：若为：若aj=bj，则则 j 增增 1 1，之后继续比较后继，之后继续比
30、较后继元素；否则即可得出比较结果。显然，元素；否则即可得出比较结果。显然，j j 的初值应为的初值应为0 0，循环的条，循环的条件是件是j不超出其中任何一个表的范围。若在循环内不能得出比较结不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有三种可能出现的情况需要区分果，则循环结束时有三种可能出现的情况需要区分:解题分析：解题分析：(1)算法要求对两个顺序表进行算法要求对两个顺序表进行“比较比较”，是一种，是一种“引用型引用型”操作，因此在操作，因此在算法中不应该破坏已知表算法中不应该破坏已知表。(2)按比较的规定，只有在两个表的长度相等，且每个对应按比较的规定，只有在两个表
31、的长度相等，且每个对应元素都相同时才相等；否则两个顺序表的大小主要取决于两表中元素都相同时才相等；否则两个顺序表的大小主要取决于两表中除去最大公共前缀后的第一个元素。除去最大公共前缀后的第一个元素。因此，比较两表的大小不应该先比较它们的长度，而应该因此，比较两表的大小不应该先比较它们的长度，而应该设一设一个下标变量个下标变量 j 同时控制两个表同时控制两个表，即对两表中，即对两表中“位序相同位序相同”的元的元素进行比较。素进行比较。线性表操作示例(2)intcompare(SqListA,SqListB)/若若 AB，则则 返回返回 1j=0;while(jA.length&jB.length
32、)if(A.elemjB.elemj)return(1);elsej+;if(A.length=B.length)return(0);else if(A.lengthnext;j=1;/变量初始化，p指向第一个结点while(p&jnext;+j;/whileif(!p|jpos)return FALSE;/链表中不存在第pos个结点e=p-data;/取到第pos个元素return TRUE;/GetElem单链表的基本操作定义单链表的基本操作定义(3)二、插入元素操作二、插入元素操作前面知道在线性表中前面知道在线性表中“插入插入”一个元素时一个元素时,使元使元素之间的关系素之间的关系改变为
33、改变为和和。当用指针指示后继元素时当用指针指示后继元素时,实现这种关系的改变就很实现这种关系的改变就很容易了容易了,只要修改相应指针即可。因为新的元素插入只要修改相应指针即可。因为新的元素插入在线性表的第在线性表的第i个元素之前，使得个元素之前，使得ai不再是不再是ai-1的后继的后继,而是新的元素而是新的元素e的后继的后继,因此需要修改元素因此需要修改元素e和元素和元素ai-1所在结点的指针。所在结点的指针。由此，算法的由此，算法的基本思想基本思想就是就是:首先找到第首先找到第i-1个结个结点，然后修改相应指针。点，然后修改相应指针。具体算法表示为：具体算法表示为：bool ListInse
34、rt(SLink&L,int pos,ElemType e)/若若1posLengthList(L)+1,则在指针则在指针L指向头结点的单链指向头结点的单链/表的第表的第 pos 个元素之前插入新的元素个元素之前插入新的元素 e,且返回函数值为且返回函数值为 TRUE,/否则不进行插入且返回函数值为否则不进行插入且返回函数值为 FALSEp=L;j=0;while(p&jnext;+j;/whileif(!p|jpos-1)return FALSE;/参数不合法，参数不合法，pos 小于小于1或者大于表长或者大于表长+1s=(Slink)malloc(sizeof(LNode);if(!s)e
35、xit(1);/存储空间分配失败存储空间分配失败s-data=e;/创建新元素的结点创建新元素的结点s-next=p-next;p-next=s;/修改指针修改指针return TRUE;/ListInsert 单链表的基本操作定义单链表的基本操作定义(5)三、删除元素操作三、删除元素操作和插入类似，由于删除元素和插入类似，由于删除元素ai改变了元素之间的改变了元素之间的关系，使关系，使ai+1不再是不再是ai的的后继，而是后继，而是ai-1的后继，因此的后继，因此需要修改需要修改ai-1元素所在结点的指针。元素所在结点的指针。因此在单链表中删除元素操作的算法基本思想和因此在单链表中删除元素操
36、作的算法基本思想和插入相同，也是：插入相同，也是：首先找到第首先找到第i-1个结点，然后修改个结点，然后修改相应指针。相应指针。具体算法表示为：具体算法表示为：bool ListDelete(SLink&L,int i,ElemType&e)/若若1posLengthList(L)，则删除指针则删除指针L指向头结点的指向头结点的/单链表中第单链表中第i 个元素并以个元素并以 e 带回其值，返回函数值为带回其值，返回函数值为 /TRUE，否则不进行删除操作且返回函数值为否则不进行删除操作且返回函数值为 FALSEp=L;j=0;while(p-next&j next;+j;if(!(p-next
37、)|j i-1)return FALSE;/删除位置不合理删除位置不合理q=p-next;p-next=q-next;/修改指针修改指针e=q-data;delete(q);/释放结点空间释放结点空间 return TRUE;/ListDelete_L 单链表操作示例单链表操作示例(1)例例:逆序创建链表逆序创建链表假设线性表(a1,a2,an)的数据元素存储在一维数组An中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为空的链表中。解题分析解题分析:由于链表是一种动态存储管理的结构,链表中每个结点占用的存储空间不需预先分配划定,而是在运行时刻由系统应需求即时生成,因此,建立链
38、表的过程是一个动态生成的过程。即从“空表空表”起,依次建立结点,并逐个插入链表。所谓“逆序”创建链表指的是，与线性表的逻辑顺序相“逆”的次序输入元素。可以看线性表(a,b,c,d,e)的逆序创建的过程:单链表操作示例单链表操作示例(2)voidCreateList_L(SLink&L,intn,ElemTypeA)/已知数组已知数组 A 中存有线性表的中存有线性表的 n 个数据元素，个数据元素，/逆序建立带头结点的单链表。逆序建立带头结点的单链表。L=(Slink)malloc(sizeof(LNode);if(!L)exit(1);/存储空间分配失败L-next=NULL;/先建立一个带头结
39、点的空的单链表for(i=n;i0;-i)p=(Slink)malloc(sizeof(LNode);if(!p)exit(1);/存储空间分配失败p-data=Ai-1;/赋元素值p-next=L-next;L-next=p;/插入在头结点之后/for/CreateList_L单链表操作示例单链表操作示例(3)例例:编写算法删除单链表中编写算法删除单链表中多余多余的数据元素，即使操作的数据元素，即使操作之后的单链表中所有元素的值都不相同。之后的单链表中所有元素的值都不相同。解题分析解题分析:可以和顺序表采用同样算法，即设想新建一个链表，然后顺序考察原链表中每一个结点的数据元素，在“新表”中进
40、行查找，如果有相同的则舍弃之，否则就插入到新表中。voidpurge_L(SLink&L)/删除单链表删除单链表L中的冗余元素，即使操作之后的单链表中只保中的冗余元素，即使操作之后的单链表中只保/留操作之前表中所有值都不相同的元素留操作之前表中所有值都不相同的元素p=L-next;L-next=NULL;/设新表为空表设新表为空表while(p)/顺序考察原表中每个元素 succ=p-next;/记下结点*p的后继q=L-next;/q指向新表的第一个结点while(q&p-data!=q-data)q=q-next;/在新表中查询是否存在和p-data相同的元素if(!q)/将结点*p插入到
41、新的表中p-next=L-next;L-next=p;else deletep;/释放结点*pp=succ;/for/purge_L单链表特点分析：链式存储结构的优势优势在于：(1)能有效利用存储空间；(2)用“指针”指示元素之间的后继关系,便于进行插入插入、删除删除等操作；链式存储结构的劣势劣势在于：不能随机存取数据元素。同时,它还丢失了一些顺序表有的长处,如线性表的“表长表长”和数据元素在线性表中的“位序位序”,在上述的单链表中都看不见了。又如,不便于在表尾插入元素,需遍历整个表才能找到插入的位置。v在实际使用链表时需重新考虑链表结构的定义并重新设计操作界面.3.2循环链表循环链表循环链表
42、循环链表(Circular Linked List)是线性表的另一种形式的链式存储表示。它的特点特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个自成循环的头结点表示。头结点头指针空循环链表头结点头指针a1a2an循环链表的操作和单链表基本一致,差别仅在于差别仅在于,判别链表中最后一个结点的条件不再是后继是否为空后继是否为空，而是后继是否为头结点后继是否为头结点。3.3双向链表双向链表(1)双向链表双向链表(Double Linked List)的特点是其结点结构中含有两个指针域，其一指向数据元素的直接后继，另
43、一指向数据元素的直接前驱，用C语言描述如下：typedef structDuLNodeElemTypedata;structDuLNode*prior;structDuLNode*next;DuLNode,*DuLink;特点特点:在双向链表中不仅能直接找到结点的前驱，也能即刻找到结点的后继。假设指针p指向双向链表中某个结点，则p-prior-next=p p-next-prior=p3.3双向链表双向链表(2)双向链表双向链表也是由指向头结点的头指针头指针唯一确定，若将头尾结点链接起来则构成双向循环链表双向循环链表。空的双向循环链表则由只含一个自成双环的头结点表示。3.3双向链表操作双向链表
44、操作双向链表的操作基本上和单向链表相同，例如，查找结点也是要从头指针指示的头结点从头指针指示的头结点开始，但插入和删除时必须同时修改两同时修改两个方向上的指针个方向上的指针。void ListInsert_DuL(DuLink&L,DuLNode*p,DuLNode*s)/在带头结点的双向循环链表在带头结点的双向循环链表 L 中结点中结点*p 之后插入结点之后插入结点*ss-next=p-next;p-next=s;s-next-prior=s;s-prior=p;/ListInsert_DuLvoid ListDelete_DuL(DuLink&L,DuNode*p,ElemType&e)/
45、删除带头结点的双向循环链表删除带头结点的双向循环链表L中结点中结点*p 的后继，的后继，/并以并以 e 返回它的数据元素返回它的数据元素q=p-next;e=q-data;p-next=q-next;p-next-prior=p;delete q;/ListDelete_DuL3.4有序表(1)若线性表中的数据元素相互之间可以比较,并且数据元素在线性表中依值非递减或非递增有序排列,即ai ai-1或aiai-1(i=2,3,n),则称该线性表为有序表有序表(OrderedList)。例例:已知两个链表(头指针分别为La和Lb)其数据元素均自小至大有序,编写算法将这两个链表归并为一个链表。解题分
46、析：解题分析：通常容易想到的这个题的做法是:将Lb表中的各个结点插入到La表中的相应位置中去。即按照有序关系首先查找插入位置,然后修改相应指针。另一种做法是,试设想新建一个空的链表,然后将已知两个链表中的结点依从小到大的次序逐个插入到这个新的链表中。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/已知单链线性表已知单链线性表 La 和和 Lb 的元素按值非递减排列。本算法的元素按值非递减排列。本算法/归并归并 La 和和 Lb 得到新的单链线性表得到新的单链线性表 Lc，Lc 的元素也按的元素也按/值非递减排列。操作之后值非递减排列。操
47、作之后 La 和和 Lb 消失消失pa=La-next;pb=Lb-next;Lc=rc=newLNode;/建空表，Lc为头指针while(pa&pb)if(pa-datadata)/将*pa插入Lc表，指针pa后移rc-next=pa;rc=pa;pa=pa-next;/ifelse/将*pb插入Lc表，指针pb后移rc-next=pb;rc=pb;pb=pb-next;/else/whilerc-next=pa?pa:pb;/插入剩余段delete(La);delete(Lb);/释放La和Lb的头结点/MergeList_L有序表类型的基本操作和线性表类型中定义的基本操作基有序表类型的基本操作和线性表类型中定义的基本操作基本相同本相同,但在但在LocateElem函数中参数函数中参数compare的类型不同的类型不同,应注意元素相互比较的结果将产生应注意元素相互比较的结果将产生三种结果三种结果(“小于小于”、“等等于于”和和“大于大于”）;同时在进行同时在进行“插入插入”操作时必须保持表的操作时必须保持表的有序性有序性,也就是说，在有序表中进行插入时首先要也就是说，在有序表中进行插入时首先要查找插入位查找插入位置置。