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

．[题目分析] 留下三个链表中公共数据首先查找两表A和B中公共数据再去C中找有无该数据要消除重复元素应记住前驱要求时间复杂度O(m+n+p)在查找每个链表时指针不能回溯

LinkedList Common(LinkedList ABC)∥AB和C是三个带头结点且结点元素值非递减排列的有序表本算法使A表仅留下三个表均包含的结点且结点值不重复释放所有结点

{pa=A>next;pb=B>next;pc=C>next;∥papb和pc分别是AB和C三个表的工作指针

pre=A;∥pre是A表中当前结点的前驱结点的指针

while(pa && pb && pc)∥当AB和C表均不空时查找三表共同元素

{ while(pa && pb)

if(pa>data<pb>data){u=pa;pa=pa>next;free(u);}∥结点元素值小时后移指针

else if(pa>data> pb>data)pb=pb>next;

else if (pa && pb) ∥处理A和B表元素值相等的结点

{while(pc && pc>data<pa>data)pc=pc>next;

if(pc)

{if(pc>data>pa>data)∥pc当前结点值与pa当前结点值不等pa后移指针

{u=pa;pa=pa>next;free(u);}

else∥pcpa和pb对应结点元素值相等

{if(pre==A){ pre>next=pa;pre=pa;pa=pa>next}∥结果表中第一个结点

else if(pre>data==pa>data)∥(处理)重复结点不链入A表

{u=pa;pa=pa>next;free(u);}

else {pre>next=pa;pre=pa;pa=pa>next;}∥将新结点链入A表

pb=pb>next;pc=pc>next;∥链表的工作指针后移

}

}∥else pcpa和pb对应结点元素值相等

if(pa==null)pre>next=null;∥原A表已到尾置新A表表尾

else∥处理原A表未到尾而B或C到尾的情况

{pre>next=null;∥置A表表尾标记

while(pa!=null)∥删除原A表剩余元素

{u=pa;pa=pa>next;free(u);}

[算法讨论] 算法中A表B表和C表均从头到尾(严格说BC中最多一个到尾)遍历一遍算法时间复杂度符合O(m+n+p)算法主要由while(pa && pb && pc)控制三表有一个到尾则结束循环算法中查到A表与B表和C表的公共元素后又分三种情况处理一是三表中第一个公共元素值相等的结点;第二种情况是尽管不是第一结点但与前驱结点元素值相同不能成为结果表中的结点;第三种情况是新结点与前驱结点元素值不同应链入结果表中前驱指针也移至当前结点以便与以后元素值相同的公共结点进行比较算法最后要给新A表置结尾标记同时若原A表没到尾还应释放剩余结点所占的存储空间

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