1.严蔚敏版《数据结构》习题集及参考答案.doc 113页

'严蔚敏版《数据结构（C语言版）》习题集以及参考答案第1章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.3设有数据结构(D,R)，其中，，试按图论中图的画法惯例画出其逻辑结构图。解：1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。解：ADTComplex{数据对象：D={r,i|r,i为实数}数据关系：R={}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C，其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C) 操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADTComplexADTRationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADTRationalNumber1.5试画出与下列程序段等价的框图。(1)product=1;i=1;while(i<=n){product*=i;i++;}(2)i=0;do{i++;}while((i!=n)&&(a[i]!=x));(3)switch{casexj)j++;elsei++;}(7)x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}(8)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)===(6)n(7)向下取整(8)11001.9假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。intTime(intn){count=0;x=2;while(x438时，1.14判断下列各对函数和，当时，哪个函数增长更快？(1)，(2)，(3)，(4)，解：(1)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快1.15试用数学归纳法证明：(1) (2)(3)(4)1.16试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值解：intmax3(intx,inty,intz){if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;}1.17已知k阶斐波那契序列的定义为，，…，，；，试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。解：k>0为阶数，n为数列的第n项intFibonacci(intk,intn){if(k<1)exit(OVERFLOW);int*p,x;p=newint[k+1];if(!p)exit(OVERFLOW);inti,j;for(i=0;iarrsize或对某个，使时，应按出错处理。注意选择你认为较好的出错处理方法。解：#include#include#defineMAXINT65535#defineArrSize100 intfun(inti);intmain(){inti,k;inta[ArrSize];cout<<"Enterk:";cin>>k;if(k>ArrSize-1)exit(0);for(i=0;i<=k;i++){if(i==0)a[i]=1;else{if(2*i*a[i-1]>MAXINT)exit(0);elsea[i]=2*i*a[i-1];}}for(i=0;i<=k;i++){if(a[i]>MAXINT)exit(0);elsecout<#include#defineN10doublepolynomail(inta[],inti,doublex,intn);intmain(){doublex;intn,i;inta[N];cout<<"输入变量的值x:";cin>>x;cout<<"输入多项式的阶次n:";cin>>n;if(n>N-1)exit(0); cout<<"输入多项式的系数a[0]--a[n]:";for(i=0;i<=n;i++)cin>>a[i];cout<<"Thepolynomailvalueis"<0)returna[n-i]+polynomail(a,i-1,x,n)*x;elsereturna[n];}本算法的时间复杂度为o(n)。第2章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2.2填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。2.3在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。解： 2.5画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode));P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++)Del_LinkList(L,i);解： 2.6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是__________________。b.在P结点前插入S结点的语句序列是__________________。c.在表首插入S结点的语句序列是__________________。d.在表尾插入S结点的语句序列是__________________。(1)P->next=S;(2)P->next=P->next->next;(3)P->next=S->next;(4)S->next=P->next;(5)S->next=L;(6)S->next=NULL;(7)Q=P;(8)while(P->next!=Q)P=P->next;(9)while(P->next!=NULL)P=P->next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是____________________。b.删除P结点的直接前驱结点的语句序列是____________________。c.删除P结点的语句序列是____________________。d.删除首元结点的语句序列是____________________。e.删除尾元结点的语句序列是____________________。(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next;}(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next;(12)P=L;(13)L=L->next;(14)free(Q); 解：a.(11)(3)(14)b.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e.(9)(11)(3)(14)2.8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是_______________________。b.在P结点前插入S结点的语句序列是_______________________。c.删除P结点的直接后继结点的语句序列是_______________________。d.删除P结点的直接前驱结点的语句序列是_______________________。e.删除P结点的语句序列是_______________________。(1)P->next=P->next->next;(2)P->priou=P->priou->priou;(3)P->next=S;(4)P->priou=S;(5)S->next=P;(6)S->priou=P;(7)S->next=P->next;(8)S->priou=P->priou;(9)P->priou->next=P->next;(10)P->priou->next=P;(11)P->next->priou=P;(12)P->next->priou=S;(13)P->priou->next=S;(14)P->next->priou=P->priou;(15)Q=P->next;(16)Q=P->priou;(17)free(P);(18)free(Q);解：a.(7)(3)(6)(12)b.(8)(4)(5)(13)c.(15)(1)(11)(18)d.(16)(2)(10)(18)e.(14)(9)(17)2.9简述以下算法的功能。(1)StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnOK;}(2)voidBB(LNode*s,LNode*q){ p=s;while(p->next!=q)p=p->next;p->next=s;}voidAA(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);}解：(1)如果L的长度不小于2，将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.10指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。StatusDeleteK(SqList&a,inti,intk){//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(i<1||k<0||i+k>a.length)returnINFEASIBLE;//参数不合法else{for(count=1;count=i+1;j--)a.elem[j-i]=a.elem[j];a.length--;}returnOK;}解：StatusDeleteK(SqList&a,inti,intk){//从顺序存储结构的线性表a中删除第i个元素起的k个元素//注意i的编号从0开始intj;if(i<0||i>a.length-1||k<0||k>a.length-i)returnINFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;returnOK;}2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解：StatusInsertOrderList(SqList&va,ElemTypex){//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法inti;if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0,xB.length?A.length:B.length;for(i=0;iB.elem[i])j=1;if(A.elem[i]k)j=1;if(B.length>k)j=-1;if(A.length==B.length)j=0;returnj;}2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);解：intLocateElem_L(LinkList&L,ElemTypex){inti=0;LinkListp=L;while(p&&p->data!=x){p=p->next;i++;}if(!p)return0;elsereturni;}2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。解：//返回单链表的长度intListLength_L(LinkList&L){inti=0;LinkListp=L; if(p)p=p-next;while(p){p=p->next;i++;}returni;}2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。解：voidMergeList_L(LinkList&ha,LinkList&hb,LinkList&hc){LinkListpa,pb;pa=ha;pb=hb;while(pa->next&&pb->next){pa=pa->next;pb=pb->next;}if(!pa->next){hc=hb;while(pb->next)pb=pb->next;pb->next=ha->next;}else{hc=ha;while(pa->next)pa=pa->next;pa->next=hb->next;}}2.16已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。StatusDeleteAndInsertSub(LinkedListla,LinkedListlb,inti,intj,intlen){if(i<0||j<0||len<0)returnINFEASIBLE;p=la;k=1;while(knext;k++;}q=p;while(k<=len){q=q->next;k++;}s=lb;k=1;while(knext;k++;}s->next=p;q->next=s->next; returnOK;}解：StatusDeleteAndInsertSub(LinkList&la,LinkList&lb,inti,intj,intlen){LinkListp,q,s,prev=NULL;intk=1;if(i<0||j<0||len<0)returnINFEASIBLE;//在la表中查找第i个结点p=la;while(p&&knext;k++;}if(!p)returnINFEASIBLE;//在la表中查找第i+len-1个结点q=p;k=1;while(q&&knext;k++;}if(!q)returnINFEASIBLE;//完成删除，注意，i=1的情况需要特殊处理if(!prev)la=q->next;elseprev->next=q->next;//将从la中删除的结点插入到lb中if(j=1){q->next=lb;lb=p;}else{s=lb;k=1;while(s&&knext;k++;}if(!s)returnINFEASIBLE;q->next=s->next;s->next=p;//完成插入}returnOK;}2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。解：StatusListDelete_L(LinkList&L,ElemTypemink,ElemTypemaxk){LinkListp,q,prev=NULL;if(mink>maxk)returnERROR;p=L;prev=p;p=p->next;while(p&&p->datadata<=mink){prev=p;p=p->next;}else{prev->next=p->next;q=p;p=p->next;free(q);}}returnOK;}2.20同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。解：voidListDelete_LSameNode(LinkList&L){LinkListp,q,prev;p=L;prev=p;p=p->next;while(p){prev=p;p=p->next;if(p&&p->data==prev->data){prev->next=p->next;q=p; p=p->next;free(q);}}}2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置为。解：//顺序表的逆置StatusListOppose_Sq(SqList&L){inti;ElemTypex;for(i=0;inext;L->next=NULL;while(p){q=p;p=p->next;q->next=L->next;L->next=q;}returnOK;}2.23设线性表，，试写一个按下列规则合并A，B为线性表C的算法，即使得当时； 当时。线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。解：//将合并后的结果放在C表中，并删除B表StatusListMerge_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A->next;pb=B->next;C=A;while(pa&&pb){qa=pa;qb=pb;pa=pa->next;pb=pb->next;qb->next=qa->next;qa->next=qb;}if(!pa)qb->next=pb;pb=B;free(pb);returnOK;}2.24假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。解：//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->datadata){qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa;}else{qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}2.25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。解：//将A、B求交后的结果放在C表中StatusListCross_Sq(SqList&A,SqList&B,SqList&C){inti=0,j=0,k=0;while(iB.elem[j])j++;else{ListInsert_Sq(C,k,A.elem[i]);i++;k++;}}returnOK; }2.26要求同2.25题。试对单链表编写求C的算法。解：//将A、B求交后的结果放在C表中，并删除B表StatusListCross_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;C=A;while(pa&&pb){if(pa->datadata){pt=pa;pa=pa->next;qa->next=pa;free(pt);}elseif(pa->data>pb->data){pt=pb;pb=pb->next;qb->next=pb;free(pt);}else{qa=pa;pa=pa->next;}}while(pa){pt=pa;pa=pa->next;qa->next=pa;free(pt);}while(pb){pt=pb;pb=pb->next;qb->next=pb;free(pt); }pb=B;free(pb);returnOK;}2.27对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。(1)假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用A表空间存放表C。解：(1)//A、B求交，然后删除相同元素，将结果放在C表中StatusListCrossDelSame_Sq(SqList&A,SqList&B,SqList&C){inti=0,j=0,k=0;while(iB.elem[j])j++;else{if(C.length==0){ListInsert_Sq(C,k,A.elem[i]);k++;}elseif(C.elem[C.length-1]!=A.elem[i]){ListInsert_Sq(C,k,A.elem[i]);k++;}i++;}}returnOK;}(2)//A、B求交，然后删除相同元素，将结果放在A表中StatusListCrossDelSame_Sq(SqList&A,SqList&B){inti=0,j=0,k=0;while(iB.elem[j])j++;else{if(k==0){ A.elem[k]=A.elem[i];k++;}elseif(A.elem[k]!=A.elem[i]){A.elem[k]=A.elem[i];k++;}i++;}}A.length=k;returnOK;}2.28对2.25题的条件作以下两点修改，对单链表重新编写求得表C的算法。(1)假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用原表（A表或B表）中的结点构成表C，并释放A表中的无用结点空间。解：(1)//A、B求交，结果放在C表中，并删除相同元素StatusListCrossDelSame_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;C=A;while(pa&&pb){if(pa->datadata){pt=pa;pa=pa->next;qa->next=pa;free(pt);}elseif(pa->data>pb->data){pt=pb;pb=pb->next;qb->next=pb;free(pt);} else{if(pa->data==qa->data){pt=pa;pa=pa->next;qa->next=pa;free(pt);}else{qa=pa;pa=pa->next;}}}while(pa){pt=pa;pa=pa->next;qa->next=pa;free(pt);}while(pb){pt=pb;pb=pb->next;qb->next=pb;free(pt);}pb=B;free(pb);returnOK;}(2)//A、B求交，结果放在A表中，并删除相同元素StatusListCrossDelSame_L(LinkList&A,LinkList&B){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;while(pa&&pb){if(pa->datadata){pt=pa;pa=pa->next; qa->next=pa;free(pt);}elseif(pa->data>pb->data){pt=pb;pb=pb->next;qb->next=pb;free(pt);}else{if(pa->data==qa->data){pt=pa;pa=pa->next;qa->next=pa;free(pt);}else{qa=pa;pa=pa->next;}}}while(pa){pt=pa;pa=pa->next;qa->next=pa;free(pt);}while(pb){pt=pb;pb=pb->next;qb->next=pb;free(pt);}pb=B;free(pb);returnOK;}2.29已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。解：//在A中删除既在B中出现又在C中出现的元素，结果放在D中 StatusListUnion_Sq(SqList&D,SqList&A,SqList&B,SqList&C){SqListTemp;InitList_Sq(Temp);ListCross_L(B,C,Temp);ListMinus_L(A,Temp,D);}2.30要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。解：//在A中删除既在B中出现又在C中出现的元素，并释放B、CStatusListUnion_L(LinkList&A,LinkList&B,LinkList&C){ListCross_L(B,C);ListMinus_L(A,B);}//求集合A-B，结果放在A表中，并删除B表StatusListMinus_L(LinkList&A,LinkList&B){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;while(pa&&pb){if(pb->datadata){pt=pb;pb=pb->next;qb->next=pb;free(pt);}elseif(pb->data>pa->data){qa=pa;pa=pa->next;}else{pt=pa;pa=pa->next;qa->next=pa;free(pt);}} while(pb){pt=pb;pb=pb->next;qb->next=pb;free(pt);}pb=B;free(pb);returnOK;}2.31假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。解：//在单循环链表S中删除S的前驱结点StatusListDelete_CL(LinkList&S){LinkListp,q;if(S==S->next)returnERROR;q=S;p=S->next;while(p->next!=S){q=p;p=p->next;}q->next=p->next;free(p);returnOK;}2.32已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。解：//建立一个空的循环链表StatusInitList_DL(DuLinkList&L){L=(DuLinkList)malloc(sizeof(DuLNode));if(!L)exit(OVERFLOW);L->pre=NULL;L->next=L;returnOK;}//向循环链表中插入一个结点StatusListInsert_DL(DuLinkList&L,ElemTypee){ DuLinkListp;p=(DuLinkList)malloc(sizeof(DuLNode));if(!p)returnERROR;p->data=e;p->next=L->next;L->next=p;returnOK;}//将单循环链表改成双向链表StatusListCirToDu(DuLinkList&L){DuLinkListp,q;q=L;p=L->next;while(p!=L){p->pre=q;q=p;p=p->next;}if(p==L)p->pre=q;returnOK;}2.33已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。解：//将单链表L划分成3个单循环链表StatusListDivideInto3CL(LinkList&L,LinkList&s1,LinkList&s2,LinkList&s3){LinkListp,q,pt1,pt2,pt3;p=L->next;pt1=s1;pt2=s2;pt3=s3;while(p){if(p->data>="0"&&p->data<="9"){q=p;p=p->next;q->next=pt1->next;pt1->next=q;pt1=pt1->next;}elseif((p->data>="A"&&p->data<="Z")||(p->data>="a"&&p->data<="z")){ q=p;p=p->next;q->next=pt2->next;pt2->next=q;pt2=pt2->next;}else{q=p;p=p->next;q->next=pt3->next;pt3->next=q;pt3=pt3->next;}}q=L;free(q);returnOK;}在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为：typedefstructXorNode{chardata;structXorNode*LRPtr;}XorNode,*XorPointer;typedestruct{//无头结点的异或指针双向链表XorPointerLeft,Right;//分别指向链表的左侧和右端}XorLinkedList;XorPointerXorP(XorPointerp,XorPointerq);//指针异或函数XorP返回指针p和q的异或值2.34假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且a⊕(a⊕b)=(a⊕a)⊕b=b(a⊕b)⊕b=a⊕(b⊕b)=a则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。解：StatusTraversingLinkList(XorLinkedList&L,chard){XorPointerp,left,right;if(d=="l"||d=="L"){p=L.Left;left=NULL;while(p!=NULL){ VisitingData(p->data);left=p;p=XorP(left,p->LRPtr);}}elseif(d=="r"||d=="R"){p=L.Right;right=NULL;while(p!=NULL){VisitingData(p->data);right=p;p=XorP(p->LRPtr,right);}}elsereturnERROR;returnOK;}2.35采用2.34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。2.36采用2.34题所述的存储结构，写出删除第i个结点的算法。2.37设以带头结点的双向循环链表表示的线性表。试写一时间复杂度O(n)的算法，将L改造为。解：//将双向链表L=(a1,a2,...,an)改造为(a1,a3,...,an,...,a2)StatusListChange_DuL(DuLinkList&L){inti;DuLinkListp,q,r;p=L->next;r=L->pre;i=1;while(p!=r){if(i%2==0){q=p;p=p->next;//删除结点q->pre->next=q->next;q->next->pre=q->pre;//插入到头结点的左面q->pre=r->next->pre;r->next->pre=q;q->next=r->next; r->next=q;}elsep=p->next;i++;}returnOK;}2.38设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。解：DuLinkListListLocate_DuL(DuLinkList&L,ElemTypee){DuLinkListp,q;p=L->next;while(p!=L&&p->data!=e)p=p->next;if(p==L)returnNULL;else{p->freq++;//删除结点p->pre->next=p->next;p->next->pre=p->pre;//插入到合适的位置q=L->next;while(q!=L&&q->freq>p->freq)q=q->next;if(q==L){p->next=q->next;q->next=p;p->pre=q->pre;q->pre=p;}else{//在q之前插入p->next=q->pre->next;q->pre->next=p;p->pre=q->pre;q->pre=p;}returnp;}}在2.39至2.40题中，稀疏多项式采用的顺序存储结构SqPoly定义为 typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{//多项式的顺序存储结构PolyTerm*data;intlast;}SqPoly;2.39已知稀疏多项式，其中，，。试采用存储量同多项式项数m成正比的顺序存储结构，编写求的算法（为给定值），并分析你的算法的时间复杂度。解：typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{PolyTerm*data;intlast;}SqPoly;//建立一个多项式StatusPolyInit(SqPoly&L){inti;PolyTerm*p;cout<<"请输入多项式的项数:";cin>>L.last;L.data=(PolyTerm*)malloc(L.last*sizeof(PolyTerm));if(!L.data)returnERROR;p=L.data;for(i=0;i>p->coef;cout<<"请输入指数:";cin>>p->exp;p++;}returnOK;}//求多项式的值doublePolySum(SqPoly&L,doublex0) {doublePn,x;inti,j;PolyTerm*p;p=L.data;for(i=0,Pn=0;iexp;j++)x=x*x0;Pn=Pn+p->coef*x;}returnPn;}2.40采用2.39题给定的条件和存储结构，编写求的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。解：//求两多项式的差StatusPolyMinus(SqPoly&L,SqPoly&L1,SqPoly&L2){PolyTerm*p,*p1,*p2;p=L.data;p1=L1.data;p2=L2.data;inti=0,j=0,k=0;while(iexpexp){p->coef=p1->coef;p->exp=p1->exp;p++;k++;p1++;i++;}elseif(p1->exp>p2->exp){p->coef=-p2->coef;p->exp=p2->exp;p++;k++;p2++;j++;}else{if(p1->coef!=p2->coef){p->coef=(p1->coef)-(p2->coef);p->exp=p1->exp;p++;k++;}p1++;p2++; i++;j++;}}if(icoef=p1->coef;p->exp=p1->exp;p++;k++;p1++;i++;}if(jcoef=-p2->coef;p->exp=p2->exp;p++;k++;p2++;j++;}L.last=k;returnOK;}在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为typedefstructPolyNode{PolyTermdata;structPolyNode*next;}PolyNode,*PolyLink;typedefPolyLinkLinkedPoly;2.41试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。解：StatusPolyDifferential(LinkedPoly&L){LinkedPolyp,q,pt;q=L;p=L->next;while(p!=L){if(p->data.exp==0){pt=p;p=p->next;q->next=p;free(pt);}else{p->data.coef=p->data.coef*p->data.exp;p->data.exp--; q=p;p=p->next;}}returnOK;}2.42试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。解：//将单链表L划分成2个单循环链表StatusListDivideInto2CL(LinkedPoly&L,LinkedPoly&L1){LinkedPolyp,p1,q,pt;q=L;p=L->next;p1=L1;while(p!=L){if(p->data.exp%2==0){pt=p;p=p->next;q->next=p;pt->next=p1->next;p1->next=pt;p1=p1->next;}else{q=p;p=p->next;}}returnOK;}第3章栈和队列3.1若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：(1)如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？(2)如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。解：(1)123231321213132(2)可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。3.2简述栈和线性表的差别。 解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。3.3写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;charx,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Push(S,‘a’);Push(S,y);Pop(S,x);Push(S,‘t’);Push(S,x);Pop(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}解：stack3.4简述以下算法的功能（栈的元素类型SElemType为int）。(1)statusalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}(2)statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}解：(1)栈中的数据元素逆置(2)如果栈中存在元素e，将其从栈中清除3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。解：任何前n个序列中S的个数一定大于X的个数。设两个合法序列为： T1=S……X……S……T2=S……X……X……假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。3.6试证明：若借助栈由输入序列12…n得到的输出序列为(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i1) cout<1){cout<>x;if(x==0)sum=0;else{test(sum);sum+=x;}cout<>x;Push(s,x);}while(x>0);while(!StackEmpty(s)){Pop(s,x);sum+=x;cout<=p)*top[0]--=x;elsecerr<<"Stackoverflow!";}else{if(top[1]top[0])return*top[1]--;elsecerr<<"Stackempty!";}returnOK;}}; //链栈的数据结构及方法的定义typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,*LinkType;typedefstruct{LinkTypetop;intsize;}Stack;voidInitStack(Stack&s){s.top=NULL;s.size=0;}voidDestroyStack(Stack&s){LinkTypep;while(s.top){p=s.top;s.top=p->next;deletep;s.size--;}}voidClearStack(Stack&s){LinkTypep;while(s.top){p=s.top;s.top=p->next;deletep;s.size--;}}intStackLength(Stacks){returns.size;} StatusStackEmpty(Stacks){if(s.size==0)returnTRUE;elsereturnFALSE;}StatusGetTop(Stacks,ElemType&e){if(!s.top)returnERROR;else{e=s.top->data;returnOK;}}StatusPush(Stack&s,ElemTypee){LinkTypep;p=newNodeType;if(!p)exit(OVERFLOW);p->next=s.top;s.top=p;p->data=e;s.size++;returnOK;}StatusPop(Stack&s,ElemType&e){LinkTypep;if(s.top){e=s.top->data;p=s.top;s.top=p->next;deletep;s.size--;}returnOK;}//从栈顶到栈底用Visit()函数遍历栈中每个数据元素voidStackTraverse(Stacks,Status(*Visit)(ElemTypee)){LinkTypep;p=s.top; while(p)Visit(p->data);}3.16假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。解：intmain(){Stacks;charBuffer[80];inti=0,j=0;InitStack(s);cout<<"请输入硬席(H)和软席车厢(S)序列：";cin>>Buffer;cout<#includetypedefstruct{intx;inty;}PosType;typedefstruct{intColor;intVisited;PosTypeseat;}ElemType;#include"d:VC99Stack.h"#defineM8#defineN8ElemTypeg[M][N];voidCreateGDS(ElemTypeg[M][N]);voidShowGraphArray(ElemTypeg[M][N]);voidRegionFilling(ElemTypeg[M][N],PosTypeCurPos,intNewColor);intmain(){CreateGDS(g);ShowGraphArray(g);PosTypeStartPos;StartPos.x=5;StartPos.y=5;intFillColor=6;RegionFilling(g,StartPos,FillColor);cout<0&&!g[CurPos.x-1][CurPos.y].Visited&&g[CurPos.x-1][CurPos.y].Color==OldColor)Push(s,g[CurPos.x-1][CurPos.y]);if(CurPos.y0&&!g[CurPos.x][CurPos.y-1].Visited&&g[CurPos.x][CurPos.y-1].Color==OldColor)Push(s,g[CurPos.x][CurPos.y-1]);}}voidCreateGDS(ElemTypeg[M][N]){inti,j;for(i=0;i=j)returnTRUE;elsereturnFALSE;}3.22如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。解：charCalVal_InverPoland(charBuffer[]){ StackOpnd;InitStack(Opnd);inti=0;charc;ElemTypee1,e2;while(Buffer[i]!="#"){if(!IsOperator(Buffer[i])){Push(Opnd,Buffer[i]);}else{Pop(Opnd,e2);Pop(Opnd,e1);c=Cal(e1,Buffer[i],e2);Push(Opnd,c);}i++;}returnc;}charCal(charc1,charop,charc2){intx,x1,x2;charch[10];ch[0]=c1;ch[1]="";x1=atoi(ch);ch[0]=c2;ch[1]="";x2=atoi(ch);switch(op){case"+":x=x1+x2;break;case"-":x=x1-x2;break;case"*":x=x1*x2;break;case"/": x=x1/x2;break;default:break;}itoa(x,ch,10);returnch[0];}3.23如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。解：#include#include#include#include"d:VC99DSConstant.h"typedefcharARRAY[30];typedefARRAYElemType;typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,*LinkType;typedefstruct{LinkTypetop;intsize;}Stack;voidInitStack(Stack&s);StatusPush(Stack&s,ElemTypee);StatusPop(Stack&s,ElemTypee);StatusIsOperator(charc);StatusStackEmpty(Stacks);StatusInvToFroPoland(chara[]);intmain(){chara[30];cout<<"请输入逆波兰算术表达式字符序列：";cin>>a;if(InvToFroPoland(a))cout<="0"&&a[i]<="9"){ch[0]=a[i];ch[1]="";Push(s,ch);}elsereturnFALSE;}else{ch[0]=a[i];ch[1]="";if(!StackEmpty(s)){Pop(s,c2);if(!StackEmpty(s)){Pop(s,c1);strcat(ch,c1);strcat(ch,c2);Push(s,ch);}elsereturnFALSE;}elsereturnFALSE;}i++;}if(!StackEmpty(s)){Pop(s,c1);strcpy(a,c1);}elsereturnFALSE;if(!StackEmpty(s))returnFALSE;returnOK;}voidInitStack(Stack&s) {s.top=NULL;s.size=0;}StatusPush(Stack&s,ElemTypee){LinkTypep;p=newNodeType;if(!p)exit(OVERFLOW);p->next=s.top;s.top=p;strcpy(p->data,e);s.size++;returnOK;}StatusPop(Stack&s,ElemTypee){LinkTypep;if(s.top){strcpy(e,s.top->data);p=s.top;s.top=p->next;deletep;s.size--;}returnOK;}StatusStackEmpty(Stacks){if(s.size==0)returnTRUE;elsereturnFALSE;}StatusIsOperator(charc){char*p="#+-*/";while(*p){if(*p==c)returnTRUE;p++;} returnFALSE;}3.24试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。解：intg(intm,intn);intmain(){intm,n;cout<<"请输入m和n的值：";cin>>m>>n;if(n>=0)cout<0)return(g(m-1,2*n)+n);elsereturn0;}假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。3064313232163383440523.25试写出求递归函数F(n)的递归算法，并消除递归：解：#include#defineN20intmain(){inti;inta[N];intn;cout<<"请输入n:";cin>>n;for(i=0;idoubleSqrt(doubleA,doublep,doublee);intmain(){doubleA,p,e;cout<<"请输入Ape:";cin>>A>>p>>e;cout<-e&&(p*p-A)1){e1.nval=e.nval;Pop(s,e);e.mval--;e.nval=e1.nval+1;}}while(StackLength(s)!=1||e.mval!=0);returne.nval+1;}0,akm(2,1)021g=akm(2,0)1,akm(2,0)620akm=akm(m-1,1)=akm(1,1)2,akm(1,1)411g=akm(m,n-1)=akm(1,0)3,akm(1,0)610akm=akm(m-1,1)=akm(0,1)4,akm(0,1)401akm=n+1=2退栈0,akm(2,1)021g=akm(2,0)1,akm(2,0)620akm=akm(m-1,1)=akm(1,1)2,akm(1,1)411g=akm(m,n-1)=akm(1,0)3,akm(1,0)610akm=akm(m-1,1)=akm(0,1)=2退栈 0,akm(2,1)021g=akm(2,0)1,akm(2,0)620akm=akm(m-1,1)=akm(1,1)2,akm(1,1)411g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2);3,akm(0,2)702akm=n+1=3退栈0,akm(2,1)021g=akm(2,0)1,akm(2,0)620akm=akm(m-1,1)=akm(1,1)2,akm(1,1)411g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2)=3;退栈0,akm(2,1)021g=akm(2,0)1,akm(2,0)620akm=akm(m-1,1)=akm(1,1)=3退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g)2,akm(1,2)612g=akm(1,1);akm(m-1,g)3,akm(1,1)611g=akm(1,0);akm(m-1,g)4,akm(1,0)610akm=akm(0,1)5,akm(0,1)401akm(0,1)=2退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g)2,akm(1,2)612g=akm(1,1);akm(m-1,g)3,akm(1,1)611g=akm(1,0);akm(m-1,g)4,akm(1,0)610akm=akm(0,1)=2退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g)2,akm(1,2)612g=akm(1,1);akm(m-1,g)3,akm(1,1)611g=akm(1,0)=2;akm(m-1,g)=akm(0,2)4,akm(0,2)702akm=n+1=3退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g)2,akm(1,2)612g=akm(1,1);akm(m-1,g)3,akm(1,1)611g=akm(1,0)=2;akm(m-1,g)=akm(0,2)=3退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g)2,akm(1,2)612g=akm(1,1)=3;akm(m-1,g)=akm(0,3)3,akm(0,3)703akm=n+1=4退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g) 2,akm(1,2)612g=akm(1,1)=3;akm(m-1,g)=akm(0,3)=4退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2)=4;akm(m-1,g)=akm(0,4)2,akm(0,4)704akm=n+1=5退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2)=4;akm(m-1,g)=akm(0,4)=5退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)=5退栈akm(2,1)=5;3.28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列何处队列的算法。解：typedefintElemType;typedefstructNodeType{ElemTypedata;NodeType*next;}QNode,*QPtr;typedefstruct{QPtrrear;intsize;}Queue;StatusInitQueue(Queue&q){q.rear=NULL;q.size=0;returnOK;}StatusEnQueue(Queue&q,ElemTypee){QPtrp;p=newQNode;if(!p)returnFALSE;p->data=e;if(!q.rear){q.rear=p;p->next=q.rear;}else{p->next=q.rear->next;q.rear->next=p;q.rear=p; }q.size++;returnOK;}StatusDeQueue(Queue&q,ElemType&e){QPtrp;if(q.size==0)returnFALSE;if(q.size==1){p=q.rear;e=p->data;q.rear=NULL;deletep;}else{p=q.rear->next;e=p->data;q.rear->next=p->next;deletep;}q.size--;returnOK;}3.29如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。解：#defineMaxQSize4typedefintElemType;typedefstruct{ElemType*base;intfront;intrear;Statustag;}Queue;StatusInitQueue(Queue&q){q.base=newElemType[MaxQSize];if(!q.base)returnFALSE;q.front=0;q.rear=0;q.tag=0;returnOK; }StatusEnQueue(Queue&q,ElemTypee){if(q.front==q.rear&&q.tag)returnFALSE;else{q.base[q.rear]=e;q.rear=(q.rear+1)%MaxQSize;if(q.rear==q.front)q.tag=1;}returnOK;}StatusDeQueue(Queue&q,ElemType&e){if(q.front==q.rear&&!q.tag)returnFALSE;else{e=q.base[q.front];q.front=(q.front+1)%MaxQSize;q.tag=0;}returnOK;}设标志节省存储空间，但运行时间较长。不设标志则正好相反。3.30假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。解：#defineMaxQSize4typedefintElemType;typedefstruct{ElemType*base;intrear;intlength;}Queue;StatusInitQueue(Queue&q){q.base=newElemType[MaxQSize];if(!q.base)returnFALSE;q.rear=0;q.length=0;returnOK;}StatusEnQueue(Queue&q,ElemTypee){if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize) returnFALSE;else{q.base[q.rear]=e;q.rear=(q.rear+1)%MaxQSize;q.length++;}returnOK;}StatusDeQueue(Queue&q,ElemType&e){if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear)returnFALSE;else{e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize];q.length--;}returnOK;}3.31假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。解：StatusSymmetryString(char*p){Queueq;if(!InitQueue(q))return0;Stacks;InitStack(s);ElemTypee1,e2;while(*p){Push(s,*p);EnQueue(q,*p);p++;}while(!StackEmpty(s)){Pop(s,e1);DeQueue(q,e2);if(e1!=e2)returnFALSE;}returnOK;}3.32试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，要求满足：而，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项） 解：intFibonacci(intk,intn){if(k<1)exit(OVERFLOW);Queueq;InitQueue(q,k);ElemTypex,e;inti=0;while(i<=n){if(i=k){//队列求和x=sum(q);DeQueue(q,e);EnQueue(q,x);}i++;}returnq.base[(q.rear+q.MaxSize-1)%q.MaxSize];}3.33在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。解：//Filename:Queue.htypedefstruct{ElemType*base;intfront;intrear;Statustag;intMaxSize;}DQueue;StatusInitDQueue(DQueue&q,intsize){q.MaxSize=size;q.base=newElemType[q.MaxSize];if(!q.base)returnFALSE;q.front=0;q.rear=0; q.tag=0;returnOK;}StatusEnDQueue(DQueue&q,ElemTypee){if(q.front==q.rear&&q.tag)returnFALSE;if(q.front==q.rear&&!q.tag){//空队列q.base[q.rear]=e;q.rear=(q.rear+1)%q.MaxSize;if(q.rear==q.front)q.tag=1;}else{//非空非满if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){//从队头入队q.front=(q.front+q.MaxSize-1)%q.MaxSize;q.base[q.front]=e;if(q.rear==q.front)q.tag=1;}else{//从队尾入队q.base[q.rear]=e;q.rear=(q.rear+1)%q.MaxSize;if(q.rear==q.front)q.tag=1;}}returnOK;}StatusDeDQueue(DQueue&q,ElemType&e){if(q.front==q.rear&&!q.tag)returnFALSE;else{//非空队列e=q.base[q.front];q.front=(q.front+1)%q.MaxSize;q.tag=0;}returnOK;}//Filename:XT333.cpp主程序文件#include#includetypedefintElemType;#include"D:VC99Queue.h"intmain(){ intt1,t2,t3,t4;ElemTypee;cout<<"请输入作业a1、a2、a3、a4的执行时间:";cin>>t1>>t2>>t3>>t4;DQueuedq;InitDQueue(dq,5);EnDQueue(dq,t1);EnDQueue(dq,t2);EnDQueue(dq,t3);EnDQueue(dq,t4);while(dq.front!=dq.rear||dq.tag){DeDQueue(dq,e);cout<>ch;inti=0;while(ch[i]){if(ch[i]=="P")cout<#include#defineMaxSize128classString{char*ch;intcurlen;public:String(constString&ob);String(constchar*init);String();~String();voidStrAssign(Stringt);intStrCompare(Stringt);intStrLength();voidConcat(Stringt);StringSubString(intstart,intlen);voidshow();};String::String(constString&ob){ch=newchar[MaxSize+1];if(!ch)exit(1);curlen=ob.curlen;strcpy(ch,ob.ch);}String::String(constchar*init){ch=newchar[MaxSize+1];if(!ch)exit(1);curlen=strlen(init); strcpy(ch,init);}String::String(){ch=newchar[MaxSize+1];if(!ch)exit(1);curlen=0;ch[0]="";}String::~String(){deletech;curlen=0;}voidString::StrAssign(Stringt){strcpy(ch,t.ch);curlen=t.curlen;}intString::StrCompare(Stringt){returnstrcmp(ch,t.ch);}intString::StrLength(){returncurlen;}voidString::Concat(Stringt){strcat(ch,t.ch);curlen=curlen+t.curlen;}StringString::SubString(intstart,intlen){Stringtemp;inti,j;if(start>=0&&start+len<=curlen&&len>0){temp.curlen=len;for(i=0,j=start;i=0;i--)t.Concat(s.SubString(i,1));s.StrAssign(t);}4.11解：第5章数组与广义表5.1解：(1)6×8×6=288Byte(2)LOC(5,7)=1000+(5×8+7)×6=1282(3)LOC(1,4)=1000+(1×8+4)×6=1072(4)LOC(4,7)=1000+(7×6+4)×6=12765.2解：(1)LOC(0,0,0,0)=100(2)LOC(1,1,1,1)=100+(1×3×5×8+1×5×8+1×8+1)×4=776(3)LOC(3,1,2,5)=100+(3×3×5×8+1×5×8+2×8+5)×4=1784(4)LOC(8,2,4,7)=100+(8×3×5×8+2×5×8+4×8+7)×4=44165.3解：(0,0,0,0)(1,0,0,0)(0,1,0,0)(1,1,0,0)(0,0,1,0)(1,0,1,0)(0,1,1,0)(1,1,1,0)(0,0,2,0)(1,0,2,0)(0,1,2,0)(1,1,2,0)(0,0,0,1)(1,0,0,1)(0,1,0,1)(1,1,0,1)(0,0,1,1)(1,0,1,1)(0,1,1,1)(1,1,1,1)(0,0,2,1)(1,0,2,1)(0,1,2,1)(1,1,2,1)(0,0,0,2)(1,0,0,2)(0,1,0,2)(1,1,0,2)(0,0,1,2)(1,0,1,2)(0,1,1,2)(1,1,1,2)(0,0,2,2)(1,0,2,2)(0,1,2,2)(1,1,2,2)5.4解：其中，a=Max(i,j)，b=Min(i,j)5.5解：(，，)5.6解：u=i-j+1v=j-15.7解：(1)k=2(i-1)+j-1()(2)i=(k+1)DIV3+1() j=k+1-2(kDIV3)5.8解：i为奇数时，k=i+j-2j为偶数时，k=i+j-1k=2(iDIV2)+j-15.9解：设稀疏矩阵为n行n列，其中的非零元为m个，m远小于。从时间上来说，采用二维数组存储稀疏矩阵需要-1次加法运算，而用三元组只需m-1次加法运算。从空间上来说，用二维数组需要个基本存储单元，而三元组需要m个基本存储单元外加2m个整型存储单元。由于远远大于m，故实际存储空间也较大。5.10解：(1)GetHead【(p,h,w)】=p(2)GetTail【(b,k,p,h)】=(k,p,h)(3)GetHead【((a,b),(c,d))】=(a,b)(4)GetTail【((a,b),(c,d))】=((c,d))(5)GetHead【GetTail【((a,b),(c,d))】】=GetHead【((c,d))】=(c,d)(6)GetTail【GetHead【((a,b),(c,d))】】=GetTail【(a,b)】=(b)(7)GetHead【GetTail【GetHead【((a,b),(c,d))】】】=GetHead【(b)】=b(8)GetTail【GetHead【GetTail【((a,b),(c,d))】】】=GetTail【(c,d)】=(d)5.11解：(1)GetHead【GetTail【GetTail【L1】】】(2)GetHead【GetHead【GetTail【L2】】】(3)GetHead【GetHead【GetTail【GetTail【GetHead【L3】】】】】(4)GetHead【GetHead【GetHead【GetTail【GetTail【L4】】】】】(5)GetHead【GetHead【GetTail【GetTail【L5】】】】(6)GetHead【GetTail【GetHead【L6】】】(7)GetHead【GetHead【GetTail【GetHead【GetTail【L7】】】】】5.12解：5.13解：(1)List=((x,(y)),(((())),(()),(z)))(2)List=(((a,b,()),()),(a,(b)),())5.14解：(n>=1) ElemTypes(inti){if(i>1)returns(i-1)+a1+(i-1)*d;elsereturna1;}5.16解：5.17解：intMax(SqList&L,intk){if(kMin(L,k+1))returnMin(L,k+1);elsereturnL.elem[k];elsereturnL.elem[k];}intSum(SqList&L,intk){if(k==0)returnL.elem[0];elsereturnL.elem[k]+Sum(a,k-1);}intProduct(SqList&L,intk){if(k==0)returnL.elem[0];elsereturnL.elem[k]*Sum(a,k-1); }doubleAvg(SqList&L,intk){if(k==0)returnL.elem[0];elsereturn(Avg(a,k-1)*k+L.elem[k])/(k+1);}5.18解：算法的基本思想是将数组分成k组，将第一组与第二组进行两两交换，再将第一组与第三组进行两两交换，...，总共需进行n-k次交换。注意最后一组可能出现不足k个元素的情况，此时最后一组为剩余元素加第一组的前几个元素共k个构成最后一组。voidRRMove(ElemTypeA[],intk,intn){ElemTypee;inti=0,j,p;while(i#defineRS4#defineCS4typedefintElemType;typedefstruct{ElemTypee;inti,j;intFlags;}NodeType;voidInitialize(NodeTypea[RS][CS],ElemTypeA[RS][CS]);voidSaddlePoint(NodeTypea[RS][CS]);ElemTypeRowMin(NodeTypea[RS][CS],intk);ElemTypeColMax(NodeTypea[RS][CS],intk);voidShow(NodeTypea[RS][CS]);intmain() {ElemTypeA[RS][CS]={{2,1,3,4},{1,3,1,2},{2,7,1,3},{3,2,4,1}};NodeTypea[RS][CS];Initialize(a,A);SaddlePoint(a);Show(a);return0;}voidInitialize(NodeTypea[RS][CS],ElemTypeA[RS][CS]){inti,j;for(i=0;ia[k][i].e){x=a[k][i].e;}returnx;}ElemTypeColMax(NodeTypea[RS][CS],intk){ElemTypex;x=a[0][k].e;inti;for(i=1;iTextOut(0+j*20,0+i*20,str,strlen(str));}}}//矩阵相加的运算符重载函数CSparseMatCSparseMat::operator+(CSparseMatB){CSparseMattemp(m_nRow,m_nCol,0);if(m_nRow!=B.m_nRow||m_nCol!=B.m_nCol)returntemp;temp.m_pt=newTriple[m_nTrs+B.m_nTrs];if(!temp.m_pt)returntemp;temp.m_nTrs=m_nTrs+B.m_nTrs;inti=0;intj=0;intk=0;while(i#include#defineMax128typedefintElemType;typedefstruct{intcol;ElemTypee;}Twin;classCSparseMat{public:CSparseMat(){}CSparseMat(intr,intc,intn); virtual~CSparseMat(){}voidShowSparse(inti,intj);Twin*m_pt;//指向非零元的指针intrpos[Max];intm_nCol;//矩阵列数intm_nRow;//矩阵行数intm_nTws;//非零元个数};CSparseMat::CSparseMat(intr,intc,intn){m_nRow=r;m_nCol=c;m_nTws=n;m_pt=newTwin[m_nTws];if(!m_pt)return;//输入矩阵的所有二元组inti;for(i=0;i>m_pt[i].col>>m_pt[i].e;}for(i=0;i>rpos[i];//该行没有非零元输入-1}}voidCSparseMat::ShowSparse(inti,intj){if(i>m_nRow||j>m_nCol)return;ElemTypex=0;ints,d;if(i==m_nRow){s=rpos[i];d=m_nTws;}else{s=rpos[i];intm=1;d=rpos[i+m]; while(d<0){if(i+m=0){intk=s;while(k>p->row>>p->col>>p->e;q=RHead[p->row];if(!q){RHead[p->row]=p;p->right=NULL;}else{qf=q;while(q&&q->colcol){qf=q;q=q->right;}p->right=qf->right;qf->right=p;}q=CHead[p->col];if(!q){CHead[p->col]=p; p->down=NULL;}else{qf=q;while(q&&q->rowrow){qf=q;q=q->down;}p->down=qf->down;qf->down=p;}}}voidCCrossListMat::ShowMat(inti,intj){ElemTypex=0;OLinkp;p=RHead[i];while(p&&p->col!=j)p=p->right;if(p)x=p->e;cout<#includetypedefintElemType;typedefstructOLNode{introw;intcol;ElemTypee;structOLNode*right,*down;}OLNode,*OLink;classCCrossListMat{public:OLink*RHead,*CHead;//行与列指针向量的头指针intm_nCol;//矩阵列数intm_nRow;//矩阵行数intm_nNum;//非零元个数 public:CCrossListMat(){}virtual~CCrossListMat(){}CCrossListMat(intr,intc,intn);voidAdd(CCrossListMatB);voidShowMat();};CCrossListMat::CCrossListMat(intr,intc,intn){m_nRow=r;m_nCol=c;m_nNum=n;inti;RHead=newOLink[m_nRow];if(!RHead)exit(-2);CHead=newOLink[m_nCol];if(!CHead)exit(-2);for(i=0;i>p->row>>p->col>>p->e;q=RHead[p->row];if(!q){RHead[p->row]=p;p->right=NULL;}else{qf=q;while(q&&q->colcol){qf=q;q=q->right;}p->right=qf->right;qf->right=p;} q=CHead[p->col];if(!q){CHead[p->col]=p;p->down=NULL;}else{qf=q;while(q&&q->rowrow){qf=q;q=q->down;}p->down=qf->down;qf->down=p;}}}voidCCrossListMat::Add(CCrossListMatB){inti,k=0;OLinkpa,pb;OLinkpre,p;//按行插入OLinkqpre,q;//按列插入for(i=0;icolcol){pre=pa;pa=pa->right;}if(pa&&pa->col==pb->col){pa->e=pa->e+pb->e;pb=pb->right;pre=pa;pa=pa->right;}else{//在A中插入一个新结点p=newOLNode;p->row=pb->row; p->col=pb->col;p->e=pb->e;pb=pb->right;if(!pre){p->right=pa;RHead[i]=p;}else{p->right=pre;pre->right=p;}//处理列指针qpre=NULL;q=CHead[p->col];while(q&&q->rowdown;}if(!qpre){p->down=q;CHead[p->col]=p;}else{p->down=pre;pre->down;}k++;}}//endwhile(pb)}//endform_nNum=m_nNum+k;}voidCCrossListMat::ShowMat(){inti,j;OLinkp;for(i=0;irow==i&&p->col==j){cout<e<<"";p=p->right;} elsecout<<0<<"";}cout<1){//如果串长大于1，说明是表结点L->tag=LIST;Sub=s.SubString(2,s.StrLength()-2);//取括号内子串if(!Sub.StrEmpty()){//建立子表StrDistrict(Sub,HSub,TSub);if(!HSub.StrEmpty())//表头不空CreateGList(L->hp,HSub);elseL->hp=NULL;if(!TSub.StrEmpty())//表尾不空CreateGList(L->tp,TSub);elseL->tp=NULL;}else{//空表L->hp=NULL;L->tp=NULL;}}else{//建立原子结点L->tag=ATOM;L->atom=s.GetStr()[0];L->tp=NULL; }}returnOK;}//显示广义表串voidShowGList(GList&L){if(L){if(L->tag==LIST){cout<<"(";if(L->hp)ShowGList(L->hp);if(L->tp){cout<<",";ShowGList(L->tp);}cout<<")";}elsecout<atom;}}5.30解：//求广义表深度的递归算法intGListDepth(GList&L){intDepth=0;intHDepth,TDepth;//表头深度，表尾深度if(!L)returnDepth;//广义表不存在if(L->tag==ATOM)returnDepth;//原子结点深度为0else{Depth++;//表结点深度为1HDepth=Depth+GListDepth(L->hp);TDepth=Depth+GListDepth(L->tp);returnHDepth>TDepth?HDepth:TDepth;}}5.31解：//由广义表L复制广义表TintCopyGList(GList&T,GList&L){if(!L)T=NULL;else{ T=newGLNode;if(!T)exit(OVERFLOW);T->tag=L->tag;if(L->tag==ATOM)T->atom=L->atom;else{CopyGList(T->hp,L->hp);CopyGList(T->tp,L->tp);}}returnOK;}5.32解：//判两广义表是否相等，相等返回OK，否则返回FALSEStatusGListCompare(GList&L1,GList&L2){if(!L1&&!L2)returnOK;//L1和L2均为空表if((!L1&&L2)||(L1&&!L2))returnFALSE;else{//L1和L2均非空表if(L1->tag==L2->tag){//表属性相同if(L1->tag==ATOM){//均为原子结点if(L1->atom==L2->atom)returnOK;elsereturnFALSE;}else{//均为表结点if(GListCompare(L1->hp,L2->hp)&&GListCompare(L1->tp,L2->tp))returnOK;//表头、表尾均相同elsereturnFALSE;}}elsereturnFALSE;//表属性不同}}5.33解：6章树和二叉树6.1已知一棵树边的集合为{,,,,,,,,,,}，请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点G的双亲？(4)哪些是结点G的祖先？(5)哪些是结点G的孩子？ (6)哪些是结点E的子孙？(7)那些是结点E的子孙？(8)结点B和N的层次号分别是什么？(9)树的深度是多少？(10)以结点C为根的子树的深度是多少？6.2一棵度为2的树与一棵二叉树有何区别？解：二叉树是颗有序树，但度为2的树则未必有序。6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6.4一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：(1)各层的结点数目是多少？(2)编号为p的结点的父结点（若存在）的编号是多少？(3)编号为p的结点的第i个儿子结点（若存在）的编号是多少？(4)编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？解：(1)(2)如果p是其双亲的最小的孩子（右孩子），则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子（左孩子），则p+k-1为其最小的弟弟，再减去一个根结点，除以k，即为其双亲结点的编号。综合来说，对于p是左孩子的情况，i=(p+k-2)/k；对于p是右孩子的情况，i=(p-1)/k如果左孩子的编号为p，则其右孩子编号必为p+k-1，所以，其双亲结点的编号为向下取整，如1.5向下取整为1(3)结点p的右孩子的编号为kp+1，左孩子的编号为kp+1-k+1=k(p-1)+2，第i个孩子的编号为k(p-1)+2+i-1=kp-k+i+1。(4)当(p-1)%k!=0时，结点p有右兄弟，其右兄弟的编号为p+1。6.5已知一棵度为k的树中有个度为1的结点，个度为2的结点，…，个度为k的结点，问该树中有多少个叶子结点？解：根据树的定义，在一颗树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加1。总结点数为而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即6.6已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子节点数目。解：利用上题结论易得结果。设度为k的结点个数为，则总结点数为 。叶子结点的数目应等于总结点数减去度不为0的结点的数目，即6.7一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？解：能达到最大深度的树是单支树，其深度为n。满k叉树的深度最小，其深度为(证明见徐孝凯著数据结构实用教程P166)6.8证明：一棵满k叉树上的叶子结点数和非叶子结点数之间满足以下关系：解：一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为，其总结点数为，则非叶子结点数，从而得6.9试分别推导含有n个结点和含个叶子结点的完全三叉树的深度H。解：(1)根据完全三叉树的定义(2)设总的结点数为n，非叶子结点数为注意到每个非叶子结点的度均为3，则由6.10对于那些所有非叶子结点均含有左右子数的二叉树：(1)试问：有n个叶子结点的树中共有多少个结点？(2)试证明：，其中n为叶子结点的个数，表示第i个叶子结点所在的层次（设根节点所在层次为1）。解：（1）总结点数为，其中为非叶子结点数，则叶子结点数为，所以总结点数为。（2）用归纳法证明。 i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，,，结论成立。设有n个叶子结点时也成立，即，现假设增加一个叶子结点，这意味着在某叶子结点p上新生两个叶子结点，而结点p则成为非叶子结点，可见，总结点数增2，叶子结点数增1。此时，所有叶子结点是原结点除去p，然后加上两个深度为的新叶子结点，由此，则当i=n+1时，也成立，由此即得到证明。6.11在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节，每个信息域占k个字节。试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个节点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？解：采用三叉链表结构，需要n(k+12)个字节的存储空间。采用顺序存储结构，需要mk个字节的存储空间，则当mkrchild;if(!r->ltag)while(!r->ltag)r=r->lchild;returnr;}//InSucc6.18解：如果p是根结点，则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历，如果某结点的左指针域等于p，说明该结点是p的双亲结点，且p是它的左孩子；如果某结点的右指针域等于p，说明该结点是p的双亲结点，且p是它的右孩子；如此即可确定访问次序。若是右孩子，其后继是双亲结点；若是左孩子，其后继是其兄弟最左下的子孙，如果兄弟不存在，其后继是其双亲结点。6.19分别画出和下列树对应的各个二叉树：解：6.20解： (1)先序：123456879101112131514(2)中序：348675211091115141312(3)后序：8765432101514131211916.23解：树的先根序列为GFKDAIEBCHJ，后根序列为DIAEKFCJHBG，可以先转化成二叉树，再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同，二叉树的中序序列对应着树的后根序列。GFKDAIEBCHJ为所求二叉树的先序序列，DIAEKFCJHBG为二叉树的中序序列。通过观察先序序列，G为二叉树的根结点，再由中序序列，G的左子树序列为DIAEKFCJHB，右子为空。可以表示成如下形式：G(DIAEKFCJHB，NULL)对于子树先序序列为FKDAIEBCHJ，中序序列为DIAEKFCJHB，显然子树根为F。再由中序序列可以看到，F的左子树是DIAEK，右子树为CJHB。进一步表示成：G(F(DIAEK,CJHB),NULL)对于DIAEK（中序表示），先序为KDAIE，K为根，左子为DIAE，右子为空；对于CJHB，B为根，左子为CJH，右子为空。进一步表示成：G(F(K(DIAE,NULL),B(CJH,NULL)),NULL)G(F(K(D(NULL,IAE),NULL),B(C(NULL,JH),NULL)),NULL)G(F(K(D(NULL,A(I,E)),NULL),B(C(NULL,H(J,NULL)),NULL)),NULL)由此画出二叉树，进而画出树。6.24解：本题应注意下列转换：树森林二叉树先根先序先序后根中序中序 6.25解；用归纳法证明。当n=2时，要使其成为最优二叉树，必须使两个结点都成为叶子结点。设n=k时成立，则当n=k+1时，要使其成为最优，必须用k个结点的哈夫曼树与第k+1个结点组成一个新的最优二叉树，所以n=k+1时也成立。6.26解：不妨设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。A:1101B:01C:11111D:1110E:10F:11110G:00H:1100采用这种方式编码，电文最短。6.27解：6.33解：intVisit(intu,intv){if(u==v)return1;if(L[v]==0){//左子树不存在if(R[v]==0)//右子树也不存在return0;else{//右子树存在，继续访问右子树if(Visit(u,R[v]))return1;elsereturn0;}} else{//左子树存在if(Visit(u,L[v]))//左子树中存在目标return1;else{//左子树中没有目标，需访问右子树if(R[v]==0)//没有右子树return0;else{//右子树存在，继续访问右子树if(Visit(u,R[v]))return1;elsereturn0;}}}}6.34解：intVisit(intu,intv){intNv;Nv=NumElem(v);//返回结点v的下标if(Nv==-1)exit(-2);//结点v不存在，退出if(u==v)return1;if(L[Nv]==0){//左子树不存在if(R[Nv]==0)//右子树也不存在return0;else{//右子树存在，继续访问右子树if(Visit(u,R[Nv]))return1;elsereturn0;}}else{//左子树存在if(Visit(u,L[Nv]))//左子树中存在目标return1;else{//左子树中没有目标，需访问右子树if(R[Nv]==0)//没有右子树return0;else{//右子树存在，继续访问右子树if(Visit(u,R[Nv]))return1;elsereturn0;}}}}//返回结点在数组T中的下标intNumElem(intx) {inti=0;while(i>c;cout<lchild,T2->lchild)&&SimilarTree(T1->rchild,T2->rchild))returnTRUE;elsereturnFALSE;}}}6.37解：//先序遍历的非递归算法StatusPOTraverse(BiTree&T,Status(*Visit)(TElemTypee)){BiTreep; Stacks;InitStack(s);p=T;while(p||!StackEmpty(s)){if(p){//如果根指针不空，访问根结点，//右指针域压栈，继续遍历左子树if(!Visit(p->data))returnERROR;Push(s,p->rchild);p=p->lchild;}//根指针已空，本子树已遍历完毕，//退栈返回上一层，继续遍历未曾访问的结点elsePop(s,p);}returnOK;}6.41解：//求位于先序序列中第k个位置的结点的值，//e中存放结点的返回值，i为计数器StatusPONodeK(TElemType&e,int&i,intk,BiTree&T){if(T){i++;if(i==k)e=T->data;else{PONodeK(e,i,k,T->lchild);PONodeK(e,i,k,T->rchild);}}returnOK;}6.42解：//求二叉树中叶子结点的数目StatusPOLeafNodeNum(int&i,BiTree&T){if(T){if(!T->lchild&&!T->rchild)i++;POLeafNodeNum(i,T->lchild);POLeafNodeNum(i,T->rchild);}returnOK;}6.43解：//按先序交换二叉树的左右子树 StatusExchangeBiTree(BiTree&T){BiTreep;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;ExchangeBiTree(T->lchild);ExchangeBiTree(T->rchild);}returnOK;}6.44解：//求二叉树中以元素值为x的结点为根的子树的深度StatusChildTreeDepth(BiTree&T,TElemTypex,int&depth){BiTreeT1;if(PreOrderLocate(T,x,T1)){depth=BiTDepth(T1);returnOK;}elsereturnERROR;}//按先序在树中查找根为x的子树，T1为指向子树根的指针StatusPreOrderLocate(BiTree&T,TElemTypex,BiTree&T1){if(T){if(T->data==x){T1=T;returnOK;}else{if(PreOrderLocate(T->lchild,x,T1))returnOK;else{if(PreOrderLocate(T->rchild,x,T1))returnOK;elsereturnERROR;}}}elsereturnERROR;} //求二叉树的深度intBiTDepth(BiTree&T){intldep,rdep;if(!T)return0;else{ldep=BiTDepth(T->lchild)+1;rdep=BiTDepth(T->rchild)+1;returnldep>rdep?ldep:rdep;}}6.45解：//删除以元素值为x的结点为根的子树StatusDelChildTree(BiTree&T,TElemTypex){if(T){if(T->data==x){DelBTree(T);T=NULL;returnOK;}else{if(DelChildTree(T->lchild,x))returnOK;else{if(DelChildTree(T->rchild,x))returnOK;elsereturnERROR;}}}elsereturnERROR;}//删除二叉树StatusDelBTree(BiTree&T){if(T){DelBTree(T->lchild);DelBTree(T->rchild);deleteT;returnOK;}elsereturnERROR; }6.46解：//复制一棵二叉树StatusCopyBiTree(BiTree&T,BiTree&T1){BiTreep;if(T){p=newBiTNode;if(!p)returnERROR;p->data=T->data;T1=p;CopyBiTree(T->lchild,T1->lchild);CopyBiTree(T->rchild,T1->rchild);}else{T1=T;}returnOK;}6.47解：typedefBiTreeQElemType;#include"c:YinincludeQueue.h"StatusLevelOrderTraverse(BiTree&T,Status(*Visit)(TElemTypee)){QElemTypep;Queueq;InitQueue(q);if(T)EnQueue(q,T);while(!QueueEmpty(q)){DeQueue(q,p);Visit(p->data);if(p->lchild)EnQueue(q,p->lchild);if(p->rchild)EnQueue(q,p->rchild);}returnOK;}6.48解：//在二叉树T中求结点*p和*q的共同最小祖先eStatusMinComAncst(BiTree&T,TElemType&e,TElemType*p,TElemType*q){if(!T)returnERROR;BiTreeT1,T2,pt=NULL;if(!CopyBiTree(T,T1))returnERROR; if(!CopyBiTree(T,T2))returnERROR;if(!PathTree(T1,p))returnERROR;//求根结点到结点p的路径树T1elseShowBiTree(T1);cout<data==T2->data){pt=T1;if(T1->lchild){T1=T1->lchild;T2=T2->lchild;}else{if(T1->rchild){T1=T1->rchild;T2=T2->rchild;}}}if(!pt)returnERROR;else{e=pt->data;returnOK;}}//在二叉树T中求根到结点p的路径树，该操作将剪去除路径之外的所有分支StatusPathTree(BiTree&T,TElemType*p){if(!T||!p)returnERROR;if(T->data==*p){//找到目标，删除目标的左右子树if(T->lchild)DelBiTree(T->lchild);if(T->rchild)DelBiTree(T->rchild);returnOK;}else{//没找到目标，继续递归查找if(PathTree(T->lchild,p)){//目标在左子树中，删除右子树if(T->rchild)DelBiTree(T->rchild);returnOK;}elseif(PathTree(T->rchild,p)){//目标在右子树中，删除左子树 if(T->lchild)DelBiTree(T->lchild);returnOK;}elsereturnERROR;//找不到目标}}6.49解：StatusCompleteBiTree(BiTree&T){intd;if(T){d=BiTDepth(T->lchild)-BiTDepth(T->rchild);if(d<0||d>1)returnERROR;else{if(CompleteBiTree(T->lchild)&&CompleteBiTree(T->rchild))returnOK;elsereturnERROR;}}elsereturnOK;}6.51解：StatusShowBiTExpress(BiTree&T){if(T){if(T->lchild){if(Low(T->lchild->data,T->data)){cout<<"(";ShowBiTExpress(T->lchild);cout<<")";}elseShowBiTExpress(T->lchild);}cout<data;if(T->rchild){if(Low(T->rchild->data,T->data)){cout<<"(";ShowBiTExpress(T->rchild);cout<<")";}elseShowBiTExpress(T->rchild);}}returnOK; }StatusLow(chara,charb){if((a=="+"||a=="-")&&(b=="*"||b=="/"))returnTRUE;elsereturnFALSE;}6．52解：intBiTreeThrive(BiTree&T){inti,d,nn[20];d=BiTDepth(T);BiTreep=T;Stacks1,s2;InitStack(s1);InitStack(s2);for(i=0;i<20;i++){nn[i]=0;//每层结点个数}if(p)Push(s1,p);elsereturn0;for(i=0;ilchild)Push(s2,p->lchild);//s2中存放第i+1层结点if(p->rchild)Push(s2,p->rchild);}}else{if(StackEmpty(s1)&&!StackEmpty(s2)){while(!StackEmpty(s2)){Pop(s2,p);nn[i]++;if(p->lchild)Push(s1,p->lchild);if(p->rchild)Push(s1,p->rchild);}}}}intmax=nn[0];for(i=0;ilchild)!=1)DelBiTree(T->lchild);elseMaxPathBiTree(T->lchild);if(BiTDepth(T)-BiTDepth(T->rchild)!=1)DelBiTree(T->rchild);elseMaxPathBiTree(T->rchild);}returnOK;}//从根到叶子最长路径中最左方的路径树StatusLMaxPathBiTree(BiTree&T){if(T){if(BiTDepth(T)-BiTDepth(T->lchild)==1){DelBiTree(T->rchild);LMaxPathBiTree(T->lchild);}else{DelBiTree(T->lchild);if(BiTDepth(T)-BiTDepth(T->rchild)==1)LMaxPathBiTree(T->rchild);elseDelBiTree(T->rchild);}}returnOK;}6.54解：//根据完全二叉顺序树创建完全二叉链表树StatusCreateCompleteBiTree(SqList&ST,BiTree<){BiTreep;inti=0,len;if(ST.Length==0)returnOK;p=newBiTNode;if(!p)returnERROR;p->data=ST.Get(i); p->lchild=NULL;p->rchild=NULL;LT=p;Queueq;InitQueue(q);EnQueue(q,p);len=ST.Length();while(!QueueEmpty(q)&&ilchild=newBiTNode;if(!p->lchild)returnERROR;p->lchild->data=ST.Get(++i);p->lchild->lchild=NULL;p->lchild->rchild=NULL;EnQueue(q,p->lchild);}if(irchild=newBiTNode;if(!p->rchild)returnERROR;p->rchild->data=ST.Get(++i);p->rchild->lchild=NULL;p->rchild->rchild=NULL;EnQueue(q,p->rchild);}}returnOK;}6.55解：StatusPreOrderTraverse(BiTree&T){if(T){T->DescNum=DescendNum(T);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}returnOK;}intDescendNum(BiTree&T){if(!T)return0; if(!T->lchild){if(!T->rchild)return0;elsereturnDescendNum(T->rchild)+1;}else{if(!T->rchild)returnDescendNum(T->lchild)+1;elsereturnDescendNum(T->rchild)+DescendNum(T->lchild)+2;}}6.56解：先对二叉树T进行先序线索，得到先序线索二叉树Thrt。然后再进行查找。//先序线索二叉树算法StatusPreOrderThreading(BiThrTree&Thrt,BiThrTree&T){BiThrTreepre;Thrt=newBiThrNode;//为线索二叉树建立头结点if(!Thrt)exit(OVERFLOW);Thrt->LTag=Thread;Thrt->RTag=Link;Thrt->lchild=Thrt;//左子树回指if(!T)Thrt->rchild=Thrt;//若二叉树空，右子树回指else{Thrt->rchild=T;pre=Thrt;PreThreading(T,pre);//先序遍历进行先序线索化pre->rchild=Thrt;//最后一个结点线索化pre->RTag=Thread;Thrt->lchild=pre;}returnOK;}StatusPreThreading(BiThrTree&T,BiThrTree&pre){if(T){if(!T->lchild){T->LTag=Thread;T->lchild=pre;}if(pre&&!pre->rchild){pre->RTag=Thread;pre->rchild=T;}pre=T; if(T->LTag==Link)PreThreading(T->lchild,pre);if(T->RTag==Link)PreThreading(T->rchild,pre);}returnOK;}//从二叉线索树上任一结点q开始查找结点*p。//如果找到，将*p的后继结点指针存于q中，返回TRUE；否则返回FALSEStatusFindNextInBiThrTree(BiThrTree&q,TElemType*p){BiThrTreept=q;if(!pt)returnFALSE;if(pt->data==*p){if(pt->LTag==Link)q=pt->lchild;elseq=pt->rchild;returnOK;}pt=q->rchild;while(pt!=q&&pt->data!=*p){if(pt->LTag==Link)pt=pt->lchild;elsept=pt->rchild;}if(pt==q)returnFALSE;if(pt->data==*p){if(pt->LTag==Link)q=pt->lchild;elseq=pt->rchild;}returnOK;}6.57解：StatusPostOrderThreading(BiThrTree&T,BiThrTree&pre);//首先建立后序线索树StatusFindNextInBiThrTree(BiThrTree&q,TElemType*p);//再进行查找//后序线索二叉树的算法StatusPostOrderThreading(BiThrTree&Thrt,BiThrTree&T){BiThrTreepre;Thrt=newBiThrNode;//为线索二叉树建立头结点if(!Thrt)exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;//右子树回指if(!T)Thrt->lchild=Thrt;//若二叉树空，左子树回指else{ Thrt->lchild=T;pre=Thrt;PostThreading(T,pre);//后序遍历进行后序线索化pre->rchild=Thrt;//最后一个结点线索化pre->RTag=Thread;Thrt->rchild=pre;}returnOK;}StatusPostThreading(BiThrTree&T,BiThrTree&pre){if(T){if(T->LTag==Link)PostThreading(T->lchild,pre);if(T->RTag==Link)PostThreading(T->rchild,pre);if(!T->lchild){T->LTag=Thread;T->lchild=pre;}if(pre&&!pre->rchild){pre->RTag=Thread;pre->rchild=T;}pre=T;}returnOK;}6.58解：typedefcharTElemType;typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;//建立树的二叉链表表示StatusCreateTree(CSTree&T){charch;cout<<"输入结点的值(一个字符，"@"表示空树)";cin>>ch;if(ch=="@"){T=NULL;}else{T=newCSNode; if(!T)returnERROR;T->data=ch;CreateTree(T->firstchild);CreateTree(T->nextsibling);}returnOK;}//输出树的各边StatusShowTree(CSTree&T,CSTree&Father){if(T&&Father)cout<<"("<data<<","<data<<")";if(T->firstchild)ShowTree(T->firstchild,T);if(T->nextsibling)ShowTree(T->nextsibling,Father);returnOK;}6.60解：intLeafNum(CSTree&T){if(T){if(!T->firstchild)return1+LeafNum(T->nextsibling);elsereturnLeafNum(T->firstchild)+LeafNum(T->nextsibling);}elsereturn0;}6.61解：intDegreeNum(CSTree&T){intd,dl,dr;if(T){if(!T->firstchild)d=0;elsed=1+RSiblingNum(T->firstchild);dl=DegreeNum(T->firstchild);dr=DegreeNum(T->nextsibling);returnMax(d,dl,dr);//三数中求最大者}elsereturn0;}//返回当前结点的兄弟数intRSiblingNum(CSTree&T){inti=0; while(T->nextsibling){i++;T=T->nextsibling;}returni;}6.62解：//树的深度intDepth(CSTree&T){intd1,d2;if(T){d1=1+Depth(T->firstchild);d2=Depth(T->nextsibling);returnd1>d2?d1:d2;}elsereturn0;}第7章图7.1解：(1)ID(1)=3OD(1)=0ID(2)=2OD(2)=2ID(3)=1OD(3)=2ID(4)=1OD(4)=3ID(5)=2OD(5)=1ID(6)=2OD(6)=3(2)000000100100010001001011100000110010(3)(4) (5)有三个连通分量1、5、23467.2解：k=1，说明了各结点之间的相互连通关系；k=2说明了结点之间按路径长度为2的相互连通关系；...。7.3解：邻接表：邻接多重表：深度优先搜索的顺序为156432广度优先搜索的顺序为156324，15161312247.14解：StatusCreateAG(ALGraph&G){intn,e,k,i,j;cout<<"请输入顶点数：";cin>>n;cout<<"请输入边数：";cin>>e;G.vernum=n;G.arcnum=e;//建立顶点数组 for(k=0;k>G.vertices[k].data;G.vertices[k].firstarc=NULL;}//建立邻接表VertexTypev1,v2;ArcNode*p,*q;for(k=0;k>v1>>v2;i=LocateVex(G,v1);if(i<0||i>G.vernum-1)returnERROR;j=LocateVex(G,v2);if(j<0||j>G.vernum-1)returnERROR;if(i==j)returnERROR;p=newArcNode;if(!p)returnERROR;p->adjvex=j;p->nextarc=NULL;q=G.vertices[i].firstarc;if(!q)G.vertices[i].firstarc=p;else{while(q->nextarc)q=q->nextarc;//指针定位于邻接表的尾结点q->nextarc=p;}}returnOK;}intLocateVex(ALGraph&G,VertexTypev){inti=0;while(G.vertices[i].data!=v&&i