．[題目分析] 留下三個鏈表中公共數據首先查找兩表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表沒到尾還應釋放剩余結點所占的存儲空間
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23317.html
