數據結構與算法線性表復習習題【6】[3]

       假設在算法描述語言中引入指針的二元運算異或若a和b為指針則a⊕b的運算結果仍為原指針類型且

　　a⊕(a⊕b)=(a⊕a)⊕b=b

　　(a⊕b)⊕b=a⊕(b⊕b)=a

　　則可利用一個指針域來實現雙向鏈表L鏈表L中的每個結點只含兩個域data域和LRPtr域其中LRPtr域存放該結點的左鄰與右鄰結點指針（不存在時為NULL）的異或若設指針LLeft指向鏈表中的最左結點LRight指向鏈表中的最右結點則可實現從左向右或從右向左遍歷此雙向鏈表的操作試寫一算法按任一方向依次輸出鏈表中各元素的值

　　解

　　Status TraversingLinkList(XorLinkedList &Lchar d)

　　{

　　XorPointer pleftright;

　　if(d==l||d==L){

　　p=LLeft;

　　left=NULL;

　　while(p!=NULL){

　　VisitingData(p>data);

　　left=p;

　　p=XorP(leftp>LRPtr);

　　}

　　}

　　else

　　if(d==r||d==R){

　　p=LRight;

　　right=NULL;

　　while(p!=NULL){

　　VisitingData(p>data);

　　right=p;

　　p=XorP(p>LRPtrright);

　　}

　　}

　　else return ERROR;

　　return OK;

　　}

　　 設有一個雙向循環鏈表每個結點中除有predata和next三個域外還增設了一個訪問頻度域freq在鏈表被起用之前頻度域freq的值均初始化為零而每當對鏈表進行一次Locate(Lx)的操作後被訪問的結點（即元素值等於x的結點）中的頻度域freq的值便增同時調整鏈表中結點之間的次序使其按訪問頻度非遞增的次序順序排列以便始終保持被頻繁訪問的結點總是靠近表頭結點試編寫符合上述要求的Locate操作的算法

　　解

　　DuLinkList ListLocate_DuL(DuLinkList &LElemType e)

　　{

　　DuLinkList pq;

　　p=L>next;

　　while(p!=L && p>data!=e)p=p>next;

　　if(p==L) return NULL;

　　else{

　　p>freq++;

　　// 刪除結點

　　p>pre>next=p>next;

　　p>next>pre=p>pre;

　　// 插入到合適的位置

　　q=L>next;

　　while(q!=L && q>freq>p>freq) q=q>next;

　　if(q==L){

　　p>next=q>next;

　　q>next=p;

　　p>pre=q>pre;

　　q>pre=p;

　　}

　　else{

　　// 在q之前插入

　　p>next=q>pre>next;

　　q>pre>next=p;

　　p>pre=q>pre;

　　q>pre=p;

　　}

　　return p;

　　}

　　}

　　 試以循環鏈表作稀疏多項式的存儲結構編寫求其導函數的方法要求利用原多項式中的結點空間存放其導函數多項式同時釋放所有無用結點

　　解

　　Status PolyDifferential(LinkedPoly &L)

　　{

　　LinkedPoly pqpt;

　　q=L;

　　p=L>next;

　　while(p!=L){

　　if(p>dataexp==){

　　pt=p;

　　p=p>next;

　　q>next=p;

　　free(pt);

　　}

　　else{

　　p>datacoef=p>datacoef*p>dataexp;

　　p>dataexp;

　　q=p;

　　p=p>next;

　　}

　　}

　　return OK;

　　}

　　 試編寫算法將一個用循環鏈表表示的稀疏多項式分解成兩個多項式使這兩個多項式中各自僅含奇次項或偶次項並要求利用原鏈表中的結點空間構成這兩個鏈表

　　解

　　// 將單鏈表L劃分成個單循環鏈表

　　Status ListDivideIntoCL(LinkedPoly &LLinkedPoly &L)

　　{

　　LinkedPoly ppqpt;

　　q=L;

　　p=L>next;

　　p=L;

　　while(p!=L){

　　if(p>dataexp%==){

　　pt=p;

　　p=p>next;

　　q>next=p;

　　pt>next=p>next;

　　p>next=pt;

　　p=p>next;

　　}

　　else{

　　q=p;

　　p=p>next;

　　}

　　}

　　return OK;

　　}

[]  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23388.html