【正文】 } }解：隊(duì)列逆置 若以1234作為雙端隊(duì)列的輸入序列，試分別求出滿足以下條件的輸出序列： (1) 能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列。 } while(!StackEmpty(S)) { Pop(S, d)。 while(!QueueEmpty(Q)) { DeQueue(Q, d)。 int d。 void algo3(Queue amp。 } coutx。 While(!QueueEmpty(Q)) { DeQueue(Q,y)。 DeQueue(Q, x)。 DeQueue(Q, x)。 EnQueue(Q, ‘r’)。 char x= ‘e’, y= ‘c’。 void main() { Queue Q。隊(duì)列也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。} 簡(jiǎn)述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。 coutsumendl。 while(!StackEmpty(s)){ Pop(s,x)。 Push(s,x)。 int x。sum){ Stack s。 } coutsum。 else { test(sum)。 cinx。 void test(int amp。 } return。 }解：void ditui(int j){ if(j1){ coutj。 i = n。解： 試將下列遞推過程改寫為遞歸過程。所以不可能存在著ijk使。解：。由于T1的輸出為……ba……，而T2的輸出順序?yàn)椤璦b……，說明兩個(gè)不同的合法棧操作序列的輸出元素的序列一定不同。第n+1個(gè)操作不同，不妨T1的第n+1個(gè)操作為S，T2的第n+1個(gè)操作為X。設(shè)兩個(gè)合法序列為：T1=S……X……S…… T2=S……X……X…… 假定前n個(gè)操作都相同，從第n+1個(gè)操作開始，為序列不同的起始操作點(diǎn)。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對(duì)同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。 } }解：(1) 棧中的數(shù)據(jù)元素逆置 (2) 如果棧中存在元素e，將其從棧中清除 假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。 } while(!StackEmpty(T)){ Pop(T,d)。 while(!StackEmpty(S)){ Pop(S,d)。 int d。i++) Push(S,A[i])。 } for(i=1。 while(!StackEmpty(S)) { n++。(1) status algo1(Stack S) { int i,n,A[255]。 } printf(x)。 while(!StackEmpty(S)) { Pop(S,y)。 Pop(S,x)。 Push(S, ‘t’)。 Push(S,y)。 Push(S,x)。 x= ‘c’。 char x,y。 寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）。解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。因?yàn)?356出站說明12已經(jīng)在棧中，1不可能先于2出棧。}第3章 棧和隊(duì)列 (b)所示鐵道進(jìn)行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請(qǐng)回答：(1) 如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？(2) 如果進(jìn)站的車廂序列為123456，則能否得到435612和135426的出站序列，并請(qǐng)說明為什么不能得到或者如何得到（即寫出以 ‘S’表示進(jìn)棧和以 ‘X’表示出棧的棧操作序列）。 p=pnext。 p1=p1next。 ptnext=p1next。 p=pnext。 p1=L1。 q=L。L,LinkedPoly amp。} 試編寫算法，將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間構(gòu)成這兩個(gè)鏈表。 p=pnext。 p。 free(pt)。 p=pnext。 p=Lnext。L){ LinkedPoly p,q,pt。 試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的方法，要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)多項(xiàng)式，同時(shí)釋放所有無用結(jié)點(diǎn)。} PolyNode, *PolyLink。}，稀疏多項(xiàng)式采用的循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)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=。L1,SqPoly amp。解：// 求兩多項(xiàng)式的差Status PolyMinus(SqPoly amp。 } return Pn。j++) x=x*x0。i++,p++){ for(j=0,x=1。 for(i=0,Pn=0。 PolyTerm *p。L,double x0){ double Pn,x。 } return OK。 cinpexp。 cinpcoef。i。 p=。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。 cout請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù):。L){ int i。} SqPoly。typedef struct{ PolyTerm *data。 int exp。試采用存儲(chǔ)量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲(chǔ)結(jié)構(gòu)，編寫求的算法（為給定值），并分析你的算法的時(shí)間復(fù)雜度。} SqPoly。typedef struct { //多項(xiàng)式的順序存儲(chǔ)結(jié)構(gòu) PolyTerm *data。 int exp。 } return p。 ppre=qpre。 } else{ // 在q之前插入 pnext=qprenext。 ppre=qpre。 if(q==L){ pnext=qnext。amp。 // 插入到合適的位置 q=Lnext。 // 刪除結(jié)點(diǎn) pprenext=pnext。 if(p==L) return NULL。amp。 p=Lnext。解：DuLinkList ListLocate_DuL(DuLinkList amp。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當(dāng)對(duì)鏈表進(jìn)行一次Locate(L,x)的操作后，被訪問的結(jié)點(diǎn)（即元素值等于x的結(jié)點(diǎn)）中的頻度域freq的值便增1，同時(shí)調(diào)整鏈表中結(jié)點(diǎn)之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)。 } return OK。 } else p=pnext。 qnext=rnext。 // 插入到頭結(jié)點(diǎn)的左面 qpre=rnextpre。 // 刪除結(jié)點(diǎn) qprenext=qnext。 while(p!=r){ if(i%2==0){ q=p。 r=Lpre。 DuLinkList p,q,r。解：// 將雙向鏈表L=(a1,a2,...,an)改造為(a1,a3,...,an,...,a2)Status ListChange_DuL(DuLinkList amp。 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表。} ，寫出在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)的算法。 } } else return ERROR。 right=p。 right=NULL。R39。r39。 p=XorP(left,pLRPtr)。 while(p!=NULL){ VisitingData(pdata)。){ p=。||d==39。 if(d==39。解：Status TraversingLinkList(XorLinkedList amp。則可實(shí)現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作。// 指針異或函數(shù)XorP返回指針p和q的異或值 假設(shè)在算法描述語言中引入指針的二元運(yùn)算“異或”，若a和b為指針，則a⊕b的運(yùn)算結(jié)果仍為原指針類型，且 a⊕(a⊕b)=(a⊕a)⊕b=b (a⊕b)⊕b=a⊕(b⊕b)=a則可利用一個(gè)指針域來實(shí)現(xiàn)雙向鏈表L。 //分別指向鏈表的左側(cè)和右端} 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。s2,LinkList amp。L,LinkList amp。} 已知由一個(gè)線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其他字符），試編寫算法將該線性表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符。 } if(p==L) ppre=q。 q=p。 p=Lnext。L){ DuLinkList p,q。 return OK。 pnext=Lnext。 if(!p) return ERROR。L,ElemType e){ DuLinkList p。 return OK。 Lpre=NULL。L){ L=(DuLinkList)malloc(sizeof(DuLNode))。} 已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：pre，data和next，其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，pre也為指針域，但它的值為空，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使pre成為指向前驅(qū)結(jié)點(diǎn)的指針域。 free(p)。 p=pnext。 p=Snext。 if(S==Snext)return ERROR。解：// 在單循環(huán)鏈表S中刪除S的前驅(qū)結(jié)點(diǎn)Status ListDelete_CL(LinkList amp。} 假設(shè)某個(gè)單向循環(huán)鏈表的長(zhǎng)度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。 free(pb)。 free(pt)。 pb=pbnext。 free(pt)。 pa=panext。 pa=panext。 free(pt)。 pb=pbnext。amp。 pb=pbnext。 // 保存pa的前驅(qū)指針 qb=pb。 pb=B。B){ LinkList pa,pb,qa,qb,pt。}// 求集合AB，結(jié)果放在A表中，并刪除B表Status ListMinus_L(LinkList amp。C){ ListCross_L(B,C)。A,LinkList amp。試對(duì)單鏈表編寫算法，請(qǐng)釋放A表中的無用結(jié)點(diǎn)空間。 ListMinus_L(A,Temp,D)。 InitList_Sq(Temp)。B,SqList amp。D,SqList amp。試對(duì)順序表編寫實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。 return OK。 } pb=B。 qbnext=pb。 } while(pb){ pt=pb。 qanext=pa。 } } } while(pa){ pt=pa。 } else{ qa=pa。 qanext=pa。 } else{