順序表的存貯特點是利用物理上的相鄰關系表達出邏輯上的前驅和後繼關系它要求用連續的存儲單元順序存儲線性表中各元素因此對順序表進行插入和刪除時需要通過移動數據元素來實現線性表的邏輯上的相鄰關系從而影響其運行效率本節介紹線性表的另一種存儲形式——鏈式存儲結構它不需要用地址連續的存儲單元來實現而是通過鏈建立起數據元素之間的次序關系因此它不要求邏輯上相鄰的兩個數據元素在物理結構上也相鄰在插入和刪除時無需移動元素從而提高其運行效率鏈式存儲結構主要有單鏈表循環鏈表雙向鏈表靜態鏈表等幾種形式
單鏈表
鏈表是通過一組任意的存儲單元(可以連續也可不連續)來存儲線性表中的數據元素根據線性表的邏輯定義單鏈表的存儲單元不僅能夠存儲元素而且要求能表達元素與元素之間的線性關系對數據元素ei而言除存放數據元素自身的信息ei之外還需要存放後繼元素ei+所在存貯單元的地址這兩部分信息組成一個結點每個結點包括兩個域數據域——存放數據元素本身的信息;指針域——存放其後繼結點的地址結點的結構如圖 所示因此n個元素的線性表通過每個結點的指針域構成了一個鏈條稱之為鏈表因為每個結點中只有一個指向後繼的指針所以稱其為單鏈表為了訪問單鏈表我們只要知道第一個結點地址就能訪問第一個元素通過第一個元素的指針域得到第二個結點的地址……以此類推可以訪問所有元素這樣稱第一個元素的地址為頭指針
例如假設有線性表(ABCDEFGH)對應的鏈式存儲結構如圖所示頭指針為H最後一個結點沒有後繼 其指針域必需置空(以NULL表示)表明此表到此結束這樣就可以從第一個結點的地址開始順籐摸瓜找到每個結點
[] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23375.html
