...表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符義用戶數據，因此稱它們為預定義數據類型。抽象數據類型通和在這些數據上所進行的操作。在定義抽象數據類型中的數據1.4試仿照三元組的抽象數據類型分別寫出抽象數據類型復數和有理數的定義(有理數是其分子、分母均ADTComplex{stroyCmoplexCetCkePutCkeMaxC,&e)MinC,&e)ADTRationalNumber{smstroyRationalNumberRetRkePutRkeMaxR,&e)MinR,&e)while(i<=n){product*=i;}do{whileinai!=x));)switch{...yzyxbreakexyzabsxybreakfaultzxyabsxabsy}。k=10*i;}do{k=10*i;hileinwhile(i<=n-1){k=10*i;}for(i=1;i<=n;i++){forjijnj+)})for(i=1;i<=n;i++){...for(j=1;j<=i;j++){forkkjkdelta}}while(x>=(y+1)*(y+1)){}while(y>0){ifxx-=10;y--;}}2i=12222i=1i=1i=1i=112412(6)nintTime(intn){count=0;x=2;while(x<n/2){x*=2;count++;}urncount}......count=logn22n試問在此條件下，這兩個算法可解問題的規模(即n值的圍)各為多少？哪個算法更適宜？請說明理由。nnn個規模下，第2222ni=1i=0(3)n2i1=2n1i=1i=1ntyintz{eturnzeturnz}ff…，fk2=0，fk1=1；f=f+f+^+fn=k,k+1,^nn1n2nk，tn{pnewintk1];riiki}orikiniforjjkjpjpj+1];...pkpk1]-x;}urnpk}DEfenumABCDESchoolNameumFemaleMaleSexTypectreventypesexNameschoolctintMaleSum;//男團總分intFemaleSum團總分intTotalSum團體總分SumSumScoreSchoolNamesnComponenta,intn){pmiinietempMaleSumaiscorealetempFemaleSumaiscore}}umtempMaleSumtempFemaleSumurntemp}deiostreamh...destdlibhdefineMAXINT5#defineArrSize100{erkiikiexitelseaiia[i-1];}}iikielsecout<<a[i]<<"";}return;}nin01.20試編寫算法求一元多項式的值P(x)=naxi的值Pnin0i=0n0和n，輸出為P(xn0deiostreamhdestdlibh#defineN10doublepolynomailintaintidoublexintn{...foriinicina[i];coutThepolynomailvalueispolynomailanxn)<<endl;return;}doublepolynomailintaintidoublexintn{urnanipolynomailaixnxnan}2.1描述以下三個概念的區別：頭指針，頭結點，首元結點(第一個元素結點)。向首元結點，其作用主要是為理。。單鏈表中邏輯上相鄰的元素的物理位置不一定(4)在單鏈表中設置頭結點的作用是插入和刪除首元結點時不用進行特殊處理。...L=(LinkList)malloc(sizeof(LNode));P=L;riiiPnextLinkListmalloc(sizeof(LNode));P=P->next;P->data=i*2-1;}PnextNULLforiiiInsLinkListL,i+1,i*2);foriiiDelLinkListL,i);...b.(7)(11)(8)(4)(1)c(5)(12)d.(9)(1)(6)d結點的語句序列是____________________。e句序列是____________________。tQnext...b.(10)(12)(8)(3)(14)c(10)(12)(7)(3)(14)d(12)(11)(3)(14)e(9)(11)(3)(14)uub.(8)(4)(5)(13)c(15)(1)(11)(18)d(16)(2)(10)(18)e(14)(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;}urnOK})voidBB(LNode*s,LNode*q){...while(p->next!=q)p=p->next;pnexts;}voidAA(LNode*pa,LNode*pb){BBpapb;BBpbpa;}StatusDeleteKSqListaintiintk){else{ountcountkcountforjalengthjija.elem[j-i]=a.elem[j];a.length--;}urnOK}StatusDeleteKSqListaintiintk){jjkjaelemjiaelemjik;halengthkurnOK}StatusInsertOrderListSqListvaElemTypex{zereturnOVERFLOW...forivalengthi>0,x<va.elem[i-1];i--)va.elem[i]=va.elem[i-1];elemixlengthurnOK}2.12設A=(a,^,a)和B=(b,^,b)均為順序表，A,和B,分別為A和B中除去最大共同前1m1n綴后的子表。若A,=B,=空表，則A=B；若A,=空表，而B,空表，或者兩者均不為空表，且A,atusCompareOrderListSqListASqListB{kAlengthBlength?A.length:B.length;iikilemijifAelemiBelemij;}engthkjgthjreturnj;}nkListLElemTypex{kListpLwhile(p&&p->data!=x){ppnext}elsereturni}度tL{kListpL...twhile(p){ppnext}returni;}voidMergeListLLinkListhaLinkListhb,LinkList&hc){Listpapbwhile(pa->next&&pb->next){papanextpbpbnext}while(pb->next)pb=pb->next;pbnextha>next;}while(pa->next)pa=pa->next;panexthb>next;}}StatusDeleteAndInsertSubLinkedListlaLinkedListlbintiintjintlen){p=la;k=1;while(k<i){p=p->next;k++;}while(k<=len){q=q->next;while(k<j){s=s->next;s->next=p;q->next=s->next;urnOK...}StatusDeleteAndInsertSubLinkListlaLinkListlbintiintj,intlen){inkListpqsprevNULLwhile(p&&k<i){pppnext}while(q&&k<len){}vnextqnext}s=lb;k=1;while(s&&k<j-1){}tsnext}urnOK}...tatusListDeleteLLinkListLElemTypeminkElemTypemaxk{nkListpqprevNULLpppnextwhile(p&&p->data<maxk){pppnext}prevnextp>next;ppnext}}urnOK}2.20同2.19題條件，試寫一高效的算法，刪除表中所有值相同的多余元素(使得操作后的線性表中所有idListDeleteLSameNodeLinkListL{kListpqprevpppnextwhile(p){pppnextaprevnextp>next;ppnext...}}}2.21試寫一算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表n1(a,^,a)逆置為1n序表的逆置usListOpposeSqSqListL{lemTypexforiiLlengthi{elemiL.elem[i]=L.elem[L.length-1-i];LelemL.length-1-i]=x;}urnOK}頭結點的單鏈表的逆置usListOpposeLLinkListL{kListpqppnextextNULLwhile(p){ppnexttLnextextq}urnOK}12m12n12m12n11mmm+1n11nnn+1m...StatusListMergeLLinkListALinkListBLinkList&C){nkListpapbqaqbpaAnextpbBnextwhile(pa&&pb){pbpa=pa->next;pb=pb->next;xtqanextb}urnOK}表歸并成一個按元素值遞減有序(即非遞增有序，允許表中含有值相同的元素)排列的線性表C，并要求AB構造C表。StatusListMergeOpposeLLinkListALinkListBLinkList&C){nkListpapbqaqbpapanextpbpbnextA->next=NULL;while(pa&&pb){papanextqanextAnextA表表頭A->next=qa;}...pbpbnextqbnextAnextA表表頭A->next=qb;}}while(pa){papanextxtAnextA->next=qa;}while(pb){pbpbnextxtAnextA->next=qb;}urnOK}2.25假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合(即同一表中的元素值各不相StatusListCrossSqSqListASqListBSqList&C){while(i<A.length&&j<B.length){ListInsertSqCkAelemi]);}}urnOK}...StatusListCrossLLinkListALinkListBLinkList&C){inkListpapbqaqbptpapanextpbpbnextwhile(pa&&pb){papanexta}pbpbnextb}papanext}}while(pa){papanexta}while(pb){pbpbnextb}...urnOK}(1)假設在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；StatusListCrossDelSameSqSqListASqListBSqList&C){while(i<A.length&&j<B.length){ListInsertSqCkAelemi]);}thAelemiListInsertSqCkAelemi]);}}}urnOK}tatusListCrossDelSameSqSqListASqListB{while(i<A.length&&j<B.length){A.elem[k]=A.elem[i];...}A.elem[k]=A.elem[i];}}}A.length=k;urnOK}(1)假設在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；StatusListCrossDelSameLLinkListALinkListBLinkList&C){inkListpapbqaqbptpapanextpbpbnextwhile(pa&&pb){papanexta}pbpbnextb}...papanexta}papanext}}}while(pa){papanexta}while(pb){pbpbnextb}urnOK}tatusListCrossDelSameLLinkListALinkListB{inkListpapbqaqbptpapanextpbpbnextwhile(pa&&pb){papanexta...}pbpbnextb}papanexta}papanext}}}while(pa){papanexta}while(pb){pbpbnextb}urnOK}C表中出現的元素。試對順序表編寫實現上述操作的算法，并分析你的算法的時間復雜度(注意：題中沒指明同一表中的元素值各不相同)。StatusListUnionSqSqListDSqListASqList&B,SqList&C){...mpstCrossLBCTempstMinusLATempD}StatusListUnionLLinkListALinkListBLinkList&C){tCrossLBCtMinusLAB}tatusListMinusLLinkListALinkListB{inkListpapbqaqbptpapanextpbpbnextwhile(pa&&pb){pbpbnextb}papanext}papanexta}}while(pb){...pbpbnextb}urnOK}usListDeleteCLLinkListS{kListpqpSnextwhile(p->next!=S){ppnext}tpnexturnOK}re一個空的循環鏈表usInitListDLDuLinkListL{LDuLinkListmallocsizeofDuLNodereNULLextLurnOK}向循環鏈表中插入一個結點StatusListInsertDLDuLinkList&L,ElemTypee){DuLinkListppDuLinkListmallocsizeofDuLNode;...dataepnextL>next;extpurnOK}循環鏈表改成雙向鏈表sListCirToDuDuLinkListL{DuLinkListpqpLnextwhile(p!=L){ppreqppnext}urnOK}StatusListDivideIntoCLLinkListLLinkListsLinkList&s2,LinkList&s3){LinkListpqptptpt3;pLnextssswhile(p){apdatappnextxtptnextptnextqptpt>next;}if((p->data>='A'&&p->data<='Z')||ppnext...xtptnextptnextqptpt>next;}ppnextxtptnextptnextqptpt>next;}}urnOK}typedefstructXorNode{structXorNode*LRPtr;ntertypedestruct{//無頭結點的異或指針雙向鏈表XorPointerLeft,Right;//分別指向鏈表的左側和右端XorPointerXorPXorPointerp,XorPointerq);aab)=(a⊕a)⊕b=b域存放該結點的左鄰與右鄰結點指針(不存在時為NULL)的異或。若設指針L.Left指向鏈表中的最左結tStatusTraversingLinkListXorLinkedListL,chard){rPointerpleftrightftwhilep!=NULL){VisitingDatap->data);...pXorPleftpLRPtr);}}ghtNULLwhile(p!=NULL){VisitingDatap->data);ppXorPpLRPtrright);}}RORurnOK}12n12n13n4213n42usListChangeDuLDuLinkListL{DuLinkListpqrpLnextrLprewhile(p!=r){ppnext刪除結點renextqnextextpreqpre到頭結點的左面rernextprernextpreq;trnextextq}...t}urnOK}始終保持被頻繁訪問的結點總是靠近表頭結點。試編寫符合上述DuLinkListListLocate_DuL(DuLinkList&L,ElemTypee){DuLinkListpqpLnextwhile(p!=L&&p->data!=e)p=p->next;pfreq刪除結點pprenext=p->next;pnext>pre=p->pre;到合適的位置while(q!=L&&q->freq>p->freq)q=q->next;pnextq>next;ppreq->pre;}pnextq>pre->next;extpppreq->pre;}urnp}}typedefstruct{intcoef;...typedefstruct{//多項式的順序存儲結構olyTermdatan12mmm11cimmm的順序存儲結構，編寫求P(x)的in0算法(x為給定值)，并分析你的算法的時間復雜度。0ctctlyTermdata一個多項式sPolyInitSqPolyL{PolyTermpcout";stp=L.data;oriiLlastiutut}urnOK}求多項式的值ePolySumSqPolyLdoublex{...PolyTermpp=L.data;foriPniLlasti,p++){forjxjpexpj)x=x*x0;PnPnpcoef*x;}rnPn}2.40采用2.39題給定的條件和存儲結構，編寫求P(x)=P(x)P(x)的算法，將結果多項式存放在n1n2求兩多項式的差StatusPolyMinusSqPolyLSqPolyLSqPoly&L2){PolyTermpp,*p2;p=L.data;p1=L1.data;p2=L2.data;while(i<L1.last&&j<L2.last){pcoefp->coef;pexpp1->exp;p1++;i++;}pcoefp2->coef;pexpp2->exp;}pexpp1->exp;p++;k++;}p1++;p2++;i++;j++;}...}while(i<L1.last){pcoefp->coef;pexpp1->exp;}while(j<L2.last){pcoefp2->coef;pexpp2->exp;}lastkurnOK}typedefstructPolyNode{olyTermdataxtinknkLinkedPolysPolyDifferentialLinkedPolyL{kedPolypqptpLnextwhile(p!=L){ppnext}pdatacoef=p->data.coef*p->data.exp;p->data.exp--;ppnext...}}urnOK}StatusListDivideIntoCLLinkedPolyLLinkedPolyL{inkedPolyppqptpLnextwhile(p!=L){ppnextptnextp->next;pnextptpp>next;}ppnext}}urnOK}1節中圖3.1(b)所示鐵道進行車廂調度(注意：兩側鐵道均為單向行駛道)，則請回...in{kSPush(S,x);Push(S,‘a’);Push(S,y);while(!StackEmpty(S)){Pop(S,y);printf(y);}ntfx}{while(!StackEmpty(S)){n++;Pop(S,A[n]);}foriiniPushSAi]);}te{StackTintd;while!StackEmpty(S)){opSd}while!StackEmpty(T)){opTdushSd}}試給出區分給定序列為合法序列或非法序列的一般準則，并證明：兩個不同的合法(棧操作)序列(對同一輸入序列)不可能得到相同的輸出元素(注意：在此指的是元素實體，而不是值)序列。TSXS……TSXX……...此時兩個棧(不妨為棧A、B)的存儲情況完全相同，假設此時棧頂元素均為a。nppp一個排列)，則在n輸出序列中不可能出現這樣的情形：存在著i<j<k使p<p<p。jki解：這個問題和3.1題比較相似。因為輸入序列是從小到大排列的，所以若p<p<p，則可以理jki解為通過輸入序列ppp可以得到輸出序列ppp，顯然通過序列123是無法得到312的，參見jkiijkjki畫1#ABC/D+E^F#SHOPNDA2#ADEFPUSH(OPTR,-)3ABCDE^F#SHOPNDB4ABFUSHOPTR5ABFSHOPNDC6ABCOperate(B,*,C)7AGUSHOPTR8AGEFSHOPNDD9AGDOperate(G,/,D)AHOperate(A,-,H)#IUSHOPTRISHOPNDEUSHOPTRSHOPNDF#Operate(E,^,F)#Operate(I,+,J)#K#oiddituiintn{while(i>1)cout<<i--;...}voidditui(intj){ituij}}dtestintsum{{}}dtestintsum{ushsxwhile(!StackEmpty(s)){opsxdl}storyStacks}ar...in{eueQEnQueueQy);DeQueueQx);EnQueueQx;DeQueueQx);WhileQueueEmpty(Q)){DeQueueQy}}3.13簡述以下算法的功能(棧和隊列的元素類型均為int)。idalgoQueueQ{kSwhile(!QueueEmpty(Q)){DeQueue(Q,d);PushS,d);}while(!StackEmpty(S)){PopS,d);EnQueueQd);}}：...ElemTypetoplemTypepecStackintm{newElemTypem}StackdeletepvoidPushintiElemTypex){rStackoverflow}cksizetopxrStackoverflow}}ElemTypePop(inti){eturntoprrStackemptyif(top[1]>top[0])return*top[1]--;rrStackempty}urnOK}...數據結構及方法的定義NodeTypeemTypedataNodeType*next;pectnkTypetopdInitStackStacks{s.top=NULL;}dDestroyStackStacks{kTypepwhile(s.top){p=s.top;s.size--;}}dClearStackStacks{kTypepwhile(s.top){p=s.top;s.size--;}}Stacks{eturnssize}StatusStackEmpty(Stacks)...{SE}tusGetTopStacksElemTypee{urnOK}}StatusPushStack&s,ElemTypee){kTypepNodeTypep->next=s.top;s.top=p;dataeurnOK}atusPopStacksElemTypee{kTypepp=s.top;s.size--;}urnOK}voidStackTraverseStacksStatus(*Visit)(ElemTypee)){kTypepp=s.top;while(p)Visit(p->data);...}寫算法，輸出對這n節車廂進行調度的操作(即入棧或出棧操作)序列，以使所有的軟席車廂都被調整到{Stacks;rendlwhile(Buffer[i]){BufferjBufferi];}Bufferi}while(Buffer[j]){PopsBufferj}endlreturn;}BOOLSymmetry(chara[]){Stacks;lemTypexwhile(a[i]!='&'&&a[i]){Pushsai;}...while(a[i]){opsxstroyStacksnFALSE}}nTRUE}BOOLBracketCorrespondency(chara[]){Stacks;lemTypexwhile(a[i]){case':Pushsai;kcase':Pushsai;kcase':tTopsxifx=='(')Pop(s,x);SEkcase':tTopsxSEkk}}nTRUE...}j從0到k的整數。編寫算法置換點(i,j)所在區域的顏色。約定和(i,j)同色的上、下、左、右的鄰接點0000udeiostreamhudestdlibhctctPosTypeseatincludedVCStackh"ElemTypegMN;voidCreateGDSElemTypegMN);voidShowGraphArrayElemTypegMN);voidRegionFillingElemTypegMNPosTypeCurPos,intNewColor);{teGDSgphArraygTypeStartPossxtPosyionFillinggStartPosFillColorphArraygreturn;}...voidRegionFillingElemTypegMNPosTypeCurPos,intFillColor){Stacks;ElemTypee;xCurPosyColorPushsgCurPos.x][CurPos.y]);while(!StackEmpty(s)){opseCurPos=e.seat;osxCurPosyColorFillColorPosxCurPosyVisitedrPosxCurPosyColorOldColor)PushsgCurPos.x+1][CurPos.y]);rPosxCurPosyColorOldColor)PushsgCurPos.x-1][CurPos.y]);rPosxCurPosyColorOldColor)PushsgCurPosx][CurPos.y+1]);rPosxCurPosyColorOldColor)Push(s,g[CurPos.x][CurPos.y-1]);}}voidCreateGDSElemTypegMN){iMijjNjtxieatyj...itedor}iiijjjorforiiMi+)jjjor}voidShowGraphArrayElemTypegMN){iiMijNjColor}}入的表達式串必須為#...#格式dInversePolandExpressioncharBuffer{Stacks;ElemTypee;PushsBufferiwhile(Buffer[i]!='#'){if(!IsOperator(Buffer[i])){//是操作數BufferjBufferi];}else{//是操作符tTopseifPrioreBufferi，退棧opseBufferje;...}PushsBufferi}}}while(!StackEmpty(s)){opseBufferje;}}StatusIsOpertorcharc{pwhile(*p){nTRUE}nFALSE}StatusPriorcharccharc2){rchwhile(ch[i]&&ch[i]!=c1)i++;ifi2)i--;//加和減可認為是同級別的運算符ifi4)i--;//乘和除可認為是同級別的運算符while(ch[j]&&ch[j]!=c2)j++;if(j==2)j--;if(j==4)j--;SE}alInverPolandcharBuffer{nd...ElemTypeee;while(Buffer[i]!='#'){PushOpndBufferi}PopOpndePopOpndeBufferieushOpndc}}returnc;}charCalcharccharopcharc{oichoichcase':kcase'-':kcase':kcase':...kk}hreturnch}udeiostreamhudestdlibhudestringhincludedVCDSConstanth"arARRAYlemTypeNodeTypeemTypedataNodeType*next;pectnkTypetopidInitStackStacksStatusPushStacksElemTypee);StatusPopStacksElemTypee);tatusIsOperatorcharcStatusStackEmptyStacks;atusInvToFroPolandchara{coutaendlelsecout達式字符序列錯誤!";return;}...atusInvToFroPolandchara{Stacks;ElemTypechElemTypec;ElemTypec;while(a[i]!='#'){ch[0]=a[i];ch[1]='\0';ushsch}SE}PopscPopscushsch}SE}SE}}Popsc}SEFALSEurnOK}dInitStackStacks{...s.top=NULL;}StatusPushStack&s,ElemTypee){kTypepNodeTypep->next=s.top;s.top=p;urnOK}StatusPopStack&s,ElemTypee){kTypepatap=s.top;s.size--;}urnOK}StatusStackEmpty(Stacks){SE}StatusIsOperatorcharc{pwhile(*p){nTRUE}nFALSE...}{ltNoSolutionreturn;}{returngm2*n)+n);urn}303132338344052udeiostreamhdefineN20{riiniiai......}ndlreturn;}3.26求解平方根A的迭代函數定義如下：udeiostreamhoubleSqrtdoubleAdoublepdoublee{rtApeendlreturn;}doubleSqrtdoubleAdoublepdoublee){urnpreturnSqrtApAp/2,e);}unsignedintakm(unsignedintm,unsignedintn){unsignedintg;turnnnakmmgakmmn1);returnakmm-1,g);}}{Stacks;ElemTypeeed;e.mval=m;e.nval=n;ushsewhile(e.mval){whilee.nval){e.nval--;ushse}}opsee.mval--;l}urnenval}km0212041110401akmakmmakm1,1)gakmmnakmakmakmmakm0,1)akm=n+1=2退棧0212041110akmakmmakm1,1)gakmmnakmakm=akm(m-1,1)=akm(0,1)=2退棧0,akm(2,1)021g=akm(2,0)...204112akmakmmakm1,1)gakmmnakm;akm=akm(m-1,g)=akm(0,2);akm=n+1=3退棧02120akmakmmakm1,1)411g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2)=3;退棧02120akm=akm(m-1,1)=akm(1,1)=3退棧021gakmakmakm,3)613gakmakm(m-1,g)612gakmakm(m-1,g)611gakmakm(m-1,g)km10km401021gakmakmakm,3)613gakmakm(m-1,g)612gakmakm(m-1,g)611gakmakm(m-1,g)km10021gakmakmakm,3)613gakmakm(m-1,g)612gakmakm(m-1,g)611gakmakmm1,g)=akm(0,2)km2akm=n+1=3退棧021gakmakmakm,3)613gakmakm(m-1,g)612gakmakm(m-1,g)611021gakmakmakm,3)613gakmakm(m-1,g)612gakmakmm1,g)=akm(0,3)03akm=n+1=4退棧021gakmakmakm,3)613gakmakm(m-1,g)2,akm(1,2)612g=akm(1,1)=3;akm(m-1,g)=akm(0,3)=4退棧...021gakmakmakm,3)613gakmakmm1,g)=akm(0,4)akm=n+1=5退棧021gakmakmakm,3)613g=akm(1,2)=4;akm(m-1,g)=akm(0,4)=5退棧0,akm(2,1)021g=akm(2,0)=3;akm=akm(1,3)=5退棧m3.28假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點(注意不設頭指針)，試mTypeNodeTypeemTypedataNodeType*next;ctrearStatusInitQueueQueueq{urnOK}StatusEnQueueQueueq,ElemTypee){rpewQNodedataeextqrear}pnextqrear->next;extp}...urnOK}StatusDeQueueQueueq,ElemType&e){rpar}pqrearnext;arnextpnext}q.size--;urnOK}并從時間和空間角度討論設標志和不設標志這兩種方法的使用圍(如當循環隊列容量較小而隊列中每個元)。#defineMaxQSize4mTypectemTypebasestagStatusInitQueueQueueq{wElemTypeMaxQSizeurnOK}...StatusEnQueueQueueq,ElemTypee){agreturnFALSEearerqrearMaxQSizeag}urnOK}StatusDeQueueQueueq,ElemType&e){agreturnFALSErontontqfrontMaxQSize}urnOK}反。數。試給出此循環隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法(在出隊列的算法中要返回隊頭#defineMaxQSize4mTypectemTypebaseStatusInitQueueQueueq{wElemTypeMaxQSizehurnOK}StatusEnQueueQueueq,ElemTypee){QSizeqrearMaxQSizeqlengthMaxQSizenFALSE...earerqrearMaxQSizeh}urnOK}StatusDeQueueQueueq,ElemType&e){lengthMaxQSizeqrearnFALSEaseqrearMaxQSizeqlengthMaxQSizeq.length--;}urnOK}ebabtusSymmetryStringcharp{Queueq;eturnStacks;ElemTypeee;while(*p){PushspnQueueqp}while(!StackEmpty(s)){PopseDeQueueqe}urnOK}nn+1...tn{Queueq;emTypexewhile(i<=n){ERFLOW}ERFLOW}//隊列求和qDeQueueqeQueueqx}}returnqbaseqrearqMaxSize1)%q.MaxSize];}3.33在順序存儲結構上實現輸出受限的雙端循環隊列的入列和出列(只允許隊頭出列)算法。設每個元素計時間。入隊列采取簡化的短作業優先原則，若一個新提交nameQueuehctemTypebasestagStatusInitDQueueDQueueqintsize{zeewElemTypeqMaxSize...urnOK}StatusEnDQueueDQueueq,ElemTypee){agreturnFALSEifqfrontqrearqtag/空隊列earearqrearqMaxSizeag}else滿qbaseqfrontqbaseqrearqMaxSizeqMaxSize隊頭入隊frontqfrontqMaxSizeqMaxSizefronteag}lseearearqrearqMaxSizeag}}urnOK}StatusDeDQueueDQueueq,ElemType&e){agreturnFALSEelse列rontontqfrontqMaxSize}urnOK}Filename:XT333.cpp主程序文件udeiostreamhudestdlibhmTypeincludeDVCQueueh"{...ElemTypee;nttttDQueuedq;nDQueuedqtnDQueuedqtnDQueuedqtnDQueuedqtgeDQueuedqe}return;}n{ElemTypee;DQueuedq;HSwhile(ch[i]){ifchiSEnDQueuedqchi頭入隊ifchiHEnDQueuedqchi尾入隊}geDQueuedqe}return;}...geplacesssoncatsssConcattSubStrings),SubString(s3,7,2))enameStringhudestdlibhudestringh#defineMaxSize128cringconstStringobStringconstcharinitgvoidStrAssignStringt;gtvoidConcatStringt;StringSubStringintstartintlen;idshowStringStringconstStringob{arMaxSizerlen}StringStringconstcharinit){arMaxSizeninit...}String{arMaxSize}gString{}voidString::StrAssign(Stringt){len}mpareStringt{returnstrcmpchtch);}{rncurlen}voidString::Concat(Stringt){lentcurlen}StringStringSubStringintstart,intlen){temprtstartlencurlenlennforijstartilenijchichjpchlen}urntemp}......dStringshow{l}voidStrReverse(String&s){tringtforij;i>=0;i--)sSubStringi}(1)6×8×6=288Byte(2)LOC(5,7)=1000+(5×8+7)×6=1282(3)LOC(1,4)=1000+(1×8+4)×6=1072(4)LOC(4,7)=1000+(7×6+4)×6=1276(1)LOC(0,0,0,0)=1000)(0,1,1,0)(1,1,1,0)1)(0,1,0,1)(1,1,0,1)1)(0,1,2,1)(1,1,2,1)2)(0,1,1,2)(1,1,1,2)f(if(i)=(n+)ii2f(j)=jc=(n+1)22DIVk=2(iDIV2)+j-1...n1n1ElemTypes(inti){returnsi-1)+a1+(i-1)*d;eturna}(a(a{gtheturnMaxLketurnLelemketurnLelemk}{gtheturnMinLketurnLelemketurnLelemk}{returnLelemreturnL.elem[k]+Sum(a,k-1);}intk{...returnLelemreturnL.elem[k]*Sum(a,k-1);}eAvgSqListLintk{returnLelemreturnAvgak*k+L.elem[k])/(k+1);}voidRRMoveElemTypeA,intk,intn){ElemTypee;while(i<n-k){ikjjkjAj=A[(p*k+j)%n];Ap*k+j)%n]=e;}}}udeiostreamhmTypectElemTypee;voidInitializeNodeTypeaRSCSElemTypeA[RS][CS]);voidSaddlePointNodeTypeaRSCS;ElemTypeRowMinNodeTypeaRS][CS],intk);ElemTypeColMaxNodeTypeaRS][CS],intk);...voidShowNodeTypeaRSCS;{ElemTypeARSCSNodeTypea[RS][CS];ointareturn;}voidInitializeNodeTypeaRSCSElemTypeA[RS][CS]){iRSijCSjaijeAij];aij.i=i;aijjj;Flags}}}voidSaddlePointNodeTypeaRSCS{emTypexyiRSiwMinaijCSjaxajaijeyFlags}}}...ElemTypeRowMinNodeTypea[RS][CS],intk){lemTypexxa[k][0].e;iCSixa[k][i].e;}turnx}ElemTypeColMaxNodeTypea[RS][CS],intk){lemTypexxa[0][k].e;iRSixa[i][k].e;}turnx}voidShowNodeTypeaRSCS{rintiiRSiintjjCSjcoutijisasaddlepoint"<<endl;}mTypecElemTypee;iplertualTripleBOOLoperator(Tripleb);BOOLoperator=(Tripleb);...BOOLTriple::operator<(Tripleb){lreturnTRUEnFALSE}BOOLTriple::operator==(Tripleb){bcolnTRUEnFALSE}t{carseMatrtualCSparseMatCSparseMatintrintcintn);SparseMatoperatorCSparseMatBidShowSparseCDCpDCplempt//指向非零元的指針矩陣列數矩陣行數非零元個數CSparseMatCSparseMatintr,intc,intn){mnRowrmnColcmnTrsnmptnewTriple[m_nTrs];矩陣的所有三元組iimnTrsinputDlgdlgmpti.row=dlg1.m_nRow;mpti.col=dlg1.m_nCol;...mpti.e=dlg1.m_nElem;}}}voidCSparseMatShowSparseCDCpDC{rintiimnRowirintjjmnColjowimptkcolj}oastrpDCTextOutj20,0+i*20,str,strlen(str));}}}加的運算符重載函數CSparseMatCSparseMatoperatorCSparseMatB){CSparseMattempmnRowmnCol;wmnColBmnColurntempptnewTriplemnTrsBmnTrsmpsmnTrsBmnTrswhile(i<m_nTrs&&j<B.m_nTrs){ptkrowmptirowmpmptkcolmpticoltempmptkempti].e;}...ptkrowmptirowmpmptkcolmpticoltempmptkempti].e+B.m_pt[j].e;}mptkrowBmptjrowempmptkcolBmptjcoltempmptkeBmpt[j].e;}}}while(i<m_nTrs){ptkrowmptirowmpmptkcolmpticoltempmptkempti].e;}while(j<B.m_nTrs){mptkrowBmptjrowempmptkcolBmptjcoltempmptkeBmpt[j].e;}urntemp}deiostreamhdestdlibh#defineMax128mTypectElemTypee;t{...carseMatCSparseMatintrintcintn);rtualCSparseMatvoidShowSparseinti,intj);Twin*m_pt;//指向非零元的指針矩陣列數矩陣行數非零元個數CSparseMatCSparseMatintr,intc,intn){mnRowrmnColcmnTwsnmptnewTwin[m_nTws];矩陣的所有二元組iimnTwsicinmpticol>m_pt[i].e;}iimnRowicout<<"請輸入每行第一個非零元在二元組中的序號(沒有輸入-1)：";cin>>rpos[i];//該行沒有非零元輸入-1}}voidCSparseMat::ShowSparse(inti,intj){lemTypex}...while(d<0){wm;}}}while(k<d){xm_pt[k].e;}}}{CSparseMatA;AShowSparse(2,1);return;}mTypetOLNodeElemTypee;htdowntMat{cOLink*RHead,*CHead;//行與列指針向量的頭指針矩陣列數矩陣行數...intm_nNum;//非零元個數cossListMatCCrossListMatintrintcintn);rtualCCrossListMatvoidShowMatinti,intj);CCrossListMatCCrossListMatintr,intc,intn){mnRowrmnColcmnNumneadnewOLinkmnRoweadnewOLinkmnColimnRowiadiNULLimnColiadiNULLkpqqfiimnNumiwOLNodecinprowpcolp->e;adprowRHeadprowprightNULL}while(q&&q->col<p->col){}prightqf>right;p}...adpcolCHeadpcolpdownNULL}while(q&&q->row<p->row){}pdownqf>down;}}}voidCCrossListMat::ShowMat(inti,intj){lemTypexkpHeadiwhile(p&&p->col!=j)pprightxpe;}deiostreamhdestdlibhmTypetOLNodeElemTypee;htdowntMat{cOLink*RHead,*CHead;//行與列指針向量的頭指針...cossListMat矩陣列數矩陣行數非零元個數rtualCCrossListMatCCrossListMatintrintcintn);dAddCCrossListMatBShowMatCCrossListMatCCrossListMatintr,intc,intn){mnRowrmnColcmnNumneadnewOLinkmnRoweadnewOLinkmnColimnRowiadiNULLimnColiadiNULLkpqqfiimnNumiwOLNodecinprowpcolp->e;adprowRHeadprowprightNULL}while(q&&q->col<p->col){}...prightqf>right;p}adpcolCHeadpcolpdownNULL}while(q&&q->row<p->row){}pdownqf>down;}}}oidCCrossListMatAddCCrossListMatB{papbOLinkpre,p;//按行插入OLinkqpre,q;//按列插入iimnRowiRHeadiBRHeadiULLwhile(pb){while(pa&&pa->col<pb->col){apaparight}pa>e=pa->e+pb->e;pbpbrightapaparight}...wOLNodeprowpb->row;pcolpb->col;p>e=pb->e;pbpbrightrightpaadip}rightprererightp}處理列指針adpcolwhile(q&&q->row<i){}downqCHeadpcolp}downpreredown}}mnNummnNum+k;}CCrossListMatShowMat{kpiimnRowiHeadijjmnColjipcolj...cout<<p->e<<"";ppright}cout<<0<<"";}}}{CCrossListMatA,B(3,3,2);AAddB);AShowMat();return;}#include"DSConst.h"http://常量定義頭文件#include"StrStat.h"http://字符串定義頭文件表數據結構聲明omTypemATOMLISTElemTagGLNodelemTagtagnAtomTypeatom;tringStrCStringHStrCStringTStr{CStrings1;CStrings2(","),s3("("),s4(")");//定義常量串trStrLength...while(i<=n&&s1.StrCompare(s2)||k!=0){ikelseif(!s1.StrCompare(s4))k--;}HStr=Str.SubString(1,i-2);TStrStr.SubString(i,n-i+1);}StrStrtrStrClear}urnOK}ListGListLCStrings{CStringSub,HSub,TSub;//子串，表頭串，表尾串else{//非空串，建立廣義表L=newGLNode;//開辟一個結點gthagLISTSub=s.SubString(2,s.StrLength()-2);//取括號子串if(!Sub.StrEmpty()){//建立子表trictSubHSubTSubif(!HSub.StrEmpty())//表頭不空CreateGListLhpHSubLif(!TSub.StrEmpty())//表尾不空CreateGListLtpTSubL}else{//空表}pNULLpNULL立原子結點...agATOMLatomsGetStr];pNULL}}urnOK}顯示廣義表串dShowGListGListL{wGListLhpwGListLtp}}Latom}}義表深度的遞歸算法{if(!L)returnDepth;//廣義表不存在Depth++;//表結點深度為1HDepth=Depth+GListDepth(L->hp);TDepthDepthGListDepthL->tp);urnHDepthTDepthHDepthTDepth}}tTGListL...{wGLNodeTtagL->tag;tomLatomCopyGListThpL->hp);CopyGListTtpL->tp);}}urnOK}StatusGListCompareGListLGListL){ifLLLLreturnFALSEif(L1->tag==L2->tag){//表屬性相同returnOKSE}else{//均為表結點LhpLhpGListCompareL>tp,L