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

       已知有一個單向循環鏈表其每個結點中含三個域predata和next其中data為數據域next為指向後繼結點的指針域pre也為指針域但它的值為空試編寫算法將此單向循環鏈表改為雙向循環鏈表即使pre成為指向前驅結點的指針域

　　解

　　// 建立一個空的循環鏈表

　　Status InitList_DL(DuLinkList &L)

　　{

　　L=(DuLinkList)malloc(sizeof(DuLNode));

　　if(!L) exit(OVERFLOW);

　　L>pre=NULL;

　　L>next=L;

　　return OK;

　　}

　　// 向循環鏈表中插入一個結點

　　Status ListInsert_DL(DuLinkList &LElemType e)

　　{

　　DuLinkList p;

　　p=(DuLinkList)malloc(sizeof(DuLNode));

　　if(!p) return ERROR;

　　p>data=e;

　　p>next=L>next;

　　L>next=p;

　　return OK;

　　}

　　// 將單循環鏈表改成雙向鏈表

　　Status ListCirToDu(DuLinkList &L)

　　{

　　DuLinkList pq;

　　q=L;

　　p=L>next;

　　while(p!=L){

　　p>pre=q;

　　q=p;

　　p=p>next;

　　}

　　if(p==L) p>pre=q;

　　return OK;

　　}

　　 已知由一個線性鏈表表示的線性表中含有三類字符的數據元素（如字母字符數字字符和其他字符）試編寫算法將該線性表分割為三個循環鏈表其中每個循環鏈表表示的線性表中均只含一類字符

　　解

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

　　Status ListDivideIntoCL(LinkList &LLinkList &sLinkList &sLinkList &s)

　　{

　　LinkList pqptptpt;

　　p=L>next;

　　pt=s;

　　pt=s;

　　pt=s;

　　while(p){

　　if(p>data>= && p>data<=){

　　q=p;

　　p=p>next;

　　q>next=pt>next;

　　pt>next=q;

　　pt=pt>next;

　　}

　　else

　　if((p>data>=A && p>data<=Z) ||

　　(p>data>=a && p>data<=z)){

　　q=p;

　　p=p>next;

　　q>next=pt>next;

　　pt>next=q;

　　pt=pt>next;

　　}

　　else{

　　q=p;

　　p=p>next;

　　q>next=pt>next;

　　pt>next=q;

　　pt=pt>next;

　　}

　　}

　　q=L;

　　free(q);

　　return OK;

　　}

　　在題中異或指針雙向鏈表類型XorLinkedList和指針異或函數XorP定義為

　　typedefstructXorNode {

　　char data;

　　structXorNode *LRPtr;

　　} XorNode *XorPointer;

　　typedestruct {//無頭結點的異或指針雙向鏈表

　　XorPointerLeft Right;//分別指向鏈表的左側和右端

　　} XorLinkedList;

　　XorPointer XorP(XorPointer p XorPointer q);

　　// 指針異或函數XorP返回指針p和q的異或值

[]  []  []  

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