一、是什么

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

前面講到，一個(gè)程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)是實(shí)現(xiàn)算法的基礎(chǔ)，選擇合適的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率

數(shù)據(jù)元素相互之間的關(guān)系稱(chēng)為結(jié)構(gòu)，根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有如下四類(lèi)基本的結(jié)構(gòu)：

• 集合結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”
• 線(xiàn)性結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系
• 樹(shù)型結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系
• 圖形結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，也稱(chēng)網(wǎng)狀結(jié)構(gòu)

由于數(shù)據(jù)結(jié)構(gòu)種類(lèi)太多，邏輯結(jié)構(gòu)可以再分成為：

• 線(xiàn)性結(jié)構(gòu)：有序數(shù)據(jù)元素的集合，其中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的
• 非線(xiàn)性結(jié)構(gòu)：各個(gè)數(shù)據(jù)元素不再保持在一個(gè)線(xiàn)性序列中，每個(gè)數(shù)據(jù)元素可能與零個(gè)或者多個(gè)其他數(shù)據(jù)元素發(fā)生關(guān)聯(lián)

二、有哪些

常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有如下：

• 數(shù)組
• 棧
• 隊(duì)列
• 鏈表
• 樹(shù)
• 圖
• 堆
• 散列表

數(shù)組

在程序設(shè)計(jì)中，為了處理方便， 一般情況把具有相同類(lèi)型的若干變量按有序的形式組織起來(lái)，這些按序排列的同類(lèi)數(shù)據(jù)元素的集合稱(chēng)為數(shù)組

棧

一種特殊的線(xiàn)性表，只能在某一端插入和刪除的特殊線(xiàn)性表，按照先進(jìn)后出的特性存儲(chǔ)數(shù)據(jù)

先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)

隊(duì)列

跟棧基本一致，也是一種特殊的線(xiàn)性表，其特性是先進(jìn)先出，只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作

鏈表

是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的

鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成

一般情況，每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域

樹(shù)

樹(shù)是典型的非線(xiàn)性結(jié)構(gòu)，在樹(shù)的結(jié)構(gòu)中，有且僅有一個(gè)根結(jié)點(diǎn)，該結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中的其他結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，而且可以有兩個(gè)以上的后繼結(jié)點(diǎn)

圖

一種非線(xiàn)性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，數(shù)據(jù)結(jié)點(diǎn)一般稱(chēng)為頂點(diǎn)，而邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊，那么就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系

堆

堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有一個(gè)值，特點(diǎn)是根結(jié)點(diǎn)的值最小（或最大），且根結(jié)點(diǎn)的兩個(gè)子樹(shù)也是一個(gè)堆

散列表

若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲(chǔ)位置上，不需比較便可直接取得所查記錄

三、區(qū)別

上述的數(shù)據(jù)結(jié)構(gòu)，之前的區(qū)別可以分成線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)：

• 線(xiàn)性結(jié)構(gòu)有：數(shù)組、棧、隊(duì)列、鏈表等
• 非線(xiàn)性結(jié)構(gòu)有：樹(shù)、圖、堆等