数据结构简明教程（第3版）课件 第2章 线性表(下)

第2章线性表2.1线性表的基本概念2.2顺序表2.3单链表和循环单链表2.4双链表和循环双链表2.5线性表的应用第2章线性表1/592.4双链表和循环双链表2.4.1双链表的定义

双链表中用两个指针表示结点间的逻辑关系。指向其前驱结点的指针域prior。指向其后继结点的指针域next。2.4双链表和循环双链表2/59仍假设数据元素的类型为ElemType。双链表的类型声明如下：typedefstructnode{ElemTypedata; //数据域

structnode*prior,*next; //分别指向前驱结点

//和后继结点的指针}DLinkNode;

//双链表结点类型2.4双链表和循环双链表3/59与单链表一样，双链表也分为非循环双链表（简称为双链表）和循环双链表两种。除特别指出外，本章所指的双链表均指带头结点的双链表。2.4双链表和循环双链表4/592.4.2线性表基本运算在双链表上的实现在带头结点的双链表中，通常头结点的数据域可以不存储任何信息，尾结点的next域置为NULL。如下图所示是一个带头结点的双链表。La1a2an∧…priornext2.4双链表和循环双链表5/591.双链表基本运算算法（1）初始化线性表运算算法创建一个空的双链表，它只有一个头结点，由L指向它，该结点的next域和prior域均为空，data域未设定任何值。voidInitList(DLinkNode*&L){L=(DLinkNode*)malloc(sizeof(DLinkNode));

//创建头结点LL->prior=L->next=NULL;}2.4双链表和循环双链表6/59（2）销毁线性表运算算法销毁一个双链表中的所有结点的算法思路与单链表的销毁算法相同。voidDestroyList(DLinkNode*&L){DLinkNode*pre=L,*p=pre->next;

while(p!=NULL)

{ free(pre); pre=p;p=p->next; //pre、p同步后移}

free(pre);}2.4双链表和循环双链表7/59（3）求线性表长度运算算法其设计思路与单链表的求表长算法完全相同。intGetLength(DLinkNode*L) {inti=0;

DLinkNode*p=L->next; //p指向第一个数据结点

while(p!=NULL)

{ i++; //i累加数据结点个数

p=p->next;

}

returni;}2.4双链表和循环双链表8/59（4）求线性表中第i个元素运算算法其设计思路与单链表的求线性表中第i个元素运算算法完全相同。intGetElem(DLinkNode*L,inti,ElemType&e){intj=0;

DLinkNode*p=L; //p指向头结点，计数器j置为0

if(i<=0)return0; //参数i错误返回0

while(p!=NULL&&j<i)

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

}

if(p==NULL)return0; //未找到返回0

else

{ e=p->data; return1; //找到后返回1

}}2.4双链表和循环双链表9/59（5）按值查找运算算法其设计思路与单链表的按值查找运算算法完全相同。intLocate(DLinkNode*L,ElemTypee) {DLinkNode*p=L->next;

inti=1; //p指向第一个数据结点，i置为其序号1

while(p!=NULL&&p->data!=e)

{ p=p->next; i++;

}if(p==NULL)return0; //未找到返回0

elsereturni; //找到后返回其序号}2.4双链表和循环双链表10/59（6）插入元素运算算法先在双链表中查找到第i-1个结点，若成功找到该结点（由p所指向），创建一个以x为值的新结点s，将s结点插入到p之后即可。2.4双链表和循环双链表11/59在双链表中p结点之后插入s结点的操作步骤如下：将结点s的next域指向结点p的下一个结点（s->next=p->next）。若p不是最后结点（若p是最后结点，只插入s作为尾结点），则将p之后结点的prior域指向s（p->next->prior=s）。将s的prior域指向p结点（s->prior=p）。将p的next域指向s（p->next=s）。ps①②④③2.4双链表和循环双链表12/59intInsElem(DLinkNode*&L,ElemTypex,inti){intj=0;

DLinkNode*p=L,*s;

if(i<=0)return0; //参数i错误返回0

while(p!=NULL&&j<i-1) //查找第i-1个结点p

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

}

if(p==NULL)return0; //未找到返回0

else

{ s=(DLinkNode*)malloc(sizeof(DLinkNode)); s->data=x; //创建一个存放元素x的新结点

s->next=p->next; //对应插入操作的步骤①

if(p->next!=NULL) //对应插入操作的步骤②

p->next->prior=s; s->prior=p; //对应插入操作的步骤③

p->next=s; //对应插入操作的步骤④

return1; //插入运算成功,返回1

}}2.4双链表和循环双链表13/59在双链表中也可以通过一个结点找到其前驱结点，所以插入操作也可以改为：在双链表中找到第i个结点p，然后在p结点之前插入新结点。2.4双链表和循环双链表14/59（7）删除结点运算算法先在双链表中查找到第i个结点，若成功找到该结点（由p所指向），通过前驱结点和后继结点的指针域改变来删除p结点。2.4双链表和循环双链表15/59在双链表中删除p结点（其前驱结点为pre）的操作：

若p不是尾结点，则将其后继结点的prior域指向pre结点:

p->next->prior=pre将pre结点的next域改为指向p结点的后继结点: pre->next=p->nextprep①②2.4双链表和循环双链表16/59intDelElem(DLinkNode*&L,inti) //删除结点{intj=0;

DLinkNode*p=L,*pre;

if(i<=0)return0; //参数i错误返回0

while(p!=NULL&&j<i) //查找第i个结点p

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

}

if(p==NULL)return0; //未找到第i个结点时返回0

else

{ pre=p->prior; //pre指向被删结点的前驱结点

if(p->next!=NULL) //从单链表中删除p结点

p->next->prior=pre; pre->next=p->next; free(p); //释放其空间

return1;

}}2.4双链表和循环双链表17/59（8）输出线性表运算算法其设计思路与单链表的输出元素值运算算法完全相同。voidDispList(DLinkNode*L){DLinkNode*p=L->next;

while(p!=NULL)

{ printf("%d",p->data); p=p->next;

}

printf("\n");}2.4双链表和循环双链表18/592.整体创建双链表的算法（1）头插法建表从一个空双链表（含有一个L指向的头结点）开始。读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到新结点的数据域中。然后将新结点s插入到当前链表的表头上。再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到双链表L中，直到数组a中所有元素读完为止。2.4双链表和循环双链表19/59voidCreateListF(DLinkNode*&L,ElemTypea[],intn){DLinkNode*s;inti;

L=(DLinkNode*)malloc(sizeof(DLinkNode));

//创建头结点

L->next=NULL;

for(i=0;i<n;i++){s=(DLinkNode*)malloc(sizeof(DLinkNode));//创建新结点

s->data=a[i];

s->next=L->next; //将s插入到头结点之后

s->prior=L;

if(L->next!=NULL) //若s不是作为尾结点插入

L->next->prior=s;

L->next=s;

}}2.4双链表和循环双链表20/59（2）尾插法建表从一个空双链表（含有一个L指向的头结点）开始。读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到新结点的数据域中。然后将新结点s插入到当前链表的表尾上。再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到双链表L中，直到数组a中所有元素读完为止。2.4双链表和循环双链表21/59voidCreateListR(DLinkNode*&L,ElemTypea[],intn){DLinkNode*s,*tc;inti;

L=(DLinkNode*)malloc(sizeof(DLinkNode));//创建头结点

tc=L; //tc始终指向尾结点,开始时指向头结点

for(i=0;i<n;i++)

{ s=(DLinkNode*)malloc(sizeof(DLinkNode));//创建新结点

s->data=a[i]; tc->next=s; //将s插入tc之后

s->prior=tc; tc=s;

}

tc->next=NULL; //尾结点next域置为NULL}2.4双链表和循环双链表22/59

【例2.22】假设一个整数序列用双链表L存储，设计一个算法删除其中最大值的结点。2.4双链表2.4.3双链表的算法设计示例

用p遍历双链表L，用maxp保存找到的第一个最大值的结点（初值为p）。最后通过其前驱结点pre和后继结点post删除maxp结点并释放其空间。23/59void

Delmax(DLinkNode*&L){DLinkNode*p=L->next,*maxp=p,*pre,*post;

while(p!=NULL) //查找第一个最大值的结点maxp

{if(p->data>maxp->data)

maxp=p;

p=p->next;

}

pre=maxp->prior; //指向被删结点的前驱结点

post=maxp->next; //指向被删结点的后继结点

pre->next=post; //删除maxp结点

if(post!=NULL)post->prior=pre;

free(maxp); //释放其空间}2.4双链表和循环双链表24/59

【例2.18】设有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进行交换。2.4双链表和循环双链表

先找到第一个元素值为x的结点p，q指向其后继结点。先删除p结点，将p结点插入到q结点之后。25/59intSwap(DLinkNode*L,ElemTypex){DLinkNode*p=L->next,*q;

while(p!=NULL&&p->data!=x)p=p->next;

if(p==NULL) //未找到值为x的结点return0; //返回0

else

{q=p->next; //q指向p的后继结点

if(q!=NULL)

{p->prior->next=q; //先删除p结点

q->prior=p->prior;

p->next=q->next; //将p结点插入到q结点之后

if(q->next!=NULL) //若q结点存在后继结点

q->next->prior=p;

q->next=p;

p->prior=q;

return1;}

elsereturn0; //表示值为x的结点是尾结点

}}2.4双链表和循环双链表26/592.4.4循环双链表与循环单链表一样，也可以使用循环双链表。循环双链表的结点类型与双链表的结点类型相同，也采用前面声明的DLinkNode类型。2.4双链表和循环双链表27/59一个带头结点的有n个结点的循环双链表。表中尾结点的next域指向头结点，头结点的prior域指向尾结点，整个链表形成两个环。在循环双链表中，从任一结点出发都可以找到表中其他结点。特点：La1a2an…2.4双链表和循环双链表28/59（1）初始化线性表运算算法创建一个空的循环双链表，它只有一个头结点，由L指向它，该结点的next域和prior域均指向该头结点，data域未设定任何值。voidInitList(DLinkNode*&L){L=(DLinkNode*)malloc(sizeof(DLinkNode));

L->prior=L->next=L;}循环双链表基本运算算法2.4双链表和循环双链表29/59（2）销毁线性表运算算法销毁一个循环双链表中的所有结点的算法思路与循环单链表的销毁算法相同。voidDestroyList(DLinkNode*&L){DLinkNode*pre=L,*p=pre->next;while(p!=L)

{ free(pre); pre=p;p=p->next; //pre、p同步后移

}

free(pre);}2.4双链表和循环双链表30/59（3）求线性表长度运算算法其设计思路与循环单链表的求表长算法完全相同。intGetLength(DLinkNode*L) //求表长运算{inti=0;

DLinkNode*p=L->next;

while(p!=L)

{ i++; p=p->next;

}

returni;}2.4双链表和循环双链表31/59（4）求线性表中第i个元素运算算法其设计思路与循环单链表中求线性表中第i个元素运算算法完全相同。intGetElem(DLinkNode*L,inti,ElemType&e){intj=1;

DLinkNode*p=L->next; //p指向第一个数据结点，j置为1

if(i<=0)return0; //参数i错误返回0

while(p!=L&&j<i)

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

}

if(p==L)return0; //未找到返回0

else

{ e=p->data; return1;

//找到后返回1

}}2.4双链表和循环双链表32/59（5）按值查找运算算法其设计思路与循环单链表中按值查找运算算法完全相同。intLocate(DLinkNode*L,ElemTypex) {inti=1;

DLinkNode*p=L->next;

while(p!=L&&p->data!=x) //从第1个结点开始查找data域为x的结点

{ p=p->next; i++;

}

if(p==L)return0;

elsereturni;}2.4双链表和循环双链表33/59（6）插入元素运算算法先在循环双链表L中查找第i个结点p及其前驱结点pre，用j记录p结点的序号。当p==L且i>j+1时表示i参数错误（如循环双链表中只有3个结点，当i>4时出现这种错误）。当成功找到pre结点后，创建data域为x的结点s。在pre结点之后插入s结点。2.4双链表和循环双链表34/59intInsElem(DLinkNode*&L,ElemTypex,inti) {intj=0;

DLinkNode*pre=L,*p=pre->next,*s;

if(i<=0)return0; //参数i错误返回0

while(p!=L&&j<i-1) //查找第i个结点p和其前驱结点pre

{ j++; pre=p;p=p->next; //pre、p同步后移一个结点

}

if(p==L&&i>j+1)return0;//参数i>n+1时错误返回0

else

//成功查找到p结点的前驱结点pre

{ s=(DLinkNode*)malloc(sizeof(DLinkNode)); s->data=x; //创建新结点s用于存放元素x pre->next->prior=s; //将s结点插入到pre结点之后

s->next=pre->next; pre->next=s; s->prior=pre; return1; //插入运算成功,返回1

}}2.4双链表和循环双链表35/59（7）删除元素运算算法

先在循环双链表L中查找第i个结点p，若成功找到后通过其前驱结点pre将p结点删除。2.4双链表和循环双链表36/59intDelElem(DLinkNode*&L,inti)//删除结点算法{intj=1;

DLinkNode*p=L->next,*pre;

if(i<=0)return0; //参数i错误返回0

if(L->next==L)return0; //空循环双链表不能删除，返回0

while(p!=L&&j<i) //查找第i个结点p

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

}

if(p==L)return0; //未找到第i个结点返回0

else

{ pre=p->prior; //pre指向被删结点的前驱结点

p->next->prior=pre; pre->next=p->next; free(p); //释放其空间

return1;

}}2.4双链表和循环双链表37/59（8）输出线性表运算算法其设计思路与循环单链表的输出元素值运算算法完全相同。voidDispList(DLinkNode*L){DLinkNode*p=L->next;

while(p!=L)

{ printf("%d",p->data); p=p->next;

}

printf("\n");}2.4双链表和循环双链表38/59

【例2.24】设计一个算法将带头结点的循环双链表L的所有结点逆置。2.4.5循环双链表的算法设计示例2.4双链表和循环双链表

先建立一个空的循环双链表L，用p遍历余下的数据结点，依次将p结点采用头插法插入到L中。39/59voidReverse(DLinkNode*&L){DLinkNode*p=L->next,*q;

L->next=L->prior=L; //构造一个空的循环双链表

while(p!=L)

{ q=p->next; p->next=L->next; //将p结点插入到表头

L->next->prior=p; L->next=p; p->prior=L; p=q;

}}2.4双链表和循环双链表40/59

【例2.25】有一个带头结点的循环双链表L，其结点data域值为整数，设计一个算法，判断其所有元素是否对称。

如果从前向后读和从后向前读得到的数据序列相同，表示是对称的；否则不是对称的。

2.4双链表和循环双链表41/59

先让p指向第一个结点，q指向尾结点，当两者所指结点值不等时返回0，否则p后移一个结点，q前移一个结点，依次比较下去，直到p->next==q或p==q。循环结束后返回1。abbapq对称情况1：结点个数为偶数abapq对称情况2：结点个数为奇数2.4双链表和循环双链表42/59intSymmetric(DLinkNode*L){intflag=1;DLinkNode*p=L->next,*q=L->prior;while(flag==1) //flag为1时循环{if(p->data!=q->data) //对应结点值不同时退出循环flag=0;else{if(p==q||p->next==q)break; //是对称的情况p=p->next; //从前向后移动q=q->prior; //从后向前移动}}returnflag;}2.4双链表和循环双链表43/592.5线性表的应用2.5.1设计线性表应用程序的一般步骤当通过分析确定了求解问题中数据逻辑结构为线性关系时，设计线性表应用程序的一般步骤如下：

（1）根据求解功能的特点设计相应的存储结构。（2）设计相应的基本运算算法。（3）设计求解问题的主程序。2.5线性表的应用44/59两类存储结构特点的比较特点顺序存储结构链式存储结构优点（1）无须为表示线性表中元素之间的逻辑关系而增加额外的存储空间，存储密度大。（2）具有随机存储特性。（1）由于采用结点的动态分配方式，具有良好的适应性。（2）插入和删除操作只需修改相关指针域，不需要移动大量元素。缺点（1）插入和删除操作需要移动大量元素。（2）如果采用静态数组存储线性表元素，其空间大小分配难以掌握，大大了会浪费空间，分小了易发生上溢出；如果采用动态数组存储线性表元素，其算法设计比较复杂。（1）为表示线性表中元素之间的逻辑关系而需要增加额外的存储空间（指针域），存储密度小。（2）不具有随机存储特性。2.5线性表的应用45/592.5.2线性表应用示例假设一个多项式形式为，其中ei（1≤i≤m）为整数类型的指数，ci（1≤i≤m）为实数类型的系数。为了简便，假设每个多项式按指数递减排列，并且没有相同指数的多项式项。编写求两个多项式相加的程序。例如：两个多项式分别为：

p(x)=3.2x5+2x3-6x+10，q(x)=1.8x5-2.5x4-2x3+x2+6x-5，则相加后的结果为：

r(x)=p(x)+q(x)=5x5-2.5x4+x2+5。1.问题描述2.5线性表的应用46/59一个多项式由多个（1≤i≤m）多项式项组成，这些多项式项之间构成一种线性关系，所以一个多项式可以看成是由多个多项式项元素构成的线性表。线性表可以采用顺序表和各种链表存储，由于本例中每个多项式的项数难以确定，所以采用带头结点的单链表存储多项式。每个多项式项采用以下结点类型进行存储：coefexpnext2.设计存储结构2.5线性表的应用47/59

coef数据域存放系数ci；expn数据域存放指数ei；next域是一个链域，指向下一个结点。这样的单链表结点的类型声明如下：typedefstructnode{floatcoef;

//系数

intexp;

//指数

structnode*next;

//指向下一个结点的指针}PolyNode;2.5线性表的应用48/59例如，前面的两个多项式p(x)、q(x)的存储结构如下图所示。

p(x)=3.2x5+2x3-6x+103.252.03-6.0110.00∧p1.85-2.54-2.031.02-5.00∧6.01q(x)=1.8x5-2.5x4-2x3+x2+6x-5q2.5线性表的应用49/593.设计基本运算算法（1）建立多项式单链表由数组a指定系数，数组b指定指数，共有n个多项式项(a[0],b[0])，(a[1],b[1])，…，(a[n-1],b[n-1])构成一个多项式，其中指数按递减排列。2.5线性表的应用50/59voidCreateListR(PolyNode*&L,doublea[],intb[],intn){PolyNode*s,*tc;

inti;

L=(PolyNode*)malloc(sizeof(PolyNode));

tc=L; //tc始终指向终端结点,开始时指向头结点

for(i=0;i<n;i++)

{ s=(PolyNode*)malloc(sizeof(PolyNode)); s->coef=a[i]; s->exp=b[i]; tc->next=s; //将s插入tc之后

tc=s;

}

tc->next=NULL; //尾结点next域置为NULL}2.5线性表的应用51/59（2）销毁多项式单链表voidDestroyList(PolyNode*&L){PolyNode*pre=L,*p=pre->next;

while(p!=NULL)

{ free(pre); pre=p;p=p->next;

}

free(pre);}2.5线性表的应用52/59（3）输出多项式单链表voidDispPoly(PolyNode*L){PolyNode*p=L->next;

while(p!=NULL)

{ printf("(%gx^%d)",p->coef,p->exp); p=p->next;

}

printf("\n");}2.5线性表的应用53/59（4）两个有序多项式单链表相加运算对于ha和hb两个有序多项式单链表，采用二路归并实现多项式相加运算（产生有序单链表hc）的过程如下：2.5线性表的应用54/59pa指向ha的第一个数据结点，pb指向hb的第一个数据结点；创建hc的头结点，尾结点指针tc指向该头结点；while(pa、pb均不为空){if(pa->exp>pb->exp)由pa结点复制建立一个新结点s，将结点s链到hc末尾，pa后移一个结点；elseif(pa->exp<pb->exp)

由pb结点复制建立一个新结点s，将结点s链到hc末尾，pb后移一个结点；

else //两结点的指数相同求两结点的系数和c，若不为0，新建一个结点s，其coef域为c，

将结点s链到hc末尾，pa、pb均后移一个结点。}此时pa、pb中至少有一个为空，将另一个未扫描完的结点逐一复制并链接到hc末尾；置hc尾结点next域为空。2.5线性表的应用55/59voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc){PolyNode*pa=ha->next,*pb=hb->next,*s,*tc;

doublec;

hc=(PolyNode*)malloc(sizeof(PolyNode));

tc=hc;

while(pa!=NULL&&pb!=NULL)

{if(pa->exp>pb->exp)

{s=(PolyNode*)malloc(sizeof(PolyNode));

s->exp=pa->exp;s->coef=pa->coef;

tc->next=s;tc=s;

p