基本概念
數(shù)據(jù)(Data) ：是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。
數(shù)據(jù)元素(Data Element) ：是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。
一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。
數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元 素的集合，是數(shù)據(jù)的一個子集。如字符集合C={‘A’,’B’,’C,…} 。
數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是指相互之間具有(存在)一定聯(lián)系(關系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關系)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如圖1-3所示。
① 集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其它關系。
② 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關系。
③ 樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關系。
④ 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關系。
數(shù)據(jù)結(jié)構(gòu)的存儲方式
數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關系的表示。
元素之間的關系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。
- 順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關系)。
- 鏈式存儲結(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer )，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關系)。
數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)的三個組成部分：
邏輯結(jié)構(gòu)： 數(shù)據(jù)元素之間邏輯關系的描述
D_S=（D，S）
存儲結(jié)構(gòu)： 數(shù)據(jù)元素在計算機中的存儲及其邏輯關系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。
數(shù)據(jù)操作： 對數(shù)據(jù)要進行的運算。
線性表，樹，圖的邏輯結(jié)構(gòu)及其采用的存儲結(jié)構(gòu)如圖1-1所示
數(shù)據(jù)類型
__ 數(shù)據(jù)類型(Data Type)__：指的是一個值的集合和定義在該值集上的一組操作的總稱。
數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關系。
抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型(Abstract Data Type ，簡稱ADT) ：是指一個數(shù)學模型以及定義在該模型上的一組操作。
ADT的定義僅是一組邏輯特性描述， 與其在計算機內(nèi)的表示和實現(xiàn)無關。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學特性不變，都不影響其外部使用。
ADT的形式化定義是三元組：ADT=(D，S，P)
其中：D是數(shù)據(jù)對象，S是D上的關系集，P是對D的基本操作集。
ADT的一般定義形式是：
ADT <抽象數(shù)據(jù)類型名>{
數(shù)據(jù)對象： <數(shù)據(jù)對象的定義>
數(shù)據(jù)關系： <數(shù)據(jù)關系的定義>
基本操作： <基本操作的定義>
} ADT <抽象數(shù)據(jù)類型名>
– 其中數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述。
– 基本操作的定義是：
<基本操作名>(<參數(shù)表>)
初始條件： <初始條件描述>
操作結(jié)果： <操作結(jié)果描述>
- 初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應滿足的條件;若不滿足，則操作失敗，返回相應的出錯信息。
- 操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和 應返回的結(jié)果。
基本概念就這么多，如果想深入了解，建議閱讀相關書籍。
- 數(shù)據(jù)結(jié)構(gòu)（c語言版）嚴蔚敏編著
