(完整版)严蔚敏数据结构题集(C语言版)答案 下载本文

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->datadata){ pt=pb;

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; }