第3章 链表及其应用

回顾：顺序表的特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先分配空间需按最大空间分配，利用不充分;表容量难以扩充。讨论：在线性排列的一组数据元素中插入和删除数据元素时可不可以不移动元素？答：可以！引入另一种数据结构——链表。1第3章链表及其应用☞

3.1链表的基本概念

3.2单链表的数据结构

3.3单链表的基本运算实现

3.4循环链表

3.5链表的应用

23.1链表的基本概念☞

3.1.1什么是链表

3.1.2链表的逻辑结构

3.1.3链表的存储结构

3.1.4静态链表和动态链表

3.1.5链表的基本运算3☻什么是链表

☞链表是满足下列条件的一种数据结构：

⑴是有限个具有相同数据类型的数据元素的集合，

D={ai|i=1，2，…，n，n≥0，ai为数据元素⑵数据元素之间的关系R={<ai-1,ai>|ai-1,ai∈Di=2，3，…，n，n≥0}；⑶数据元素ai-1、ai（i=2，3，…，n，n≥0）在存储器中占用任意的、连续或不连续物理存储区域。43.1链表的基本概念

3.1.1什么是链表☞

3.1.2链表的逻辑结构

3.1.3链表的存储结构

3.1.4静态链表和动态链表

3.1.5链表的基本运算5♣

链表的逻辑结构

☞同一链表中所有数据元素的数据类型必须相同。

☞链表中相邻的元素ai-1、ai间存在序偶关系，即对于非空的链表，ai-1是ai的唯一直接前驱，ai＋1是ai的唯一直接后继；而a1无前驱，an无后继

☞链表属于线性逻辑结构。63.1链表的基本概念

3.1.1什么是链表

3.1.2链表的逻辑结构☞

3.1.3链表的存储结构

3.1.4静态链表和动态链表

3.1.5链表的基本运算7♣

链表的存储结构

☞

用一组任意的存储单元来存放表中的元素，这使得链表中数据元素的逻辑顺序与其物理存储顺序不一定相同；

☞为确保表中数据元素间的线性逻辑关系，在存储每一个数据元素的同时，存储其逻辑后继的存储地址；

8♣链表的存储结构

……

☞

ai的值与ai＋1的存储地址共同组成了链表中的一个结点：datanext其中：data域是数据域，用来存放数据元素ai的值；

next域是指针域，用来存放ai的直接后继ai＋1的存储地址。☞

链表正是通过每个结点的指针域将表中n个数据元素按其逻辑顺序链接在一起的。9【例】设有一组线性排列的数据元素（zhao,qian,sun,li,zhou,wu,zheng,wang），其链接存储形式如图所示：存储地址数据域指针域………………………………………zhaolizhouzhengqianwang100sunwu160170200210220310320320210160310200220100∧10讨论：在该存储方式下，如何找到表中任一元素？答：在链接存储方式下（链表中），每一个数据元素的存储地址是存放在其直接前驱结点的next域中，只要知道第一个数据元素（结点）zhao的存储地址，就可以“顺藤摸瓜”找到其后续的所有结点。

另外：链表中的最后一个数据元素无后继，则最后一个结点（尾结点）的指针域为空。

11通常情况下，我们用箭头来表示指针域中的指针，忽略每一个结点的实际存储位置，而重点突出链表中结点间的逻辑顺序，将链表直观地画成用箭头链接起来的结点序列。zhaozhouzhengqianlisunwuwang∧123.1链表的基本概念

3.1.1什么是链表

3.1.2链表的逻辑结构

3.1.3链表的存储结构☞

3.1.4静态链表和动态链表

3.1.5链表的基本运算13

☞静态链表

静态链表是用地址连续的存储空间(一般使用计算机语言中的“数组”)存储链表中的元素，及其逻辑后继在数组中的位置。与顺序表不同的是，在静态链表中逻辑位置相邻的元素其物理位置不一定相邻。14

【例】如图所示的静态链表。该链表存储在一个数组空间中，该数组为结构类型，每一个数组元素包括两个分量(也可以是多个分量)：存放表中元素值的data分量和存放该元素直接后继位置的next分量。15我们可以用结构体来定义静态链表的节点数据类型：

typedef

struct{

Datatypedata；

intnext；

}node；一个静态链表可以描述为：

#definemaxsize100nodenodepool[maxsize]；//存放链表的数组

inthead； //放头指针的head

在静态链表中进行插入与删除操作不需要移动元素，只需改变被插入(删除)元素的直接前驱的next域中的值。16☞动态链表

由于静态链表需要事先估计表中数据元素的个数，通常情况下，我们可以为链表中的每一个数据元素分配相应的存储空间.

该存储空间中存放有该数据元素的值(data域)和其直接后继的存储空间地址(next域)，数据元素之间的逻辑关系由每一个这样的存储空间中所存储的地址来维系。我们称这样的链表为动态链表。我们在本章后续所讨论的链表都是动态链表。173.1链表的基本概念

3.1.1什么是链表

3.1.2链表的逻辑结构

3.1.3链表的存储结构

3.1.4静态链表和动态链表☞

3.1.5链表的基本运算18我们可以定义链表的以下6种基本运算：（1）置空表LLsetnull(L)

运算的结果是将链表L置成空表。（2）求表长LLlength(L)

运算结果是输出链表中数据元素的个数。（3）按序号取元素LLget(L,i)

当1≤i≤length(L)时，输出链表L中第i个结点的值或其地址。19（4）按值查找（定位）LLlocate(L,x)

当链表L中存在值为x的结点时，输出该元素的地址。若表L中存在多个值为x的结点，则依次输出它的所有地址；当表中不存在值为x的结点时，则输出空指针。（5）插入LLinsert(L,i,x)

在链表L中的第i位置插入值为x的结点，表长由n变为n+1。20（6）删除LLdelete(L,i)

在链表L中删除第i个结点，表长由n变为n-1。

在解决具体问题时，所需要的运算可能仅是上述运算中的一部分，也可能需要更为复杂的运算。对于复杂运算，可通过上述6种基本运算的组合来实现。21第3章链表及其应用

3.1链表的基本概念☞

3.2单链表的数据结构

3.3单链表的基本运算实现

3.4循环链表

3.5链表的应用

22定义

单链表是满足下列条件的一种数据：⑴是有限个具有相同数据类型的数据元素组成的链表；⑵该链表的每个结点只有一个指针域。23单链表中的每一个结点包括两个域：♣

存储该结点所对应的数据元素信息的data域

——数据域♣存储其直接后继的存储位置的next域

——指针域datanext24该结点的数据类型用C语言描述为：

typedef

structnode{DataTypedata;

structnode*next;}LinkList

；可以定义一个该类型的指针变量：LinkList*H；datanext25zhaozhouqianlisunzhengwuwang∧H称H为该单链表的头指针。若已知单链表的头指针，则可以搜索到表中任一结点；也就是说，单链表由头指针唯一确定。因此，单链表可以用头指针的名字来命名。上图所示的单链表可称为单链表H。若有：26注意：严格区分指针变量和结点变量

☞

对于上例，H为指针变量；若它的值非空，则它的值为linklist类型的某结点的地址；

☞

若H非空，*H为LinkList类型的结点变量，它有两个分量：(*H).data

和(*H).next

或者写成H->data和H->next其中：(*H).data为DataType类型的变量，若它的值非空，其值为该数据元素ai的值；

(*H).next是与H同类型的指针变量，其值为ai的直接后继ai+1的地址。

27上图所示的单链表H，表中各结点的地址及数据元素值分别表示为：

结点1的地址：H数据元素a1值：H->data

结点2的地址：H->next

数据元素a2值：H->next->data若令p=H->next

：

则数据元素a2值为：p->data

结点3的地址：p->next；

pa1a2a4a5a3∧H28再令p=p->next，

数据元素a3值：p->data

结点4的地址：p->next；pa1a2a4a5a3∧Hp29再令p=p->next

数据元素a4值：p->data

结点5的地址：p->next；pa1a2a4a5a3∧H再令p=p->next，

数据元素a5值：p->data

结点5无后继结点，则p->next=NULL。pa1a2a4a5a3∧Hp30

♣

可以看出：若有LinkList*p＝H->next（或LinkList*p＝H），则除第一个结点外，其余结点的地址、数据元素值均有一致的表述方式，分别为

p->next

p->data

♣为使单链表中所有结点都有一致的描述方式，不妨在第一个结点之前加一个同类型的结点，并称该结点为头结点。anaiai+1ai-1a1a2∧H31anaiai+1ai-1a1a2∧H

♣头结点的data域中不存放任何内容，或者存放表长信息；

♣

头结点的next域中存放第一个数据元素结点的地址，而指针H记录头结点的地址。♣

我们称这样的单链表为带头结点的单链表。

在带头结点的单链表中，我们称第一个数据元素结点为首元素结点，称最后一个数据元素结点为尾结点。头指针头结点首元素结点尾结点32何谓头指针、头结点和首元结点？头指针是指向链表中第一个结点（或为头结点或为首元素结点）的指针。

单链表可由一个头指针唯一确定。头结点是在链表的首元素结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元素结点是指链表中存储线性表第一个数据元素a1的结点。

头指针头结点首元素结点a133答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元素结点之前附设的一个结点，该结点的数据域中不存储数据元素的值，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元素结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点34第3章链表及其应用

3.1链表的基本概念

3.2单链表的数据结构☞

3.3单链表的基本运算实现

3.4循环链表

3.5链表的应用

353.3单链表的基本运算实现☞

3.3.1带头结点的单链表的基本运算实现

3.3.2单链表的运算效率分析

3.3.3单链表的建立和输出361、置空表LLsetnull(L)

∧L没有元素，仅有头结点即：L->next=NULL(空）算法：

LinkList*LLsetnull(LinkList*L){L->next=NULL;return(L);}372、求表长LLlength(L)a1a2a3anL∧P难点分析：每个数据元素在内存中是“零散”存放的，怎么查询数据元素的个数？实现思路：从头结点开始，顺着各个结点next域中记录的地址，依次访问各结点，直到遇到某结点的next的值为空（NULL）为止。38流程图：p=L－>nextn=0n=n+1p=p－>nextYp=NULLNa1a2a3anL∧P39int

LLlength(LinkList*L){

//求带头结点的单链表L的长度

LinkList*p;intn;p=L->next;n=0;//用来存放单链表的长度

while(p!=NULL){p=p->next;n++;}returnn;}算法描述如下：403、取第i个元素LLget(L,i）思路：要取第i个数据元素，关键是要先找到该结点的指针p，然后输出该结点的地址p，或输出该数据元素的值p->data均可。难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取。a1a2a3anL∧P41方法：从单链表的头指针L出发，从首元素结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向首元素结点，用j做计数器，累计当前扫描过的结点数（初值为1），当j=i时，指针p所指的结点就是要找的第i个结点。a1a2a3anL∧P42流程图：j=ip=NULL

Np=p－>next；j++;Np=L－>next；j=1;YY所找的结点不存在返回pa1a2a3anL∧P43算法描述：LinkList*Get(LinkList*L,inti){//在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置;否则返回NULL

intj；LinkList*p；p=L->next；

j=1；

//从首元素结点开始扫描

while(p!=NULL&&j<i){p=p->next；//扫描下一结点

j++；//已扫描结点计数器

}if（i==j）returnp；//找到了第i个结点

elsereturnNULL；//找不到，i≤0或i>n

}444、查找LLlocate(L,x)在表L中查找值为x的结点的地址思路：从单链表的头指针指向的头结点出发（或者从首元素结点出发），顺着链逐个将结点的值和给定值x作比较。若有结点值等于x的结点，则返回首次找到的其值为x的结点的存储位置，否则返回NULL。

a1a2a3anL∧P45流程图：p=NULLp->data=xNp=p－>nextNp=L－>nextYY返回pa1a2a3anL∧P所找的结点不存在46算法描述：LinkList*LLlocate(LinkList*L,DataTypex){//在带头结点的单链表L中查找其结点值等于X的结点，若找到则返回该结点的位置p；否则返回NULL

LinkList

*p;p=L->next;//从表中第一个结点比较

while(p!=NULL)if(p->data!=x)p=p->next;elsebreak;//找到值为x的结点，

退出循环

returnp;}475.单链表的插入LLinsert(L,i,x)

在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x结点应预先生成：S=(LinkList)malloc(m);S->data=x;48插入条件：

1≤i≤n+1

即：可在a1前，或an后插入也就是说，要求第i–1位置不空即：get(L,i-1)≠NULL(空）

49流程图：p=get(L,i–1)

p=NULL

S=malloc(sizeof(linklist))S－>data=xS－>next=p－>nextP－>next=SNY50voidLLinsert(LinkList*L,inti,DataTypex){//在带头结点的单链表L中第i个位置插入值为x的新结点

LinkList*p,*s;p=get(L,i-1);//在第i个元素之前插入，则先找到第i-1个数据元素的存储位置,使指针p指向它

if(p!=NULL){s=malloc(sizeof(LinkList));

//为e申请一个新的结点并由s指向它

s->data=x;//将待插入结点的值x赋给s的数据域

s->next=p->next;//完成插入操作

p->next=s;;}}516.单链表的删除LLdelete(L,i)

在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q=p->next;/*保存b的指针，靠它才能指向c*/p->next=q->next;/*

a、c两结点相连*/free(q)；

/*

删除b结点，彻底释放*/p->next思考：省略free(q)语句行不行？(p->next)->next××52删除条件:

1≤i≤n

即：结点ai-1不空，且不是尾结点。

即：若p＝get(L,i-1)，则p≠NULL

且p->next≠NULL53voidLLdelete(LinkList*L,inti){

//在带头结点的单链表L中删除第i个结点LinkList*p,*q;p=get(L,i-1);//删除第i个结点，则先找到第i-1个结点的存储位置,使指针p指向它

if(p!=NULL&&p->next!=NULL){//第

i-1个结点和第i个结点均存在

q=p->next;p->next=q->next;

free(q)；

}}543.3单链表的基本运算实现

3.3.1带头结点的单链表的基本运算实现☞

3.3.2单链表的运算效率分析

3.3.3单链表的建立和输出55链表的运算效率分析（1）查找包括按序号查找LLget()和按值查找LLlocate()，因单链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。☞

时间效率分析（2）插入和删除因单链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。

但在单链表中进行插入或删除操作时，要调用LLget()函数，该函数的时间复杂度为O(n)，这使得插入或删除操作所耗时间复杂度为

O(n)。56☞

空间效率分析

单链表中每个结点都要增加一个指针空间，相当于总共增加了n个整型变量，空间复杂度为

O(n)。573.3单链表的基本运算实现

3.3.1带头结点的单链表的基本运算实现

3.3.2单链表的运算效率分析☞

3.3.3单链表的建立和输出581、头插法建立单链表实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将该结点插入到头结点后（首元素结点前）。59建表过程如图所示:

L=malloc(sizeof(LinkList));L->next=NULL;60scanf(“%d”,&x);S=malloc(sizeof(LinkList));S->data=x;S->next=NULL;61L->next=S;62while(条件

){

scanf(“%d”,&x);S=malloc(sizeof(LinkList));S->data=x;S->next=L->next;L->next=S;}63LinkList*SetList(){

//字母链表的生成，要一个一个链入LinkList*L,*S;inti;L=malloc(sizeof(LinkList));S=malloc(sizeof(LinkList));L->next=S;

S->next=NULL;

for(i=0;i<25;i++){

S->data=‘z’-i;//倒数第一个结点值为字符zS=malloc(sizeof(LinkList));S->next=L->next;L->next=S;}S->data=‘z’-i;//插入第一个结点字符areturnL;}

642.单链表的输出实现思路：顺着头指针，从第一个结点开始，“顺藤摸瓜”，直到最后一个结点（其next域为空）。算法：

voiddisplay(LinkList*head){//字母链表的输出

p=head->next;

while(p!=NULL){

printf("%c",p->data);

p=p->next;//只要没到最后一个元素，就不停地向后搜索

}

}65第3章链表及其应用

3.1链表的基本概念

3.2单链表的数据结构

3.3单链表的基本运算实现☞

3.4循环链表

3.5链表的应用

663.4循环链表☞

3.4.1单循环链表

3.4.2双向循环链表67讨论1：单链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可(P->next=L;)。这种形成环路的单链表称为单循环链表。a1Lanaip68特别地：带头结点的空循环链表样式

单循环链表的特点：

1、从任一结点出发均可找到表中其他结点。

2、操作仅有一点与单链表不同：结束循环的条件单链表-----p=NULL或p->next=NULL

循环链表-----p=L或p->next=LL这时：L－>next=L69带尾指针的单循环链表：a1anaiRR空表：这时：R－>next=R这时：头指针为：

R－>next70例：两个带尾指针的循环链表首尾相接思路:(1)将b1的地址存放在an的next域中，同时注意不可以丢掉链表A的头指针；

(2)应记录完成后的链表的头指针或尾指针。a1aianAb1bibnB实现:(1)用指针变量u记录链表A的头指针；

(2)将b1的地址存放在an的next域中；

(3)记下链表B的尾指针，并释放其头结点。u71a1aianAb1bibnBu(A)步骤:(1)u=A－>next(2)A－>next=B－>next－>next(3)free(B－>next)(4)B－>next=u(5)A=B723.4循环链表

3.4.1单循环链表☞

3.4.2双向循环链表

73讨论2：单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可。这种有两个指针的链表称为双向链表。La1anai74☞

双向链表中的指针域next和prior分别记录其前驱、后继结点的地址。priordatanext☞结点数据类型描述：typedef

struct

dnode{

datatypedata;

struct

dnode*prior,*next;}

Dlinklist;75☞

带头结点的空双向链表样式：L这时：L－>next=L－>prior=L☞

双向链表中的运算，基本上同单链表。这里，重点介绍插入和删除运算：插入：包括前插和后插

前插：在*p结点前插入新结点

后插：在*p结点后插入新结点76后插：ai-1paiai+1插入方法同单链表。xsx插入过程：ai+1aipai-177(4)p－>prior=s(3)p－>prior－>next=s(1)s－>prior=p－>prior(2)s－>next=pxspai-1aiai+1p->prior

前插：78删除：删除结点*ppaiai+1ai-1p－>prior－>next=p－>next;

p－>next－>prior=p－>prior;free(p);p－>priorp－>next79第3章链表及其应用

3.1链表的基本概念

3.2单链表的数据结构

3.3单链表的基本运算实现

3.4循环链表☞

3.5链表的应用

803.5链表的应用☞

3.5.1多项式相加问题

3.5.2两个链表的归并问题

3.5.3链表在字符处理方面的应用

——链串81☞一元多项式的表示通常，一个n次一元多项式P(x)可按升幂的形式写成：

P(x)=a0+a1x+a2x2+…+anxn

它实际上包含n+1项，由n+1个系数唯一确定。在计算机内，我们可以用一个链表来表示一个一元多项式。为了节省存储空间，我们只存储多项式中系数非0的项。链表中的每一个节点存放多项式的一个系数非0项，它包含三个域，分别存放该项的系数、指数以及指向下一多项式项节点的指针。82下图所示为该节点的结构：该节点的数据类型如下：typedef

struct

Pnode{

int

coef；

intexp；

struct

Pnode*next；}Polynode；83例如：多项式P=3+4x+6x3+8x7+23x21的单链表表示形式如下图所示：为方便以后的运算，我们也在该单链表中增加了头节点，并给定指数值为-1。84☞

两个一元多项式相加

两个多项式相加的法则是：两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多项式”中的一项；所有指数不同的项均直接移位至“和多项式”中。85【例】

两个一元多项式A(x)=2+5x+9x8+5x17，B(x)=10x+22x6-9x8，分别用单链表表示，试描述其相加的过程。

A-1028915175∧pB-11106228-9∧q指针p、q指向多项式链表A、B的首元素结点，并令指针pre=A;pre86A-1028915175∧pB-11106228-9∧qpp->exp<

q->exp，指针p、pre后移：即：pre=p,p=p->next此时p->exp=q->exp，则将*p和*q结点的系数相加：

p->coef=p->coef+q->coefprepreB若约定相加的结果用单链表A表示，则free(B)，且B=q；87A-102891175∧B1106228-9∧qp15qB指针q后移，即：q=q->next，同时free(B)，且B=q；prep->exp<q->exp，指针p、pre后移：即：pre=p,p=p->nextppre88A-102891175∧6228-9∧15qBp->exp>

q->exp，应将*q插入到*p结点前：

q=q->next；

B->next=p；

pre->next=B；pre=B；

B=q；ppreq××Bpre8989175∧6228-9∧A-102115Bppreq此时p->exp=

q->exp，则将*p和*q结点的系数相加：

p->coef=p->coef+q->coef9080175∧6228-9∧A-102115Bppreq但相加后p->coef=0；需要将结点*p从链表A中删除：

pre->next=p->next；

free(p)；

p=pre->next；指针q后移，即：q=q->next，同时free(B)，且B=q；qBp此时q=NULL，算法结束。91综合以上分析，两个一元多项式相加的算法如下：Polynode*polyadd(Polynode*A，Polynode*B){//两个多项式相加，将和多项式存放在多项式A中，并将多项式B删除

Polynode*p，*q，*temp，*pre；

intsum；

p=A->next；

q=B->next//p和q分别指向A和B多项式链表中的第一个节点

pre=A； //pre指向*p的前趋节点

free(B)； //释放多项式B的头节点空间92

while(p!=NULL&&q!=NULL){//当两个多项式均未扫描结束时

if(p->exp<q->exp){pre=p；p=p->next；

}//如果p指向的多项式项的指数小于q的指数，指针p后移

elseif(p->exp==q->exp){//若指数相等，则相应的系数相加sum=p->coef+q->coef

；

if(sum!=0){ p->coef=sum；B=q；pre=p；

p=p->next；q=q->next；

free(B)； //释放原先的*q节点空间

}93

else{temp=p；p=p->next；pre->next=p；free(temp)；

B=q；q=q->next；free(B)；//若系数和为零，则删除节点*p与*q，并将指针指向下一个节点

}else{//若p->exp>q->exp，将*q节点插入到多项式A中*p节点前 B=q；q=q->next；B->next=p；pre->next=B；

pre=pre->next；

}}94

if(q!=NULL)pre->next=q；

//若多项式B中还有剩余，则将剩余的节点加入到和多项式A中

return(A)；

}

若多项式A有n项，多项式B有m项，则上述算法的时间复杂度为953.5链表的应用

3.5.1多项式相加问题☞

3.5.2两个链表的归并问题

3.5.3链表在字符处理方面的应用

——链串96两个链表的归并

若将多项式链表A、B中的每个节点的系数域去掉，并修改上节中的一元多项式相加算法，则可形成两个链表的归并操作算法。97【例】有两个有序表A=(0,1,8,17)，B=(1,6,8)，将它们归并为一个有序表。0

p->data<q->data，令指针p后移；1∧1781∧86BApqpp->data＝q->data，应将*q节点插入到链表A中的*p节点之前qpqqp->data<q->data，令指针p后移p->data>q->data，应将*q节点插入到链表A中的*p节点之前p->data=q->data，应将*q节点插入到链表A中的*p节点之前q=NULL，则链表A即归并后的链表98算法分析：算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。99两个有序链表归并的算法可以描述为：

LinkList*Lmerge(LinkList*A，LinkList*B){

LinkList*p，*q，*pre；

p=A->next；

q=B->next；//p和q分别指向链表A和B中的第一个节点

pre=A； //pre指向*p的前趋节点

free(B)； /释放链表B的头节点空间

while(p!=NULL&&q!=NULL){//当两个链表均未扫描结束时

if(p->data<q->data){pre=p；p=p->next；}//如果*p节点的data值小于*q的data值，指针p后移

100

else{//否则，将*q节点插入到链表A中*p节点前

B=q；q=q->next；

B->next=p；pre->next=B；pre=pre->next；

}}

if(q!=NULL)pre->next=q；

//若链表B中还有剩余，则将剩余的节点插入到链表A的表尾

return(A)；

}1013.5链表的应用

3.5.1多项式相加问题

3.5.2两个链表的归并问题☞

3.5.3链表在字符处理方面的应用

——链串102链串是满足下列条件的一种数据结构：⑴由0个或多个字符组成的有限序列；一般记为：S=“a1...ai...an”，i=1，2，…，n。⑵字符之间的关系R={<ai，ai＋1>|ai，ai＋1∈S}。⑶相邻字符ai、ai＋1在存储器中不一定占用相邻的物理存储单元。其中ai(1≤i≤n)是单个字符，可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度。

链串的概念：103

在许多系统中，当一个字符占用一个字节空间的情况时，而链表节点中指针域要占用多个字节存储空间。这样，普通链串(如图所示的每个节点只有一个字符的链串)空间利用率非常低。其节点类型可描述为：typedef

structnode{chardata；structnode*next；}LinkString；

链串的存储结构

：104

为了提高存储密度，可以让每个节点存放多个字符，也称这种存储结构为块链结构，相应的链串称为块链串，而块链串中每个节点最多能存放的字符的个数称为节点的大小。下图所示的是节点大小为4的块链串。105块链结构中，结点类型描述为：

#define