【正文】 } }　　解：(1) 棧中的數(shù)據(jù)元素逆置 (2) 如果棧中存在元素e將其從棧中清除 假設以S和X分別表示入棧和出棧的操作則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列稱可以操作的序列為合法序列（例如SXSX為合法序列SXXS為非法序列）試給出區(qū)分給定序列為合法序列或非法序列的一般準則并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體而不是值）序列　　解：任何前n個序列中S的個數(shù)一定大于X的個數(shù) 設兩個合法序列為： T1=S......X......S...... T2=S......X......X...... 假定前n個操作都相同從第n+1個操作開始為序列不同的起始操作點由于前n個操作相同故此時兩個棧（不妨為棧A、B）的存儲情況完全相同假設此時棧頂元素均為a 第n+1個操作不同不妨T1的第n+1個操作為ST2的第n+1個操作為XT1為入棧操作假設將b壓棧則T1的輸出順序一定是先b后a；而T2將a退棧則其輸出順序一定是先a后b由于T1的輸出為......ba......而T2的輸出順序為......ab......說明兩個不同的合法棧操作序列的輸出元素的序列一定不同 試證明：若借助棧由輸入序列12...n得到的輸出序列為(它是輸入序列的一個排列)則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使　　解：因為輸入序列是從小到大排列的所以若則可以理解為通過輸入序列可以得到輸出序列顯然通過序列123是無法得到312的所以不可能存在著ijk使 按照四則運算加、減、乘、除和冪運算(↑)優(yōu)先關系的慣例畫出對下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程： ABC/D+E↑F　　解：BC=G G/D=H AH=I E^F=J I+J=K步驟
OPTR棧
OPND棧
輸入字符
主要操作
1
AB*C/D+E^F
PUSH(OPNDA)
2
A
B*C/D+E^F
PUSH(OPTR)
3
。 } while(!StackEmpty(T)){ Pop(Td)。 while(!StackEmpty(S)){ Pop(Sd)。 int d。i++) Push(SA[i])。 } for(i=1。 while(!StackEmpty(S)) { n++。 }　　解：stack 簡述以下算法的功能（棧的元素類型SElemType為int） (1) status algo1(Stack S) { int inA[255]。 printf(y)。)。 Push(S 39。 Push(Sx)。t39。 Pop(Sx)。)。 Push(S 39。k39。c39。 InitStack(S)。表示出棧的棧操作序列）　　解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列但不能得到435612的出站序列因為4356出站說明12已經(jīng)在棧中1不可能先于2出棧 簡述棧和線性表的差別　　解：線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列棧是限定僅在表尾進行插入或刪除操作的線性表 寫出下列程序段的輸出結果（棧的元素類型SElemType為char） void main() { Stack S。表示進棧和以 39。}第3章 棧和隊列 (b)所示鐵道進行車廂調度（注意：兩側鐵道均為單向行駛道）則請回答： (1) 如果進站的車廂序列為123則可能得到的出站車廂序列是什么？ (2) 如果進站的車廂序列為123456則能否得到435612和135426的出站序列并請說明為什么不能得到或者如何得到（即寫出以 39。 p=pnext。 p1=p1next。 ptnext=p1next。 p=pnext。 p1=L1。 q=L。LLinkedPoly amp。 } } return OK。 q=p。 } else{ p=p*p。 qnext=p。 while(p!=L){ if(p==0){ pt=p。 q=L。 試以循環(huán)鏈表作稀疏多項式的存儲結構編寫求其導函數(shù)的方法要求利用原多項式中的結點空間存放其導函數(shù)多項式同時釋放所有無用結點　　解：Status PolyDifferential(LinkedPoly amp。 } PolyNode *PolyLink。} 稀疏多項式采用的循環(huán)鏈表存儲結構LinkedPoly定義為 typedef struct PolyNode { PolyTerm data。 } =k。 p2++。 p++。 } if(j) while(j){ pcoef=p2coef。 p1++。 p++。 } } if(i) while(i){ pcoef=p1coef。 i++。 } p1++。 p++。 } else{ if(p1coef!=p2coef){ pcoef=(p1coef)(p2coef)。 p2++。 p++。 } else if(p1expp2exp){ pcoef=p2coef。 p1++。 p++。j){ if(p1expp2exp){ pcoef=p1coef。 while(iamp。 p2=。 p=。L1SqPoly amp。} 編寫求的算法將結果多項式存放在新辟的空間中并分析你的算法的時間復雜度　　解：// 求兩多項式的差Status PolyMinus(SqPoly amp。 Pn=Pn+pcoef*x。jpexp。i。 p=。 int ij。} // 求多項式的值double PolySum(SqPoly amp。 p++。 cout請輸入指數(shù):。i++){ cout請輸入系數(shù):。 for(i=0。 if(!) return ERROR。 cin。 PolyTerm *p。// 建立一個多項式Status PolyInit(SqPoly amp。 int last。} PolyTerm。 已知稀疏多項式其中試采用存儲量同多項式項數(shù)m成正比的順序存儲結構編寫求的算法（為給定值）并分析你的算法的時間復雜度　　解：typedef struct{ int coef。 int last。 } PolyTerm。 }} 稀疏多項式采用的順序存儲結構SqPoly定義為 typedef struct { int coef。 qpre=p。 qprenext=p。 qpre=p。 qnext=p。 qfreqpfreq) q=qnext。 while(q!=L amp。 pnextpre=ppre。 else{ pfreq++。 pdata!=e) p=pnext。 while(p!=L amp。LElemType e){ DuLinkList pq。 } return OK。 } else p=pnext。 qnext=rnext。 // 插入到頭結點的左面 qpre=rnextpre。 // 刪除結點 qprenext=qnext。 while(p!=r){ if(i%2==0){ q=p。 r=Lpre。 DuLinkList pqr。} 寫出在第i個結點之前插入一個結點的算法 寫出刪除第i個結點的算法 設以帶頭結點的雙向循環(huán)鏈表表示的線性表試寫一時間復雜度O(n)的算法將L改造為　　解：// 將雙向鏈表L=(a1a2...an)改造為(a1a3...an...a2)Status ListChange_DuL(DuLinkList amp。 } } else return ERROR。 right=p。 right=NULL。R39。r39。 p=XorP(leftpLRPtr)。 while(p!=NULL){ VisitingData(pdata)。){ p=。||d==39。 if(d==39。 // 指針異或函數(shù)XorP返回指針p和q的異或值 假設在算法描述語言中引入指針的二元運算異或若a和b為指針則a⊕b的運算結果仍為原指針類型且 a⊕(a⊕b)=(a⊕a)⊕b=b (a⊕b)⊕b=a⊕(b⊕b)=a則可利用一個指針域來實現(xiàn)雙向鏈表L鏈表L中的每個結點只含兩個域：data域和LRPtr域其中LRPtr域存放該結點的左鄰與右鄰結點指針（不存在時為NULL）的異或則可實現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作試寫一算法按任一方向依次輸出鏈表中各元素的值　　解：Status TraversingLinkList(XorLinkedList amp。 //分別指向鏈表的左側和右端 } XorLinkedList。 } XorNode *XorPointer。} 異或指針雙向鏈表類型XorLinkedList和指針異或函數(shù)XorP定義為： typedef struct XorNode { char data。 free(q)。 pt3=pt3next。 qnext=pt3next。 } else{ q=p。 pt2next=q。 p=pnext。z39。amp。a39。Z39。amp。A39。 pt1=pt1next。 qnext=pt1next。){ q=p。 pdata=39。 amp。 while(p){ if(pdata=39。 pt2=s2。 p=Lnext。s2LinkList amp。LLinkList amp。 return OK。 p=pnext。 while(p!=L){ ppre=q。 q=L。} // 將單循環(huán)鏈表改成雙向鏈表Status ListCirToDu(DuLinkList amp。 Lnext=p。 pdata=e。 p=(DuLinkList)malloc(sizeof(DuLNode))。} // 向循環(huán)鏈表中插入一個結點Status ListInsert_DL(DuLinkList amp。 Lnext=L。 if(!L) exit(OVERFLOW)。} 已知有一個單向循環(huán)鏈表其每個結點中含三個域：predata和next其中data為數(shù)據(jù)域next為指向后繼結點的指針域pre也為指針域但它的值為空試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表即使pre成為指向前驅結點的指針域　　解：// 建立一個空的循環(huán)鏈表Status InitList_DL(DuLinkList amp。 free(p)。 p=pnext。 p=Snext。 if(S==Snext)return ERROR。} 假設某個單向循環(huán)鏈表的長度大于1且表中既無頭結點也無頭指針已知s為指向鏈表中某個結點的指針試編寫算法在鏈表中刪除指針s所指結點的前驅結點　　解：// 在單循環(huán)鏈表S中刪除S的前驅結點Status ListDelete_CL(LinkList amp。 free(pb)。 free(pt)。 pb=pbnext。 free(pt)。 pa=panext。 pa=panext。 free(pt)。 pb=pbnext。amp。 pb=pbnext。 // 保存pa的前驅指針 qb=pb。 pb=B。B){ LinkList papbqaqbpt。} // 求集合AB結果放在A表中并刪除B表Status ListMinus_L(LinkList amp。C){ ListCross_L(BC)。ALinkList amp。 ListMinus_L(ATempD)。 InitList_Sq(Temp)。BSqList amp。DS