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

在《數(shù)據(jù)結(jié)構(gòu)，算法及應(yīng)用》一書中有這樣的解釋“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象，存在與該對象的實例以及組成實例的數(shù)據(jù)元素之間的各種關(guān)系，并且這種關(guān)系可以通過定義相關(guān)的函數(shù)來給出?！彼麑?shù)據(jù)對象定義為一個實例或值的集合。
上面這種說發(fā)比較難以理解，我們可以簡單的理解為數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。（百度百科https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450?fr=aladdin）
數(shù)據(jù)結(jié)構(gòu)包含三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)的運算。

• 數(shù)據(jù)的邏輯結(jié)構(gòu)即數(shù)據(jù)元素之間的邏輯關(guān)系，是一種獨立于計算機的抽象概念。例如一組元素中按順序排列的這種前后關(guān)系。
• 數(shù)據(jù)的存儲結(jié)構(gòu)即數(shù)據(jù)元素以及其邏輯關(guān)系在計算機存儲器中的表現(xiàn)形式。是一種具體的概念，真實的存儲表現(xiàn)。例如數(shù)據(jù)結(jié)構(gòu)中的每個數(shù)據(jù)元素都按照順序依此存儲在一片連續(xù)的存儲單元中。
• 數(shù)據(jù)的運算即能夠?qū)?shù)據(jù)施加的操作。例如增刪改查和排序。

數(shù)據(jù)結(jié)構(gòu)的這三個方面是一個有機的整體，缺一不可。數(shù)據(jù)的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)及運算任何一個發(fā)生變化都將導(dǎo)致一個全新的數(shù)據(jù)結(jié)構(gòu)出現(xiàn)。

數(shù)據(jù)結(jié)構(gòu)的的邏輯關(guān)系

數(shù)據(jù)結(jié)構(gòu)的結(jié)點之間的邏輯關(guān)系可以分為以下兩類：

1. 線性結(jié)構(gòu)

簡單的理解，線性結(jié)構(gòu)就是各個結(jié)點具有線性關(guān)系（一個有序數(shù)據(jù)元素的集合）。線性結(jié)構(gòu)應(yīng)該包括如下內(nèi)容：

• 線性結(jié)構(gòu)是非空集
• 線性結(jié)構(gòu)有且僅有一個開始結(jié)點和結(jié)束結(jié)點
• 線性結(jié)構(gòu)中每個結(jié)點最多可以有一個直接前驅(qū)結(jié)點，同時最多可以有一個直接后驅(qū)結(jié)點。
  典型的線性結(jié)構(gòu)有：棧，隊列

2. 非線性結(jié)構(gòu)

非線性結(jié)構(gòu)就是各個結(jié)點之間具有多個對應(yīng)關(guān)系。非線性結(jié)構(gòu)應(yīng)該包括如下內(nèi)容：

• 非線性結(jié)構(gòu)是非空集
• 非線性結(jié)構(gòu)的一個結(jié)點可能有多個直接前驅(qū)結(jié)點和直接后驅(qū)結(jié)點。
  典型的非線性結(jié)構(gòu)有：廣義表，樹結(jié)構(gòu)，圖結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的存儲方式

數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的一個重要內(nèi)容，在計算機中，數(shù)據(jù)的存儲結(jié)構(gòu)采用如下四種方法來實現(xiàn)：

1.順序存儲方式

順序存儲方式就是在一塊連續(xù)的存儲區(qū)域一個接著一個的存放數(shù)據(jù)。順序存儲方式把邏輯上相鄰的兩個結(jié)點存儲在物理地址相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來提現(xiàn)。該存儲方式主要用于線性邏輯結(jié)構(gòu)的數(shù)據(jù)存放，而對于圖和樹等非線性邏輯結(jié)構(gòu)則不適用。

2.鏈?zhǔn)酱鎯Ψ绞?/h6>

鏈?zhǔn)酱鎯Ψ绞奖容^靈活，它不要求邏輯上相鄰的結(jié)點在物理存儲上的位置相鄰。結(jié)點間的邏輯關(guān)系通過結(jié)點附帶的引用字段來表示。一個結(jié)點的引用字段往往指向下一個結(jié)點的存儲位置。

3.索引存儲方式

索引存儲方式是采用附加的索引表的方式來存儲結(jié)點信息。索引表由若干索引項組成，索引項的的一般形式為（關(guān)鍵字和數(shù)據(jù)元素存儲地址）。其中關(guān)鍵字是能夠唯一標(biāo)識一個結(jié)點的數(shù)據(jù)項。就像新華字典一樣。
按照索引表中索引項所對應(yīng)的結(jié)點的數(shù)量，索引存儲方式還可以細(xì)分為稠密索引和稀疏索引

• 稠密索引（Dense Index）:每個結(jié)點在索引表中對應(yīng)一個索引項，其中索引項中的地址指向結(jié)點的存儲位置
• 稀疏索引（Spare Index）:索引表中的一個索引項對應(yīng)一組結(jié)點，索引項中的地址指向這一組結(jié)點的起始存儲位置。

4.散列存儲方式

散列存儲方式是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址的一種存儲方式。

常用的數(shù)據(jù)結(jié)構(gòu)

1.數(shù)組(Array)

數(shù)組是一種聚合數(shù)據(jù)類型，是將具有相同數(shù)據(jù)類型的若干元素有序組織在一起的集合。數(shù)組可以說是最基本的數(shù)據(jù)結(jié)構(gòu)。一個數(shù)組可以分解成多個數(shù)組元素，按照數(shù)據(jù)元素的類型的不同，數(shù)組類型可以分為整型數(shù)組，字符型數(shù)組，浮點型數(shù)組，對象型數(shù)組。數(shù)組還可以分為一維數(shù)組，二維數(shù)組和多為數(shù)組等形式。

2.棧(Stack)

棧是一種特殊的線性表，其只能在表的一個固定端進(jìn)行數(shù)據(jù)結(jié)點的插入和刪除操作。棧按照先進(jìn)后出的原則來存儲數(shù)據(jù)，也就是說先入棧的被壓入了棧底，最后入棧的則在棧頂，讀出數(shù)據(jù)時從棧頂開始逐個讀出。棧中沒有數(shù)據(jù)時稱為空棧。

3.隊列(Queue)

隊列和棧類似，也是一種特殊的線性表。和棧不同的是 隊列只允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作。一般來說進(jìn)行插入操作的是隊尾，進(jìn)行刪除操作的是隊首，也就是說隊列是按照先進(jìn)先出的原則進(jìn)行數(shù)據(jù)存儲。隊列中沒有數(shù)據(jù)的時候稱為空隊列。

4.鏈表（LinkedList）

鏈表是一種按照鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)，這種存儲結(jié)構(gòu)在物理上具有非連續(xù)的存儲區(qū)域的特點。鏈表由一系列的數(shù)據(jù)結(jié)點構(gòu)成，每個數(shù)據(jù)結(jié)點包括數(shù)據(jù)域和引用域兩部分，其中引用域存儲了邏輯關(guān)系上下一個結(jié)點的存儲地址。鏈表中數(shù)據(jù)元素的邏輯關(guān)系是通過鏈表中的引用鏈次序來實現(xiàn)的。

5.樹（Tree）

樹是典型的非線性結(jié)構(gòu)，是包含n個數(shù)據(jù)結(jié)點的有窮集合。在樹結(jié)構(gòu)中有且僅有一個跟結(jié)點，跟結(jié)點沒有前驅(qū)結(jié)點但有0個或多個后繼結(jié)點，在樹結(jié)構(gòu)中其他結(jié)點有且僅有一個前驅(qū)結(jié)點，但有0個或多個后繼節(jié)點。

6.圖（Graph）

圖是另外一種典型的非線性結(jié)構(gòu)，在圖結(jié)構(gòu)中數(shù)據(jù)結(jié)點一般稱為頂點，而邊是頂點的有序偶對，如果兩個頂點之間存在一條邊，那么就表示這兩個頂點具有相鄰關(guān)系。

7.堆（Heap）

堆是一種特殊的樹結(jié)構(gòu)，一般討論的堆都是二叉堆。堆的特點是跟結(jié)點的值是所有結(jié)點中最小的或者最大的，并且根節(jié)點的兩個子樹也是一個堆結(jié)構(gòu)。

8.散列表（Hash）

散列表一般指哈希表，是根據(jù)關(guān)鍵碼值直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說它通過關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

本內(nèi)容均來自《Java常用算法手冊》