數據（Data）
數據是信息的載體它能夠被計算機識別存儲和加工處理是計算機程序加工的原料
隨著計算機應用領域的擴大數據的范疇包括
整數實數字符串圖像和聲音等
數據元素（Data Element）
數據元素是數據的基本單位數據元素也稱元素結點頂點記錄
一個數據元素可以由若干個數據項（也可稱為字段域屬性）組成
數據項是具有獨立含義的最小標識單位
數據結構（Data Structure）
數據結構指的是數據之間的相互關系即數據的組織形式
．數據結構一般包括以下三方面內容
① 數據元素之間的邏輯關系也稱數據的邏輯結構（Logical Structure）
數據的邏輯結構是從邏輯關系上描述數據與數據的存儲無關是獨立於計算機的數據的邏輯結構可以看作是從具體問題抽象出來的數學模型
② 數據元素及其關系在計算機存儲器內的表示稱為數據的存儲結構（Storage Structure）
數據的存儲結構是邏輯結構用計算機語言的實現（亦稱為映象）它依賴於計算機語言對機器語言而言存儲結構是具體的一般只在高級語言的層次上討論存儲結構
③ 數據的運算即對數據施加的操作
數據的運算定義在數據的邏輯結構上每種邏輯結構都有一個運算的集合最常用的檢索插入刪除更新排序等運算實際上只是在抽象的數據上所施加的一系列抽象的操作
所謂抽象的操作是指我們只知道這些操作是做什麼而無須考慮如何做只有確定了存儲結構之後才考慮如何具體實現這些運算
為了增加對數據結構的感性認識下面舉例來說明有關數據結構的概念
【例．】 學生成績表見下表
注意在表中指出數據元素數據項開始結點和終端結點等概念
（）邏輯結構
表中的每一行是一個數據元素（或記錄結點）它由學號姓名各科成績及平均成績等數據項組成
表中數據元素之間的邏輯關系是對表中任一個結點與它相鄰且在它前面的結點（亦稱為直接前趨（Immediate Predecessor））最多只有一個與表中任一結點相鄰且在其後的結點（亦稱為直接後繼（Immediate Successor））也最多只有一個表中只有第一個結點沒有直接前趨故稱為開始結點也只有最後一個結點沒有直接後繼故稱之為終端結點例如表中馬二所在結點的直接前趨結點和直接後繼結點分別是丁一和張三所在的結點上述結點間的關系構成了這張學生成績表的邏輯結構
（）存儲結構
該表的存儲結構是指用計算機語言如何表示結點之間的這種關系即表中的結點是順序鄰接地存儲在一片連續的單元之中還是用指針將這些結點鏈接在一起？
（）數據的運算
在上面的學生成績表中可能要經常查看某一學生的成績當學生退學時要刪除相應的結點進來新學生時要增加結點究竟如何進行查找刪除插入這就是數據的運算問題
搞清楚了上述三個問題也就弄清了學生成績表這個數據結構
．數據的邏輯結構分類
在不產生混淆的前提下常將數據的邏輯結構簡稱為數據結構數據的邏輯結構有兩大類
（）線性結構
線性結構的邏輯特征是若結構是非空集則有且僅有一個開始結點和一個終端結點並且所有結點都最多只有一個直接前趨和一個直接後繼
線性表是一個典型的線性結構棧隊列串等都是線性結構
（）非線性結構
非線性結構的邏輯特征是一個結點可能有多個直接前趨和直接後繼數組廣義表樹和圖等數據結構都是非線性結構
．數據的四種基本存儲方法
數據的存儲結構可用以下四種基本存儲方法得到
（）順序存儲方法
該方法把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元裡結點間的邏輯關系由存儲單元的鄰接關系來體現
由此得到的存儲表示稱為順序存儲結構 （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相當於是在概念層（或稱為抽象層）上描述問題而類相當於是在實現層上描述問題此
From:http://tw.wingwit.com/Article/program/sjjg/201311/22632.html
