嚴蔚敏版數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案-完整版

嚴蔚敏版數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案-完整版__1.1簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲觀事物的符號表示。在計算機科學(xué)中是指所有能輸。一個整素的集作的總模型以及定義在該模型上的一組操統(tǒng)內(nèi)部定義，直義數(shù)據(jù)類型。抽的數(shù)據(jù)和在這些分和操作部結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存抽象層次更高，更能為其他用戶提解：理數(shù)的定義(有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分數(shù))。解：ADTComplex{基本操作：eroyCmoplexCkeCkeMaxCe)MinCe)ADTRationalNumber{基本操作：stroyRationalNumberRkeRkeMaxRe)一個MinRe)一個while(i<=n){product*=i;}do{}while((i!=n)&&(a[i]!=x));(3)switch{casex<y:z=y-x;break;casex=y:z=abs(x*y);break;default:z=(x-y)/abs(x)*abs(y);}常用下列三種不同的出錯處理方式：，可采用下列三種方法實現(xiàn)輸出和輸入：為煩瑣，如果出現(xiàn)錯度：while(i<=n-1){@k+=10*i;}do{@k+=10*i;}while(i<=n-1);while(i<=n-1){@k+=10*i;}for(i=1;i<=n;i++){for(j=i;j<=n;j++)k+;}(5)for(i=1;i<=n;i++){for(j=1;j<=i;j++){for(k=1;k<=j;k++)@x+=delta;}while(i+j<=n){@if(i>j)j++;elsei}while(x>=(y+1)*(y+1)){y++;}while(y>0){y}22i=12222i=1i=1i=1i=1412變量count的值(以n的函數(shù)形式表示)。intTime(intn){count=0;x=2;while(x<n/2){x*=2;count++;}returncount;}解：o(logn)2count=logn22和O(n10)，假設(shè)現(xiàn)實計算機可連續(xù)運算的時間為107秒(100多天)，又每秒可執(zhí)行基本操作(根據(jù)這些操作來估算算法時間復(fù)雜度)105次。試問在此條件下，這兩個算法可解問題的規(guī)模(即n值的范圍)各為多少？哪個算法更適宜？請說明理由。2設(shè)有以下三個函數(shù)：請判斷以下斷言正確與否：2222fngnn1.15試用數(shù)學(xué)歸納法證明：i=1i=0i=1i=1解：{rnzrnz}{pnewintk];}rjjkjpjpjpkp[k-1]-x;}pk}項項目名性別校名成績得分稱的男、女總分和團體總解：CDESchoolNamealeMaleSexTypetsexschoolintMaleSum;//男團總分intFemaleSum;//女團總分intTotalSum;//團體總分SumSumScoreSchoolNamesnComponentaintn){aiscore}}pMaleSumtempFemaleSumntemp}解：ludeiostreamhudestdlibhefineMAXINT#defineArrSize100{elseaiiai];}}elsecoutai}return;}nin0i=0度。注意選擇你i0輸出為P(x)。n0解：ludeiostreamhudestdlibh#defineN10oublepolynomailintaintidoublexintn{oriinicinaicoutThepolynomailvalueisndlreturn;}lepolynomailintaintidoublexintn{ynomailaixnx}法的時間復(fù)雜度為o(n)。2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點(第一個元素結(jié)點)。元結(jié)點之前附設(shè)的向首元結(jié)點，其作、非空表以及首元 用進行特殊處理。解：L=(LinkList)malloc(sizeof(LNode));P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++)Del_LinkList(L,i);解：extb.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)提供的答案中選擇合適的語句序____________________。____________________。d.刪除首元結(jié)點的語句序列是____________________。e.刪除尾元結(jié)點的語句序列是____________________。(6)while(Q->next!=NULL){P=Q;Q=Q->next;}xtQPPnextPnextnextNULLPPnextb.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d(12)(11)(3)(14)e(9)(11)(3)(14)_______________________。_______________________。_______________________。_______________________。eP。b.(8)(4)(5)(13)c(15)(1)(11)(18)d(16)(2)(10)(18)e4)(9)(17)if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnOK;}(2)voidBB(LNode*s,LNode*q){while(p->next!=q)p=p->next;p->next=s;}voidAA(LNode*pa,LNode*pb){BB(pa,pb);BB(pb,pa);}和低效之處，并將它改寫為一個既正確StatusDeleteKSqListaintiintk){else{untkcount//刪除第一個元素for(j=a.length;j>=i+1;j--)a.elem[j-i]=a.elem[j];a.length--;}OK}解：StatusDeleteKSqListaintiintk){lemjiaelemjikthalengthkOK}解：StatusInsertOrderListSqListvaElemTypex){RFLOWfor(i=va.length;i>0,x<va.elem[i-1];i--)va.elem[i]=va.elem[i-1];xgthOK}m1n解：sCompareOrderListSqListASqListB{kAlengthBlength?A.length:B.length;lemiBelemij}kjreturnj;}的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作Locate(L,x);解：emTypex{tpLwhile(p&&p->data!=x){ext}elsereturni}的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作Length(L)。解：{tpLwhilep){ext}returni;}解：voidMergeListLLinkListhaLinkList&hb,LinkList&hc){tpapbwhile(pa->next&&pb->next){panextpbnext}while(pb->next)pb=pb->next;pbnexthanext}while(pa->next)pa=pa->next;panexthbnext}}AndInsertSubLinkedListlaLinkedList{p=la;k=1;while(k<i){p=p->next;k++;}while(k<=len){q=q->next;k++;}while(k<j){s=s->next;k++;}s->next=p;q->next=s->next;OK}解：eteAndInsertSubLinkListlaLinkListlbint{kListpqsprevNULLwhile(p&&k<i){ext}q=p;k=1;whileq&k<len){}xtext}slbk;while(s&&k<j-1){}}OK}頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表操作InsertLib相同操作的算值遞增有序排列，并以單鏈表作存儲結(jié)元素(若表中存在這樣的元素)，同時釋放被刪結(jié)點空間，并分析量，它們的值可以和表中的元素相同，也可以不同)。解：leteLLinkListLElemTypeminkElemTypexk{istpqprevNULLextwhile(p&&p->data<maxk){xt}prevnextp>next;xt}}OK}多余元素(使得操作后的線性表中所有元素的值均不相同)，同時解：ListDeleteLSameNodeLinkListL{tpqprevextwhilep){extprevnextp>next;xt}}}序表的就地逆置，即利用原表的存儲空間將線性表(a,^,a)逆置為(a,^,a)。1nn1解：ListOpposeSqSqListL{ElemTypexLlengthiiL.elem[i]=L.elem[L.length-1-i];LelemL.length-1-i]=x;}OK}解：的單鏈表的逆置istOpposeLLinkListL{tpqextLLwhilep){ext}OK}12m12nmmm+1n11nnn+1m解：StatusListMergeLLinkListALinkListBLinkListC){stpapbqaqbaAnextbBnextwhile(pa&&pb){panextpbnextxt}OK}有序(即非遞增有序，允許表中含有值相同的元素)排列的線性表C，并要求利用原表(即A表和B表)的結(jié)點空間構(gòu)造C表。解：StatusListMergeOpposeLLinkListA,LinkListBLinkList&C){stpapbqaqbpanextpbnextA>next=NULL;while(pa&&pb){anextxtA->next=qa;}bnextxtA->next=qb;}}whilepa{panextxtA->next=qa;}whilepb{pbnextxt//將當(dāng)前最小結(jié)點插入A//將當(dāng)前最小結(jié)點插入AA->next=qb;}OK}個集合(即同一表中的元素值各不相同)，現(xiàn)要求另辟空間構(gòu)成一解：tatusListCrossSqSqListASqListBSqListC{while(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;if(A.elem[i]>B.elem[j])j++;ListInsertSqCkAelemi;}}OK}解：StatusListCrossLLinkListALinkListBLinkListC){istpapbqaqbptpanextpbnextwhile(pa&&pb){anext}pbnext}panext}}whilepa{panext}whilepb{pbnext}OK}(1)假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求解：StatusListCrossDelSame_Sq(SqList&A,SqList&B,SqList&C){while(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;ListInsertSqCkAelemi);}ListInsertSqCkAelemi);}}}OK}ListCrossDelSameSqSqListASqListB{while(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;A.elem[k]=A.elem[i];}A.elem[k]=A.elem[i];}}}A.length=k;OK}(1)假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求(2)利用原表(A表或B表)中的結(jié)點構(gòu)成表C，并釋放A表中解：tatusListCrossDelSameLLinkListALinkListBLinkList&C){istpapbqaqbptpanextpbnextwhile(pa&&pb){anext}pbnext}panext}panext}}}whilepa{panext}whilepb{pbnext}OK}sListCrossDelSameLLinkListALinkListB{istpapbqaqbptpanextpbnextwhile(pa&&pb){anext}pbnext}panext}panext}}}whilepa{panext}whilepb{pbnext}OK}序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復(fù)雜度(注意：題中沒有特別指明同一表中的元素值各不相同)。解：中StatusListUnionSqSqListDSqListASqList&B,SqList{tCrossLBCTemptMinusLATempD}解：StatusListUnionLLinkListALinkListBLinkListC){CrossLBCMinusLAB}tusListMinusLLinkListALinkListB{istpapbqaqbptpanextpbnextwhile(pa&&pb){bnext}panext}panext}}whilepb{pbnext}OK}解：tDeleteCLLinkListS{tpqextwhile(p->next!=S){ext}OKae}解：循環(huán)鏈表tListDLDuLinkListL{uLinkListmallocsizeofDuLNodeULLOK}中插入一個結(jié)點StatusListInsert_DL(DuLinkList&L,ElemTypee){uLinkListppDuLinkListmallocsizeofDuLNodenextLnextOK}雙向鏈表CirToDuDuLinkListL{LinkListpqextwhilep!=L){eqext}OK}示的線性表中含有三類字符的數(shù)據(jù)元素 (如：字母字符、數(shù)字字符和其他字符)，試編寫算法將該線性表個循環(huán)鏈表表示的線性表中均只含一解：videIntoCLLinkListLLinkLists,LinkList&s2,LinkList&s3){LinkListpqptptptextwhilep){xtxtextqptptnext}if((p->data>='A'&&p->data<='Z')||xtxtnextqptptnext;}xtxtnextqptptnext;}}OK}typedefstructXorNode{rdatastructXorNode*LRPtr;}XorNode,*XorPointer;typedestruct{//無頭結(jié)點的異或指針雙向鏈表XorPointerLeft,Right;//分別指向鏈表的左右端orLinkedListXorPointerXorP(XorPointerp,XorPointerq);a⊕(a⊕b)=(a⊕a)⊕b=b(a⊕b)⊕b=a⊕(b⊕b)=a鄰結(jié)點指針(不存在時為NULL)的異或。若設(shè)指針L.Left指向鏈此雙向鏈表的操作。試寫一算法按任一方向依解：StatusTraversingLinkListXorLinkedList&L,chard){nterpleftrighttwhile(p!=NULL){VisitingData(p->data);pXorPleftpLRPtr);}}whilep!=NULL){VisitingData(p->data);XorPpLRPtrright}}OK}12n13n42解：sListChangeDuLDuLinkListL{DuLinkListpqrextrewhilep!=r){xtqnextreqpre左面extprextpreq}}OK}freq前，頻的操作后，被訪問的結(jié)點(即元素值等于x的結(jié)點)中的頻度域順序排列，以便始終保持被頻繁訪問的結(jié)點總是靠解：DuLinkListListLocate_DuL(DuLinkList&L,ElemTypee){LinkListpqexteqpprenextp>next;pnextpre=p->pre;while(q!=L&&q->freq>p->freq)q=q->next;extqnextppreqpre;}pnextqpre>next;ppreqpre;}np}}typedefstruct{intcoeftypedefstruct{PolyTerm結(jié)構(gòu)an12mmm1i式項數(shù)m成正比的順序存儲結(jié)構(gòu)，編寫求P(x)的算法(x為給定n00值)，并分析你的算法的時間復(fù)雜度。解：yTermdata項式y(tǒng)InitSqPolyL{olyTermpp=L.data;Llasti}OK}的值ySumSqPolyLdoublex{xolyTermpp=L.data;foriPniLlastip{forjxjpexpjxxxPnPnpcoefx}}Px解：項式的差StatusPolyMinusSqPolyLSqPolyLSqPolyL){PolyTermpp*p2;p=L.data;p1=L1.data;p2=L2.data;while(i<L1.last&&j<L2.last){ppcoefp>coef;pexppexp;p++;k++;p1++;i++;}ppcoefp>coef;pexpp>exp;p++;k++;p2++;j++;}stkpexpp>exp;p++;k++;}p1++;p2++;i++;j++;}}while(i<L1.last){pcoefp>coef;pexppexp;p++;k++;p1++;i++;}while(j<L2.last){pcoefp>coef;pexppexp;p++;k++;p2++;j++;}OK}typedefstructPolyNode{PolyTermdata;structPolyNode*next;}PolyNode,*PolyLink;typedefPolyLinkLinkedPoly;項式的存儲結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的方多項式中的結(jié)點空間存放其導(dǎo)函數(shù)多項式，同時釋解：yDifferentialLinkedPolyL{Polypqptextwhilep!=L){xt}pdata.coef=p->data.coef*p->data.exp;p->data.exp--;xt}}OK}循環(huán)鏈表表示的稀疏多項式分解成兩個式中各自僅含奇次項或偶次項，并要求利用解：tatusListDivideIntoCLLinkedPolyLLinkedPolyL{dPolyppqptextwhilep!=L){pxtptnextpnext;xtptpnext}xt}}OK}135426的出站序列，并請說明為什么不能得到或者如何得到(即寫出以‘S’表示進棧和以‘X’表示出棧的棧操作序列)。3.3寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為char)。voidmain(){StackS;Push(S,x);Push(S,‘a(chǎn)’);Pop(S,x);Push(S,‘t’);Pop(S,x);Push(S,‘s’);Push(S,y);Push(S,x);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}3.4簡述以下算法的功能(棧的元素類型SElemType為int)。{while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}e{StackT;intd;while(!StackEmpty(S)){Pop(S,d);ushTd}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}法序列)。試給出區(qū)分給定序列為合法序列或非法序列的一般準則，并證明：兩個不同的合法(棧操作)序列(對同一輸入序列)不可能得到相同的輸出元素(注意：在此指的是元素實體，而不是值)序列。個合法序列為：起始操作點。由于前n個操作相同，故此時兩個棧(不妨為棧A、B)的存儲情況完全相同，假設(shè)此時棧頂元素均為a。pp^p(它是輸入序列的一個排列)，則在輸出序列中不可能出現(xiàn)這12n樣的情形：存在著i<j<k使p<p<p。jki列的，所以若p<p<p，則可以理解為通過輸入序列ppp可以得jkijki到輸出序列ppp，顯然通過序列123是無法得到312的，參見ijkjki系的慣例，并作數(shù)棧和運算符棧的變化過程：步步驟1#A-CDEFNDA2#A-CDEFPUSH(OPTR,-)3ACDEFNDB4ABPTR5#-*ABNDC6#-*ABC)7AGPTR8#-/AGNDD9#-/AGD)AHOperate(A,-1111#IPTR12#+INDE13#+PTR14#+^NDF15#+^#)16#+#)17#K#voidditui(intn){while(i>1)}解：voidditui(intj){tuij}}dtestintsum{intx;cin>>x;{}}stintsum{Stacks;xwhile(!StackEmpty(s)){x}ryStacks}解：棧是一種運算受限的線性表，其限制是僅允許在表的一端char)。{InitQueue(Q);{}}3.13簡述以下算法的功能(棧和隊列的元素類型均為int)。{intd;InitStackS{}{}}3.14若以1234作為雙端隊列的輸入序列，試分別求出滿足以下條(1)能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端(2)能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端(3)既不能由輸入受限的雙端隊列得到，也不能由輸出受限的3.15假設(shè)以順序存儲結(jié)構(gòu)實現(xiàn)一個雙向棧，即在一維數(shù)組的存儲空間中存在著兩個棧，它們的棧底分別設(shè)在數(shù)組的兩個端點。試編寫實現(xiàn)這個雙向棧tws的三個操作：初始化inistack(tws)、入棧分別指示設(shè)在數(shù)組兩端的兩個棧，并討論按過程(正/誤狀態(tài)變量可lemTypetopmTypepackintm{ElemTypem}ckdeletepvoidPushintiElemTypex{erflow}erflow}}ElemTypePop(inti){emptyif(top[1]>top[0])return*top[1]--;empty}OK}p=s.top;方法的定義emTypedataNodeType*next;ypetoptStackStacks{s.top=NULL;}troyStackStacks{Typepwhile(s.top){s.size--;}}learStackStacks{Typepwhile(s.top){p=s.top;s.size--;}}{eturnssize}StatusStackEmpty(Stacks){}GetTopStacksElemTypee{OK}}StatusPushStack&s,ElemTypee){TypepeTypep->next=s.top;s.top=p;aeOK}PopStacksElemTypee{Typepp=s.top;s.size--;}OK}itvoidStackTraverse(Stacks,Status(*Visit)(ElemTypee)){Typepp=s.top;while(p)Visit(p->data);} (分別以H和S表示)等待調(diào)度，試編寫算法，輸出對這n節(jié)車廂進行調(diào)度的操作(即入?；虺鰲２僮?序列，以使所有的軟席車廂解：{Stacks;while(Buffer[i]){BufferjBufferi;}}while(Buffer[j]){opsBufferj}return;}，識別一次讀入的一個以@為結(jié)束符的字符序列解：BOOLSymmetry(chara[]){Stacks;ElemTypexwhile(a[i]!='&'&&a[i]){hsai}whilea[i]){xyStacksE}}UE}解：BOOLBracketCorrespondency(chara[]){Stacks;ElemTypex{}UE}換點(i,j)所在區(qū)域的顏色。約定和(i,j)同色的上、下、左、右0000解：ludeiostreamhncludestdlibhosTypeseatincludedVC\Stack.h"#defineM8#defineN8lemTypegMNoidCreateGDSElemTypegMNvoidShowGraphArrayElemTypegMNvoidRegionFillingElemTypegMNPosTypeCurPosintwColor{gygypeStartPosgionFillinggStartPosFillColorygreturn;}oidRegionFillingElemTypegMNPosTypeCurPosint{Stacks;ElemTypee;orPushsgCurPosx][CurPos.y]);while(!StackEmpty(s)){eCurPos=e.seat;rPosyColorFillColorrPosyVisitedsxCurPosyColorOldColor)PushsgCurPos.x+1][CurPos.y]);sxCurPosyColorOldColor)PushsgCurPos.x-1][CurPos.y]);sxCurPosyColorOldColor)PushsgCurPosx[CurPos.y+1]);sxCurPosyColorOldColor)Push(s,g[CurPos.x][CurPos.y-1]);}}oidCreateGDSElemTypegMN{}iiMi}voidShowGraphArrayElemTypegMN{}}四則運算符構(gòu)成。試寫一個算轉(zhuǎn)換為逆波蘭表達解：InversePolandExpressioncharBuffer{Stacks;ElemTypee;shsBufferiwhile(Buffer[i]!='#'){if(!IsOperator(Buffer[i])){//是操作數(shù)BufferjBufferi;}else{//是操作符seefferje}shsBufferi}}}while(!StackEmpty(s)){eufferje}}tatusIsOpertorcharc{whilep){E}E}StatusPriorcharccharc{while(ch[i]&&ch[i]!=c1)i++;if(i==2)i--;//加和減可認為是同級別的運算符if(i==4)i--;//乘和除可認為是同級別的運算符while(ch[j]&&ch[j]!=c2)j++;if(j==2)j--;if(j==4)j--;}的解：rPolandcharBuffer{lemTypeeewhile(Buffer[i]!='#'){shOpndBufferi}ndendeendc}}returnc;}alcharccharopcharc{ludeiostreamh}rnch}綴，則將它轉(zhuǎn)化為波蘭解：ncludestdlibhncludestringhincludedVC9\DSConstant.h"emTypedataNodeType*next;ypetopInitStackStacksStatusPushStacksElemTypee;StatusPopStacksElemTypee;tusIsOperatorcharctatusStackEmptyStackssInvToFroPolandchara{coutreturn;}usInvToFroPolandchara{Stacks;ElemTypechElemTypec;ElemTypec;while(a[i]!='#'){ch[0]=a[i];ch[1]='\0';sch}}cchsch}}}}c}OK}tStackStacks{s.top=NULL;}StatusPushStack&s,ElemTypee){TypepeTypep->next=s.top;s.top=p;OK}StatusPopStack&s,ElemTypee){Typepp=s.top;s.size--;}OK}StatusStackEmpty(Stacks){}StatusIsOperatorcharc){whilep){E}E}數(shù)的遞歸算法，并根據(jù)算法畫出求解：{tionreturn;}{returngmn)+n);}0048423.25試寫出求遞歸函數(shù)F(n)的遞歸算法，并消除遞歸：解：ludeiostreamhdefineN0{}return;}3.26求解平方根A的迭代函數(shù)定義如下：(pp2-A<e解：ludeiostreamhbleSqrtdoubleAdoublepdoublee{lreturn;}doubleSqrtdoubleAdoublepdoublee){npreturnSqrtApApe;}akm(m,n)=〈|akm(m-1,1)m豐0,n=0解：unsignedintakm(unsignedintm,unsignedintn){unsignedintg;rnnakmmnreturnakmm1,g);}}{Stacks;mTypeeede.mval=m;e.nval=n;ewhile(e.mval){while(e.nval){e.nval--;e}e.mval--;e.nval=1;}ee.mval--;}enval}021620411610401akmakmmakmakmakmakmmakmakmn2退棧0,akm(2,1)021g=akm(2,0)620411610akmmakmakmakmakmm1,1)=akm(0,1)=2退棧0,akm(2,1)0212,akm(1,1)411kmakmmgakm,akm(0,2)702akmakmmakmkmmnakmakmn3退棧021620411akmakmmakmkmmnakmakmakmm1,g)=akm(0,2)=3;退棧021620akmakmmakm3退棧021makmakm613gakmakm(m-1,g)2,akm(1,2)612g=akm(1,1);akm(m-1,g)611gakmakm(m-1,g)610401021makmakm613gakmakm(m-1,g)612gakmakm(m-1,g)611gakmakm(m-1,g)610021makmakm613gakmakm(m-1,g)612gakmakm(m-1,g)611akmakmmgakmakmn3退棧0,akm(2,1)0212,akm(1,2)6123,akm(1,1)611makmakmgakmakm(m-1,g)gakmakm(m-1,g)gakm;akm(m-02161361203akmakmmggakmakmmgakmakmn4退棧0,akm(2,1)02,akm(1,2)621makmakmgakmakm(m-1,g)gakm;akm(m-021613akmakmgakmakmmgakmakmn5退棧0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)1,akm(1,3)613g=akm(1,2)=4;akm(m-0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)=5退棧隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針)，試編寫相應(yīng)的隊列初始化、入解：emTypedataNodeType*next;tatusInitQueueQueueq{OK}StatusEnQueueQueue&q,ElemTypee){Nodeaextqrear}pnextqrearnext;}OK}StatusDeQueue(Queue&q,ElemType&e){r}qrearnextpnext}q.size--;OK}得到利用，則需設(shè)置一個標志間和空間角度討論設(shè)標志和不設(shè)標志這兩種方法的使用范圍(如當(dāng)循環(huán)隊列容量較小而隊列中每個元素占的空間較多時，哪一種方法較好)。解：#defineMaxQSize4ypebasegtatusInitQueueQueueq{ypeMaxQSizeOK}StatusEnQueueQueue&q,ElemTypee){EMaxQSize}OK}StatusDeQueue(Queue&q,ElemType&e){ErontMaxQSize}OK}正好相位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件，并寫出相應(yīng)的入隊列和出隊列的算法(在出隊列的算法中要返回隊頭元素)。解：#defineMaxQSize4ypebasetatusInitQueueQueueq{ypeMaxQSizeOK}StatusEnQueueQueue&q,ElemTypee){qrearMaxQSizeizeEMaxQSize}OK}StatusDeQueue(Queue&q,ElemType&e){SizeqrearErearMaxQSizeqlengthMaxQSizeq.length--;}OK}解：SymmetryStringcharp{Queueq;Stacks;lemTypeeewhilep){shspeueqp}while(!StackEmpty(s)){eeQueueqe}OK}要求滿足：fmax而f>max，其中max為某個約定的常數(shù)。(注nn+1解：{Queueq;ypexewhilei<=n){}}//隊列求和ueqeqx}}returnqbaseqrearqMaxSize1)%q.MaxSize];}的雙端循環(huán)隊列的入列和出列 (只允許隊頭出列)算法。設(shè)每個元素表示一個待處理的作業(yè)，元若平均時解：ypebasegStatusInitDQueueDQueueqintsize{emTypeqMaxSizeOK}StatusEnDQueue(DQueue&q,ElemTypee){EarqtagarqMaxSize}ontqbaseqrearqMaxSizetqfrontqMaxSizeqMaxSize}arqMaxSize}}OK}StatusDeDQueueDQueue&q,ElemType&e){EntqMaxSize}OK}ludeiostreamhncludestdlibhincludeDVC\Queue.h"{ElemTypee;DQueuedq;uedqtuedqtuedqtuedqtQueuedqe}return;}3.34‘E’和‘D’表示對雙端隊列的頭端進行入隊列和出隊列的操作；解：{ElemTypee;DQueuedq;whilechi]){uedqchiuedqchi}Queuedqe}return;}4.1解：空格串是指一個或多個空格字符(ASCII碼為20H)組成的gnStrCompareStrLengthConcat子串(SubString)這五種基本操4.6解：essstsssConcattSubStrings),SubString(s3,7,2))ncludestdlibhncludestringh#defineMaxSize128ngconstStringobtringconstcharinitvoidStrAssignStringt);voidConcatStringt);StringSubStringintstartintlen);howringStringconstStringob{ze}StringStringconstcharinit{ze}{ze}ng{}voidString::StrAssign(Stringt){}ngt{ntempreturnstrcmpchtch;}{curlen}voidString::Concat(Stringt){rlen}StringStringSubStringintstart,intlen){curlenlenartilenijj}}tringshow{}4.10解：voidStrReverse(String&s){ringtforij-1;i>=0;i--)ngi}4.11解：解：解：解：)f(i)f(i)=(n+)ii2f(j)=jc=(n+1)25.6解：u=i-j+1v=j-1k=2(iDIV2)+j-15.10解：5.11解：5.12解：5.13解：andnn1ElemTypes(inti){returns(i-1)+a1+(i-1)*d;na}5.17解：{nMaxLkurnLelemkurnLelemk}{}{}{Min(SqList&L,intk)nMinLkurnLelemkurnLelemkListLintkturnLelemreturnL.elem[k]+Sum(a,k-1);ProductSqList&L,intk)turnLelemreturnL.elem[k]*Sum(a,k-1);}ListLintk{turnLelemreturnAvgakk+L.elem[k])/(k+1);}voidRRMoveElemTypeA],intk,intn){ElemTypee;while(i<n-k){Aj=A[(p*k+j)%n];Apk+j)%n]=e;}}}5.19解：ludeiostreamh#defineRS4#defineCS4ElemTypee;voidInitializeNodeTypeaRSCSElemTypeA[RS][CS]);voidSaddlePointNodeTypeaRSCSElemTypeRowMinNodeTypea[RS][CS],intk);ElemTypeColMaxNodeTypea[RS][CS],intk);dShowNodeTypeaRSCS{emTypeARSCSNodeTypea[RS][CS];return;}voidInitializeNodeTypeaRSCSElemTypeA[RS][CS]){Aijaijiijj}}}voidSaddlePointNodeTypeaRSCS{ypexyai}}}urnxElemTypeRowMinNodeTypea[RS][CS],intk){ElemTypexxa[k][0].e;xa[k][i].e;}urnx}ElemTypeColMaxNodeTypea[RS][CS],intk){ElemTypexxa[0][k].e;xa[i][k].e;}}dShowNodeTypeaRSCS{SiSjijisasaddlel}5.21解：eElemTypee;ualTripleBOOLoperator<(Tripleb);BOOLoperator==(Tripleb);{{}TripleoperatorTripleb)ETripleoperatorTripleb)UEE{eMatalCSparseMatCSparseMatintrintcintn;parseMatoperatorCSparseMatBShowSparseCDCpDClempt數(shù)CSparseMatCSparseMatintr,intc,intn){mnRowr;mnColc;mnTrsn;mptnewTriple[m_nTrs];三元組rsiutDlgdlgmpti].row=dlg1.m_nRow;mpti].col=dlg1.m_nCol;mpt[i].e=dlg1.m_nElem;}}}oidCSparseMatShowSparseCDCpDC{imnRowijmnColj}pDCTextOutj0,0+i*20,str,strlen(str));}}}重載函數(shù)CSparseMatCSparseMatoperatorCSparseMatB){SparseMattempmnRowmnCololntempTriplemnTrsBmnTrsrsBmnTrswhile(i<m_nTrs&&j<B.m_nTrs){wmptirowkcolmpticoltempmptkemptie;}wmptirowkcolmpticoltempmptkempti.e+B.m_pt[j].e;}krowBmptjrowmptkcolBmptjcoltempmptkeBmptje}}}while(i<m_nTrs){wmptirowkcolmpticoltempmptkemptie;}{{H[9mTVq99:{eMatCSparseMatintrintcintn;alCSparseMatvoidShowSparse(inti,intj);Twin*m_pt;//指向非零元的指針數(shù)CSparseMatCSparseMatintr,intc,intn){mnRowr;mnColc;mnTwsn;m_pt=newTwin[m_nTws];二元組wsicinmpticolm_pt[i].e;}owicout的序號(沒：";cin>>rpos[i];//該行沒有非零元輸入-1}}voidCSparseMat::ShowSparse(inti,intj){Typex}while(d<0){m}}}while(k<d){xm_pt[k].e;}}}{SparseMatAAShowSparse(2,1);return;}5.26解：eElemTypee;k{數(shù)ListMatCCrossListMatintrintcintn;alCCrossListMatvoidShowMat(inti,intj);CCrossListMatCCrossListMatintr,intc,intn){mnRowr;mnColc;mnNumn;dnewOLinkmnRowdnewOLinkmnColNULLNULLumiNodecinprowpcolpedprowphtNULL}while(q&&q->col<p->col){}prightqfright;Typex}dpcolpULL}while(q&&q->row<p->row){}pdownqfdown;}}}voidCCrossListMat::ShowMat(inti,intj){{adiwhile(p&&p->col!=j)righte}5.27解：ludeiostreamhudestdlibheElemTypee;kintm_nNum;//非零元個數(shù)ListMatalCCrossListMatCCrossListMatintrintcintn;ddCCrossListMatBMatCCrossListMatCCrossListMatintr,intc,intn){mnRowr;mnColc;mnNumn;dnewOLinkmnRowdnewOLinkmnColNULLNULLumiNodecinprowpcolpedprowphtNULL}while(q&&q->col<p->col){}prightqfright;}dpcolpULL}while(q&&q->row<p->row){}pdownqfdown;}}}idCCrossListMatAddCCrossListMatB{OLinkpre,p;//按行插入OLinkqpre,q;//按列插入owidiRHeadiwhilepb{while(pa&&pa->col<pb->col){right}pae=pa->e+pb->e;rightright}odeprowpbrow;pcolpbcol;p>e=pb->e;righthtpap}tpreghtp}while(q&&q->row<i){}nqdpcolp}npreown}}mnNummnNum+k;}ossListMatShowMat{owiadiColjoutperight}ut}}}{CCrossListMatAB3,3,2);AAddB);AShowMat();return;}法聲明STElemTagemTagtagAtomTypeatom;串CStringHStrCStringTStr{CStrings1;CStrings,s3("("),s4(")");//定義常量串rLengthwhile(i<=n&&s1.StrCompare(s2)||k!=0){elseif(!s1.StrCompare(s4))k--;}HStr=Str.SubString(1,i-2);TStr=Str.SubString(i,n-i+1);}rStrrClear}OK}GListLCStrings{CStringSub,HSub,TSub;//子串，表頭串，表尾串else{//非空串，建立廣義表L=newGLNode;//開辟一個結(jié)點STSubsSubStringsStrLength-2);//取括ubHSubTSubateGListLhpHSubateGListLtpTSub}else{//空表LLLL}}else{//建立原子結(jié)點OMLatomsGetStr;LL}}OK}串wGListGListL{istLhpistLtp}}}}5.30解：深度的遞歸算法{intHDepth,TDepth;//表頭深度，表尾深度Depth++;//表結(jié)點深度為1HDepth=Depth+GListDepth(L->hp);TDepthDepthGListDepth(L->tp);nHDepthTDepthHDepthTDepth}}5.31解：{odeTtagL>tag;CopyGListThpLhp);CopyGListTtpLtp);}}OK}5.32解：StatusGListCompareGListLGListL{ifLLLL)returnFALSE;if(L1->tag==L2->tag){//表屬性相同if(L1->tag==ATOM){//均為原子結(jié)點returnOK}else{//均為表結(jié)點GListCompareLtpL>tp))returnOK;//表頭、表尾均相同}}elsereturnFALSE;//表屬性不同}}5.33解：6.1已知一棵樹邊的集合為{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<A,C>}，請畫出這棵樹，并(2)編號為p的結(jié)點的父結(jié)點(若存在)的編號是多少？(3)編號為p的結(jié)點的第i個兒子結(jié)點(若存在)的編號是多k1(2)如果p是其雙親的最小的孩子(右孩子)，則p減去根結(jié)點的孩子(左孩子)，則p+k-1為其最小的弟弟，再減去一個根結(jié)p+1。12k向它的一個分支一結(jié)點的分支數(shù)，即為123k即in0123k123kii=1kk0kkk1滿足以下關(guān)系：01為n=kh1，其總結(jié)點數(shù)為kh1，則非葉子結(jié)點數(shù)0k1n=kh1n01033311n+n=n0120230306.10對于那些所有非葉子結(jié)點均含有左右子數(shù)的二叉樹：ii個葉子結(jié)點所在的層次(設(shè)根節(jié)點所在層次為1)。1nn1 (2)用歸納法證明。1點是原結(jié)點除去p，然后加上兩個深度為l+1的新葉子結(jié)點，由p儲結(jié)構(gòu)中，實際上隱含著雙親的信息，因此域占k恰恰相反或不一定)填寫下表：問問方時時時方)。6.14找出所有滿足下列條件的二叉樹：b6.15解：oABCDEFGHIJKLMNg000101010011112462739g00110001110111356589308BiTreeInSucc(BiTreeq){ildwhile(!r->ltag)r=r->lchild;rnr后繼是雙親結(jié)點；若是左果兄弟不存在，其后繼是6.19分別畫出和下列樹對應(yīng)的各個二叉樹：解：6.20解：G根序列相同，二叉樹的中序序列對形式：HBCJHB示成：AEKCJHBNULL一步表示成：GFKDIAENULLBCJHNULL)),NULL)GFKDNULLIAE,NULL),B(C(NULL,JH),NULL)),NULL)GFKDNULLAIENULLB(C(NULL,H(J,NULL)),NULL)),ULL樹先根后根先序二叉樹先序6.33解：A01B:01C:11111D:1110E:10F:11110G:006.27解：{returnvreturn}}return1;returnrn}}}}6.34解：{vreturntuRNvreturn}}return1;returntuRNvreturn}}}}{while(i<N&&T[i]!=x)i++;elsereturn-1;}6.35解：#defineN8charTNabcde','f','g'};右孩子，否則為左孩子{lreturn;}{whilek){}odejExpjurnx}b{urnx}{while(i<N&&T[i]!=c)i++;elsereturn-1;}6.36解：tatusSimilarTreeBiTreeTBiTreeT{}&&SimilarTree(T1->rchild,T2->rchild))UE}}}6.37解：遞歸算法StatusPOTraverseBiTreeT,Status(*Visit)(TElemTypee)){BiTreep;Stacks;針域壓棧，繼續(xù)遍歷左子樹ifVisitpdatareturnERROR;Pushsprchildhild歷未曾訪問的結(jié)點}OK}6.41解：StatusPONodeKTElemTypeeinti,intk,BiTree&T){PONodeKeik,T->lchild);PONodeKeik,T->rchild);}}OK}6.42解：子結(jié)點的數(shù)目atusPOLeafNodeNumintiBiTreeT{diPOLeafNodeNumiTlchild;POLeafNodeNumiTrchild;}OK}6.43解：樹的左右子樹sExchangeBiTreeBiTreeT{BiTreep;childTlchildTrchildildpExchangeBiTreeTlchildExchangeBiTreeTrchild}OK}6.44解：xStatusChildTreeDepthBiTreeTTElemTypexintdepth){BiTreeTOK}}atusPreOrderLocateBiTreeTTElemTypexBiTreeT{K}KK}}}}樹的深度{depBiTDepthTrchildrnldeprdepldeprdep}}6.45解：StatusDelChildTreeBiTreeTTElemTypex){TreeTK}KK}}}}DelBTreeBiTreeT{DelBTreeTlchild);DelBTreeTrchild);OK}}6.46解：叉樹StatusCopyBiTreeBiTreeTBiTreeT{BiTreep;TNodedataTdataCopyBiTreeTlchildTlchild;CopyBiTreeTrchildTrchild;}}OK}6.47解：ypeincludecYinincludeQueue.h"rderTraverseBiTreeTStatus{TypepQueueq;while(!QueueEmpty(q)){eueqpVisitp>data);}OK}6.48解：omAncstBiTreeTTElemTypeeTElemTypemTypeq{BiTreeTTpt=NULL;while(T1&&T2&&T1->data==T2->data){TlchildTlchild}TTrchildTTrchild}}}OK}}StatusPathTreeBiTreeTTElemTypep{ifTlchildDelBiTreeTlchildifTrchildDelBiTreeTrchildOK}childpK}K}turnERROR}}6.49解：sCompleteBiTreeBiTreeT{DepthTlchildBiTDepthTrchildCompleteBiTreeTrchild)returnOK;}}}6.51解：sShowBiTExpressBiTreeT{xpressTlchild}ressTlchild}xpressTrchild}ressTrchil