数据结构与算法线性表复习习题【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的异或值

[] [] []