数据结构习题集 (严蔚敏著) 课后答案(完整版).pdf 79页

456.19 KB
2022-04-22 11:52:24 发布

数据结构习题集 (严蔚敏著) 课后答案(完整版).pdf

关闭预览

79页
当前文档由用户上传发布，收益归属用户

下载提示
文本预览

1、本文档共5页，可阅读全部内容。
2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
文档侵权举报电话：19940600175。

'课后答案网www.khdaw.com1.17说明:Statusfib(intk,intm,int&f)//求k阶斐1.本文是对严蔚敏《数据结构(c语言波那契序列的第m项的值f版)习题集》一书中所有算法设计题目{的解决方案,主要作者为kaoyan.com计inttempd;算机版版主一具.以下网友:siice,龙抬if(k<2||m<0)returnERROR;头,iamkent,zames,birdthinking等为答if(my;//<->为表示交换的双intscore;目运算符,以下同}resulttype;if(yz;if(xy;//冒泡排序typedefstruct{printf("%d%d%d",x,y,z);intmalescore;}//print_descendingintfemalescore; 课后答案网www.khdaw.cominttotalscore;Statusalgo119(inta[ARRSIZE])//求}scoretype;i!*2^i序列的值且不超过maxint{voidsummary(resulttyperesult[])//求各last=1;校的男女总分和团体总分,假设结果已for(i=1;i<=ARRSIZE;i++)经储存在result[]数组中{{a[i-1]=last*2*i;scoretypescore;if((a[i-1]/last)!=(2*i))reurni=0;OVERFLOW;while(result[i].sport!=NULL)last=a[i-1];{returnOK;switch(result[i].schoolname)}{}//algo119case"A":分析:当某一项的结果超过了maxint时,score[0].totalscore+=result[i].scor它除以前面一项的商会发生异常.e;if(result[i].gender==0)1.20score[0].malescore+=result[i].score;elsevoidpolyvalue()score[0].femalescore+=result[i].score;{break;floatad;case"B":float*p=a;score.totalscore+=result[i].score;printf("Inputnumberofterms:");if(result[i].gender==0)scanf("%d",&n);score.malescore+=result[i].score;printf("Inputthe%dcoefficientsfromelsea0toa%d:n",n,n);score.femalescore+=result[i].score;for(i=0;i<=n;i++)scanf("%f",p++);break;printf("Inputvalueofx:");………………scanf("%f",&x);}p=a;xp=1;sum=0;//xp用于存放x的ii++；次方}for(i=0;i<=n;i++)for(i=0;i<5;i++){{sum+=xp*(*p++);printf("School%d:n",i);xp*=x;printf("Totalscoreof}male:%dn",score[i].malescore);printf("Valueis:%f",sum);printf("Totalscoreof}//polyvaluefemale:%dn",score[i].femalescore);printf("Totalscoreofall:%dnn",score[i].totalscore);第二章线性表}}//summary2.101.19 课后答案网www.khdaw.comStatusDeleteK(SqList&a,inti,intk)//删{除线性表a中第i个元素起的k个元素for(p=l->next;p&&p->data!=x;p=p->n{ext);if(i<1||k<0||i+k-1>a.length)returnreturnp;INFEASIBLE;}//Locatefor(count=1;i+count-1<=a.length-k;count++)//注意循环结束的条件2.14a.elem[i+count-1]=a.elem[i+count+k-1];intLength(LinkListL)//求链表的长度a.length-=k;{returnOK;for(k=0,p=L;p->next;p=p->next,k++);}//DeleteKreturnk;}//Length2.112.15StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中voidListConcat(LinkListha,LinkList{hb,LinkList&hc)//把链表hb接在ha后if(va.length+1>va.listsize)return面形成链表hcERROR;{va.length++;hc=ha;p=ha;for(i=va.length-1;va.elem[i]>x&&i>=0while(p->next)p=p->next;;i--)p->next=hb;va.elem[i+1]=va.elem[i];}//ListConcatva.elem[i+1]=x;2.16returnOK;}//Insert_SqList见书后答案.2.122.17intListComp(SqListA,SqListB)//比较StatusInsert(LinkList&L,inti,intb)//在字符表A和B,并用返回值表示结果,无头结点链表L的第i个元素之前插入值为正,表示A>B;值为负,表示A1)p=p->next; 课后答案网www.khdaw.comq->next=p->next;p->next=q;//插入在StatusDelete_Equal(Linklist&L)//删除第i个元素的位置元素递增排列的链表L中所有值相同}的元素}//Insert{p=L->next;q=p->next;//p,q指向相邻2.18两元素while(p->next)StatusDelete(LinkList&L,inti)//在无{头结点链表L中删除第i个元素if(p->data!=q->data){{if(i==1)L=L->next;//删除第一个元p=p->next;q=p->next;//当相邻两元素素不相等时,p,q都向后推一步else}{elsep=L;{while(--i>1)p=p->next;while(q->data==p->data)p->next=p->next->next;//删除第i个{元素free(q);}q=q->next;}//Delete}p->next=q;p=q;q=p->next;//当相邻2.19元素相等时删除多余元素}//elseStatusDelete_Between(Linklist&L,int}//whilemink,intmaxk)//删除元素递增排列的}//Delete_Equal链表L中值大于mink且小于maxk的所有元素2.21{p=L;voidreverse(SqList&A)//顺序表的就while(p->next->data<=mink)地逆置p=p->next;//p是最后一个不大于mink{的元素for(i=1,j=A.length;inext)//如果还有比mink更大A.elem[i]<->A.elem[j];的元素}//reverse{q=p->next;2.22while(q->datanext;//q是第一个不小于maxk的元素voidLinkList_reverse(Linklist&L)//链p->next=q;表的就地逆置;为简化算法,假设表长}大于2}//Delete_Between{p=L->next;q=p->next;s=q->next;p->ne2.20xt=NULL;while(s->next){ 课后答案网www.khdaw.comq->next=p;p=q;q;//将A的元素插入新表q=s;s=s->next;//把L的元素逐个插}入新表表头else}{q->next=p;s->next=q;L->next=s;pc=pb;q=pb->next;pb->next=pre;pb}//LinkList_reverse=q;//将B的元素插入新表分析:本算法的思想是,逐个地把L的当}前元素q插入新的链表头部,p为新表pre=pc;表头.}C=A;A->next=pc;//构造新表头2.23}//reverse_merge分析:本算法的思想是,按从小到大的voidmerge1(LinkList&A,LinkList顺序依次把A和B的元素插入新表的&B,LinkList&C)//把链表A和B合并头部pc处,最后处理A或B的剩余元为C,A和B的元素间隔排列,且使用原素.存储空间{2.25p=A->next;q=B->next;C=A;while(p&&q)voidSqList_Intersect(SqListA,SqList{B,SqList&C)//求元素递增排列的线性s=p->next;p->next=q;//将B的元素表A和B的元素的交集并存入C中插入{if(s)i=1;j=1;k=0;{while(A.elem[i]&&B.elem[j])t=q->next;q->next=s;//如A非空,将{A的元素插入if(A.elem[i]B.elem[j])j++;p=s;q=t;if(A.elem[i]==B.elem[j])}//while{}//merge1C.elem[++k]=A.elem[i];//当发现了一个在A,B中都存在的元素,2.24i++;j++;//就添加到C中}voidreverse_merge(LinkList}//while&A,LinkList&B,LinkList&C)//把元素}//SqList_Intersect递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间2.26{pa=A->next;pb=B->next;pre=NULL;voidLinkList_Intersect(LinkList//pa和pb分别指向A,B的当前元素A,LinkListB,LinkList&C)//在链表结while(pa||pb)构上重做上题{{if(pa->datadata||!pb)p=A->next;q=B->next;{pc=(LNode*)malloc(sizeof(LNode));pc=pa;q=pa->next;pa->next=pre;pa=while(p&&q) 课后答案网www.khdaw.com{if(p->datadata)p=p->next;if(p->datadata)p=p->next;elseif(p->data>q->data)q=q->next;elseif(p->data>q->data)q=q->next;elseif(p->data!=pc->data)else{{pc=pc->next;s=(LNode*)malloc(sizeof(LNode));pc->data=p->data;s->data=p->data;p=p->next;q=q->next;pc->next=s;pc=s;}p=p->next;q=q->next;}//while}}//LinkList_Intersect_True}//whileC=pc;2.29}//LinkList_IntersectvoidSqList_Intersect_Delete(SqList2.27&A,SqListB,SqListC){voidSqList_Intersect_True(SqListi=0;j=0;k=0;m=0;//i指示A中元素&A,SqListB)//求元素递增排列的线性原来的位置,m为移动后的位置表A和B的元素的交集并存回A中while(iC.elem[k])k++;if(A.elem[i]B.elem[j])j++;{elseif(A.elem[i]!=A.elem[k])same=B.elem[j];//找{到了相同元素sameA.elem[++k]=A.elem[i];//当发现了while(B.elem[j]==same)j++;一个在A,B中都存在的元素while(C.elem[k]==same)k++;i++;j++;//且C中没有,就添加到C//j,k后移到新的元素中}while(inext;q=B->next;pc=A;A.length=m;while(p&&q)}//SqList_Intersect_Delete{ 课后答案网www.khdaw.com分析:先从B和C中找出共有元素,记为while(p->next->next!=s)p=p->next;//same,再在A中从当前位置开始,凡小找到s的前驱的前驱p于same的p->next=s;元素均保留(存到新的位置),等于samereturnOK;的就跳过,到大于same时就再找下一}//Delete_Pre个same.2.322.30StatusDuLNode_Pre(DuLinkList&L)//voidLinkList_Intersect_Delete(LinkList完成双向循环链表结点的pre域&A,LinkListB,LinkListC)//在链表结{构上重做上题for(p=L;!p->next->pre;p=p->next){p->next->pre=p;p=B->next;q=C->next;r=A-next;returnOK;while(p&&q&&r)}//DuLNode_Pre{if(p->datadata)p=p->next;2.33elseif(p->data>q->data)q=q->next;elseStatusLinkList_Divide(LinkList{&L,CiList&A,CiList&B,CiList&C)//u=p->data;//确定待删除元素u把单链表L的元素按类型分为三个循while(r->next->datanext;//环链表.CiList为带头结点的单循环链确定最后一个小于u的元素指针r表类型.if(r->next->data==u){{s=L->next;s=r->next;A=(CiList*)malloc(sizeof(CiLNode));pwhile(s->data==u)=A;{B=(CiList*)malloc(sizeof(CiLNode));qt=s;s=s->next;free(t);//确定第一=B;个大于u的元素指针sC=(CiList*)malloc(sizeof(CiLNode));r}//while=C;//建立头结点r->next=s;//删除r和s之间的元素while(s)}//if{while(p->data=u)p=p->next;if(isalphabet(s->data))while(q->data=u)q=q->next;{}//elsep->next=s;p=s;}//while}}//LinkList_Intersect_Deleteelseif(isdigit(s->data)){2.31q->next=s;q=s;}StatusDelete_Pre(CiLNode*s)//删除单else循环链表中结点s的直接前驱{{r->next=s;r=s;p=s;} 课后答案网www.khdaw.com}//whilepre=p;p=q;p->next=A;q->next=B;r->next=C;//完}//while//在p,q两结点之间插入成循环链表if(!q)returnINFEASIBLE;//i不可以}//LinkList_Divide超过表长p->LRPtr=XorP(XorP(p->LRPtr,q),r);2.34q->LRPtr=XorP(XorP(q->LRPtr,p),r);r->LRPtr=XorP(p,q);//修改指针voidreturnOK;Print_XorLinkedList(XorLinkedListL)//}//Insert_XorLinkedList从左向右输出异或链表的元素值{2.36p=L.left;pre=NULL;while(p)Status{Delete_XorLinkedList(XorlinkedListprintf("%d",p->data);&L,inti)//删除异或链表L的第i个元q=XorP(p->LRPtr,pre);素pre=p;p=q;//任何一个结点的LRPtr{域值与其左结点指针进行异或运算即p=L.left;pre=NULL;得到其右结点指针if(i==1)//删除最左结点的情况}{}//Print_XorLinkedListq=p->LRPtr;q->LRPtr=XorP(q->LRPtr,p);2.35L.left=q;free(p);returnOK;Status}Insert_XorLinkedList(XorLinkedListj=1;q=p->LRPtr;&L,intx,inti)//在异或链表L的第i个while(++jLRPtr,pre);p=L.left;pre=NULL;pre=p;p=q;r=(XorNode*)malloc(sizeof(XorNode)}//while//找到待删结点q);if(!q)returnINFEASIBLE;//i不可以r->data=x;超过表长if(i==1)//当插入点在最左边的情况if(L.right==q)//q为最右结点的情况{{p->LRPtr=XorP(p.LRPtr,r);p->LRPtr=XorP(p->LRPtr,q);r->LRPtr=p;L.right=p;free(q);L.left=r;returnOK;returnOK;}}r=XorP(q->LRPtr,p);//q为中间结点j=1;q=p->LRPtr;//当插入点在中间的的情况,此时p,r分别为其左右结点情况p->LRPtr=XorP(XorP(p->LRPtr,q),r);while(++jLRPtr=XorP(XorP(r->LRPtr,q),p);{//修改指针q=XorP(p->LRPtr,pre);free(q); 课后答案网www.khdaw.comreturnOK;if(p==L)returnNULL;//没找到}//Delete_XorLinkedListp->freq++;q=p->pre;while(q->freq<=p->freq)q=q->pre;//2.37查找插入位置if(q!=p->pre)voidOEReform(DuLinkedList&L)//按{1,3,5,...4,2的顺序重排双向循环链表Lp->pre->next=p->next;p->next->pre=中的所有结点p->pre;{q->next->pre=p;p->next=q->next;p=L.next;q->next=p;p->pre=q;//调整位置while(p->next!=L&&p->next->next!=}L)returnp;{}//Locate_DuListp->next=p->next->next;p=p->next;2.39}//此时p指向最后一个奇数结点if(p->next==L)p->next=L->pre->pre;floatGetValue_SqPoly(SqPolyP,intelsep->next=l->pre;x0)//求升幂顺序存储的稀疏多项式的p=p->next;//此时p指向最后一个偶值数结点{while(p->pre->pre!=L)PolyTerm*q;{xp=1;q=P.data;p->next=p->pre->pre;sum=0;ex=0;p=p->next;while(q->coef)}{p->next=L;//按题目要求调整了nextwhile(exexp)xp*=x0;链的结构,此时pre链仍为原状sum+=q->coef*xp;for(p=L;p->next!=L;p=p->next)q++;p->next->pre=p;}L->pre=p;//调整pre链的结构,同2.32returnsum;方法}//GetValue_SqPoly}//OEReform分析:next链和pre链的调整只能分开2.40进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破voidSubtract_SqPoly(SqPoly坏链表结构,造成结点丢失.P1,SqPolyP2,SqPoly&P3)//求稀疏多项式P1减P2的差式P32.38{PolyTerm*p,*q,*r;DuLNode*Create_SqPoly(P3);//建立空多项式Locate_DuList(DuLinkedList&L,intP3x)//带freq域的双向循环链表上的查找p=P1.data;q=P2.data;r=P3.data;{while(p->coef&&q->coef)p=L.next;{while(p.data!=x&&p!=L)p=p->next;if(p->expexp) 课后答案网www.khdaw.com{{r->coef=p->coef;L->next=p->next;p=p->next;//跳过r->exp=p->exp;常数项p++;r++;}}while(p!=L)elseif(p->expexp){{p->data.coef*=p->data.exp--;//对每一r->coef=-q->coef;项求导r->exp=q->exp;p=p->next;q++;r++;}}}//QiuDao_LinkedPolyelse{2.42if((p->coef-q->coef)!=0)//只有同次项相减不为零时才需要存入P3中voidDivide_LinkedPoly(LinkedPoly{&L,&A,&B)//把循环链表存储的稀疏r->coef=p->coef-q->coef;多项式L拆成只含奇次项的A和只含r->exp=p->exp;r++;偶次项的B}//if{p++;q++;p=L->next;}//elseA=(PolyNode*)malloc(sizeof(PolyNod}//whilee));while(p->coef)//处理P1或P2的剩余B=(PolyNode*)malloc(sizeof(PolyNod项e));{pa=A;pb=B;r->coef=p->coef;while(p!=L)r->exp=p->exp;{p++;r++;if(p->data.exp!=2*(p->data.exp/2))}{while(q->coef)pa->next=p;pa=p;{}r->coef=-q->coef;elser->exp=q->exp;{q++;r++;pb->next=p;pb=p;}}}//Subtract_SqPolyp=p->next;}//while2.41pa->next=A;pb->next=B;}//Divide_LinkedPolyvoidQiuDao_LinkedPoly(LinkedPoly&L)//对有头结点循环链表结构存储的第三章栈与队列稀疏多项式L求导{p=L->next;3.15if(!p->data.exp) 课后答案网www.khdaw.comtypedefstruct{elsereturnERROR;Elemtype*base[2];returnOK;Elemtype*top[2];}//pop}BDStacktype;//双向栈类型3.16StatusInit_Stack(BDStacktype&tws,intvoidTrain_arrange(char*train)//这里用m)//初始化一个大小为m的双向栈tws字符串train表示火车,"H"表示硬席,"S"{表示软席tws.base[0]=(Elemtype*)malloc(sizeof{(Elemtype));p=train;q=train;tws.base[1]=tws.base[0]+m;InitStack(s);tws.top[0]=tws.base[0];while(*p)tws.top[1]=tws.base[1];{returnOK;if(*p=="H")push(s,*p);//把"H"存入栈}//Init_Stack中else*(q++)=*p;//把"S"调到前部Statuspush(BDStacktype&tws,intp++;i,Elemtypex)//x入栈,i=0表示低端}栈,i=1表示高端栈while(!StackEmpty(s)){{if(tws.top[0]>tws.top[1])returnpop(s,c);OVERFLOW;//注意此时的栈满条件*(q++)=c;//把"H"接在后部if(i==0)*tws.top[0]++=x;}elseif(i==1)*tws.top[1]--=x;}//Train_arrangeelsereturnERROR;returnOK;3.17}//pushintIsReverse()//判断输入的字符串中Statuspop(BDStacktype&tws,int"&"前和"&"后部分是否为逆串,是则返i,Elemtype&x)//x出栈,i=0表示低端回1,否则返回0栈,i=1表示高端栈{{InitStack(s);if(i==0)while((e=getchar())!="&"){push(s,e);if(tws.top[0]==tws.base[0])returnwhile((e=getchar())!="@")OVERFLOW;{x=*--tws.top[0];if(StackEmpty(s))return0;}pop(s,c);elseif(i==1)if(e!=c)return0;{}if(tws.top[1]==tws.base[1])returnif(!StackEmpty(s))return0;OVERFLOW;return1;x=*++tws.top[1];}//IsReverse} 课后答案网www.khdaw.com3.18}coordinate;StatusBracket_Test(char*str)//判别表达式中小括号是否匹配voidRepaint_Color(intg[m][n],inti,int{j,intcolor)//把点(i,j)相邻区域的颜色置count=0;换为colorfor(p=str;*p;p++){{old=g[i][j];if(*p=="(")count++;InitQueue(Q);elseif(*p==")")count--;EnQueue(Q,{I,j});if(count<0)returnERROR;while(!QueueEmpty(Q))}{if(count)returnERROR;//注意括号不DeQueue(Q,a);匹配的两种情况x=a.x;y=a.y;returnOK;if(x>1)}//Bracket_Testif(g[x-1][y]==old){3.19g[x-1][y]=color;EnQueue(Q,{x-1,y});//修改左邻StatusAllBrackets_Test(char*str)//判别点的颜色表达式中三种括号是否匹配}{if(y>1)InitStack(s);if(g[x][y-1]==old)for(p=str;*p;p++){{g[x][y-1]=color;if(*p=="("||*p=="["||*p=="{")push(s,*p);EnQueue(Q,{x,y-1});//修改上邻elseif(*p==")"||*p=="]"||*p=="}")点的颜色{}if(StackEmpty(s))returnERROR;if(x=0)s=0;}//F_nonrecursiveelseif(m>0&&n>=0)s=n+g(m-1,2*n);elsereturnERROR;3.26returnOK;}//gfloatSqrt_recursive(floatA,floatp,floate)//求平方根的递归算法3.25{if(abs(p^2-A)<=e)returnp;StatusF_recursive(intn,int&s)//递归算elsereturnsqrt_recurve(A,(p+A/p)/2,e);法}//Sqrt_recurve{if(n<0)returnERROR;floatSqrt_nonrecursive(floatA,floatif(n==0)s=n+1;p,floate)//求平方根的非递归算法else{{while(abs(p^2-A)>=e)F_recurve(n/2,r);p=(p+A/p)/2;s=n*r;returnp;}}//Sqrt_nonrecursivereturnOK;}//F_recursive3.27StatusF_nonrecursive(intn,ints)//非递这一题的所有算法以及栈的变化过程归算法请参见《数据结构(pascal版)》,作者不{再详细写出.if(n<0)returnERROR;3.28if(n==0)s=n+1;elsevoidInitCiQueue(CiQueue&Q)//初始{化循环链表表示的队列QInitStack(s);//s的元素类型为struct{{inta;intb;}Q=(CiLNode*)malloc(sizeof(CiLNodewhile(n!=0)));{Q->next=Q;a=n;b=n/2;}//InitCiQueuepush(s,{a,b});n=b;voidEnCiQueue(CiQueue&Q,intx)//把}//while元素x插入循环链表表示的队列Q,Qs=1;指向队尾元素,Q->next指向头结while(!StackEmpty(s))点,Q->next->next指向队头元素{{pop(s,t);p=(CiLNode*)malloc(sizeof(CiLNode)s*=t.a;);}//whilep->data=x;}p->next=Q->next;//直接把p加在Q的课后答案网www.khdaw.com后面3.30Q->next=p;Q=p;//修改尾指针StatusEnCyQueue(CyQueue&Q,intx)//}带length域的循环队列入队算法{StatusDeCiQueue(CiQueue&Q,intx)//if(Q.length==MAXSIZE)return从循环链表表示的队列Q头部删除元OVERFLOW;素xQ.rear=(Q.rear+1)%MAXSIZE;{Q.base[Q.rear]=x;if(Q==Q->next)returnINFEASIBLE;Q.length++;//队列已空returnOK;p=Q->next->next;}//EnCyQueuex=p->data;Q->next->next=p->next;StatusDeCyQueue(CyQueue&Q,intfree(p);&x)//带length域的循环队列出队算法returnOK;{}//DeCiQueueif(Q.length==0)returnINFEASIBLE;head=(Q.rear-Q.length+1)%MAXSIZE;3.29//详见书后注释x=Q.base[head];StatusEnCyQueue(CyQueue&Q,intx)//Q.length--;带tag域的循环队列入队算法}//DeCyQueue{if(Q.front==Q.rear&&Q.tag==1)//tag3.31域的值为0表示"空",1表示"满"returnOVERFLOW;intPalindrome_Test()//判别输入的字符Q.base[Q.rear]=x;串是否回文序列,是则返回1,否则返回Q.rear=(Q.rear+1)%MAXSIZE;0if(Q.front==Q.rear)Q.tag=1;//队列满{}//EnCyQueueInitStack(S);InitQueue(Q);while((c=getchar()!="@")StatusDeCyQueue(CyQueue&Q,int{&x)//带tag域的循环队列出队算法Push(S,c);EnQueue(Q,c);//同时使用{栈和队列两种结构if(Q.front==Q.rear&&Q.tag==0)return}INFEASIBLE;while(!StackEmpty(S))Q.front=(Q.front+1)%MAXSIZE;{x=Q.base[Q.front];Pop(S,a);DeQueue(Q,b));if(Q.front==Q.rear)Q.tag=1;//队列空if(a!=b)returnERROR;returnOK;}}//DeCyQueuereturnOK;分析:当循环队列容量较小而队列中每}//Palindrome_Test个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.3.32 课后答案网www.khdaw.comvoidGetFib_CyQueue(intk,intn)//求kif(Q.front==Q.rear)return阶斐波那契序列的前n+1项INFEASIBLE;//队列空{x=Q.base[Q.front];InitCyQueue(Q);//其MAXSIZE设置Q.front=(Q.front+1)%MAXSIZE;为kreturnOK;for(i=0;i=avr)//根据x的值决定插入在队厢从头端入队列头还是队尾}{elseQ.base[Q.rear]=x;{Q.rear=(Q.rear+1)%MAXSIZE;printf("A");}//插入在队尾EnDQueue(Q,*r,1);//1表示把H车else厢从尾端入队列{}Q.front=(Q.front-1)%MAXSIZE;}//whileQ.base[Q.front]=x;while(!DQueueEmpty(Q))}//插入在队头{returnOK;printf("D");}//EnDQueueDeDQueue(Q);}//while//从头端出队列的车厢必然StatusDeDQueue(DQueue&Q,int&x)//是先S后H的顺序输出受限的双端队列的出队操作}//Train_Rearrange{ 课后答案网www.khdaw.comintReplace(Stringtype&S,Stringtype第四章串T,StringtypeV);//将串S中所有子串T替换为V,并返回置换次数4.10{for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;ivoidString_Reverse(Stringtype++)//注意i的取值范围s,Stringtype&r)//求s的逆串rif(!StrCompare(SubString(S,i,Strlen({T)),T))//找到了与T匹配的子串StrAssign(r,"");//初始化r为空串{//分别把T的前面和后面部分保存for(i=Strlen(s);i;i--)为head和tail{StrAssign(head,SubString(S,1,i-1));StrAssign(c,SubString(s,i,1));StrAssign(tail,SubString(S,i+Strlen(StrAssign(r,Concat(r,c));//把s的字T),Strlen(S)-i-Strlen(T)+1));符从后往前添加到r中StrAssign(S,Concat(head,V));}StrAssign(S,Concat(S,tail));//把}//String_Reversehead,V,tail连接为新串i+=Strlen(V);//当前指针跳到插入4.11串以后n++;voidString_Subtract(Stringtype}//ifs,Stringtypet,Stringtype&r)//求所有包returnn;含在串s中而t中没有的字符构成的新}//Replace串r分析:i+=Strlen(V);这一句是必需的,也{是容易忽略的.如省掉这一句,则在某StrAssign(r,"");些情况下,会引起不希望的后果,虽然for(i=1;i<=Strlen(s);i++)在大多数情况下没有影响.请思考:设{S="place",T="ace",V="face",则省掉StrAssign(c,SubString(s,i,1));i+=Strlen(V);运行时会出现什么结果?for(j=1;jStrlen(t))+)StrAssign(r,Concat(r,c));if(!StrCompare(SubString(s,i,Strlen(t)}),t))}//for{}//String_SubtractStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(t4.12),Strlen(s)-i-Strlen(t)+1));StrAssign(S,Concat(head,tail));//把课后答案网www.khdaw.comhead,tail连接为新串for(i=0,T[0]=0;chars[i];T[0]++,i++)n++;T[i+1]=chars[i];}//if}//StrAssignreturnn,}//Delete_SubString4.164.14charStrCompare(Stringtypes,Stringtypet)//串的比较,s>t时返回正数,s=t时返回StatusNiBoLan_to_BoLan(Stringtype0,ss[0]&&i>t[0])return0;型elseif(i>s[0])return-t[i];for(i=1;i<=Strlen(str);i++)elseif(i>t[0])returns[i];{elsereturns[i]-t[i];r=SubString(str,i,1);}//StrCompareif(r为字母)push(s,r);else4.17{if(StackEmpty(s))returnERROR;intString_Replace(Stringtypepop(s,a);&S,StringtypeT,StringtypeV);//将串Sif(StackEmpty(s))returnERROR;中所有子串T替换为V,并返回置换次pop(s,b);数StrAssign(t,Concat(r,b));{StrAssign(c,Concat(t,a));//把算符r,for(n=0,i=1;i<=S[0]-T[0]+1;i++)子前缀表达式a,b连接为新子前缀表{达式cfor(j=i,k=1;T[k]&&S[j]==T[k];j++,kpush(s,c);++);}if(k>T[0])//找到了与T匹配的子串:}//for分三种情况处理pop(s,new);{if(!StackEmpty(s))returnERROR;if(T[0]==V[0])returnOK;for(l=1;l<=T[0];l++)//新子串长度}//NiBoLan_to_BoLan与原子串相同时:直接替换分析:基本思想见书后注释3.23.请读者S[i+l-1]=V[l];用此程序取代作者早些时候对3.23题elseif(T[0]=i+T[0];l--)S[l+V[0]-T[0]]=S[l];voidStrAssign(Stringtype&T,charfor(l=1;l<=V[0];l++)chars&#;)//用字符数组chars给串T赋S[i+l-1]=V[l];值,Stringtype的定义见课本}{else//新子串长度小于原子串时:先课后答案网www.khdaw.com将后部左移r[0]=0;{for(i=1;i<=s[0];i++)for(l=i+V[0];l<=S[0]+V[0]-T[0];l+{+)c=s[i];S[l]=S[l-V[0]+T[0]];for(j=1;jt[0])r[++r[0]]=c;}//for}returnn;}//for}//String_Replace}//Subtract_String4.184.20intSubString_Delete(Stringtypetypedefstruct{&s,Stringtypet)//从串s中删除所有与tcharch;相同的子串,并返回删除次数intnum;{}mytype;for(n=0,i=1;i<=s[0]-t[0]+1;i++)voidStrAnalyze(StringtypeS)//统计串S{中字符的种类和个数for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++);{if(j>m)//找到了与t匹配的子串mytypeT[MAXSIZE];//用结构数组T{存储统计结果for(k=i;k<=s[0]-t[0];k++)for(i=1;i<=S[0];i++)s[k]=s[k+t[0]];//左移删除{s[0]-=t[0];n++;c=S[i];j=0;}while(T[j].ch&&T[j].ch!=c)j++;//查}//for找当前字符c是否已记录过returnn;if(T[j].ch)T[j].num++;}//Delete_SubStringelseT[j]={c,1};}//for4.21for(j=0;T[j].ch;j++)printf("%c:%dn",T[j].ch,T[j].num);typedefstruct{}//StrAnalyzecharch;LStrNode*next;4.19}LStrNode,*LString;//链串结构voidSubtract_String(Stringtypes,Stringtypet,Stringtype&r)//求所有包voidStringAssign(LString&s,LString含在串s中而t中没有的字符构成的新t)//把串t赋值给串s串r{{s=malloc(sizeof(LStrNode)); 课后答案网www.khdaw.comfor(q=s,p=t->next;p;p=p->next)returni;{}//StringLenr=(LStrNode*)malloc(sizeof(LStrNode));LString*Concat(LStrings,LStringt)//r->ch=p->ch;连接串s和串t形成新串,并返回指针q->next=r;q=r;{}p=malloc(sizeof(LStrNode));q->next=NULL;for(q=p,r=s->next;r;r=r->next)}//StringAssign{q->next=(LStrNode*)malloc(sizeof(LvoidStringCopy(LString&s,LStringt)//StrNode));把串t复制为串s.与前一个程序的区别q=q->next;在于,串s业已存在.q->ch=r->ch;{}//for//复制串sfor(p=s->next,q=t->next;p&&q;p=p->nfor(r=t->next;r;r=r->next)ext,q=q->next){{q->next=(LStrNode*)malloc(sizeof(Lp->ch=q->ch;pre=p;StrNode));}q=q->next;while(q)q->ch=r->ch;{}//for//复制串tp=(LStrNode*)malloc(sizeof(LStrNoq->next=NULL;de));returnp;p->ch=q->ch;}//Concatpre->next=p;pre=p;}LString*Sub_String(LStrings,intp->next=NULL;start,intlen)//返回一个串,其值等于串s}//StringCopy从start位置起长为len的子串{charStringCompare(LStrings,LStringp=malloc(sizeof(LStrNode));q=p;t)//串的比较,s>t时返回正数,s=t时返回for(r=s;start;start--,r=r->next);//找到0,snext)for(p=s->next,q=t->next;p&&q&&p->{ch==q->ch;p=p->next,q=q->next);q->next=(LStrNode*)malloc(sizeof(Lif(!p&&!q)return0;StrNode));elseif(!p)return-(q->ch);q=q->next;elseif(!q)returnp->ch;q->ch=r->ch;elsereturnp->ch-q->ch;}//复制串t}//StringCompareq->next=NULL;returnp;intStringLen(LStrings)//求串s的长度}//Sub_String(元素个数){4.22for(i=0,p=s->next;p;p=p->next,i++); 课后答案网www.khdaw.comvoidLString_Concat(LString&t,LString}//Find_Char&s,charc)//用块链存储结构,把串s插入到串t的字符c之后{4.23p=t.head;while(p&&!(i=Find_Char(p,c)))intLString_Palindrome(LStringL)//判p=p->next;//查找字符c断以块链结构存储的串L是否为回文if(!p)//没找到序列,是则返回1,否则返回0{{t.tail->next=s.head;InitStack(S);t.tail=s.tail;//把s连接在t的后面p=S.head;i=0;k=1;//i指示元素在块中}的下标,k指示元素在整个序列中的序else号(从1开始){for(k=1;k<=S.curlen;k++)q=p->next;{r=(Chunk*)malloc(sizeof(Chunk));//if(k<=S.curlen/2)Push(S,p->ch[i]);//将包含字符c的节点p分裂为两个将前半段的字符入串for(j=0;jch[j]="#";//原结点elseif(k>(S.curlen+1)/2)p包含c及其以前的部分{for(j=i;jch[i]!=c)return0;//失配r->ch[j]=p->ch[j];}p->ch[j]="#";//p的后半部分和r的if(++i==CHUNKSIZE)//转到下一个前半部分的字符改为无效字符"#"元素,当为块中最后一个元素时,转到}下一块p->next=s.head;{s.tail->next=r;p=p->next;r->next=q;//把串s插入到结点p和ri=0;之间}}//else}//fort.curlen+=s.curlen;//修改串长return1;//成功匹配s.curlen=0;}//LString_Palindrome}//LString_Concat4.24intFind_Char(Chunk*p,charc)//在某个voidHString_Concat(HString块中查找字符c,如找到则返回位置是s1,HStrings2,HString&t)//将堆结构表第几个字符,如没找到则返回0示的串s1和s2连接为新串t{{for(i=0;ich[i]!=cif(t.ch)free(t.ch);;i++);t.ch=malloc((s1.length+s2.length)*sizeif(i==CHUNKSIZE)return0;of(char));elsereturni+1;for(i=1;i<=s1.length;i++)t.ch[i-1]=s1.ch[i-1]; 课后答案网www.khdaw.comfor(j=1;j<=s2.length;j++,i++)4.26t.ch[i-1]=s2.ch[j-1];t.length=s1.length+s2.length;StatusHString_Insert(HString&S,int}//HString_Concatpos,HStringT)//把T插入堆结构表示的串S的第pos个字符之前4.25{if(pos<1)returnERROR;intHString_Replace(HStringif(pos>S.length)pos=S.length+1;//当&S,HStringT,HStringV)//堆结构串上插入位置大于串长时,看作添加在串尾的置换操作,返回置换次数S.ch=realloc(S.ch,(S.length+T.length)*{sizeof(char));for(n=0,i=0;i<=S.length-T.length;i++)for(i=S.length-1;i>=pos-1;i--){S.ch[i+T.length]=S.ch[i];//后移为插for(j=i,k=0;k=i+T.length;l--)i=1;j=1;S.ch[l+V.length-T.length]=S.ch[l];while(i<=s[0]&&j<=t[0])for(l=0;lt[0])returni-t[0];}//if}//Index_New}//forreturnn;4.28}//HString_Replace 课后答案网www.khdaw.comvoidLGet_next(LString&T)//链串上的{get_next算法for(maxlen=0,i=1;isucc;p->next=T;q=T;{while(p->succ)for(k=0,j=1;j<=S[0]-i;j++)//j为串S2{的当前指针,此时串S1的当前指针为if(q==T||p->data==q->data)i+j,两指针同步移动{{p=p->succ;q=q->succ;if(S[j]==S[j+i])k++;//用k记录连p->next=q;续相同的字符数}elsek=0;//失配时k归零elseq=q->next;if(k>maxlen)//发现了比以前发现}//while的更长的重复子串}//LGet_next{lrs1=j-k+1;lrs2=mrs1+i;maxlen=k;4.29//作记录}LStrNode*LIndex_KMP(LString}//forS,LStringT,LStrNode*pos)//链串上的}//forKMP匹配算法,返回值为匹配的子串if(maxlen)首指针{{printf("LongestRepeatingSubstringp=pos;q=T->succ;length:%dn",maxlen);while(p&&q)printf("Position1:%dPosition{2:%dn",lrs1,lrs2);if(q==T||p->chdata==q->chdata)}{elseprintf("NoRepeatingSubstringp=p->succ;found!n");q=q->succ;}//Get_LRepSub}分析:i代表"错位值".本算法的思想是,elseq=q->next;依次把串S的一个副本S2向右错位平}//while移1格,2格,3格,...与自身S1相匹配,if(!q)如果存在最长重复子串,则必然能在此{过程中被发现.用变量lrs1,lrs2,maxlenfor(i=1;i<=Strlen(T);i++)来记录已发现的最长重复子串第一次p=p->next;出现位置,第二次出现位置和长度.题returnp;目中未说明"重复子串"是否允许有重}//发现匹配后,要往回找子串的头叠部分,本算法假定允许.如不允许,只returnNULL;需在第二个for语句的循环条件中加上}//LIndex_KMPk<=i即可.本算法时间复杂度为O(Strlen(S)^2).4.304.31voidGet_LRepSub(StringtypeS)//求S的最长重复子串的位置和长度课后答案网www.khdaw.comvoidGet_LPubSub(Stringtype{S,StringtypeT)//求串S和串T的最长公lpsS=lps1;lpsT=lps2;共子串位置和长度}{elseif(S[0]>=T[0]){{lpsS=lps2;lpsT=lps1;StrAssign(A,S);StrAssign(B,T);}//将A,B上的位置映射回S,T上的}位置elseprintf("LongestPublicSubstring{length:%dn",maxlen);StrAssign(A,T);StrAssign(B,S);printf("PositioninS:%dPositionin}//为简化设计,令S和T中较长的那T:%dn",lpsS,lpsT);个为A,较短的那个为B}//iffor(maxlen=0,i=1-B[0];iA[0]-B[0])置不同时,需要匹配的区间的计算公式{也各不相同,请读者自己画图以帮助理jmin=i;jmax=A[0];解.本算法的时间复杂度是o（strlrn（s）}//B有一部分在A右端的右边*strlen（t））。else{jmin=i;jmax=i+B[0];第五章数组和广义表}//B在A左右两端之间.//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合5.18的区间)的端点:jmin,jmax.voidRSh(intA[n],intk)//把数组A的元for(k=0,j=jmin;j<=jmax;j++)素循环右移k位,只用一个辅助存储空{间if(A[j]==B[j-i])k++;{elsek=0;for(i=1;i<=k;i++)if(k>maxlen)if(n%i==0&&k%i==0)p=i;//求n和k{的最大公约数plps1=j-k+1;lps2=j-i-k+1;maxlen=k;for(i=0;i=T[0])temp=A[l]; 课后答案网www.khdaw.comA[l]=A[j];for(flag=1,k=0;kA[6],A[6]->A[12],A[12]->A[voidTSMatrix_Add(TSMatrix3],A[3]->A[9],A[9]->A[0].A,TSMatrixB,TSMatrix&C)//三元组第二条表示的稀疏矩阵加法链:A[1]->A[7],A[7]->A[13],A[13]->A[{4],A[4]->A[10],A[10]->A[1].C.mu=A.mu;C.nu=A.nu;C.tu=0;第三条pa=1;pb=1;pc=1;链:A[2]->A[8],A[8]->A[14],A[14]->A[for(x=1;x<=A.mu;x++)//对矩阵的每5],A[5]->A[11],A[11]->A[2].一行进行加法恰好使所有元素都右移一次.{虽然未经数学证明,但作者相信上述规while(A.data[pa].iB.data[pb].j)置{pa=MAXSIZE-A.tu+1;pb=1;pc=1;C.data[pc].i=x;for(x=1;x<=A.mu;x++)//对矩阵的每C.data[pc].j=B.data[pb].j;一行进行加法C.data[pc].e=B.data[pb].e;{pb++;pc++;while(A.data[pa].iB.data[pb].j)}{while(B.data[pb]==x)//插入B中剩A.data[pc].i=x;余的元素(第x行)A.data[pc].j=B.data[pb].j;{A.data[pc].e=B.data[pb].e;C.data[pc].i=x;pb++;pc++;C.data[pc].j=B.data[pb].j;}C.data[pc].e=B.data[pb].e;elsepb++;pc++;{}A.data[pc].i=x;}//forA.data[pc].j=A.data[pa].j;C.tu=pc;A.data[pc].e=A.data[pa].e}//TSMatrix_Addpa++;pc++;}5.22}//whilewhile(A.data[pa]==x)//插入A中剩voidTSMatrix_Addto(TSMatrix余的元素(第x行)&A,TSMatrixB)//将三元组矩阵B加到{A上A.data[pc].i=x;{A.data[pc].j=A.data[pa].j;for(i=1;i<=A.tu;i++)A.data[pc].e=A.data[pa].eA.data[MAXSIZE-A.tu+i]=A.data[i];/pa++;pc++;把A的所有元素都移到尾部以腾出位} 课后答案网www.khdaw.comwhile(B.data[pb]==x)//插入B中剩typedefstruct{余的元素(第x行)intseq;//该元素在以行{为主序排列时的序号A.data[pc].i=x;inte;A.data[pc].j=B.data[pb].j;}SElem;A.data[pc].e=B.data[pb].e;pb++;pc++;typedefstruct{}SElemdata[MAXSIZE];}//forintmu,nu,tu;A.tu=pc;}SMatrix;//单下标二元for(i=A.tu;ij>pb->j)//新插elseif(A.map[i][j]&&!B.map[i][j])入一个结点{{C.elem[pc]=A.elem[pa];p=(OLNode*)malloc(sizeof(OLNoC.map[i][j]=1;de));pa++;pc++;if(!pre)A.rhead[i]=p;}elsepre->right=p;elseif(!A.map[i][j]&&B.map[i][j])p->right=pa;pre=p;{p->i=i;p->j=pb->j;p->e=pb->e;//插C.elem[pc]=B.elem[pb];入行链表中C.map[i][j]=1;if(!A.chead[p->j])pb++;pc++;{}A.chead[p->j]=p;}p->down=NULL;}//BMMatrix_Add}else5.26{while(cp[p->j]->down)voidPrint_OLMatrix(OLMatrixA)//以cp[p->j]=cp[p->j]->down;三元组格式输出十字链表表示的矩阵p->down=cp[p->j]->down;{cp[p->j]->down=p;for(i=0;ij]=p;//插入列链表中if(A.rhead[i])}//iffor(p=A.rhead[i];p;p=p->right)//逐elseif(pa->jj)次遍历每一个行链表{printf("%d%d%dn",i,p->j,p->e;pre=pa;}pa=pa->right;}//Print_OLMatrix}//pa右移一步elseif(pa->e+pb->e)5.27{pa->e+=pb->e;voidOLMatrix_Add(OLMatrixpre=pa;pa=pa->right;&A,OLMatrixB)//把十字链表表示的课后答案网www.khdaw.compb=pb->right;elseMul(p->hp,x);}//直接相加}else}//Mul{if(!pre)A.rhead[i]=pa->right;5.29elsepre->right=pa->right;p=pa;pa=pa->right;//从行链表中voidMPList_Add(MPListA,MPList删除B,MPList&C)//广义表存储结构的多if(A.chead[p->j]==p)项式相加的递归算法A.chead[p->j]=cp[p->j]=p->down;{elsecp[p->j]->down=p->down;//C=(MPLNode*)malloc(sizeof(MPLNo从列链表中删除de));free(p);if(!A->tag&&!B->tag)//原子项,可直}//else接相加}//while{}//forC->coef=A->coef+B->coef;}//OLMatrix_Addif(!C->coef)分析:本题的具体思想在课本中有详细{的解释说明.free(C);C=NULL;5.28}}//ifvoidMPList_PianDao(MPList&L)//对elseif(A->tag&&B->tag)//两个多项广义表存储结构的多元多项式求第一式相加变元的偏导{{p=A;q=B;pre=NULL;for(p=L->hp->tp;p&&p->exp;pre=p,p=while(p&&q)p->tp){{if(p->exp==q->exp)if(p->tag)Mul(p->hp,p->exp);{elsep->coef*=p->exp;//把指数乘在C=(MPLNode*)malloc(sizeof(MP本结点或其下属结点上LNode));p->exp--;C->exp=p->exp;}MPList_Add(A->hp,B->hp,C->hp);pre->tp=NULL;pre->tp=C;pre=C;if(p)free(p);//删除可能存在的常数p=p->tp;q=q->tp;项}}//MPList_PianDaoelseif(p->exp>q->exp){voidMul(MPList&L,intx)//递归算法,C=(MPLNode*)malloc(sizeof(MP对多元多项式L乘以xLNode));{C->exp=p->exp;for(p=L;p;p=p->tp)C->hp=A->hp;{pre->tp=C;pre=C;if(!p->tag)p->coef*=x; 课后答案网www.khdaw.comp=p->tp;else}{elseq=(MPLNode*)malloc(sizeof(MPL{Node));C=(MPLNode*)malloc(sizeof(MPq->coef=x;q->exp=0;LNode));q->tag=0;q->tp=NULL;C->exp=q->exp;p->tp=q;C->hp=B->hp;}//否则新建常数项,下同pre->tp=C;pre=C;}//elseifq=q->tp;else}{}//whilex=A->coef;while(p)for(p=B;p->tp->tp;p=p->tp);{if(p->tp->exp==0)p->tp->coef+=x;C=(MPLNode*)malloc(sizeof(MPLif(!p->tp->coef)Node));{C->exp=p->exp;free(p->tp);C->hp=p->hp;p->tp=NULL;pre->tp=C;pre=C;}p=p->tp;else}{while(q)q=(MPLNode*)malloc(sizeof(MPL{Node));C=(MPLNode*)malloc(sizeof(MPLq->coef=x;q->exp=0;Node));q->tag=0;q->tp=NULL;C->exp=q->exp;p->tp=q;C->hp=q->hp;}pre->tp=C;pre=C;}//elseq=q->tp;}//MPList_Add}//将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题5.30}//elseifelseif(A->tag&&!B->tag)//多项式和intGList_Getdeph(GListL)//求广义表常数项相加深度的递归算法{{x=B->coef;if(!L->tag)return0;//原子深度为0for(p=A;p->tp->tp;p=p->tp);elseif(!L)return1;//空表深度为1if(p->tp->exp==0)p->tp->coef+=x;//m=GList_Getdeph(L->ptr.hp)+1;当多项式中含有常数项时,加上常数项n=GList_Getdeph(L->ptr.tp);if(!p->tp->coef)returnm>n?m:n;{}//GList_Getdephfree(p->tp);5.31p->tp=NULL;} 课后答案网www.khdaw.comvoidGList_Copy(GListA,GList&B)//在层次,layer表示当前层次复制广义表的递归算法{{if(!A)return;if(!A->tag)//当结点为原子时,直接复if(!A->tag)printf("%d制%dn",A->atom,layer);{elseB->tag=0;{B->atom=A->atom;GList_PrintElem(A->ptr.hp,layer+1);}GList_PrintElem(A->ptr.tp,layer);//else//当结点为子表时注意尾表与原表是同一层次{}B->tag=1;}//GList_PrintElemif(A->ptr.hp){5.34B->ptr.hp=malloc(sizeof(GLNode));GList_Copy(A->ptr.hp,B->ptr.hp);voidGList_Reverse(GListA)//递归逆}//复制表头转广义表Aif(A->ptr.tp){{if(A->tag&&A->ptr.tp)//当A不为原B->ptr.tp=malloc(sizeof(GLNode));子且表尾非空时才需逆转GList_Copy(A->ptr.tp,B->ptr.tp);{}//复制表尾D=C->ptr.hp;}//elseA->ptr.tp->ptr.hp=A->ptr.hp;A->ptr.h}//GList_Copyp=D;//交换表头和表尾GList_Reverse(A->ptr.hp);5.32GList_Reverse(A->ptr.tp);//逆转表头和表尾intGList_Equal(GListA,GListB)//判断}广义表A和B是否相等,是则返回1,}//GList_Reverse否则返回0{//广义表相等可分三种情况:5.35if(!A&&!B)return1;//空表是相等的if(!A->tag&&!B->tag&&A->atom==BStatusCreate_GList(GList&L)//根据输->atom)return1;//原子的值相等入创建广义表L,并返回指针if(A->tag&&B->tag){if(GList_Equal(A->ptr.hp,B->ptr.hp)scanf("%c",&ch);&&GList_Equal(A->ptr.tp,B->ptr.tp))if(ch=="")return1;//表头表尾都相等{return0;L=NULL;}//GList_Equalscanf("%c",&ch);if(ch!=")")returnERROR;5.33returnOK;}voidGList_PrintElem(GListA,intL=(GList)malloc(sizeof(GLNode));layer)//递归输出广义表的原子及其所L->tag=1; 课后答案网www.khdaw.comif(isalphabet(ch))//输入是字母voidGList_DelElem(GList&A,intx)//{从广义表A中删除所有值为x的原子p=(GList)malloc(sizeof(GLNode));//{建原子型表头if(A->ptr.hp->tag)p->tag=0;p->atom=ch;GList_DelElem(A->ptr.hp,x);L->ptr.hp=p;else}if(!A->ptr.hp->tag&&A->ptr.hp->atom=elseif(ch=="(")=x)Create_GList(L->ptr.hp);//建子表型表{头q=A;elsereturnERROR;A=A->ptr.tp;//删去元素值为x的scanf("%c",&ch);表头if(ch==")")L->ptr.tp=NULL;free(q);elseif(ch==",")Create_GList(L->ptr.tp);GList_DelElem(A,x);//建表尾}elsereturnERROR;if(A->ptr.tp)returnOK;GList_DelElem(A->ptr.tp,x);}//Create_GList}//GList_DelElem分析:本题思路见书后解答.5.395.36voidGList_PrintElem_LOrder(GListvoidGList_PrintList(GListA)//按标准A)//按层序输出广义表A中的所有元形式输出广义表素{{if(!A)printf("()");//空表InitQueue(Q);elseif(!A->tag)for(p=L;p;p=p->ptr.tp)EnQueue(Q,p);printf("%d",A->atom);//原子while(!QueueEmpty(Q))else{{DeQueue(Q,r);printf("(");if(!r->tag)printf("%d",r->atom);GList_PrintList(A->ptr.hp);elseif(A->ptr.tp)for(r=r->ptr.hp;r;r=r->ptr.tp){EnQueue(Q,r);printf(",");}//whileGList_PrintList(A->ptr.tp);}//GList_PrintElem_LOrder}//只有当表尾非空时才需要打印逗号分析:层序遍历的问题,一般都是借助printf(")");队列来完成的,每次从队头取出一个元}//else素的同时把它下一层的孩子插入队尾.}//GList_PrintList这是层序遍历的基本思想.5.37第六章树和二叉树课后答案网www.khdaw.com6.33elsereturn0;}//Bitree_SimintIs_Descendant_C(intu,intv)//在孩子存储结构上判断u是否v的子孙,是6.37则返回1,否则返回0{voidPreOrder_Nonrecursive(BitreeT)//if(u==v)return1;先序遍历二叉树的非递归算法else{{InitStack(S);if(L[v])Push(S,T);//根指针进栈if(Is_Descendant(u,L[v]))return1;while(!StackEmpty(S))if(R[v]){if(Is_Descendant(u,R[v]))return1;while(Gettop(S,p)&&p)//这是个递归算法{}visit(p->data);return0;push(S,p->lchild);}//Is_Descendant_C}//向左走到尽头pop(S,p);6.34if(!StackEmpty(S)){intIs_Descendant_P(intu,intv)//在双亲pop(S,p);存储结构上判断u是否v的子孙,是则push(S,p->rchild);//向右一步返回1,否则返回0}{}//whilefor(p=u;p!=v&&p;p=T[p]);}//PreOrder_Nonrecursiveif(p==v)return1;elsereturn0;6.38}//Is_Descendant_Ptypedefstruct{6.35BTNode*ptr;enum{0,1,2}mark;这一题根本不需要写什么算法,见书后}PMType;//有mark域注释:两个整数的值是相等的.的结点指针类型6.36voidPostOrder_Stack(BiTreeT)//后续遍历二叉树的非递归算法,用栈intBitree_Sim(BitreeB1,BitreeB2)//判{断两棵树是否相似的递归算法PMTypea;{InitStack(S);//S的元素为PMType类if(!B1&&!B2)return1;型elsePush(S,{T,0});//根结点入栈if(B1&&B2&&Bitree_Sim(B1->lchild,while(!StackEmpty(S))B2->lchild)&&Bitree_Sim(B1->rchild,{B2->rchild))Pop(S,a);return1;switch(a.mark) 课后答案网www.khdaw.com{if(p->lchild)p=p->lchild;//访问左case0:子树Push(S,{a.ptr,1});//修改mark域break;if(a.ptr->lchild)case1:Push(S,{a.ptr->lchild,0});//访问左子树p->mark=2;break;if(p->rchild)p=p->rchild;//访问右case1:子树Push(S,{a.ptr,2});//修改mark域break;if(a.ptr->rchild)case2:Push(S,{a.ptr->rchild,0});//访问右子树visit(p);break;p->mark=0;//恢复mark值case2:p=p->parent;//返回双亲结点visit(a.ptr);//访问结点,返回}}}//PostOrder_Nonrecursive}//while分析:本题思路与上一题完全相同,只}//PostOrder_Stack不过结点的mark值是储存在结点中的,分析:为了区分两次过栈的不同处理方而不是暂存在堆栈中,所以访问完毕后式,在堆栈中增加一个mark域,mark=0要将mark域恢复为0,以备下一次遍表示刚刚访问此结点,mark=1表示左历.子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的6.40mark域值决定做何种动作.typedefstruct{6.39intdata;PBTNode*lchild;typedefstruct{PBTNode*rchild;intdata;PBTNode*parent;EBTNode*lchild;}PBTNode,PBitree;//有EBTNode*rchild;双亲指针域的二叉树结点类型EBTNode*parent;enum{0,1,2}mark;voidInorder_Nonrecursive(PBitreeT)//}EBTNode,EBitree;//有不设栈非递归遍历有双亲指针的二叉mark域和双亲指针域的二叉树结点类树型{p=T;voidPostOrder_Nonrecursive(EBitreewhile(p->lchild)p=p->lchild;//向左走T)//后序遍历二叉树的非递归算法,不到尽头用栈while(p){{p=T;visit(p);while(p)if(p->rchild)//寻找中序后继:当有右switch(p->mark)子树时{{case0:p=p->rchild;p->mark=1;while(p->lchild)p=p->lchild;//后继课后答案网www.khdaw.com就是在右子树中向左走到尽头main()}{elseif(p->parent->lchild==p)...p=p->parent;//当自己是双亲的左孩子scanf("%d",&k);时后继就是双亲c=0;//在主函数中调用前,要给计数器else赋初值0{Get_PreSeq(T,k);p=p->parent;...while(p->parent&&p->parent->rchil}//maind==p)p=p->parent;p=p->parent;6.42}//当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子intLeafCount_BiTree(BitreeT)//求二叉树中的祖先树中叶子结点的数目}//while{}//Inorder_Nonrecursiveif(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return6.411;//叶子结点elsereturnintc,k;//这里把k和计数器c作为全局Leaf_Count(T->lchild)+Leaf_Count(T->变量处理rchild);//左子树的叶子数加上右子树的叶子数voidGet_PreSeq(BitreeT)//求先序序列}//LeafCount_BiTree为k的结点的值{6.43if(T){voidBitree_Revolute(BitreeT)//交换所c++;//每访问一个子树的根都会使有结点的左右子树前序序号计数器加1{if(c==k)T->lchild<->T->rchild;//交换左右子{树printf("Valueis%dn",T->data);if(T->lchild)exit(1);Bitree_Revolute(T->lchild);}if(T->rchild)elseBitree_Revolute(T->rchild);//左右子树{再分别交换各自的左右子树Get_PreSeq(T->lchild);//在左子树}//Bitree_Revolute中查找Get_PreSeq(T->rchild);//在右子树6.44中查找intGet_Sub_Depth(BitreeT,intx)//求二}叉树中以值为x的结点为根的子树深}//if度}//Get_PreSeq{if(T->data==x) 课后答案网www.khdaw.com{if(T->rchild)Del_Sub(T->rchild);printf("%dn",Get_Depth(T));//找到free(T);了值为x的结点,求其深度}//Del_Subexit1;}6.46else{voidBitree_Copy_Nonrecursive(Bitreeif(T->lchild)T,Bitree&U)//非递归复制二叉树Get_Sub_Depth(T->lchild,x);{if(T->rchild)InitStack(S1);InitStack(S2);Get_Sub_Depth(T->rchild,x);//在左右push(S1,T);//根指针进栈子树中继续寻找U=(BTNode*)malloc(sizeof(BTNode));}U->data=T->data;}//Get_Sub_Depthq=U;push(S2,U);while(!StackEmpty(S))intGet_Depth(BitreeT)//求子树深度的{递归算法while(Gettop(S1,p)&&p){{if(!T)return0;q->lchild=(BTNode*)malloc(sizeof(elseBTNode));{q=q->lchild;q->data=p->data;m=Get_Depth(T->lchild);push(S1,p->lchild);n=Get_Depth(T->rchild);push(S2,q);return(m>n?m:n)+1;}//向左走到尽头}pop(S1,p);}//Get_Depthpop(S2,q);if(!StackEmpty(S1))6.45{pop(S1,p);pop(S2,q);voidDel_Sub_x(BitreeT,intx)//删除所q->rchild=(BTNode*)malloc(sizeof(有以元素x为根的子树BTNode));{q=q->rchild;q->data=p->data;if(T->data==x)Del_Sub(T);//删除该push(S1,p->rchild);//向右一步子树push(S2,q);else}{}//whileif(T->lchild)Del_Sub_x(T->lchild,x);}//BiTree_Copy_Nonrecursiveif(T->rchild)Del_Sub_x(T->rchild,x);分析:本题的算法系从6.37改写而来.//在左右子树中继续查找}//else6.47}//Del_Sub_xvoidLayerOrder(BitreeT)//层序遍历二voidDel_Sub(BitreeT)//删除子树T叉树{{if(T->lchild)Del_Sub(T->lchild);InitQueue(Q);//建立工作队列课后答案网www.khdaw.comEnQueue(Q,T);子树中继续寻找while(!QueueEmpty(Q))if(!found)path[i]=NULL;//回溯{}//FindpathDeQueue(Q,p);visit(p);6.49if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);intIsFull_Bitree(BitreeT)//判断二叉树}是否完全二叉树,是则返回1,否则返回}//LayerOrder0{6.48InitQueue(Q);flag=0;intfound=FALSE;EnQueue(Q,T);//建立工作队列while(!QueueEmpty(Q))Bitree*Find_Near_Ancient(Bitree{T,Bitreep,Bitreeq)//求二叉树T中结点DeQueue(Q,p);p和q的最近共同祖先if(!p)flag=1;{elseif(flag)return0;Bitreepathp[100],pathq[100]//设立else两个辅助数组暂存从根到p,q的路径{Findpath(T,p,pathp,0);EnQueue(Q,p->lchild);found=FALSE;EnQueue(Q,p->rchild);//不管孩子Findpath(T,q,pathq,0);//求从根到p,q是否为空,都入队列的路径放在pathp和pathq中}for(i=0;pathp[i]==pathq[i]&&pathp[i];i}//while++);//查找两条路径上最后一个相同return1;结点}//IsFull_Bitreereturnpathp[--i];分析:该问题可以通过层序遍历的方法}//Find_Near_Ancient来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.voidFindpath(BitreeT,Bitreep,Bitree这样当树为完全二叉树时,遍历时得到path[],inti)//求从T到p路径的递归算是一个连续的不包含空指针的序列.反法之,则序列中会含有空指针.{if(T==p)6.50{found=TRUE;StatusCreateBitree_Triplet(Bitree&T)//return;//找到输入三元组建立二叉树}{path[i]=T;//当前结点存入路径if(getchar()!="^")returnERROR;if(T->lchild)T=(BTNode*)malloc(sizeof(BTNode));Findpath(T->lchild,p,path,i+1);//在左子p=T;p->data=getchar();树中继续寻找getchar();//滤去多余字符if(T->rchild&&!found)InitQueue(Q);Findpath(T->rchild,p,path,i+1);//在右EnQueue(Q,T); 课后答案网www.khdaw.comwhile((parent=getchar())!="^"&&(childreturnERROR;=getchar())&&(side=getchar()))printf(")");{}while(QueueHead(Q)!=parent&&!Quelseif(!Print_Expression(T->rchild))eueEmpty(Q))DeQueue(Q,e);returnERROR;if(QueueEmpty(Q))returnERROR;//}未按层序输入elsereturnERROR;//非法字符p=QueueHead(Q);returnOK;q=(BTNode*)malloc(sizeof(BTNode)}//Print_Expression);if(side=="L")p->lchild=q;6.52elseif(side=="R")p->rchild=q;elsereturnERROR;//格式不正确typedefstruct{q->data=child;BTNodenode;EnQueue(Q,q);intlayer;}}BTNRecord;//包含结点returnOK;所在层次的记录类型}//CreateBitree_TripletintFanMao(BitreeT)//求一棵二叉树的6.51"繁茂度"{StatusPrint_Expression(BitreeT)//按标intcountd;//count数组存放每一层的准形式输出以二叉树存储的表达式结点数{InitQueue(Q);//Q的元素为if(T->data是字母)BTNRecord类型printf("%c",T->data);EnQueue(Q,{T,0});elseif(T->data是操作符)while(!QueueEmpty(Q)){{if(!T->lchild||!T->rchild)returnDeQueue(Q,r);ERROR;//格式错误count[r.layer]++;if(T->lchild->data是操作符if(r.node->lchild)&&T->lchild->data优先级低于T->data)EnQueue(Q,{r.node->lchild,r.layer+1});{if(r.node->rchild)printf("(");EnQueue(Q,{r.node->rchild,r.layer+1});if(!Print_Expression(T->lchild))}//利用层序遍历来统计各层的结点returnERROR;数printf(")");h=r.layer;//最后一个队列元素所在层}//注意在什么情况下要加括号就是树的高度elseif(!Print_Expression(T->lchild))for(maxn=count[0],i=1;count[i];i++)returnERROR;if(count[i]>maxn)maxn=count[i];//if(T->rchild->data是操作符求层最大结点数&&T->rchild->data优先级低于T->data)returnh*maxn;{}//FanMaoprintf("(");分析:如果不允许使用辅助数组,就必if(!Print_Expression(T->rchild)) 课后答案网www.khdaw.com须在遍历的同时求出层最大结点数,形sa中各结点对应的树指针式上会复杂一些,你能写出来吗?if(!sa.last){6.53T=NULL;//空树return;intmaxh;}ptr[1]=(BTNode*)malloc(sizeof(BTNoStatusPrintpath_MaxdepthS1(Bitreede));T)//求深度等于树高度减一的最靠左ptr[1]->data=sa.elem[1];//建立树根的结点T=ptr[1];{for(i=2;i<=sa.last;i++)Bitreepathd;{maxh=Get_Depth(T);//Get_Depth函if(!sa.elem[i])returnERROR;//顺序数见6.44错误if(maxh<2)returnERROR;//无符合条ptr[i]=(BTNode*)malloc(sizeof(BTN件结点ode));Find_h(T,1);ptr[i]->data=sa.elem[i];returnOK;j=i/2;//找到结点i的双亲j}//Printpath_MaxdepthS1if(i-j*2)ptr[j]->rchild=ptr[i];//i是j的右孩子voidFind_h(BitreeT,inth)//寻找深度elseptr[j]->lchild=ptr[i];//i是j的左为maxh-1的结点孩子{}path[h]=T;returnOK;if(h==maxh-1)}//CreateBitree_SqList{for(i=1;path[i];i++)6.55printf("%c",path[i]->data);exit;//打印输出路径intDescNum(BitreeT)//求树结点T的}子孙总数填入DescNum域中,并返回else该数{{if(T->lchild)Find_h(T->lchild,h+1);if(!T)return-1;if(T->rchild)Find_h(T->rchild,h+1);else}d=(DescNum(T->lchild)+DescNum(T->path[h]=NULL;//回溯rchild)+2);//计算公式}//Find_hT->DescNum=d;returnd;6.54}//DescNum分析:该算法时间复杂度为O(n),n为树StatusCreateBitree_SqList(Bitree结点总数.注意:为了能用一个统一的&T,SqListsa)//根据顺序存储结构建立公式计算子孙数目,所以当T为空指针二叉链表时,要返回-1而不是0.{Bitreeptr[sa.last+1];//该数组储存与6.56 课后答案网www.khdaw.comBTNode*PreOrder_Next(BTNode*p)//if(!p->ltag&&!p->rtag)return在先序后继线索二叉树中查找结点pINFEASIBLE;//无法插入的先序后继,并返回指针if(p->ltag)//x作为p的左子树{{if(p->lchild)returnp->lchild;s=p->lchild;//s为p的前驱elsereturnp->rchild;p->ltag=Link;}//PreOrder_Nextp->lchild=x;分析:总觉得不会这么简单.是不是哪q=x;儿理解错了?while(q->lchild)q=q->lchild;q->lchild=s;//找到子树中的最左结6.57点,并修改其前驱指向sq=x;BitreePostOrder_Next(Bitreep)//在后while(q->rchild)q=q->rchild;序后继线索二叉树中查找结点p的后q->rchild=p;//找到子树中的最右结序后继,并返回指针点,并修改其前驱指向p{}if(p->rtag)returnp->rchild;//p有后继else//x作为p的右子树线索{elseif(!p->parent)returnNULL;//p是s=p->rchild;//s为p的后继根结点p->rtag=Link;elseif(p==p->parent->rchild)returnp->rchild=x;p->parent;//p是右孩子q=x;elsewhile(q->rchild)q=q->rchild;if(p==p->parent->lchild&&p->parent->tq->rchild=s;//找到子树中的最右结ag)点,并修改其前驱指向sreturnp->parent;//p是左孩子且双亲q=x;没有右孩子while(q->lchild)q=q->lchild;else//p是左孩子且双亲有右孩子q->lchild=p;//找到子树中的最左结{点,并修改其前驱指向pq=p->parent->rchild;}while(!q->ltag||!q->rtag)returnOK;{}//Insert_BiThrTreeif(!q->ltag)q=q->lchild;elseq=q->rchild;6.59}//从p的双亲的右孩子向下走到底returnq;voidPrint_CSTree(CSTreeT)//输出孩}//else子兄弟链表表示的树T的各边}//PostOrder_Next{for(child=T->firstchild;child;child=chil6.58d->nextsib){StatusInsert_BiThrTree(BiThrTreeprintf("(%c,%c),",T->data,child->data&T,BiThrTree&p,BiThrTree&x)//在中);序线索二叉树T的结点p下插入子树xPrint_CSTree(child);{ 课后答案网www.khdaw.com}if(!T)return0;//空树}//Print_CSTreeelse{6.60for(maxd=0,p=T->firstchild;p;p=p->nextsib)intLeafCount_CSTree(CSTreeT)//求孩if((d=GetDepth_CSTree(p))>maxd)子兄弟链表表示的树T的叶子数目maxd=d;//子树的最大深度{returnmaxd+1;if(!T->firstchild)return1;//叶子结点}else}//GetDepth_CSTree{count=0;6.63for(child=T->firstchild;child;child=child->nextsib)intGetDepth_CTree(CTreeA)//求孩子count+=LeafCount_CSTree(child);链表表示的树A的深度returncount;//各子树的叶子数之和{}returnSubDepth(A.r);}//LeafCount_CSTree}//GetDepth_CTree6.61intSubDepth(intT)//求子树T的深度{intGetDegree_CSTree(CSTreeT)//求孩if(!A.nodes[T].firstchild)return1;子兄弟链表表示的树T的度for(sd=1,p=A.nodes[T].firstchild;p;p=p{->next)if(!T->firstchild)return0;//空树if((d=SubDepth(p->child))>sd)sd=d;elsereturnsd+1;{}//SubDepthdegree=0;for(p=T->firstchild;p;p=p->nextsib)6.64degree++;//本结点的度for(p=T->firstchild;p;p=p->nextsib)intGetDepth_PTree(PTreeT)//求双亲{表表示的树T的深度d=GetDegree_CSTree(p);{if(d>degree)degree=d;//孩子结点maxdep=0;的度的最大值for(i=0;i=0;j=T.nodes[j].parent)}//GetDegree_CSTreedep++;//求每一个结点的深度if(dep>maxdep)maxdep=dep;6.62}returnmaxdep;intGetDepth_CSTree(CSTreeT)//求孩}//GetDepth_PTree子兄弟链表表示的树T的深度{6.65 课后答案网www.khdaw.comcharPred,Ind;//假设前序序列和中序下标,终止下标,和在中序子序列里的序列已经分别储存在数组Pre和In中起始和终止下标.BitreeBuild_Sub(intPre_Start,int6.66Pre_End,intIn_Start,intIn_End)//由子树的前序和中序序列建立其二叉链表typedefstruct{{CSNode*ptr;sroot=(BTNode*)malloc(sizeof(BTNoCSNode*lastchild;de));//建根}NodeMsg;//结点的指针sroot->data=Pre[Pre_Start];和其最后一个孩子的指针for(i=In_Start;In[i]!=sroot->data;i++);//在中序序列中查找子树根StatusBulid_CSTree_PTree(PTreeT)//leftlen=i-In_Start;由树T的双亲表构造其孩子兄弟链表rightlen=In_End-i;//计算左右子树的{大小NodeMsgTreed;if(leftlen)for(i=0;ilchild=lroot;Tree[i].ptr->data=T.node[i].data;//建}//建左子树,注意参数表的计算结点if(rightlen)if(T.nodes[i].parent>=0)//不是树根{{rroot=Build_Sub(Pre_End-rightlen+1,j=T.nodes[i].parent;//本算法要求双Pre_End,In_End-rightlen+1,In_End);亲表必须是按层序存储sroot->rchild=rroot;if(!(Tree[j].lastchild))//双亲当前还}//建右子树,注意参数表的计算没有孩子returnsroot;//返回子树根Tree[j].ptr->firstchild=Tree[i].ptr;}//Build_Sub//成为双亲的第一个孩子else//双亲已经有了孩子main()Tree[j].lastchild->nextsib=Tree[i].p{tr;//成为双亲最后一个孩子的下一个...兄弟Build_Sub(1,n,1,n);//初始调用参数,nTree[j].lastchild=Tree[i].ptr;//成为为树结点总数双亲的最后一个孩子...}//if}}//for分析:本算法利用了这样一个性质,即}//Bulid_CSTree_PTree一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始6.67下标和终止下标来确定一棵子typedefstruct{树.Pre_Start,Pre_End,In_Start和In_Endchardata;分别指示子树在前序子序列里的起始CSNode*ptr;CSNode*lastchild; 课后答案网www.khdaw.com}NodeInfo;//结点数据,结点指{针和最后一个孩子的指针CSNode*ptrd;//树结点指针的辅助存储StatusCreateCSTree_Duplet(CSTreeptr[0]=(CSNode*)malloc(sizeof(CSNo&T)//输入二元组建立树的孩子兄弟链de));表i=0;k=1;//i为当前结点序号,k为当前{孩子的序号NodeInfoTreed;while(node[i])n=1;k=0;{if(getchar()!="^")returnERROR;//未ptr[i]->data=node[i];按格式输入d=degree[i];if((c=getchar())=="^")T=NULL;//空树if(d)Tree[0].ptr=(CSNode*)malloc(sizeof({CSNode));ptr[k++]=(CSNode*)malloc(sizeof(Tree[0].data=c;CSNode));//k为当前孩子的序号Tree[0].ptr->data=c;ptr[i]->firstchild=ptr[k];//建立i与while((p=getchar())!="^"&&(c=getchar(第一个孩子k之间的联系))!="^")for(j=2;j<=d;j++){{Tree[n].ptr=(CSNode*)malloc(sizeof(ptr[k++]=(CSNode*)malloc(sizeof(CSNode));CSNode));Tree[n].data=c;ptr[k-1]->nextsib=ptr[k];//当结点Tree[n].ptr->data=c;的度大于1时,为其孩子建立兄弟链表for(k=0;Tree[k].data!=p;k++);//查找}//for当前边的双亲结点}//ifif(Tree[k].data!=p)returnERROR;//i++;未找到:未按层序输入}//whiler=Tree[k].ptr;}//CreateCSTree_Degreeif(!r->firstchild)r->firstchild=Tree[n].ptr;6.69elseTree[k].lastchild->nextsib=Tree[n].ptr;voidPrint_BiTree(BiTreeT,inti)//按树Tree[k].lastchild=Tree[n].ptr;//这一状打印输出二叉树的元素,i表示结点段含义同上一题所在层次,初次调用时i=0n++;{}//whileif(T->rchild)returnOK;Print_BiTree(T->rchild,i+1);}//CreateCSTree_Dupletfor(j=1;j<=i;j++)printf("");//打印i个空格以表示出层次6.68printf("%cn",T->data);//打印T元素,换行StatusCreateCSTree_Degree(charif(T->lchild)node[],intdegree[])//由结点的层序序Print_BiTree(T->rchild,i+1);列和各结点的度构造树的孩子兄弟链}//Print_BiTree表课后答案网www.khdaw.com分析:该递归算法实际上是带层次信息6.72的中序遍历,只不过按照题目要求,顺序为先右后左.voidPrint_CTree(inte,inti)//按凹入表形式打印输出树的元素,i表示结点所6.70在层次{StatusCreateBiTree_GList(BiTreefor(j=1;j<=i;j++)printf("");//留出i个&T)//由广义表形式的输入建立二叉链空格以表现出层次表printf("%cn",T.nodes[e].data);//打印{元素,换行c=getchar();for(p=T.nodes[e].firstchild;p;p=p->nexif(c=="#")T=NULL;//空子树t)elsePrint_CSTree(p->child,i+1);//打印子{树T=(CSNode*)malloc(sizeof(CSNode)}//Print_CSTree);T->data=c;main()if(getchar()!="(")returnERROR;{if(!CreateBiTree_GList(pl))return...ERROR;Print_CTree(T.r,0);//初次调用时i=0T->lchild=pl;...if(getchar()!=",")returnERROR;}//mainif(!CreateBiTree_GList(pr))returnERROR;6.73T->rchild=pr;if(getchar()!=")")returnERROR;//这charc;//全局变量,指示当前字符些语句是为了保证输入符合A(B,C)的StatusCreateCSTree_GList(CSTree格式&T)//由广义表形式的输入建立孩子兄}弟链表returnOK;{}//CreateBiTree_GListc=getchar();6.71T=(CSNode*)malloc(sizeof(CSNode));T->data=c;voidPrint_CSTree(CSTreeT,inti)//按if((c=getchar())=="(")//非叶结点凹入表形式打印输出树的元素,i表示{结点所在层次,初次调用时i=0if(!CreateCSTree_GList(fc))return{ERROR;//建第一个孩子for(j=1;j<=i;j++)printf("");//留出i个T->firstchild=fc;空格以表现出层次for(p=fc;c==",";p->nextsib=nc,p=nc)//printf("%cn",T->data);//打印元素,换建兄弟链行if(!CreateCSTree_GList(nc))returnfor(p=T->firstchild;p;p=p->nextsib)ERROR;Print_CSTree(p,i+1);//打印子树p->nextsib=NULL;}//Print_CSTreeif((c=getchar())!=")")returnERROR; 课后答案网www.khdaw.com//括号不配对{}CreateCTree_GList();elseT->firtchild=NULL;//叶子结点p=(CTBox*)malloc(sizeof(CTBox));returnOK;T.nodes[i].firstchild=p;}//CreateBiTree_GListp->child=pos;//建立孩子链的头分析:书后给出了两个间接递归的算法,for(;c==",";p=p->next)//建立孩子链事实上合成一个算法在形式上可能更{好一些.本算法另一个改进之处在于加CreateCTree_GList(T,j);//用j返回入了广义表格式是否合法的判断.分配得到的子树根位置p->child=j;6.74p->next=(CTBox*)malloc(sizeof(CTBox));voidPrintGlist_CSTree(CSTreeT)//按}广义表形式输出孩子兄弟链表表示的p->next=NULL;树if((c=getchar())!=")")returnERROR;{//括号不配对printf("%c",T->data);}//ifif(T->firstchild)//非叶结点elseT.nodes[i].firtchild=NULL;//叶子{结点printf("(");returnOK;for(p=T->firstchild;p;p=p->nextsib)}//CreateBiTree_GList{分析:该算法中,pos变量起着"分配"结PrintGlist_CSTree(p);点在表中的位置的作用,是按先序序列if(p->nextsib)printf(",");//最后一个从上向下分配,因此树根T.r一定等于孩子后面不需要加逗号0,而最终的pos值就是结点数T.n.}printf(")");6.76}//if}//PrintGlist_CSTreevoidPrintGList_CTree(CTreeT,inti)//按广义表形式输出孩子链表表示的树6.75{printf("%c",T.nodes[i].data);charc;if(T.nodes[i].firstchild)//非叶结点intpos=0;//pos是全局变量,指示已经{分配到了哪个结点printf("(");for(p=T->firstchild;p;p=p->nextsib)StatusCreateCTree_GList(CTree&T,int{&i)//由广义表形式的输入建立孩子链PrintGlist_CSTree(T,p->child);表if(p->nextsib)printf(",");//最后一个{孩子后面不需要加逗号c=getchar();}T.nodes[pos].data=c;printf(")");i=pos++;//i是局部变量,指示当前正}//if在处理的子树根}//PrintGlist_CTreeif((c=getchar())=="(")//非叶结点课后答案网www.khdaw.com7.15第七章图//本题中的图G均为有向无权图,其余情况容易由此写出7.14StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点StatusBuild_AdjList(ALGraph&G)//输v入有向图的顶点数,边数,顶点信息和{边的信息建立邻接表if(G.vexnum+1)>MAX_VERTEX_NU{MreturnINFEASIBLE;InitALGraph(G);G.vexs[++G.vexnum]=v;scanf("%d",&v);returnOK;if(v<0)returnERROR;//顶点数不能}//Insert_Vex为负G.vexnum=v;StatusInsert_Arc(MGraph&G,charscanf("%d",&a);v,charw)//在邻接矩阵表示的图G上插if(a<0)returnERROR;//边数不能为入边(v,w)负{G.arcnum=a;if((i=LocateVex(G,v))<0)returnfor(m=0;mnextarif((m=LocateVex(G,v))<0)returnc;q=q->nextarc);ERROR;q->nextarc=p;G.vexs[m]<->G.vexs[n];//将待删除顶}点交换到最后一个顶点p->adjvex=j;p->nextarc=NULL;for(i=0;iq->nexG.vexnum--;tarc;q=q->nextarc)returnOK;if(q->adjvex==j)returnERROR;//}//Delete_Vex边已经存在分析:如果不把待删除顶点交换到最后q->nextarc=p;一个顶点的话,算法将会比较复杂,而}伴随着大量元素的移动,时间复杂度也G.arcnum++;会大大增加.returnOK;}//Insert_ArcStatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删7.17除边(v,w){//为节省篇幅,本题只给出较为复杂的if((i=LocateVex(G,v))<0)returnDelete_Vex算法.其余算法请自行写出.ERROR;if((j=LocateVex(G,w))<0)returnStatusDelete_Vex(OLGraph&G,charERROR;v)//在十字链表表示的图G上删除顶点if(G.arcs[i][j].adj)v{{G.arcs[i][j].adj=0;if((m=LocateVex(G,v))<0)returnG.arcnum--;ERROR;}n=G.vexnum;returnOK;for(i=0;itailvex==m)//如果待删除的边是头链上的第一个结点//为节省篇幅,本题只给出Insert_Arc算{法.其余算法请自行写出.q=G.xlist[i].firstin;G.xlist[i].firstin=q->hlink;StatusInsert_Arc(ALGraph&G,charfree(q);G.arcnum--;v,charw)//在邻接表表示的图G上插入}边(v,w)else//否则{{if((i=LocateVex(G,v))<0)returnfor(p=G.xlist[i].firstin;p&&p->hlinkERROR;->tailvex!=m;p=p->hlink);if((j=LocateVex(G,w))<0)returnif(p)ERROR;{p=(ArcNode*)malloc(sizeof(ArcNode)q=p->hlink;);p->hlink=q->hlink;p->adjvex=j;p->nextarc=NULL;free(q);G.arcnum--;if(!G.vertices[i].firstarc)}G.vertices[i].firstarc=p;}//elseelse}//for 课后答案网www.khdaw.comfor(i=0;iheadvex==m)//ERROR;如果待删除的边是尾链上的第一个结if((j=LocateVex(G,w))<0)return点ERROR;{if(G.adjmulist[i].firstedge->jvex==j)q=G.xlist[i].firstout;G.adjmulist[i].firstedge=G.adjmulist[iG.xlist[i].firstout=q->tlink;].firstedge->ilink;free(q);G.arcnum--;else}{else//否则for(p=G.adjmulist[i].firstedge;p&&p-{>ilink->jvex!=j;p=p->ilink);for(p=G.xlist[i].firstout;p&&p->tlinkif(!p)returnERROR;//未找到->headvex!=m;p=p->tlink);p->ilink=p->ilink->ilink;if(p)}//在i链表中删除该边{if(G.adjmulist[j].firstedge->ivex==i)q=p->tlink;G.adjmulist[j].firstedge=G.adjmulist[jp->tlink=q->tlink;].firstedge->jlink;free(q);G.arcnum--;else}{}//elsefor(p=G.adjmulist[j].firstedge;p&&p-}//for>jlink->ivex!=i;p=p->jlink);for(i=m;ijlink;{p->jlink=q->jlink;G.xlist[i]=G.xlist[i+1];//修改表头向free(q);量}//在i链表中删除该边for(p=G.xlist[i].firstin;p;p=p->hlink)G.arcnum--;p->headvex--;returnOK;for(p=G.xlist[i].firstout;p;p=p->tlink)}//Delete_Arcp->tailvex--;//修改各链中的顶点序号7.19}G.vexnum--;StatusBuild_AdjMulist(AMLGraphreturnOK;&G)//输入有向图的顶点数,边数,顶点}//Delete_Vex信息和边的信息建立邻接多重表{7.18InitAMLGraph(G);scanf("%d",&v);//为节省篇幅,本题只给出Delete_Arcif(v<0)returnERROR;//顶点数不能算法.其余算法请自行写出.为负G.vexnum=v;StatusDelete_Arc(AMLGraph&G,charscanf(%d",&a);v,charw)////在邻接多重表表示的图G 课后答案网www.khdaw.comif(a<0)returnERROR;//边数不能为}负if(r->jvex==j)r->jlink=p;G.arcnum=a;elser->ilink=p;for(m=0;mivex=i;p->jvex=j;for(y=0;yilink=NULL;p->jlink=NULL;//边if(G.arcs[x][y])结点赋初值{if(!G.adjmulist[i].firstedge)for(z=0;zivex==i)q=q->ilink;7.21elseq=q->jlink;}intPass_ALGraph(ALGraphG)//判断if(r->ivex==i)r->ilink=p;//注意i值一个邻接表存储的有向图是不是可传既可能出现在边结点的ivex域中,递的,是则返回1,否则返回0elser->jlink=p;//又可能出现在边{结点的jvex域中for(x=0;xneif(!G.adjmulist[j].firstedge)xtarc)G.adjmulist[j].firstedge=p;{elsey=p->adjvex;{for(q=G.vertices[y].firstarc;q;q=q->nq=G.adjmulist[i].firstedge;extarc)while(q){{z=q->adjvex;r=q;if(z!=x&&!is_adj(G,x,z))return0;if(q->jvex==j)q=q->jlink;}//forelseq=q->ilnk; 课后答案网www.khdaw.com}//forInitQueue(Q);}//Pass_ALGraphEnQueue(Q,i);while(!QueueEmpty(Q))intis_adj(ALGraphG,intm,intn)//判断{有向图G中是否存在边(m,n),是则返回DeQueue(Q,u);1,否则返回0visited[u]=1;{for(p=G.vertices[i].firstarc;p;p=p->nefor(p=G.vertices[m].firstarc;p;p=p->nextarc)xtarc){if(p->adjvex==n)return1;k=p->adjvex;return0;if(k==j)return1;}//is_adjif(!visited[k])EnQueue(Q,k);}//for7.22}//whilereturn0;intvisited[MAXSIZE];//指示顶点是否}//exist_path_BFS在当前路径上7.24intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到voidSTraverse_Nonrecursive(Graph顶点j是否有路径,是则返回1,否则返G)//非递归遍历强连通图G回0{{intvisited[MAXSIZE];if(i==j)return1;//i就是jInitStack(S);elsePush(S,GetVex(S,1));//将第一个顶点{入栈visited[i]=1;visit(1);for(p=G.vertices[i].firstarc;p;p=p->nevisited=1;xtarc)while(!StackEmpty(S)){{k=p->adjvex;while(Gettop(S,i)&&i)if(!visited[k]&&exist_path(k,j)){return1;//i下游的顶点到j有路径j=FirstAdjVex(G,i);}//forif(j&&!visited[j])}//else{}//exist_path_DFSvisit(j);visited[j]=1;7.23Push(S,j);//向左走到尽头}intexist_path_BFS(ALGraphG,inti,int}//whilej)//广度优先判断有向图G中顶点i到if(!StackEmpty(S))顶点j是否有路径,是则返回1,否则返{回0Pop(S,j);{Gettop(S,i);intvisited[MAXSIZE]; 课后答案网www.khdaw.comk=NextAdjVex(G,i,j);//向右走一步}//forif(k&&!visited[k])}//while{if(count0){{intvisited[i]=1;new[MAXSIZE],indegree[MAXSIZE];for(p=G.vertices[i].firstarc;p;p=p->ne//储存结点的新序号xtarc)n=G.vexnum;{FindInDegree(G,indegree);l=p->adjvex;InitStack(S);if(!visited[l])for(i=1;inextarc)intpath[MAXSIZE],visited[MAXSIZE];{//暂存遍历过程中的路径k=p->adjvex;if(!(--indegree[k]))Push(S,k); 课后答案网www.khdaw.comintFind_All_Path(ALGraphG,intu,intvisited[i]=1;v,intk)//求有向图G中顶点u到v之间for(p=G.vertices[i].firstarc;p;p=p->ne的所有简单路径,k表示当前路径长度xtarc){{path[k]=u;//加入当前路径中l=p->adjvex;visited[u]=1;if(!visited[l])if(u==v)//找到了一条简单路径sum+=GetPathNum_Len(G,l,j,len-{1)//剩余路径长度减一printf("Foundonepath!n");}//forfor(i=0;path[i];i++)visited[i]=0;//本题允许曾经被访问printf("%d",path[i]);//打印输出过的结点出现在另一条路径中}}//elseelsereturnsum;for(p=G.vertices[u].firstarc;p;p=p->ne}//GetPathNum_Lenxtarc){7.30l=p->adjvex;if(!visited[l])intvisited[MAXSIZE];Find_All_Path(G,l,v,k+1);//继续寻找intpath[MAXSIZE];//暂存当前路径}intcycles[MAXSIZE][MAXSIZE];//储visited[u]=0;存发现的回路所包含的结点path[k]=0;//回溯intthiscycle[MAXSIZE];//储存当前发}//Find_All_Path现的一个回路intcycount=0;//已发现的回路个数main(){voidGetAllCycle(ALGraphG)//求有向...图中所有的简单回路Find_All_Path(G,u,v,0);//在主函数中{初次调用,k值应为0for(v=0;vnexelseif(len>0)tarc){{sum=0;//sum表示通过本结点的路w=p->adjvex;径数if(!visited[w])DFS(G,w,k+1); 课后答案网www.khdaw.comelse//发现了一条回路thiscycle比较{return1;//完全相等for(i=0;path[i]!=w;i++);//找到回路for(m=0;m=0;i--)//第二次逆k,CSTree&T)//从顶点k出发,构造邻接向的深度优先遍历表结构的有向图G的最小生成森林T,{用孩子兄弟链表存储v=finished(i);{if(!visited[v])for(j=0;jn}//forextarc)}//Get_SGraphif(p->adjvex==k)closedge[j].lowcost=p->cost;voidDFS1(OLGraphG,intv)//第一次}//if深度优先遍历的算法closedge[k].lowcost=0;{for(i=1;itlink)k=minimum(closedge);{if(closedge[k].lowcostheadvex;{if(!visited[w])DFS1(G,w);Addto_Forest(T,closedge[k].adjvex,}//fork);//把这条边加入生成森林中finished[++count]=v;//在第一次遍历closedge[k].lowcost=0;中建立finished数组for(p=G.vertices[k].firstarc;p;p=p->n}//DFS1extarc)if(p->costadjvex].lovoidDFS2(OLGraphG,intv)//第二次wcost)逆向的深度优先遍历的算法closedge[p->adjvex]={k,p->cost};{}//ifvisited[v]=1;elseForest_Prim(G,k);//对另外一个printf("%d",v);//在第二次遍历中输出连通分量执行算法结点序号}//forfor(p=G.xlist[v].firstin;p;p=p->hlink)}//Forest_Prim{w=p->tailvex;voidAddto_Forest(CSTree&T,inti,intif(!visited[w])DFS2(G,w);j)//把边(i,j)添加到孩子兄弟链表表示}//for的树T中}//DFS2{ 课后答案网www.khdaw.comp=Locate(T,i);//找到结点i对应的指typedefstruct{针p,过程略intvex;//结点序号q=(CSTNode*)malloc(sizeof(CSTNodintecno;//结点所属的e));连通分量号q->data=j;}VexInfo;if(!p)//起始顶点不属于森林中已有的VexInfovexs[MAXSIZE];//记录结点任何一棵树所属连通分量号的数组{p=(CSTNode*)malloc(sizeof(CSTNovoidInit_VexInfo(VexInfo&vexs[],intde));vexnum)//初始化p->data=i;{for(r=T;r->nextsib;r=r->nextsib);for(i=0;inextsib=p;vexs[i]={i,i};//初始状态:每一个结p->firstchild=q;点都属于不同的连通分量}//作为新树插入到最右侧}//Init_VexInfoelseif(!p->firstchild)//双亲还没有孩子intis_ec(VexInfovexs[],inti,intj)//判p->firstchild=q;//作为双亲的第一个断顶点i和顶点j是否属于同一个连通孩子分量else//双亲已经有了孩子{{if(vexs[i].ecno==vexs[j].ecno)return1;for(r=p->firstchild;r->nextsib;r=r->neelsereturn0;xtsib);}//is_ecr->nextsib=q;//作为双亲最后一个孩voidmerge_ec(VexInfo&vexs[],int子的兄弟ec1,intec2)//合并连通分量ec1和ec2}{}//Addto_Forestfor(i=0;vexs[i].vex;i++)main()if(vexs[i].ecno==ec2){vexs[i].ecno==ec1;...}//merge_ecT=(CSTNode*)malloc(sizeof(CSTNodvoidMinSpanTree_Kruscal(Graphe));//建立树根G,EdgeSetType&EdgeSet,CSTreeT->data=1;&T)//求图的最小生成树的克鲁斯卡尔Forest_Prim(G,1,T);算法...{}//mainInit_VexInfo(vexs,G.vexnum);分析:这个算法是在Prim算法的基础ecnum=G.vexnum;//连通分量个数上添加了非连通图支持和孩子兄弟链while(ecnum>1)表构建模块而得到的,其时间复杂度为{O(n^2).GetMinEdge(EdgeSet,u,v);//选出最7.33短边if(!is_ec(vexs,u,v))//u和v属于不同连通分量课后答案网www.khdaw.com{intindegree[MAXSIZE];//本算法就Addto_CSTree(T,u,v);//加入到生成是拓扑排序树中FindIndegree(G,indegree);merge_ec(vexs,vexs[u].ecno,vexs[v]Initstack(S);.ecno);//合并连通分量for(i=0;inevoidAddto_CSTree(CSTree&T,inti,intxtarc)j)//把边(i,j)添加到孩子兄弟链表表示{的树T中k=p->adjvex;{if(!(--indegree[k]))Push(S,k);p=Locate(T,i);//找到结点i对应的指}针p,过程略}//whileq=(CSTNode*)malloc(sizeof(CSTNodif(countdata=j;}//TopoSeqif(!p->firstchild)//双亲还没有孩子p->firstchild=q;//作为双亲的第一个7.35孩子else//双亲已经有了孩子intvisited[MAXSIZE];{for(r=p->firstchild;r->nextsib;r=r->nevoidGet_Root(ALGraphG)//求有向无xtsib);环图的根,如果有的话r->nextsib=q;//作为双亲最后一个孩{子的兄弟for(v=0;vnextarc)7.37{w=p->adjvex;intmaxlen,path[MAXSIZE];//数组pathif(!visited[w])DFS(G,w);用于存储当前路径}intmlp[MAXSIZE];//数组mlp用于存}//DFS储已发现的最长路径7.36voidGet_Longest_Path(ALGraphG)//求一个有向无环图中最长的路径voidFill_MPL(ALGraph&G)//为有向{无环图G添加MPL域maxlen=0;{FindIndegree(G,indegree);FindIndegree(G,indegree);for(i=0;imaxlen&&!G.vertices[i].firstarc){//新的最长路径max=0;{for(p=G.vertices[i].firstarc;p;p=p->nefor(j=0;j<=len;j++)mlp[j]=path[j];//xtarc)保存下来{maxlen=len;j=p->adjvex;}if(G.vertices[j].MPL==0)elsek=Get_MPL(G,j);{if(k>max)max=k;//求其直接后继for(p=G.vertices[i].firstarc;p;p=p->ne顶点MPL的最大者xtarc)}{G.vertices[i]=max+1;//再加一,就是j=p->adjvex;当前顶点的MPLif(!visited[j])DFS(G,j,len+1); 课后答案网www.khdaw.com}printf("%c",T->data);}//else}//PrintNiBoLan_Bitreepath[i]=0;visited[i]=0;7.40}//DFSintEvaluate_DAG(ALGraphG)//给有7.38向无环图表示的表达式求值{voidNiBoLan_DAG(ALGraphG)//输FindIndegree(G,indegree);出有向无环图形式表示的表达式的逆for(i=0;iadjvex);if(!G.vertices[i].firstarc)//c是原子v2=Evaluate_imp(G,p->nextarc->adjvprintf("%c",c);ex);else//子表达式return{calculate(v1,G.vertices[i].optr,v2);p=G.vertices[i].firstarc;}PrintNiBoLan_DAG(G,p->adjvex);}//Evaluate_impPrintNiBoLan_DAG(G,p->nexarc->a分析:本题中,邻接表的vertices向量的djvex);元素类型修改如下:printf("%c",c);struct{}enumtag{NUM,OPTR};}//PrintNiBoLan_DAGunion{intvalue;7.39charoptr;};voidPrintNiBoLan_Bitree(BitreeT)//在ArcNode*firstarc;二叉链表存储结构上重做上一题}Elemtype;{if(T->lchild)7.41PrintNiBoLan_Bitree(T->lchild);if(T->rchild)voidCritical_Path(ALGraphG)//利用深PrintNiBoLan_Bitree(T->rchild);度优先遍历求网的关键路径课后答案网www.khdaw.com{voidALGraph_DIJ(ALGraphG,intFindIndegree(G,indegree);v0,Pathmatrix&P,ShortestPathTablefor(i=0;inefor(i=0;i<=G.vexnum;i++)xtarc)if(vl[i]==ve[i])printf("%d",i);//打印D[p->adjvex]=*p->info;//给D数组输出关键路径赋初值}//Critical_Pathfor(v=0;vnextif(D[v]info;P[v][v]=1;if(ve[i]+dut>ve[p->adjvex])}ve[p->adjvex]=ve[i]+dut;}//forDFS1(G,p->adjvex);D[v0]=0;final[v0]=1;//初始化}for(i=1;inev=w;xtarc)min=D[w];{}DFS2(G,p->adjvex);final[v]=1;dut=*p->info;for(p=G.vertices[v].firstarc;p;p=p->neif(vl[p->adjvex]-dutadjvex]-dut;{}w=p->adjvex;}//elseif(!final[w]&&(min+(*p->info)uplink;收空闲块pt=f+1;{s->size+=n+t->size;n=p->size;t->llink->rlink=t->rlink;f=p+n-1;//f指向空闲块底部t->rlink->llink=t->llink;if((p-1)->tag&&(f+1)->tag)//回收块(t+t->size-1)->uplink=s;上下邻块均为占用块}{}//Free_BT,该算法在课本里有详细的p->tag=0;f->tag=0;描述.f->uplink=p;if(!pav)8.14{p->llink=p;voidFree_BS(freelist&avail,charp->rlink=p;*addr,intn)//伙伴系统的空闲块回收算}法else{{buddy=addr%(2*n)?(addr-n):(addr+n);q=pav->llink;//求回收块的伙伴地址p->llink=q;p->rlink=pav;addr->tag=0;q->rlink=p;pav->llink=p;addr->kval=n;}for(i=0;avail[i].nodesizetag&&(f+1)->tag)//上闲块邻块为空闲块{{addr->llink=addr;q=(p-1)->uplink;addr->rlink=addr;q->size+=n;avail[i].first=addr;//作为唯一一个该f->uplink=q;大小的空闲块f->tag=0;}}elseelseif((p-1)->tag&&!(f+1)->tag)//下{邻块为空闲块for(p=avail[i].first;p!=buddy&&p!=av{ail[i].first;p=p->rlink);//寻找伙伴q=f+1;if(p==buddy)//伙伴为空闲块,此时s=q->llink;t=q->rlink;进行合并p->llink=s;p->rlink=t;{s->rlink=p;t->llink=p;if(p->rlink==p)p->size+=q->size;avail[i].first=NULL;//伙伴是此大小的(q+q->size-1)->uplink=p;唯一空闲块p->tag=0;else}{else//上下邻块均为空闲块p->llink->rlink=p->rlink;p->rlink->llink=p->llink; 课后答案网www.khdaw.com}//从空闲块链中删去伙伴q=MemStart;j=0;new=addr>p?p:addr;//合并后的新for(i=0;itag)Free_BS(avail,new,2*n);//递归地回{收新块s=H.list[i].length;}//ifp=H.list[i].stadr;else//伙伴为占用块,此时插入空闲for(k=0;krlink;H.list[j].length=s;//紧缩占用空间p->rlink=addr;addr->llink=p;表q->llink=addr;addr->rlink=q;j++;}}}//else}//Mem_Contract}//Free_BS8.15第九章查找FBList*MakeList(char*highbound,char*lowbound)//把堆结构存储的的所有空9.25闲块链接成可利用空间表,并返回表头指针intSearch_Sq(SSTableST,intkey)//在{有序表上顺序查找的算法,监视哨设在p=lowbound;高下标端while(p->tag&&p=highbound)returnNULL;//没有for(i=1;ST.elem[i].key>key;i++);空闲块if(i>ST.length||ST.elem[i].keytag)分析:本算法查找成功情况下的平均查{找长度为ST.length/2,不成功情况下为q->next=p;ST.length.q=p;}//if9.26p->next=NULL;intSearch_Bin_Recursive(SSTablereturnhead;//返回头指针ST,intkey,intlow,inthigh)//折半查找}//MakeList的递归算法8.16{if(low>high)return0;//查找不到时返voidMem_Contract(Heap&H)//对堆H回0执行存储紧缩mid=(low+high)/2;{if(ST.elem[mid].key==key)returnmid; 课后答案网www.khdaw.comelseif(ST.elem[mid].key>key)idx[MAXBLOCK];//每块起始位置和return最大元素,其中idx[0]不利用,其内容初Search_Bin_Recursive(ST,key,low,mid-始化为{0,0}以利于折半查找1);intblknum;//块的数目elsereturn}IdxSqList;//索引顺序Search_Bin_Recursive(ST,key,mid+1,hi表类型gh);}intSearch_IdxSeq(IdxSqListL,intkey)//}//Search_Bin_Recursive分块查找,用折半查找法确定记录所在块,块内采用顺序查找法9.27{if(key>L.idx[L.blknum].maxkey)intLocate_Bin(SSTableST,intkey)//折returnERROR;//超过最大元素半查找,返回小于或等于待查元素的最low=1;high=L.blknum;后一个结点号found=0;{while(low<=high&&!found)//折半查int*r;找记录所在块号midr=ST.elem;{if(key=r[ST.length].key)returnif(key<=L.idx[mid].maxkey&&key>ST.length;L.idx[mid-1].maxkey)low=1;high=ST.length;found=1;while(low<=high)elseif(key>L.idx[mid].maxkey){low=mid+1;mid=(low+high)/2;elsehigh=mid-1;if(key>=r[mid].key&&keydatadatanext;key)//在有序单循环链表存储结构上的L.sp=p;查找算法,假定每次查找都成功}{returnp;if(L.t->data==key)returnL.t;}//Search_DSListelseif(L.t->data>key)分析:本题的平均查找长度与上一题相for(p=L.h,i=1;p->data!=key;p=p->nex同,也是n/3.t,i++);else9.31for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);intlast=0,flag=1;L.t=p;//更新t指针returnp;intIs_BSTree(BitreeT)//判断二叉树T}//Search_CSList是否二叉排序树,是则返回1,否则返回分析:由于题目中假定每次查找都是成0功的,所以本算法中没有关于查找失败{的处理.由微积分可得,在等概率情况if(T->lchild&&flag)下,平均查找长度约为n/3.Is_BSTree(T->lchild);if(T->datadata;typedefstruct{if(T->rchild&&flag)DLNode*pre;Is_BSTree(T->rchild);intdata;returnflag;DLNode*next;}//Is_BSTree}DLNode;9.32typedefstruct{DLNode*sp;intlast=0;intlength;}DSList;//供查找的双向voidMaxLT_MinGT(BiTreeT,intx)//循环链表类型找到二叉排序树T中小于x的最大元素和大于x的最小元素DLNode*Search_DSList(DSList&L,int{key)//在有序双向循环链表存储结构上if(T->lchild)的查找算法,假定每次查找都成功MaxLT_MinGT(T->lchild,x);//本算法{仍是借助中序遍历来实现p=L.sp;if(lastdata>=x)//找到了小于if(p->data>key)x的最大元素{printf("a=%dn",last);while(p->data>key)p=p->pre;if(last<=x&&T->data>x)//找到了大于课后答案网www.khdaw.comx的最小元素while(!p->ltag)p=p->lchild;//找到最printf("b=%dn",T->data);小元素last=T->data;while(p&&p->datarchild){MaxLT_MinGT(T->rchild,x);if(p->data>a)printf("%dn",p->data);}//MaxLT_MinGT//输出符合条件的元素if(p->rtag)p=p->rtag;9.33else{voidPrint_NLT(BiTreeT,intx)//从大到p=p->rchild;小输出二叉排序树T中所有不小于xwhile(!p->ltag)p=p->lchild;的元素}//转到中序后继{}//whileif(T->rchild)Print_NLT(T->rchild,x);}//Print_Betweenif(T->datadata);if(T->lchild)Print_NLT(T->lchild,x);voidBSTree_Insert_Key(BiThrTree//先右后左的中序遍历&T,intx)//在后继线索二叉排序树T中}//Print_NLT插入元素x{9.34if(T->datartag)//T没有右子树时,作为右除二叉排序树T中所有不小于x元素孩子插入结点,并释放空间{{p=T->rchild;if(T->rchild)Delete_NLT(T->rchild,x);q=(BiThrNode*)malloc(sizeof(BiThif(T->datadata=x;q=T;T->rchild=q;T->rtag=0;T=T->lchild;q->rtag=1;q->rchild=p;//修改原线free(q);//如果树根不小于x,则删除树索根,并以左子树的根作为新的树根}if(T)Delete_NLT(T,x);//继续在左子else树中执行算法BSTree_Insert_Key(T->rchild,x);//T有}//Delete_NLT右子树时,插入右子树中}//if9.35elseif(T->data>x)//插入到左子树中{voidPrint_Between(BiThrTreeT,intif(!T->lchild)//T没有左子树时,作为a,intb)//打印输出后继线索二叉排序树左孩子插入T中所有大于a且小于b的元素{{q=(BiThrNode*)malloc(sizeof(BiThp=T;rNode)); 课后答案网www.khdaw.comq->data=x;Delete_BSTree(ptr);//删除x结点T->lchild=q;if(pre&&pre->rtag)q->rtag=1;q->rchild=T;//修改自身pre->rchild=suc;//修改线索的线索returnOK;}}//BSTree_Delete_keyelseBSTree_Insert_Key(T->lchild,x);//T有voidDelete_BSTree(BiThrTree&T)//课左子树时,插入左子树中本上给出的删除二叉排序树的子树T}//if的算法,按照线索二叉树的结构作了一}//BSTree_Insert_Key些改动{9.37q=T;if(!T->ltag&&T->rtag)//结点无右子StatusBSTree_Delete_key(BiThrTree树,此时只需重接其左子树&T,intx)//在后继线索二叉排序树T中T=T->lchild;删除元素xelseif(T->ltag&&!T->rtag)//结点无左{子树,此时只需重接其右子树BTNode*pre,*ptr,*suc;//ptr为x所在T=T->rchild;结点,pre和suc分别指向ptr的前驱和elseif(!T->ltag&&!T->rtag)//结点既后继有左子树又有右子树p=T;last=NULL;//last始终指向当前{结点p的前一个(前驱)p=T;r=T->lchild;while(!p->ltag)p=p->lchild;//找到中while(!r->rtag)序起始元素{while(p)s=r;{r=r->rchild;//找到结点的前驱r和rif(p->data==x)//找到了元素x结点的双亲s{}pre=last;T->data=r->data;//用r代替T结点ptr=p;if(s!=T)}s->rchild=r->lchild;elseif(last&&last->data==x)suc=p;//elses->lchild=r->lchild;//重接r的左找到了x的后继子树到其双亲结点上if(p->rtag)p=p->rtag;q=r;else}//else{free(q);//删除结点p=p->rchild;}//Delete_BSTreewhile(!p->ltag)p=p->lchild;分析:本算法采用了先求出x结点的前}//转到中序后继驱和后继,再删除x结点的办法,这样修last=p;改线索时会比较简单,直接让前驱的线}//while//借助中序遍历找到元素x及索指向后继就行了.如果试图在删除x其前驱和后继结点结点的同时修改线索,则问题反而复杂if(!ptr)returnERROR;//未找到待删化了.结点9.38 课后答案网www.khdaw.comvoidBSTree_Merge(BiTree&T,BiTreeif(T->lchild)&S)//把二叉排序树S合并到T中BSTree_Split(T->lchild,A,B,x);{if(T->rchild)if(S->lchild)BSTree_Split(T->rchild,A,B,x);//分裂BSTree_Merge(T,S->lchild);左右子树if(S->rchild)if(T->data<=x)Insert_Node(A,T);BSTree_Merge(T,S->rchild);//合并子elseInsert_Node(B,T);//将元素结点树插入合适的树中Insert_Key(T,S);//插入元素}//BSTree_Split}//BSTree_MergevoidInsert_Node(Bitree&T,BTNodevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置*S)//把树结点S插入到T的合适位置上上{{if(!T)T=S;//考虑到刚开始分裂时树if(S->data>T->data)A和树B为空的情况{elseif(S->data>T->data)//其余部分与if(!T->rchild)T->rchild=S;上一题同elseInsert_Node(T->rchild,S);{}if(!T->rchild)T->rchild=S;elseif(S->datadata)elseInsert_Node(T->rchild,S);{}if(!T->lchild)T->lchild=S;elseif(S->datadata)elseInsert_Node(T->lchild,S);{}if(!T->lchild)T->lchild=S;S->lchild=NULL;//插入的新结点必elseInsert_Node(T->lchild,S);须和原来的左右子树断绝关系}S->rchild=NULL;//否则会导致树结S->lchild=NULL;构的混乱S->rchild=NULL;}//Insert_Node}//Insert_Key分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任9.40何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把typedefstruct{一棵树中的元素逐个连接到另一棵树intdata;上,否则将会导致树的结构的混乱.intbf;intlsize;//lsize域表示9.39该结点的左子树的结点总数加1BlcNode*lchild,*rchild;voidBSTree_Split(BiTree&T,BiTree}BlcNode,*BlcTree;//含&A,BiTree&B,intx)//把二叉排序树Tlsize域的平衡二叉排序树类型分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部BTNode*Locate_BlcTree(BlcTreeT,int大于xk)//在含lsize域的平衡二叉排序树T中{确定第k小的结点指针课后答案网www.khdaw.com{p=T;if(!T)returnNULL;//k小于1或大于while(p.tag==BRANCH)//沿分支向树结点总数下查找if(T->lsize==k)returnT;//就是这个结{点for(i=0;ikeynum&&key>p->key[elseif(T->lsize>k)i];i++);//确定关键字所在子树returnLocate_BlcTree(T->lchild,k);//if(i==p->keynum)returnERROR;//在左子树中寻找关键字太大elsereturnp=p->child[i];Locate_BlcTree(T->rchild,k-T->lsize);}//在右子树中寻找,注意要修改k的值for(i=0;ikeynum&&key!=p->key[}//Locate_BlcTreei];i++);//在叶子结点中查找if(i==p->keynum)returnERROR;//找9.41不到关键字ptr=p;pos=i;typedefstruct{returnOK;enum{LEAF,BRANCH}}//BPTree_Searchtag;//结点类型标识intkeynum;9.42BPLinkparent;//双亲指针voidTrieTree_Insert_Key(TrieTreeintkey[MAXCHILD];//&T,StringTypekey)//在Trie树T中插关键字入字符串key,StringType的结构见第union{四章BPLink{child[MAXCHILD];//非叶结点的q=(TrieNode*)malloc(sizeof(TrieNode孩子指针));struct{q->kind=LEAF;rectypeq->lf.k=key;//建叶子结点*info[MAXCHILD];//叶子结点的klen=key[0];信息指针p=T;i=1;BPNode*next;while(p&&i<=klen&&p->bh.ptr[ord(k//指向下一个叶子结点的链接ey[i])])}leaf;{}last=p;}p=p->bh.ptr[ord(key[i])];BPNode,*BPLink,*BPTree;//B+树i++;及其结点类型}//自上而下查找if(p->kind==BRANCH)//如果最后落StatusBPTree_Search(BPTreeT,int到分支结点(无同义词):key,BPNode*ptr,intpos)//B+树中按关{键字随机查找的算法,返回包含关键字p->bh.ptr[ord(key[i])]=q;//直接连上的叶子结点的指针ptr以及关键字在叶叶子子结点中的位置posp->bh.num++;{} 课后答案网www.khdaw.comelse//如果最后落到叶子结点(有同义elsereturnERROR;//没找到待删除元词):素{}//TrieTree_Delete_Keyr=(TrieNode*)malloc(sizeof(TrieNode));//建立新的分支结点9.44last->bh.ptr[ord(key[i-1])]=r;//用新分支结点取代老叶子结点和上一层的voidPrint_Hash(HashTableH)//按第一联系个字母顺序输出Hash表中的所有关键r->kind=BRANCH;r->bh.num=2;字,其中处理冲突采用线性探测开放定r->bh.ptr[ord(key[i])]=q;址法r->bh.ptr[ord(p->lf.k[i])]=p;//新分支{结点与新老两个叶子结点相连for(i=1;i<=26;i++)}for(j=i;H.elem[j].key;j=(j+1)%hashsiz}//TrieTree_Insert_Keye[sizeindex])//线性探测分析:当自上而下的查找结束时,存在if(H(H.elem[j].key)==i)两种情况.一种情况,树中没有待插入printf("%sn",H.elem[j]);关键字的同义词,此时只要新建一个叶}//Print_Hash子结点并连到分支结点上即可.另一种intH(char*s)//求Hash函数情况,有同义词,此时要把同义词的叶{子结点与树断开,在断开的部位新建一if(s)returns[0]-96;//求关键字第一个个下一层的分支结点,再把同义词和新字母的字母序号(小写)关键字的叶子结点连到新分支结点的elsereturn0;下一层.}//H9.439.45StatusTrieTree_Delete_Key(TrieTreetypedef*LNode[MAXSIZE]&T,StringTypekey)//在Trie树T中删CHashTable;//链地址Hash表类型除字符串key{StatusBuild_Hash(CHashTable&T,intp=T;i=1;m)//输入一组关键字,建立Hash表,表while(p&&p->kind==BRANCH&&i<长为m,用链地址法处理冲突.=key[0])//查找待删除元素{{if(m<1)returnERROR;last=p;T=malloc(m*sizeof(WORD));//建立p=p->bh.ptr[ord(key[i])];表头指针向量i++;for(i=0;ikind==LEAF&&p->lf.k=ke定Inputkey函数用于从键盘输入关键y)//找到了待删除元素字{{last->bh.ptr[ord(key[i-1])]=NULL;q=(LNode*)malloc(sizeof(LNode));free(p);q->data=key;q->next=NULL;returnOK;n=H(key);} 课后答案网www.khdaw.comif(!T[n])T[n]=q;//作为链表的第一序个结点if(L.r[i].key>L.r[i+1].key)else{{L.r[k+1].key=L.r[i].key;//监视哨for(p=T[n];p->next;p=p->next);for(j=i+1;L.r[j].key>L.r[i].key;++j)p->next=q;//插入链表尾部.本算法L.r[j-1].key=L.r[j].key;//前移不考虑排序问题.L.r[j-1].key=L.r[k+1].key;//插入}}}//while}//Insert_Sort1returnOK;}//Build_Hash10.249.46voidBiInsert_Sort(SqList&L)//二路插入排序的算法StatusLocate_Hash(HashTableH,int{row,intcol,KeyTypekey,int&k)//根据intd[MAXSIZE];//辅助存储行列值在Hash表表示的稀疏矩阵中确x=L.r.key;d=x;定元素key的位置kfirst=1;final=1;{for(i=2;i<=L.length;i++)h=2*(100*(row/10)+col/10);//作者设{计的Hash函数if(L.r[i].key>=x)//插入前部while(H.elem[h].key&&!EQ(H.elem[h{].key,key))for(j=final;d[j]>L.r[i].key;j--)h=(h+1)%20000;d[j+1]=d[j];if(EQ(H.elem[h].key,key))k=h;d[j+1]=L.r[i].key;elsek=NULL;final++;}//Locate_Hash}分析:本算法所使用的Hash表长20000,else//插入后部装填因子为50%,Hash函数为行数前两{位和列数前两位所组成的四位数再乘for(j=first;d[j]a[i+1])q=L.r[p].next;{if(p!=i)a[i]<->a[i+1];{change=1;L.r[p]<->L.r[i];}L.r[i].next=p;high--;//修改上界}for(i=high;i>low;i--)//从下向上起泡p=q;if(a[i]a[i-1];change=1;10.26}low++;//修改下界voidBubble_Sort1(inta[],intn)//对包}//while含n个元素的数组a进行改进的冒泡}//Bubble_Sort2排序{10.28change=n-1;//change指示上一趟冒泡中最后发生交换的元素voidBubble_Sort3(inta[],intn)//对上while(change)一题的算法进行化简,循环体中只包含{一次冒泡for(c=0,i=0;ia[i+1])intb[3];//b[0]为冒泡的下界,b[2]为{上界,b[1]无用a[i]<->a[i+1];d=1;b[0]=0;b[2]=n-1;//d为冒泡方向的标识,1为向上,-1为向下课后答案网www.khdaw.comchange=1;10.30while(b[0]0)//注意这个交上下界类型换条件{voidQSort_NotRecurve(intSQLista[i]<->a[i+d];&L)//快速排序的非递归算法change=1;{}low=1;high=L.length;b[1+d]-=d;//修改边界InitStack(S);//S的元素为boundary类d*=-1;//换个方向型}//whilewhile(low2)//如果当前子序列长度大于3且尚未排好序voidOE_Sort(inta[],intn)//奇偶交换{排序的算法pivot=Partition(L,low,high);//进行{一趟划分change=1;if(high-pivot>pivot-low)while(change){{Push(S,{pivot+1,high});//把长的change=0;子序列边界入栈for(i=1;ia[i+1])}{elsea[i]<->a[i+1];{change=1;Push(S,{low,pivot-1});}low=pivot+1;for(i=0;ia[i+1])elseif(lowa[i+1];序change=1;{}Easy_Sort(L,low,high);//直接进行}//while比较排序}//OE_Sortlow=high;//当前子序列标志为已分析:本算法的结束条件是连续两趟比排好序较无交换发生} 课后答案网www.khdaw.comelse//如果当前子序列已排好序但栈L.r[low]<->L.r[low+1];中还有未排序的子序列}{}//Easy_SortPop(S,a);//从栈中取出一个子序列low=a.low;10.31high=a.high;}voidDivide(inta[],intn)//把数组a中所}//while有值为负的记录调到非负的记录之前}//QSort_NotRecurve{low=0;high=n-1;intPartition(SQList&L,intlow,intwhile(low=0)L.r[0]=L.r[low];high--;//以0作为虚拟的枢轴记录pivotkey=L.r[low].key;a[low]<->a[high];while(lowa[high];while(low=pi}votkey)}//Dividehigh--;L.r[low]=L.r[high];10.32while(lowa[j];if(high-low==1)//子序列只含两个元i++;素j++;if(L.r[low].key>L.r[high].key)break;L.r[low]<->L.r[high];caseWHITE:else//子序列含有三个元素j++;{break;if(L.r[low].key>L.r[low+1].key)caseBLUE:L.r[low]<->L.r[low+1];a[j]<->a[k];if(L.r[low+1].key>L.r[high].key)k--;//这里没有j++;语句是为了防L.r[low+1]<->L.r[high];止交换后a[j]仍为蓝色的情况if(L.r[low].key>L.r[low+1].key) 课后答案网www.khdaw.com}if(H.r[j].key>H.r[k].key)}//Flag_ArrangeH.r[j]<->H.r[k];分析:这个算法中设立了三个指针.其j=k;中,j表示当前元素;i以前的元素全部为}红色;k以后的元素全部为蓝色.这样,就}//for可以根据j的颜色,把其交换到序列的}//Build_Heap前部或者后部.10.3510.33voidTriHeap_Sort(Heap&H)//利用三voidLinkedList_Select_Sort(LinkedList叉树形式的堆进行排序的算法&L)//单链表上的简单选择排序算法{{for(i=H.length/3;i>0;i--)for(p=L;p->next->next;p=p->next)Heap_Adjust(H,i,H.length);{for(i=H.length;i>1;i--)q=p->next;x=q->data;{for(r=q,s=q;r->next;r=r->next)//在qH.r[1]<->H.r[i];后面寻找元素值最小的结点Heap_Adjust(H,1,i-1);if(r->next->datanext->data;s=r;voidHeap_Adjust(Heap&H,ints,int}m)//顺序表H中,H.r[s+1]到H.r[m]已经if(s!=q)//找到了值比q->data更小的是堆,把H.r[s]插入并调整成堆最小结点s->next{{rc=H.r[s];p->next=s->next;s->next=q;for(j=3*s-1;j<=m;j=3*j-1)t=q->next;q->next=p->next->next;{p->next->next=t;if(jnext两个结点j++;}//forif(jnext,e2=p;p->next;p=e2){{for(l=1;lnext;i++,q=q段长->next);for(i=0;(2*i-1)*lnext;i++,q=q->ne{xt);start1=2*l*i;//求出待归并的两段e2=q;//求出两个待归并子序列的的上下界尾指针end1=start1+l-1;if(e1!=e2)start2=end1+1;LinkedList_Merge(L,p,e1,e2);//归并end2=(start2+l-1)>(n-1)?(n-1):(start2}+l-1);//注意end2可能超出边界}//LinkedList_Merge_Sort1Merge(a,start1,end1,start2,end2);//归并voidLinkedList_Merge(LinkedList}&L,LNode*p,LNode*e1,LNode*e2)//}//Merge_Sort对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从voidMerge(inta[],ints1,inte1,ints2,inte1->next到e2e2)//将有序子序列a[s1]到a[e1]和a[s2]{到a[e2]归并为有序序列a[s1]到a[e2]q=p->next;r=e1->next;//q和r为两个{子序列的起始位置intb[MAXSIZE];//设立辅助存储数while(q!=e1->next&&r!=e2->next)组b{for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)if(q->datadata)//选择关键字较{小的那个结点接在p的后面if(a[i]next=q;p=q;}q=q->next;while(i<=e1)b[k++]=a[i++];}while(j<=e2)b[k++]=a[j++];//归并到elseb中{for(i=s1;i<=e2;i++)//复制回去p->next=r;p=r;a[i]=b[i];r=r->next;}//Merge}}//while10.37while(q!=e1->next)//接上剩余部分{voidp->next=q;p=q;LinkedList_Merge_Sort1(LinkedListq=q->next;&L)//链表结构上的归并排序非递归算}法while(r!=e2->next){{for(l=1;lnext=r;p=r;while(q!=e1->next&&r!=e2->next)r=r->next;{}if(q->datadata)}//LinkedList_Merge{p->next=q;p=q;10.38q=q->next;}voidelseLinkedList_Merge_Sort2(LinkedList{&L)//初始归并段为最大有序子序列的p->next=r;p=r;归并排序,采用链表存储结构r=r->next;{}LNode*end[MAXSIZE];//设立一个}//while数组来存储各有序子序列的尾指针while(q!=e1->next)for(p=L->next->next,i=0;p;p=p->next){//求各有序子序列的尾指针p->next=q;p=q;if(!p->next||p->data>p->next->data)q=q->next;end[i++]=p;}while(end[0]->next)//当不止一个子while(r!=e2->next)序列时进行两两归并{{p->next=r;p=r;j=0;k=0;//j:当前子序列尾指针存储r=r->next;位置;k:归并后的子序列尾指针存储位}置}//LinkedList_Merge,与上一题完全相for(p=L->next,e2=p;p->next;p=e2)//同两两归并所有子序列{10.39e1=end[j];e2=end[j+1];//确定两个子序列voidSL_Merge(inta[],intl1,intl2)//把if(e1->next)长度分别为l1,l2且l1^2<(l1+l2)的两个LinkedList_Merge(L,p,e1,e2);//归并有序子序列归并为有序序列end[k++]=e2;//用新序列的尾指针{取代原来的尾指针start1=0;start2=l1;//分别表示序列1j+=2;//转到后面两个子序列和序列2的剩余未归并部分的起始位}置}//whilefor(i=0;inext到e1,第二个是从RSh(a,start1,j-1,k);//将a[start1]到e1->next到e2a[j-1]之间的子序列循环右移k位{start1+=k+1;q=p->next;r=e1->next; 课后答案网www.khdaw.comstart2=j;//修改两序列尚未归并部分for(i=0;i<1000;i++)//直接按关键字散的起始位置列}{}//SL_Mergefor(j=a[i];b[j];j=(j+1)%10000);b[j]=a[i];voidRSh(inta[],intstart,intend,intk)//}将a[start]到a[end]之间的子序列循环for(i=0,j=0;i<1000;j++)//将散列收回右移k位,算法原理参见5.18a中{if(b[j])len=end-start+1;{for(i=1;i<=k;i++)for(x=b[j],k=j;b[k];k=(k+1)%10000)if(len%i==0&&k%i==0)p=i;//求lenif(b[k]==x)和k的最大公约数p{for(i=0;ia[i])b[i].gt++;elseif(a[j]a[min];//与第i个记录交换{c[min]=INFINITY;//修改该记录的cfor(i=0;i1&&change;i--)//对影子序列执行冒泡排序{change=0;for(j=0;jd[j+1].key){d[j]<->d[j+1];change=1;}}//forfor(i=0;i

数据结构习题集 (严蔚敏著) 课后答案(完整版).pdf 79页