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

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

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

　　LinkedList Common(LinkedList A B C)∥A B和C是三个带头结点且结点元素值非递减排列的有序表 本算法使A表仅留下三个表均包含的结点 且结点值不重复 释放所有结点 　　{pa=A >next;pb=B >next;pc=C >next;∥pa pb和pc分别是A B和C三个表的工作指针 　　pre=A;∥pre是A表中当前结点的前驱结点的指针 　　while(pa && pb && pc)∥当A B和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∥pc pa和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 pc pa和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表均从头到尾(严格说B C中最多一个到尾)遍历一遍 算法时间复杂度符合O(m+n+p) 算法主要由while(pa && pb && pc)控制 三表有一个到尾则结束循环 算法中查到A表与B表和C表的公共元素后 又分三种情况处理 一是三表中第一个公共元素值相等的结点;第二种情况是 尽管不是第一结点 但与前驱结点元素值相同 不能成为结果表中的结点;第三种情况是新结点与前驱结点元素值不同 应链入结果表中 前驱指针也移至当前结点 以便与以后元素值相同的公共结点进行比较 算法最后要给新A表置结尾标记 同时若原A表没到尾 还应释放剩余结点所占的存储空间