熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第二章 答案[17]

2013-11-15 15:23:56  來源: 數據結構 

  () [題目分析]本題首先求B和C的交集即求B和C中共有元素再與A求並集同時刪除重復元素以保持結果A遞增

  LinkedList union(LinkedList ABC)∥AB和C均是帶頭結點的遞增有序的單鏈表本算法實現A= A∪(B∩C)使求解結構保持遞增有序
  {pa=A>next;pb=B>next;pc=C>next;∥設置三個工作指針
  pre=A;∥pre指向結果鏈表中當前待合並結點的前驅
  if(pa>data<pb>data||pa>data<pc>data)∥A中第一個元素為結果表的第一元素
  {pre>next=pa;pre=pa;pa=pa>next;}
  else{while(pb&&pc)∥找B表和C表中第一個公共元素
  if(pb>data<pc>data)pb=pb>next;
  else if(pb>data>pc>data)pc=pc>next;
  else break;∥找到B表和C表的共同元素就退出while循環
  if(pb&&pc)∥ 因共同元素而非B表或C表空而退出上面while循環
  if(pa>data>pb>data)∥A表當前元素值大於B表和C表的公共元素先將B表元素鏈入
  {pre>next=pb;pre=pb;pb=pb>next;pc=pc>next;}∥ BC公共元素為結果表第一元素
  }∥結束了結果表中第一元素的確定
  while(pa&&pb&&pc)
  {while(pb&&pc)
  if(pb>data<pc>data) pb=pb>next;
  else if(pb>data>pc>data) pc=pc>next;
  else break;∥B表和C表有公共元素
  if(pb&&pc)
  {while(pa&&pa>data<pb>data)∥先將A中小於BC公共元素部分鏈入
  {pre>next=pa;pre=pa;pa=pa>next;}
  if(pre>data!=pb>data){pre>next=pb;pre=pb;pb=pb>next;pc=pc>next;}
  else{pb=pb>next;pc=pc>next;}∥ 若A中已有BC公共元素則不再存入結果表
  }
  }∥ while(pa&&pb&&pc)
  if(pa) pre>next=pa;∥當BC無公共元素(即一個表已空)將A中剩余鏈入
  }∥算法Union結束

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


From:http://tw.wingwit.com/Article/program/sjjg/201311/23352.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.