数据结构考研分类复习真题 第二章 答案[14]

．[题目分析]本组题有个本质上都是链表的合并操作合并中有各种条件与前组题不同的是叙述上是用线性表代表集合而操作则是求集合的并交差(A∪BA∩BAB)等本题与上面．()基本相同不同之处．()中链表是非递减有序(可能包含相等元素)本题是元素递增有序(不准有相同元素)因此两表中合并时如有元素值相等元素则应删掉一个

LinkedList Union(LinkedList hahb)∥线性表A和B代表两个集合以链式存储结构存储元素递增有序ha和hb分别是其链表的头指针本算法求A和B的并集A∪B仍用线性表表示结果链表元素也是递增有序

{ pa=ha>next;pb=hb>next;∥设工作指针pa和pb

pc=ha;∥pc为结果链表当前结点的前驱指针

while(pa&&pb)

if(pa>data<pb>data)

{pc>next=pa;pc=pa;pa=pa>next;}

else if(pa>data>pb>data)

{pc>next=pb;pc=pb;pb=pb>next;}

else∥处理pa>data=pb>data

{pc>next=pa;pc=pa;pa=pa>next;

u=pb;pb=pb>next;free(u);}

if(pa) pc>next=pa;∥ 若ha表未空则链入结果表

else pc>next=pb;∥若hb表未空则链入结果表

free(hb); ∥释放hb头结点

return(ha);

}∥算法Union结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []