严蔚敏版数据结构课后习题答案-完整版

最新精品文档，知识共享！

}

LinkList pa,pb,qa,qb; pa=A->next; pb=B->next; C=A;

while(pa&&pb){ }

if(!pa)qb->next=pb; pb=B; free(pb); return OK;

qa=pa;

qb=pb;

pa=pa->next; pb=pb->next; qb->next=qa->next; qa->next=qb;

2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造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){ } else{

qb=pb; pb=pb->next;

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

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

最新精品文档，知识共享！

}

}

}

A->next=qb;

while(pa){ }

while(pb){ } pb=B; free(pb); return OK;

qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; qa=pa; pa=pa->next; qa->next=A->next; A->next=qa;

2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递

最新精品文档，知识共享！

增有序排列。试对顺序表编写求C的算法。

解：

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

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

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

解：

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

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

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

while(i

return OK;

if(A.elem[i]

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

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