发布时间 : 星期四 文章(完整版)严蔚敏数据结构题集(C语言版)答案更新完毕开始阅读6e7832cad6d8d15abe23482fb4daa58da0111c94
ListCross_L(B C
Temp);
ListMinus_L(A Temp D); }
2.30 要求同2.29题 试对单链表编写算法
请释放A表中的无用结点空间
解：
// 在A中删除既在B中出现又在C中出现的元素 并释放B、C
Status ListUnion_L(LinkList &A LinkList &B LinkList &C) {
ListCross_L(B C);
ListMinus_L(A B); }
// 求集合A-B 结果放在A表中 并删除B表
Status ListMinus_L(LinkList &A LinkList &B) {
LinkList pa pb qa qb pt;
pa=A; pb=B;
qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; while(pa&&pb){
if(pb->data
pb=pb->next;
qb->next=pb; free(pt); } else
if(pb->data>pa->data){ qa=pa;
pa=pa->next; } else{
pt=pa;
pa=pa->next; qa->next=pa; free(pt); } }
while(pb){ pt=pb;
pb=pb->next; qb->next=pb; free(pt); } pb=B; free(pb); return OK; }
2.31 假设某个单向循环链表的长度大于1 且表中既无头结点也无头指针
已知s为指向链表中某个结点的指针
试编写算法在链表中删除指针s所指结点的前驱结点
解：
// 在单循环链表S中删除S的前驱结点 Status ListDelete_CL(LinkList &S) {
LinkList p q;
if(S==S->next)return ERROR; q=S;
p=S->next;
while(p->next!=S){ q=p;
p=p->next; }
q->next=p->next;
free(p); return OK; }
2.32 已知有一个单向循环链表 其每个结点中含三个域：pre data和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 &L ElemType 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 p q;
q=L;
p=L->next; while(p!=L){ p->pre=q;
q=p;
p=p->next; }
if(p==L) p->pre=q; return OK; }
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'){ q=p;
p=p->next;
q->next=pt1->next; pt1->next=q; pt1=pt1->next; } else
if((p->data>='A' && p->data<='Z') || (p->data>='a' && p->data<='z')){ q=p;
p=p->next;
q->next=pt2->next; pt2->next=q; pt2=pt2->next; }