1.2.5 數據的存儲結構

數據的存儲結構是邏輯結構用計算機語言的實現或在計算機中的表示（亦稱為映象），也就是邏輯結構在計算機中的存儲方式，它是依賴于計算機語言的。數據元素之間的關系在計算機中有兩種表示方式：順序映象和非順序映象。歸納起來，數據的存儲結構在計算機中有以下4種。

1. 順序存儲結構

順序存儲結構是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點之間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲結構稱為順序存儲結構，通常順序存儲結構是借助于計算機程序設計語言的數組來描述的。

順序存儲結構的主要優點是節省存儲空間，因為分配給數據的存儲單元全部用于存放結點的數據，結點之間的邏輯關系沒有占用額外的存儲空間。采用這種結構時，可實現對結點的隨機存取。然而順序存儲結構的主要缺點是不便于修改，在對結點進行插入、刪除運算時，可能要移動一系列的結點。

2. 鏈式存儲結構

鏈式存儲結構不要求邏輯上相鄰的結點在物理位置上也相鄰，結點間的邏輯關系是由附加的“指針”字段表示的。由此得到的存儲結構稱為鏈式存儲結構。

鏈式存儲結構的優點是便于修改，在對結點進行插入、刪除操作時，僅需要修改相應結點的“指針域”，不必移動結點。但與順序存儲結構相比，鏈式存儲結構的存儲空間利用率較低，因為分配給數據的存儲單元有一部分被用來存儲結點間的邏輯關系了。另外，由于邏輯上相鄰的結點在物理位置上并不一定相鄰，所以不能對結點進行隨機訪問操作。

3. 索引存儲結構

索引存儲結構通常在存儲結點信息的同時建立附加的索引表。索引表的每一項稱為索引項，索引項的一般形式是（關鍵字，地址），關鍵字唯一標識一個結點，地址作為指向結點的指針。這種帶有索引表的存儲結構可以大大提高數據查找的速度。

線性結構采用索引存儲結構后，可以對結點進行隨機訪問。在對結點進行插入、刪除運算時，只需移動存儲在索引表中對應結點的存儲地址，而不必移動存放在結點表中結點的數據，所以仍保持較高的數據修改效率。索引存儲結構的缺點是增加了索引表及存儲空間開銷。

4. 哈希存儲結構

哈希存儲結構的基本思想是根據結點的關鍵字通過哈希函數直接計算出一個值，并將這個值作為該結點的存儲地址。

哈希存儲結構的優點是查找速度快，只要給出待查找結點的關鍵字，就可以計算出該結點的存儲地址。與前3種存儲結構不同的是，哈希存儲結構只存儲結點的數據，不存儲結點之間的邏輯關系。哈希存儲結構一般適用于要求對數據能夠進行查找和插入的場景。