【正文】 EnQueue(Q, d)。 InitStack(S)。 }解：char 簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）。 EnQueue(Q, ‘a(chǎn)’)。 EnQueue(Q, y)。 InitQueue(Q)。解：棧是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。 sum+=x。 do{ cinx。 }解：void test(int amp。 if(x==0) sum=0。} 試將下列遞歸過(guò)程改寫為非遞歸過(guò)程。 while(i1) couti。 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算(↑)優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程： ABC/D+E↑F解：BC=G G/D=H AH=I E^F=J I+J=K步驟OPTR棧OPND棧輸入字符主要操作1AB*C/D+E^FPUSH(OPND,A)2AB*C/D+E^FPUSH(OPTR,)3AB*C/D+E^FPUSH(OPND,B)4A B*C/D+E^FPUSH(OPTR,*)5*A BC/D+E^FPUSH(OPND,C)6*A B C/D+E^FOperate(B,*,C)7A G/D+E^FPUSH(OPTR,/)8/A GD+E^FPUSH(OPND,D)9/A G D+E^FOperate(G,/,D)10A H+E^FOperate(A,,H)11I+E^FPUSH(OPTR,+)12+IE^FPUSH(OPND,E)13+I E^FPUSH(OPTR,^)14+^I EFPUSH(OPND,F)15+^I E FOperate(E,^,F)16+I JOperate(I,+,J)17KRETURN 試推導(dǎo)求解n階梵塔問(wèn)題至少要執(zhí)行的move操作的次數(shù)。 試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使。由于前n個(gè)操作相同，故此時(shí)兩個(gè)棧（不妨為棧A、B）的存儲(chǔ)情況完全相同，假設(shè)此時(shí)棧頂元素均為a。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。 if(d!=e) Push(T,d)。 }(2) status algo2(Stack S,int e) { Stack T。 Pop(S,A[n])。 }解：stack 簡(jiǎn)述以下算法的功能（棧的元素類型SElemType為int）。 Push(S, ‘s’)。 Pop(S,x)。 y= ‘k’。 void main() { Stack S。 簡(jiǎn)述棧和線性表的差別。 } } return OK。 p1next=pt。 while(p!=L){ if(p%2==0){ pt=p。L1){ LinkedPoly p,p1,q,pt。 } } return OK。 } else{ p=p*p。 while(p!=L){ if(p==0){ pt=p。解：Status PolyDifferential(LinkedPoly amp。 struct PolyNode *next。 j++。 pexp=p2exp。 k++。 j++。 k++。 j++。 pexp=p2exp。 k++。amp。 p1=。L,SqPoly amp。 Pn=Pn+pcoef*x。i。 int i,j。 p++。i++){ cout請(qǐng)輸入系數(shù):。 if(!) return ERROR。 PolyTerm *p。 int last。解：typedef struct{ int coef。 int last。 }}，稀疏多項(xiàng)式采用的順序存儲(chǔ)結(jié)構(gòu)SqPoly定義為typedef struct { int coef。 qprenext=p。 qnext=p。 while(q!=L amp。 else{ pfreq++。 while(p!=L amp。試編寫符合上述要求的Locate操作的算法。 i++。 rnextpre=q。 p=pnext。 p=Lnext。試寫一時(shí)間復(fù)雜度O(n)的算法，將L改造為。 return OK。 while(p!=NULL){ VisitingData(pdata)。||d==39。 left=p。L39。L,char d){ XorPointer p,left,right。鏈表L中的每個(gè)結(jié)點(diǎn)只含兩個(gè)域：data域和LRPtr域，其中LRPtr域存放該結(jié)點(diǎn)的左鄰與右鄰結(jié)點(diǎn)指針（不存在時(shí)為NULL）的異或。typede struct { //無(wú)頭結(jié)點(diǎn)的異或指針雙向鏈表 XorPointer Left, Right。 return OK。 pt3next=q。 pt2=pt2next。)){ q=p。 amp。 pdata=39。 } else if((pdata=39。 p=pnext。amp。 pt3=s3。s3){ LinkList p,q,pt1,pt2,pt3。解：// 將單鏈表L劃分成3個(gè)單循環(huán)鏈表Status ListDivideInto3CL(LinkList amp。 p=pnext。 q=L。 Lnext=p。 p=(DuLinkList)malloc(sizeof(DuLNode))。 Lnext=L。解：// 建立一個(gè)空的循環(huán)鏈表Status InitList_DL(DuLinkList amp。 } qnext=pnext。 q=S。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。 } pb=B。 } } while(pb){ pt=pb。 } else{ pt=pa。 qbnext=pb。 while(paamp。 qa=pa。A,LinkList amp。B,LinkList amp。} 。C){ SqList Temp。解：// 在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中Status ListUnion_Sq(SqList amp。 free(pb)。 pb=pbnext。 pa=panext。 free(pt)。 free(pt)。 free(pt)。amp。 // 保存pa的前驅(qū)指針 qb=pb。B){ LinkList pa,pb,qa,qb,pt。 free(pb)。 pb=pbnext。 pa=panext。 free(pt)。 free(pt)。 free(pt)。amp。 // 保存pb的前驅(qū)指針 pa=panext。 pa=A。解： (1)// A、B求交，結(jié)果放在C表中，并刪除相同元素Status ListCrossDelSame_L(LinkList amp。 } } =k。 k++。amp。}(2)// A、B求交，然后刪除相同元素，將結(jié)果放在A表中Status ListCrossDelSame_Sq(SqList amp。 } else if([]!=[i]){ ListInsert_Sq(C,k,[i])。 j){ if([i][j]) i++。B,SqList amp。} ，對(duì)順序表重新編寫求得表C的算法。 free(pt)。 free(pt)。 pa=panext。 pb=pbnext。 pa=panext。 C=A。 qa=pa。B,LinkList amp。} 。 else{ ListInsert_Sq(C,k,[i])。 while(i amp。解：// 將A、B求交后的結(jié)果放在C表中Status ListCross_Sq(SqList amp。 free(pb)。 pb=pbnext。 pa=panext。 pb=pbnext。 pa=panext。 C=A。 // 保存pa的前驅(qū)指針 qb=pb。C){ LinkList pa,pb,qa,qb。} 假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。 } if(!pa)qbnext=pb。 pa=panext。 while(paamp。C){ LinkList pa,pb,qa,qb。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。 Lnext=q。 Lnext=NULL。解：// 帶頭結(jié)點(diǎn)的單鏈表的逆置Status ListOppose_L(LinkList amp。 [i]=[]。 ElemType x。 free(q)。amp。 p=pnext。解：void ListDelete_LSameNode(LinkList amp。 p=pnext。pdatamaxk){ if(pdata=mink){ prev=p。 prev=p。解：Status ListDelete_L(LinkList amp。} 試寫一算法，在無(wú)頭結(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)行比較。 } if(!s)return INFEASIBLE。 while(samp。 // 將從la中刪除的結(jié)點(diǎn)插入到lb中 if(j=1){ qnext=lb。 k++。 k=1。 p=pnext。 // 在la表中查找第i個(gè)結(jié)點(diǎn) p=la。la,LinkList amp。 } snext=p。 } s=lb。 k++。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len){ if(i0||j0||len0) return INFEASIBLE。 panext=hbnext。 while(pbnext) pb=pbnext。amp。hc){ LinkList pa,pb。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。 i++。L){ int i=0。 } if(!p) return 0。 while(pamp。} 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x)。 } if(k) j=1。 for(i=0。解：Status CompareOrderList(SqList amp。 return OK。i0,x[i1]。解：Status InsertOrderList(SqList amp。 =。 if(i0||i||k0||k) return INFEASIBLE。 。countk。 指出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)既正確又高效的算法。 } void AA(LNode *pa, LNode *pb) { //pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn) BB(pa,pb)。 } return OK。 P=L。(1) Status A(LinkedList L) { //L是無(wú)表頭結(jié)點(diǎn)的單鏈表 if(L amp。(16) Q=Ppriou。(12) Pnextpriou=S。(8) Spriou=Ppriou。(4) Ppriou=S。e. 刪除P結(jié)點(diǎn)的語(yǔ)句序列是_______________________。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是_______________________。(12) P=L。(8) while(Pnextnext!=Q) P=Pnext。(5) while(P!=NULL) P=Pnext。(1) P=Pnext。 b. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是____________________。(12) L=S。(8) while(Pnext!=Q) P=Pnext。(4) Snext=Pnext。d. 在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是__________________。解： 已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列