《数据结构与算法设计幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法设计幻灯片.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法设计课件第1页，共99页，编辑于2022年，星期六线性表是一种最简单的线性结构。什么是线性结构？简单地说，线性结构线性结构是一个数是一个数据元素的有序（次序）集合。它有四个基本特征：据元素的有序（次序）集合。它有四个基本特征：1集合中必存在唯一的一个集合中必存在唯一的一个第一元素第一元素；2集合中必存在唯一的一个集合中必存在唯一的一个最后元素最后元素；3除最后元素之外，其它数据元素均有唯一的除最后元素之外，其它数据元素均有唯一的后继后继；4除第一元素之外，其它数据元素均有唯一的除第一元素之外，其它数据元素均有唯一的前驱前驱。第2页，共99页，编辑于2022年，星期六2.1.1 抽
2、象数据类型线性表的定义抽象数据类型线性表的定义通常可以下列“n个数据元素的序列”表示线性表线性表(Linear_List)(a1,a2,.,ai,.,an)序列中数据元素的个数n定义为线性表的表长；n=0时的线性表被称为空表。称i为ai在线性表中的位序。其抽象数据类型的定义如下：ADT List 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|,D,i=2,.,n第3页，共99页，编辑于2022年，星期六基本操作：基本操作：结构初始化结构初始化InitList(&L)操作结果：构造一个空的线性表L。销毁结构销毁结构DestroyList(&L)
3、初始条件：线性表L已存在。操作结果：销毁线性表L。第4页，共99页，编辑于2022年，星期六引用型操作引用型操作ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。第5页，共99页，编辑于2022年，星期六NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结
4、果：若cur_e是L中的数据元素，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElem(L,i,&e)初始条件：线性表L已存在，1iLengthList(L)。操作结果：用e返回L中第i个元素的值。第6页，共99页，编辑于2022年，星期六LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit()初始条件：线性表L已存在，visit()为元素的访问函数。操作结果：依次对L的每
5、个元素调用函数visit()。一旦visit()失败，则操作失败。第7页，共99页，编辑于2022年，星期六加工型操作加工型操作ClearList(&L)初始条件：线性表初始条件：线性表 L 已存在。已存在。操作结果：将操作结果：将 L 重置为空表。重置为空表。PutElem(&L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iLengthList(L)。操作结果：操作结果：L 中第中第 i 个元素赋值同个元素赋值同 e 的值。的值。第8页，共99页，编辑于2022年，星期六ListInsert(&L,i,e)初始条件：线性表L已存在，1iLengthList(L)+1。操作
6、结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1iLengthList(L)。操作结果：删除删除 L的第i个元素，并用e返回其值，L的长度减长度减1。ADT List第9页，共99页，编辑于2022年，星期六2.1.2 2.1.2 线性表类型的应用线性表类型的应用 如果已经实现了上述定义的线性表类型，那么在应用问题的求解中就可以利用类型中定义的各种操作。下面将举三个例子说明之。第10页，共99页，编辑于2022年，星期六例例2-12-1 已知集合 A 和 B，求两个集合的并集，使 AAB，且 B 不再单独存在。从集
7、合的观点看，此问题求解的方法很简单，只要对集合 B 中的所有元素一个一个地检查，看看在集合 A 中是否存在相同元素，若不存在，则将该元素插入到集合 A，否则舍弃之。要在计算机中求解，首先要确定如何表示集合。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。现假设以线性表 LA 和 LB 分别表示集合 A 和 B，即构造两个线性表 LA 和 LB，它们的数据元素分别为集合 A 和 B 中的成员。由此，上述集合求并的问题便可演绎为：要求对线性表作如下操作：扩大线性表 LA，将存在于存在于线性表线性表 LB LB 中中而不存在于线性表不存在于线性表 LA LA 中中的数据元素插入到线
8、性表插入到线性表 LA LA 中中去。第11页，共99页，编辑于2022年，星期六具体操作步骤为：1从线性表 LB 中取出一个数据元素；2依值在线性表 LA 中进行查询；3若不存在，则将它插入到 LA 中。重复上述三步直至 LB 为空表止。那么，其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢？第12页，共99页，编辑于2022年，星期六容易看出，上述的每一步恰好对应线性表的一个基本操作：1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal();3.ListInsert(LA,n+1,e)第13页，共99页，编辑于2022年，星期六由此得到求并集的
9、算法如下所示：算法算法2.12.1voidvoid union(List&LA,List&LB)/将所有在线性表将所有在线性表LBLB中但不在中但不在LALA中的数据元素插入到中的数据元素插入到 LA LA 中中,算法执行之后，线性表算法执行之后，线性表 LB LB 不再存在。不再存在。La_len=ListLength(LA);/求得线性表 LA 的长度whilewhile(!ListEmpty(LB)/依次处理 LB 中元素直至 LB 为空表止 ListDelete(LB,1,e);/从 LB 中删除第1个数据元素并赋给 e ifif(!LocateElem(LA,e,equal()Lis
10、tInsert(LA,+La_len,e);/当LA中不存在和 e 值相同的数据元素时进行插入 /whileDestroyList(LB);/销毁线性表 LB)/union第14页，共99页，编辑于2022年，星期六例例2-22-2 已知一个非纯集合 B，试构造一个集合 A，使 A 中只包含 B 中所有值各不相同的数据元素。换句话说，此问题即为从 B 中挑选出所有彼此相异的元素构成一个新的集合。如何区分元素的相异或相同，一个简单方法即为将每个从 B 中取出的元素和已经加入到集合 A 中的元素相比较。如果还是以线性表 LB 和 LA 分别表示集合 B 和 A，那么和例2-1的问题相比，此问题求解
11、的算法应该如何写呢？第15页，共99页，编辑于2022年，星期六容易看出，应对线性表作和上例相同的操作，具体的三步也都相同，所不同之处仅仅在于所不同之处仅仅在于两点：两点：一是例2-1的算法中 LA 是已知的，而在此例算法中的 LA 是待新建的；二是例2-1在求得并集之后，原来的两个集合不再保留，而在此例中构建新的集合 A 的同时，原来的集合 B 不变。第16页，共99页，编辑于2022年，星期六算法算法2.22.2voidvoid purge(List&LA,List LB)/构造线性表构造线性表LALA，使其只包含使其只包含LBLB中所有值不相同的数据中所有值不相同的数据/元素元素,算法不
12、改变线性表算法不改变线性表LBLB InitList(LA);/创建一个空的线性表 LA La_len=0;Lb_len=ListLength(LB);/求线性表 LB 的长度 forfor(i=1;i=Lb_len;i+)/依次处理 LB 中每个元素 GetElem(LB,i,e);/取 LB 中第 i 个数据元素赋给 eifif(!LocateElem(LA,e,equal()ListInsert(LA,+La_len,e);/当 LA 中不存在和 e 值相同的数据元素时进行插入 /for)/purge第17页，共99页，编辑于2022年，星期六例例2-32-3 判别两个集合是否相等。两个
13、集合相等的充分必要条件是它们具有相同的元素。当以线性表表示集合时，两个线性表的长度应该相等，且表中所有数据元素都能一一对应，但相同的数据元素在各自的线性表中的位序不一定相同。由此，判别两个线性表中的数据元素是否完全相同的算法的基本思想为：首先判别两者的表长是否相等；在表长相等的前提下，如果对于一个表中的所有元素，都能在另一个表中找到和它相等的元素的话，便可得到两个线性表表示的集合相等的结论；反之，只要有一个元素在另一个表中不能找到相等元素时，便可得出不等的结论。第18页，共99页，编辑于2022年，星期六算法算法2.32.3boolbool isEqual(List LA,List LB)/若
14、线性表若线性表 LA LA 和和 LB LB 不仅长度相等，且所含数据元素也相同，不仅长度相等，且所含数据元素也相同，/则返回则返回 TRUETRUE，否则返回否则返回 FALSEFALSE。La_len=Listlength(LA);Lb_len=Listlength(LB);ifif(La_len!=Lb_len)returnreturn FALSEFALSE;/两表的长度不等 elseelse i=1;found=TRUETRUE;whilewhile(i=La_len&found)GetElem(LA,i,e);/取得 LA 中一个元素 ifif(LocateElem(LB,e,equ
15、al()i+;/依次处理下一个 elseelse found=FALSEFALSE;/LB中没有和该元素相同的元素 /whilereturnreturn found;/else)/isEqual第19页，共99页，编辑于2022年，星期六2.2.1 2.2.1 顺序表顺序表顺序表顺序表是线性表的顺序存储表示的简称，它指的是，“用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素”，即以“存储位置相邻存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系(有序对)”，并以表中第一个元素的存储位置作为线性表的起始地址，称作线线性表的基地址性表的基地址。如下图所示。第20页，
16、共99页，编辑于2022年，星期六 不失一般性，假设每个数据元素占据的存储量是一个常量 C，则后继元素的存储地址和其前驱元素相隔一个常量，即：LOC(ai)=LOC(ai-1)+C C 一个数据元素所占存储量由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到 LOC(ai)=LOC(a1)+(i-1)C 基地址基地址第21页，共99页，编辑于2022年，星期六用C语言描述的顺序表类型顺序表类型如下所示：/存储结构存储结构constconst intint MAXLISTSIZE=80;/预设的存储空间最大容量typedef struct typedef struct ElemTyp
17、e*elem;/存储空间基址 intint length;/当前长度 intint listsize;/允许的最大存储容量(以sizeofsizeof(ElemType)为单位)SqList;/俗称 顺序表顺序表第22页，共99页，编辑于2022年，星期六/基本操作接口基本操作接口(函数声明函数声明)voidvoid InitList(SqList&L,intint maxsize);/构造一个最大存储容量为 maxsize 的空的顺序表 L。void void DestroyList(SqList&L)/销毁顺序表 L。boolbool ListEmpty(SqList L)/若顺序表 L
18、为空表，则返回TRUETRUE，否则返回 FALSEFALSE。intint ListLength(SqList L)/返回顺序表 L 中元素个数。intint PriorElem(SqList L,ElemType cur_e)/若 cur_e 是顺序表 L 的元素，则返回其前驱的位序/(设第一个元素的前驱的位序为0)，否则返回-1。第23页，共99页，编辑于2022年，星期六intint NextElem(SqList L,ElemType cur_e)/若 cur_e 是顺序表 L 的元素，则返回其后继的位序/(设最后一个元素的后继的位序为L的表长+1)，否则返回-1。boolbool
19、GetElem(SqList L,intint pos,ElemType&e)/若11posLengthList(L)posLengthList(L)，则用 e 带回顺序表 L 中第 /pos个元素的值且返回函数值为TRUETRUE，否则返回函数值为FALSEFALSE。intint LocateElem(SqList L,ElemType e,boolbool(*compare)(ElemType,ElemType)/返回顺序表L中第第1 1个个与 e 满足满足关系 compare()的数据元素的位序。/若这样的元素不存在，则返回值为0。compare()为数据元素的判定函数。voidvoi
20、d ListTraverse(SqList L,voidvoid(*visit)(ElemType)/依次依次对顺序表 L 的每个元素调用函数 visit()。/一旦 visit()失败，则操作失败。voidvoid ClearList(SqList&L)/将顺序表 L 重置为空表。第24页，共99页，编辑于2022年，星期六boolbool PutElem(SqList L,intint pos,ElemType&e)/若1 1posposLengthList(L)LengthList(L)，则对顺序表 L 中第 pos 个元素/赋值同 e 的值且返回函数值为 TRUE，否则返回函数值为 F
21、ALSE。boolbool ListInsert(SqList&L,intint pos,ElemType e)/若存储空间未满且1 1posposLengthList(L)+1LengthList(L)+1，则在顺序表 L 的/第 pos 个元素之前插入新的元素 e，L的长度增1，且返回函数值为TRUE，/否则不改变顺序表且返回函数值为 FALSE。boolbool ListDelete(SqList&L,intint pos,ElemType&e)/若1 1posposLengthList(L)LengthList(L)，则删除顺序表 L 的第 pos 个元素 e，/L的长度增1，且返回函
22、数值为TRUE，否则不改变顺序表且返回函数值为FALSE。第25页，共99页，编辑于2022年，星期六以上定义的函数可在程序设计中引用，例如，上述算法算法2.22.2可改写为下列可在主函数中调用的函数。voidvoid purge(SqList&La,SqList Lb)/构造顺序表构造顺序表 LaLa，使其只包含使其只包含 Lb Lb 中所有值不相同的数据元素中所有值不相同的数据元素,/算法不改变顺序表算法不改变顺序表 Lb Lb boolbool b;intint Lb_len=Listlength(Lb);/求线性表 Lb 的长度 InitList(La,Lb_len);/创建一个空的线
23、性表 Laintint La_len=0;forfor(i=1;i=Lb_len;i+)/依次处理 Lb 中每个元素 b=GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 eifif(!LocateElem(La,e,equal()+La_len;b=ListInsert(La,La_len,e);/当 La 中不存在和 e 值相同的 /数据元素时，进行插入 /for第26页，共99页，编辑于2022年，星期六2.2.2 2.2.2 顺序表中基本操作的实现顺序表中基本操作的实现从顺序表的存储结构定义容易看出，由于顺序表的长度是个显值，且由于第i个元素恰好存储在数组的第 i 个分
24、量(数组下标为 i-1)中，因此其求长、判空以及存取第 i 个数据元素等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。一、初始化操作一、初始化操作二、元素定位操作二、元素定位操作三、插入元素操作三、插入元素操作四、删除元素操作四、删除元素操作五、销毁结构操作五、销毁结构操作第27页，共99页，编辑于2022年，星期六一、初始化操作一、初始化操作对顺序表而言，初始化的实质是为它分配一个足够应用的元素存储空间，由用户根据它对线性表的使用要求定义一个最大存储容量 maxsize，并约定当用户没有提出特殊需求(maxsize=0)时，按予设的最大存储量 MAXLISTSIZE 进行分配
25、。第28页，共99页，编辑于2022年，星期六算法算法2.42.4voidvoid InitList(SqList&L,intint maxsize)/构造一个空的线性表构造一个空的线性表 L Lifif(maxsize=0)maxsize=MAXLISTSIZE;L.elem=newnew ElemTypemaxsize;if if(!L.elem)exitexit(1);/存储分配失败L.length=0;/顺序表的初始长度为0L.listsize=maxsize;/该顺序表可以存储元素的最大容量 /InitList此算法的时间复杂度为O O(1)(1)。第29页，共99页，编辑于2022
26、年，星期六二、元素定位操作二、元素定位操作在顺序表中查询是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。第30页，共99页，编辑于2022年，星期六算法算法 2.5 2.5intint LocateElem(SqList L,ElemType e,voidvoid(*compare)(ElemType,ElemType)/在顺序表在顺序表L L中查找第中查找第1 1个值与个值与 e e 满足判定条件满足判定条件compare()compare()的元素，的元素，/若找到，则返回其在若找到，则返回其在 L L 中的位序，否则返回中的位序，否则返回
27、0 0。i=1;/i 的初值为第1元素的位序p=L.elem;/p 的初值为第1元素的存储位置whilewhile(i=L.length&!&!(*compare)(*p+,e)+i;/依次进行判定ifif(i=L.length)returnreturn i;/找到满足判定条件的数据元素为第 i 个元素elseelse returnreturn 0;/该线性表中不存在满足判定的数据元素 /LocateElem 此算法的时间复杂度为：O(ListLength(L)第31页，共99页，编辑于2022年，星期六三、插入元素操作三、插入元素操作首先分析，“插入元素”使线性表的逻辑结构发生什么变化？假设
28、在线性表的第i个元素之前插入一个元素e，使得线性表(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an)即：(1)改变了表中元素之间的关系，使 改变为和(2)表长增1由于顺序表是以存储位置相邻 表示元素之间的前驱和后继关系，则必须移动元素来体现元素之间发生的变化。第32页，共99页，编辑于2022年，星期六算法算法 2.6 2.6boolbool ListInsert(SqList&L,intint pos,ElemType e)/若存储空间不满且若存储空间不满且1 1posposListlength(L)+1Listlength(L)+1，则在顺序表则在顺序表 L L 的的/
29、第第 pos pos 个元素之前插入新的元素个元素之前插入新的元素 e e 且返回且返回TRUETRUE，否则返回否则返回FALSEFALSEifif(pos L.length+1)return FALSEreturn FALSE;/插入位置不合法ifif(L.length=L.listsize)return FALSEreturn FALSE;/当前存储空间已满，无法插入forfor(j=L.length-1;j=pos-1;-j)L.elemj+1=L.elemj;/插入位置及之后的元素右移L.elempos-1=e;/插入 e+L.length;/表长增1returnreturn TRU
30、ETRUE;/ListInsert 此算法的时间复杂度为：O O(ListLength(L)(ListLength(L)第33页，共99页，编辑于2022年，星期六四、删除元素操作四、删除元素操作同样首先分析，“删除元素”使线性表的逻辑结构发生什么变化？假设删除线性表中第i个元素，使得线性表(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an)即：(1)改变了表中元素之间的关系，使和 改变为(2)表长减1对顺序表而言，需要改变从第 i+1 个元素起到第 n 个元素的存储位置，即进行从第 i+1 到第 n 个元素往前移动一个位置。第34页，共99页，编辑于2022年，星
31、期六算法算法 2.7 2.7boolbool ListDelete(SqList&L,intint pos,ElemType&e)/若若11posListlength(L)posListlength(L)，则以则以 e e 带回从顺序表带回从顺序表 L L 中删除的中删除的 /第第 pos pos 个元素且返回个元素且返回 TRUETRUE，否则返回否则返回 FALSEFALSEifif(pos L.length)return FALSEreturn FALSE;/删除位置不合法forfor(j=pos;jL.length;+j)L.elemj-1=L.elemj;/被删除元素之后的元素左移
32、-L.length;/表长减1return TRUEreturn TRUE;/ListDelete 此算法的时间复杂度为：O O(ListLength(L)(ListLength(L)第35页，共99页，编辑于2022年，星期六五、销毁结构操作五、销毁结构操作算法算法 2.8 2.8voidvoid DestroyList(SqList&L)/释放顺序表释放顺序表 L L 所占存储空间所占存储空间deletedelete L.elem;L.listsize=0;L.length=0;/DestroyList_Sq 此算法的时间复杂度为：O O(1)(1)第36页，共99页，编辑于2022年，星
33、期六六、插入和删除操作的性能分析六、插入和删除操作的性能分析(p25)第37页，共99页，编辑于2022年，星期六2.2.3 顺序表其它算法举例顺序表其它算法举例例例2-4试编写算法“比较”两个顺序表的大小。算法的基本思想为：若ai=bj，则j增1，之后继续比较后继元素；否则即可得出比较结果。显然，j 的初值应为的初值应为 0，循环的条件是，循环的条件是 j 不超出其中任何一个表的范围不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有三种可能出现的情况需要区分。根据以上分析可得下列算法。第38页，共99页，编辑于2022年，星期六算法算法 2.9 intcompare(Sq
34、ListA,SqListB)/若若 AB，则返回则返回 1j=0;while(jA.length&jB.length)if(A.elemjB.elemj)return(1);elsej+;if(A.length=B.length)return(0);else if(A.lengthB.length)return(-1);else return(1);/compare上述算法中只有一个while循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法2.9的时间复杂度为O(Min(A.length,B.length)。第39页，共99页，编辑于2022年，星期六例例2-5试设计一个算法，用尽可能
35、少的辅助空间将顺序表中前m个元素和后n个元素进行互换，即将线性表(a1,a2,am,b1,b2,bn)改变成(b1,b2,bn,a1,a2,am)。第40页，共99页，编辑于2022年，星期六算法算法2.10voidinvert(ElemType&R,ints,intt)/本算法将数组本算法将数组 R 中下标自中下标自 s 到到 t 的元素逆置，即将的元素逆置，即将/（Rs,Rs+1,Rt-1,Rt）改变为（改变为（Rt,Rt-1,Rs+1,Rs）for(k=s;k0&mA.length)n=A.length-m;invert(A.elem,0,m+n-1);invert(A.elem,0,n
36、-1);invert(A.elem,n,m+n-1);/exchange第42页，共99页，编辑于2022年，星期六例例2-6编写算法删除顺序表中多余的数据元素，即使操作之后的顺序表中所有元素的值都不相同。第43页，共99页，编辑于2022年，星期六算法算法2.12voidpurge_Sq(SqList&L)/删除顺序表删除顺序表L中的冗余元素，即使操作之后的顺序表中只保留中的冗余元素，即使操作之后的顺序表中只保留/操作之前表中所有值都不相同的元素操作之前表中所有值都不相同的元素 k=-1;/k指示新表的表尾for(i=0;iL.length;+i)/顺序考察表中每个元素j=0;while(j
37、k)/k=-1表明当前考察的是第一个元素L.elem+k=L.elemi;/forL.length=k+1;/修改表长/purge_Sq此算法的时间复杂度为O(ListLength2(L)第44页，共99页，编辑于2022年，星期六分析：算法中的基本操作为比较，控制结构为两重循环，外循环的执行次数和顺序表的表长相同，内循环的执行次数则不超过表长。此外，比较操作相对于移动操作所需的时间也少。从这个题的算法可以得到一些有益的启示，某种情况下，删除操作也可利用插入来实现。第45页，共99页，编辑于2022年，星期六2.3.1 单链表和指针单链表和指针线性表的链式存储表示的特点是用一组任意的存储单元存
38、储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个结点（如下图所示），表示线性表中一个数据元素ai其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链链。数据域 data指针域 next第46页，共99页，编辑于2022年，星期六由分别表示a1,a2,an的N个结点依次相链构成的链表，称为线
39、性表的链式存储表示线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表单链表或线性链表线性链表，如下图所示。和顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，通常称它为头指针，线性表中所有数据元素都可以从头指针出发找到。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的指针是一个特殊的值NULL（在图上用表示），通常称它为空指针。第47页，共99页，编辑于2022年，星期六为了便于处理一些特殊情况，在第一个结点之前附加一个头结点，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，如下图所示。值得注意的是，若线性表为空，在
40、不带头结点的情况下，头指针为空(NULL)，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空，如下图所示。第48页，共99页，编辑于2022年，星期六可以用C语言中的“结构指针”来描述链表结构typedef structLNodeElemTypedata;structLNode*next;*SLink;若设LNode*p,*q;SLinkH;则p，q和H均为以上定义的指针型变量。若p的值非空，则表明p指向某个结点，p-data表示p所指结点中的数据域，p-next表示p所指结点中的指针域，若非空，则指向其后继结点。第49页，共99页，编辑于2022年，星期六指针型变量只
41、能作同类型的指针赋值与比较操作。并且，指针型变量的值除了由同类型的指针变量赋值得到外，都必须用C语言中的动态分配函数得到。例如，p=newLNode;表示在运行时刻系统动态生成了一个LNode类型的结点，并令指针p指向该结点。反之，当指针p所指结点不再使用，可用deletep;释放此结点空间。第50页，共99页，编辑于2022年，星期六2.3.2 单链表中基本操作的实现单链表中基本操作的实现以下重点讨论线性表的五个基本操作在链式存储结构中的实现。一、初始化操作一、初始化操作根据上一节的约定，初始化建一个空的链表即为建立一个只有头结点的链表。算法算法2.13voidInitList(SLink&
42、L)/创建一个带头结点的空链表创建一个带头结点的空链表,L 为指向头结点的指针为指向头结点的指针L=newLNode;if(!L)exit(1);/存储空间分配失败L-next=NULL;/nitList算法的时间复杂度为O(1)。第51页，共99页，编辑于2022年，星期六二、销毁结构操作二、销毁结构操作算法算法2.14voidDestroyList(SLink&L)/销毁以销毁以L为头指针的单链表，释放链表中所有结点空间为头指针的单链表，释放链表中所有结点空间while(L)p=L;L=L-next;deletep;/whileL=NULL;/DestroyList算法的时间复杂度为O(L
43、istlength(L)。第52页，共99页，编辑于2022年，星期六三、存取元素操作三、存取元素操作单链表是一种“顺序存取”的结构，即：为取第i元素，首先必须先找到第i-1个元素。因此不论i值为多少，都必须从头结点开始起“点数“，直数到第i个为止。头结点可看成是第0个结点。第53页，共99页，编辑于2022年，星期六算法算法2.15boolGetElem(SLinkL,intpos,ElemType&e)/若若1posLengthList(L)，则用则用 e 带回指针带回指针L指向头结点的单链表指向头结点的单链表/中第中第 pos 个元素的值且返回函数值为个元素的值且返回函数值为TRUE,否
44、则返回函数值为否则返回函数值为FALSEp=L-next;j=1;/变量初始化，p指向第一个结点while(p&jnext;+j;/whileif(!p|jpos)return FALSE;/链表中不存在第pos个结点e=p-data;/取到第pos个元素return TRUE;/GetElem算法的时间复杂度为O(ListLength(L)。第54页，共99页，编辑于2022年，星期六四、插入元素操作前面已经分析过，在线性表中“插入”一个元素时，使元素之间的关系改变为和。当用指针指示后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可。因为新的元素插入在线性表的第i个元素之前，使得
45、ai不再是ai-1的后继，而是新的元素e的后继，因此需要修改元素e和元素ai-1所在结点的指针。由此，算法的基本思想就是，首先找到第i-1个结点，然后修改相应指针。第55页，共99页，编辑于2022年，星期六算法算法2.16boolListInsert(SLink&L,intpos,ElemTypee)/若若1posLengthList(L)+1，则在指针则在指针L指向头结点的单链表指向头结点的单链表/的第的第 pos 个元素之前插入新的元素个元素之前插入新的元素 e，且返回函数值为且返回函数值为 TRUE,/否则不进行插入且返回函数值为否则不进行插入且返回函数值为 FALSEp=L;j=0;
46、while(p&jnext;+j;/whileif(!p|jpos-1)return FALSE;/参数不合法，pos小于1或者大于表长+1s=newLNode;if(!s)exit(1);/存储空间分配失败s-data=e;/创建新元素的结点s-next=p-next;p-next=s;/修改指针return TRUE;/ListInsert算法时间复杂度为O(ListLength(L)。第56页，共99页，编辑于2022年，星期六五、删除元素操作五、删除元素操作和插入类似，由于删除元素ai改变了元素之间的关系，使ai+1不再是ai的后继，而是ai-1的后继，因此需要修改元素ai-1所在结点
47、的指针。因此在单链表中删除元素操作的算法基本思想和插入相同，也是：首先找到第i-1个结点，然后修改相应指针。第57页，共99页，编辑于2022年，星期六算法算法2.17boolListDelete(SLink&L,intpos,ElemType&e)/若若1posLengthList(L)，则删除指针则删除指针L指向头结点的单链表指向头结点的单链表/中第中第 pos 个元素并以个元素并以 e 带回其值，返回函数值为带回其值，返回函数值为 TRUE，/否则不进行删除操作且返回函数值为否则不进行删除操作且返回函数值为 FALSEp=L;j=0;while(p-next&jnext;+j;if(!(
48、p-next)|ji-1)return FALSE;/删除位置不合理q=p-next;p-next=q-next;/修改指针e=q-data;delete(q);/释放结点空间return TRUE;/ListDelete_L算法时间复杂度为O(ListLength(L)。第58页，共99页，编辑于2022年，星期六2.3.3 单链表其它算法举例单链表其它算法举例例例2-7逆序创建链表假设线性表(a1，a2，an)的数据元素存储在一维数组An中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为空的链表中。第59页，共99页，编辑于2022年，星期六算法算法2.19voidCrea
49、teList_L(SLink&L,intn,ElemTypeA)/已知数组已知数组 A 中存有线性表的中存有线性表的 n 个数据元素，个数据元素，/逆序建立带头结点的单链表。逆序建立带头结点的单链表。L=newLNode;if(!L)exit(1);/存储空间分配失败L-next=NULL;/先建立一个带头结点的空的单链表for(i=n;i0;-i)p=newLNode;if(!p)exit(1);/存储空间分配失败p-data=Ai-1;/赋元素值p-next=L-next;L-next=p;/插入在头结点之后/for/CreateList_L容易看出，算法的时间复杂度为O(ListLeng
50、th(L)。第60页，共99页，编辑于2022年，星期六例例2-8以链表作存储结构解例2-5的问题，即将线性表(a1,a2,am,b1,b2,bn)改变成(b1,b2,bn,a1,a2,am)。解题分析解题分析：因为对链表来说，“插入”和“删除”仅需修改指针即可完成，并且由于前m个元素之间和后n个元素之间的链接关系分别都不需要改变，则算法的实际操作为：第61页，共99页，编辑于2022年，星期六算法算法2.20voidexchange_L(SLink&L，intm)/本算法实现单链表中前本算法实现单链表中前 m 个结点和后个结点和后 n 个结点的互换个结点的互换if(m&L-next)/链表不