广工数据结构作业系统-第1-10章答案

◆2.11②设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现以下函数：voidInsertOrderList(SqList&L,ElemTypex)/*在有序的顺序表L中保序插入数据元素x*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInsertOrderList(SqList&L,ElemTypex)//在有序的顺序表L中保序插入数据元素x{inti=0,j;while(L.elem[i]<x&&i<L.length)i++;for(j=L.length;j>i;j--){L.elem[j]=L.elem[j-1];}L.elem[i]=x;L.length+=1;}◆2.12③设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表〔例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，那么两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为A'=(x,z)和B'=(y,x,x,z)〕。假设A'=B'=空表，那么A=B；假设A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，那么A<B；否那么A>B。试写一个比较A和B大小的算法。〔注意：在算法中，不要破坏原表A和B，也不一定先求得A'和B'才进行比拟〕。要求实现以下函数：charCompare(SqListA,SqListB);/*比拟顺序表A和B,*//*返回'<',假设A<B;*//*'=',假设A=B;*//*'>',假设A>B*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;charCompare(SqListA,SqListB)//比拟顺序表A和B,//返回'<',假设A<B;//'=',假设A=B;//'>',假设A>B{inti=0;while(A.elem[i]==B.elem[i]&&i<A.length&&i<B.length)i++;if(i==A.length&&i==B.length)return'=';elseif(A.elem[i]<B.elem[i]||i==A.length)return'<';elseif(A.elem[i]>B.elem[i]||i==B.length)return'>';}2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现以下函数：LinkListLocate(LinkListL,ElemTypex);//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerpointingnode'x',//otherwisereturn'NULL'单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerhapointingnode'x',//otherwisereturn'NULL'{LinkListp;inti=0;p=L->next;while(p->data!=x&&p!=NULL){i++;p=p->next;}returnp;}2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现以下函数：intLength(LinkListL);//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intLength(LinkListL)//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'{LinkListp;inti=0;p=L->next;while(p!=NULL){i++;p=p->next;}returni;}2.17②试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比拟。实现以下函数：voidInsert(LinkList&L,inti,ElemTypeb);单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidInsert(LinkList&L,inti,ElemTypeb){LinkListp,q;intj=2;p=L;while(j<i){j++;p=p->next;}if(i!=0&&i!=1){q=(LinkList)malloc(sizeof(LNode));q->data=b;q->next=p->next;p->next=q;}if(i==1){q=(LinkList)malloc(sizeof(LNode));q->data=b;q->next=p;L=q;}}2.18②同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。实现以下函数：voidDelete(LinkList&L,inti);单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidDelete(LinkList&L,inti){LinkListp,q;intj=2;p=L;while(j<i&&p!=NULL){j++;p=p->next;}if(i!=0&&i!=1){q=p->next;p->next=q->next;free(q);}if(i==1){q=L;L=L->next;free(q);}}2.20②同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)同时释放被删结点空间，并分析你的算法的时间复杂度。实现以下函数：voidPurge(LinkList&L);单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidPurge(LinkList&L){LinkListp,q;inti=0;p=L;while(p!=NULL&&p->next!=NULL){if(p->data==p->next->data){q=p->next;p->next=q->next;free(q);}elsep=p->next;}}◆2.21③试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。实现以下函数：voidInverse(SqList&L);顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInverse(SqList&L){inti=0,j=0;i=L.length/2;for(j=0;j<i;j++){ElemTypee=L.elem[j];L.elem[j]=L.elem[L.length-j-1];L.elem[L.length-j-1]=e;}}◆2.22③试写一算法，对单链表实现就地逆置。实现以下函数：voidInverse(LinkList&L);/*对带头结点的单链表L实现就地逆置*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidInverse(LinkList&L)/*对带头结点的单链表L实现就地逆置*/{LinkListp,q,k;q=p=L->next;while(p->next!=NULL){k=q;q=p->next;p->next=q->next;q->next=k;}L->next=q;}2.23③设线性表A=(a1,...,am),B=(b1,...,bn)，试写一个按以下规那么合并A、B为线性表C的算法，即使得C=(a1,b1,...,am,bm,bm+1,...,bn)当m≤n时；或者C=(a1,b1,...,an,bn,an+1,...,am)当m＞n时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。实现以下函数：voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依题意，合并带头结点的单链表ha和hb为hc*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依题意，合并带头结点的单链表ha和hb为hc*/{LinkListp,q,k,r;p=ha->next;q=hb->next;if(p==NULL)hc=hb;elseif(q==NULL)hc=ha;else{while(p->next!=NULL&&q->next!=NULL){k=p->next;r=q->next;p->next=q;p=k;q->next=p;q=r;}if(p->next!=NULL)q->next=p->next;p->next=q;hc=ha;}}◆2.24④假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序〔即非递增有序，允许表中含有值相同的元素〕排列的线性表C，并要求利用原表〔即A表和B表〕的结点空间构造C表。实现以下函数：voidUnion(LinkList&lc,LinkListla,LinkListlb);/*依题意，利用la和lb原表的结点空间构造lc表*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidUnion(LinkList&lc,LinkListla,LinkListlb){LinkListpa=la->next;LinkListpb=lb->next;LinkListpre=NULL;LinkListq,pc;while(pa||pb){if((pa->data<pb->data&&pa!=NULL)||pb==NULL){pc=pa;q=pa->next;pa->next=pre;pa=q;}else{pc=pb;q=pb->next;pb->next=pre;pb=q;}pre=pc;printf("%s","done");}lc=la;la->next=pc;//构造新表头/*LinkListpa=la->next;LinkListpb=lb->next;LinkListpc=la;lc=la;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(lb);//将c实现就地逆置'LinkListp,q;p=lc->next;while(p->next){q=p->next;p->next=p->next->next;q->next=lc->next;lc->next=q;}*/}2.31②假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。实现以下函数：ElemTypeDeleteNode(LinkLists);/*删除指针s所指结点的前驱结点，并返回被删结点的元素值*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;ElemTypeDeleteNode(LinkLists)/*删除指针s所指结点的前驱结点，并返回被删结点的元素值*/{LinkListp;p=s->next;while(p->next->next!=s)p=p->next;ElemTypee=p->next->data;p->next=s;returne;}2.32②有一个单向循环链表，其每个结点中含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。实现以下函数：voidPerfectBiLink(BiLinkList&CL);双向循环链表类型定义如下：typedefstructBiNode{ElemTypedata;intfreq;//2.38题用structBiNode*prev,*next;}BiNode,*BiLinkList;voidPerfectBiLink(BiLinkList&CL){BiLinkListp,q,k;k=p=q=CL;while(p->next!=q){p=p->next;p->prev=k;k=p;}q->prev=p;}◆2.33③由一个线性链表表示的线性表中含有三类字符的数据元素〔如：字母字符、数字字符和其它字符〕，试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。实现以下函数：voidSplit(LinkList&lc,LinkList&ld,LinkList&lo,LinkListll);单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidSplit(LinkList&A,LinkList&B,LinkList&C,LinkListL){LinkLists,p,q,r;s=L->next;A=(LinkList)malloc(sizeof(LNode));p=A;B=(LinkList)malloc(sizeof(LNode));q=B;C=(LinkList)malloc(sizeof(LNode));r=C;//建立头结点while(s){if((s->data>='a'&&s->data<='z')||(s->data<='Z'&&s->data>='A')){p->next=s;p=s;}elseif(s->data>='0'&&s->data<='9'){q->next=s;q=s;}else{r->next=s;r=s;}s=s->next;}//whilep->next=A;q->next=B;r->next=C;//完成循环链表}2.37④设以带头结点的双向循环链表表示的线性表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。实现以下函数：voidReverseEven(BiLinkList&L);双向循环链表类型定义如下：typedefstructBiNode{ElemTypedata;intfreq;//2.38题用structBiNode*prev,*next;}BiNode,*BiLinkList;voidReverseEven(BiLinkList&L){BiLinkListp=NULL;p=L->next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}//此时p指向最后一个奇数结点if(p->next==L)p->next=L->prev->prev;elsep->next=L->prev;p=p->next;//此时p指向最后一个偶数结点while(p->prev->prev!=L){p->next=p->prev->prev;p=p->next;}if(p!=L)p->next=L;//按题目要求调整了next链的结构,此时pre链仍为原状for(p=L;p->next!=L;p=p->next)p->next->prev=p;L->prev=p;//调整pre链的结构,同2.32方法}◆2.39③试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法〔x0为给定值〕，并分析你的算法的时间复杂度。实现以下函数：floatEvaluate(SqPolypn,floatx);/*pn.data[i].coef存放ai，*//*pn.data[i].exp存放ei(i=1,2,...,m)*//*本算法计算并返回多项式的值。不判别溢出。*//*入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/多项式的顺序存储结构:typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{PolyTerm*data;intlength;}SqPoly;floatf(floatx,intj){inti;floats=1;for(i=0;i<j;++i){s*=x;}returns;}floatEvaluate(SqPolypn,floatx)/*pn.data[i].coef存放ai，*//*pn.data[i].exp存放ei(i=1,2,...,m)*//*本算法计算并返回多项式的值。不判别溢出。*//*入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/{inti;floats=0;for(i=0;i<pn.length;++i){s+=pn.data[i].coef*f(x,pn.data[i].exp);}returns;}◆2.41②试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数〔多项式〕，同时释放所有无用〔被删〕结点。实现以下函数：voidDifference(LinkedPoly&pa);/*稀疏多项式pa以循环链表作存储结构，*//*将此链表修改成它的导函数，并释放无用结点*/链式多项式的类型定义：typedefstructPolyNode{intcoef;intexp;structPolyNode*next;}PolyNode,*PolyLink;//多项式元素〔项〕结点类型typedefPolyLinkLinkedPoly;//链式多项式voidDifference(LinkedPoly&pa)/*稀疏多项式pa以循环链表作存储结构，*//*将此链表修改成它的导函数，并释放无用结点*/{LinkedPolyp,t;t=pa->next;if(t->exp==0){free(t);pa->next=pa->next->next;}p=pa->next;while(p!=pa){p->coef*=p->exp;p->exp--;//if(p->next->exp==0)p->next=p->next->next;p=p->next;}}◆3.17③试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而'1+3&3-1'那么不是。实现以下函数:Statusmatch(char*str);/*假设str是属该模式的字符序列，*//*那么返回TRUE，否那么返回FALSE*/Stack是一个已实现的栈。可使用的相关类型和函数：typedefcharSElemType;//栈Stack的元素类型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);StatusGetTop(Stacks,SElemType&e);Statusmatch(char*str)/*假设str是属该模式的字符序列，*//*那么返回TRUE，否那么返回FALSE*/{Stacks;SElemTypee;InitStack(s);while(*str!='&'){Push(s,*str);str++;}str++;while(*str!='@'){if(StackEmpty(s))returnFALSE;Pop(s,e);if(*str!=e)returnFALSE;str++;}if(!StackEmpty(s))returnFALSE;elsereturnTRUE;}3.18②试写一个判别表达式中开、闭括号是否配对出现的算法。实现以下函数：StatusMatchCheck(SqListexp);/*顺序表exp表示表达式；*//*假设exp中的括号配对，那么返回TRUE，否那么返回FALSE*//*注：本函数不使用栈*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//顺序表StatusMatchCheck(SqListexp)/*顺序表exp表示表达式；*//*假设exp中的括号配对，那么返回TRUE，否那么返回FALSE*//*注：本函数不使用栈*/{inti,j=0;for(i=0;i<exp.length;i++){if(exp.elem[i]=='(')j++;elseif(exp.elem[i]==')'&&j==0)returnFALSE;elsej--;}if(j==0)returnTRUE;elsereturnFALSE;}◆3.19④假设一个算术表达式中可以包含三种括号：圆括号"("和")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的次序嵌套使用〔如：…[…{…}…[…]…]…[…]…(…)…〕。编写判别给定表达式中所含括号是否正确配对出现的算法(表达式已存入数据元素为字符的顺序表中)。实现以下函数：StatusMatchCheck(SqListexp);/*顺序表exp表示表达式；*//*假设exp中的括号配对，那么返回TRUE，否那么返回FALSE*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//顺序表Stack是一个已实现的栈。可使用的相关类型和函数：typedefcharSElemType;//栈Stack的元素类型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);StatusGetTop(Stacks,SElemType&e);StatusMatchCheck(SqListexp)/*顺序表exp表示表达式；*//*假设exp中的括号配对，那么返回TRUE，否那么返回FALSE*/{Stacks;inti;SElemTypee;InitStack(s);for(i=0;i<exp.length;i++){if(exp.elem[i]=='{'||exp.elem[i]=='['||exp.elem[i]=='(')Push(s,exp.elem[i]);elseif(exp.elem[i]=='}'||exp.elem[i]==']'||exp.elem[i]==')'){if(StackEmpty(s))returnFALSE;else{Pop(s,e);if(e=='{'&&exp.elem[i]!='}')returnFALSE;if(e=='['&&exp.elem[i]!=']')returnFALSE;if(e=='('&&exp.elem[i]!=')')returnFALSE;}}}if(StackEmpty(s))returnTRUE;elsereturnFALSE;}3.20③假设以二维数组g(1..m,1..n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。实现以下函数：voidChangeColor(GTYPEg,intm,intn,charc,inti0,intj0);/*在g[1..m][1..n]中，将元素g[i0][j0]*//*所在的同色区域的颜色置换为颜色c*/表示图像区域的类型定义如下：typedefcharGTYPE[m+1][n+1];Stack是一个已实现的栈。可使用的相关类型和函数：typedefintSElemType;//栈Stack的元素类型StatusStackInit(Stack&s,intinitsize);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);StatusGetTop(Stacks,SElemType&e);voidChangeColor(GTYPEg,intm,intn,charc,inti0,intj0)/*在g[1..m][1..n]中，将元素g[i0][j0]*//*所在的同色区域的颜色置换为颜色c*/{charcolor=g[i0][j0];g[i0][j0]=c;if(i0-1>=1&&g[i0-1][j0]==color)ChangeColor(g,m,n,c,i0-1,j0);if(j0-1>=1&&g[i0][j0-1]==color)ChangeColor(g,m,n,c,i0,j0-1);if(i0+1<=m&&g[i0+1][j0]==color)ChangeColor(g,m,n,c,i0+1,j0);if(j0+1<=n&&g[i0][j0+1]==color)ChangeColor(g,m,n,c,i0,j0+1);}◆3.21③假设表达式由单字母变量和双目四那么运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。实现以下函数：char*RPExpression(char*e);/*返回表达式e的逆波兰式*/Stack是一个已实现的栈。可使用的相关类型和函数：typedefcharSElemType;//栈Stack的元素类型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);SElemTypeTop(Stacks);char*RPExpression(char*e)/*返回表达式e的逆波兰式*/{char*a;chari=0,j=0,m;Stacks;InitStack(s);a=(char*)malloc(sizeof(char)*20);while(e[i]!=0){if(e[i]>='a'&&e[i]<='z'){a[j]=e[i];j++;}elseif(e[i]=='(')Push(s,e[i]);elseif(e[i]=='*'||e[i]=='/'){if(GetTop(s,m)==ERROR)Push(s,e[i]);elseif(m=='*'||m=='/'){Pop(s,m);a[j++]=m;Push(s,e[i]);}elsePush(s,e[i]);}elseif(e[i]=='+'||e[i]=='-'){if(GetTop(s,m)==ERROR)Push(s,e[i]);elseif(m=='+'||m=='-'){Pop(s,m);a[j++]=m;Push(s,e[i]);}elseif(m=='*'||m=='/'){Pop(s,m);a[j++]=m;if(GetTop(s,m)==ERROR)Push(s,e[i]);else{if(m=='+'||m=='-'){Pop(s,m);a[j++]=m;}Push(s,e[i]);}}elseif(m=='(')Push(s,e[i]);}elseif(e[i]==')'){Pop(s,m);while(m!='('){a[j++]=m;Pop(s,m);}}i++;}while(GetTop(s,m)!=ERROR){Pop(s,m);a[j++]=m;}returna;}3.24③试编写如下定义的递归函数的递归算法:g(m,n)=0当m=0,n>=0g(m,n)=g(m-1,2n)+n当m>0,n>=0并根据算法画出求g(5,2)时栈的变化过程。实现以下函数：intg(intm,intn);/*ifm<0orn<0thenreturn-1.*/intG(intm,intn)/*ifm<0orn<0thenreturn-1.*/{if(m<0||n<0)return-1;if(m==0&&n>=0)return0;elsereturnG(m-1,2*n)+n;}3.25④试写出求递归函数F(n)的递归算法，并消除递归：F(n)=n+1当n=0F(n)=nF(n/2)当n>0实现以下函数：intF(intn);/*ifn<0thenreturn-1.*/intF(intn)/*ifn<0thenreturn-1.*/{if(n<0)return-1;elseif(n==0)returnn+1;elsereturnn*F(n/2);}◆3.28②假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。实现以下函数：StatusInitCLQueue(CLQueue&rear);StatusEnCLQueue(CLQueue&rear,ElemTypex);StatusDeCLQueue(CLQueue&rear,ElemType&x);带头结点循环链队列CLQueue的类型为以下LinkList类型：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;typedefLinkListCLQueue;StatusInitCLQueue(CLQueue&rear){rear=(LinkList)malloc(sizeof(LNode));if(rear==NULL)exit(0);elserear->next=rear;returnOK;}StatusEnCLQueue(CLQueue&rear,ElemTypex){LinkListp;p=(LinkList)malloc(sizeof(LNode));if(p==NULL)exit(0);else{p->data=x;p->next=rear->next;rear->next=p;rear=p;}returnOK;}StatusDeCLQueue(CLQueue&rear,ElemType&x){LinkListp;if(rear==rear->next)returnERROR;p=rear->next->next;x=p->data;rear->next->next=p->next;free(p);returnOK;}3.29③如果希望循环队列中的元素都能得到利用，那么需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是"空"还是"满"。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围〔比方，当循环队列容量较小而队列中每个元素占的空间较多时，那一种方法较好？〕。实现以下函数：StatusEnCQueue(CTagQueue&Q,QElemTypex);StatusDeCQueue(CTagQueue&Q,QElemType&x);此题的循环队列CTagQueue的类型定义如下：typedefcharQElemType;typedefstruct{QElemTypeelem[MAXQSIZE];inttag;intfront;intrear;}CTagQueue;StatusEnCQueue(CTagQueue&Q,QElemTypex){if(Q.front==Q.rear&&Q.tag==1)returnERROR;else{Q.elem[Q.rear]=x;Q.rear=(Q.rear+1)%MAXQSIZE;}returnOK;}StatusDeCQueue(CTagQueue&Q,QElemType&x){if(Q.front==Q.rear&&Q.tag==0)returnERROR;else{x=Q.elem[Q.front];Q.front=(Q.front+1)%MAXQSIZE;}returnOK;}◆3.30②假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法〔在出队列的算法中要返回队头元素〕。实现以下函数：StatusEnCQueue(CLenQueue&Q,QElemTypex);StatusDeCQueue(CLenQueue&Q,QElemType&x);此题的循环队列CLenQueue的类型定义如下：typedefcharQElemType;typedefstruct{QElemTypeelem[MAXQSIZE];intlength;intrear;}CLenQueue;StatusEnCQueue(CLenQueue&Q,QElemTypex){if(Q.length==MAXQSIZE)returnERROR;else{Q.rear=(Q.rear+1)%MAXQSIZE;Q.elem[Q.rear]=x;Q.length+=1;}returnOK;}StatusDeCQueue(CLenQueue&Q,QElemType&x){if(Q.length==0)returnERROR;else{x=Q.elem[(MAXQSIZE-Q.length+Q.rear+1)%MAXQSIZE];Q.length--;}returnOK;}◆3.31③假设称正读和反读都相同的字符序列为"回文"，例如，'abba'和'abcba'是回文，'abcde'和'ababab'那么不是回文。试写一个算法判别读入的一个以'@'为结束符的字符序列是否是"回文"。实现以下函数：StatusPalindrome(char*word);/*利用栈和队列判定字符序列word是否是回文*/可使用栈Stack和队列Queue及其以下操作：StatusInitStack(Stack&S);StatusPush(Stack&S,ElemTypex);StatusPop(Stack&S,ElemType&x);StatusStackEmpty(StackS);StatusInitQueue(Queue&Q);StatusEnQueue(Queue&Q,ElemTypex);StatusDeQueue(Queue&Q,ElemType&x);StatusQueueEmpty(QueueQ);StatusPalindrome(char*word)/*利用栈和队列判定字符序列word是否是回文*/{StackS;QueueQ;charc1,c2;InitStack(S);InitQueue(Q);while(*word!='@'){Push(S,*word);EnQueue(Q,*word);word++;}while(!StackEmpty(S)&&!QueueEmpty(Q)){Pop(S,c1);DeQueue(Q,c2);if(c1!=c2)returnERROR;}returnOK;}4.10③编写对串求逆的递推算法。要求实现以下函数：voidReverse(StringType&s);/*Reversesbyiteration.*/StringType是串的一个抽象数据类型，它包含以下6种根本操作：voidInitStr(StringType&s);//初始化s为空串。voidStrAssign(StringType&t,StringTypes);//将s的值赋给t。s的实际参数是串变量。intStrCompare(StringTypes,StringTypet);//比拟s和t。假设s>t，返回值>0；假设s=t，返回值=0；假设s<t，返回值<0。intStrLength(StringTypes);//返回s中的元素个数，即该串的长度。StringTypeConcat(StringType&s,StringTypet);//返回由s和t联接而成的新串。StringTypeSubString(StringTypes,intstart,intlen);//当1<=start<=StrLength(s)且0<=len<=StrLength(s)-start+1时，//返回s中第start个字符起长度为len的子串，否那么返回空串。//注意,不要使用"s="的形式为StringType类型的变量赋值,//而要使用StrAssign函数!!!voidReverse(StringType&s)/*Reversesbyiteration.*/{StringTypet;intn,i;n=StrLength(s);InitStr(t);for(i=n;i>0;i--){Concat(t,SubString(s,i,1));}StrAssign(s,t);}4.12③编写一个实现串的置换操作Replace(&S,T,V)的算法。要求实现以下函数：voidReplace(StringType&S,StringTypeT,StringTypeV);/*以串v置换串s中出现的所有和串t相同的非空串*/StringType是串的一个抽象数据类型，它包含以下6种根本操作：voidInitStr(StringType&s);//初始化s为空串。voidStrAssign(StringType&t,StringTypes);//将s的值赋给t。s的实际参数是串变量。intStrCompare(StringTypes,StringTypet);//比拟s和t。假设s>t，返回值>0；假设s=t，返回值=0；假设s<t，返回值<0。intStrLength(StringTypes);//返回s中的元素个数，即该串的长度。StringTypeConcat(StringType&s,StringTypet);//返回由s和t联接而成的新串。StringTypeSubString(StringTypes,intstart,intlen);//当1<=start<=StrLength(s)且0<=len<=StrLength(s)-start+1时，//返回s中第start个字符起长度为len的子串，否那么返回空串。//注意,不要使用"s="的形式为StringType类型的变量赋值,//而要使用StrAssign函数!!!voidReplace(StringType&S,StringTypeT,StringTypeV)/*以串v置换串s中出现的所有和串t相同的非空串*/{inti,flag;StringTypestr1,str2,str3;InitStr(str1);InitStr(str2);InitStr(str3);for(i=1;i<=StrLength(S)-StrLength(T)+1;i++){str1=SubString(S,i,StrLength(T));flag=StrCompare(str1,T);if(flag==0){str2=SubString(S,1,i-1);str3=SubString(S,i+StrLength(T),StrLength(S)-i-StrLength(T)+1);StrAssign(S,str2);Concat(S,V);Concat(S,str3);i+=StrLength(V)-1;}}}4.13③编写算法，从串s中删除所有和串t相同的子串。要求实现以下函数：voidDelSubString(StringType&scrStr,StringTypesubStr);/*Removeallsubstringmatching'subStr'from'scrStr'.*/StringType是串的一个抽象数据类型，它包含以下6种根本操作：voidInitStr(StringType&s);//初始化s为空串。voidStrAssign(StringType&t,StringTypes);//将s的值赋给t。s的实际参数是串变量。intStrCompare(StringTypes,StringTypet);//比拟s和t。假设s>t，返回值>0；假设s=t，返回值=0；假设s<t，返回值<0。intStrLength(StringTypes);//返回s中的元素个数，即该串的长度。StringTypeConcat(StringType&s,StringTypet);//返回由s和t联接而成的新串。StringTypeSubString(StringTypes,intstart,intlen);//当1<=start<=StrLength(s)且0<=len<=StrLength(s)-start+1时，//返回s中第start个字符起长度为len的子串，否那么返回空串。//注意,不要使用"s="的形式为StringType类型的变量赋值,//而要使用StrAssign函数!!!voidDelSubString(StringType&scrStr,StringTypesubStr)/*Removeallsubstringmatching'subStr'from'scrStr'.*/{inti,flag;StringTypestr1,str2,str3;InitStr(str1);InitStr(str2);InitStr(str3);for(i=1;i<=StrLength(scrStr)-StrLength(subStr)+1;i++){str1=SubString(scrStr,i,StrLength(subStr));flag=StrCompare(str1,subStr);if(flag==0){str2=SubString(scrStr,1,i-1);str3=SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1);StrAssign(scrStr,str2);Concat(scrStr,str3);i--;}}}4.17③编写算法，实现串的根本操作Replace(&S,T,V)。要求采用教科书4.2.1节中所定义的定长顺序存储表示，但不允许调用串的根本操作。要求实现以下函数：StatusReplace(SString&s,SStringt,SStringv);/*用串v替换串s中所有和串t匹配的子串。*//*假设有与t匹配的子串被替换，那么返回TRUE；*//*否那么返回FALSE*/定长顺序串SString的类型定义：typedefunsignedcharSString[MAXSTRLEN+1];/*s[0]isthestring'slength*/StatusReplace(SString&s,SStringt,SStringv)/*用串v替换串s中所有和串t匹配的子串。*//*假设有与t匹配的子串被替换，那么返回TRUE；*//*否那么返回FALSE*/{inti=1,j=1;intk,c,flag=0;while(i<=s[0]){if(s[i]==t[j]){i++;j++;}else{i=i-j+2;j=1;}if(j>t[0]){if(v[0]>t[0]){for(k=s[0],c=v[0]-t[0];k>=i;k--)s[k+c]=s[k];}elseif(v[0]<t[0]){for(k=i,c=t[0]-v[0];k<=s[0];k++)s[k-c]=s[k];}for(k=i-j+1,c=1;c<=v[0];k++,c++)s[k]=v[c];s[0]=s[0]+v[0]-t[0];i=i-t[0]+v[0];j=1;flag=1;}}if(flag==1)returnTRUE;elsereturnFALSE;}4.20③编写算法，从串s中删除所有和串t相同的子串。要求实现以下函数：StatusDelSub(SString&s,SStringt);/*从串s中删除所有和串t匹配的子串。*//*假设有与t匹配的子串被删除，那么返回TRUE；*//*否那么返回FALSE*/定长顺序串SString的类型定义：typedefunsignedcharSString[MAXSTRLEN+1];/*s[0]isthestring'slength*/StatusDelSub(SString&s,SStringt)/*从串s中删除所有和串t匹配的子串。*//*假设有与t匹配的子串被删除，那么返回TRUE；*//*否那么返回FALSE*/{inti=1,j=1;intk,c,flag=0;while(i<=s[0]){if(s[i]==t[j]){i++;j++;}else{i=i-j+2;j=1;}if(j>t[0]){for(k=i,c=t[0];k<=s[0];k++)s[k-c]=s[k];s[0]=s[0]-t[0];flag=1;i=i-t[0];j=1;}}if(flag==1)returnTRUE;elsereturnFALSE;}4.24③采用教科书4.2.2节中所定义的堆分配存储表示。试写一算法，在串的堆存储结构上实现串基本操作Concat(&T,s1,s2)。要求实现以下函数：StatusConcat(HString&S,HStringS1,HStringS2)/*用S返回由S1和S2联接而成的新串*/堆串HString的类型定义：typedefstruct{char*ch;//假设是非空串,那么按串长分配存储区,否那么ch为NULLintlength;//串长度}HString;StatusConcat(HString&S,HStringS1,HStringS2)/*用S返回由S1和S2联接而成的新串*/{inti,j;if(S.ch)free(S.ch);S.ch=(char*)malloc((S1.length+S2.length)*sizeof(char));for(i=0;i<S1.length;i++)S.ch[i]=S1.ch[i];for(i=S1.length,j=0;j<S2.length;i++,j++)S.ch[i]=S2.ch[j];S.length=S1.length+S2.length;returnTRUE;}4.30⑤假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现的第一个最长重复子串及其位置，并分析你的算法的时间复杂度。要求实现以下函数：voidCommonStr(SStrings,SString&sub,int&loc);/*求串s中出现的第一个最长重复子串sub及其位置loc*/定长顺序串SString的类型定义：typedefunsignedcharSString[MAXSTRLEN+1];/*s[0]isthestring'slength*/voidCommonStr(SStrings,SString&sub,int&loc)/*求串s中出现的第一个最长重复子串sub及其位置loc*/{inti,j,k,len=0,count;for(i=2;i<=s[0];i++){k=i;count=0;for(j=1;k<=s[0];j++,k++){if(s[k]==s[j])count++;elseif(len<count){len=count;loc=j-count;count=0;}elsecount=0;}if(count!=0&&len<count){len=count;loc=j-count;}}for(i=loc,j=1;i<=len;i++,j++)sub[j]=s[i];sub[0]=len;}5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。要求实现以下函数：StatusAddTSM(TSMatrixA,TSMatrixB,TSMatrix&C);/*三元组表示的稀疏矩阵加法:C=A+B*/稀疏矩阵的三元组顺序表类型TSMatrix的定义：#defineMAXSIZE20//非零