《数据结构》习题集答案(C语言版)严蔚敏

qb->next=pb; free(pt); } pb=B; free(pb); return OK; } (2)

// A、B求交,结果放在A表中,并删除相同元素

Status ListCrossDelSame_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(pa->datadata){ pt=pa;

pa=pa->next; qa->next=pa; free(pt); } else

if(pa->data>pb->data){ pt=pb;

pb=pb->next; qb->next=pb; free(pt); }

else{

if(pa->data==qa->data){ pt=pa;

pa=pa->next; qa->next=pa; free(pt); } else{

qa=pa;

pa=pa->next; } }

精选

}

while(pa){ 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.29 已知A,B和C为三个递增有序的线性表,现要求对A表作如下操作:删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法,并分析你的算法的时间复杂度(注意:题中没有特别指明同一表中的元素值各不相同)。

解:

// 在A中删除既在B中出现又在C中出现的元素,结果放在D中 Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C) {

SqList Temp;

InitList_Sq(Temp);

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

else{ q=p;

p=p->next;

q->next=pt3->next; pt3->next=q; pt3=pt3->next; } } q=L; free(q); return OK;

精选

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4