數據的四種基本存儲方法
數據的存儲結構可用以下四種基本存儲方法得到
( )順序存儲方法
該方法把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元裡結點間的邏輯關系由存儲單元的鄰接關系來體現
由此得到的存儲表示稱為順序存儲結構 ( Sequential Storage Structure )通常借助程序語言的數組描述
該方法主要應用於線性的數據結構非線性的數據結構也可通過某種線性化的方法實現順序存儲
( )鏈接存儲方法
該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰結點間的邏輯關系由附加的指針字段表示由此得到的存儲表示稱為鏈式存儲結構(
Linked Storage Structure ) 通常借助於程序語言的指針類型描述
() 索引存儲方法
該方法通常在儲存結點信息的同時 還建立附加的索引表
索引表由若干索引項組成若每個結點在索引表中都有一個索引項則該索引表稱之為稠密索引( Dense Index )若一組結點在索引表中只
對應一個索引項則該索引表稱為稀疏索引 (Spare Index) 索引項的一般形式是
( 關鍵字地址 )
關鍵字是能唯一標識一個結點的那些數據項稠密索引中索引項的地址指示結點所在的存儲位置;稀疏索引中索引項的地址指示一組結點的起始
存儲位置
() 散列存儲方法
該方法的基本思想是根據結點的關鍵字直接計算出該結點的存儲地址
四種基本存儲方法既可單獨使用也可組合起來對數據結構進行存儲映像
同一邏輯結構采用不同的存儲方法可以得到不同的存儲結構選擇何種存儲結構來表示相應的邏輯結構視具體要求而定主要考慮運算方便
及算法的時空要求
數據結構三方面的關系
數據的邏輯結構數據的存儲結構及數據的運算這三方面是一個整體孤立地去理解一個方面而不注意它們之間的聯系是不可取的
存儲結構是數據結構不可缺少的一個方面同一邏輯結構的不同存儲結構可冠以不同的數據結構名稱來標識
【例】線性表是一種邏輯結構若采用順序方法的存儲表示可稱其為順序表;若采用鏈式存儲方法則可稱其為鏈表;若采用散列存儲方法
則可稱為散列表
數據的運算也是數據結構不可分割的一個方面在給定了數據的邏輯結構和存儲結構之後按定義的運算集合及其運算的性質不同也可能導致
完全不同的數據結構
【例】 若對線性表上的插入刪除運算限制在表的一端進行則該線性表稱之為棧;若對插入限制在表的一端進行而刪除限制在表的另一端
進行則該線性表稱之為隊列更進一步若線性表采用順序表或鏈表作為存儲結構則對插入和刪除運算做了上述限制之後可分別得到順序
棧或鏈棧順序隊列或鏈隊列
數據類型(Data Type)
所謂數據類型是一個值的集合以及在這些值上定義的一組操作的總稱通常數據類型可以看作是程序設計語言中已實現的數據結構
【例】C語言的整數類型就定義了一個整數可取值的范圍(其最大值INTMAX依賴於具體機器)以及對整數可施加的加減乘除和取模
等操作
按值是否可分解可將數據類型劃分為兩類
① 原子類型 其值不可分解通常是由語言直接提供
【例】 C語言的整型字符型等標准類型及指針等簡單的導出類型;
② 結構類型 其值可分解為若干個成分(或稱為分量)是用戶借助於語言提供的描述機制自己定義的它通常是由標准類型派生的故它
也是一種導出類型
【例】 C的數組結構等類型
抽象數據類型(Abstract Type簡稱ADT)
ADT是指抽象數據的組織和與之相關的操作可以看作是數據的邏輯結構及其在邏輯結構上定義的操作
一個ADT可描述為
ADT ADTName{
Data://數據說明
數據元素之間邏輯關系的描述
Operations://操作說明
Operation://操作它通常可用C或C﹢﹢的函數原型來描述
Input:對輸入數據的說明
Preconditions:執行本操作前系統應滿足的狀態//可看作初始條件
Process:對數據執行的操作
Output:對返回數據的說明
Postconditions:執行本操作後系統的狀態//系統可看作某個數據結構
Operation://操作
……
}//ADT
抽象數據類型可以看作是描述問題的模型它獨立於具體實現它的優點是將數據和操作封裝在一起使得用戶程序只能通過在ADT裡定義的
某些操作來訪問其中的數據從而實現了信息隱藏在C﹢﹢中我們可以用類(包括模板類)的說明來表示ADT用類的實現來實現ADT【參閱
[]】因此C﹢﹢中實現的類相當於是數據的存儲結構及其在存儲結構上實現的對數據的操作
ADT和類的概念實際上反映了程序或軟件設計的兩層抽象ADT相當於是在概念層(或稱為抽象層)上描述問題而類相當於是在實現層上
描述問題此外C﹢﹢中的類只是一個由用戶定義的普通類型可用它來定義變量(稱為對象或類的實例)因此在C﹢﹢中最終是通過操
作對象來解決實際問題的所以我們可將該層次看作是應用層例如main程序就可看作是用戶的應用程序
由於C語言中沒有提供類這一數據類型因此無法實現ADT故我們不采用ADT的形式來描述數據結構以節省篇幅大家只要記住它實
際上等價於我們定義的數據的邏輯結構以及在邏輯結構上定義的抽象操作
From:http://tw.wingwit.com/Article/program/sjjg/201311/23586.html
