【正文】 一時(shí)間復(fù)雜度O(n)的算法將L改造為　　解：// 將雙向鏈表L=(a1a2...an)改造為(a1a3...an...a2)Status ListChange_DuL(DuLinkList amp。L){ int i。 DuLinkList pqr。 p=Lnext。 r=Lpre。 i=1。 while(p!=r){ if(i%2==0){ q=p。 p=pnext。 // 刪除結(jié)點(diǎn) qprenext=qnext。 qnextpre=qpre。 // 插入到頭結(jié)點(diǎn)的左面 qpre=rnextpre。 rnextpre=q。 qnext=rnext。 rnext=q。 } else p=pnext。 i++。 } return OK。} 設(shè)有一個(gè)雙向循環(huán)鏈表每個(gè)結(jié)點(diǎn)中除有predata和next三個(gè)域外還增設(shè)了一個(gè)訪問(wèn)頻度域freq在鏈表被起用之前頻度域freq的值均初始化為零而每當(dāng)對(duì)鏈表進(jìn)行一次Locate(Lx)的操作后被訪問(wèn)的結(jié)點(diǎn)（即元素值等于x的結(jié)點(diǎn)）中的頻度域freq的值便增1同時(shí)調(diào)整鏈表中結(jié)點(diǎn)之間的次序使其按訪問(wèn)頻度非遞增的次序順序排列以便始終保持被頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)試編寫(xiě)符合上述要求的Locate操作的算法　　解：DuLinkList ListLocate_DuL(DuLinkList amp。LElemType e){ DuLinkList pq。 p=Lnext。 while(p!=L amp。amp。 pdata!=e) p=pnext。 if(p==L) return NULL。 else{ pfreq++。 // 刪除結(jié)點(diǎn) pprenext=pnext。 pnextpre=ppre。 // 插入到合適的位置 q=Lnext。 while(q!=L amp。amp。 qfreqpfreq) q=qnext。 if(q==L){ pnext=qnext。 qnext=p。 ppre=qpre。 qpre=p。 } else{ // 在q之前插入 pnext=qprenext。 qprenext=p。 ppre=qpre。 qpre=p。 } return p。 }} 稀疏多項(xiàng)式采用的順序存儲(chǔ)結(jié)構(gòu)SqPoly定義為 typedef struct { int coef。 int exp。 } PolyTerm。 typedef struct { //多項(xiàng)式的順序存儲(chǔ)結(jié)構(gòu) PolyTerm *data。 int last。 } SqPoly。 已知稀疏多項(xiàng)式其中試采用存儲(chǔ)量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲(chǔ)結(jié)構(gòu)編寫(xiě)求的算法（為給定值）并分析你的算法的時(shí)間復(fù)雜度　　解：typedef struct{ int coef。 int exp。} PolyTerm。typedef struct{ PolyTerm *data。 int last。} SqPoly。// 建立一個(gè)多項(xiàng)式Status PolyInit(SqPoly amp。L){ int i。 PolyTerm *p。 cout請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù):。 cin。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。 if(!) return ERROR。 p=。 for(i=0。i。i++){ cout請(qǐng)輸入系數(shù):。 cinpcoef。 cout請(qǐng)輸入指數(shù):。 cinpexp。 p++。 } return OK。} // 求多項(xiàng)式的值double PolySum(SqPoly amp。Ldouble x0){ double Pnx。 int ij。 PolyTerm *p。 p=。 for(i=0Pn=0。i。i++p++){ for(j=0x=1。jpexp。j++) x=x*x0。 Pn=Pn+pcoef*x。 } return Pn。} 編寫(xiě)求的算法將結(jié)果多項(xiàng)式存放在新辟的空間中并分析你的算法的時(shí)間復(fù)雜度　　解：// 求兩多項(xiàng)式的差Status PolyMinus(SqPoly amp。LSqPoly amp。L1SqPoly amp。L2){ PolyTerm *p*p1*p2。 p=。 p1=。 p2=。 int i=0j=0k=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。} 稀疏多項(xiàng)式采用的循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)LinkedPoly定義為 typedef struct PolyNode { PolyTerm data。 struct PolyNode *next。 } PolyNode *PolyLink。 typedef PolyLink LinkedPoly。 試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)編寫(xiě)求其導(dǎo)函數(shù)的方法要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)多項(xiàng)式同時(shí)釋放所有無(wú)用結(jié)點(diǎn)　　解：Status PolyDifferential(LinkedPoly amp。L){ LinkedPoly pqpt。 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。} 試編寫(xiě)算法將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)并要求利用原鏈表中的結(jié)點(diǎn)空間構(gòu)成這兩個(gè)鏈表　　解：// 將單鏈表L劃分成2個(gè)單循環(huán)鏈表Status ListDivideInto2CL(LinkedPoly amp。LLinkedPoly amp。L1){ LinkedPoly pp1qpt。 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章 棧和隊(duì)列 (b)所示鐵道進(jìn)行車(chē)廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道）則請(qǐng)回答： (1) 如果進(jìn)站的車(chē)廂序列為123則可能得到的出站車(chē)廂序列是什么？ (2) 如果進(jìn)站的車(chē)廂序列為123456則能否得到435612和135426的出站序列并請(qǐng)說(shuō)明為什么不能得到或者如何得到（即寫(xiě)出以 39。S39。表示進(jìn)棧和以 39。X39。表示出棧的棧操作序列）　　解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列但不能得到435612的出站序列因?yàn)?356出站說(shuō)明12已經(jīng)在棧中1不可能先于2出棧 簡(jiǎn)述棧和線性表的差別　　解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表 寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char） void main() { Stack S。 char xy。 InitStack(S)。 x= 39。c39。 y= 39。k39。 Push(Sx)。 Push(S 39。a39。)。 Push(Sy)。 Pop(Sx)。 Push(S 39。t39。)。 Push(Sx)。 Pop(Sx)。 Push(S 39。s39。)。 while(!StackEmpty(S)) { Pop(Sy)。 printf(y)。 } printf(x)。 }　　解：stack 簡(jiǎn)述以下算法的功能（棧的元素類型SElemType為int） (1) status algo1(Stack S) { int inA[255]。 n=0。 while(!StackEmpty(S)) { n++。 Pop(SA[n])。 } for(i=1。i=n。i++) Push(SA[i])。 } (2) status algo2(Stack Sint e) { Stack T。 int d。 InitStack(T)。 while(!StackEmpty(S)){ Pop(Sd)。 if(d!=e) Push(Td)。 } while(!StackEmpty(T)){ Pop(Td)。 Push(Sd)。 } }　　解：(1) 棧中的數(shù)據(jù)元素逆置 (2) 如果棧中存在元素e將其從棧中清除 假設(shè)以S和X分別表示入棧和出棧的操作則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列稱可以操作的序列為合法序列（例如SXSX為合法序列SXXS為非法序列）試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則并證明：兩個(gè)不同的合法（棧操作）序列（對(duì)同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體而不是值）序列　　解：任何前n個(gè)序列中S的個(gè)數(shù)一定大于X的個(gè)數(shù) 設(shè)兩個(gè)合法序列為： T1=S......X......S...... T2=S......X......X...... 假定前n個(gè)操作都相同從第n+1個(gè)操作開(kāi)始為序列不同的起始操作點(diǎn)由于前n個(gè)操作相同故此時(shí)兩個(gè)棧（不妨為棧A、B）的存儲(chǔ)情況完全相同假設(shè)此時(shí)棧頂元素均為a 第n+1個(gè)操作不同不妨T1的第n+1個(gè)操作為ST2的第n+1個(gè)操作為XT1為入棧操作假設(shè)將b壓棧則T1的輸出順序一定是先b后a；而T2將a退棧則其輸出順序一定是先a后b由于T1的輸出為......ba......而T2的輸出順序?yàn)?.....ab......說(shuō)明兩個(gè)不同的合法棧操作序列的輸出元素的序列一定不同 試證明：若借助棧由輸入序列12...n得到的輸出序列為(它是輸入序列的一個(gè)排列)則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使　　解：因?yàn)檩斎胄蛄惺菑男〉酱笈帕械乃匀魟t可以理解為通過(guò)輸入序列可以得到輸出序列顯然通過(guò)序列123是無(wú)法得到312的所以不可能存在著ijk使 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算(↑)優(yōu)先關(guān)系的慣例畫(huà)出對(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棧
輸入字符
主要操作
1
AB*C/D+E^F
PUSH(OPNDA)
2
A
B*C/D+E^F
PUSH(OPTR)
3