1、第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 本章小结本章小结 2.5 2.5 有序表有序表 最新.课件12.1 2.1 线性表的基本概念线性表的基本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算最新.课件22.1.1 2.1.1 线性表的定义线性表的定义 线性表是具有相同特性的数据元素的一个有线性表是具有相同特性的数据元素的一个有限序列。限序列。该序列中所含元素的个数叫做线性表的该序列中所含
2、元素的个数叫做线性表的长度长度,用用n表示表示,n0。当当n=0时时,表示线性表是一个空表表示线性表是一个空表,即表中不包即表中不包含任何元素。设序列中第含任何元素。设序列中第i(i表示位序表示位序)个元素为个元素为ai(1in)。线性表的一般表示为线性表的一般表示为:(a1,a2,ai,ai+1,an)最新.课件3 其中其中a1为第一个元素为第一个元素,又称做表头元素又称做表头元素,a2为为第二个元素第二个元素,an为最后一个元素为最后一个元素,又称做表尾元又称做表尾元素。素。例如例如,在线性表在线性表 (1,4,3,2,8,10)中中,1为表头元素为表头元素,10为表尾元素。为表尾元素。最
3、新.课件42.1.2 2.1.2 线性表的运算线性表的运算 线性表的基本运算如下线性表的基本运算如下:(1)初始化线性表初始化线性表InitList(&L):构造一个空的线性构造一个空的线性表表L。(2)销毁线性表销毁线性表DestroyList(&L):释放线性表释放线性表L占用占用的内存空间。的内存空间。最新.课件5 (3)判线性表是否为空表判线性表是否为空表ListEmpty(L):若若L为空为空表表,则返回真则返回真,否则返回假。否则返回假。(4)求线性表的长度求线性表的长度ListLength(L):返回返回L中元素中元素个数。个数。(5)输出线性表输出线性表DispList(L):
4、当线性表当线性表L不为空时不为空时,顺序显示顺序显示L中各结点的值域。中各结点的值域。(6)求线性表求线性表L中指定位置的某个数据元素中指定位置的某个数据元素GetElem(L,i,&e):用用e返回返回L中第中第 i(1iListLength(L)个元素的值。个元素的值。最新.课件6 (7)定位查找定位查找LocateElem(L,e):返回返回L中第中第1个值域个值域与与e相等的位序。若这样的元素不存在相等的位序。若这样的元素不存在,则返回值为则返回值为0。(8)插入数据元素插入数据元素ListInsert(&L,i,e):在在L的第的第i(1iListLength(L)+1)个元素之前插
5、入新的元素个元素之前插入新的元素e,L的长度增的长度增1。(9)删除数据元素删除数据元素ListDelete(&L,i,&e):删除删除L的第的第i(1iListLength(L)个元素个元素,并用并用e返回其值返回其值,L的长度的长度减减1。最新.课件7 例例2.1 假设有两个集合假设有两个集合 A 和和 B 分别用两个线性分别用两个线性表表 LA 和和 LB 表示表示,即线性表中的数据元素即为集合即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合中的成员。编写一个算法求一个新的集合C=AB,即将两个集合的并集放在线性表即将两个集合的并集放在线性表LC中。中。解解:本算法思想是
6、本算法思想是:先初始化线性表先初始化线性表LC,将将LA的所的所有元素复制到有元素复制到LC中中,然后扫描线性表然后扫描线性表LB,若若LB的当的当前元素不在线性表前元素不在线性表LA中中,则将其插入到则将其插入到LC中。算法中。算法如下如下:最新.课件8void unionList(List LA,List LB,List&LC)int lena,lenc,i;ElemType e;InitList(LC);for(i=1;i=ListLength(LA);i+)/*将将LA的所有元素插入到的所有元素插入到Lc中中*/GetElem(LA,i,e);ListInsert(LC,i,e);le
7、na=ListLength(LA);/*求线性表的长度求线性表的长度*/lenB=ListLength(LB);最新.课件9for(i=1;i=lenb;i+)GetElem(LB,i,e);/*取取LB中第中第i个数据元素赋给个数据元素赋给e*/if (!LocateElem(LA,e)ListInsert(LC,+lenc,e);/*LA中不存在和中不存在和e相同者相同者,则插入到则插入到LC中中*/最新.课件10 由于由于LocateElem(LA,e)运算的时间复杂度为运算的时间复杂度为O(ListLength(LA),所以本算法的时间复杂度为所以本算法的时间复杂度为:O(ListLe
8、ngth(LA)*ListLength(LB)。最新.课件112.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表基本运算的实现顺序表基本运算的实现最新.课件122.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是线性表的顺序存储结构就是:把线性表中的所把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。器中指定存储位置开始的一块连续的存储空间中。这样这样,线性表中第一个元素的存储位置就是指线性
9、表中第一个元素的存储位置就是指定的存储位置定的存储位置,第第i+1个元素个元素(1in-1)的存储的存储位置位置紧接在第紧接在第i i个元素的存储位置的后面。个元素的存储位置的后面。线性表线性表 逻辑结构逻辑结构顺序顺序表表 存储结构存储结构最新.课件13 假定线性表的元素类型为假定线性表的元素类型为ElemType,则每个元则每个元素所占用存储空间大小素所占用存储空间大小(即字节数即字节数)为为sizeof(ElemType),整个线性表所占用存储空间的大整个线性表所占用存储空间的大小为小为:n*sizeof(ElemType)其中其中,n表示线性表的长度。表示线性表的长度。最新.课件14
10、a a1 1 LOC(A)0 a a2 2 LOC(A)+sizeof(ElemType)1 线性表存储空间线性表存储空间 存储地址存储地址 下标位置下标位置 a ai i LOC(A)+(i-1)*sizeof(ElemType)i-1 a an n LOC(A)+(n-1)*sizeof(ElemType)n-1 LOC(A)+(MaxSize-1)*sizeof(ElemType)MaxSize-1 顺序表示意图顺序表示意图最新.课件15 在定义一个线性表的顺序存储类型时在定义一个线性表的顺序存储类型时,需要定义需要定义一个数组来存储线线表中的所有元素和定义一个整一个数组来存储线线表中的
11、所有元素和定义一个整型变量来存储线性表的长度。型变量来存储线性表的长度。假定数组用假定数组用dataMaxSize表示表示,长度整型变量用长度整型变量用length表示表示,并采用结构体类型表示并采用结构体类型表示,则元素类型为通则元素类型为通用类型标识符用类型标识符ElemType的线性表的顺序存储类型可的线性表的顺序存储类型可描述如下描述如下:最新.课件16 typedef struct ElemType dataMaxSize;int length;SqList;/*顺序表类型顺序表类型*/其中其中,data成员存放元素成员存放元素,length成员存放线性表的成员存放线性表的实际长度。
12、实际长度。说明：由于说明：由于C/C+C/C+中数组的下标从中数组的下标从0 0开始，线性表的第开始，线性表的第i i个元素个元素a ai i存放顺序表的第存放顺序表的第i-1i-1位置上。为了清楚，将位置上。为了清楚，将a ai i在逻辑在逻辑序列中的位置称为序列中的位置称为逻辑位序逻辑位序，在顺序表中的位置称为，在顺序表中的位置称为物理位物理位序序。最新.课件172.2.2 2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构一旦采用顺序表存储结构,我们就可以用我们就可以用C/C+语言实现线性表的各种基本运算。为了方便语言实现线性表的各种基本运算。为了方便,假设假设
13、ElemType为为char类型类型,使用如下自定义类型语句使用如下自定义类型语句:typedef char ElemType;最新.课件181.建立顺序表建立顺序表其方法是将给定的含有其方法是将给定的含有n个元素的数组的个元素的数组的每个元素依次放入到顺序表中，并将每个元素依次放入到顺序表中，并将n赋给顺赋给顺序表的长度成员。算法如下：序表的长度成员。算法如下：void CreateList(SqList*&L,ElemType a,int n)/*建立顺序表建立顺序表*/int i;L=(SqList*)malloc(sizeof(SqList);for(i=0;idatai=ai;L-l
14、ength=n;最新.课件192.顺序表基本运算算法顺序表基本运算算法(1)初始化线性表初始化线性表InitList(L)该运算的结果是构造一个空的线性表该运算的结果是构造一个空的线性表L。实际上只。实际上只需将需将length成员设置为成员设置为0即可。即可。void InitList(SqList*&L)/引用型指针引用型指针 L=(SqList*)malloc(sizeof(SqList);/*分配存放线性表的空间分配存放线性表的空间*/L-length=0;本算法的时间复杂度为本算法的时间复杂度为O(1)。顺序表L最新.课件20 (2)销毁线性表销毁线性表DestroyList(L)该
15、运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。void DestroyList(SqList*&L)free(L);本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件21 (3)判定是否为空表判定是否为空表ListEmpty(L)该运算返回一个值表示该运算返回一个值表示L是否为空表。若是否为空表。若L为空为空表表,则返回则返回1,否则返回否则返回0。int ListEmpty(SqList*L)return(L-length=0);本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件22 (4)求线性表的长度求线性表的长度ListLength
16、(L)该运算返回顺序表该运算返回顺序表L的长度。实际上只需返回的长度。实际上只需返回length成员的值即可。成员的值即可。int ListLength(SqList*L)return(L-length);本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件23 (5)输出线性表输出线性表DispList(L)该运算当线性表该运算当线性表L不为空时不为空时,顺序显示顺序显示L中各元素的中各元素的值。值。void DispList(SqList*L)int i;if(ListEmpty(L)return;for(i=0;ilength;i+)printf(%c,L-datai);prin
17、tf(n);最新.课件24 本算法中基本运算为本算法中基本运算为for循环中的循环中的printf语句语句,故时间复杂度为故时间复杂度为:O(L-length)或或O(n)最新.课件25 (6)求某个数据元素值求某个数据元素值GetElem(L,i,e)该运算返回该运算返回L中第中第 i(1iListLength(L)个元素的值个元素的值,存放在存放在e中。中。int GetElem(SqList*L,int i,ElemType&e)if(iL-length)return 0;e=L-datai-1;return 1;本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件26 (7)按
18、元素值查找按元素值查找LocateElem(L,e)该运算顺序查找第该运算顺序查找第1个值域与个值域与e相等的元素的位序。相等的元素的位序。若这样的元素不存在若这样的元素不存在,则返回值为则返回值为0。int LocateElem(SqList*L,ElemType e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;else return i+1;最新.课件27 本算法中基本运算为本算法中基本运算为while循环中的循环中的i+语句语句,故时故时间复杂度为间复杂度为:O(L-length)或或O(n)最新.课件28 (8)
19、插入数据元素插入数据元素ListInsert(L,i,e)该 运 算 在 顺 序 表该 运 算 在 顺 序 表 L 的 第的 第 i 个 位 置个 位 置(1iListLength(L)+1)上插入新的元素上插入新的元素e。思路：如果思路：如果i值不正确值不正确,则显示相应错误信息；则显示相应错误信息；否则将顺序表原来第否则将顺序表原来第i个元素及以后元素均后移个元素及以后元素均后移一个位置一个位置,腾出一个空位置插入新元素腾出一个空位置插入新元素,顺序表长顺序表长度增度增1。最新.课件29 int ListInsert(SqList*&L,int i,ElemType e)int j;if(
20、iL-length+1)return 0;i-;/*将顺序表将顺序表逻辑位序逻辑位序转化为转化为elem下标即下标即物理位序物理位序*/for(j=L-length;ji;j-)L-dataj=L-dataj-1;/*将将datai及后面元素后移一个位置及后面元素后移一个位置*/L-datai=e;L-length+;/*顺序表长度增顺序表长度增1*/return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 最新.课件30 对于本算法来说对于本算法来说,元素移动的次数不仅与表长元素移动的次数不仅与表长L.length=n有关有关,而且与插入位置而且与插入位置
21、i有关有关:当当i=n+1时时,移移动次数为动次数为0；当；当i=1时时,移动次数为移动次数为n,达到最大值。在达到最大值。在线性表线性表sq中共有中共有n+1个可以插入元素的地方。假设个可以插入元素的地方。假设pi(=)是在第是在第i个位置上插入一个元素的概率个位置上插入一个元素的概率,则在则在长度为长度为n的线性表中插入一个元素时所需移动元素的线性表中插入一个元素时所需移动元素的平均次数为的平均次数为:因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。11n)(2)1(11)1(1111nOninninniniip 最新.课件31 (9)删除数据元素删除数据元素List
22、Delete(L,i,e)删除顺序表删除顺序表L中的第中的第i(1iListLength(L)个元个元素。素。思路：如果思路：如果i值不正确值不正确,则显示相应错误信息；则显示相应错误信息；否则将线性表第否则将线性表第i个元素以后元素均向前移动一个个元素以后元素均向前移动一个位置位置,这样覆盖了原来的第这样覆盖了原来的第i个元素个元素,达到删除该元达到删除该元素的目的素的目的,最后顺序表长度减最后顺序表长度减1。最新.课件32int ListDelete(SqList*&L,int i,ElemType&e)int j;if(iL-length)return 0;i-;/*将顺序表逻辑位序转化
23、为将顺序表逻辑位序转化为elem下标即物理位序下标即物理位序*/e=L-datai;for(j=i;jlength-1;j+)L-dataj=L-dataj+1;/*将将datai之后的元素后前移一个位置之后的元素后前移一个位置*/L-length-;/*顺序表长度减顺序表长度减1*/return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 最新.课件33 对于本算法来说对于本算法来说,元素移动的次数也与表长元素移动的次数也与表长n和和删除元素的位置删除元素的位置i有关有关:当当i=n时时,移动次数为移动次数为0；当；当i=1时时,移动次数为移动次数为n-1
24、。在线性表。在线性表sq中共有中共有n个元素可以个元素可以被删除。假设被删除。假设pi(pi=)是删除第是删除第i个位置上元素的概个位置上元素的概率率,则在长度为则在长度为n的线性表中删除一个元素时所需移的线性表中删除一个元素时所需移动元素的平均次数为动元素的平均次数为:=因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。)(21)(1)(11nOninninpninii n1最新.课件34 例例2.2 设计一个算法设计一个算法,将将x插入到一个有序插入到一个有序(从小到大排序从小到大排序)的线性表的线性表(顺序存储结构即顺序顺序存储结构即顺序表表)的适当位置上的适当位置上
25、,并保持线性表的有序性。并保持线性表的有序性。解解:先通过比较在顺序表先通过比较在顺序表L中找到存放中找到存放x的位的位置置i,然后将然后将x插入到插入到L.datai中中,最后将顺序表的最后将顺序表的长度增长度增1。最新.课件35 void Insert(SqList*&L,ElemType x)int i=0,j;while(ilength&L-datailength-1;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;查找插入位置查找插入位置元素后移一个位置元素后移一个位置a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize
26、 最新.课件36 例例2.3 设计一个算法设计一个算法,将两个元素有序将两个元素有序(从从小到大小到大)的顺序表合并成一个有序顺序表。的顺序表合并成一个有序顺序表。求解思路求解思路:将两个顺序表进行二路归并。将两个顺序表进行二路归并。最新.课件37归并到顺序表归并到顺序表r中中 k记录记录r中元素个数中元素个数 1(i=0)2(j=0)将将1(i=1)插入插入r(k=1)3(i=1)2(j=0)将将2(j=1)插入插入r(k=2)3(i=1)4(j=1)将将3(i=2)插入插入r(k=3)5(i=2)4(j=1)将将4(j=2)插入插入r(k=4)5(i=2)10(j=2)将将5(j=3)插入
27、插入r(k=5)将将q中余下元素插入中余下元素插入r中。中。顺序表顺序表p：135i顺序表顺序表q：241020j顺序表顺序表r：1k最新.课件38SqList*merge(SqList *p,SqList *q)SqList*r;int i=0,j=0,k=0;r=(SqList*)malloc(sizeof(SqList);while(ilength&jlength)if(p-datai dataj)r-datak=p-datai;i+;k+;else r-datak=q-dataj;j+;k+;最新.课件39while(ilength)r-datak=p-datai;i+;k+;whil
28、e(jlength)r-datak=q-dataj;j+;k+;r-length=k;/*或或p-length+q-length*/return(r);最新.课件40 例例2.4 已知长度为已知长度为n的线性表的线性表A采用顺序存储结采用顺序存储结构构,编写一个时间复杂度为编写一个时间复杂度为O(n)、空间复杂度为、空间复杂度为O(1)的算法的算法,该算法删除线性表中所有值为该算法删除线性表中所有值为item的数据元的数据元素。素。解解:用用k记录顺序表记录顺序表A中等于中等于item的元素个数的元素个数,边边扫描扫描A边统计边统计k,并将不为并将不为item的元素前移的元素前移k个位置个位置
29、,最最后修改后修改A的长度。对应的算法如下的长度。对应的算法如下:最新.课件41void delnode1(SqList&A,ElemType item)int k=0,i;/*k记录值不等于记录值不等于item的元素个数的元素个数*/for (i=0;iA.length;i+)if(A.datai!=item)A.datak=A.datai;k+;/*不等于不等于item的元素增的元素增1*/A.length=k;/*顺序表顺序表A的长度等于的长度等于k*/算法算法1：类似于：类似于建顺序表建顺序表最新.课件42void delnode2(SqList&A,ElemType item)int
30、 k=0,i=0;/*k记录值等于记录值等于item的元素个数的元素个数*/while(inext=NULL;for(i=0;idata=ai;s-next=L-next;/*将将*s插在原开始结点之前插在原开始结点之前,头结点之后头结点之后*/L-next=s;最新.课件55adc bi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步:建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点
31、,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点,插入到头结点之后插入到头结点之后最新.课件56 (2)尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单,但生成的链表但生成的链表中结点的次序和原数组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上,为此必须增加一为此必须增加一个尾指针个尾指针r,r,
32、使其始终指向当前链表的尾结点。采使其始终指向当前链表的尾结点。采用尾插法建表的算法如下用尾插法建表的算法如下:最新.课件57 void CreateListR(LinkList*&L,ElemType a,int n)LinkList*s,*r;int i;L=(LinkList*)malloc(sizeof(LinkList);/*创建头结点创建头结点*/r=L;/*r始终指向终端结点始终指向终端结点,开始时指向头结点开始时指向头结点*/for(i=0;idata=ai;r-next=s;/*将将*s插入插入*r之后之后*/r=s;r-next=NULL;/*终端结点终端结点next域置为域
33、置为NULL*/最新.课件58bcdai=0 i=1 i=2 i=3head头结点头结点adcbb采用尾插法建立单链表的过程采用尾插法建立单链表的过程最新.课件592.插入结点运算插入结点运算 插入运算是将值为插入运算是将值为x的新结点插入到单链表的新结点插入到单链表的第的第i个结点的位置上。先在单链表中找到第个结点的位置上。先在单链表中找到第i-1个结点个结点,再在其后插入新结点。再在其后插入新结点。单链表插入结点的过程如下图所示。单链表插入结点的过程如下图所示。最新.课件60插入结点示意图插入结点示意图最新.课件61 3.删除结点运算删除结点运算 删除运算是将单链表的第删除运算是将单链表的
34、第i个结点删去。先在单个结点删去。先在单链表中找到第链表中找到第i-1个结点个结点,再删除其后的结点。删除再删除其后的结点。删除单链表结点的过程如下图所示。单链表结点的过程如下图所示。最新.课件62删除结点示意图删除结点示意图最新.课件63 4.线性表基本运算实现线性表基本运算实现 (1)初始化线性表初始化线性表InitList(L)该运算建立一个空的单链表该运算建立一个空的单链表,即创建一个头结点。即创建一个头结点。void InitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/*创建头结点创建头结点*/L-next=NULL;
35、最新.课件64 (2)销毁线性表销毁线性表DestroyList(L)释放单链表释放单链表L占用的内存空间。即逐一释放全部结点占用的内存空间。即逐一释放全部结点的空间。的空间。void DestroyList(LinkList*&L)LinkList*p=L,*q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);最新.课件65 (3)判线性表是否为空表判线性表是否为空表ListEmpty(L)若单链表若单链表L没有数据结点没有数据结点,则返回真则返回真,否则返回假。否则返回假。int ListEmpty(LinkList*L)return(L
36、-next=NULL);最新.课件66 (4)求线性表的长度求线性表的长度ListLength(L)返回单链表返回单链表L中数据结点的个数。中数据结点的个数。int ListLength(LinkList*L)LinkList*p=L;int i=0;while(p-next!=NULL)i+;p=p-next;return(i);最新.课件67 (5)输出线性表输出线性表DispList(L)逐一扫描单链表逐一扫描单链表L的每个数据结点的每个数据结点,并显示各结点并显示各结点的的data域值。域值。void DispList(LinkList*L)LinkList*p=L-next;whil
37、e(p!=NULL)printf(%c,p-data);p=p-next;printf(n);最新.课件68 (6)求线性表求线性表L中指定位置的某 个 数 据 元 素中指定位置的某 个 数 据 元 素GetElem(L,i,&e)思路：在单链表思路：在单链表L中从头开始找到第中从头开始找到第 i个结点个结点,若若存在第存在第i个数据结点个数据结点,则将其则将其data域值赋给变量域值赋给变量e。最新.课件69 int GetElem(LinkList*L,int i,ElemType&e)int j=0;LinkList*p=L;while(jnext;if(p=NULL)return 0;
38、/*不存在第不存在第i个数据结点个数据结点*/else /*存在第存在第i个数据结点个数据结点*/e=p-data;return 1;最新.课件70 (7)按元素值查找按元素值查找LocateElem(L,e)思路：在单链表思路：在单链表L中从头开始找第中从头开始找第1个值域与个值域与e相等的相等的结点结点,若存在这样的结点若存在这样的结点,则返回位置则返回位置,否则返回否则返回0。int LocateElem(LinkList*L,ElemType e)LinkList*p=L-next;int n=1;while(p!=NULL&p-data!=e)p=p-next;n+;if(p=NUL
39、L)return(0);else return(n);最新.课件71 (8)插入数据元素插入数据元素ListInsert(&L,i,e)思路：先在单链表思路：先在单链表L中找到第中找到第i-1个结点个结点*p,若存在这若存在这样的结点样的结点,将值为将值为e的结点的结点*s插入到其后。插入到其后。int ListInsert(LinkList*&L,int i,ElemType e)int j=0;LinkList*p=L,*s;while(jnext;最新.课件72if(p=NULL)return 0;/*未找到位序为未找到位序为i-1的结点的结点*/else/*找到位序为找到位序为i-1的
40、结点的结点*p*/s=(LinkList*)malloc(sizeof(LinkList);/*创建新结点创建新结点*s*/s-data=e;s-next=p-next;/*将将*s插入到插入到*p之后之后*/p-next=s;return 1;最新.课件73 (9)删除数据元素删除数据元素ListDelete(&L,i,&e)思路：思路：先在单链表先在单链表L L中找到第中找到第i-1i-1个结点个结点*p,p,若存在这若存在这样的结点样的结点,且也存在后继结点且也存在后继结点,则删除该后继结点。则删除该后继结点。int ListDelete(LinkList*&L,int i,ElemTy
41、pe&e)int j=0;LinkList*p=L,*q;while(jnext;最新.课件74if(p=NULL)return 0;/*未找到位序为未找到位序为i-1的结点的结点*/else/*找到位序为找到位序为i-1的结点的结点*p*/q=p-next;/*q指向要删除的结点指向要删除的结点*/if(q=NULL)return 0;/*若不存在第若不存在第i个结点个结点,返回返回0*/p-next=q-next;/*从单链表中删除从单链表中删除*q结点结点*/free(q);/*释放释放*q结点结点*/return 1;最新.课件75 例例2.5 设设C=a1,b1,a2,b2,an,b
42、n为一线性表为一线性表,采用带头结点的采用带头结点的hc单链表存放单链表存放,编写一个算法编写一个算法,将将其拆分为两个线性表其拆分为两个线性表,使得使得:A=a1,a2,an,B=b1,b2,bn 最新.课件76 解解:设拆分后的两个线性表都用带头结点的单链表设拆分后的两个线性表都用带头结点的单链表存放。存放。先建立两个头结点先建立两个头结点*ha和和*hb,它们用于存放拆分后它们用于存放拆分后的线性表的线性表A和和B,ra和和rb分别指向这两个单链表的表尾分别指向这两个单链表的表尾,用用p指针扫描单链表指针扫描单链表hc,将当前结点将当前结点*p链到链到ha未尾未尾,p沿沿next域下移一
43、个结点域下移一个结点,若不为空若不为空,则当前结点则当前结点*p链到链到hb未未尾尾,p沿沿next域下移一个结点域下移一个结点,如此这样如此这样,直到直到p为空。最为空。最后将两个尾结点的后将两个尾结点的next域置空。域置空。对应算法如下对应算法如下:最新.课件77 void fun(LinkList*hc,LinkList*&ha,LinkList*&hb)LinkList*p=hc-next,*ra,*rb;ha=hc;/*ha的头结点利用的头结点利用hc的头结点的头结点*/ra=ha;/*ra始终指向始终指向ha的末尾结点的末尾结点*/hb=(LinkList*)malloc(siz
44、eof(LinkList);/*创建创建hb头结点头结点*/rb=hb;/*rb始终指向始终指向hb的末尾结点的末尾结点*/最新.课件78 while(p!=NULL)ra-next=p;ra=p;/*将将*p链到链到ha单链表未尾单链表未尾*/p=p-next;if(p!=NULL)rb-next=p;rb=p;/*将将*p链到链到hb单链表未尾单链表未尾*/p=p-next;ra-next=rb-next=NULL;/*两个尾结点的两个尾结点的next域置空域置空*/最新.课件79 本算法实际上是采用尾插法建立两个新表。本算法实际上是采用尾插法建立两个新表。所以所以,尾插法建表算法是很多类
45、似习题的基础！尾插法建表算法是很多类似习题的基础！最新.课件80 例例2.6 有一个带头结点的单链表有一个带头结点的单链表head,其其ElemType类型为类型为char,设计一个算法使其元素递增设计一个算法使其元素递增有序。有序。解解:若原单链表中有一个或以上的数据结点若原单链表中有一个或以上的数据结点,先构造只含一个数据结点的有序表先构造只含一个数据结点的有序表(只含一个数只含一个数据结点的单链表一定是有序表据结点的单链表一定是有序表)。扫描原单链表。扫描原单链表余下的结点余下的结点*p(p(直到直到p=NULLp=NULL为止为止),),在有序表中通在有序表中通过比较找插入过比较找插入
46、*p p的前驱结点的前驱结点*q,q,然后将然后将*p p插入到插入到*q q之后之后(这里实际上采用的是直接插入排序方法这里实际上采用的是直接插入排序方法)。最新.课件81 void Sort(LinkList*&head)LinkList*p=head-next,*q,*r;if(p!=NULL)/*head有一个或以上的数据结点有一个或以上的数据结点*/r=p-next;/*r保存保存*p结点后继结点的指针结点后继结点的指针*/p-next=NULL;/*构造只含一个数据结点的有序表构造只含一个数据结点的有序表*/p=r;while(p!=NULL)r=p-next;/*r保存保存*p结
47、点后继结点的指针结点后继结点的指针*/最新.课件82 q=head;while(q-next!=NULL&q-next-datadata)q=q-next;/*在有序表中找插入在有序表中找插入*p的前驱结点的前驱结点*q*/p-next=q-next;/*将将*p插入到插入到*q之后之后*/q-next=p;p=r;/*扫描原单链表余下的结点扫描原单链表余下的结点*/最新.课件832.3.3 2.3.3 双链表双链表 对于双链表对于双链表,采用类似于单链表的类型定义采用类似于单链表的类型定义,其其DLinkList类型的定义如下类型的定义如下:typedef struct DNode /*定义
48、双链表结点类型定义双链表结点类型*/ElemType data;struct DNode*prior;/*指向前驱结点指向前驱结点*/struct DNode*next;/*指向后继结点指向后继结点*/DLinkList;最新.课件84 在双链表中在双链表中,有些操作如求长度、取元素值和有些操作如求长度、取元素值和查找元素等操作算法与单链表中相应算法是相同的查找元素等操作算法与单链表中相应算法是相同的,这里不多讨论。但在单链表中这里不多讨论。但在单链表中,进行结点插入和删除进行结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链时涉及到前后结点的一个指针域的变化。而在双链表中表中,结点的
49、插入和删除操作涉及到前后结点的两个结点的插入和删除操作涉及到前后结点的两个指针域的变化。指针域的变化。最新.课件85双链表中插入结点示意图双链表中插入结点示意图最新.课件86 归纳起来归纳起来,在双链表中在双链表中p所指的结点之后插入所指的结点之后插入一个一个*s结点。其操作语句描述为结点。其操作语句描述为:s-next=p-next;/*将将*s插入到插入到*p之后之后*/p-next-prior=s;s-prior=p;p-next=s;最新.课件87删除结点示意图删除结点示意图 在 双 链 表在 双 链 表中删除一个中删除一个结点的过程结点的过程如右图所示如右图所示:最新.课件88 归纳
50、起来归纳起来,删除双链表删除双链表L L中中*p p结点的后续结点。结点的后续结点。其操作语句描述为其操作语句描述为:p-next=q-next;q-next-prior=p;最新.课件892.3.4 2.3.4 循环链表循环链表 循环链表循环链表是另一种形式的链式存储结构。它的是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空特点是表中最后一个结点的指针域不再是空,而是而是指向表头结点指向表头结点,整个链表形成一个环。由此整个链表形成一个环。由此,从表中从表中任一结点出发均可找到链表中其他结点。任一结点出发均可找到链表中其他结点。最新.课件90 带头结点的循环单链表和循环
