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

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

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

  .[題目分析] 將具有兩個鏈域的單循環鏈表改造成雙向循環鏈表關鍵是控制給每個結點均置上指向前驅的指針而且每個結點的前驅指針置且僅置一次

  void  StoDouble(LinkedList la)∥la是結點含有predatalink三個域的單循環鏈表其中data為數據域pre為空指針域link是指向後繼的指針域本算法將其改造成雙向循環鏈表
  {while(la>link>pre==null)
  {la>link>pre=la;∥將結點la後繼的pre指針指向la
  la=la>link;∥la指針後移
  }
  }∥算法結束

  [算法討論] 算法中沒有設置變量記住單循環鏈表的起始結點至少省去了一個指針變量當算法結束時la恢復到指向剛開始操作的結點這是本算法的優點所在

  .[題目分析] 求兩個集合A和B的差集AB即在A中刪除A和B中共有的元素由於集合用單鏈表存儲問題變成刪除鏈表中的結點問題因此要記住被刪除結點的前驅以便順利刪除被刪結點兩鏈表均從第一元素結點開始直到其中一個鏈表到尾為止

  void  Difference(LinkedList  AB*n)∥A和B均是帶頭結點的遞增有序的單鏈表分別存儲了一個集合本算法求兩集合的差集存儲於單鏈表A中*n是結果集合中元素個數調用時為
  {p=A>next;∥p和q分別是鏈表A和B的工作指針
  q=B>next; pre=A;∥pre為A中p所指結點的前驅結點的指針
  while(p!=null && q!=null)
  if(p>data<q>data){pre=p;p=p>next;*n++;}∥A鏈表中當前結點指針後移
  else if(p>data>q>data)q=q>next;∥B鏈表中當前結點指針後移
  else {pre>next=p>next;∥處理AB中元素值相同的結點應刪除
  u=p; p=p>next; free(u);}∥刪除結點

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


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