循環鏈表
對於單鏈表而言最後一個結點的指針域是空指針如果將該鏈表頭指針置入該指針域則使得鏈表頭尾結點相連就構成了循環單鏈表(也稱單循環鏈表)如圖所示
圖帶頭結點的單循環鏈表
對循環單鏈表的操作與單鏈表基本相同只是將原來判斷指針是否為NULL變為是否是頭指針而已其它沒有較大的變化
對於單鏈表只能從頭結點開始遍歷整個鏈表而對於循環單鏈表則可以從表中任意結點開始遍歷整個鏈表不僅如此對鏈表的操作可以在表尾表頭進行此時可以改變一下鏈表的標識方法不用頭指針而用一個指向尾結點的指針R來標識既可以找到尾結點又可以找到頭結點(R>next)可以使得操作效率得以提高
例如對兩個循環單鏈表H H的連接操作是將H的第一個元素結點接到H的尾結點如用頭指針標識則需要找到第一個鏈表的尾結點其時間復雜性為O(n)而鏈表若用尾指針R R來標識則時間性能為O()操作如下
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23075.html
