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

()本题基本与()相同但要求无重复元素故在算法中待合并结点数据要与其前驱比较只有在与前驱数据不同时才并入链表其核心语句段如下

pa=L>next;pb=L>next;∥papb是两链表的工作指针

pc=L;∥L作结果链表的头指针

while(pa&&pb)

if(pa>data<pb>data) {u=pa;pa=pa>next;free(u);}∥删除L表多余元素

else if (pa>data>pb>data) pb=pb>next;∥pb指针后移

else∥处理交集元素

{if(pc==L) {pc>next=pa;pc=pa;pa=pa>next;}∥处理第一个相等的元素

else if(pc>data==pa>data){ u=pa;pa=pa>next;free(u);}∥重复元素不进入L表

else{ pc>next=pa;pc=pa;pa=pa>next;}∥交集元素并入结果表

} ∥while

while(pa) {u=pa;pa=pa>next;free(u);}∥ 删L表剩余元素

pc>next=null; ∥置结果链表尾

注 本算法中对L表未作释放空间的处理

() 本题与上面()算法相同只是结果表要另辟空间

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