数据结构线性表PPT

数据结构线性表PPT第1页，共108页。2.1 2.1 线性表的根本概念线性表的根本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算第2页，共108页。2.1.1 2.1.1 线性表的定义线性表的定义 线性表是具有一样特性的数据元素的一线性表是具有一样特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线个有限序列。该序列中所含元素的个数叫做线性表的长度性表的长度,用用n n表示表示,n0,n0。当当n=0n=0时时,表示线性表是一个空表表示线性表是一个空表,即表即表中不包含任何元素。设序列中第中不包含任何元素。设序列中第i(ii(i表示位序表示位序)个元素为个元素为ai(1in)ai(1in)。线性表的一般表示为线性表的一般表示为:(a1,a2,ai,ai+1,an)(a1,a2,ai,ai+1,an)第3页，共108页。其其中中a1为为第第一一个个元元素素,又又称称做做表表头头元元素素,a2为为第第二二个元素个元素,an为最后一个元素为最后一个元素,又称做表尾元素。又称做表尾元素。例如例如,在线性表在线性表 (1,4,3,2,8,10)中中,1为表头元素为表头元素,10为表尾元素。为表尾元素。第4页，共108页。2.1.2 2.1.2 线性表的运算线性表的运算 线性表的根本运算如下线性表的根本运算如下:(1)(1)初始化线性表初始化线性表InitList(&L):InitList(&L):构造一个空的构造一个空的线性表线性表L L。(2)(2)销毁线性表销毁线性表DestroyList(&L):DestroyList(&L):释放线性表释放线性表L L占用的内存空间。占用的内存空间。第5页，共108页。(3)判判线线性性表表是是否否为为空空表表ListEmpty(L):假假设设L为空表为空表,那么返回真那么返回真,否那么返回假。否那么返回假。(4)求求线线性性表表的的长长度度ListLength(L):返返回回L中元素个数。中元素个数。(5)输输出出线线性性表表DispList(L):当当线线性性表表L不为空时不为空时,顺序显示顺序显示L中各结点的值域。中各结点的值域。(6)求求线线性性表表L中中指指定定位位置置的的某某个个数数据据元元 素素 GetElem(L,i,&e):用用 e返返 回回 L中中 第第 i(1iListLength(L)个元素的值。个元素的值。第6页，共108页。(7)(7)定定位位查查找找LocateElem(L,e):LocateElem(L,e):返返回回L L中中第第1 1个个值值域域与与e e相相等等的的位位序序。假假设设这这样样的的元元素素不存在不存在,那么返回值为那么返回值为0 0。(8)(8)插插入入数数据据元元素素ListInsert(&L,i,e):ListInsert(&L,i,e):在在L L的的第第i(1iListLength(L)+1)i(1iListLength(L)+1)个个元元素素之之前前插插入入新的元素新的元素e,Le,L的长度增的长度增1 1。(9)(9)删删除除数数据据元元素素ListDelete(&L,i,&e):ListDelete(&L,i,&e):删删除除L L的的第第i(1iListLength(L)i(1iListLength(L)个个元元素素,并并用用e e返返回回其值其值,L,L的长度减的长度减1 1。第7页，共108页。假假设设有有两两个个集集合合 A A 和和 B B 分分别别用用两两个个线线性性表表 LA LA 和和 LB LB 表表示示,即即线线性性表表中中的的数数据据元元素素即即为为集集合合中中的的成成员员。编编写写一一个个算算法法求求一一个个新新的的集集合合C=AB,C=AB,即即将将两两个个集集合的并集放在线性表合的并集放在线性表LCLC中。中。解解:本本算算法法思思想想是是:先先初初始始化化线线性性表表LC,LC,将将LALA的的所所有有元元素素复复制制到到LCLC中中,然然后后扫扫描描线线性性表表LB,LB,假假设设LBLB的的当当前前元元素素不不在在线线性性表表LALA中中,那那么么将将其其插插入入到到LCLC中中。算算法法如如下下:第8页，共108页。void 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);lena=ListLength(LA);/*求线性表的长度求线性表的长度*/lenB=ListLength(LB);第9页，共108页。for(i=1;i=lenb;i+)GetElem(LB,i,e);/*取LB中第i个数据元素赋给e*/if (!LocateElem(LA,e)ListInsert(LC,+lenc,e);/*LA中不存在和e一样者,那么插入到LC中*/第10页，共108页。由由 于于 LocateElem(LA,e)运运 算算 的的 时时 间间 复复 杂杂 度度 为为O(ListLength(LA),所以本算法的时间复杂度为所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB)。第11页，共108页。2.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表根本运算的实现顺序表根本运算的实现第12页，共108页。2.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储构造就是线性表的顺序存储构造就是:把线性表中的所有把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开场的一块连续的存储空间中。指定存储位置开场的一块连续的存储空间中。这样这样,线性表中第一个元素的存储位置就是指定线性表中第一个元素的存储位置就是指定的存储位置的存储位置,第第i+1i+1个元素个元素(1in-1)(1in-1)的存储位置紧接的存储位置紧接在第在第i i个元素的存储位置的后面。个元素的存储位置的后面。线性表线性表 逻辑构造逻辑构造顺序表顺序表 存储构造存储构造第13页，共108页。假定线性表的元素类型为假定线性表的元素类型为ElemType,ElemType,那么每个元素所占用存储空间大小那么每个元素所占用存储空间大小(即字即字节数节数)为为sizeof(ElemType),sizeof(ElemType),整个线性表所整个线性表所占用存储空间的大小为占用存储空间的大小为:n*sizeof(ElemType)n*sizeof(ElemType)其中其中,n,n表示线性表的长度。表示线性表的长度。第14页，共108页。顺序表示意图顺序表示意图第15页，共108页。在在定定义义一一个个线线性性表表的的顺顺序序存存储储类类型型时时,需需要要定定义义一一个个数数组组来来存存储储线线线线表表中中的的所所有有元元素素和和定定义义一一个个整整型变量来存储线性表的长度。型变量来存储线性表的长度。假假定定数数组组用用dataMaxSizedataMaxSize表表示示,长长度度整整型型变变量量用用lengthlength表表示示,并并采采用用构构造造体体类类型型表表示示,那那么么元元素素类类型型为为通通用用类类型型标标识识符符ElemTypeElemType的的线线性性表表的顺序存储类型可描述如下的顺序存储类型可描述如下:第16页，共108页。typedef struct ElemType dataMaxSize;int length;SqList;/*顺顺序表序表类类型型*/其其中中,data成成员员存存放放元元素素,length成成员员存存放放线线性性表表的的实实际际长长度。度。说说明明：由由于于C/C+中中数数组组的的下下标标从从0开开场场，线线性性表表的的第第i个个元元素素ai存存放放顺顺序序表表的的第第i-1位位置置上上。为为了了清清楚楚，将将ai在在逻逻辑辑序序列列中中的的位位置置称称为为逻逻辑辑位位序序，在在顺顺序序表表中中的的位位置称置称为为物理位序。物理位序。第17页，共108页。2.2.2 2.2.2 顺序表根本运算的实现顺序表根本运算的实现 一旦采用顺序表存储构造一旦采用顺序表存储构造,我们就可我们就可以用以用C/C+C/C+语言实现线性表的各种根本语言实现线性表的各种根本运算。为了方便运算。为了方便,假设假设ElemTypeElemType为为charchar类型类型,使用如下自定义类型语句使用如下自定义类型语句:typedef char ElemType;typedef char ElemType;第18页，共108页。1.建立顺序表建立顺序表其方法是将给定的含有其方法是将给定的含有n个元素的数组的每个元素的数组的每个元素依次放入到顺序表中，并将个元素依次放入到顺序表中，并将n赋给顺序表赋给顺序表的长度成员。算法如下：的长度成员。算法如下：void CreateList(SqList*&L,ElemType a,int n)/*建立顺序表建立顺序表*/int i;L=(SqList*)malloc(sizeof(SqList);for(i=0;idatai=ai;L-length=n;第19页，共108页。2.顺序表根本运算算法顺序表根本运算算法(1)初始化线性表初始化线性表InitList(L)该运算的结果是构造一个空的线性表该运算的结果是构造一个空的线性表L。实际上只需。实际上只需将将length成员设置为成员设置为0即可。即可。void InitList(SqList*&L)/引用型指针引用型指针 L=(SqList*)malloc(sizeof(SqList);/*分配存放线性表的空间分配存放线性表的空间*/L-length=0;本算法的时间复杂度为本算法的时间复杂度为O(1)。顺序表L第20页，共108页。(2)销毁线性表销毁线性表DestroyList(L)该运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。void DestroyList(SqList*&L)free(L);本算法的时间复杂度为本算法的时间复杂度为O(1)。第21页，共108页。(3)判定是否为空表判定是否为空表ListEmpty(L)该该运运算算返返回回一一个个值值表表示示L是是否否为为空空表表。假假设设L为为空空表表,那么返回那么返回1,否那么返回否那么返回0。int ListEmpty(SqList*L)return(L-length=0);本算法的时间复杂度为本算法的时间复杂度为O(1)。第22页，共108页。(4)求线性表的长度求线性表的长度ListLength(L)该该运运算算返返回回顺顺序序表表L的的长长度度。实实际际上上只只需需返返回回length成成员员的值即可。的值即可。int ListLength(SqList*L)return(L-length);本算法的时间复杂度为本算法的时间复杂度为O(1)。第23页，共108页。(5)输出线性表输出线性表DispList(L)该运算当线性表该运算当线性表L不为空时不为空时,顺序显示顺序显示L中各元素的值。中各元素的值。void DispList(SqList*L)int i;if(ListEmpty(L)return;for(i=0;ilength;i+)printf(%c,L-datai);printf(n);第24页，共108页。本本算算法法中中根根本本运运算算为为forfor循循环环中中的的printfprintf语句语句,故时间复杂度为故时间复杂度为:O(L-length)O(L-length)或或O(n)O(n)第25页，共108页。(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页，共108页。(7)按元素值查找按元素值查找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页，共108页。本本算算法法中中根根本本运运算算为为while循循环环中中的的i+语语句句,故故时时间复杂度为间复杂度为:O(L-length)或或O(n)第28页，共108页。(8)插入数据元素插入数据元素ListInsert(L,i,e)该该运运算算在在顺顺序序表表L的的第第i个个位位置置(1iListLength(L)+1)上插入新的元素上插入新的元素e。思思路路：如如果果i值值不不正正确确,那那么么显显示示相相应应错错误误信信息息；否否那那么么将将顺顺序序表表原原来来第第i个个元元素素及及以以后后元元素素均均后后移移一一个个位位置置,腾出一个空位置插入新元素腾出一个空位置插入新元素,顺序表长度增顺序表长度增1。第29页，共108页。int ListInsert(SqList*&L,int i,ElemType e)int j;if(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页，共108页。对于本算法来说对于本算法来说,元素移动的次数不仅与元素移动的次数不仅与表长表长L.length=n有关有关,而且与插入位置而且与插入位置i有关有关:当当i=n+1时时,移动次数为移动次数为0；当；当i=1时时,移动次数为移动次数为n,到达最大值。在线性表到达最大值。在线性表sq中共有中共有n+1个可以插个可以插入元素的地方。假设入元素的地方。假设pi(=)是在第是在第i个位置个位置上插入一个元素的概率上插入一个元素的概率,那么在长度为那么在长度为n的线的线性表中插入一个元素时所需移动元素的平均性表中插入一个元素时所需移动元素的平均次数为次数为:因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。第31页，共108页。(9)删除数据元素删除数据元素ListDelete(L,i,e)删除顺序表删除顺序表L中的第中的第i(1iListLength(L)个元素。个元素。思思路路：如如果果i值值不不正正确确,那那么么显显示示相相应应错错误误信信息息；否否那那么么将将线线性性表表第第i个个元元素素以以后后元元素素均均向向前前移移动动一一个个位位置置,这这样样覆覆盖盖了了原原来来的的第第i个个元元素素,到到达达删删除除该该元元素素的目的的目的,最后顺序表长度减最后顺序表长度减1。第32页，共108页。int ListDelete(SqList*&L,int i,ElemType&e)int j;if(iL-length)return 0;i-;/*将顺序表逻辑位序转化为将顺序表逻辑位序转化为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页，共108页。对于本算法来说对于本算法来说,元素移动的次数也与表元素移动的次数也与表长长n n和删除元素的位置和删除元素的位置i i有关有关:当当i=ni=n时时,移动移动次数为次数为0 0；当；当i=1i=1时时,移动次数为移动次数为n-1n-1。在线性。在线性表表sqsq中共有中共有n n个元素可以被删除。假设个元素可以被删除。假设pi(pi=)pi(pi=)是删除第是删除第i i个位置上元素的概个位置上元素的概率率,那么在长度为那么在长度为n n的线性表中删除一个元素的线性表中删除一个元素时所需移动元素的平均次数为时所需移动元素的平均次数为:=因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)O(n)。第34页，共108页。设设计计一一个个算算法法,将将x x插插入入到到一一个个有有序序(从从小小到到大大排排序序)的的线线性性表表(顺顺序序存存储储构构造造即即顺顺序序表表)的的适适当当位位置置上上,并并保保持持线线性性表的有序性。表的有序性。解解:先先通通过过比比较较在在顺顺序序表表L L中中找找到到存存放放x x的的位位置置i,i,然然后后将将x x插插入入到到L.dataiL.datai中中,最后将顺序表的长度增最后将顺序表的长度增1 1。第35页，共108页。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 第36页，共108页。设设计计一一个个算算法法,将将两两个个元元素素有有序序(从从小小到到大大)的的顺顺序序表表合合并并成一个有序顺序表。成一个有序顺序表。求解思路求解思路:将两个顺序表进展二路归并。将两个顺序表进展二路归并。第37页，共108页。归并到顺序表归并到顺序表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)插入插入r(k=5)将将q中余下元素插入中余下元素插入r中。中。顺序表顺序表p：135i顺序表顺序表q：241020j顺序表顺序表r：1k第38页，共108页。SqList*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+;第39页，共108页。while(ilength)r-datak=p-datai;i+;k+;while(jlength)r-datak=q-dataj;j+;k+;r-length=k;/*或或p-length+q-length*/return(r);第40页，共108页。长长度度为为n的的线线性性表表A采采用用顺顺序序存存储储构构造造,编编写写一一个个时时间间复复杂杂度度为为O(n)、空空间间复复杂杂度度为为O(1)的的算算法法,该算法删除线性表中所有值为该算法删除线性表中所有值为item的数据元素。的数据元素。解解:用用k记记录录顺顺序序表表A中中等等于于item的的元元素素个个数数,边边扫扫描描A边边统统计计k,并并将将不不为为item的的元元素素前前移移k个个位置位置,最后修改最后修改A的长度。对应的算法如下的长度。对应的算法如下:第41页，共108页。void 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：类似于：类似于建顺序表建顺序表第42页，共108页。void delnode2(SqList&A,ElemType item)int k=0,i=0;/*k记录值等于记录值等于item的元素个数的元素个数*/while(inext=NULL;for(i=0;idata=ai;s-next=L-next;/*将将*s插在原开场结点之前插在原开场结点之前,头结点之后头结点之后*/L-next=s;第55页，共108页。adc bi=0i=1i=2 i=3 head采用头插法建立单链表的过程采用头插法建立单链表的过程heada headda headcda headbcda 第第1 1步步:建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点,插入到头结点之后插入到头结点之后第56页，共108页。(2)尾插法建表尾插法建表 头头插插法法建建立立链链表表虽虽然然算算法法简简单单,但但生生成成的的链链表表中中结结点点的的次次序序和和原原数数组组元元素素的的顺顺序序相相反反。假假设设希希望望两两者者次次序序一一致致,可可采采用用尾尾插插法法建建立立。该该方方法法是是将将新新结结点点插插到到当当前前链链表表的的表表尾尾上上,为为此此必必须须增增加加一一个个尾尾指指针针r,使使其其始始终终指指向向当当前前链链表表的的尾尾结结点点。采采用用尾尾插插法法建建表表的的算算法如下法如下:第57页，共108页。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域置为域置为NULL*/第58页，共108页。bcdai=0i=1 i=2 i=3head头结点头结点adcb b采用尾插法建立单链表的过程采用尾插法建立单链表的过程第59页，共108页。2.插入结点运算插入结点运算 插插入入运运算算是是将将值值为为x的的新新结结点点插插入入到到单单链链表表的的第第i个个结结点点的的位位置置上上。先先在在单单链链表表中中找找到到第第i-1个个结结点点,再在其后插入新结点。再在其后插入新结点。单链表插入结点的过程如以下图所示。单链表插入结点的过程如以下图所示。第60页，共108页。插入结点示意图插入结点示意图第61页，共108页。3.删除结点运算删除结点运算 删删除除运运算算是是将将单单链链表表的的第第i个个结结点点删删去去。先先在在单单链链表表中中找找到到第第i-1个个结结点点,再再删删除除其其后后的的结结点点。删删除除单单链链表表结结点点的的过程如以下图所示。过程如以下图所示。第62页，共108页。删除结点示意图删除结点示意图第63页，共108页。4.线性表根本运算实现线性表根本运算实现 (1)初始化线性表初始化线性表InitList(L)该运算建立一个空的单链表该运算建立一个空的单链表,即创立一个头结点。即创立一个头结点。void InitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/*创创立立头结点头结点*/L-next=NULL;第64页，共108页。(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页，共108页。(3)判线性表是否为空表判线性表是否为空表ListEmpty(L)假设单链表假设单链表L没有数据结点没有数据结点,那么返回真那么返回真,否那么返回假。否那么返回假。int ListEmpty(LinkList*L)return(L-next=NULL);第66页，共108页。(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页，共108页。(5)输出线性表输出线性表DispList(L)逐逐一一扫扫描描单单链链表表L的的每每个个数数据据结结点点,并并显显示示各各结结点点的的data域值。域值。void DispList(LinkList*L)LinkList*p=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);第68页，共108页。(6)求线性表求线性表L中指定位置的某个数据元素中指定位置的某个数据元素GetElem(L,i,&e)思思路路：在在单单链链表表L中中从从头头开开场场找找到到第第 i个个结结点点,假假设设存存在在第第i个数据结点个数据结点,那么将其那么将其data域值赋给变量域值赋给变量e。第69页，共108页。int GetElem(LinkList*L,int i,ElemType&e)int j=0;LinkList*p=L;while(jnext;if(p=NULL)return 0;/*不存在第不存在第i个数据结点个数据结点*/else /*存在第存在第i个数据结点个数据结点*/e=p-data;return 1;第70页，共108页。(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=NULL)return(0);else return(n);第71页，共108页。(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;第72页，共108页。if(p=NULL)return 0;/*未找到位序为i-1的结点*/else/*找到位序为i-1的结点*p*/s=(LinkList*)malloc(sizeof(LinkList);/*创立新结点*s*/s-data=e;s-next=p-next;/*将*s插入到*p之后*/p-next=s;return 1;第73页，共108页。(9)删除数据元素删除数据元素ListDelete(&L,i,&e)思思路路：先先在在单单链链表表L中中找找到到第第i-1个个结结点点*p,假假设设存存在在这这样样的的结点结点,且也存在后继结点且也存在后继结点,那么删除该后继结点。那么删除该后继结点。int ListDelete(LinkList*&L,int i,ElemType&e)int j=0;LinkList*p=L,*q;while(jnext;第74页，共108页。if(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页，共108页。设设C=a1,b1,a2,b2,an,bn为为一一线线性性表表,采采用用带带头头结结点点的的hc单单链链表表存存放放,编编写写一一个个算算法法,将将其其拆拆分分为为两两个线性表个线性表,使得使得:A=a1,a2,an,B=b1,b2,bn 第76页，共108页。解解:设设拆拆分分后后的的两两个个线线性性表表都都用用带带头头结结点点的的单单链链表存放。表存放。先先建建立立两两个个头头结结点点*ha和和*hb,它它们们用用于于存存放放拆拆分分后后的的线线性性表表A和和B,ra和和rb分分别别指指向向这这两两个个单单链链表表的的表表尾尾,用用p指指针针扫扫描描单单链链表表hc,将将当当前前结结点点*p链链到到ha未未尾尾,p沿沿next域域下下移移一一个个结结点点,假假设设不不为为空空,那那么么当当前前结结点点*p链链到到hb未未尾尾,p沿沿next域域下下移移一一个个结结点点,如如此此这这样样,直直到到p为为空空。最后将两个尾结点的最后将两个尾结点的next域置空。域置空。对应算法如下对应算法如下:第77页，共108页。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(sizeof(LinkList);/*创立创立hb头结点头结点*/rb=hb;/*rb始终指向始终指向hb的末尾结点的末尾结点*/第78页，共108页。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页，共108页。本本算算法法实实际际上上是是采采用用尾尾插插法法建建立立两两个个新新表表。所以所以,尾插法建表算法是很多类似习题的根底！尾插法建表算法是很多类似习题的根底！第80页，共108页。有有一一个个带带头头结结点点的的单单链链表表head,head,其其ElemTypeElemType类型为类型为char,char,设计一个算法使其元素递增有序。设计一个算法使其元素递增有序。解解:假假设设原原单单链链表表中中有有一一个个或或以以上上的的数数据据结结点点,先先构构造造只只含含一一个个数数据据结结点点的的有有序序表表(只只含含一一个个数数据据结结点点的的单单链链表表一一定定是是有有序序表表)。扫扫描描原原单单链链表表余余下下的的结结点点*p(*p(直直到到p=NULLp=NULL为为止止),),在在有有序序表表中中通通过过比比较较找找插插入入*p*p的的前前驱驱结结点点*q,*q,然然后后将将*p*p插插入入到到*q*q之之后后(这这里里实实际际上上采采用用的的是是直直接接插插入入排排序方法序方法)。第81页，共108页。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结点后继结点的指针结点后继结点的指针*/第82页，共108页。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;/*扫描原单链表余下的结点扫描原单链表余下的结点*/第83页，共108页。2.3.3 2.3.3 双链表双链表 对对于于双双链链表表,采采用用类类似似于于单单链链表表的的类类型型定定义义,其其DLinkList类型的定义如下类型的定义如下:typedef struct DNode /*定义双链表结点类型定义双链表结点类型*/ElemType data;struct DNode*prior;/*指向前驱结点指向前驱结点*/struct DNode*next;/*指向后继结点指向后继结点*/DLinkList;第84页，共108页。在双链表中在双链表中,有些操作如求长度、取元素值和查有些操作如求长度、取元素值和查找元素等操作算法与单链表中相应算法是一样的找元素等操作算法与单链表中相应算法是一样的,这这里不多讨论。但在单链表中里不多讨论。但在单链表中,进展结点插入和删除时进展结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链表中涉及到前后结点的一个指针域的变化。而在双链表中,结点的插入和删除操作涉及到前后结点的两个指针域结点的插入和删除操作涉及到前后结点的两个指针域的变化。的变化。第85页，共108页。双链表中插入结点示意图双链表中插入结点示意图第86页，共108页。归纳起来归纳起来,在双链表中在双链表中p所指的结点之后插入一个所指的结点之后插入一个*s结点。其操作语句描述为结点。其操作语句描述为:s-next=p-next;/*将将*s插入到插入到*p之后之后*/p-next-prior=s;s-prior=p;p-next=s;第87页，共108页。删除结点示意图删除结点示意图 在在双双链链表表中中删删除除一一个个结结点点的的过过程程如如右图所示右图所示:第88页，共108页。归纳起来归纳起来,删除双链表删除双链表L L中中*p*p结点的后续结点。其操作语结点的后续结点。其操作语句描述为句描述为:p-next=q-next;q-next-prior=p;第89页，共108页。2.3.4 2.3.4 循环链表循环链表 循环链表是另一种形式的链式存储构造。它的特循环链表是另一种形式的链式存储构造。它的特点是表中最后一个结点的指针域不再是空点是表中最后一个结点的指针域不再是空,而是指向表而是指向表头结点头结点,整个链表形成一个环。由此整个链表形成一个环。由此,从表中任一结点出从表中任一结点出发均可找到链表中其他结点。发均可找到链表中其他结点。第90页，共108页。带头结点的循环单链表和循环双链表的示意图带头结点的循环单链表和循环双链表的示意图第91页，共108页。编编写写出出判判断断带带头头结结点点的的双双向向循循环环链链表表L是是否否对称相等的算法。对称相等的算法。解解:p从从左左向向右右扫扫描描L,q从从右右向向左左扫扫描描L,假假设设对对应应数数据据结结点点的的data域域不不相相等等,那那么么退退出出循循环环,否否那那么么继继续续比比较较,直直到到p与与q相相等等或或p的的下下一一个个结结点点为为*q为为止。对应算法如下止。对应算法如下:第92页，共108页。int Equeal(DLinkList*L)int same=1;DLinkList*p=L-next;/*p指向第一个数据结点指向第一个数据结点*/DLinkList*q=L-prior;/*q指向最后数据结点指向最后数据结点*/while(same=1)if(p-data!=q-data)same=0;else if(p=q)break;/*数据结点为奇数的情况数据结点为奇数的情况*/q=q-prior;if(p=q)break;/*数据结点为偶数的情况数据结点为偶数的情况*/p=p-next;return same;第93页，共108页。2.3.5 2.3.5 静态链表静态链表 静态链表借用一维数组来描述线性链表。数组中的一个静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点分量表示一个结点,同时使用游标同时使用游标(指示器指示器curcur即为伪指针即为伪指针)代替代替指针以指示结点在数组中的相对位置。数组中的第指针以指示结点在数组中的相对位置。数组中的第0 0个分量可个分量可以看成头结点以看成头结点,其指针域指示静态链表的第一个结点。其指针域指示静态链表的第一个结点。这种存储构造仍然需要预先分配一个较大空间这种存储构造仍然需要预先分配一个较大空间,但是在进展线性表的插入和删除操作时不需要移动元素但是在进展线性表的插入和删除操作时不需要移动元素,仅需要修改仅需要修改“指针指针,因此仍然具有链式存储构造的主要因此仍然具有链式存储构造的主要优点。优点。第94页，共108页。以下图给出了一个静态链表的例如。图以下图给出了一个静态链表的例如。图(a)是一是一个修改之前的静态链表个修改之前的静态链表,图图(b)是删除数据元素是删除数据元素“陈华陈华之后的静态链表之后的静态链表,图图(c)插入数据元素插入数据元素“王华之后王华之后的静态链表的静态链表,图中用阴影表示修改的游标。图中用阴影表示修改的游标。第95页，共108页。2.4 2.4 线性表的应用线性表的应用 计算任意两个表的简单自然连接过程讨论线性表的应用。计算任意两个表的简单自然连接过程讨论线性表的应用。假设有两个表假设有两个表A和和B,分别是分别是m1行、行、n1列和列和m2行、行、n2列列,它们它们简单自然连接结果简单自然连接结果C=A B,其中其中i表示表表示表A中列号中列号,j表示表表示表B中的列号中的列号,C为为A和和B的笛卡儿积中满足指定连接条件的所有的笛卡儿积中满足指定连接条件的所有记录组记录组,该连接条件为表该连接条件为表A的第的第i列与表列与表B的第的第j列相等。例如列相等。例如:i=j第96页，共108页。C=A B的计算结果如下的计算结果如下:3=1第97页，共108页。由由于于每每个个表表的的行行数数不不确确定定,为为此此,用用单单链链表表作作为为表表的的存存储储构构造造,每每行行作作为为一一个个数数据据结结点点。另另外外,每每行行中中的的数数据据个个数数也也是是不不确确定定的的,但但由由于于提提供供随随机机查查找找行行中中的的数数据据,所所以以每每行行的的数数据据采采用用顺顺序序存存储储构构造造,这这里里用用长长度度为为MaxCol的的数数组组存存储储每每行行的的数数据据。因因此此,该该单单链链表表中中数数据结点类型定义如下据结点类型定义如下:#define MaxCol 10/*最大列数最大列数*/typedef struct Node1/*定义数据结点类型定义数据结点类型*/ElemType dataMaxCol;struct Node1*next;/*指向后继数据结点指向后继数据结点*/DList;第98页，共108页。另另外外,需需要要指指定定每每个个表表的的行行数数和和列列数数,为为此此将将单单链链表表的的头头结结点类型定义如下点类型定义如下:typedef struct Node2/*定义头结点类型定义头结点类型*/int Row,Col;/*行数和列数行数和列数*/DList*next;/*指向第一个数据结点指向第一个数据结点*/HList;采采用用尾尾插插法法建建表表方方法法创创立立单单链链表表,用用户户先先输输入入表表的的行行数数和和列列数数,然然后后输输入入各各行行的的数数据据,为为了了简简便便,假假设设表表中中数数据据为为int型型,因此定义因此定义:typedef int ElemType;对应的建表算法如下对应的建表算法如下:第99页，共108页。void create(HList*&h)int i,j;DList*r,*s;h=(HList*)malloc(sizeof(HList);h-next=NULL;printf(表的行数表的行数,列数列数:);scanf(%d%d,&h-Row,&h-Col);for(i=0;iRow;i+)printf(第第%d行行:,i+1);s=(DList*)malloc(sizeof(DList);for(j=0;jCol;j+)scanf(%d,&s-dataj);if(h-next=NULL)h-next=s;else r-next=s;r=s;/*r始终指向最后一个数据结点始终指向最后一个数据结点*/r-next=NULL;采用尾插法建表采用尾插法建表第100页，共108页。对应的输出表的算法如下对应的输出表的算法如下:void display(HList*h)int j;DList*p=h-next;while(p!=NULL)for(j=0;jCol;j+)printf(%4d,p-dataj);printf(n);p=p-next;第101页，共108页。为了实现两个表为了实现两个表h1和和h2的简单自然连接的简单自然连接,先先要输入两个表连接的列序号要输入两个表连接的列序号f1和和f2,然后扫描然后扫描单链表单链表h1,对于对于h1的每个结点的每个结点,从头至尾扫描单从头至尾扫描单链表链表h2,假设自然连接条件成立假设自然连接条件成立,即即h1的当前结的当前结点点*p和和h2的当前结点的当前结点*q满足满足:p-dataf1-1=q-dataf2-1那么在新建单链表那么在新建单链表h中添加一个新结点。中添加一个新结点。新建的单链表新建的单链表h也是采用尾插法建表方法也是采用尾插法建表方法创立的。创立的。实现两个表实现两个表h1和和h2的简单自然连接并生成结的简单自然连接并生成结果果h的算法如下的算法如下:第102页，共108页。void link(HList*h1,HList*h2,HList*&h)int f1,f2,i;DList*p=h1-next,*q,*s,*r;printf(连接字段是连接字段是:第第1个表位序个表位序,第第2个表位序个表位序:);scanf(%d%d,&f1,&f2);h=(HList*)malloc(sizeof(HList);h-Row=0;h-Col=h1-Col+h2-Col;h-next=NULL;while(p!=NULL)q=h2-next;第103页，共108页。while(q!=NULL)if(p-dataf1-1=q-dataf2-1)/*对应字段值相等对应字段值相等*/s=(DList*)malloc(sizeof(DList);/*创立一个数据结点创立一个数据结点*/for(i=0;iCol;i+)/*复制表复制表1的当前行的当前行*/s-datai=p-datai;for(i=0;iCol;i+)s-datah1-Col+i=q-datai;/*复复制制表表2的的当当前前行行*/if(h-next=NULL)h-next=s;else r-next=s;r=s;/*r始终指向最后数据结点始终指向最后数据结点*/h-Row+;/*表行数增表行数增1*/q=q-next;/*表表2下移一个记录下移一个记录*/p=p-next;/*表表1下移一个记录下移一个记录*/r-next=NULL;/*表尾结点表尾结点next域置空域置空*/尾插法建表尾插法建表第104页，共108页。2.5 2.5 有序表有序表 所谓有序表所谓有序表,是指这样的线性表是指这样的线性表,其中所有元素以其中所有元素以递增或递减方式排列递增或递减方式排列,并规定有序表中不存在元素并规定有序表中不存在元素值一样的元素。在这里仍以顺序表进展存储。值一样的元素。在这里仍以顺序表进展存储。其中只有其中只有ListInsert()根本运算与前面的顺序表根本运算与前面的顺序表对应的运算有所差异对应的运算有所差异,其余都是一样的。有序表其余都是一样的。有序表的的ListInsert()运算对应的算法如下运算对应的算法如下:第105页，共108页。int ListInsert(SqList&L,ElemType e)int i=0,j;while(iL.length&L.dataii;j-)/*将将datai及后面元素后移一个位置及后面元素后移一个位置*/L.dataj=L.dataj-1;L.datai=e;L.length+;/*顺序表长度增顺序表长度增1*/return 1;注意：这里用的不是顺序注意：这里用的不是顺序表指针，直接就是顺序表表指针，直接就是顺序表第106页，共108页。本章小结本章小结本章的根本学习要点如下本章的根本学习要点如下:(1)(1)理解线性表的逻辑构造特性。理解线性表的逻辑构造特性。(2)(2)深入掌握线性表的两种存储方法深入掌握线性表的两种存储方法,即顺即顺序表和链表。体会这两种存储构造之间的差异。序表和链表。体会这两种存储构造之间的差异。(3)(3)重点掌握顺序表和链表上各种根本运重点掌握顺序表和链表上各种根本运算的实现。算的实现。(4)(4)综合运用线性表这种数据构造解决一些综合运用线性表这种数据构造解决一些复杂的实际问题。复杂的实际问题。第107页，共108页。谢谢大家！结结 语语第108页，共108页。