ListCross_L(B,C,Temp); }
2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。
解：
// 在A中删除既在B中出现又在C中出现的元素，并释放B、C Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C) { }
// 求集合A-B，结果放在A表中，并删除B表 Status ListMinus_L(LinkList &A,LinkList &B) {
LinkList pa,pb,qa,qb,pt; pa=A; pb=B; qa=pa; qb=pb;
// 保存pa的前驱指针 // 保存pb的前驱指针
ListCross_L(B,C); ListMinus_L(A,B); ListMinus_L(A,Temp,D);
pa=pa->next; pb=pb->next; while(pa&&pb){ }
while(pb){
pt=pb; pb=pb->next; qb->next=pb;
if(pb->data
if(pb->data>pa->data){ } else{ }
pt=pa; pa=pa->next; qa->next=pa; free(pt); qa=pa; pa=pa->next; pt=pb; pb=pb->next; qb->next=pb; free(pt);
}
}
free(pt);
pb=B; free(pb); return OK;
2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
解：
// 在单循环链表S中删除S的前驱结点 Status ListDelete_CL(LinkList &S) { }
2.32 已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。
解：
// 建立一个空的循环链表
Status InitList_DL(DuLinkList &L) { }
// 向循环链表中插入一个结点
Status ListInsert_DL(DuLinkList &L,ElemType e) {
DuLinkList p;
p=(DuLinkList)malloc(sizeof(DuLNode)); if(!p) return ERROR; p->data=e;
L=(DuLinkList)malloc(sizeof(DuLNode)); if(!L) exit(OVERFLOW); L->pre=NULL; L->next=L; return OK; LinkList p,q;
if(S==S->next)return ERROR; q=S; p=S->next;
while(p->next!=S){ }
q->next=p->next; free(p); return OK;
q=p; p=p->next;
}
p->next=L->next; L->next=p; return OK;
// 将单循环链表改成双向链表 Status ListCirToDu(DuLinkList &L) { }
DuLinkList p,q; q=L; p=L->next; while(p!=L){ }
if(p==L) p->pre=q; return OK;
p->pre=q; q=p; p=p->next;
2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。
解：
// 将单链表L划分成3个单循环链表
Status ListDivideInto3CL(LinkList &L,LinkList &s1,LinkList &s2,LinkList &s3) {
LinkList p,q,pt1,pt2,pt3; p=L->next; pt1=s1; pt2=s2; pt3=s3; while(p){
if(p->data>='0' && p->data<='9'){ } else
if((p->data>='A' && p->data<='Z') ||
(p->data>='a' && p->data<='z')){
q=p; p=p->next;
q->next=pt1->next; pt1->next=q; pt1=pt1->next;
q=p; p=p->next;
q->next=pt2->next; pt2->next=q;
}
}
}
pt2=pt2->next;
else{ }
q=p; p=p->next;
q->next=pt3->next; pt3->next=q; pt3=pt3->next;
q=L; free(q); return OK;
在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为： typedef struct
XorNode {
char data; struct
XorNode *LRPtr;
//无头结点的异或指针双向链表 Left, Right;
//分别指向链表的左侧和右端
} XorNode, *XorPointer; typede
struct { XorPointer
} XorLinkedList;
XorPointer XorP(XorPointer p, XorPointer q); // 指针异或函数XorP返回指针p和q的异或值
2.34 假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且
a⊕(a⊕b)=(a⊕a)⊕b=b (a⊕b)⊕b=a⊕(b⊕b)=a
则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。
解：
Status TraversingLinkList(XorLinkedList &L,char d) {
XorPointer p,left,right; if(d=='l'||d=='L'){
p=L.Left; left=NULL; while(p!=NULL){ }
VisitingData(p->data); left=p;
p=XorP(left,p->LRPtr);
}
} else
if(d=='r'||d=='R'){ }
else return ERROR;
p=L.Right; right=NULL; while(p!=NULL){ }
VisitingData(p->data); right=p;
p=XorP(p->LRPtr,right);
return OK;
2.35 采用2.34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。 2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。
2.37 设以带头结点的双向循环链表表示的线性表L??a1,a2,?,an?。试写一时间复杂度O(n)的算法，将L改造为L??a1,a3,?,an,?,a4,a2?。
解：
// 将双向链表L=(a1,a2,...,an)改造为(a1,a3,...,an,...,a2) Status ListChange_DuL(DuLinkList &L) {
int i;
DuLinkList p,q,r; p=L->next; r=L->pre; i=1;
while(p!=r){
if(i%2==0){ }
else p=p->next; i++;
q=p; p=p->next; // 删除结点
q->pre->next=q->next; q->next->pre=q->pre; // 插入到头结点的左面 q->pre=r->next->pre; r->next->pre=q; q->next=r->next; r->next=q;
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构及应用算法 课后复习题（附答案 严蔚敏版）(6)在线全文阅读。
相关推荐：