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

數據結構之單鏈表基本運算的實現[11]

2013-11-15 15:13:18  來源: 數據結構 

  p= R –>next; /*保存R 的頭結點指針*/

  R>next=R>next>next; /*頭尾連接*/

  free(R>next); /*釋放第二個表的頭結點*/

  R>next=p; /*組成循環鏈表*/

  這一過程可見圖

  

  圖

  雙向鏈表

  以上討論的單鏈表其結點只含有一個指向其後繼結點的指針域next因此若已知某結點的指針為p其後繼結點的指針則為p>next 若要找其前驅則只能從該鏈表的頭指針開始順著各結點的next域進行也就是說查找後繼的時間性能是O()查找前驅的時間性能是O(n)如果要克服單鏈表的缺點希望查找前驅的時間性能達到O()則只能付出空間的代價每個結點再加一個指向前驅的指針域結點的結構為如圖所示用這種帶前驅和後繼指針結點組成的鏈表稱為雙向鏈表

  

  圖 帶頭結點的雙向循環鏈表

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


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