数据结构题集（C语言版）答案 - 严蔚敏编著

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