数据结构线性表PPT.ppt

第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 本章小结本章小结 2.5 2.5 有序表有序表 2.1 2.1 线性表的基本概念线性表的基本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算2.1.1 2.1.1 线性表的定义线性表的定义 线性表是具有相同特性的数据元素的一个有线性表是具有相同特性的数据元素的一个有限序列。限序列。该序列中所含元素的个数叫做线性表的该序列中所含元素的个数叫做线性表的长度长度,用用n表示表示,n0。当当n=0时时,表示线性表是一个空表表示线性表是一个空表,即表中不包即表中不包含任何元素。设序列中第含任何元素。设序列中第i(i表示位序表示位序)个元素为个元素为ai(1in)。线性表的一般表示为线性表的一般表示为:(a1,a2,ai,ai+1,an)其其中中a1为为第第一一个个元元素素,又又称称做做表表头头元元素素,a2为为第第二二个个元元素素,an为为最最后后一一个个元元素素,又又称称做做表表尾尾元元素。素。例如例如,在线性表在线性表 (1,4,3,2,8,10)中中,1为表头元素为表头元素,10为表尾元素。为表尾元素。2.1.2 2.1.2 线性表的运算线性表的运算 线性表的基本运算如下线性表的基本运算如下:(1)初初始始化化线线性性表表InitList(&L):构构造造一一个个空空的的线线性性表表L。(2)销销毁毁线线性性表表DestroyList(&L):释释放放线线性性表表L占占用用的内存空间。的内存空间。(3)判判线线性性表表是是否否为为空空表表ListEmpty(L):若若L为为空空表表,则返回真则返回真,否则返回假。否则返回假。(4)求求线线性性表表的的长长度度ListLength(L):返返回回L中中元元素素个数。个数。(5)输输出出线线性性表表DispList(L):当当线线性性表表L不不为为空空时时,顺序显示顺序显示L中各结点的值域。中各结点的值域。(6)求求线线性性表表L中中指指定定位位置置的的某某个个数数据据元元素素GetElem(L,i,&e):用用e返返回回L中中第第 i(1iListLength(L)个元素的值。个元素的值。(7)定定位位查查找找LocateElem(L,e):返返回回L中中第第1个个值值域域与与e相等的位序。若这样的元素不存在相等的位序。若这样的元素不存在,则返回值为则返回值为0。(8)插插入入数数据据元元素素ListInsert(&L,i,e):在在L的的第第i(1iListLength(L)+1)个个元元素素之之前前插插入入新新的的元元素素e,L的长度增的长度增1。(9)删除数据元素删除数据元素ListDelete(&L,i,&e):删除删除L的第的第i(1iListLength(L)个元素个元素,并用并用e返回其值返回其值,L的长度的长度减减1。例例2.1 假假设设有有两两个个集集合合 A 和和 B 分分别别用用两两个个线线性性表表 LA 和和 LB 表表示示,即即线线性性表表中中的的数数据据元元素素即即为为集集合合中中的的成成员员。编编写写一一个个算算法法求求一一个个新新的的集集合合C=AB,即将两个集合的并集放在线性表即将两个集合的并集放在线性表LC中。中。解解:本算法思想是本算法思想是:先初始化线性表先初始化线性表LC,将将LA的所的所有元素复制到有元素复制到LC中中,然后扫描线性表然后扫描线性表LB,若若LB的当的当前元素不在线性表前元素不在线性表LA中中,则将其插入到则将其插入到LC中。算法中。算法如下如下: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);for(i=1;i=lenb;i+)GetElem(LB,i,e);/*取取LB中第中第i个数据元素赋给个数据元素赋给e*/if (!LocateElem(LA,e)ListInsert(LC,+lenc,e);/*LA中不存在和中不存在和e相同者相同者,则插入到则插入到LC中中*/由由 于于 LocateElem(LA,e)运运 算算 的的 时时 间间 复复 杂杂 度度 为为O(ListLength(LA),所以本算法的时间复杂度为所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB)。2.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表基本运算的实现顺序表基本运算的实现2.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是线性表的顺序存储结构就是:把线性表中的所把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。器中指定存储位置开始的一块连续的存储空间中。这样这样,线性表中第一个元素的存储位置就是指线性表中第一个元素的存储位置就是指定的存储位置定的存储位置,第第i+1个元素个元素(1in-1)的存储的存储位置位置紧接在第紧接在第i i个元素的存储位置的后面。个元素的存储位置的后面。线性表线性表 逻辑结构逻辑结构顺序顺序表表 存储结构存储结构 假定线性表的元素类型为假定线性表的元素类型为ElemType,则每个元则每个元素所占用存储空间大小素所占用存储空间大小(即字节数即字节数)为为sizeof(ElemType),整个线性表所占用存储空间的大小整个线性表所占用存储空间的大小为为:n*sizeof(ElemType)其中其中,n表示线性表的长度。表示线性表的长度。顺序表示意图顺序表示意图 在在定定义义一一个个线线性性表表的的顺顺序序存存储储类类型型时时,需需要要定定义义一一个个数数组组来来存存储储线线线线表表中中的的所所有有元元素素和和定定义义一一个个整整型变量来存储线性表的长度。型变量来存储线性表的长度。假假定定数数组组用用dataMaxSize表表示示,长长度度整整型型变变量量用用length表表示示,并并采采用用结结构构体体类类型型表表示示,则则元元素素类类型型为为通通用用类类型型标标识识符符ElemType的的线线性性表表的的顺顺序序存存储储类类型型可可描述如下描述如下:typedef struct ElemType dataMaxSize;int length;SqList;/*/*顺序表类型顺序表类型*/其中其中,data成员存放元素成员存放元素,length成员存放线性表的成员存放线性表的实际长度。实际长度。说明：由于说明：由于C/C+C/C+中数组的下标从中数组的下标从0 0开始，线性表的第开始，线性表的第i i个元素个元素a ai i存放顺序表的第存放顺序表的第i-1i-1位置上。为了清楚，将位置上。为了清楚，将a ai i在逻辑在逻辑序列中的位置称为序列中的位置称为逻辑位序逻辑位序，在顺序表中的位置称为，在顺序表中的位置称为物理位物理位序序。2.2.2 2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构一旦采用顺序表存储结构,我们就可以用我们就可以用C/C+语言实现线性表的各种基本运算。为了方便语言实现线性表的各种基本运算。为了方便,假设假设ElemType为为char类型类型,使用如下自定义类型语句使用如下自定义类型语句:typedef char ElemType;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;2.顺序表基本运算算法顺序表基本运算算法(1)初始化线性表初始化线性表InitList(L)该该运运算算的的结结果果是是构构造造一一个个空空的的线线性性表表L。实实际际上上只只需需将将length成员设置为成员设置为0即可。即可。void InitList(SqList*&L)/引用型指针引用型指针 L=(SqList*)malloc(sizeof(SqList);/*分配存放线性表的空间分配存放线性表的空间*/L-length=0;本算法的时间复杂度为本算法的时间复杂度为O(1)。顺序表L (2)销毁线性表销毁线性表DestroyList(L)该运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。void DestroyList(SqList*&L)free(L);本算法的时间复杂度为本算法的时间复杂度为O(1)。(3)判定是否为空表判定是否为空表ListEmpty(L)该该运运算算返返回回一一个个值值表表示示L是是否否为为空空表表。若若L为为空空表表,则返回则返回1,否则返回否则返回0。int ListEmpty(SqList*L)return(L-length=0);本算法的时间复杂度为本算法的时间复杂度为O(1)。(4)求线性表的长度求线性表的长度ListLength(L)该该运运算算返返回回顺顺序序表表L的的长长度度。实实际际上上只只需需返返回回length成员的值即可。成员的值即可。int ListLength(SqList*L)return(L-length);本算法的时间复杂度为本算法的时间复杂度为O(1)。(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);本本算算法法中中基基本本运运算算为为for循循环环中中的的printf语语句句,故故时间复杂度为时间复杂度为:O(L-length)或或O(n)(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)。(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;本本算算法法中中基基本本运运算算为为while循循环环中中的的i+语语句句,故故时时间复杂度为间复杂度为:O(L-length)或或O(n)(8)插入数据元素插入数据元素ListInsert(L,i,e)该该 运运 算算 在在 顺顺 序序 表表 L的的 第第 i个个 位位 置置(1iListLength(L)+1)上插入新的元素上插入新的元素e。思思路路：如如果果i值值不不正正确确,则则显显示示相相应应错错误误信信息息；否否则则将将顺顺序序表表原原来来第第i个个元元素素及及以以后后元元素素均均后后移移一一个个位位置置,腾腾出出一一个个空空位位置置插插入入新新元元素素,顺顺序序表表长长度增度增1。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 对于本算法来说对于本算法来说,元素移动的次数不仅与表长元素移动的次数不仅与表长L.length=n有关有关,而且与插入位置而且与插入位置i有关有关:当当i=n+1时时,移移动次数为动次数为0；当；当i=1时时,移动次数为移动次数为n,达到最大值。在达到最大值。在线性表线性表sq中共有中共有n+1个可以插入元素的地方。假设个可以插入元素的地方。假设pi(=)是在第是在第i个位置上插入一个元素的概率个位置上插入一个元素的概率,则在则在长度为长度为n的线性表中插入一个元素时所需移动元素的的线性表中插入一个元素时所需移动元素的平均次数为平均次数为:因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。(9)删除数据元素删除数据元素ListDelete(L,i,e)删删除除顺顺序序表表L中中的的第第i(1iListLength(L)个个元元素。素。思思路路：如如果果i值值不不正正确确,则则显显示示相相应应错错误误信信息息；否否则则将将线线性性表表第第i个个元元素素以以后后元元素素均均向向前前移移动动一一个个位位置置,这这样样覆覆盖盖了了原原来来的的第第i个个元元素素,达达到到删删除除该该元元素的目的素的目的,最后顺序表长度减最后顺序表长度减1。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 对于本算法来说对于本算法来说,元素移动的次数也与表长元素移动的次数也与表长n和和删除元素的位置删除元素的位置i有关有关:当当i=n时时,移动次数为移动次数为0；当；当i=1时时,移动次数为移动次数为n-1。在线性表。在线性表sq中共有中共有n个元素可以个元素可以被删除。假设被删除。假设pi(pi=)是删除第是删除第i个位置上元素的概个位置上元素的概率率,则在长度为则在长度为n的线性表中删除一个元素时所需移的线性表中删除一个元素时所需移动元素的平均次数为动元素的平均次数为:=因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。例例2.2 设设计计一一个个算算法法,将将x插插入入到到一一个个有有序序(从从小小到到大大排排序序)的的线线性性表表(顺顺序序存存储储结结构构即即顺顺序序表表)的适当位置上的适当位置上,并保持线性表的有序性。并保持线性表的有序性。解解:先先通通过过比比较较在在顺顺序序表表L中中找找到到存存放放x的的位位置置i,然然后后将将x插插入入到到L.datai中中,最最后后将将顺顺序序表表的的长度增长度增1。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 例例2.3 设设计计一一个个算算法法,将将两两个个元元素素有有序序(从从小到大小到大)的顺序表合并成一个有序顺序表。的顺序表合并成一个有序顺序表。求解思路求解思路:将两个顺序表进行二路归并。将两个顺序表进行二路归并。归并到顺序表归并到顺序表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：1kSqList*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+;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);例例2.4 已已知知长长度度为为n的的线线性性表表A采采用用顺顺序序存存储储结结构构,编编写写一一个个时时间间复复杂杂度度为为O(n)、空空间间复复杂杂度度为为O(1)的的算算法法,该该算算法法删删除除线线性性表表中中所所有有值值为为item的的数数据据元元素。素。解解:用用k记记录录顺顺序序表表A中中等等于于item的的元元素素个个数数,边边扫扫描描A边边统统计计k,并并将将不不为为item的的元元素素前前移移k个个位位置置,最最后修改后修改A的长度。对应的算法如下的长度。对应的算法如下: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：类似于：类似于建顺序表建顺序表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;adc bi=0 i=1 i=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结点结点,插入到头结点之后插入到头结点之后 (2)尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单,但生成的链表但生成的链表中结点的次序和原数组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上,为此必须增加一为此必须增加一个尾指针个尾指针r,r,使其始终指向当前链表的尾结点。采使其始终指向当前链表的尾结点。采用尾插法建表的算法如下用尾插法建表的算法如下: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*/bcdai=0 i=1 i=2 i=3head头结点头结点adcb b采用尾插法建立单链表的过程采用尾插法建立单链表的过程2.插入结点运算插入结点运算 插插入入运运算算是是将将值值为为x的的新新结结点点插插入入到到单单链链表表的的第第i个个结结点点的的位位置置上上。先先在在单单链链表表中中找找到到第第i-1个结点个结点,再在其后插入新结点。再在其后插入新结点。单链表插入结点的过程如下图所示。单链表插入结点的过程如下图所示。插入结点示意图插入结点示意图 3.删除结点运算删除结点运算 删除运算是将单链表的第删除运算是将单链表的第i个结点删去。先在单个结点删去。先在单链表中找到第链表中找到第i-1个结点个结点,再删除其后的结点。删除再删除其后的结点。删除单链表结点的过程如下图所示。单链表结点的过程如下图所示。删除结点示意图删除结点示意图 4.线性表基本运算实现线性表基本运算实现 (1)初始化线性表初始化线性表InitList(L)该运算建立一个空的单链表该运算建立一个空的单链表,即创建一个头结点。即创建一个头结点。void InitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/*创建头结点创建头结点*/L-next=NULL;(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);(3)判线性表是否为空表判线性表是否为空表ListEmpty(L)若单链表若单链表L没有数据结点没有数据结点,则返回真则返回真,否则返回假。否则返回假。int ListEmpty(LinkList*L)return(L-next=NULL);(4)求线性表的长度求线性表的长度ListLength(L)返回单链表返回单链表L中数据结点的个数。中数据结点的个数。int ListLength(LinkList*L)LinkList*p=L;int i=0;while(p-next!=NULL)i+;p=p-next;return(i);(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);(6)求求 线线 性性 表表 L中中 指指 定定 位位 置置 的的 某某 个个 数数 据据 元元 素素GetElem(L,i,&e)思思路路：在在单单链链表表L中中从从头头开开始始找找到到第第 i个个结结点点,若若存在第存在第i个数据结点个数据结点,则将其则将其data域值赋给变量域值赋给变量e。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;(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);(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;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;(9)删除数据元素删除数据元素ListDelete(&L,i,&e)思思路路：先先在在单单链链表表L L中中找找到到第第i-1i-1个个结结点点*p,p,若若存存在在这这样的结点样的结点,且也存在后继结点且也存在后继结点,则删除该后继结点。则删除该后继结点。int ListDelete(LinkList*&L,int i,ElemType&e)int j=0;LinkList*p=L,*q;while(jnext;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;例例2.5 设设C=a1,b1,a2,b2,an,bn为为一一线线性性表表,采采用用带带头头结结点点的的hc单单链链表表存存放放,编编写写一一个个算算法法,将将其拆分为两个线性表其拆分为两个线性表,使得使得:A=a1,a2,an,B=b1,b2,bn 解解:设设拆拆分分后后的的两两个个线线性性表表都都用用带带头头结结点点的的单单链链表表存放。存放。先先建建立立两两个个头头结结点点*ha和和*hb,它它们们用用于于存存放放拆拆分分后后的的线线性性表表A和和B,ra和和rb分分别别指指向向这这两两个个单单链链表表的的表表尾尾,用用p指指针针扫扫描描单单链链表表hc,将将当当前前结结点点*p链链到到ha未未尾尾,p沿沿next域域下下移移一一个个结结点点,若若不不为为空空,则则当当前前结结点点*p链链到到hb未未尾尾,p沿沿next域域下下移移一一个个结结点点,如如此此这这样样,直直到到p为为空空。最最后后将两个尾结点的将两个尾结点的next域置空。域置空。对应算法如下对应算法如下: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的末尾结点的末尾结点*/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域置空域置空*/本本算算法法实实际际上上是是采采用用尾尾插插法法建建立立两两个个新新表表。所以所以,尾插法建表算法是很多类似习题的基础！尾插法建表算法是很多类似习题的基础！例例 2.6 有有 一一 个个 带带 头头 结结 点点 的的 单单 链链 表表 head,其其ElemType类类型型为为char,设设计计一一个个算算法法使使其其元元素素递递增增有序。有序。解解:若若原原单单链链表表中中有有一一个个或或以以上上的的数数据据结结点点,先先构构造造只只含含一一个个数数据据结结点点的的有有序序表表(只只含含一一个个数数据据结结点点的的单单链链表表一一定定是是有有序序表表)。扫扫描描原原单单链链表表余余下下的的结结点点*p(p(直直到到p=NULLp=NULL为为止止),),在在有有序序表表中中通通过过比比较较找找插插入入*p p的的前前驱驱结结点点*q,q,然然后后将将*p p插插入入到到*q q之之后后(这里实际上采用的是直接插入排序方法这里实际上采用的是直接插入排序方法)。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结点后继结点的指针结点后继结点的指针*/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;/*扫描原单链表余下的结点扫描原单链表余下的结点*/2.3.3 2.3.3 双链表双链表 对对于于双双链链表表,采采用用类类似似于于单单链链表表的的类类型型定定义义,其其DLinkList类型的定义如下类型的定义如下:typedef struct DNode /*定义双链表结点类型定义双链表结点类型*/ElemType data;struct DNode*prior;/*指向前驱结点指向前驱结点*/struct DNode*next;/*指向后继结点指向后继结点*/DLinkList;在双链表中在双链表中,有些操作如求长度、取元素值和查有些操作如求长度、取元素值和查找元素等操作算法与单链表中相应算法是相同的找元素等操作算法与单链表中相应算法是相同的,这这里不多讨论。但在单链表中里不多讨论。但在单链表中,进行结点插入和删除时进行结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链表涉及到前后结点的一个指针域的变化。而在双链表中中,结点的插入和删除操作涉及到前后结点的两个指结点的插入和删除操作涉及到前后结点的两个指针域的变化。针域的变化。双链表中插入结点示意图双链表中插入结点示意图 归纳起来归纳起来,在双链表中在双链表中p所指的结点之后插入所指的结点之后插入一个一个*s结点。其操作语句描述为结点。其操作语句描述为:s-next=p-next;/*将将*s插入到插入到*p之后之后*/p-next-prior=s;s-prior=p;p-next=s;删除结点示意图删除结点示意图 在在 双双 链链 表表中中删删除除一一个个结结点点的的过过程程如如右右图图所所示示:归纳起来归纳起来,删除双链表删除双链表L L中中*p p结点的后续结点。结点的后续结点。其操作语句描述为其操作语句描述为:p-next=q-next;q-next-prior=p;2.3.4 2.3.4 循环链表循环链表 循环链表循环链表是另一种形式的链式存储结构。它的是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空特点是表中最后一个结点的指针域不再是空,而是而是指向表头结点指向表头结点,整个链表形成一个环。由此整个链表形成一个环。由此,从表中从表中任一结点出发均可找到链表中其他结点。任一结点出发均可找到链表中其他结点。带头结点的循环单链表和循环双链表的示意图带头结点的循环单链表和循环双链表的示意图 例例2.7 编编写写出出判判断断带带头头结结点点的的双双向向循循环环链链表表L是是否对称相等的算法。否对称相等的算法。解解:p从从左左向向右右扫扫描描L,q从从右右向向左左扫扫描描L,若若对对应应数数据据结结点点的的data域域不不相相等等,则则退退出出循循环环,否否则则继继续续比比较较,直直到到p与与q相相等等或或p的的下下一一个个结结点点为为*q为为止止。对对应应算算法如下法如下: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;2.3.5 2.3.5 静态链表静态链表 静态链表借用一维数组来描述线性链表。数组中静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点的一个分量表示一个结点,同时使用同时使用游标游标(指示器指示器cur即即为为伪指针伪指针)代替指针以指示结点在数组中的相对位置。代替指针以指示结点在数组中的相对位置。数组中的第数组中的第0个分量可以看成头结点个分量可以看成头结点,其指针域指示静其指针域指示静态链表的第一个结点。态链表的第一个结点。这种存储结构仍然需要预先分配一个较大空间这种存储结构仍然需要预先分配一个较大空间,但但是在进行线性表的插入和删除操作时不需要移动元素是在进行线性表的插入和删除操作时不需要移动元素,仅需要修改仅需要修改“指针指针”,因此仍然具有链式存储结构的因此仍然具有链式存储结构的主要