【正文】 rm。typedef struct { //多項式的順序存儲結(jié)構(gòu) PolyTerm *data。 int last。} SqPoly。 已知稀疏多項式，其中。試采用存儲量同多項式項數(shù)m成正比的順序存儲結(jié)構(gòu)，編寫求的算法（為給定值），并分析你的算法的時間復(fù)雜度。解：typedef struct{ int coef。 int exp。} PolyTerm。typedef struct{ PolyTerm *data。 int last。} SqPoly。// 建立一個多項式Status PolyInit(SqPoly amp。L){ int i。 PolyTerm *p。 cout請輸入多項式的項數(shù):。 cin。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。 if(!) return ERROR。 p=。 for(i=0。i。i++){ cout請輸入系數(shù):。 cinpcoef。 cout請輸入指數(shù):。 cinpexp。 p++。 } return OK。} // 求多項式的值double PolySum(SqPoly amp。L,double x0){ double Pn,x。 int i,j。 PolyTerm *p。 p=。 for(i=0,Pn=0。i。i++,p++){ for(j=0,x=1。jpexp。j++) x=x*x0。 Pn=Pn+pcoef*x。 } return Pn。} ，編寫求的算法，將結(jié)果多項式存放在新辟的空間中，并分析你的算法的時間復(fù)雜度。解：// 求兩多項式的差Status PolyMinus(SqPoly amp。L,SqPoly amp。L1,SqPoly amp。L2){ PolyTerm *p,*p1,*p2。 p=。 p1=。 p2=。 int i=0,j=0,k=0。 while(iamp。amp。j){ if(p1expp2exp){ pcoef=p1coef。 pexp=p1exp。 p++。 k++。 p1++。 i++。 } else if(p1expp2exp){ pcoef=p2coef。 pexp=p2exp。 p++。 k++。 p2++。 j++。 } else{ if(p1coef!=p2coef){ pcoef=(p1coef)(p2coef)。 pexp=p1exp。 p++。 k++。 } p1++。 p2++。 i++。 j++。 } } if(i) while(i){ pcoef=p1coef。 pexp=p1exp。 p++。 k++。 p1++。 i++。 } if(j) while(j){ pcoef=p2coef。 pexp=p2exp。 p++。 k++。 p2++。 j++。 } =k。 return OK。}，稀疏多項式采用的循環(huán)鏈表存儲結(jié)構(gòu)LinkedPoly定義為typedef struct PolyNode { PolyTerm data。 struct PolyNode *next。} PolyNode, *PolyLink。typedef PolyLink LinkedPoly。 試以循環(huán)鏈表作稀疏多項式的存儲結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的方法，要求利用原多項式中的結(jié)點空間存放其導(dǎo)函數(shù)多項式，同時釋放所有無用結(jié)點。解：Status PolyDifferential(LinkedPoly amp。L){ LinkedPoly p,q,pt。 q=L。 p=Lnext。 while(p!=L){ if(p==0){ pt=p。 p=pnext。 qnext=p。 free(pt)。 } else{ p=p*p。 p。 q=p。 p=pnext。 } } return OK。} 試編寫算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間構(gòu)成這兩個鏈表。解：// 將單鏈表L劃分成2個單循環(huán)鏈表Status ListDivideInto2CL(LinkedPoly amp。L,LinkedPoly amp。L1){ LinkedPoly p,p1,q,pt。 q=L。 p=Lnext。 p1=L1。 while(p!=L){ if(p%2==0){ pt=p。 p=pnext。 qnext=p。 ptnext=p1next。 p1next=pt。 p1=p1next。 } else{ q=p。 p=pnext。 } } return OK。}第3章 棧和隊列 (b)所示鐵道進行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請回答：(1) 如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？(2) 如果進站的車廂序列為123456，則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到（即寫出以 ‘S’表示進棧和以 ‘X’表示出棧的棧操作序列）。解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因為4356出站說明12已經(jīng)在棧中，1不可能先于2出棧。 簡述棧和線性表的差別。解：線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。棧是限定僅在表尾進行插入或刪除操作的線性表。 寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）。 void main() { Stack S。 char x,y。 InitStack(S)。 x= ‘c’。 y= ‘k’。 Push(S,x)。 Push(S, ‘a(chǎn)’)。 Push(S,y)。 Pop(S,x)。 Push(S, ‘t’)。 Push(S,x)。 Pop(S,x)。 Push(S, ‘s’)。 while(!StackEmpty(S)) { Pop(S,y)。 printf(y)。 } printf(x)。 }解：stack 簡述以下算法的功能（棧的元素類型SElemType為int）。(1) status algo1(Stack S) { int i,n,A[255]。 n=0。 while(!StackEmpty(S)) { n++。 Pop(S,A[n])。 } for(i=1。i=n。i++) Push(S,A[i])。 }(2) status algo2(Stack S,int e) { Stack T。 int d。 InitStack(T)。 while(!StackEmpty(S)){ Pop(S,d)。 if(d!=e) Push(T,d)。 } while(!StackEmpty(T)){ Pop(T,d)。 Push(S,d)。 } }解：(1) 棧中的數(shù)據(jù)元素逆置 (2) 如果棧中存在元素e，將其從棧中清除 假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體，而不是值）序列。解：任何前n個序列中S的個數(shù)一定大于X的個數(shù)。設(shè)兩個合法序列為：T1=S……X……S…… T2=S……X……X…… 假定前n個操作都相同，從第n+1個操作開始，為序列不同的起始操作點。由于前n個操作相同，故此時兩個棧（不妨為棧A、B）的存儲情況完全相同，假設(shè)此時棧頂元素均為a。第n+1個操作不同，不妨T1的第n+1個操作為S，T2的第n+1個操作為X。T1為入棧操作，假設(shè)將b壓棧，則T1的輸出順序一定是先b后a；而T2將a退棧，則其輸出順序一定是先a后b。由于T1的輸出為……ba……，而T2的輸出順序為……ab……，說明兩個不同的合法棧操作序列的輸出元素的序列一定不同。 試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序列的一個排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使。解：。因為輸入序列是從小到大排列的，所以若，則可以理解為通過輸入序列可以得到輸出序列，顯然通過序列123是無法得到312的。所以不可能存在著ijk使。 按照四則運算加、減、乘、除和冪運算(↑)優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程： 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階梵塔問題至少要執(zhí)行的move操作的次數(shù)。解： 試將下列遞推過程改寫為遞歸過程。 void ditui(int n) { int i。 i = n。 while(i1) couti。 }解：void ditui(int j){ if(j1){ coutj。 ditui(j1)。 } return。} 試將下列遞歸過程改寫為非遞歸過程。 void test(int amp。sum) { int x。 cinx。 if(x==0) sum=0。 else { test(sum)。 sum+=x。 } coutsum。 }解：void test(int amp。sum){ Stack s。 InitStack(s)。 int x。 do{ cinx。 Push(s,x)。 }while(x0)。 while(!StackEmpty(s)){ Pop(s,x)。 sum+=x。 coutsumendl。 } DestoryStack(s)。} 簡述隊列和堆棧這兩種數(shù)據(jù)類型的相同點和差異處。解：棧是一種運算受限的線性表，其限制是僅允許在表的一端進行插入和刪除運算。隊列也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。 寫出以下程序段的輸出結(jié)果（隊列中的元素類型QElemType為char）。 void main() { Queue Q。 InitQueue(Q)。 char x= ‘e’, y= ‘c’。 EnQueue(Q, ‘h’)。 EnQueue(Q, ‘r’)。 EnQueue(Q, y)。 DeQueue(Q, x)。 EnQueue(Q, x)。 DeQueue(Q, x)。 EnQueue(Q, ‘a(chǎn)’)。 While(!QueueEmpty(Q)) { DeQueue(Q,y)。 couty。 } coutx。 }解：char 簡述以下算法的功能（棧和隊列的元素類型均為int）。 void algo3(Queue amp。Q) { Stack S。 int d。 InitStack(S)。 while(!QueueEmpty(Q)) { DeQueue(Q, d)。 Push(S, d)。