(2)--lecture2数据结构数据结构.ppt

《(2)--lecture2数据结构数据结构.ppt》由会员分享，可在线阅读，更多相关《(2)--lecture2数据结构数据结构.ppt（139页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第第2章章 线性表线性表 线线性表是一种最性表是一种最简单简单的数据的数据结结构，也是构造其它各构，也是构造其它各类类复复杂杂数据数据结结构的基构的基础础。它有。它有顺顺序和序和链链式两种存式两种存储储表表示方法。示方法。线线性表的性表的类类型定型定义义包括它的包括它的逻辑逻辑定定义义及其操作，以及其操作，以不同的存不同的存储储方式表示方式表示线线性表性表时时，其操作也各具特色。，其操作也各具特色。通通过对线过对线性表的操作及性表的操作及线线性表性表应应用算法的用算法的评评价，可价，可以加深以加深对对算法分析方法的理解。算法分析方法的理解。2v 2.1 线性表的性表的类型定型定义v 2.3

2、线性表的性表的链式表示和式表示和实现 v 2.4 有序表有序表v 2.2 线性表的性表的顺序表示和序表示和实现 v 2.5 顺序表和序表和链表的表的综合比合比较32.1 线性表的性表的类型定型定义41集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素”；3除最后元素在外，均有除最后元素在外，均有 唯一的后唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前唯一的前驱。线性结构的基本特征为:一个数据元素的有序（次序）集,例如:(A,2,3,10,J,Q,K)线性表性表是一种最简单的线性性结构构5线性表线性

3、表的定义的定义 线性表中的元素个数性表中的元素个数n（n0）定）定义为其其长度，度，n=0 的的线性表称性表称为空表。空表。记作作 （a1,a2,ai-1,ai,ai+1,an）在非空在非空线性表中的每个元素都有一个确定性表中的每个元素都有一个确定的位置，如的位置，如 a1 是第一个元素，是第一个元素，an 是最后一个是最后一个元素；元素；ai 为第第 i 个元素，称个元素，称 i 为数据元素数据元素 ai 在在线性表中的性表中的序位序位。6线性表线性表的的基本操作：基本操作：（可划分成四大类操作）（可划分成四大类操作）v 结构初始化操作v 结构销毁操作v 引用型操作v 加工型操作7 Init

4、List(&L)操作结果：构造一个空的线性表L。初始化操作初始化操作8 结构构销毁操作操作DestroyList(&L)初始条件：操作结果：线性表 L 已存在。销毁线性表 L。9ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare()ListTraverse(L,visit()引用型操作引用型操作(不涉及表不涉及表结构的构的变化化):):10 ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TR

5、UE，否则FALSE。（线性表判空）11ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）12 PriorElem(L,cur_e,&pre_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）13NextElem(L,cur_e,&next_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）14GetElem(L,i,&e)初

6、始条件：操作结果：线性表L已存在，且 1iLengthList(L)。用e 返回L中第 i 个元素的值。（求线性表中某个数据元素）15LocateElem(L,e，compare()初始条件：操作结果：线性表L已存在，e为给定值，返回L中第中第1个个与e满足足关系的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）16 ListTraverse(L,visit()初始条件：操作结果：线性表L已存在。依次依次访问L中中的每个元素。（遍历线性表）17加工型操作加工型操作(表的表的结构有构有变化化):):ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i

7、,e)ListDelete(&L,i,&e)18ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）19PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）20 ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)+1。在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）21ListDelete(&L,i,&e)初始条件：操作结果：线性表L已存在且非空，1iLengthList(L)。

8、删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）22 利用上述定义的线性表性表类型可以实现其它更复杂的操作例例 2-2例例 2-1 此时尚未触及线性表性表类型具体的存储结构，仅使用其操作操作来描述算法，评估算法。例例 2-323 假设:有两个集合集合 A 和和 B 分别用两个线性表性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合要求一个新的集合AAB。例例 2-1 24 要求对线性表作如下操作：扩大线性表 LA，将存在于存在于线性表性表LB 中中而不存在于不存在于线性表性表 LA 中中的数据元素插入到插入到线性表性表 LA 中中去。上述

9、问题可演绎为：251.从线性表LB中依次察看每个数据元素;2.依值在线性表LA中进行查访;3.若不存在，则插入之。GetElem(LB,i)e LocateElem(LA,e,equal()(equal()函数函数实现元素的比元素的比较操作操作)ListInsert(LA,n+1,e)操作步操作步骤：26 GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之void union(List&La,List Lb)La_len=ListLe

10、ngth(La);/求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)/union时间复复杂度：度：O(ListLength(LA)*ListLength(LB)?27 已知已知一个非非纯集合集合 B，试构造构造一个纯集合集合 A，使使 A中只包含中只包含 B 中所有中所有值各不相同各不相同的数据元素数据元素。仍选用线性表性表表示集合。例例 2-228集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同同样物件不能有两件以上物件不能有两件以上因此，算法的策略算法的策略应该和例和例2-1相同相同29void union1(Lis

11、t&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);/union1 GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 e if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之for(i=1;i=Lb_len;i+)InitList(La);/构造(空的)线性表LA时间复复杂度：度：O(ListLength(LB)2)30 有序表有序表的定的定义：若线性表中的数据元素相互之间可以比比较，并且数据元素在线性表中依依值非非递减或

12、非减或非递增有序增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表有序表(Ordered List)。若按有序表若按有序表类型，型，试考考虑例例2-2的算法的算法例如：例如：（2，3，3，5，6，6，6，8，12）对集合集合 B 而言，而言，值相同的数据元素必定相相同的数据元素必定相邻对集合集合 A 而言，而言，数据元素依数据元素依值从小至大的从小至大的顺序插入序插入因此，数据因此，数据结构改构改变了，了，解决解决问题的策略也相的策略也相应要改要改变。32void purge(List&La,List Lb)/Lb为有序表 InitList(LA);La_l

13、en=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度 for(i=1;i=Lb_len;i+)/purge GetElem(Lb,i,e);/取Lb中第i个数据元素赋给 eif(ListEmpty(La)|(en!=e)ListInsert(La,+La_len,e);en=e;/La中不存在和 e 相同的数据元素，则插入之算法算法时间复复杂度：度：O(ListLength(LB)33例例 2-3 有序有序线性表合并性表合并LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)LC=(2,3,5,6,8,8,9,11,11,15,20)

14、合并后：合并后：已知已知两个有序线性表LA,LB,合并后的线性表同样有序1初始化初始化 LC 为空表；空表；基本操作：基本操作：2分分别从从 LA和和LB中取得当前元素中取得当前元素 ai 和和 bj；3若若 aibj，则将将 ai 插入到插入到 LC 中，否中，否则将将 bj 插入到插入到 LC 中；中；4重复重复 2 和和 3 两步，直至两步，直至 LA 或或 LB 中元素中元素 被取完被取完为止；止；5将将 LA 表或表或 LB 表中剩余元素复制插入到表中剩余元素复制插入到 LC 表中。表中。35void MergeList(List La,List Lb,List&Lc)InitLis

15、t(LC);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j /while 36 while(i=La_len)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);

16、/MergeList时间复复杂度：度：O(ListLength(LA)+ListLength(LB)372.2 线性表的性表的顺序表示和序表示和实现 现在将涉及线性表的存储结构，并以此来实现线性表类型的那些基本操作。首先，是顺序表。38 用一组地址地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的性表的起始地址起始地址称作线性表的基地址基地址顺序表的由来：序表的由来：39 顺序存储顺序存储：把线性表的结点：把线性表的结点按逻辑顺序按逻辑顺序依次存放在依次存放在一组地址连续的存储单元一组地址连续的存储单元里。用这种方法存储的线性表里。用这种方法存储的

17、线性表简称顺序表。简称顺序表。顺序存储顺序存储的线性表的的线性表的特点特点：线性表的逻辑顺序与物理顺序一致线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内数据元素之间的关系是以元素在计算机内“物理物理位置相邻位置相邻”来体现。来体现。设有非空的线性表：设有非空的线性表：(a1，a2，an)。顺序存储如图。顺序存储如图2-1所示。所示。在具体的机器在具体的机器环境下境下：设线性表的每个元素需占用性表的每个元素需占用l个存个存储单元，以所占的第一个元，以所占的第一个单元的存元的存储地址作地址作为数据数据元素的存元素的存储位置。位置。则线性表中第性表中第i+1个数据元素的存个数据

18、元素的存储位置位置LOC(ai+1)和第和第i个数据元素的存个数据元素的存储位置位置LOC(ai)之之间满足下列关系：足下列关系：LOC(ai+1)=LOC(ai)+l 线性表的第性表的第i个数据元素个数据元素ai的存的存储位置位置为：LOC(ai)=LOC(a1)+(i-1)*l a1 a2 ai an Loc(a1)Loc(ai)+(i-1)*l 图图2-1 线性表的顺序存储表示线性表的顺序存储表示41 在高级语言的层次，通常以一一维数数组来实现“依次存放依次存放”线性表性表数据元素数据元素的顺序表序表。并可直接通过数组元素的下下标方便地访问数据元素数据元素。a1aia2an01i-1L.

19、length-1 L.listsize 应当注意，存放数据元素的数组下下标比元素的位序位序差1。42顺序表的序表的 C 语言描述言描述typedef struct SqList;/俗称顺序表序表#define LIST_INIT_SIZE 80 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /（以ElemType为单位)int incrementsize;/约定的增补空间量43线性表的基本操作在性表的基本操作在顺序表

20、中的序表中的实现InitList(&L)/结构初始化LocateElem(L,e)/查找ListInsert(&L,i,e)/插入元素ListDelete(&L,i)/删除元素 （限于版面，仅实现四个典型操作）44void InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq算法时间复复杂度度：O(1)L.elem=new ElemTypeLIST_INIT_SIZE;if(!L.elem)exit(OVERFLOW);L.length=0;/线性表当前长度L.listsize=LIST_INIT_SIZE;L.incrementsize=LISTINCRE

21、MENT;/增补空间量45顺序表的查找算法 LocateElem 操作示意23 75 41 38 54 62 17L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p 可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。46 int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)）/在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回 0/LocateElem_Sq/依次进行判定 O(ListLength(L)算法的算法的时

22、间复复杂度度为：i=1;/i 的初值为第 1 元素的位序p=L.elem;/p 的初值为第 1 元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;47线性表操作 ListInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构构发生什么生什么变化化？若线性表的空间不够了，如何如何扩容容？48(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an),表的表的长度增加度增加a1 a2 ai-1 ai ana1 a2 ai-1ai ane插入元素

23、之前插入元素之前插入元素插入元素过程程（自动演示动画）49 void ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1 /ListInsert_Sq 算法的算法的时间复复杂度度为:O(ListLength(L)q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e;/插入e+L.length;/表长增1（具体具体见后面的程序段后面的程序段）元素右移元素右移50

24、21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;p51 在进行插入算法分析时，按渐进时间复杂度衡量是O(n)。但实际的发生情况又不尽然是“最坏情况”，具体的操作发生位置是随机的。插入和删除操作是经常要使用的操作，若进行统计性的分析，可求得到一个平均的结果。52考考虑移移动元素的平均情况元素的平均情况:假设在第 i 个元素之前插入的概率为 ，则在长度为n 的

25、线性表中插入一个元素所需插入一个元素所需移移动元素次数的期望元素次数的期望值为：若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移移动元素的期望元素的期望值为：53if(L.length=L.listsize)/当前存储空间已满，增加分配 increment(L,k)；/调用扩充空间的函数 if(!increment)exit(“OVERFLOW);/存储分配失败 if(i L.length+1)return ERROR;/插入位置不合法合法性判断与空间动态扩充的程序段：54动态扩充空间函数的实现算法：void increment(SqlList&L,int k)E

26、lemType a;a=new ElemTypeL.listsize+k;/申请缓存L的辅助空间if(!a)return ERROR;/ERROR状态码为0for(i=0;iL.length;i+)ai=L.elemi;/用a缓存LDelete L.elem;L.elem=a;/把缓存的数据复制到LL.listsize+=k;55线性表操作 ListDelete(&L,i,&e)的实现：首先分析：首先分析：删除元素时，线性表的逻辑结构发生什么变化？56(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an),表的长度减少a1 a2 ai-1 ai ai+1 ana1

27、a2 ai-1aiai+1 an删除元素之前除元素之前删除元素除元素过程程（自动演示动画）57void ListDelete_Sq (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减1算法的算法的时间复复杂度度为:O(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置e=*p;/被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置if(i L.length)return ERROR;/删除位置不合法元素左移

28、元素左移5821 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p=&(L.elemi-1);q=L.elem+L.length-1;for(+p;p data=20;p-next=NULL;p20NULL指指针最常用的基本操作及其示意最常用的基本操作及其示意图 常见的指针操作常见的指针操作 q=p;pa操作前操作前paq操作后操作后 q=p-next;bpa操作前操作前操作后操作后qbpa p=p-next;bpa操作前操作前操作后操作后pba q-next=p;cpbqa操作前操作前操作后操作后qbacp(a)q-next=p-next;(a

29、)xypbqa操作前操作前操作后操作后qbaxyp操作前操作前ypxbqa操作后操作后ypxbqa(b)操作前操作前ypxbqa操作后操作后ypxbqa(b)69三、单链表的基本操作三、单链表的基本操作ListLength_L /求求线性表的性表的长度度LocateElem_L /查找元素找元素ListInsert_L /插入插入结点点ListDelete_L /删除除结点点70 线性表的操作 ListLength_L(L)在单链表中的实现:L211830754256pk0p1p2p3 4p5pp671 单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器。边遍历链表的结

30、点，边进行计数，当遍历的指针跑空时，计数器的累计结果即为线性表的长度。72int ListLength_L(LinkList L)/L 为链表的头指针，本函数返回 L 所指链表的长度 p=L;k=0;while(p)k+;p=p-next;/k 计非空结点数 /while return k;/ListLength_L算法算法时间复复杂度度为:O(ListLength(L)单链表的表的查找找按序号按序号查找找 取取单链表中的第表中的第i个元素。个元素。对于于单链表，不能象表，不能象顺序表中那序表中那样直接按序号直接按序号i访问结点，而只能从点，而只能从链表的表的头结点出点出发，沿，沿链域域nex

31、t逐逐个个结点往下搜索，直到搜索到第点往下搜索，直到搜索到第i个个结点点为止。因此，止。因此，链表不是随机存取表不是随机存取结构构。设单链表的表的长度度为n，要，要查找表中第找表中第i个个结点，点，仅当当1 i n时，i的的值是合法的。是合法的。算法描述算法描述Status Get_Elem(LinkList L,int i,ElemType&e)int j;LNode*p;p=L-next;j=1;/*使使p指向第一个结点指向第一个结点 */while (p&jnext;j+;/*移动指针移动指针p,j计数计数 */if (!p|ji)return ERROR;/*p为为NULL 表示表示i

32、太大太大;ji表示表示idata;return OK;移移动指指针p的的频度：度：in：n次。次。时间复复杂度度:O(n)。75线性表的操作 LocateElem_L(L,e)在单链表中的实现:pppe=3058L211830754256ppppppp按内容按内容查找找76 与求链表长度的算法类似，在遍历单链表时，边遍历，边比较给定值与结点的数据域值。查找结果有两种可能：找到时，返回第一个和值e 相等的数据结点指针；找不到，返回空指针。77LNode*LocateElem_L(LinkList L，ElemType e)/在 L 所指的链表中查找第一个值和 e 相等的数据/元素，若存在，则返回

33、它在链表中的位置，/即指向该数据元素所在结点的指针；否则返回 NULL p=L;while(p&p-data!=e)p=p-next;return p;/LocateElem_L算法算法时间复复杂度度为:O(ListLength(L)单链表的插入表的插入(按序号按序号)插入运算是将插入运算是将值为e的新的新结点插入到表的第点插入到表的第i个个结点的点的位置上，即插入到位置上，即插入到ai-1与与ai之之间。因此，必。因此，必须首先找到首先找到ai-1所所在在的的结点点p，然后生成一个数据域，然后生成一个数据域为e的新的新结点点q，q结点作点作为p的直接后的直接后继结点。点。算法描述算法描述St

34、atus Insert_LNode(LinkList&L,int i,ElemType e)/*在以在以L为头结点的点的单链表的第表的第i个位置插入个位置插入值为e的的结点点*/int j=0;LNode*p，*s;p=Lnext;while (p&jnext;j+;/*寻找第寻找第i-1个节点个节点*/if (!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);sdata=e;snext=pnext;pnext=s;return OK;设链表的表的长度度为n，合法的插入位置是，合法的插入位置是1 i n。算。算法的法的时间主要耗主要耗费

35、移移动指指针p上，故上，故时间复复杂度亦度亦为O(n)。80 线性表的操作ListInsert_L(&L,p,s)在单链表中的实现：epsq单链表的插入表的插入(按位置按位置)81 在p指针所指的结点之前，插入已经生成的结点s。为完成插入操作，指针的链接改动需要先确定p指针原来的前驱结点位置信息。为此，需从头遍历链表，以定位前驱结点的指针q。82void ListInsert_L(LinkList&L,Lnode*p,Lnode*s)/指针 p 指向 L 为头指针的链表中某个结点，/将 s 结点插入到 p 结点之前 if(p=L)/将 s 结点插入在链表的第一个结点之前 s-next=L;L=

36、s;else q=L;while(q-next!=p)q=q-next;/查找 p 的前驱结点 q q-next=s;s-next=p;/在链表中 q 结点之后插入 s 结点 /else/ListInsert_L算法算法时间复复杂度度为:O(ListLength(L)单链表的表的删除除 按序号按序号删除除 删除除单链表中的第表中的第i个个结点。点。为了了删除第除第i个个结点点ai，必，必须找到找到结点的存点的存储地址。地址。该存存储地址是在其直接前地址是在其直接前趋结点点ai-1的的next域中，因此，域中，因此，必必须首先找到首先找到ai-1的存的存储位置位置p，然后令，然后令pnext指向

37、指向ai的直接后的直接后继结点，即把点，即把ai从从链上摘下。最后上摘下。最后释放放结点点ai的空的空间，将其，将其归还给“存存储池池”。设单链表表长度度为n，则删去第去第i个个结点点仅当当1 i n时是合法的。是合法的。则当当i=n+1时，虽然被然被删结点不存在，但其点不存在，但其前前趋结点却存在，是点却存在，是终端端结点。故判断条件之一是点。故判断条件之一是pnext!=NULL。显然此算法的然此算法的时间复复杂度也是度也是O(n)(n)。算法描述算法描述Status Delete_LinkList(LNode*L，int i，ElemType&e)/*删除以除以L为头结点的点的单链表中的

38、第表中的第i i个个结点点 */int j=0;LNode*p，*q;p=L;q=L-next;while (p-next!=NULL&jnext;j+;/p/p指向第指向第i i个节点的前驱个节点的前驱if (!(p-next)|ji-1)return ERROR;q=pnext;pnext=qnext;e=q-data;free(q);85线性表性表的操作ListDelete_L(&L,p,&e)在链表中的实现:pqe按位置按位置删除除86 删除p指针所指的结点时，为完成删除操作，指针的链接改动需要先确定p指针原来的前驱结点的位置。为此，需从头遍历链表，以定位前驱结点的指针q。在删除p指针

39、所指的结点之前，应将结点的数据移交给引用参量e。87void ListDelete_L(LinkList&L,Lnode*p,ElemType&e)/p指向L为头指针的链表中某个结点，/从链表中删除该结点并由e返回其元素 if(p=L)/删除链表中第一个结点，修改链表头指针 L=p-next;else q=L;while(q-next!=p)q=q-next;/查找 p 的前驱结点 q q-next=p-next;/修改 q 结点的指针域 /else e=p-data;delete p;/返回被删结点的数据元素，并释放结点空间/ListDelete_L按按值删除除 删除除单链表中表中值为key

40、的第一个的第一个结点。点。与按与按值查找相找相类似，首先要似，首先要查找找值为keykey的的结点是点是否存在否存在?若存在，若存在，则删除；否除；否则返回返回NULL。算法描述算法描述void Delete_LinkList(LNode*L，int key)/*删除以除以L为头结点的点的单链表中表中值为key的第一个的第一个结点点 */LNode*p=L,*q=Lnext;while (q!=NULL&qdata!=key)p=q;q=qnext;if (qdata=key)p-next=q-next;free(q);else printf(“所要删除的结点不存在所要删除的结点不存在!n”)

41、;90如何从线性表得到单链表？链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。四、单链表的创建操作四、单链表的创建操作 CreateList(&L,n)生成单链表有多种方式，本例采取逆位序输入元素值，以方便编写算法。91例如：逆位序输入n n个数据元素的值，建立带头结点的单链表。操作步操作步骤：1.建立一个“空表”；2.输入数据元素an，建立结点并插入；3.输入数据元素an-1，建立结点并插入；ananan-14.依次类推，直至输入a1为止。92void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头

42、结点的单链表/CreateList_L算法的算法的时间复复杂度度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入单链表的合并表的合并 设有两个有序的有两个有序的单链表，它表，它们的的头指指针分分别是是La、Lb，将它，将它们合并合并为以以Lc为头指指针的有序的有序链表。合并表。合并前的示意前的示意图如如

43、图2-4所示。所示。15 图2-4 两个有序的两个有序的单链表表La，Lb的初始状的初始状态-2 4 9 Lb pb-7 3 12 23 La Lcpapc合并了合并了值为-7，-2的的结点后示意点后示意图如如图2-5所示。所示。图2-5 合并了合并了值为-7，-2的的结点后的状点后的状态-2 4 9 15 Lb pcpbLc-7 3 12 23 La pa算法说明算法说明 算法中算法中pa，pb分别是待考察的两个链表的当前结分别是待考察的两个链表的当前结点，点，pc是合并过程中合并的链表的最后一个结点。是合并过程中合并的链表的最后一个结点。算法描述算法描述void MergeList_L(L

44、inkList&La，LinkList&Lb,LinkList&Lc)/*合并以合并以La,Lb为头结点的两个有序点的两个有序单链表表 */LNode*Lc,*pa,*pb,*pc,*ptr;Lc=pc=La ;pa=La-next;pb=Lb-next ;while(pa&pb)if (pa-datadata)pc-next=pa;pc=pa;pa=pa-next ;/*将将pa所指的结点合并，所指的结点合并，pa指向下一个结点指向下一个结点 */else pc-next=pb;pc=pb;pb=pb-next ;/*将将pa所指的结点合并，所指的结点合并，pa指向下一个结点指向下一个结点

45、*/while pc-next=pa?pa:pb;/*将剩余的结点链上将剩余的结点链上*/free(Lb);/MergeList_L算法分析算法分析 若若La，Lb两个两个链表的表的长度分度分别是是m，n，则链表表合并的合并的时间复复杂度度为O(m+n)。97 1.双向双向链表表五、其它形式的五、其它形式的链表表typedef struct DuLNode ElemType data;/数据域 struct DuLNode *prior;/指向前驱的指针域 struct DuLNode *next;/指向后继的指针域 DuLNode,*DuLinkList;98 最后一个结点的指针域的指针又指

46、回第一个结点的链表 a1 a2 .an 2.循循环链表表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。99 在循环链表中，头指针也可以改变到指向尾结点，这样用一个头指针就能够控制首位两端，可为有些操作带来便利。a1 a2 .an 100双向循双向循环链表表空表空表非空表非空表 a1 a2 .an101双向双向链表的操作特点：表的操作特点：“查询”和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。由于前驱指针的设置，如需要前驱的位置信息时，可直接使用，避免了遍历操作的时间消耗。102ai-1aies-next=p-next;p

47、-next=s;s-next-prior=s;s-prior=p;psai-1ai插入插入103ai-1删除除aiai+1p-next=p-next-next;p-next-prior=p;pai-1104 顺序表序表和和链表表的的综合比合比较105v 线性表性表长度的考度的考虑w若表的长度增加不太多时，顺序表可作为首选的结构；反之，则选择链表。v 算法所涉及到具体操作的考算法所涉及到具体操作的考虑w算法是否频繁遇到插入和删除的操作？如是，则选用链表。w算法是否常会遇到位序的定位操作？如是，则以顺序表为宜。在在计算机中，可以用一个算机中，可以用一个线性表来表示性表来表示:P=(p0,p1,，p

48、n)一元多一元多项式式但是但是对于形如于形如S(x)=1+3x10000 2x20000的多的多项式，上述表示方法是否合适？式，上述表示方法是否合适？一般情况下的一元稀疏多一般情况下的一元稀疏多项式可写成式可写成 Pn(x)=p1xe1+p2xe2+pmxem其中：其中：pi 是指数是指数为ei 的的项的非零系数，的非零系数，0 e1 e2 em=n可以下列可以下列线性表表示：性表表示：（p1,e1）,(p2,e2),(pm,em)）P999(x)=7x3-2x12-8x999例如例如:可用可用线性表性表 (7,3),(-2,12),(-8,999)表示表示ADT Polynomial 数据数

49、据对象象：数据关系数据关系：抽象数据类型一元多项式的定义如下：抽象数据类型一元多项式的定义如下：D ai|ai TermSet,i=1,2,.,m,m0 TermSet 中的中的每个元素包含一个每个元素包含一个 表示系数的表示系数的实数和表示指数的整数数和表示指数的整数 R1|ai-1,ai D,i=2,.,n 且且ai-1中的指数中的指数值ai中的指数中的指数值 CreatPolyn(&P,m)DestroyPolyn(&P)PrintPolyn(&P)基本操作：基本操作：操作操作结果果：输入入 m 项的系数和指数，的系数和指数，建立一元多建立一元多项式式 P。初始条件初始条件：一元多：一元

50、多项式式 P 已存在。已存在。操作操作结果果：销毁一元多一元多项式式 P。初始条件初始条件：一元多：一元多项式式 P 已存在。已存在。操作操作结果果：打印：打印输出一元多出一元多项式式 P。PolynLength(P)AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)ADT Polynomial初始条件初始条件：一元多：一元多项式式 P 已存在。已存在。操作操作结果果：返回一元多：返回一元多项式式 P 中的中的项数。数。初始条件初始条件：一元多：一元多项式式 Pa 和和 Pb 已存在。已存在。操作操作结果果：完成多：完成多项式相加运算，即：式相加运算，即：Pa=Pa