數(shù)據(jù)的四種基本存儲方法

　　數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到：

　?。?）順序存儲方法

　　該方法把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。

　　由此得到的存儲表示稱為順序存儲結(jié)構(gòu)（SequentialStorageStructure），通常借助程序語言的數(shù)組描述。

　　該方法主要應用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實現(xiàn)順序存儲。

　?。?）鏈接存儲方法

　　該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關系由附加的指針字段表示。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)（LinkedStorageStructure），通常借助于程序語言的指針類型描述。

　?。?）索引存儲方法

　　該方法通常在儲存結(jié)點信息的同時，還建立附加的索引表。索引表由若干索引項組成。若每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引（DenseIndex）。若一組結(jié)點在索引表中只對應一個索引項，則該索引表稱為稀疏索引（SpareIndex）。索引項的一般形式是：

　?。P鍵字、地址）

　　關鍵字是能唯一標識一個結(jié)點的那些數(shù)據(jù)項。稠密索引中索引項的地址指示結(jié)點所在的存儲位置；稀疏索引中索引項的地址指示一組結(jié)點的起始存儲位置。

　　（4）散列存儲方法

　　該方法的基本思想是：根據(jù)結(jié)點的關鍵字直接計算出該結(jié)點的存儲地址。

　　四種基本存儲方法，既可單獨使用，也可組合起來對數(shù)據(jù)結(jié)構(gòu)進行存儲映像。

　　同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運算方便及算法的時空要求。

　　數(shù)據(jù)結(jié)構(gòu)三方面的關系

　　數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算這三方面是一個整體。孤立地去理解一個方面，而不注意它們之間的聯(lián)系是不可取的。存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個方面：同一邏輯結(jié)構(gòu)的不同存儲結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標識。

　　【例】線性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲表示，可稱其為順序表；若采用鏈式存儲方法，則可稱其為鏈表；若采用散列存儲方法，則可稱為散列表。

　　數(shù)據(jù)的運算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個方面。在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之后，按定義的運算集合及其運算的性質(zhì)不同，也可能導致完全不同的數(shù)據(jù)結(jié)構(gòu)。

　　【例】若對線性表上的插入、刪除運算限制在表的一端進行，則該線性表稱之為棧；若對插入限制在表的一端進行，而刪除限制在表的另一端進行，則該線性表稱之為隊列。更進一步，若線性表采用順序表或鏈表作為存儲結(jié)構(gòu)，則對插入和刪除運算做了上述限制之后，可分別得到順序?；蜴湕?，順序隊列或鏈隊列。
責任編輯人：CC