一、數(shù)據(jù)結(jié)構(gòu)到底是什么

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。

邏輯結(jié)構(gòu)和物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）

1.邏輯結(jié)構(gòu)

1）定義

邏輯結(jié)構(gòu)是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間相互關(guān)系（邏輯關(guān)系），即從邏輯關(guān)系上描述數(shù)據(jù)。它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)存儲(chǔ)器的。

2）分類（線性結(jié)構(gòu)和非線性結(jié)構(gòu)）

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常有下列4類基本結(jié)構(gòu)，復(fù)雜程度依次遞進(jìn)。

①集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合外，沒有其他的關(guān)系。

②線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。

③樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)多的關(guān)系。

④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的元素之間是多對(duì)多的關(guān)系。

2.物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）

1）定義

數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式。又稱存儲(chǔ)結(jié)構(gòu)。

它研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)元素的表示和元素之間的關(guān)系。

數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式主要有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

2）順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

①順序存儲(chǔ)結(jié)構(gòu)

是利用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯順序。

順序存儲(chǔ)結(jié)構(gòu)是把數(shù)據(jù)元素放在地址連續(xù)的存儲(chǔ)單元中，程序設(shè)計(jì)中使用數(shù)組類型來實(shí)現(xiàn)。（邏輯相鄰物理相鄰）

②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

利用結(jié)點(diǎn)中指針來表示數(shù)據(jù)元素之間的關(guān)系。

把數(shù)據(jù)元素存儲(chǔ)在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是連續(xù)的，程序設(shè)計(jì)中使用指針類型來實(shí)現(xiàn)。（邏輯相鄰物理不一定相鄰）

3）其他存儲(chǔ)方式

索引存儲(chǔ)：類似于目錄，以后可以聯(lián)系操作系統(tǒng)的文件系統(tǒng)章節(jié)來理解。

散列存儲(chǔ)：通過關(guān)鍵字直接計(jì)算出元素的物理地址。

抽象數(shù)據(jù)類型

1.定義

①數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。

例如：C語言中數(shù)據(jù)類型分為基本類型和構(gòu)造類型

基本類型：整型、浮點(diǎn)型、字符型等

構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義類型等

②抽象數(shù)據(jù)類型（abstract data type，ADT）：是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。

延伸閱讀：

二、散列（哈希）存儲(chǔ)結(jié)構(gòu)

就是根據(jù)數(shù)據(jù)元素的關(guān)鍵字通過哈希函數(shù)計(jì)算出一個(gè)數(shù)值用做數(shù)據(jù)元素的存儲(chǔ)地址，優(yōu)點(diǎn)在于查找速度快，只需要給出關(guān)鍵字可立即計(jì)算出該數(shù)據(jù)元素的地址 特點(diǎn)是指存儲(chǔ)數(shù)據(jù)元素不存儲(chǔ)數(shù)據(jù)之間的邏輯關(guān)系，只適合進(jìn)行快速查找和插入的場(chǎng)合。