廣工數(shù)據(jù)結(jié)構(gòu)作業(yè)系統(tǒng)-第1-10章答案

◆2.11②設(shè)順序表L中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到L的適當(dāng)位置上，并保持該表的有序性。要求實(shí)現(xiàn)以下函數(shù)：voidInsertOrderList(SqList&L,ElemTypex)/*在有序的順序表L中保序插入數(shù)據(jù)元素x*/順序表類型定義如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInsertOrderList(SqList&L,ElemTypex)//在有序的順序表L中保序插入數(shù)據(jù)元素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③設(shè)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)〕。假設(shè)A'=B'=空表，那么A=B；假設(shè)A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，那么A<B；否那么A>B。試寫一個(gè)比較A和B大小的算法。〔注意：在算法中，不要破壞原表A和B，也不一定先求得A'和B'才進(jìn)行比擬〕。要求實(shí)現(xiàn)以下函數(shù)：charCompare(SqListA,SqListB);/*比擬順序表A和B,*//*返回'<',假設(shè)A<B;*//*'=',假設(shè)A=B;*//*'>',假設(shè)A>B*/順序表類型定義如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;charCompare(SqListA,SqListB)//比擬順序表A和B,//返回'<',假設(shè)A<B;//'=',假設(shè)A=B;//'>',假設(shè)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②試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x)。實(shí)現(xiàn)以下函數(shù)：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②試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。實(shí)現(xiàn)以下函數(shù)：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②試寫一算法，在無頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作INSERT(L,i,b)，并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比擬。實(shí)現(xiàn)以下函數(shù)：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題要求。試寫一算法，實(shí)現(xiàn)線性表操作DELETE(L,i)。實(shí)現(xiàn)以下函數(shù)：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題條件，試寫一高效的算法，刪除表中所有值相同的多余元素(使得操作后的線性表中所有元素的值均不相同)同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。實(shí)現(xiàn)以下函數(shù)：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③試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表(a1,a2,…,an)逆置為(an,an-1,…,a1)。實(shí)現(xiàn)以下函數(shù)：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③試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。實(shí)現(xiàn)以下函數(shù)：voidInverse(LinkList&L);/*對(duì)帶頭結(jié)點(diǎn)的單鏈表L實(shí)現(xiàn)就地逆置*/單鏈表類型定義如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidInverse(LinkList&L)/*對(duì)帶頭結(jié)點(diǎn)的單鏈表L實(shí)現(xiàn)就地逆置*/{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③設(shè)線性表A=(a1,...,am),B=(b1,...,bn)，試寫一個(gè)按以下規(guī)那么合并A、B為線性表C的算法，即使得C=(a1,b1,...,am,bm,bm+1,...,bn)當(dāng)m≤n時(shí)；或者C=(a1,b1,...,an,bn,an+1,...,am)當(dāng)m＞n時(shí)。線性表A、B和C均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L度值m和n均未顯式存儲(chǔ)。實(shí)現(xiàn)以下函數(shù)：voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依題意，合并帶頭結(jié)點(diǎn)的單鏈表ha和hb為hc*/單鏈表類型定義如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依題意，合并帶頭結(jié)點(diǎn)的單鏈表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④假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序〔即非遞增有序，允許表中含有值相同的元素〕排列的線性表C，并要求利用原表〔即A表和B表〕的結(jié)點(diǎn)空間構(gòu)造C表。實(shí)現(xiàn)以下函數(shù)：voidUnion(LinkList&lc,LinkListla,LinkListlb);/*依題意，利用la和lb原表的結(jié)點(diǎn)空間構(gòu)造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;//構(gòu)造新表頭/*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實(shí)現(xiàn)就地逆置'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②假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。實(shí)現(xiàn)以下函數(shù)：ElemTypeDeleteNode(LinkLists);/*刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，并返回被刪結(jié)點(diǎn)的元素值*/單鏈表類型定義如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;ElemTypeDeleteNode(LinkLists)/*刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，并返回被刪結(jié)點(diǎn)的元素值*/{LinkListp;p=s->next;while(p->next->next!=s)p=p->next;ElemTypee=p->next->data;p->next=s;returne;}2.32②有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：prev、data和next，其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，prev也為指針域，但它的值為空(NULL)，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使prev成為指向前驅(qū)結(jié)點(diǎn)的指針域。實(shí)現(xiàn)以下函數(shù)：voidPerfectBiLink(BiLinkList&CL);雙向循環(huán)鏈表類型定義如下：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③由一個(gè)線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素〔如：字母字符、數(shù)字字符和其它字符〕，試編寫算法將該線性鏈表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符。實(shí)現(xiàn)以下函數(shù)：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;//建立頭結(jié)點(diǎn)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;//完成循環(huán)鏈表}2.37④設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表L=(a1,a2,...,an)。試寫一時(shí)間復(fù)雜度為O(n)的算法，將L改造為L=(a1,a3,...,an,...,a4,a2)。實(shí)現(xiàn)以下函數(shù)：voidReverseEven(BiLinkList&L);雙向循環(huán)鏈表類型定義如下：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;}//此時(shí)p指向最后一個(gè)奇數(shù)結(jié)點(diǎn)if(p->next==L)p->next=L->prev->prev;elsep->next=L->prev;p=p->next;//此時(shí)p指向最后一個(gè)偶數(shù)結(jié)點(diǎn)while(p->prev->prev!=L){p->next=p->prev->prev;p=p->next;}if(p!=L)p->next=L;//按題目要求調(diào)整了next鏈的結(jié)構(gòu),此時(shí)pre鏈仍為原狀for(p=L;p->next!=L;p=p->next)p->next->prev=p;L->prev=p;//調(diào)整pre鏈的結(jié)構(gòu),同2.32方法}◆2.39③試對(duì)稀疏多項(xiàng)式Pn(x)采用存儲(chǔ)量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲(chǔ)結(jié)構(gòu)，編寫求Pn(x0)的算法〔x0為給定值〕，并分析你的算法的時(shí)間復(fù)雜度。實(shí)現(xiàn)以下函數(shù)：floatEvaluate(SqPolypn,floatx);/*pn.data[i].coef存放ai，*//*pn.data[i].exp存放ei(i=1,2,...,m)*//*本算法計(jì)算并返回多項(xiàng)式的值。不判別溢出。*//*入口時(shí)要求0≤e1<e2<...<em，算法內(nèi)不對(duì)此再作驗(yàn)證*/多項(xiàng)式的順序存儲(chǔ)結(jié)構(gòu):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)*//*本算法計(jì)算并返回多項(xiàng)式的值。不判別溢出。*//*入口時(shí)要求0≤e1<e2<...<em，算法內(nèi)不對(duì)此再作驗(yàn)證*/{inti;floats=0;for(i=0;i<pn.length;++i){s+=pn.data[i].coef*f(x,pn.data[i].exp);}returns;}◆2.41②試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的算法，要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)〔多項(xiàng)式〕，同時(shí)釋放所有無用〔被刪〕結(jié)點(diǎn)。實(shí)現(xiàn)以下函數(shù)：voidDifference(LinkedPoly&pa);/*稀疏多項(xiàng)式pa以循環(huán)鏈表作存儲(chǔ)結(jié)構(gòu)，*//*將此鏈表修改成它的導(dǎo)函數(shù)，并釋放無用結(jié)點(diǎn)*/鏈?zhǔn)蕉囗?xiàng)式的類型定義：typedefstructPolyNode{intcoef;intexp;structPolyNode*next;}PolyNode,*PolyLink;//多項(xiàng)式元素〔項(xiàng)〕結(jié)點(diǎn)類型typedefPolyLinkLinkedPoly;//鏈?zhǔn)蕉囗?xiàng)式voidDifference(LinkedPoly&pa)/*稀疏多項(xiàng)式pa以循環(huán)鏈表作存儲(chǔ)結(jié)構(gòu)，*//*將此鏈表修改成它的導(dǎo)函數(shù)，并釋放無用結(jié)點(diǎn)*/{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③試寫一個(gè)算法，識(shí)別依次讀入的一個(gè)以@為結(jié)束符的字符序列是否為形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是屬該模式的字符序列，而'1+3&3-1'那么不是。實(shí)現(xiàn)以下函數(shù):Statusmatch(char*str);/*假設(shè)str是屬該模式的字符序列，*//*那么返回TRUE，否那么返回FALSE*/Stack是一個(gè)已實(shí)現(xiàn)的棧?？墒褂玫南嚓P(guān)類型和函數(shù)：typedefcharSElemType;//棧Stack的元素類型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);StatusGetTop(Stacks,SElemType&e);Statusmatch(char*str)/*假設(shè)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②試寫一個(gè)判別表達(dá)式中開、閉括號(hào)是否配對(duì)出現(xiàn)的算法。實(shí)現(xiàn)以下函數(shù)：StatusMatchCheck(SqListexp);/*順序表exp表示表達(dá)式；*//*假設(shè)exp中的括號(hào)配對(duì)，那么返回TRUE，否那么返回FALSE*//*注：本函數(shù)不使用棧*/順序表類型定義如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//順序表StatusMatchCheck(SqListexp)/*順序表exp表示表達(dá)式；*//*假設(shè)exp中的括號(hào)配對(duì)，那么返回TRUE，否那么返回FALSE*//*注：本函數(shù)不使用棧*/{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④假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種括號(hào)：圓括號(hào)"("和")"，方括號(hào)"["和"]"和花括號(hào)"{"和"}"，且這三種括號(hào)可按任意的次序嵌套使用〔如：…[…{…}…[…]…]…[…]…(…)…〕。編寫判別給定表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)的算法(表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中)。實(shí)現(xiàn)以下函數(shù)：StatusMatchCheck(SqListexp);/*順序表exp表示表達(dá)式；*//*假設(shè)exp中的括號(hào)配對(duì)，那么返回TRUE，否那么返回FALSE*/順序表類型定義如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//順序表Stack是一個(gè)已實(shí)現(xiàn)的棧?？墒褂玫南嚓P(guān)類型和函數(shù)：typedefcharSElemType;//棧Stack的元素類型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);StatusGetTop(Stacks,SElemType&e);StatusMatchCheck(SqListexp)/*順序表exp表示表達(dá)式；*//*假設(shè)exp中的括號(hào)配對(duì)，那么返回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③假設(shè)以二維數(shù)組g(1..m,1..n)表示一個(gè)圖像區(qū)域，g[i,j]表示該區(qū)域中點(diǎn)(i,j)所具顏色，其值為從0到k的整數(shù)。編寫算法置換點(diǎn)(i0,j0)所在區(qū)域的顏色。約定和(i0,j0)同色的上、下、左、右的鄰接點(diǎn)為同色區(qū)域的點(diǎn)。實(shí)現(xiàn)以下函數(shù)：voidChangeColor(GTYPEg,intm,intn,charc,inti0,intj0);/*在g[1..m][1..n]中，將元素g[i0][j0]*//*所在的同色區(qū)域的顏色置換為顏色c*/表示圖像區(qū)域的類型定義如下：typedefcharGTYPE[m+1][n+1];Stack是一個(gè)已實(shí)現(xiàn)的棧?？墒褂玫南嚓P(guān)類型和函數(shù)：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]*//*所在的同色區(qū)域的顏色置換為顏色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③假設(shè)表達(dá)式由單字母變量和雙目四那么運(yùn)算算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。實(shí)現(xiàn)以下函數(shù)：char*RPExpression(char*e);/*返回表達(dá)式e的逆波蘭式*/Stack是一個(gè)已實(shí)現(xiàn)的棧?？墒褂玫南嚓P(guān)類型和函數(shù)：typedefcharSElemType;//棧Stack的元素類型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);SElemTypeTop(Stacks);char*RPExpression(char*e)/*返回表達(dá)式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③試編寫如下定義的遞歸函數(shù)的遞歸算法:g(m,n)=0當(dāng)m=0,n>=0g(m,n)=g(m-1,2n)+n當(dāng)m>0,n>=0并根據(jù)算法畫出求g(5,2)時(shí)棧的變化過程。實(shí)現(xiàn)以下函數(shù)：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④試寫出求遞歸函數(shù)F(n)的遞歸算法，并消除遞歸：F(n)=n+1當(dāng)n=0F(n)=nF(n/2)當(dāng)n>0實(shí)現(xiàn)以下函數(shù)：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②假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。實(shí)現(xiàn)以下函數(shù)：StatusInitCLQueue(CLQueue&rear);StatusEnCLQueue(CLQueue&rear,ElemTypex);StatusDeCLQueue(CLQueue&rear,ElemType&x);帶頭結(jié)點(diǎn)循環(huán)鏈隊(duì)列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③如果希望循環(huán)隊(duì)列中的元素都能得到利用，那么需設(shè)置一個(gè)標(biāo)志域tag，并以tag的值為0或1來區(qū)分，尾指針和頭指針值相同時(shí)的隊(duì)列狀態(tài)是"空"還是"滿"。試編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)列和出隊(duì)列的算法，并從時(shí)間和空間角度討論設(shè)標(biāo)志和不設(shè)標(biāo)志這兩種方法的使用范圍〔比方，當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí)，那一種方法較好？〕。實(shí)現(xiàn)以下函數(shù)：StatusEnCQueue(CTagQueue&Q,QElemTypex);StatusDeCQueue(CTagQueue&Q,QElemType&x);此題的循環(huán)隊(duì)列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②假設(shè)將循環(huán)隊(duì)列定義為：以域變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法〔在出隊(duì)列的算法中要返回隊(duì)頭元素〕。實(shí)現(xiàn)以下函數(shù)：StatusEnCQueue(CLenQueue&Q,QElemTypex);StatusDeCQueue(CLenQueue&Q,QElemType&x);此題的循環(huán)隊(duì)列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③假設(shè)稱正讀和反讀都相同的字符序列為"回文"，例如，'abba'和'abcba'是回文，'abcde'和'ababab'那么不是回文。試寫一個(gè)算法判別讀入的一個(gè)以'@'為結(jié)束符的字符序列是否是"回文"。實(shí)現(xiàn)以下函數(shù)：StatusPalindrome(char*word);/*利用棧和隊(duì)列判定字符序列word是否是回文*/可使用棧Stack和隊(duì)列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)/*利用棧和隊(duì)列判定字符序列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③編寫對(duì)串求逆的遞推算法。要求實(shí)現(xiàn)以下函數(shù)：voidReverse(StringType&s);/*Reversesbyiteration.*/StringType是串的一個(gè)抽象數(shù)據(jù)類型，它包含以下6種根本操作：voidInitStr(StringType&s);//初始化s為空串。voidStrAssign(StringType&t,StringTypes);//將s的值賦給t。s的實(shí)際參數(shù)是串變量。intStrCompare(StringTypes,StringTypet);//比擬s和t。假設(shè)s>t，返回值>0；假設(shè)s=t，返回值=0；假設(shè)s<t，返回值<0。intStrLength(StringTypes);//返回s中的元素個(gè)數(shù)，即該串的長度。StringTypeConcat(StringType&s,StringTypet);//返回由s和t聯(lián)接而成的新串。StringTypeSubString(StringTypes,intstart,intlen);//當(dāng)1<=start<=StrLength(s)且0<=len<=StrLength(s)-start+1時(shí)，//返回s中第start個(gè)字符起長度為len的子串，否那么返回空串。//注意,不要使用"s="的形式為StringType類型的變量賦值,//而要使用StrAssign函數(shù)!!!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③編寫一個(gè)實(shí)現(xiàn)串的置換操作Replace(&S,T,V)的算法。要求實(shí)現(xiàn)以下函數(shù)：voidReplace(StringType&S,StringTypeT,StringTypeV);/*以串v置換串s中出現(xiàn)的所有和串t相同的非空串*/StringType是串的一個(gè)抽象數(shù)據(jù)類型，它包含以下6種根本操作：voidInitStr(StringType&s);//初始化s為空串。voidStrAssign(StringType&t,StringTypes);//將s的值賦給t。s的實(shí)際參數(shù)是串變量。intStrCompare(StringTypes,StringTypet);//比擬s和t。假設(shè)s>t，返回值>0；假設(shè)s=t，返回值=0；假設(shè)s<t，返回值<0。intStrLength(StringTypes);//返回s中的元素個(gè)數(shù)，即該串的長度。StringTypeConcat(StringType&s,StringTypet);//返回由s和t聯(lián)接而成的新串。StringTypeSubString(StringTypes,intstart,intlen);//當(dāng)1<=start<=StrLength(s)且0<=len<=StrLength(s)-start+1時(shí)，//返回s中第start個(gè)字符起長度為len的子串，否那么返回空串。//注意,不要使用"s="的形式為StringType類型的變量賦值,//而要使用StrAssign函數(shù)!!!voidReplace(StringType&S,StringTypeT,StringTypeV)/*以串v置換串s中出現(xiàn)的所有和串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相同的子串。要求實(shí)現(xiàn)以下函數(shù)：voidDelSubString(StringType&scrStr,StringTypesubStr);/*Removeallsubstringmatching'subStr'from'scrStr'.*/StringType是串的一個(gè)抽象數(shù)據(jù)類型，它包含以下6種根本操作：voidInitStr(StringType&s);//初始化s為空串。voidStrAssign(StringType&t,StringTypes);//將s的值賦給t。s的實(shí)際參數(shù)是串變量。intStrCompare(StringTypes,StringTypet);//比擬s和t。假設(shè)s>t，返回值>0；假設(shè)s=t，返回值=0；假設(shè)s<t，返回值<0。intStrLength(StringTypes);//返回s中的元素個(gè)數(shù)，即該串的長度。StringTypeConcat(StringType&s,StringTypet);//返回由s和t聯(lián)接而成的新串。StringTypeSubString(StringTypes,intstart,intlen);//當(dāng)1<=start<=StrLength(s)且0<=len<=StrLength(s)-start+1時(shí)，//返回s中第start個(gè)字符起長度為len的子串，否那么返回空串。//注意,不要使用"s="的形式為StringType類型的變量賦值,//而要使用StrAssign函數(shù)!!!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③編寫算法，實(shí)現(xiàn)串的根本操作Replace(&S,T,V)。要求采用教科書4.2.1節(jié)中所定義的定長順序存儲(chǔ)表示，但不允許調(diào)用串的根本操作。要求實(shí)現(xiàn)以下函數(shù)：StatusReplace(SString&s,SStringt,SStringv);/*用串v替換串s中所有和串t匹配的子串。*//*假設(shè)有與t匹配的子串被替換，那么返回TRUE；*//*否那么返回FALSE*/定長順序串SString的類型定義：typedefunsignedcharSString[MAXSTRLEN+1];/*s[0]isthestring'slength*/StatusReplace(SString&s,SStringt,SStringv)/*用串v替換串s中所有和串t匹配的子串。*//*假設(shè)有與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相同的子串。要求實(shí)現(xiàn)以下函數(shù)：StatusDelSub(SString&s,SStringt);/*從串s中刪除所有和串t匹配的子串。*//*假設(shè)有與t匹配的子串被刪除，那么返回TRUE；*//*否那么返回FALSE*/定長順序串SString的類型定義：typedefunsignedcharSString[MAXSTRLEN+1];/*s[0]isthestring'slength*/StatusDelSub(SString&s,SStringt)/*從串s中刪除所有和串t匹配的子串。*//*假設(shè)有與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節(jié)中所定義的堆分配存儲(chǔ)表示。試寫一算法，在串的堆存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串基本操作Concat(&T,s1,s2)。要求實(shí)現(xiàn)以下函數(shù)：StatusConcat(HString&S,HStringS1,HStringS2)/*用S返回由S1和S2聯(lián)接而成的新串*/堆串HString的類型定義：typedefstruct{char*ch;//假設(shè)是非空串,那么按串長分配存儲(chǔ)區(qū),否那么ch為NULLintlength;//串長度}HString;StatusConcat(HString&S,HStringS1,HStringS2)/*用S返回由S1和S2聯(lián)接而成的新串*/{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⑤假設(shè)以定長順序存儲(chǔ)結(jié)構(gòu)表示串，試設(shè)計(jì)一個(gè)算法，求串s中出現(xiàn)的第一個(gè)最長重復(fù)子串及其位置，并分析你的算法的時(shí)間復(fù)雜度。要求實(shí)現(xiàn)以下函數(shù)：voidCommonStr(SStrings,SString&sub,int&loc);/*求串s中出現(xiàn)的第一個(gè)最長重復(fù)子串sub及其位置loc*/定長順序串SString的類型定義：typedefunsignedcharSString[MAXSTRLEN+1];/*s[0]isthestring'slength*/voidCommonStr(SStrings,SString&sub,int&loc)/*求串s中出現(xiàn)的第一個(gè)最長重復(fù)子串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④假設(shè)稀疏矩陣A和B均以三元組表作為存儲(chǔ)結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組表C存放結(jié)果矩陣。要求實(shí)現(xiàn)以下函數(shù)：StatusAddTSM(TSMatrixA,TSMatrixB,TSMatrix&C);/*三元組表示的稀疏矩陣加法:C=A+B*/稀疏矩陣的三元組順序表類型TSMatrix的定義：#defineMAXSIZE20//非零