线性表应用(与“元素”有关的文档共104张)

线性表应用第一页，共104页。问题的提出目前计算机技术已经渗透到各个应用领域，信息管理系统得到普遍应用。以学校为例，不论是大学、中学和小学，都已经将学生的成绩管理采用计算机管理。学号姓名班级英语数学总分1051250101陈俊俊

软件05031021105761051250102陈小龙

软件05031001125801051250103刘静静

软件0503105120590第二页，共104页。问题中的数据分析每一行对应一个新生的数据（包括学号、姓名、班级、英语、数学和总分），是一个结构体类型的数据，即数据元素，多个学生的数据之间存在如下的前后次序关系：（1）第一个新生数据前面无其他新生数据；（2）最后一个新生数据后面无其他新生数据；（3）中间每一个新生数据前面一定有一个其他新生的数据，后面也必有一个其他新生数据。第三页，共104页。问题中的功能分析1、创建新生数据

2、插入新生数据

3、删除新生数据

4、修改新生数据

5、查询英语成绩

6、查询数学成绩

7、查询总成绩

8、显示新生数据第四页，共104页。问题中的数据结构经过上面的分析，不难看出，新生成绩管理系统中的数据是一组具有相同数据类型的数据元素，数据元素之间的关系是“前后”的次序关系，系统的功能就是对这个数据对象进行操作。第五页，共104页。数据的特征一个数据元素的有序（次序）集1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。第六页，共104页。2.1线性表的类型定义7第七页，共104页。抽象数据类型线性表的定义如下：ADTList{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n

为线性表的表长;

称n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai在线性表中的位序。}8第八页，共104页。

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList9第九页，共104页。

InitList(&L)操作结果：构造一个空的线性表L。初始化操作10第十页，共104页。

结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。11第十一页，共104页。ListEmpty(L)ListLength(L)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作:12第十二页，共104页。

ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）13第十三页，共104页。ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）14第十四页，共104页。GetElem(L,i,&e)

初始条件：

操作结果：线性表L已存在，用

e返回L中第i

个元素的值。（求线性表中某个数据元素）且1≤i≤LengthList(L)15第十五页，共104页。LocateElem(L,e,compare())初始条件：操作结果：线性表L已存在，e

为给定值，

compare()是元素判定函数。返回L中第1个与e满足关系

compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）16第十六页，共104页。

ListTraverse(L,visit())初始条件：操作结果：线性表L已存在。Visit()为某个访问函数。依次对L中每个元素调用函数标visit()。一旦visit()失败，则操作失败。（遍历线性表）17第十七页，共104页。加工型操作

ClearList(&L)PutElem(&L,i,e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

18第十八页，共104页。ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）19第十九页，共104页。PutElem(&L,i,e)初始条件：操作结果：线性表L已存在，L中第i个元素赋值e。（改变数据元素的值）且1≤i≤LengthList(L)20第二十页，共104页。

ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在，在L的第i个元素之前插入新的元素e，L的长度增1。（插入数据元素）且1≤i≤LengthList(L)+121第二十一页，共104页。ListDelete(&L,i,&e)初始条件：操作结果：线性表L已存在且非空，删除L

的第

i

个元素，并用e返回其值，L的长度减1。（删除数据元素）1≤i≤LengthList(L)22第二十二页，共104页。23

在实际的软件开发过程中，仅仅给出数据的逻辑结构定义是不够的，必须要设计出数据的物理存储结构及其上的操作，才能用程序设计语言来实现。

数据的存储结构不仅要考虑数据元素的存储，还要考虑数据元素之间的关系存储。根据线性表中的数据元素特点以及它们的前后次序关系，通常采用顺序存储和链式存储。第二十三页，共104页。2.2线性表类型的实现----顺序映象24第二十四页，共104页。最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。顺序映象——

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>25第二十五页，共104页。

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址，称作线性表的基地址26第二十六页，共104页。以“存储位置相邻”表示有序对<ai-1,ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址27第二十七页，共104页。

在顺序存储中，如果只定义存放数据元素的数组，不提供数组的容量和已经存进去的数据元素个数，对线性表做操作是很不方便的。但是C语言提供的数组不能满足这些需求，因此必须自定义结构体数据类型，包括：（1）一片连续的存储空间（数组或数组的起始地址）（2）线性表的容量（数组的大小）（3）线性表的长度（已存入到数组中的数据元素个数）28第二十八页，共104页。顺序映像的C语言描述#defineMAX100typedefstruct{

}SqList;//俗称顺序表ElemTypeelem[MAX];//存储空间基址int

length;//当前长度int

listsize;//当前分配的存储容量

//(以sizeof(ElemType)为单位)29数组容量数据元素个数第二十九页，共104页。顺序映像的C语言描述typedefstruct{

}SqList;//俗称顺序表ElemType*elem;//存储空间基址int

length;//当前长度int

listsize;//当前分配的存储容量

//(以sizeof(ElemType)为单位)30第三十页，共104页。对比两种存储结构：

第一种理解容易，使用相对简单，数组大小固定，缺乏灵活性；

第二种理解有一定的难度，但数组大小的定义不在数据类型中，可根据实际问题的需要，在初始化操作中自定义数组的大小，具有非常好的通用性。31第三十一页，共104页。线性表的基本操作在顺序表中的实现InitList(&L)//结构初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//删除元素32第三十二页，共104页。

函数之间的数据传递是通过参数来实现的。一般分为两种情况：（1）如果被调用函数需要接收主调函数中的某个值，则被调用函数的形参是与主调函数中这个值类型相同的变量，形参的任何变化都不影响实参。（2）如果被调用函数需要先接收主调函数中某个变量的值，然后再修改主调函数中这个变量的值，则被调用函数的形参是存放这种类型变量地址的指针变量。（3）一般情况下用函数值表示操作的成功与失败。函数值为1，表示成功；函数值为0，表示失败。第三十三页，共104页。Status

InitList_Sq(SqList&L,intmaxsize)

{//构造一个最大容量为maxsize的顺序表

}//InitList_Sq算法时间复杂度：O(1)L.elem=newElemType[maxsize];

//

为顺序表分配大小为maxsize的数组空间if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;34第三十四页，共104页。Status

InitList_Sq(SqList*L,intmaxsize)

{//构造一个最大容量为maxsize的顺序表

}//InitList_Sq算法时间复杂度：O(1)L->elem=(ElemType*)malloc(sizeof(ElemType)*maxsize);if(!L->elem)exit(OVERFLOW);L->length=0;L->listsize=maxsize;returnOK;35第三十五页，共104页。例如：顺序表，查找指定元素的位置23754138546217L.elemL.length=7L.listsizee=38pppppi12341850p可见，基本操作是，将顺序表中的元素逐个和给定值e相比较。36第三十六页，共104页。

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}//LocateElem_Sq

O(ListLength(L))if(i<=L.length)returni;elsereturn0;算法的时间复杂度为：i=1;//i的初值为第1元素的位序p=L.elem;

//p的初值为第1元素的存储位置while

(i<=L.length&&!(*compare)(*p++,e))++i;(*compare)(*p++,e)//找到满足条件的元素//没有找到满足条件的元素37第三十七页，共104页。boolcomp(ElemTypea,ElemTypeb);intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}//LocateElem_SqLocateElem_Sq(L,e,com);if(i<=L.length)returni;elsereturn0;i=1;p=L.elemwhile

(i<=L.length&&!(*compare)(*p++,e))++i;//找到满足条件的元素//没有找到满足条件的元素第三十八页，共104页。线性表操作

ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？39第三十九页，共104页。

(a1,…,ai-1,ai,…,an)改变为a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加(a1,…,ai-1,e,ai,…,an)40第四十页，共104页。

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在顺序表L的第i个位置插入新的元素e,

//i的合法范围为1≤i≤L.length+1}//ListInsert_Sq

算法时间复杂度为:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;……元素右移41第四十一页，共104页。if(L.length>=L.listsize)returnOVERFLOW;//当前存储空间已满

if(i<1||i>L.length+1)

returnERROR;

//

插入位置不合法42第四十二页，共104页。考虑移动元素的平均情况:

假设在第

i个元素之前插入的概率为，

则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：43第四十三页，共104页。2118307542568721183075例如：ListInsert_Sq(L,5,66)

L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p44第四十四页，共104页。

StatusListInsert_Sq(SqList*L,inti,ElemTypee){//i的合法范围为1≤i≤L->length+1}//ListInsert_Sq

for(k=L->length;k>=i;i--)L->elem[k]=L->elem[k-1];L->elem[i-1]=e;++L->length;returnOK;if(i<1||i>L->length+1)returnERROR;if(L->length==L->listsize)returnOVERFLOW;45C语言的实现第四十五页，共104页。

StatusListInsert_Sq(SqList*L,inti,ElemTypee){//i的合法范围为1≤i≤L->length+1}//ListInsert_Sq

q=&(L.elem[i-1]);//q指示插入位置for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L->length;//表长增1returnOK;if(i<1||i>L->length+1)returnERROR;if(L->length==L->listsize)returnOVERFLOW;46C语言的实现第四十六页，共104页。线性表操作

ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？47第四十七页，共104页。

(a1,…,ai-1,ai,ai+1,…,an)改变为ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1

ai

ai+1

…

ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)48第四十八页，共104页。StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被删除元素之后的元素左移--L.length;//表长减1returnOK;算法时间复杂度为:

O(ListLength(L))p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//删除位置不合法元素左移49第四十九页，共104页。考虑移动元素的平均情况:

假设删除第

i个元素的概率为

,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：50第五十页，共104页。2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)

p51第五十一页，共104页。52基于顺序表的实例解决方案

对于本章提出的新生管理系统，采用顺序表存放学生数据，类型描述如下：typedefstruct{charxh[15]://存放学生学号charxm[20];//存放学生姓名

charbj[20];//存放班级floatscore1;//存放英语分数floatscore2;//存放数学分数floatscore3;//存放总分

}STD;

typedefstruct{STD*data;//dada是一个指向STD类型的指针变量

intlistSize;intlength;}SQList;第五十二页，共104页。53基于顺序表的实例解决方案

各个功能对应以下函数；

（1）创建新生数据——createSqList();

（2）插入新生数据——insertSqList();

（3）删除新生数据——deleteSqList()；

（4）修改新生数据——updateSqList();

（5）根据学号查询——locationSqList();

（6）查询英语成绩——findSqList();

（7）查询数学成绩——findSqList();

（8）查询总成绩——findSqList();

（9）显示新生数据——dispSqList()

这里除了查询函数需要在定位函数的基础上做一定的改动之外，其余函数稍作修改即可。以查询英语成绩为例。

voidfindSqList(SQListL,floatx){for(i=0;i<L.length;i++)if(L.data[i].score1>=x)printf("%s%s%s%7,2f\n",L.data[i].xh,L.data[i].xm,L.data[i].bj,L.data[i].score1);}第五十三页，共104页。54创建函数的定义：voidcreateSqList(SQList*L,intmaxsize){intn=0;STDx;charyn;initSqList(L,maxsize);//创建空表do{printf("请输入第%d个学生的姓名和分数，用空格隔开：",n+1);scanf("%s%f",,&x.score);getchar();//空读回车insertSqList(L,n+1,x);n++;printf("继续输入吗？Y/N：");yn=getchar(); }while(yn=='Y'||yn=='y');}基于顺序表的实例解决方案

第五十四页，共104页。55为了使程序结构清晰，从上至下的书写顺序为：（1）编译预处理命令（2）自定义数据类型(typedef)（3）函数声明（4）主函数（5）各个函数的定义第五十五页，共104页。2.3线性表类型的实现----链式映象56第五十六页，共104页。一、单链表二、结点和单链表的C语言描述三、线性表的操作在单链表中的实现四、其它形式的链表57五、线性表的应用第五十七页，共104页。

用一组地址任意的存储单元存放线性表中的数据元素。一、单链表

结点=

元素(数据元素的映象)+指针(指示后继元素存储位置)

(表示数据元素或数据元素的映象)以“结点的序列”表示线性表

称作链表58第五十八页，共104页。L的数据类型不同于结点的数据类型，L是一个指针变量，存放的是第一个结点的地址。通常称为头指针。链表是否为空，只要看L中的存放的地址值即可，当L中的值为NULL时，L是一个空链表，否则是一个非空链表。59

a1a2…...an^L^L头指针第五十九页，共104页。头指针L指向的结点称为头结点（数据域为空），头结点的后继结点是第一个结点。

链表是否为空取决于头结点的指针域是否为空。如果头结点的指针域为NULL，则为空链表，否则链表不为空。头结点

a1a2…...an^60L^L第六十页，共104页。

TypedefstructLNode{ElemTypedata;//数据域

structLNode*next;//指针域

}LNode,*LinkList;

二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针61第六十一页，共104页。三、单链表操作的实现GetElem(L,i,e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)

//生成含n个数据元素的链表62第六十二页，共104页。L

线性表的操作

GetElem(L,i,&e)在单链表中的实现:211830754256∧pppj12363第六十三页，共104页。

因此，查找第i个数据元素的基本操作为：移动指针，比较j和i

单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

令指针p

始终指向线性表中第j

个数据元素64第六十四页，共104页。

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&j<i){p=p->next;++j;}//

顺指针向后查找，直到p指向第i个元素

//

或p为空if(!p||j>i)

returnERROR;e=p->data;//取得第i个元素returnOK;65//i大于表长或者小于1第六十五页，共104页。ai-1

线性表的操作

ListInsert(&L,i,e)

在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>eaiai-166第六十六页，共104页。

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。67第六十七页，共104页。StatusListInsert_L(LinkListL,inti,ElemTypee){

//L为带头结点的单链表的头指针，本算法

//在链表中第i个结点之前插入新的元素e

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第i-1个结点if(!p||j>i-1)

returnERROR;//

i大于表长或者小于168第六十八页，共104页。s=newLNode;

//生成新结点if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp69第六十九页，共104页。线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-170第七十页，共104页。

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pq71第七十一页，共104页。StatusListDelete_L(LinkListL,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i-1个结点q=p->next;p->next=q->next;

//删除并释放结点e=q->data;delete(q);returnOK;if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理72第七十二页，共104页。操作ClearList(&L)在链表中的实现:voidClearList(&L){//将单链表重新置为一个空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListdelete(p);算法时间复杂度：O(ListLength(L))73第七十三页，共104页。如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。74第七十四页，共104页。例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；ananan-1四、依次类推，直至输入a1为止。75第七十五页，共104页。voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i){p=newLNode;

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;//插入}76第七十六页，共104页。77main(){LinkListL;…switch(n){case1：

initLinkList(&L);}}intinitLinkList(LinkList*L){*L=(LinkList)malloc(sizeof(Lnode));if(L==NULL)return0;(*L)->next=NULL;return1;

}typedefstructLnode{STDdata;structLnode*next;}LNode,*LinkList;structLnode{STDdata;structLnode*next;};typedefstructLnodeLNode;typedefstructLnode*LinkList;第七十七页，共104页。78

Lmain(){LinkListL;…switch(n){case1：

initLinkList(&L);}}intinitLinkList(LinkList*L){*L=(LinkList)malloc(sizeof(Lnode));if(L==NULL)return0;(*L)->next=NULL;return1;

}^第七十八页，共104页。79基于链表的实例解决方案

对于本章提出的新生成绩管理系统，采用不带头结点的单向链表存放学生数据，类型描述如下：typedefstruct{charxh[15]://存放学生学号charxm[20];//存放学生姓名charbj[20];//存放班级floatscore1;//存放英语分数

floatscore2;//存放数学分数

floatscore3;//存放总分}STD;typedefstructLNode{STDdata;structLNode*next}LNode,*LinkList;第七十九页，共104页。80基于链表的实例解决方案

各个功能对应以下函数；

（1）创建新生数据——createLinkList();

（2）插入新生数据——insertLinkList();

（3）删除新生数据——deleteLinkList()；

（4）修改新生数据——updateLinkList();

（5）根据学号查询——locationLinkList();

（5）查询英语成绩——findLinkList();

（6）查询数学成绩——findLinkList();

（7）查询总成绩——findLinkList();

（8）显示新生数据——dispLinkList()

这里除了查询函数需要在定位函数的基础上做一定的改动之外，其余函数稍作修改即可。以查询英语成绩为例。

voidfindLinkList(LinkListL,floatx){LinkListp=L->next;while(p){if(p->data.score1>=x)printf("%s%s%s%7.2f\n",p->data.xh,p->data.xm,p->data.bj,p->data.score1);p=p->next;}}第八十页，共104页。81顺序存储结构与链式存储结构的比较

顺序结构

链式存储结构空间相对静态结构 每个结点都动态管理存储密度相对高； 存储密度相对低；插入或删除时需移动大量元素；只要修改指针；可以随机存取表中任一元素；只能顺序访问；

数据元素的值所占的存储量

线性表所占的存储总量存储密度（μ）=第八十一页，共104页。

1.双向链表四、其它形式的链表typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}

DuLNode,*DuLinkList;82第八十二页，共104页。83L/\

a1a2

…an/\

L/\/\空双向链表存储特点:

链表中每个结点有两个指针成员，一个指向直接前驱，一个指向直接后继。双向链表第八十三页，共104页。

最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an2.循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。84第八十四页，共104页。双向循环链表空表非空表a1a2…...an85第八十五页，共104页。双向链表的操作特点：“查询”和单链表相同“插入”和“删除”时需要同时修改两个方向上的指针。86第八十六页，共104页。ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入87第八十七页，共104页。ai-1删除aiai+1p->next=p->next->next;p->next->prior=p;pai-188第八十八页，共104页。则

归并两个“其数据元素按值非递减有序排列”的有序表A和B，求得有序表C也具有同样特性。设

A=(a1,…,ai,…,an),B=(b1,…,bj,…,bm)

C=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)归并得

(c1,…,ck-1)k=1,2,…,m+n89五、线性表的应用1.两个线性表的合并第八十九页，共104页。1．初始化C为空表；（1）使用新的节点：2．分别从A和B中取得当前元素ai

和bj；3．若ai≤bj，则将ai

插入到C中，否则将

bj

插入到C中；4．重复2和3两步，直至A或B中元素被取完为止；5．将A表或B表中剩余元素复制插入到

C表中。90第九十页，共104页。voidMergeList(ListLa,ListLb,List&Lc){

//本算法将非递减的有序表A和B归并为C}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);91第九十一页，共104页。//La和Lb均非空，i=j=1,k=0GetElem(La,i,&ai);GetElem(Lb,j,&bj);

if(ai<=bj){//将ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//将bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}92第九十二页，共104页。

while(i<=La_len){//当La不空时

GetElem(La,i++,&ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//当Lb不空时

GetElem(Lb,j++,&bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素93讲义上的例子（图2-22以及程序）是用线性链表实现的算法第九十三页，共104页。94LinkListA,B;……LinkListC;twoLinkList2(A,B,&C)；第九十四页，共104页。95（2）使用现有节点—链表：第九十五页，共104页。96voidtwoLinkList1(LinkListLa