【文章內(nèi)容簡介】 } } while(pa){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } while(pb){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } pb=B。 free(pb)。 return OK。} 已知A，B和C為三個遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實(shí)現(xiàn)上述操作的算法，并分析你的算法的時間復(fù)雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。解：// 在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中Status ListUnion_Sq(SqList amp。D,SqList amp。A,SqList amp。B,SqList amp。C){ SqList Temp。 InitList_Sq(Temp)。ListCross_L(B,C,Temp)。 ListMinus_L(A,Temp,D)。} 。試對單鏈表編寫算法，請釋放A表中的無用結(jié)點(diǎn)空間。解：// 在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，并釋放B、CStatus ListUnion_L(LinkList amp。A,LinkList amp。B,LinkList amp。C){ ListCross_L(B,C)。 ListMinus_L(A,B)。}// 求集合AB，結(jié)果放在A表中，并刪除B表Status ListMinus_L(LinkList amp。A,LinkList amp。B){ LinkList pa,pb,qa,qb,pt。 pa=A。 pb=B。 qa=pa。 // 保存pa的前驅(qū)指針 qb=pb。 // 保存pb的前驅(qū)指針 pa=panext。 pb=pbnext。 while(paamp。amp。pb){ if(pbdatapadata){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } else if(pbdatapadata){ qa=pa。 pa=panext。 } else{ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } } while(pb){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } pb=B。 free(pb)。 return OK。} 假設(shè)某個單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。解：// 在單循環(huán)鏈表S中刪除S的前驅(qū)結(jié)點(diǎn)Status ListDelete_CL(LinkList amp。S){ LinkList p,q。 if(S==Snext)return ERROR。 q=S。 p=Snext。 while(pnext!=S){ q=p。 p=pnext。 } qnext=pnext。 free(p)。 return OK。} 已知有一個單向循環(huán)鏈表，其每個結(jié)點(diǎn)中含三個域：pre，data和next，其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，pre也為指針域，但它的值為空，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使pre成為指向前驅(qū)結(jié)點(diǎn)的指針域。解：// 建立一個空的循環(huán)鏈表Status InitList_DL(DuLinkList amp。L){ L=(DuLinkList)malloc(sizeof(DuLNode))。 if(!L) exit(OVERFLOW)。 Lpre=NULL。 Lnext=L。 return OK。} // 向循環(huán)鏈表中插入一個結(jié)點(diǎn)Status ListInsert_DL(DuLinkList amp。L,ElemType e){ DuLinkList p。 p=(DuLinkList)malloc(sizeof(DuLNode))。 if(!p) return ERROR。 pdata=e。 pnext=Lnext。 Lnext=p。 return OK。} // 將單循環(huán)鏈表改成雙向鏈表Status ListCirToDu(DuLinkList amp。L){ DuLinkList p,q。 q=L。 p=Lnext。 while(p!=L){ ppre=q。 q=p。 p=pnext。 } if(p==L) ppre=q。 return OK。} 已知由一個線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其他字符），試編寫算法將該線性表分割為三個循環(huán)鏈表，其中每個循環(huán)鏈表表示的線性表中均只含一類字符。解：// 將單鏈表L劃分成3個單循環(huán)鏈表Status ListDivideInto3CL(LinkList amp。L,LinkList amp。s1,LinkList amp。s2,LinkList amp。s3){ LinkList p,q,pt1,pt2,pt3。 p=Lnext。 pt1=s1。 pt2=s2。 pt3=s3。 while(p){ if(pdata=39。039。 amp。amp。 pdata=39。939。){ q=p。 p=pnext。 qnext=pt1next。 pt1next=q。 pt1=pt1next。 } else if((pdata=39。A39。 amp。amp。 pdata=39。Z39。) || (pdata=39。a39。 amp。amp。 pdata=39。z39。)){ q=p。 p=pnext。 qnext=pt2next。 pt2next=q。 pt2=pt2next。 } else{ q=p。 p=pnext。 qnext=pt3next。 pt3next=q。 pt3=pt3next。 } } q=L。 free(q)。 return OK。}，“異或指針雙向鏈表”類型XorLinkedList和指針異或函數(shù)XorP定義為：typedef struct XorNode { char data。 struct XorNode *LRPtr。} XorNode, *XorPointer。typede struct { //無頭結(jié)點(diǎn)的異或指針雙向鏈表 XorPointer Left, Right。 //分別指向鏈表的左側(cè)和右端} XorLinkedList。XorPointer XorP(XorPointer p, XorPointer q)。// 指針異或函數(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則可利用一個指針域來實(shí)現(xiàn)雙向鏈表L。鏈表L中的每個結(jié)點(diǎn)只含兩個域：data域和LRPtr域，其中LRPtr域存放該結(jié)點(diǎn)的左鄰與右鄰結(jié)點(diǎn)指針（不存在時為NULL）的異或。，則可實(shí)現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依次輸出鏈表中各元素的值。解：Status TraversingLinkList(XorLinkedList amp。L,char d){ XorPointer p,left,right。 if(d==39。l39。||d==39。L39。){ p=。 left=NULL。 while(p!=NULL){ VisitingData(pdata)。 left=p。 p=XorP(left,pLRPtr)。 } } else if(d==39。r39。||d==39。R39。){ p=。 right=NULL。 while(p!=NULL){ VisitingData(pdata)。 right=p。 p=XorP(pLRPtr,right)。 } } else return ERROR。 return OK。} ，寫出在第i個結(jié)點(diǎn)之前插入一個結(jié)點(diǎn)的算法。 ，寫出刪除第i個結(jié)點(diǎn)的算法。 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表。試寫一時間復(fù)雜度O(n)的算法，將L改造為。解：// 將雙向鏈表L=(a1,a2,...,an)改造為(a1,a3,...,an,...,a2)Status ListChange_DuL(DuLinkList amp。L){ int i。 DuLinkList p,q,r。 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è)有一個雙向循環(huán)鏈表，每個結(jié)點(diǎn)中除有pre，data和next三個域外，還增設(shè)了一個訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當(dāng)對鏈表進(jìn)行一次Locate(L,x)的操作后，被訪問的結(jié)點(diǎn)（即元素值等于x的結(jié)點(diǎn)）中的頻度域freq的值便增1，同時調(diào)整鏈表中結(jié)點(diǎn)之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)。試編寫符合上述要求的Locate操作的算法。解：DuLinkList ListLocate_DuL(DuLinkList amp。L,ElemType e){ DuLinkList p,q。 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)式采用的順序存儲結(jié)構(gòu)SqPoly定義為typedef struct { int coef。 int exp。} PolyTerm。typedef struct { //多項(xiàng)式的順序存儲結(jié)構(gòu) PolyTerm *data。 int last。} SqPoly。 已知稀疏多項(xiàng)式，其中。試采用存儲量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲結(jié)構(gòu)，編寫求的算法（為給定值），并分析你的算法的時間復(fù)雜度。解：typedef struct{ int coef。 int exp。} PolyTerm。typedef struct{ PolyTerm *data。 int last。} SqPoly。// 建立一個多項(xiàng)式Status PolyInit(SqPoly amp。L){ int i。 PolyTerm *p。 cout請輸入多項(xiàng)式的項(xiàng)數(shù):。 cin。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。 if(!) return ERROR。 p=。 for(i=0。i。i++){ cout請輸入系數(shù):。 cinpcoef。 cout請輸入指數(shù):。 cinpexp。 p++。 } return OK。} // 求多項(xiàng)式的值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é)果多項(xiàng)式存放在新辟