《数据结构题集C语言版严蔚敏著答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
第1章绪论1.1简述卜.列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.3设有数据结构(D,R),其中D={d1,d2,d3,d4},R={r},r={0,d2),(d2,d3),(d3,d4)}试按图论中图的画法惯例画出其逻辑结构图。解：1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。解：ADTComplex{数据对象:D={r,i|r,i为实数}数据关系：R={〈r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C,其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为e
1IsAscending(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={ 2)1.6在程序设计中，常用下列三种不同的出错处理方式：(1)用exit语句终止执行并报告错误；(2)以函数的返回值区别正确返回或错误返回；(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。解：(l)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。(3)用整型函数进行错误处理的优点是可以给出借误类型，便于迅速确定错误。2.7在程序设计中，可采用下列三种方法实现输出和输入：(1)通过scanf和printf语句：(2)通过函数的参数显式传递；(3)通过全局变量隐式传递。试讨论这三种方法的优缺点。解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。3.8设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(1)i=l;k=0;while(i<=n-l){@k+=10*i;i++；)(2)i=l;k=0;do{@k+=10*i;i++；}while(i<=n-l);(3)i=l;k=0;while(i<=n-l){i++；@k+=10*i;)(4)k=0：for(i=l;i<=n;i++){for(j=i;j<=n;j++)@k++;)(5)for(i=l;i<=n;i++){for(j=l;j<=i：j++){for(k=l;k<=j;k++)@x+=delta;(6)i=l;j=0;while(i+j<=n){@if(i>j)j++；elsei++;}(7)x=n;y=0;//n是不小于1的常数 3while(x>=(y+1)*(y+1)){©y++;}(1)x=91;y=100;while(y>0){@if(x>100){x-=10;y-;}elsex++;}解：(1)n-1⑵n-1⑶n-1/c、+(4)n+(n-l)+(n-2)+...+1=21+(1+2)+(1+2+3)+.・・+(1+2+3+...+n)=i=l]〃1ninin4»a+l)=；Z(/Zz=lZ/=1Z/=!Zi=\=一〃(〃+1)(2〃+1)+—〃(〃+1)=-n(/j+1)(2〃+3)12412(6)n(7)卜份_|向下取整(8)11001.9假设n为2的乘嘉，并且n>2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。intTime(intn){count=0;x=2;while(x 4解：2"=1012n=40H10=1012n=16则对于同样的循环次数n,在这个规模K.第二种算法所花费的代价要大得多。故在这个规模F,第一种算法更适宜。1.12设有以下三个函数:/(n)=21n4+n2+1000,g(n)=15n4+500n3,A(n)=500n35+nlogn请判断以下断言正确与否：(1)f(n)是0(g(n))(2)h(n^O(f(n))(3)8((1)是0(11(11))(4)h(n)是0(*)(5)h(n)是O(nlogn)解：⑴对⑵错(3)错⑷对⑸错1.13试设定若干n值，比较两函数〃2和50〃log?”的增长趋势，并确定n在什么范围内，函数〃2的值大于50〃log2n的值。解：〃2的增长趋势快。但在n较小的时候，50“log2〃的值较大。当n>438时，n2>50/?log,n1.14判断下列各对函数/(〃)和g(〃)，当〃一>oo时，哪个函数增长更快？(1)/(〃)=IO"?+ln(〃!+10"),g(n)=2n4+n+7(2)/(«)=(ln(n!)+5)2,g(n)=13n25(3)f(n)=n~'+J/+1,g(n)=(ln(n!))2+n(4)/(〃)=2(""+(2")一,=解：(l)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快L15试用数学归纳法证明:(1)>?+1)(2〃+1)/6(n>0)/=!(2)=(x向一l)/(x-l)(x^l,n>0)i=0(3)(m>1)i=\ 5(1)£⑵-1)=〃2(W>1)/=!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阶斐波那契序列的定义为/o=。，力=。fk-2=。，fk-\=1；fn=A-1+fn-2+…+/"-*，〃=女,女+1,…试编写求k阶斐波那契序列的第m项位的函数算法，k和m均以值调用的形式在函数参数表中出现。解：k>0为阶数，n为数列的第n项intFibonacci(intk,intn)(if(k 6编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。解：typedefenum{A,B,C,D,E}SchoolName;typedefenum{Female,Male}SexType;typedefstruct{charevent[3];〃项目SexTypesex;SchooINameschool;intscore;}Component;typedefstruct{intMaleSum;〃男团总分intFemaleSum;〃女团总分intTotalSum;〃团体总分}Sum;SumSumScore(SchooINamesn,Componenta[],intn){Sumtemp;temp.MaleSum=0;temp.FemaleSum=O;temp.TotalSum=0;inti;for(i=0;i 7if(k>ArrSize-l)exit(0);for(i=0;i<=k;i++){if(i==0)else{if(2*i*a[i-l]>MAXINT)exit(O);elsea[i]=2*i*a[i-l];})for(i=0;i<=k;i++){if(a[i]>MAXINT)exit(O);elsecout«a[i]«*)return0;}1.20试编写算法求一元多项式的值2(x)=£的值匕(%),并确定算法中每一语句的执/=0行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为=0,1,…,〃)，无。和〃，输出为匕(X。)。解：#include 8第2章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点,该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2.2填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表中一半元素,具体移动的元素个数5元素在表中的位置有失。(2)顺序表中逻辑上相邻的元素的物理位置幺谑紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由其前驳结点的链域的值指示。(4)在嵬函表中设罩.央靖点由忤用是插入和删除首元结点时不用进行特殊处理。2.3在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。 9LLL(4LLL2.3画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode));P=L;for(i=l;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-l;)P->next=NULL;for(i=4;i>=l;i—)Ins_LinkList(L,i+1,i*2);for(i=l;i<=3;i++)Del_LinkList(L,i);解：L-►13►5——►7A「——•一^丁P 10L-►►2——►4►6——•7►8人丁p2.3已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是ob.在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; 11(1)while(Q->next!=NULL){P=Q;Q=Q->next;}(2)while(P->next!=Q)P=P->next;(3)while(P->next->next!=Q)P=P->next;(4)while(P->next->next!=NULL)P=P->next;(5)Q二P;(6)Q=P->next;(7)P=L;(8)L=L->next;(9)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结点的语句序列是ob.在P结点前插入S结点的语句序列是oc,删除P结点的直接后继结点的语句序列是od.删除P结点的直接前驱结点的语句序列是0e.删除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){ 12Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;)returnOK;}(1)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 13StatusCompareOrderList(SqList&A,SqList&B)(inti,k,j;k=A.length>B.length?A.length:B.length;for(i=0;i 14pa=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个元素后，将它们插入到表1b中第i个元素之前。试问此算法是否正确？若有错，请改正之。StatusDeleteAndlnsertSub(LinkedListla,LinkedListlb,inti,intj,intlen)if(i<0!Ij 15k++;)if(!p)returnINFEASIBLE;//在la表中查找第i+len-l个结点q=p；k=l;while(q&&k 16else(while(-i>l)p=p->next;q->next=p->next;p->next=q;〃插入在第i个元素的位置}}//Insert2.18试写一算法，实现线性表操作Delete。,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。解：StatusDelete(LinkList&L,inti)〃在无头结点链表L中删除第i个元素{if(i==l)L=L->next;〃删除第一个元素else{P=L;while(-i>l)p=p->next;p->next=p->next->next;〃删除第i个元素}}//Delete2.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->data 17prev->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试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(4,逆置为解：//顺序表的逆置StatusListOpposeSq(SqList&L){inti;ElemTypex;for(i=0;i 18StatusListOpposeL(LinkList&L){LinkListp,q;P=L；p=p->next;L->next=NULL;while(p){q=P；p=p->next;q->next=L->next;L->next=q;}returnOK;}2.23设线性表A《J，8=(伉，&，…,b“)，试写一个按下列规则合并A,B为线性表C的算法，即使得C=(外,如…,b,"+|,…也)当机4〃时；C={a},b},---,an,bn,an+],---,am)当加>〃时。线性表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; 19pb二B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data 20C=A;while(pa&&pb){if(pa->data 21}i++;})returnOK;}(1)//A、B求交，然后删除相同元素，将结果放在A表中StatusListCrossDelSame_Sq(SqList&A,SqList&B)(inti=0,j=0,k=0;while(i 22pb=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;}(1)//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->data 23if(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;InitListSq(Temp);ListCross_L(B,C,Temp);ListMinusL(A,Temp,D);) 242.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->data 25returnOK;}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);—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;} 26//将单循环链表改成双向链表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&sl,LinkList&s2,LinkList&s3)(LinkListp,q,ptl,pt2,pt3;p=L->next;ptl=sl;pt2=s2;pt3=s3;while(p){if(p->data>=0*&&p->data<=91){q=P；p=p->next;q->next=ptl->next;ptl->next=q;ptl=ptl->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； 27p=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); 28)}elsereturnERROR;returnOK;}2.35采用2.34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。解：StatusInsert_XorLinkedList(XorLinkedList&L,intx,inti)〃在异或链表L的第i个元素前插入元素x(p=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode));r->data=x;if(i==l)〃当插入点在最左边的情况(p->LRPtr=XorP(p.LRPtr,r);r->LRPtr=p;L.left=r;returnOK;}j=l;q=p->LRPtr;〃当插入点在中间的情况while(++j 29while(++j 30)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已知稀疏多项式£,(x)=C|X”+c2xf2+• •+cmxe",其中〃=>em_}>♦♦•>4>0,c,.*0(/=1,2,•••,/«).m>\,试采用存储量同多项式项数m成正比的顺序存储结构，编写求 312(/)的算法(/为给定值)，并分析你的算法的时间复杂度。解：typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{PolyTerm*data;intlast;}SqPoly;//建立一个多项式StatusPolylnit(SqPoly&L)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 32PolyTerm*p,*pl,*p2;p=L.data;pl=Ll.data;p2=L2.data;inti=0,j=0,k=0;while(i 33在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,pl,q,pt;q=L;p=L->next;pl=Ll;while(p!=L){if(p->data.exp%2==0){Pt=P；p=p->next;q->next=p;pt->next=pl->next;pl->next=pt;pl=pl->next;}else{q=P；p=p->next;returnOK;第3章栈和队列 343.1若按教科书3.L1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道)，则请回答：(1)如果进站的车厢序列为123,则可能得到的出站车厢序列是什么？(2)如果进站的车厢序列为123456,则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出以'S，表示进栈和以'X'表示出栈的栈操作序列).解：⑴123231321213132(2)可以得到135426的出站序列,但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。3.2简述栈和线性表的差别。解：线性表是R有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。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)statusalgol(StackS)(inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=l;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); 35解：（1）栈中的数据元素逆置（2）如果栈中存在元素e,将其从栈中清除1.15假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。解：任何前n个序列中S的个数一定大于X的个数。设两个合法序列为：T1=SXST2=SXX假定前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后bo由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。3.6试证明：若借助栈由输入序列12…n得到的输出序列为p〃2…p“（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i 3615#+'IEFOperate(E,,F)16#+IJ#Operated,+,J)17K#RETURN3.8试推导求解n阶梵塔问题至少要执行的move操作的次数。解：2n-13.9试将下列递推过程改写为递归过程。voidditui(intn)(inti;1=n;while(i>l)cout< 37while(!StackEmpty(s)){Pop(s,x);sum+二x;cout< 38)解：队列逆置3.14若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。(3)既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。3.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1,用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解：classDStack{ElemType*top[2];ElemType*p;intstacksize;intdi;public:DStack(intm){p=newElemType[m];if(!p)exit(OVERFLOW);top[0]=p+m/2;top[l]=top[0];stacksize=m;)^DStack(){deletep;}voidPush(inti,ElemTypex)di=i;if(di==O){if(top[0]>=p)*top[0]-=x;elsecerr«*Stackoverflow!*;}else{if(top[l] 39}else{if(top[l]>top[0])return*top[l]一;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―; 40))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―; 41)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)和软席车厢⑸序列：”；cin»Buffer;cout< 42inti=0;Stacks;InitStack(s);ElemTypex;while(a[i]!=，&&a[i]){Push(s,a[i]);i++;}if(a[i])returnFALSE;i++；while(a[i]){Pop(s,x);if(x!=a[i]){DestroyStack(s);returnFALSE;}i++；)returnTRUE;)3.18试写一个判别表达式中开、闭括号是否配对出现的算法。解：BOOLBracketCorrespondency(chara[])inti=0;Stacks;InitStack(s);ElemTypex;while(a[i]){switch(a[i]){case'(':Push(s,a[i]);break;case'[’:Push(s,a[i]);break;case')’：GetTop(s,x);if(x—C)Pop(s,x);elsereturnFALSE;break;case':GetTop(s,x);if(x='「)Pop(s,x); 43elsereturnFALSE;break;default:break;}i++；)if(s.size!=0)returnFALSE：returnTRUE;}3.19假设一个算术表达式中可以包括三种括号：圆括号“和“)”、方括号和和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用(如：…[…{…}…[…]…]…[…]…(-)-)o编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。解：StatusAllBracketsTest(char*str)〃判别表达式中三种括号是否匹配(InitStack(s);for(p=str;*p;p++)(if(*p==C|i*p==，['[*p='{')push(s,*p);elseif(*p==，y|i*p==,],||*p==,},)(if(StackEmpty(s))returnERROR;pop(s,c);if(*p=')'&&c!;'(')returnERROR;if(*p=']'&&c!;'[')returnERROR;if(*p=='}'&&c!='{')returnERROR;〃必须与当前栈顶括号匹配)}//forif(!StackEmpty(s))returnERROR;returnOK;}//AlIBracketsTest3.20假设以二维数组晨1…叫1…n)表示一个图像区域,g[i,j]表示该区域中点(i,j)所具颜色,其值为从0到k的整数。编写算法置换点(i。,j0)所在区域的颜色。约定和(i。,j。)同色的上、下、左、右的邻接点为同色区域的点。解：^include 44typedefstruct{intx;inty;}PosType;typedefstruct{intColor;intVisited;PosTypeseat;}ElemType;^include'd:\VC99\Stack.h*^defineM8^defineN8ElemTypeg[M][N];voidCreateGDS(ElemTypeg[M][N]);voidShowGraphArray(ElemTypeg[M][N]);voidRegionFi11ing(ElemTypeg[M][N],PosTypeCurPos,intNewColor);intmain(){CreateGDS(g);ShowGraphArray(g);PosTypeStartPos;StartPos.x=5;StartPos.y=5;intFillColor=6;RegionFi11ing(g,StartPos,FillColor);cout«endl;ShowGraphArray(g);return0;)voidRegionFi11ing(ElemTypeg[M][N],PosTypeCurPos,intFillColor)(Stacks;InitStack(s);ElemTypee;int01dColor=g[CurPos.x][CurPos.y].Color;Push(s,g[CurPos.x][CurPos.y]); 45while(!StackEmpty(s)){Pop(s,e);CurPos=e.seat;g[CurPos.x][CurPos.y].Color=FillColor;g[CurPos.x][CurPos.y].Visited=l;if(CurPos.x 46voidShowGraphArray(ElemTypeg[M][N])(inti,j;for(i=0;i 473.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,el);c=Cal(el,Buffer[i],e2);Push(Opnd,c);}i++；)returnc;}charCal(charcl,charop,charc2)(intx,xl,x2;charch[10];ch[0]=cl;ch[l]=\0*;xl=atoi(ch);ch[0]=c2;ch[l]=\0*;x2=atoi(ch);switch(op){case'+':x=xl+x2;break;casex=xl-x2; 48break;case':x=xl*x2;break;case'/':x=xl/x2;break;default:break;}itoa(x,ch,10);returnch[0];)3.23如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。解：#include 49if(InvToFroPoland(a))cout< 50}voidTnitStack(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; 51P++；)returnFALSE;}3.24试编写如卜一定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。(0m=O,nNO&-1,2，)+nm>0,n>0解：intg(intm,intn);intmain(){intm,n;cout<<”请输入m和n的值：”；cin»m»n;if(n>=0)cout< 52cout<〈”请输入n:*;cin»n;for(i=0;i 53(1)写出递归算法：(2)写出非递归算法；(3)根据非递归算法，画出求akm(2,l)时栈的变化过程。解：unsignedintakm(unsignedintm,unsignedintn)(unsignedintg;if(m=O)returnn+1;elseif(n==0)returnakm(m-l,1);else(g=akm(m,n-l);returnakm(m-l,g);))非递归算法：intakml(intm,intn)(Stacks;InitStack(s);ElemTypee,el,d;e.mval=m;e.nval=n;Push(s,e);do{while(e.mval){while(e.nval){e.nval—;Push(s,e);}e.mval—;e.nval=l;}if(StackLength(s)>1){el.nval=e.nval;Pop(s,e);e.mval―;e.nval=el.nval+1;})whi1e(StackLength(s)!=11|e.mval!=0);returne.nval+1;0,akm(2,1)1,akm(2,0)g=akm(2,0)akm=akm(m-l,l)=akm(l,1) 542,akm(l,1)411g=akm(m,n_l)=akm(l,0)3,akm(1,0)610akm=akm(m-l,l)=akm(0,1)4,akm(0,1)401akm=n+l=2退栈0,akm(2,1)021g=akm(2,0)l,akm(2,0)620akm=akm(ni-l,l)=akm(l,1)2,akm(l,1)411g=akm(m,n-l)=akm(l,0)3,akm(1,0)610akm=akm(m-l,l)=akm(0,1)=2退栈0,akm(2,1)021g=akm(2,0)1,akm(2,0)620akm=akm(m-l,l)=akm(l,1)2,akm(l,1)411g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2)3,akm(0,2)702akm=n+l=3退栈0,akm(2,1)0211,akm(2,0)6202,akm(l,1)411g=akm(2,0)akm=akm(m_l,l)=akm(l,1)g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2)=3;退栈0,akm⑵1)1,akm(2,0)021620g=akm(2,0)akm=akm(m-1,l)=akn)(l,1)=3退栈0,akm(2,1)021g=akm⑵0)=3;akm=akm(1,3)l,akm(l,3)613g=akm(1,2);akm(m-1,g)2,akm(l,2)612g=akm(l,1);akm(m-l,g)3,akm(l,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(l,2)612g=akm(l,1);akm(m-l,g)3,akm(l,1)611g=akm(1,0);akm(m-l,g)4,akm(l,0)610akm=akm(0,1)=2退栈0,akm(2,1)021g=akm⑵0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2);akm(m-1,g)2,akm(1,2)612g=akm(l,1);akm(m-1,g)3,akm(l,1)611g=akm(1,0)=2;akm(m-l,g)=akm(0,2)4,akm(0,2)702akm=n+l=3退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(l,3)613g=akm(l,2);akm(m-l,g)2,akm(l,2)612g=akm(1,1);akm(m-l,g)3,akm(l,1)611g=akm(1,0)=2;akm(m-l,g)=akm(0,2)=3退栈 550,akm(2,1)021g=akm⑵0)=3;akm=akm(1,3)l,akm(l,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+l=4退栈0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(l,3)613g=akm(1,2);akm(m-l,g)2,akm(l,2)612g=akm(l,1)=3;akm(m-1,g)=akm(0,3)=4退栈0,akm(2,1)021g=akm⑵0)=3;akm=akm(1,3)1,akm(l,3)613g=akm(1,2)=4;akm(m-1,g)=akm(0,4)2,akm(0,4)704akm=n+l=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)akm(2,1)=5;021g=akm(2,0)=3;akm=akm(1,3)=5退栈3.28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列何处队列的算法。解：typedefintElemType;typedefstructNodeType{ElemTypedata;NodeType*next;}QNode,*QPtr;typedefstruct{QPtrrear;intsize;[Queue;StatusInitQueue(Queuedq)(q.rear=NULL;q.size=0;returnOK;)StatusEnQueue(Queue&q,ElemTypee)QPtrp;p=newQNode;if(!p)returnFALSE;p->data=e; 56if(!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(Queuedq,ElemType&e){QPtrp;if(q.size==0)returnFALSE;if(q.size==l){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; 57Statustag;}Queue;StatusInitQueue(Queue&q){q.base二newElemType[MaxQSize];if(!q.base)returnFALSE;q.front=0;q.rear=O;q.tag=O;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=l;)returnOK;)StatusDeQueue(Queue&q,ElemTypefte)(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; 58}Queue;StatusInitQueue(Queue&q)q.base=newElemType[MaxQSize];if(!q.base)returnFALSE;q.rear=O;q.length=O;returnOK;)StatusEnQueue(Queue&q,ElemTypee)(if((q.rear+l)%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);ElemTypeel,e2;while(*p){Push(s,*p)；EnQueue(q,*p); 59p++；)while(!StackEmpty(s)){Pop(s,el);DeQueue(q,e2);if(el!=e2)returnFALSE;}returnOK;)3.32试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，要求满足： 60则插入在队尾。解：//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+l)%q.MaxSize;if(q.rear-q.front)q.tag=l;)else{//非空非满if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){//从队头入队q.front=(q.front+q.MaxSize-l)%q.MaxSize;q.base[q.front]=e;if(q.rear==q.front)q.tag=1;)else{//从队尾入队q.basetq.rear]=e;q.rear=(q.rear+l)%q.MaxSize;if(q.rear==q.front)q.tag=l;))returnOK;}StatusDeDQueue(DQueue&q,ElemTypefte)if(q.front==q.rear&&!q.tag)returnFALSE; 61else{//非空队列e=q.base[q.front];q.front=(q.front+l)%q.MaxSize;q.tag=O;returnOK;)//Filename:XT333.cpp主程序文件#include 62if(ch[i]=-S*)EnDQueue(dq,ch[i],0);//从队头入队if(ch[i]==，W)EnDQueue(dq,ch[i],1);//从队尾入队i++；)while(dq.front!=dq.rearIdq.tag){DeDQueue(dq,e);cout< 63if(!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]八(T;}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+1en<=cur1en&&len>0){temp.curlen=len;for(i=0,j=start;i 64)returntemp;}voidString::show()(cout< 65for(n=0,i=l;i<=Strlen(S)-Strlen(T)+1;i++)〃注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T)),T))〃找到了与T匹配的子串{〃分别把T的前面和后面部分保存为head和tailStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail));〃把head,V,tail连接为新串i+=Strlen(V);〃当前指针跳到插入串以后n++;)//ifreturnn;}//Replace分析：i+二Strlen");这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果，虽然在大多数情况下没有影响.请思考：设S='place',T='ace',V='face',则省掉i+=Strlen(V);运行时会出现什么结果？4.13intDelete_SubString(Stringtype&s,Stringtypet)〃从串s中删除所有与t相同的子串,并返回删除次数(for(n=0,i=l;i<=Strlen(s)-Strlen(t)+l;i++)if(!StrCompare(SubString(s,i,Strlen(t)),t))IStrAssign(head,SubString(S,1,i-l));StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));StrAssign(S,Concat(head,tail));〃把head,tail连接为新串n++;}//ifreturnn,}//DeleteSubString4.14StatusNiBoLan_to_BoLan(Stringtypestr,Stringtype&new)〃把前缀表达式str转换为后缀式new(Initstack(s);//s的元素为Stringtype类型for(i=l;i<=Strlen(str);i++){r=SubString(str,i,1);if(r为字母)push(s,r);else(if(StackEmpty(s))returnERROR;pop(s,a);if(StackEmpty(s))returnERROR;pop(s,b);StrAssign(t,Concat(r,b));StrAssign(c,Concat(t,a));〃把算符r,子前缀表达式a,b连接为新子前缀表达式cpush(s,c);) 66}//forpop(s,new);if([StackEmpty(s))returnERROR;returnOK;}//NiBoLan_to_BoLan分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.4.15voidStrAssign(Stringtype&T,charchars&#;)〃用字符数组chars给串T赋值,Stringtype的定义见课本(for(i=0,T[0]=0;chars[i];T[0]++,i++)T[i+l]=chars[i];}//StrAssign4.16charStrCompare(Stringtypes,Stringtypet)〃串的比较,s>t时返回正数，s=t时返回0,s 67for(i=l;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);if(i>s[0]&&i>t[0])return0;elseif(i>s[0])return-t[i];elseif(i>t[0])returns[i];elsereturns[i]-t[i];}//StrCompare4.17intString_Replace(Stringtype&S,StringtypeT,StringtypeV);〃将串S中所有子串T替换为V,并返回置换次数(for(n=0,i=l;i<=S[0]-T[0]+l;i++){for(j=i,k=l;T[k]&&S[j]==T[k];j++,k++);if(k>T[O])〃找到了与T匹配的子串：分三种情况处理{if(T[0]==V[0])for(l=l;K=T[0];1++)〃新子串长度与原子串相同时:直接替换S[i+l-l]=V[l];elseif(T[0] 68returnn;}//StringReplace 69typedefstruct{charch;intnum;}mytype;voidStrAnalyze(StringtypeS)〃统计串S中字符的种类和个数{mytypeT[MAXSIZE];〃用结构数组T存储统计结果for(i=l;i<=S[0];i++){c=S[i];j=0;while(T[j].ch&&T[j].ch!=c)j++;〃查找当前字符c是否已记录过if(T[j].ch)T[j].num++;elseT[j]={c,1};}//forfor(j=0;T[j].ch;j++)printf(*%c:%d 70*,T[j].ch,T[j].num);}//StrAnalyze4.19voidSubtractString(Stringtypes,Stringtypet,Stringtype&r)〃求所有包含在串s中而t中没有的字符构成的新串r(r[0]=0;for(i=l;i〈=s[0];i++)(c=s[i];for(j=l;!=c;j++);〃判断s的当前字符c是否第一次出现if(i==j)for(k=l;k<=t[0]&4t[k]!=c;k++);〃判断当前字符是否包含在t中if(k>t[0])r[++r[0]]=c：)}//for}//SubtractString4.20intSubString_Delete(Stringtype&s,Stringtypet)〃从串s中删除所有与t相同的子串，并返回删除次数{for(n=0,i=l;i<=s[0]-t[0]+l;i++){for(j=l;j<=t[0]&&s[i+j-1]==t[i];j++);if(j>m)〃找到了与t匹配的子串for(k=i;k<=s[0]-t[0];k++)s[k]=s[k+t[0]];〃左移删除s[0]-=t[0];n++;)}//forreturnn;}//Delete_SubString 714.21typedefstruct{charch;LStrNode*next;}LStrNode,*LString;〃链串结构voidStringAssign(LString&s,LStringt)〃把串t赋值给串s{s=malloc(sizeof(LStrNode));for(q=s,p=t->next;p;p=p->next)(r=(LStrNode*)malloc(sizeof(LStrNode));r->ch=p->ch;q->next=r;q=r;)q->next=NULL;}//StringAssignvoidStringCopy(LString&s,LStringt)〃把串t复制为串s.与前一个程序的区别在于，串s业已存在.(for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)(p->ch=q->ch;pre=p;)while(q)(p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}//StringCopycharStringCompare(LStrings,LStringt)〃串的比较，s>t时返回正数,s=t时返回0,s 72LString*Concat(LStrings,LStringt)〃连接串s和串t形成新串，并返回指针(p=malloc(sizeof(LStrNode));for(q=p,r=s->next;r;r=r->next)(q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for//复制串sfor(r=t->next;r;r=r->next){q->next=(LStrNode*)ma1loc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for〃复制串tq->next=NULL;returnp;}//ConcatLString*Sub_String(LStrings,intstart,intlen)〃返回一个串，其值等于串s从start位置起长为len的子串(p=malloc(sizeof(LStrNode));q=p;for(r=s;start;start—,r=r->next);〃找到start所对应的结点指针rfor(i=l;i<=len;i++,r=r->next)(q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;)〃复制串tq->next=NULL; 73returnp;}//Sub_String4.22voidLStringConcat(LString&t,LString&s,charc)〃用块链存储结构，把串s插入到串t的字符c之后(p=t.head;while(p&&!(i=Find_Char(p,c)))p=p->next;〃查找字符cif(!p)〃没找到(t.tail->next=s.head;t.tail=s.tail;〃把s连接在t的后面}else(q=p->next;r=(Chunk*)malloc(sizeof(Chunk));〃将包含字符c的节点p分裂为两个for(j=0：j 74intLStringPalindrome(LStringL)〃判断以块链结构存储的串L是否为回文序列，是则返回1,否则返回0{InitStack(S);p=S.head;i=0;k=l;//i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)for(k=l;k<=S.curlen;k++)(if(k<=S.curlen/2)Push(S,p->ch[i]);//将前半段的字符入串elseif(k>(S.curlen+l)/2)(Pop(S,c);〃将后半段的字符与栈中的元素相匹配if(p->ch[i]!=c)return0;〃失配)if(++i==CHUNKSIZE)〃转到下一个元素，当为块中最后一个元素时，转到下一块(p=p->next;i=0;}}//forreturn1;〃成功匹配}//LStringPalindrome4.24voidHString_Concat(HStringsi,HStrings2,HString&t)//将堆结构表示的串si和s2连接为新串t(if(t.ch)free(t.ch);t.ch=malloc((si.Iength+s2.length)*sizeof(char));for(i=l;i<=sl.length;i++)t.ch[i-l]=sl.ch[i-l];for(j=l;j<=s2.length;j++,i++)t.ch[i-l]=s2.ch[j-l];t.length=sl.Iength+s2.length;}//HString_Concat4.25intHString_Replace(HString&S,HStringT,HStringV)〃堆结构串上的置换操作，返回置换次数{for(n=0,i=0;i<=S.length-T.length;i++)(for(j=i,k=0;k 75if(T.length==V.length)for(1=1;1<=T.length;1++)〃新子串长度与原子串相同时:直接替换S.ch[i+l-l]=V.ch[l-l];elseif(T.length 76)elseIi++；j++；)}//whileif(j>t[0])returni-t[0];}//Index_New4.28voidLGetnext(LString&T)〃链串上的getnext算法(p=T->succ;p->next=T;q=T;while(p->succ)(if(q==T||p->data-q->data)(p=p->succ;q=q->succ;p->next=q;)elseq=q->next;}//while}//LGet_next4.29LStrNode*LIndex_KMP(LStringS,LStringT,LStrNode*pos)〃链串上的KMP匹配算法，返回值为匹配的子串首指针(p=pos;q=T->succ;while(p&&q){if(q==T||p->chdata==q->chdata){p=p->succ;q=q->succ;)elseq=q->next;}//whileif(!q)(for(i=l;i<=Strlen(T);i++)p=p->next;returnp;)〃发现匹配后，要往回找子串的头returnNULL;}//LIndex_KMP4.30 77voidGet_LRepSub(StringtypeS)〃求S的最长重复广串的位置和长度(for(maxlen=0,i=l;i〈S[0];i++)〃串S2向右移i格(for(k=0,j=l：j<=S[O]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动(if(S[j]==S[j+i])k++;〃用k记录连续相同的字符数elsek=0;〃失配时k归零if(k>maxlen)〃发现了比以前发现的更长的重复子串{lrsl=j_k+l;lrs2=mrsl+i;maxlen=k;//作记录)}//for}//forif(maxien)(printf("LongestRepeatingSubstringlength:%d 78'z,maxlen);printf("Position1:%dPosition2:%d 79"',Irsl,lrs2);}elseprintf(^NoRepeatingSubstringfound! 80");}//GetLRepSub分析:i代表"错位值”.木算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串，则必然能在此过程中被发现.用变量Irsl,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置，第二次出现位置和长度.题目中未说明"重复子串”是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k〈=i即可.本算法时间复杂度为0(Strlen(S)~2).4.31voidGetLPubSub(StringtypeS,StringtypeT)〃求串S和串T的最长公共子串位置和长度(if(S[0]>=T[0DStrAssign(A,S);StrAssign(B,T);else(StrAssign(A,T);StrAssign(B,S);)〃为简化设计,令S和T中较长的那个为A,较短的那个为Bfor(maxlen=0,i=l-B[0];i 81}//B有一部分在A左端的左边elseif(i>A[0]-B[0])jmin=i;jmax=A[0];}//B有一部分在A右端的右边else{jmin=i;jmax=i+B[0];}//B在A左右两端之间.〃以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点：jmin,jmax.for(k=0,j=jmin;j<=jmax;j++)|if(A[j]==B[j-i])k++;elsek=0;if(k>maxlen)lpsl=j-k+l;lps2=j-i-k+l;maxlen=k;)}//for}//forif(maxien){if(S[0]>=T[0]){lpsS=lpsl;lpsT=lps2;)else|lpsS=lps2;lpsT=lpsl;)〃将A,B上的位置映射回S.T上的位置printf(",LongestPublicSubstringlength:%d 82w,maxlen)：printf(""PositioninS:%dPositioninT:%d 83”,IpsS,IpsT); 84}//ifelseprintf("NoRepeatingSubstringfound! 85");}//GetLPubSub分析:本题基本思路与上题同.唯一的区别是，由于A,B互不相同，因此B不仅要向右错位,而且还要向左错位，以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同，请读者自己画图以帮助理解.本算法的时间复杂度是。(strlrn(s)*strlen(t))。第5章数组与广义表4.1解:(1)6X8X6=288Byte(2)L0C(5,7)=1000+(5X8+7)X6=1282(3)LOC(1,4)=1000+(1X8+4)X6=1072(4)LOC(4,7)=1000+(7X6+4)X6=12765.2解：(1)LOC(O,0,0,0)=100(2)LOC(1,1,1,1)=1OO+(1X3X5X8+1X5X8+1X8+1)X4=776(3)L0C(3,1,2,5)=100+(3X3X5X8+1X5X8+2X8+5)X4=1784(4)L0C(8,2,4,7)=100+(8X3X5X8+2X5X8+4X8+7)X4=44165.3解：(0,0,0,0)(0,0,2,0)(0,0,1,1)(0,0,0,2)(0,0,2,2)(1,0,0,0)(1,0,2,0)(1,0,1,1)(1,0,0,2)(1,0,2,2)(0,1,0,0)(0,1,2,0)(0,1,1,1)(0,1,0,2)(0,1,2,2)(1,1,0,0)(1,1,2,0)(1,1,1,1)(1,1,0,2)(1,1,2,2)(0,0,1,0)(0,0,0,1)(0,0,2,1)(0,0,1,2)(1,0,1,0)(1,0,0,1)(1,0,2,1)(1,0,1,2)(0,1,1,0)(0,1,0,1)(0,1,2,1)(0,1,1,2)(1,1,1,0)(1,1,0,1)(1,1,2,1)(1,1,1,2)a”,a(a+1),5.4解：k=--+b2其中，a=Max(i,j),b=Min(i,j)5.5解：k=ni-(n-j)-^^-l(i>l,j>l,i>j)11,f,(i)=(n+-)i--rf(j)=jc=-(n+l)5.6解：u=i-j+lv=j-l5.7解：(1)k=2(i-l)+j-l(2)i=(k+DDIV3+1(0 865.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[LI]]](2)GetHead[GetHead[GetTail[L2]]](3)GetHead[GetHead[GetTail[GetTail[GetHead[L3]]]]](4)GetHead[GetHead[GetHead[GetTail[GetTail[L4]]]]](5)GetHead[GetHead[GetTai1[GetTai1[L5]]]](6)GetHead[GetTail[GetHead[L6]]](7)GetHead[GetHead[GetTail[GetHead[GetTail[L7]]]]]5.12解：6.13解：(1)List=((x,(y)),(((())),(0),(z)))(2)List=(((a,b,()),()),(a,(b)),())5.14解：s(n)=s(n-l)+an=s(n-1)+a1+(n—l)d(n>=l)ElemTypes(inti)(if(i>l)returns(i-l)+al+(i-l)*d; 87elsereturnal;)b=0b>0[a5.16解：add(a,b)=<[add(++a,—b)5.17解：intMax(SqList&L,intk)(if(k 88returnL.elem[O];elsereturn(Avg(a,k-l)*k+L.elem[k])/(k+1);)5.18解：算法的基本思想是招数组分成k组，将第一组与第二组进行两两交换，再将第一组与第三组进行两两交换，・・・，总共需进行n-k次交换。注意最后一组可能出现不足k个元素的情况，此时最后一组为剩余元素加第一组的前几个元素共k个构成最后一组。voidRRMove(ElemTypeA[],intk,intn){ElemTypee;inti=0,j,p;while(i 89(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;i 90x=a[k][i].e;returnx;)ElemTypeColMax(NodeTypea[RS][CS],intk)(ElemTypex;x=a[0][k].e;inti;for(i=l;i 91for(i=0;i 92}BOOLTriple::operator==(Tripleb){if(row==b.row&&col==b.col)returnTRUE;elsereturnFALSE;)classCSparseMat(public:CSparseMat(){}virtual^CSparseMat(){}CSparseMat(intr,intc,intn);CSparseMatoperator+(CSparseMatB);voidShowSparse(CDC*pDC);Triple*m_pt;//指向非零元的指针intm_nCol;//矩阵列数intm_nRow;//矩阵行数intm_nTrs;//非零元个数)；CSparseMat::CSparseMat(intr,intc,intn)m_nRow=r;m_nCol=c;m_nTrs=n;m_pt=newTriple[m_nTrs];//输入矩阵的所有三元组inti;for(i=0;i 93k++;)elseitoa(0,str,10);pDC->TextOut(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,mpt=newTriple[mnTrs+B.mnTrs];if(!temp.m_pt)returntemp;temp.m_nTrs=m_nTrs+B.m_nTrs;inti=0;intj=0;intk=0;while(i 94temp.m_pt[k].row=m_pt[i].row;temp.m_pt[k].col=m_pt[i].col;temp.m_pt[k].e=m_pt[i].e;i++；k++;)while(j 95A.data[pc].j=B.data[pb].j;A.data[pc].e=B.data[pb].e;pb++;pc++;)else{A.datatpc].i=x;A.data[pc].j=A.data[pa],j;A.data[pc].e=A.data[pa],epa++;pc++;)}//whilewhile(A.data[pa]=x)〃插入A中剩余的元素(第x行)(A.data[pc].i=x;A.data[pc].j=A.data[pa].j;A.data[pc].e=A.data[pa],epa++;pc++;while(B.data[pb]==x)//插入B中剩余的元素(第x行)(A.data[pc].i=x;A.data[pc].j=B.data[pb].j;A.data[pc].e=B.data[pb].e;pb++;pc++;)}//forA.tu=pc;for(i=A.tu;i 96Twin*m_pt;//指向非零元的指针intrpos[Max];intm_nCol;//矩阵列数intm_nRow;//矩阵行数intm_nTws;//非零元个数)；CSparseMat::CSparseMat(intr,intc,intn)mnRow=rm_nCol=cmnTws=nm_pt=newTwin[m_nTws];if(!m_pt)return;//输入矩阵的所有二元组inti;for(i=0;i 97if(s>=0){intk=s;while(k 98)BMMatrix;〃用位图表示的矩阵类型voidBMMatrix_Add(BMMatrixA,BMMatrixB,BMMatrix&C)〃位图矩阵的加法(C.mu=A.mu;C.nu=A.nu;pa=l;pb=l;pc=l;for(i=0;i 99CCrossListMat(intr,intc,intn);virtual^CCrossListMat(){}voidShowMat(inti,intj);)；CCrossListMat::CCrossListMat(intr,intc,intn)(m_nRow=r;m_nCol=c;mnNum=n;inti;RHead=newOLink[m_nRow];if(!RHead)exit(-2);CHead=newOLink[m_nCol];if(JCHead)exit(-2);for(i=0;i 100}))voidCCrossListMat::ShowMat(inti,intj){ElemTypex=0;OLinkp;p=RHead[i];while(p&&p->col!=j)p=p->right;if(p)x=p->e;cout< 101RHead=newOLink[mnRow];if(!RHead)exit(-2);CHead=newOLink[mnCol];if(!CHead)exit(-2);for(i=0;i 102inti,k=0;OLinkpa,pb;OLinkpre,p;//按行插入OLinkqpre,q;//按列插入for(i=0;i 103}//endform_nNum=m_nNum+k;}voidCCrossListMat::ShowMat()inti,j;OLinkp;for(i=0;i 104〃将非空串Str分割成两部分，HStr为第一个，TStr为之后的子串intStrDistrict(CString&Str,CString&HStr,CString&TStr)(intn,i,k;CStringsi;CStrings2s3("("),s4(")");〃定义常量串n=Str.StrLength();i=l；k=0;while(i<=n&&sl.StrCompare(s2)||k!=0){si=Str.SubString(i,1);if(!sl.StrCompare(s3))k++;elseif(!sl.StrCompare(s4))k-;i++；)if(i<=n){HStr=Str.SubStringd,i-2);TStr=Str.SubString(i,n-i+l);}else{HStr=Str;TStr.StrClear();}returnOK;)//用串s建立广义表LintCreateGList(GList&L,CString&s)(CStringSub,HSub,TSub;〃子串，表头串，表尾串if(s.StrEmptyO)L=NULL;else{//非空串，建立广义表L=newGLNode;//开辟一个结点if(!L)exit(OVERFLOW);if(s.StrLength()>l){//如果串长大于1,说明是表结点L->tag=LIST;Sub=s.SubString(2,s.StrLength()-2);//取括号内子串if(!Sub.StrEmptyO){//建立子表StrDistrict(Sub,HSub,TSub);if(!HSub.StrEmpty())//表头不空CreateGList(L->hp,HSub);elseL->hp=NULL;if(!TSub.StrEmptyO)//表尾不空CreateGList(L->tp,TSub);elseL->tp=NULL; 105}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< 106voidMPList_Add(MPListA,MPListB,MPList&C)〃广义表存储结构的多项式相加的递归算法{C=(MPLNode*)malloc(sizeof(MPLNode));if(!A->tag&&!B->tag)〃原子项,可直接相加{C->coef=A->coef+B->coef;if(!C->coef)(free(C);C=NULL;)}//ifelseif(A->tag&&B->tag)〃两个多项式相加{p=A;q=B;pre=NULL;while(p&&q)(if(p->exp==q->exp)(C=(MPLNode*)malloc(sizeof(MPLNode));C->exp=p->exp;MPList_Add(A->hp,B->hp,C->hp);pre->tp=C;pre=C;p=p->tp;q=q->tp;}elseif(p->exp>q->exp){C=(MPLNode*)malloc(sizeof(MPLNode));C->exp=p->exp;C->hp=A->hp;pre->tp=C;pre=C;p=p->tp;}elseC=(MPLNode*)malloc(sizeof(MPLNode));C->exp=q->exp;C->hp=B->hp;pre->tp=C;pre=C;q=q->tp;)}//whilewhile(p)IC=(MPLNode*)malloc(sizeof(MPLNode));C->exp=p->exp; 107C->hp=p->hp;pre->tp=C;pre=C;p=p->tp;}while(q)(C=(MPLNode*)malloc(sizeof(MPLNode));C->exp=q->exp;C->hp=q->hp;pre->tp=C;pre=C;q=q->tp;)〃将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题}//elseifelseif(A->tag&&!B->tag)〃多项式和常数项相加(x=B->coef;for(p=A;p->tp->tp;p=p->tp);if(p->tp->exp==0)p->tp->coef+二x;〃当多项式中含有常数项时，加上常数项if(!p->tp->coef)(free(p->tp);p->tp=NULL;)else(q=(MPLNode*)malloc(sizeof(MPLNode));q->coef=x;q->exp=0;q->tag=0;q->tp=NULL;p->tp=q;)〃否则新建常数项，下同}//elseifelsex=A->coef;for(p=B;p->tp->tp;p=p->tp);if(p->tp->exp~0)p->tp->coef+=x;if(!p->tp->coef)(free(p->tp);p->tp=NULL;)else(q=(MPLNode*)malloc(sizeof(MPLNode));q->coef=x;q->exp=0;q->tag=0;q->tp=NULL;p->tp=q;}}//else}//MPList_Add5.30解: 108II求广义表深度的递归算法intGListDepth(GList&L)(intDepth=0;intHDepth,TDepth;//表头深度，表尾深度if(!L)returnDepth;//广义表不存在if(L->tag==AT0M)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==AT0M)T->atom=L->atom;else{CopyGList(T->hp,L->hp);CopyGList(T->tp,L->tp);)}returnOK;)5.32解：//判两广义表是否相等，相等返回0K,否则返回FALSEStatusGListCompare(GList&LI,GList&L2)(if(!Ll&&!L2)returnOK;//LI和L2均为空表if((!Ll&&L2)||(LI&&!L2))returnFALSE;else{〃口和L2均非空表if(Ll->tag-L2->tag){//表属性相同if(Ll->tag==ATOM){//均为原子结点if(Ll->atom==L2->atom)returnOK;elsereturnFALSE;}else{//均为表结点if(GListCompare(Ll->hp,L2->hp)&&GListCompare(Ll->tp,L2->tp))returnOK;//表头、表尾均相同elsereturnFALSE;))elsereturnFALSE;//表属性不同))5.33解：voidGList_PrintElem(GListA,intlayer)〃递归输出广义表的原子及其所在层次，layer表示当前层次(if(!A)return;if(!A->tag)printf(*%d%d 109*»A->atom,layer);else(GListPrintElem(A->ptr.hp,layer+1);GList_PrintElem(A->ptr.tp,layer);〃注意尾表与原表是同一层次}}//GList_PrintElem5.34voidGListReverse(GListA)〃递归逆转广义表A(GLNode*ptr[MAX_SIZE];if(A->tag&&A->ptr.tp)〃当A不为原子且表尾非空时才需逆转(for(i=0,p=A;p;p=p->ptr.tp,i++)(if(p->ptr.hp)GList_Reverse(p->ptr.hp);〃逆转各子表ptr[i]=p->ptr.hp; 110}for(p=A;p;p=p->ptr.tp)//重新按逆序排列各子表的顺序p->ptr.hp=ptr[-i];}}//GList_Reverse5.35StatusCreate_GList(GList&L)〃根据输入创建广义表L,并返回指针(scanf(*%c*,&ch);if(ch==，')(L=NULL;scanf&ch);if(ch!==')')returnERROR;returnOK;}L=(GList)malloc(sizeof(GLNode));L->tag=l;if(isalphabet(ch))〃输入是字母{p=(GList)malloc(sizeof(GLNode));〃建原子型表头p->tag=0;p->atom=ch;L->ptr.hp=p;)elseif(ch=*C)Create_GList(L->ptr.hp);〃建子表型表头elsereturnERROR;scanf&ch);if(ch==，)*)L->ptr.tp=NULL;elseif(ch=，,*)Create_GList(L->ptr.tp);〃建表尾elsereturnERROR;returnOK;}//CreateGList分析:本题思路见书后解答.5.36voidGList_PrintList(GListA)〃按标准形式输出广义表(if(!A)printfCOO；〃空表elseif(!A->tag)printf("%d”,A->atom);〃原子else(printf("(");for(p=A;p;p=p->ptr.tp)(GList_PrintList(p->ptr.hp);if(p->ptr.tp)printf只有当表尾非空时才需要打印逗号)printf(")"); 111}//else}//GList_PrintList5.37voidGListDelElem(GList&A,intx)〃从广义表A中删除所有值为x的原子{if(A&&A->ptr.hp)(if(A->ptr.hp->tag)GListDelElem(A->ptr.hp,x);elseif(!A->ptr.hp->tag&&A->ptr.hp->atom~x)(q二A;A=A->ptr.tp;〃删去元素值为x的表头free(q);GList_DelElem(A,x);if(A&&A->ptr.tp)GList_DelElem(A->ptr.tp,x);}//GList_DelElem5.38voidGListPrintElemLOrder(GListA)〃按层序输出广义表A中的所有元素(InitQueue(Q);for(p=L;p;p=p->ptr.tp)EnQueue(Q,p);whi1e(!QueueEmpty(Q))DeQueue(Q,r);if(!r->tag)printfr-〉atom);elsefor(r=r->ptr.hp;r;r=r->ptr.tp)EnQueue(Q,r);}//while}//GListPrintElemLOrder分析:层序遍历的问题，一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.6章树和二叉树6.1已知一棵树边的集合为 112(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的结点有右兄弟的条件是什么？其右兄弟的编号是多少？kH_1解：⑴k-1(2)如果p是其双亲的最小的孩子(右孩子)，则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子(左孩子)，则p+k-1为其最小的弟弟，再减去一个根结点，除以k,即为其双亲结点的编号。综合来说，对于p是左孩子的情况，i=(p+k-2)/k；对于p是右孩子的情况，i=(p-l)/k如果左孩子的编号为P，则其右孩子编号必为p+k-1,所以，其双亲结点的编号为 113p+k—1向下取整，如1.5向下取整为1(3)结点p的右孩子的编号为kp+1,左孩子的编号为kp+l-k+l=k(p-l)+2,第i个孩子的编号为k(p-l)+2+i-l=kp-k+i+l.(4)当(pT)%k!=0时，结点p有右兄弟，其右兄弟的编号为p+1。6.5已知一棵度为k的树中有〃।个度为1的结点，〃2个度为2的结点，…，个度为k的结点，问该树中有多少个叶子结点？解：根据树的定义，在一颗树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加1。总结点数为1+/+2々+3〃3+•••+而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即*=1++2n2+3%+•••+knk—(n,+n2+n3+...+nk)=1+i=i6.6已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子节点数目。解：利用上题结论易得结果。设度为k的结点个数为〃小则总结点数为〃=1+〃叶子结点的数目应等于总结点数减去度不为0的结点的数目，即M—1nQ=n-nk=nk6.7一棵含有n个结点的k又树，可能达到的最大深度和最小深度各为多少？解：能达到最大深度的树是单支树，其深度为n。满k叉树的深度最小，其深度为「log*(〃(k-1)+1)1(证明见徐孝凯著数据结构实用教程P166)6.8证明：一棵满k叉树上的叶子结点数〃0和非叶子结点数〃।之间满足以下关系：%=(4-1)叫+1解：一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为〃()=k%T,其总结点数心kh-]kn-1为，则非叶子结点数为=项)=项)，从而得k-l1k-1°k-1°〃o=(A—l)〃i+16.9试分别推导含有n个结点和含n0个叶子结点的完全三叉树的深度Ho解：(1)根据完全三叉树的定义“HT_1kH_1- 1142/?+l<3w<3(2n+1)log3(2n+1) 115空间。6.12对题6.3所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。解：6.13假设n和m为二叉树中两结点，用1、0或#(分别表示肯定、恰恰相反或不一定)填写下表：已知前序遍历时n在m前？中序遍历时n在m前？后序遍历时n在m前？n在m左方n在m右左方n是m祖先n是m子孙注：如果⑴离a和b最近的共同祖先p存在，且(2)a在p的左子树中，b在p的右子树中,则称a在b的左方(即b在a的右方)。解：6.14找出所有满足下列条件的二叉树：(a)它们在先序遍历和中序遍历时，得到的节点访问序列相同；(b)它们在后序遍历和中序遍历时，得到的结点访问序列相同：(c)它们在先序遍历和后序遍历时，得到的节点访问序列相同。解：(a)不含左子树的二叉树。(b)不含右子树的二叉树。(c)即不含左子树，也不含右子树的二叉树。6.15解：6.16解：12J%34567891011121314InfoABCDEFGHIJKLMNLtag00010101001111Lchild246273101412131391011Rtag00110001110111Rchild35658911312131401186.17解：其错误在于中序遍历应先访问其左子树，可做如下修改:BiTreeInSucc(BiTreeq){//一直q是指向中序线索二叉树上某个结点的指针，//本函数返回指向*q的后继的指针。r=q->rchild;if(!r->ltag) 116while(!r->ltag)r=r->lchild;returnr;}//InSucc6.18解：如果p是根结点，则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历，如果某结点的左指针域等于P，说明该结点是p的双亲结点，且p是它的左孩子；如果某结点的右指针域等于P，说明该结点是P的双亲结点，且p是它的右孩子；如此即可确定访问次序。若是右孩子，其后继是双亲结点；若是左孩子，其后继是其兄弟最左下的子孙，如果兄弟不存在，其后继是其双亲结点。6.19分别画出和下列树对应的各个二叉树：解：(2)中序：348675211091115141312(3)后序：8765432101514131211916.23解：树的先根序列为GFKDAIEBCHJ,后根序列为DIAEKFCJHBG,可以先转化成二叉树，再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同，二叉树的中序序列对应着树的后根序列。 117GFKDAIEBCHJ为所求二叉树的先序序列，DIAEKFCJHBG为二叉树的中序序列。通过观察先序序列，G为二叉树的根结点，再由中序序列，G的左子树序列为D1AEKFCJHB,右子为空。可以表示成如下形式：G(DIAEKFCJHB,NULL)对于子树先序序列为FKDAIEBCHJ,中序序列为DIAEKFCJHB,显然子树根为F。再由中序序列可以看到，F的左子树是DIAEK,右子树为CJHB。进一步表示成：G(F(DIAEK,CJHB),NULL)对于DIAEK(中序表示)，先序为KDA1E,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+l时，要使其成为最优，必须用k个结点的哈夫曼树与第k+1个结点组成一个新的最优二叉树，所以n=k+l时也成立。6.26解：不妨设这8个结点为A、B,C、D、E、F,G、H,其相应的权为7、19、2、6、32、3、21、10o 118too214。196003228171110B:01C:lllllD:1110E:10G:00H:1100采用这种方式编码，电文最短。6.27解:6.33解：intVisit(intu,intv)(1f(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解： 119intVisit(intu,intv)(intNv;Nv=NumElem(v);//返回结点v的下标if(Nv==-1)exit(-2);//结点v不存在，退出if(u==v)return1;if(L[Nv]=O){〃左子树不存在if(R[Nv]=O)〃右子树也不存在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 120//若某结点编号为奇数，//则它必为其双亲的右孩子，否则为左孩子//编号为k的结点的双亲结点的编号为k/2intNumTree(charc);//求结点在树中的编号intExp(inta,intb);//求a的b次方intNumElem(charc);//返回元素在数组中的下标intmain()(charc;cout<<〃请输入结点的值：〃；cin»c;cout< 121//返回结点在数组T中的下标intNumElem(charc)(inti=0;while(i 122returnOK;)6.38解：typedefstruct{BTNode*ptr;enum{0,1,2}mark;}PMType;〃有mark域的结点指针类型voidPostOrder_Stack(BiTreeT)〃后续遍历二叉树的非递归算法，用栈{PMTypea;InitStack(S);〃S的元素为PMType类型Push(S,{T,0});〃根结点入栈while(!StackEmpty(S))(Pop(S,a);switch(a.mark)(case0:Push(S,{a.ptr,1});〃修改mark域if(a.ptr->lchiId)Push(S,{a.ptr->lchild,0});〃访问左子树break;case1:Push(S,{a.ptr,2});//修改mark域if(a.ptr->rchild)Push(S,{a.ptr->rchild,0});〃访问右子树break;case2:visit(a.ptr);〃访问结点，返回)}//while}//PostOrder_Stack分析：为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=l表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.6.39解：typedefstruct{intdata;EBTNode*lchild;EBTNode*rchiId;EBTNode*parent;enum(0,1,2}mark; 123}EBTNode,EBitree;〃有mark域和双亲指针域的二叉树结点类型voidPostOrder_Nonrecursive(EBitreeT)〃后序遍历二叉树的非递归算法，不用栈(P=T;while(p)switch(p->mark)(case0:p->mark=l;if(p->lchild)p=p->lchild;〃访问左子树break;case1:p->mark=2;if(p->rchild)p=p->rchild;〃访问右子树break;case2:visit(p);p->mark=0;〃恢复mark值p=p->parent;〃返回双亲结点)}//PostOrderNonrecursive分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.6.40解：typedefstruct{intdata;PBTNode*lchild;PBTNode*rchild;PBTNode"parent;}PBTNode,PBitree;〃有双亲指针域的二叉树结点类型voidInorder_Nonrecursive(PBitreeT)〃不设栈非递归遍历有双亲指针的二叉树(P=T；while(p->lchild)p=p->lchild;〃向左走到尽头while(p)(visit(p);if(p->rchild)〃寻找中序后继:当有右子树时p=p->rchiId;while(p->lchild)p=p->lchild;〃后继就是在右子树中向左走到尽头)elseif(p->parent->lchild==p)p=p->parent;〃当自己是双亲的左孩子时后继就是双亲else(p=p->parent;while(p->parent&&p->parent->rchild==p)p=p->parent; 124p=p->parent;}〃当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先}//while}//Inorder_Nonrecursive6.41解：//求位于先序序列中第k个位置的结点的值，//e中存放结点的返回值，i为计数器StatusPONodeK(TElemType&e,int&i,intk,BiTree&T)Iif(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;)7.43解：//按先序交换二叉树的左右子树StatusExchangeBiTree(BiTree&T)BiTreep;if(T){p=T->lchild;T->Ichiid=T->rchild;T->rchild=p;ExchangeBiTree(T->lchild);ExchangeBiTree(T->rchiId);}returnOK;} 1256.44解：//求二叉树中以元素值为x的结点为根的子树的深度StatusChiIdTreeDepth(BiTree&T,TElemTypex,int&depth)(BiTreeT1;if(PreOrderLocate(T,x,Tl)){depth=BiTDepth(Tl);returnOK;)elsereturnERROR;}//按先序在树中查找根为x的子树，Tl为指向子树根的指针StatusPreOrderLocate(BiTree&T,TElemTypex,BiTree&Tl)(ifCT){if(T->data==x){T1=T;returnOK;)else{if(PreOrderLocate(T->1chi1d,x,Tl))returnOK;else{if(PreOrderLocate(T->rchiId,x,Tl))returnOK;elsereturnERROR;}})elsereturnERROR;//求二叉树的深度intBiTDepth(BiTree&,T)(intIdep,rdep;if(!T)return0;else(ldep=BiTDepth(T->lchild)+l;rdep=BiTDepth(T->rchiId)+1;returnldep>rdep?ldep:rdep;))6.45解：//删除以元素值为x的结点为根的子树StatusDelChildTree(BiTree&T,TElemTypex) 126(ifCr){if(T->data==x){DelBTree(T);T=NULL;returnOK;}else{if(DelChildTree(T->lchild,x))returnOK;else{if(DelChildTree(T->rchiId,x))returnOK;elsereturnERROR;}))elsereturnERROR;}//删除二叉树StatusDelBTree(BiTree&T)(if(T){DelBTree(T->lchild);DelBTree(T->rchiId);deleteT;returnOK;)elsereturnERROR;6.46解://复制一棵二叉树StatusCopyBiTree(BiTree&T,BiTree&Tl)(BiTreep;if(T){p=newBiTNode;if(!p)returnERROR;p->data=T->data;Tl=p;CopyBiTree(T->lchiId,Tl->lchild);CopyBiTree(T->rchiId,Tl->rchiId);}else{ 127T1=T;}returnOK;)6.47解：typedefBiTreeQElemType;#include"c:\Yin\include\Queue.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中求结点*口和*q的共同最小祖先eStatusMinComAncst(BiTree&T,TElemType&e,TElemType*p,TElemType*q)(if(!T)returnERROR;BiTreeTl,T2,pt=NULL;if(!CopyBiTree(T,Tl))returnERROR;if(!CopyBiTree(T,T2))returnERROR;if(!PathTree(Tl,p))returnERROR;//求根结点到结点p的路径树T1elseShowBiTree(Tl);cout< 128Tl=Tl->rchild;T2=T2->rchild;})}if(!pt)returnERROR;else{e=pt->data;returnOK;)}//在二叉树T中求根到结点p的路径树，该操作将剪去除路径之外的所有分支StatusPathTree(BiTree&T,TElemType*p)Iif(!TI|!p)returnERROR;if(T->data==*p){//找到目标，删除目标的左右子树if(T->lchild)DelBiTree(T->lchild);if(T->rchild)DelBiTree(T->rchild);returnOK;}else{//没找到目标，继续递归查找if(PathTree(T->lchiId,p)){//目标在左子树中，删除右子树if(T->rchild)DelBiTree(T->rchiId);returnOK;)elseif(PathTree(T->rchiId,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>l)returnERROR;else(if(CompleteBiTree(T->lchiId)&&CompleteBiTree(T->rchi1d))returnOK;elsereturnERROR;} 129)elsereturnOK;)6.50解：StatusCreateBitreeTriplet(Bitree&T)〃输入三元组建立二叉树(if(getchar()!='')returnERROR;T=(BTNode*)malloc(sizeof(BTNode));p=T;p->data=getchar();getcharO;〃滤去多余字符InitQueue(Q);EnQueue(Q,T);while((parent=getchar())!=,&&(child=getchar0)&&(side=getchar()))(while(QueueHead(Q)!=parent&&!QueueEmpty(Q))DeQueue(Q,e);if(QueueEmpty(Q))returnERROR;〃未按层序输入p二QueueHead(Q);q二(BTNode*)malloc(sizeof(BTNode));if(side==，L*)p->lchild=q;elseif(side=二'R')p->rchild=q;elsereturnERROR;〃格式不正确q->data=child;EnQueue(Q,q);}returnOK;}//CreateBitree_Triplet6.51解：StatusShowBiTExpress(BiTree&T)(if(T){if(T->lchild){if(Low(T->Ichild->data,T->data)){cout«*(*;ShowBiTExpress(T->lchild);cout<<‘)’;|elseShowBiTExpress(T->lchiId);)cout< 130})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;Stacksi,s2;InitStack(si);InitStack(s2);for(i=0;i<20;i++){nn[i]=0;//每层结点个数)if(p)Push(sl,p);elsereturn0;for(i=0;i 131for(i=0;i 132p->data=ST.Get(i);p->lchild=NULL;p->rchild=NULL;LT=p;Queueq;InitQueue(q);EnQueue(q,p);len=ST.Length();while(!QueueEmpty(q)&&i 133elsereturnDescendNum(T->rchiId)+1;}else{if(!T->rchild)returnDescendNum(T->lchild)+l;elsereturnDescendNum(T->rchiId)+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)(ifCr){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->lchiId,pre);if(T->RTag==Link)PreThreading(T->rchiId,pre);}returnOK; 134}//从二叉线索树上任一结点q开始查找结点*P。//如果找到，将*p的后继结点指针存于q中，返回TRUE；否则返回FALSEStatusFindNextlnBiThrTree(BiThrTree&q,TElemType*p)(BiThrTreept=q;if(!pt)returnFALSE;if(pt->data==*p){if(pt->LTag-Link)q=pt->lchild;elseq=pt->rchiId;returnOK;)pt=q->rchild;while(pt!=q&&pt->data!=*p){if(pt->LTag==Link)pt=pt->lchiId;elsept=pt->rchiId;}if(pt==q)returnFALSE;if(pt->data==*p){if(pt->LTag=Link)q=pt->lchiId;elseq=pt->rchild;)returnOK;}6.57解：StatusPostOrderThreading(BiThrTree&T,BiThrTree&pre);〃首先建立后序线索树StatusFindNextInBiThrTree(BiThrTree&q,TElemType*p);〃再进行杳找//后序线索二叉树的算法StatusPostOrderThreadin晨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; 135)returnOK;}StatusPostThreading(BiThrTree&T,BiThrTree&pre)(if(T){if(T->LTag==Link)PostThreading(T->lchild,pre);if(T->RTag==Link)PostThreading(T->rchiId,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=0){T=NULL;)else{T=newCSNode;if(!T)returnERROR;T->data=ch;CreateTree(T->firstchiId);CreateTree(T->nextsibling);)returnOK;}//输出树的各边StatusShowTree(CSTree&T,CSTree&Father)(if(T&&Father)cout«*(*«Father->data«*,*«T->data«")*;if(T->firstchild)ShowTree(T->firstchild,T);if(T->nextsibling)ShowTree(T->nextsibling,Father);returnOK;)6.59解：voidPrint_CSTree(CSTreeT)〃输出孩子兄弟链表表示的树T的各边for(child=T->firstchild;chiId;child=child->nextsib)printf(*(%c,%c),T->data,child->data);Print_CSTree(child); 136)}//Print_CSTree6.60解：intLeafNum(CSTree&T){if]){if(!T->firstchild)returnl+LeafNum(T->nextsibling);elsereturnLeafNum(T->firstchild)+LeafNum(T->nextsibling);)elsereturn0;}6.61解：intDegreeNum(CSTree&T){intd,dl,dr;ifCT){if(!T->firstchild)d=0;elsed=l+RSiblingNum(T->firstchiId);dl=DegreeNum(T->firstchild);dr=DegreeNum(T->nextsibling);returnMax(d,dl,dr);//三数中求最大者)elsereturn0;)//返回当前结点的兄弟数intRSib1ingNum(CSTree&T){inti=0;while(T->nextsibling){i++；T=T->nextsibling;)returni;)6.62解：//树的深度intDepth(CSTree&T)(intdl,d2;if(T){dl=l+Depth(T->firstchiId);d2=Depth(T->nextsibling);returndl>d2?dl:d2;)elsereturn0; 137}6.63解：intGetDepth_CTree(CTreeA)〃求孩子链表表示的树A的深度(returnSubDepth(A.r);}//GetDepthCTreeintSubDepth(intT)〃求子树T的深度(if(!A.nodes[T].firstchild)return1;for(sd=l,p=A.nodes[T].firstchild;p;p=p->next)if((d=SubDepth(p->chiId))>sd)sd=d;returnsd+1;}//SubDepth7.64解:intGetDepth_PTree(PTreeT)〃求双亲表表示的树T的深度{maxdep=0;for(i=0;i 138(rroot=Bui1d_Sub(Pre_End-righ11en+1,Pre_End,In_End-rightlen+l,In_End);sroot->rchild=rroot;}〃建右子树，注意参数表的计算returnsroot;〃返回子树根}//Build_Submain()Build_Sub(l,n,1,n);〃初始调用参数,n为树结点总数)分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.6.66解:typedefstruct{CSNode*ptr;CSNode*lastchild;}NodeMsg;〃结点的指针和其最后一个孩子的指针StatusBui1d_CSTree_PTree(PTreeT)〃由树T的双亲表构造其孩子兄弟链表(NodeMsgTree[MAXSIZE];for(i=0;i 139}Nodeinfo;〃结点数据，结点指针和最后一个孩子的指针StatusCreateCSTreeDuplet(CSTree&T)〃输入二元组建立树的孩子兄弟链表(NodeinfoTreed;n=l;k=0;if(getchar()!=，9)returnERROR：//未按格式输入if((c=getchar())==*T=NULL;〃空树Tree[0].ptr=(CSNode*)malloc(sizeof(CSNode));Tree[0].data=c;Tree[0].ptr->data=c;while((p=getchar())!=,&&(c=getchar())!='"){Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode));Tree[nJ.data=c;Tree[n].ptr->data=c;for(k=0;Tree[k].data!=p;k++);〃查找当前边的双亲结点if(Tree[k].data!=p)returnERROR;//未找到:未按层序输入r=Tree[k].ptr;if(!r->firstchild)r->firstchild=Tree[n].ptr;elseTree[k].lastchild->nextsib=Tree[n].ptr;Tree[k].lastchild=Tree[n].ptr;〃这一段含义同上一题n++;}//whilereturnOK;}//CreateCSTreeDuplet6.68解：StatusCreateCSTree_Degree(charnode[],intdegree[])〃由结点的层序序列和各结点的度构造树的孩子兄弟链表(CSNode*ptr[MAXSIZE];〃树结点指针的辅助存储ptr[0]=(CSNode*)malloc(sizeof(CSNode));i=0;k=l;〃i为当前结点序号,k为当前孩子的序号while(node[i])(ptr[i]->data=node[i];d=degree[i];if(d)(ptr[k]=(CSNode*)malloc(sizeof(CSNode));//k为当前孩子的序号ptr[i]->firstchild=ptr[k];〃建立i与第一个孩子k之间的联系for(j=2;j<=d;j++)(ptr[k]=(CSNode*)malloc(sizeof(CSNode));ptr[k-l]->nextsib=ptr[k];〃当结点的度大于1时，为其孩子建立兄弟链表k++;}//forptr[k-l]->nextsib=NULL;}//if 140i++；}//while}//CreateCSTree_Degree6.69解：voidPrint.BiTree(BiTreeT,inti)〃按树状打印输出二叉树的元素，i表示结点所在层次，初次调用时i=0{if(T->rchild)Print_BiTree(T->rchild,i+1);for(j=l;j<=i;j++)printfC")；〃打印i个空格以表示出层次printf("%c 141",T->data);//打印T元素,换行if(T->lchild)Print_BiTree(T->rchiId,i+1);}//Print_BiTree分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求，顺序为先右后左.6.70解：StatusCreateBiTreeGList(BiTree&T)〃由广义表形式的输入建立二叉链表c=getchar();if(c==tf)T=NULL;〃空子树else(T二(CSNode*)maHoc(sizeof(CSNode));T->data=c;if(getcharO!=，C)returnERROR;if(ICreateBiTreeGList(pl))returnERROR;T->lchild=pl;if(getchar0!=，,*)returnERROR;if(!CreateBiTree_GList(pr))returnERROR;T->rchild=pr;if(getcharO!-)*)returnERROR;〃这些语句是为了保证输入符合A(B,C)的格式}returnOK;}//CreateBiTreeGList6.71解：voidPrintCSTree(CSTreeT,inti)〃按凹入表形式打印输出树的元素，i表示结点所在层次,初次调用时i=0(for(j=l;j<=i;j++)printfC");〃留出i个空格以表现出层次printf("枇 142”,T->data);〃打印元素,换行for(p=T->firstchild;p;p=p->nextsib) 143Print_CSTree(p,i+1);〃打印子树}//Print_CSTree6.72解：voidPrintCTree(inte,inti)〃按凹入表形式打印输出树的元素，i表示结点所在层次(for(j=l;j<=i;j++)printfC")；〃留出i个空格以表现出层次printf(*%c 144*,T.nodes[e].data);〃打印元素，换行for(p=T.nodes[e].firstchiId;p;p=p->next)Print_CSTree(p->chiId,i+1);〃打印子树}//PrintCSTreemain()(PrintCTree(T.r,0);〃初次调用时i=0}//main6.73解:charc;〃全局变量,指示当前字符StatusCreateCSTree_GList(CSTree&T)〃由广义表形式的输入建立孩广兄弟链表(c=getchar();T=(CSNode*)malloc(sizeof(CSNode));T->data=c;if((c=getchar())==，C)〃非叶结点(if(!CreateCSTreeGList(fc))returnERROR;〃建第一个孩子T->firstchild=fc;for(p=fc;c==，,,;p->nextsib=nc,p=nc)〃建兄弟链if(!CreateCSTree_GList(nc))returnERROR;p->nextsib=NULL;if((c=getchar())!=)*)returnERROR;〃括号不配对}elseT->firtchild=NULL;〃叶子结点returnOK;}//CreateBiTree_GList分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断.6.74解: 145voidPrintGlistCSTree(CSTreeT)〃按广义表形式输出孩子兄弟链表表示的树(printfT->data);if(T->firstchild)〃非叶结点(printf("(");for(p=T->firstchiId;p;p=p->nextsib)(PrintGlist_CSTree(p);if(p->nextsib)printff,");〃最后一个孩子后面不需要加逗号)printf，)”);}//if}//PrintGlist_CSTree6.75解：charc;intpos=0;〃pos是全局变量,指示已经分配到了哪个结点StatusCreateCTreeGList(CTree&T,int&i)〃由广义表形式的输入建立孩子链表(c=getchar();T.nodes[pos].data=c;i=pos++;〃i是局部变量,指示当前正在处理的子树根if((c=getchar())==*(*)〃非叶结点(CreateCTree_GList();p=(CTBox*)malloc(sizeof(CTBox));T.nodesti].firstchild=p;p->child=pos;〃建立孩子链的头forCic=/;p=p->next)〃建立孩子链(CreateCTree_GList(T,j);〃用j返回分配得到的子树根位置p->child=j;p->next=(CTBox*)malloc(sizeof(CTBox));)p->next=NULL;if((c二getchar())!=')')returnERROR;//括号不配对}//ifelseT.nodes[i].firtchild=NULL;//叶子结点returnOK;}//CreateBiTreeGList分析:该算法中,pos变量起着“分配”结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n. 1466.76解：voidPrintGList_CTree(CTreeT,inti)〃按广义表形式输出孩子链表表示的树(printfT.nodes[i].data);if(T.nodes[i].firstchild)〃非叶结点(printf(〃(〃)；for(p=T->firstchiId;p;p=p->nextsib)(PrintGlistCSTree(T,p->chiId);if(p->nextsib)printfC,");〃最后一个孩子后面不需要加逗号)printf(")”);}//if}//PrintGlist_CTree 1477.1解：(1)ID(1)=30D(l)=0ID(2)=2OD(2)=2TD(3)=1OD(3)=21D(4)=1OD(4)=3ID(5)=2OD(5)=1ID(6)=2OD(6)=3(2)000000100100010001001011100000110010⑶(5)有三个连通分量1、5、23466.2解：k=l,说明了各结点之间的相互连通关系：k=2说明了结点之间按路径长度为2的相互连通关系；。6.3解：邻接表：邻接多重表: 148深度优先搜索的顺序为156432广度优先搜索的顺序为156324,15161312246.14解：StatusCreateAG(ALGraph&G)(intn,e,k,i,j;cout<〈”请输入顶点数：”；cin»n;cout«"请输入边数：”；cin»e;G.vernum=n;G.arcnum=e;//建立顶点数组for(k=O;k 149while(q->nextarc)q=q->nextarc;//指针定位于邻接表的尾结点q->nextarc=p;})returnOK;}intLocateVex(ALGraph&G,VertexTypev)(inti=0;while(G.vertices[i].data!=v&&i 150G.arcs[m][i]=G.arcs[n][i]；〃将边的关系随之交换)G.arcs[m][m].adj=O;G.vexnum一;returnOK;}//Delete_Vex分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂，而伴随着大量元素的移动,时间复杂度也会大大增加.StatusDelete_Arc(MGraph&G,charv,charw)〃在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum—;}returnOK;}//Delete_Arc7.16〃为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.StatusInsert_Arc(ALGraph&G,charv,charw)〃在邻接表表示的图G上插入边(v,w)(if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)if(q->adjvex==j)returnERROR;〃边已经存在q->nextarc=p;}G.arcnum++;returnOK;}//InsertArc 151//为节省篇幅,本题只给出较为复杂的Delete.Vex算法.其余算法请自行写出.StatusDelete_Vex(OLGraph&G,charv)〃在十字链表表示的图G上删除顶点v(if((m=LocateVex(G,v))<0)returnERROR;n=G.vexnum;for(i=0;i 152}//forfor(i=m;i 153StatusBuild_AdjMulist(AMLGraph&G)〃输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表{InitAMLGraph(G);scanf&v);if(v<0)returnERROR;〃顶点数不能为负G.vexnum=v;scanf(%d*,&a);if(a<0)returnERROR;〃边数不能为负G.arcnum=a;for(m=0;m 154}//Build_AdjList7.20intPass_MGraph(MGraphG)〃判断一个邻接矩阵存储的有向图是不是可传递的，是则返回1,否则返回0(for(x=0;x 155intvisited[MAXSIZE];〃指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)〃深度优先判断有向图G中顶点i到顶点j是否有路径，是则返回1,否则返回0(if(i==j)return1;〃i就是jelse(visited[i]=l;for(p=G.vertices[ij.firstarc;p;p=p->nextarc)(k=p->adjvex;if(!visited[k]&&exist_path(k,j))returnl;〃i下游的顶点到j有路径}//for}//else}//existpathDFS7.23intexist_path_BFS(ALGraphG,inti,intj)〃广度优先判断有向图G中顶点i到顶点j是否有路径，是则返回1,否则返回0(intvisited[MAXSIZE];InitQueue(Q);EnQueue(Q,i);whiledQueueEmpty(Q))(DeQueue(Q,u);visited[u]=l;for(p=G.vertices[i].firstarc;p;p=p->nextarc)(k=p->adjvex;if(k==j)return1;if(!visited[k])EnQueue(Q,k);}//for}//whilereturn0;}//existpathBFS 156voidSTraverseNonrecursive(GraphG)〃非递归遍历强连通图G(intvisited[MAXSIZE];InitStack(S);Push(S,GetVex(S,1));〃将第一个顶点入栈visit(1);visited=l;while(!StackEmpty(S))(while(Gettop(S,i)&&i)(j=FirstAdjVex(G,i);if(j&&!visited[j])(visit(j);visited[j]=l;Push(S,j);〃向左走到尽头}}//whileif(IStackEmpty(S))(Pop(S,j);Gettop(S,i);k=NextAdjVex(G,i,j);〃向右走一步if(k&&!visited[k])(visit(k);visited[k]=l;Push(S,k);))//if}//while}//Straverse_Nonrecursive分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第•个结点出发一定能够访问到所有结点.7.25见书后解答.7.26StatusTopoNo(ALGraphG)〃按照题目要求顺序重排有向图中的顶点intnew[MAXS!ZE],indegree[MAXSIZE];〃储存结点的新序号n=G.vexnum;FindlnDegree(G,indegree);InitStack(S); 157for(i=l;i 158*,i,new[i])returnOK;}//TopoNo分析:只要按拓扑逆序对顶点编号，就可以使邻接矩阵成为下三角矩阵.7.27intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)〃判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径(if(i==j&&k==O)return1;〃找到了一条路径，且长度符合要求elseif(k>0){visited[i]=l;for(p=G.vertices[i].firstarc;p;p=p->nextarc)(l=p->adjvex;if(!visited[l])if(exist_path_len(G,1,j,k-l))return1;〃剩余路径长度减一}//forvisited[i]=O;〃本题允许曾经被访问过的结点出现在另一条路径中}//elsereturn0;〃没找到}//exist_path_len7.28intpath[MAXSIZE],visited[MAXSIZE];〃暂存遍历过程中的路径intFind_A11_Path(ALGraphG,intu,intv,intk)〃求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度(path[k]=u;〃加入当前路径中visited[u]=l;if(u==v)〃找到了一条简单路径(printf("Foundonepath! 159*);for(i=0;path[i];i++)printfpath[i]);〃打印输出 160}elsefor(p=G.vertices[u].firstarc;p;p=p->nextarc)(l=p->adjvex;if(!visited[l])FindAll_Path(G,1,v,k+1);〃继续寻找}visited[u]=O;path[k]=0;〃回溯}//Find_All_Pathmain()Find_All_Path(G,u,v,0);〃在主函数中初次调用，k值应为0}//main7.29intGetPathNum_Len(ALGraphG,inti,intj,intlen)〃求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数(if(i==j&&len==0)return1;〃找到了一条路径，且长度符合要求elseif(len>0)(sum=0;〃sum表示通过本结点的路径数visited[i]=l;for(p=G.vertices[i].firstarc;p;p=p->nextarc)(l=p->adjvex;if(!visited[l])sum+=GetPathNumLen(G,1,j,lenT)〃剩余路径长度减一}//forvisited[i]=0;〃本题允许曾经被访问过的结点出现在另一条路径中}//elsereturnsum;}//GetPathNum_Len7.30intvisited[MAXSIZE];intpath[MAXSIZE];〃暂存当前路径intcycles[MAXSIZE][MAXSIZE];〃储存发现的回路所包含的结点intthiscycle[MAXSIZE];〃储存当前发现的一个回路intcycount=0;〃已发现的回路个数 161voidGetAlICycle(ALGraphG)〃求有向图中所有的简单回路{for(v=0;v 162分析:这个算法的思想是,在遍历中暂存当前路径，当遇到一个结点已经在路径之中时就表明存在一条回路;扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如，142857)存入thiscycle中；由于这种算法中,一条回路会被发现好儿次,所以必须先判断该回路是否已经在cycles中被记录过，如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序，比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如，thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同，因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.7.31intvisited[MAXSIZE];intfinished[MAXSIZE];intcount;〃count在第一次深度优先遍历中用于指示finished数组的填充位置voidGet_SGraph(OLGraphG)〃求十字链表结构储存的有向图G的强连通分量(count=0;for(v=0;v 163");〃不同的强连通分量在不同的行输出DFS2(G,v);)}//for}//GetSGraphvoidDFS1(OLGraphG,intv)〃第-•次深度优先遍历的算法,■visited[v]=l;for(p=G.xlist[v].firstout;p;p=p->tlink)(w=p->headvex;if(!visited[w])DFS1(G,w);}//forfinished[++count]=v;〃在第一次遍历中建立finished数组J//DFS1voidDFS2(OLGraphG,intv)〃第二次逆向的深度优先遍历的算法(visited[v]=l;printfv);〃在第二次遍历中输出结点序号for(p=G.xlist[v].firstin;p;p=p->hlink)(w=p->tailvex;if(!visited[w])DFS2(G,w); 164}//for}//DFS2分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为0(n+e).7.32voidForestPrim(ALGraphG,intk,CSTree&T)〃从顶点k出发，构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储(for(j=0;j 165p->firstchild=q;〃作为双亲的第一个孩子else〃双亲已经有了孩子{for(r=p->firstchiId;r->nextsib;r=r->nextsib);r->nextsib二q;〃作为双亲最后一个孩子的兄弟}}//Addto_Forestmain()(T=(CSTNode*)malloc(sizeof(CSTNode));〃建立树根T->data=l;Forest_Prim(G,1,T);}//main分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为0(r/2).7.33typedefstruct{intvex;〃结点序号intecno;〃结点所属的连通分量号}Vexlnfo;Vexlnfovexs[MAXSIZE];〃记录结点所属连通分量号的数组voidInit_VexInfo(Vexlnfo&vexs[],intvexnum)〃初始化(for(i=0;Kvexnum;i++)vexs[i]={i,i};〃初始状态:每一个结点都属于不同的连通分量}//Init_VexInfointis_ec(Vexlnfovexs[],inti,intj)〃判断顶点i和顶点j是否属于同一个连通分量(if(vexs[i].ecno==vexs[j].ecno)return1;elsereturn0;}//is_ecvoidmerge_ec(Vexlnfo&vexs[],inteel,intec2)〃合并连通分量eel和ec2for(i=0;vexs[i].vex;i++)if(vexs[i].ecno==ec2)vexs[i].ecno==ec1;}//merge_ec 166voidMinSpanTreeKruscal(GraphG,EdgeSetType&EdgeSet,CSTree&T)〃求图的最小生成树的克鲁斯卡尔算法(Init_VexInfo(vexs,G.vexnum);ecnum=G.vexnum;〃连通分量个数while(ecnum>l){GetMinEdge(EdgeSet,u,v);〃选出最短边if(!is_ec(vexs,u,v))//u和v属于不同连通分量(Addto_CSTree(T,u,v);〃加入到生成树中merge_ec(vexs,vexs[u].ecno,vexs[v].ecno);//合并连通分量eenum一；DelMinEdge(EdgeSet,u,v);//从边集中删除}//while}//MinSpanTree_KruscalvoidAddto_CSTree(CSTree&T,inti,intj)〃把边(i,j)添加到孩子兄弟链表表示的树T中(p=Locate(T,i);〃找到结点i对应的指针p,过程略q=(CSTNode*)malloc(sizeof(CSTNode));q->data=j;if(!p->firstchild)〃双亲还没有孩子p->firstchild=q;〃作为双亲的第一个孩子else〃双亲已经有了孩子(for(r=p->firstchild;r->nextsib;r=r->nextsib);r->nextsib=q;〃作为双亲最后一个孩子的兄弟}}//Addto_CSTree分析:本算法使用一维结构体变量数组来表示等价类,每个连通分量所包含的所有结点属于一个等价类.在这个结构上实现了初始化,判断元素是否等价(两个结点是否属于同一个连通分量)，合并等价类(连通分量)的操作.7.34StatusTopoSeq(ALGraphG,intnew[])〃按照题目要求给有向无环图的结点重新编号，并存入数组new中(intindegree[MAXSIZE];〃本算法就是拓扑排序Findindegree(G,indegree); 167Initstack(S);for(i=0;i 168”,v);}//for}//Get_Root,这个算法要求图中不能有环,否则会发生误判voidDFS(ALGraphG,intv)visited[v]=l;for(p=G.vertices[v].firstarc;p;p=p->nextarc){w=p->adjvex;if(!visited[w])DFS(G,w);)}//DFS7.36voidFill_MPL(ALGraph&G)〃为有向无环图G添加MPL域(Findindegree(G,indegree); 169for(i=0;i 170path[len]=i;if(len>maxlen&&!G.vertices[i].firstarc)〃新的最长路径(for(j=0;j<=len;j++)mlp[j]=path[j];〃保存下来maxlen=len;}else{for(p=G.vertices[i].firstarc;p;p=p->nextarc){j=p->adjvex;if(!visited[j])DFS(G,j,len+1);)}//elsepath[i]=0;visited[i]=O;}//DFS7.38voidNiBoLan_DAG(ALGraphG)〃输出有向无环图形式表示的表达式的逆波兰式Findindegree(G,indegree);for(i=0;i 171}//PrintNiBoLan_Bitree7.40intEvaluate_DAG(ALGraphG)〃给有向无环图表示的表达式求值(Findindegree(G,indegree);for(i=0;i 172if(!indegree[i])ve[i]=0;for(p=G.vertices[i].firstarc;p;p=p->nextarc)(dut=*p->info;if(ve[i]+dut>ve[p->adjvex])ve[p->adjvex]=ve[i]+dut;DFS1(G,p->adjvex);)J//DFS1voidDFS2(ALGraphG,inti)(if(!G.vertices[i].firstarc)vl[i]=ve[i];else(for(p=G.vertices[i].firstarc;p;p=p->nextarc)(DFS2(G,p->adjvex);dut=*p->info;if(vl[p->adjvex]-dut 173}//for}//ALGraph_DIJ分析:本算法对迪杰斯特拉算法中直接取任意边长度的语句作了修改.由于在原算法中，每次循环都是对尾相同的边进行处理，所以可以用遍历邻接表中的一条链来代替.第八章动态存储管理7.11typedefstruct{char*start;intsize;}fmblock;//空闲块类型char*Malloc_Fdlf(intn)〃遵循最后分配者最先释放规则的内存分配算法{while(Gettop(S,b)&&b.size 174(Pop(S,b);Push(T,b);)〃在按地址排序的栈中找到合适的插入位置if(Gettop(T,b)&&(b.start+b.size==addr))〃可以与上邻块合并{Pop(T,b);addr=b.start;n+=b.size;)if(Gettop(S,b)&&(addr+n==b.start))〃可以与下邻块合并(Pop(S,b);n+=b.size;)Push(S,{addr,n});//插入到空闲块栈中while(!StackEmpty(T))(Pop(T,b);Push(S,b);)〃恢复原来次序}//Free_Fdlf8.13voidFreeBT(Space&pav,Spacep)〃在边界标识法的动态存储管理系统中回收空闲块p{n=p->size;f=p+n-l;〃f指向空闲块底部if((p-1)->tag&&(f+1)->tag)〃回收块上下邻块均为占用块(p->tag=0;f->tag=0;f->uplink=p;if(!pav)(p->llink=p;p->rlink=p;)else(q=pav->11ink;p->l1ink=q;p_>rlink=pav;q->rlink=p;pav->Hink=p;)pav=p;}//ifelseif(!(p-l)->tag&&(f+l)->tag)〃上邻块为空闲块( 175q=(p-l)->uplink;q->size+=n;f->uplink=q;f->tag=O;)elseif((p-l)->tag&&!(f+l)->tag)〃下邻块为空闲块(q=f+l;s=q->llink;t=q->rlink;p->llink=s;p->rlink=t;s->rlink=p;t->llink=p;p->size+=q->size;(q+q->size-l)->uplink=p;p->tag=O;}else〃上下邻块均为空闲块(s=(p-l)->uplink;t=f+l;s->size+=n+t->size;t->Hink->rlink=t->rlink;t->r1ink->l1ink=t->llink;(t+t->size-l)->uplink=s;)}//Free_BT,该算法在课本里有详细的描述.8.14voidFree_BS(freelist&avail,char♦addr,intn)〃伙伴系统的空闲块回收算法buddy=addr%(2*n)?(addr-n):(addr+n);〃求回收块的伙伴地址addr->tag=O;addr->kval=n;for(i=O;avail[i].nodesize 176new=addr>p?p:addr;〃合并后的新块首址FreeBS(avail,new,2*n);〃递归地回收新块)//ifelse〃伙伴为占用块，此时插入空闲块链头部(q=p->rlink;p->rlink=addr;addr->1link=p;q->Hink=addr;addr->rlink=q;}}//else}//Free_BS8.15FBList*MakeList(char*highbound,char*lowbound)〃把堆结构存储的的所有空闲块链接成可利用空间表,并返回表头指针(p=lowbound;while(p->tag&&p 177q->next=p;q=P；}//ifp->next=NULL;returnhead;〃返回头指针}//MakeList8.16voidMem_Contract(Heap&H)〃对堆H执行存储紧缩(q=MemStart;j=0;for(i=0;i 178a1=lxl+lx2+2x3+4x4解:9.7a2=1x2+1x3+2x4+4x5an=lxn+lx(n+l)+2x(n+2)+4x(n+3) 1798NSN=^ann=lASL="+?29.9解：(1)=^[8N+17]=8N(N-1)+17Nn=l28ASL=^[1x1+2x24-3x3+3x4+2x5+1x6]=3.59.25intSearch_Sq(SSTableST,intkey)〃在有序表上顺序查找的算法,监视哨设在高下标端(ST.elem[ST.length+1].key=key;for(i=l;ST.elem[i].key>key;i++);if(i>ST.lengthlIST.elem[i].key 180mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearchBinRecursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);)}//Search_Bin_Recursive9.27intLocate_Bin(SSTableST,intkey)〃折半查找，返回小于或等于待查元素的最后一个结点号(int*r;r=ST.elem;if(key 181intSearchIdxSeq(IdxSqListL,intkey)〃分块查找,用折半查找法确定记录所在块,块内采用顺序查找法(if(key>L.idx[L.blknum].maxkey)returnERROR;〃超过最大元素1ow=1;high=L.blknum;found=0;while(low<=high&&!found)〃折半查找记录所在块号mid(mid=(low+high)/2;if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)found=l;elseif(key>L.idx[mid],maxkey)low=mid+l;elsehigh=mid-1;}i=L.idx[mid],firstloc;〃块的下界j=i+blksize-l;〃块的上界temp=L.elem[i-l];〃保存相邻元素L.elem[iT]=key;〃设置监视哨for(k=j;L.elem[k]!=key;k—);〃顺序查找L.elem[i-l]=temp;〃恢复元素if(k 182p=L.sp;if(p->data>key)(while(p->data>key)p=p->pre;L.sp=p;}elseif(p->data 183*,last);if(last<=x&&T->data>x)〃找到了大于x的最小元素printf(/xb=%d 184*,T->data);last=T->data;if(T->rchild)MaxLT_MinGT(T->rchiId,x);}//MaxLT_MinGT9.33 185voidPrint_NLT(BiTreeT,intx)〃从大到小输出二叉排序树T中所有不小于x的元素[if(T->rchild)Print_NLT(T->rchiId,x);if(»data 186”,T->data);if(T->lchild)Print_NLT(T->lchild,x);〃先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)〃删除二叉排序树T中所有不小于x元素结点，并释放空间(if(T->rchiId)DeleteNLT(T->rchi1d,x);if(T->data 187*,p->data);〃输出符合条件的元素if(p->rtag)p=p->rtag;else(p=p->rchild;while(!p->ltag)p=p->lchild;)〃转到中序后继}//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)〃在后继线索二叉排序树T中插入元素x(if(T->data 188(p=T->rchild;q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->rchild=q;T->rtag=0;q->rtag=1;q->rchi1d=p;〃修改原线索)elseBSTree」nsert_Kcy(T->rchild,x);//T有右子树时,插入右子树中}//ifelseif(T->data>x)〃插入到左子树中(if(!T->lchild)//T没有左子树时,作为左孩子插入(q二(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->lchild=q;q->rtag=l;q->rchild=T;〃修改自身的线索)elseBSTreelnsertKey(T->lchiId,x);//T有左子树时,插入左子树中}//if}//BSTreeInsertKeyStatusBSTreeDeletekey(BiThrTree&T,intx)〃在后继线索二叉排序树T中删除元素x(BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和sue分别指向ptr的前驱和后继p=T;last=NULL;//last始终指向当前结点p的前一个(前驱)while(!p->ltag)p=p->lchild;〃找到中序起始元素while(p)(if(p->data==x)〃找到了元素x结点(pre=last;ptr=p;)elseif(last&&last->data==x)suc=p;〃找到了x的后继if(p->rtag)p=p->rtag;elseIp=p->rchiId;while(!p->ltag)p=p->lchild;}〃转到中序后继last=p;}//while//借助中序遍历找到元素x及其前驱和后继结点if(!ptr)returnERROR;〃未找到待删结点DeleteBSTree(ptr);//删除x结点if(pre&&pre->rtag) 189pre->rchild=suc;〃修改线索returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)〃课本上给出的删除二义排序树的子树T的算法，按照线索二叉树的结构作了一些改动(q=T；if(!T->ltag&&T->rtag)〃结点无右子树,此时只需重接其左子树T=T->lchild;elseif(T->ltag&&!T->rtag)〃结点无左子树，此时只需重接其右子树T=T->rchild;elseif(!T->ltag&&!T->rtag)〃结点既有左子树又有右子树{p=T;r=T->lchild;while(!r->rtag)(s=r;r=r->rchild;〃找到结点的前驱r和r的双亲sT->data=r->data;〃用r代替T结点if(s!=T)s->rchi1d=r->lchild;elses->lchild=r->lchild;〃重接r的左子树到其双亲结点上q=r;}//elsefree(q);〃删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了,如果试图在删除x结点的同时修改线索，则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)〃把二叉排序树S合并到T中(if(S->lchild)BSTree_Merge(T,S->lchild);if(S->rchild)BSTree_Merge(T,S->rchild);〃合并子树Insert_Key(T,S);〃插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)〃把树结点S插入到T的合适位置上(if(S->data>T->data)(if(!T->rchild)T->rchild=S; 190elseInsert_Node(T->rchild,S);)elseif(S->data 191intIsize;〃lsize域表示该结点的左子树的结点总数加1BlcNode*lchild,*rchild;}BlcNode,*BlcTree;〃含Isize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)〃在含Isize域的平衡二叉排序树T中确定第k小的结点指针(if(!T)returnNULL;〃k小于1或大于树结点总数if(T->lsize==k)returnT;〃就是这个结点elseif(T->lsize>k)returnLocate_BlcTree(T->lchild,k);〃在左子树中寻找elsereturnLocate_BlcTree(T->rchild,k-T->lsize);〃在右子树中寻找，注意要修改k的值}//LocateBlcTree9.41 192typedefstruct{enum{LEAF,BRANCH}tag;〃结点类型标识intkeynum;BPLinkparent;〃双亲指针intkey[MAXCHILD];//关键字union{BPLinkchild[MAXCHILD];〃非叶结点的孩子指针struct{rectype*info[MAXCHILD];〃叶子结点的信息指针BPNode*next;〃指向下一个叶子结点的链接}leaf;}}BPNode,*BPLink,*BPTrce;〃B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)〃B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos(P-T;while(p.tag==BRANCH)〃沿分支向下查找{for(i=0;i 193else〃如果最后落到叶子结点(有同义词)：(r=(TrieNode*)ma11oc(sizeof(TrieNode));〃建立新的分支结点last->bh.ptr[ord(key[i-l])]=r;〃用新分支结点取代老叶子结点和上一层的联系r->kind=BRANCH;r->bh.num=2;r->bh.ptr[ord(key[i])]=q;r->bh.ptr[ord(p->lf.k[i])]=p;〃新分支结点与新老两个叶子结点相连}}//TrieTreeInsertKey分析：当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点，再把同义词和新关键字的叶子结点连到新分支结点的下一层.9.43StatusTrieTreeDeleteKey(TrieTree&T,StringTypekey)〃在Trie树T中删除字符串key(P=T;i=l;while(p&&p->kind==BRANCH&&i<=key[O])〃查找待删除元素{last=p;p=p->bh.ptr[ord(key[i])];i++；}if(p&&p->kind==LEAF&&p->lf.k=key)〃找到了待删除元素(last->bh.ptrford(key[i-l])]=NULL;free(p);returnOK;)elsereturnERROR;〃没找到待删除元素}//TrieTreeDeleteKey9.44voidPrint_Hash(HashTableH)〃按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法for(i=l;i<=26;i++)for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])〃线性探测if(H(H.elem[j].key)==i)printf("%s 194",H.elem[j]);}//Print_HashintH(char*s)〃求Hash函数{ 195if(s)returns[0]-96;〃求关键字第一个字母的字母序号(小写)elsereturn0;}//H9.45typedef*LNode[MAXSIZE]CHashTable;〃链地址Hash表类型StatusBuild_Hash(CHashTable&T,intm)〃输入一组关键字，建立Hash表，表长为m,用链地址法处理冲突.(if(m 196k=L.length;for(i=k-l;i;―i)〃从后向前逐个插入排序if(L.r[i].key>Lr[i+l].key)(L.r[k+l].key=L.r[i].key;〃监视哨for(j=i+l;L.r[j].key>L.r[i].key;++j)L.r[jT].key=L.r[j].key;〃前移L.r[j-l].key=Lr[k+l].key;//插入)}//Insert_Sortl10.24voidBiInsert_Sort(SqList&L)〃二路插入排序的算法{intd[MAXSIZE];〃辅助存储x=L.r.key;d=x;first=l;final=l;for(i=2;i<=L.length;i++)(if(L.r[i].key>=x)//插入前部for(j=final;d[j]>L.r[i].key;j-)d[j+l]=d[j]：d[j+l]=L.r[i].key;final++;)else〃插入后部(for(j=first;d[j] 197L.r[l].next=0;〃建初始循环链表for(i=2;i<=L.length;i++)〃逐个插入(p=0;x=L.r[i].key;while(L.r[L.r[p].next].key 198if(a[i]>a[i+l])(a[i]<->a[i+l];change=l;}high—;〃修改上界for(i=high;i>low;i")〃从下向上起泡if(a[i] 199if(a[i]>a[i+l])(a[i]<->a[i+l];change=l;)for(i=0;i 200Pop(S,a);〃从栈中取出一个子序列low=a.low;high=a.high;)}//while}//QSort_NotRecurveintPartition(SQList&L,intlow,inthigh)//一趟划分的算法，与书上相同(L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low 201whi1e(1ow 202s=r;}if(s!=q)〃找到了值比q->data更小的最小结点s->next(p->next=s->next;s->next=q;t=q->next;q->next=p->next->next;p->next->next=t;)〃交换q和s->next两个结点}//for}//LinkedList_Select_Sort10.34voidBuiIdHeap(Heap&H,intn)〃从低下标到高下标逐个插入建堆的算法(for(i=2;i 203if(j 204for(p=L->next,e2=p;p->next;p=e2)(for(i=l,q=p;i<=l&&q->next;i++,q=q->next);el=q;for(i=l;i<=l&&q->next;i++,q=q->next);e2=q;〃求出两个待归并子序列的尾指针if(el!=e2)LinkedList_Merge(L,p,el,e2);〃归并)}//LinkedList_Merge_Sort1voidLinkedListMerge(LinkedList&L,LNode*p,LNode*el,LNode*e2)〃对链表上的子序列进行归并，第一个子序列是从p->next到el,第二个是从el->next到e2(q=p->next;r=el->next;〃q和r为两个子序列的起始位置while(q!=el->next&&r!=e2->next)(if(q->data 205(LNode*end[MAXSIZE];〃设立一个数组来存储各有序子序列的尾指针for(p=L->next->next,i=0;p;p=p->next)〃求各有序子序列的尾指针if(!p->next|p->data>p->next->data)end[i++]=p;while(end[0]->next)〃当不止一个子序列时进行两两归并(j=O;k=0;〃j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置for(p=L->next,e2=p;p->next;p=e2)〃两两归并所有子序列(el=end[j];e2=end[j+l];〃确定两个子序列if(el->next)LinkedList_Merge(L,p,el,e2);〃归并end[k++]=e2;〃用新序列的尾指针取代原来的尾指针j+=2;〃转到后面两个子序列)}//while}//LinkedListMergeSort2voidLinkedList_Merge(LinkedList&L,LNode*p,LNode*el,LNode*c2)〃对链表上的子序列进行归并，第一个子序列是从p->next到el,第二个是从el->next到e2{q=p->next;r=el->next;while(q!=el->next&&r!=e2->next)if(q->data 206r=r->next;}}//LinkedListMerge,与上一题完全相同10.39voidSL_Merge(inta[],int11,int12)〃把长度分别为11,12且1r2<(11+12)的两个有序子序列归并为有序序列(startl=0;start2=ll;〃分别表示序列1和序列2的剩余未归并部分的起始位置for(i=0;i 207if(len%i==O&&k%i==O)p=i;〃求len和k的最大公约数pfor(i=0;i〈p;i++)〃对p个循环链分别进行右移(j=start+i;l=start+(i+k)%len;temp=a[j];while(1!=start+i){a[j]=temp;temp=a[l];a[l]=a[j];j=l;l=start+(j-start+k)%len;〃依次向右移)a[start+i]=temp;}//for}//RSh10.40书后给出的解题思路在表述上存在问题,无法理解.比如说,“把第一个序列划分为两个子序列，使其中的第一个子序列含有si个记泵,0<=sl〈s,第二个子序列有s个记录.”可是题目中并没有说明,第一个序列的长度<2s.请会做的朋友提供解法.10.41voidHash_Sort(inta[])〃对1000个关键字为四位整数的记录进行排序(intb[10000];for(i=0;i<1000;i++)〃直接按关键字散列{for(j=a[i];b[j]：j=(j+l)%10000);b[j]=a[i];)for(i=0,j=0;i<1000;j++)〃将散列收回a中if(b[j])(for(x=b[j],k=j：b[k];k=(k+l)%10000)if(b[k]==x)(a[i++]=x;b[k]=0：) 208}//if}//HashSorttypedefstruct{intgt;〃大于该记录的个数intIt;〃小于该记录的个数}place;〃整个序列中比某个关键字大或小的记录个数intGet_Mid(inta[],intn)〃求一个序列的中值记录的位置{placeb[MAXSIZE];for(i=0;i 209}}//Count_SortvoidEnumSort(inta[],intn)〃对关键字只能取v到w之间任意整数的序列进行排序(intnumber[w+1],pos[w+1];for(i=0;i 210intpos;}Shadow;〃影子序列的记录类型voidShadowSort(Rectypeb[],Rectype&a[],intn)〃对元素很大的记录序列b进行排序,结果放入a中，不移动元素Shadowd[MAXSIZE];for(i=0;i
此文档下载收益归作者所有
