基本介紹
- 中文名：外部數據結構
- 外文名：External Data Structure
- 學科：計算機
- 定義：數據在計算機存儲空間的存放形式
- 有關術語：順序存儲結構、鏈式存儲結構
- 領域：數據結構
簡介,順序存儲結構,鏈式存儲結構,鍊表,鏈式存儲結構特點,
簡介
外部數據結構即數據結構在計算機中的表示（映像）稱為數據的物理（存儲）結構。它包括數據元素的表示和關係的表示。 與之相反的是數據的邏輯結構，即反映數據元素之間的邏輯關係的數據結構，其中的邏輯關係是指數據元素之間的前後件關係，而與他們在計算機中的存儲位置無關。外部數據結構實際上研究的就是如何把數據元素存儲到計算機的存儲器中。外部數據結構一般可以分為順序存儲結構和鏈式存儲結構。
順序存儲結構
順序存儲結構的主要優點是節省存儲空間，因為分配給數據的存儲單元全用存放結點的數據（不考慮c/c++語言中數組需指定大小的情況），結點之間的邏輯關係沒有占用額外的存儲空間。採用這種方法時，可實現對結點的隨機存取，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存儲地址。但順序存儲方法的主要缺點是不便於修改，對結點的插入、刪除運算時，可能要移動一系列的結點。
鏈式存儲結構
鍊表
鍊表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鍊表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。
使用鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機記憶體空間，實現靈活的記憶體動態管理。但是鍊表失去了數組隨機讀取的優點，同時鍊表由於增加了結點的指針域，空間開銷比較大。
在計算機科學中，鍊表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鍊表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的連結（"links"）。鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁碟上順序，數據的訪問往往要在不同的排列順序中轉換。而鍊表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（連結）。鍊表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。
鏈式存儲結構特點
1、比順序存儲結構的存儲密度小(鏈式存儲結構中每個結點都由數據域與指針域兩部分組成，相比順序存儲結構增加了存儲空間)。
2、邏輯上相鄰的節點物理上不必相鄰。
3、插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。
4、查找結點時鏈式存儲要比順序存儲慢。
5、每個結點是由數據域和指針域組成。
