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

解：

// 将合并逆置后的结果放在C表中，并删除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) {

LinkList pa,pb,qa,qb; pa=A; pb=B;

qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; A->next=NULL; C=A;

while(pa&&pb){

if(pa->datadata){ qa=pa;

pa=pa->next;

qa->next=A->next; //将当前最小结点插入A表表头 A->next=qa; } else{

qb=pb;

pb=pb->next;

qb->next=A->next; //将当前最小结点插入A表表头 A->next=qb; } }

while(pa){ qa=pa;

pa=pa->next;

qa->next=A->next; A->next=qa; }

while(pb){ qb=pb;

pb=pb->next;

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

2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即

精选

同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。

解：

// 将A、B求交后的结果放在C表中

Status ListCross_Sq(SqList &A,SqList &B,SqList &C) {

int i=0,j=0,k=0;

while(i

if(A.elem[i]>B.elem[j]) j++; else{

ListInsert_Sq(C,k,A.elem[i]); i++; k++; } }

return OK; }

2.26 要求同2.25题。试对单链表编写求C的算法。

解：

// 将A、B求交后的结果放在C表中，并删除B表

Status ListCross_L(LinkList &A,LinkList &B,LinkList &C) {

LinkList pa,pb,qa,qb,pt; pa=A; pb=B;

qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; C=A;

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{

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.27 对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。

(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；

(2) 利用A表空间存放表C。 解： (1)

// A、B求交，然后删除相同元素，将结果放在C表中

Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C) {

int i=0,j=0,k=0;

while(i

if(A.elem[i]>B.elem[j]) j++; else{

if(C.length==0){

ListInsert_Sq(C,k,A.elem[i]); k++; } else

精选

if(C.elem[C.length-1]!=A.elem[i]){ ListInsert_Sq(C,k,A.elem[i]); k++; } i++; } }

return OK; } (2)

// A、B求交，然后删除相同元素，将结果放在A表中 Status ListCrossDelSame_Sq(SqList &A,SqList &B) {

int i=0,j=0,k=0;

while(i

if(A.elem[i]>B.elem[j]) j++; else{

if(k==0){

A.elem[k]=A.elem[i]; k++; } else

if(A.elem[k]!=A.elem[i]){ A.elem[k]=A.elem[i]; k++; } i++; } }

A.length=k; return OK; }

2.28 对2.25题的条件作以下两点修改，对单链表重新编写求得表C的算法。

(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；

(2) 利用原表（A表或B表）中的结点构成表C，并释放A表中的无用结点空间。

解： (1)

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

Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkList &C) {

精选

LinkList pa,pb,qa,qb,pt; pa=A; pb=B;

qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; C=A;

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;

精选