一、在鏈式存儲結構中,數據之間的關系的體現
在鏈式存儲結構中,數據之間的關系是通過指針(結點中的指針)決定的。鏈式存儲結構,又叫鏈接存儲。結構。在計算機中用一組任意的存儲單元存儲線性表的數據元素。
一般在計算機的硬盤中,文件都是鏈式存儲的。我們知道,多個扇區組成一個簇,簇是計算機存儲數據的基本單位。而一個文件是存儲在多個在空間上也許并不相連的簇中的,這就是鏈式存儲。
但是為了能夠讀取出這個文件,計算機會在該文件名列前茅部分的尾部寫上第二部分所在的簇號。第二部分的尾部又寫上第三部分,以此類推,最后一部分寫上一段代碼,表示這是該文件的最后一部分。值得一提的是,高簇號在后。文件所占簇可認為是隨機分配的。
延伸閱讀:
二、鏈表數據結構
鏈表(Linked list)是一種常見的基礎數據結構,是一種線性表,但是并不會按線性的順序存儲數據,而是在每一個節點里存到下一個節點的指針(Pointer)。由于不必須按順序存儲,鏈表在插入的時候可以達到O(1)的復雜度,比另一種線性表順序表快得多,但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間,而順序表相應的時間復雜度分別是O(logn)和O(1)。
使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點,鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點,同時鏈表由于增加了結點的指針域,空間開銷比較大。
在計算機科學中,鏈表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鏈表通常由一連串節點組成,每個節點包含任意的實例數據(data fields)和一或兩個用來指向上一個/或下一個節點的位置的鏈接(”links”)。鏈表最明顯的好處就是,常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序,數據的訪問往往要在不同的排列順序中轉換。而鏈表是一種自我指示數據類型,因為它包含指向另一個相同類型的數據的指針(鏈接)。鏈表允許插入和移除表上任意位置上的節點,但是不允許隨機存取。鏈表有很多種不同的類型:單向鏈表,雙向鏈表以及循環鏈表。