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


數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，并確保經(jīng)過這些運算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。簡而言之，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合。“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。


數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個密切相關(guān)的方面，同一邏輯結(jié)構(gòu)可以對應(yīng)不同的存儲結(jié)構(gòu)。算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于指定的存儲結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容是構(gòu)造復(fù)雜軟件系統(tǒng)的基礎(chǔ)，它的核心技術(shù)是分解與抽象。通過分解可以劃分出數(shù)據(jù)的3個層次；再通過抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現(xiàn)細(xì)節(jié)，就得到運算的定義。上述兩個方面的結(jié)合可以將問題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。然后，通過增加對實現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲結(jié)構(gòu)和實現(xiàn)運算，從而完成設(shè)計任務(wù)。這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實現(xiàn)）的過程。

研究對象

數(shù)據(jù)的邏輯結(jié)構(gòu)

指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們在計算機(jī)中的存儲位置無關(guān)。邏輯結(jié)構(gòu)包括：

1.集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個集合” 的相互關(guān)系外，別無其他關(guān)系；

2.線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系；

3.樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系；

4.圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系。

數(shù)據(jù)的物理結(jié)構(gòu)

指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間的存放形式。

數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（又稱映像），它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示。由于具體實現(xiàn)的方法有順序、鏈接、索引、散列等多種，所以，一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲結(jié)構(gòu)。

數(shù)據(jù)元素的機(jī)內(nèi)表示（映像方法）： 用二進(jìn)制位（bit）的位串表示數(shù)據(jù)元素。通常稱這種位串為節(jié)點（node）。當(dāng)數(shù)據(jù)元素有若干個數(shù)據(jù)項組成時，位串中與個數(shù)據(jù)項對應(yīng)的子位串稱為數(shù)據(jù)域（data field）。因此，節(jié)點是數(shù)據(jù)元素的機(jī)內(nèi)表示（或機(jī)內(nèi)映像）。

關(guān)系的機(jī)內(nèi)表示（映像方法）：數(shù)據(jù)元素之間的關(guān)系的機(jī)內(nèi)表示可以分為順序映像和非順序映像，常用兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序映像借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映像借助指示元素存儲位置的指針（pointer）來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

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

數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)(也稱為存儲結(jié)構(gòu))。一般來說，一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序存儲、鏈?zhǔn)酱鎯Α⑺饕鎯凸４鎯Φ取?br />
數(shù)據(jù)的順序存儲結(jié)構(gòu)的特點是：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；非順序存儲的特點是：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

分類

數(shù)據(jù)結(jié)構(gòu)有很多種，一般來說，按照數(shù)據(jù)的邏輯結(jié)構(gòu)對其進(jìn)行簡單的分類，包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 https://zhuanlan.zhihu.com/p/140769626/edit

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

簡單地說，線性結(jié)構(gòu)就是表中各個結(jié)點具有線性關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語言來描述，線性結(jié)構(gòu)應(yīng)該包括如下幾點： https://zhuanlan.zhihu.com/p/140769626/edit

1、線性結(jié)構(gòu)是非空集。 https://zhuanlan.zhihu.com/p/140769626/edit

2、線性結(jié)構(gòu)有且僅有一個開始結(jié)點和一個終端結(jié)點。 https://zhuanlan.zhihu.com/p/140769626/edit

3、線性結(jié)構(gòu)所有結(jié)點都最多只有一個直接前趨結(jié)點和一個直接后繼結(jié)點。 https://zhuanlan.zhihu.com/p/140769626/edit

線性表就是典型的線性結(jié)構(gòu)，還有棧、隊列和串等都屬于線性結(jié)構(gòu)。 https://zhuanlan.zhihu.com/p/140769626/edit

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

簡單地說，非線性結(jié)構(gòu)就是表中各個結(jié)點之間具有多個對應(yīng)關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語言來描述，非線性結(jié)構(gòu)應(yīng)該包括如下幾點： https://zhuanlan.zhihu.com/p/140769626/edit

1、非線性結(jié)構(gòu)是非空集。 https://zhuanlan.zhihu.com/p/140769626/edit

2、非線性結(jié)構(gòu)的一個結(jié)點可能有多個直接前趨結(jié)點和多個直接后繼結(jié)點。 https://zhuanlan.zhihu.com/p/140769626/edit

在實際應(yīng)用中，數(shù)組、廣義表、樹結(jié)構(gòu)和圖結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 https://zhuanlan.zhihu.com/p/140769626/edit

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

在計算機(jī)科學(xué)的發(fā)展過程中，數(shù)據(jù)結(jié)構(gòu)也隨之發(fā)展。程序設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)包括如下幾個。 https://zhuanlan.zhihu.com/p/140769626/edit

數(shù)組(Array)

數(shù)組是一種聚合數(shù)據(jù)類型，它是將具有相同類型的若干變量有序地組織在一起的集合。數(shù)組可以說是最基本的數(shù)據(jù)結(jié)構(gòu)，在各種編程語言中都有對應(yīng)。一個數(shù)組可以分解為多個數(shù)組元素，按照數(shù)據(jù)元素的類型，數(shù)組可以分為整型數(shù)組、字符型數(shù)組、浮點型數(shù)組、指針數(shù)組和結(jié)構(gòu)數(shù)組等。數(shù)組還可以有一維、二維以及多維等表現(xiàn)形式。 https://zhuanlan.zhihu.com/p/140769626/edit

棧( Stack)

棧是一種特殊的線性表，它只能在一個表的一個固定端進(jìn)行數(shù)據(jù)結(jié)點的插入和刪除操作。棧按照后進(jìn)先出的原則來存儲數(shù)據(jù)，也就是說，先插入的數(shù)據(jù)將被壓入棧底，最后插入的數(shù)據(jù)在棧頂，讀出數(shù)據(jù)時，從棧頂開始逐個讀出。棧在匯編語言程序中，經(jīng)常用于重要數(shù)據(jù)的現(xiàn)場保護(hù)。棧中沒有數(shù)據(jù)時，稱為空棧。 https://zhuanlan.zhihu.com/p/140769626/edit

隊列(Queue)

隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列只允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作。一般來說，進(jìn)行插入操作的一端稱為隊尾，進(jìn)行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列。 https://zhuanlan.zhihu.com/p/140769626/edit

鏈表( Linked List)

鏈表是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯Y(jié)構(gòu)進(jìn)行存儲的數(shù)據(jù)結(jié)構(gòu)，這種存儲結(jié)構(gòu)具有在物理上存在非連續(xù)的特點。鏈表由一系列數(shù)據(jù)結(jié)點構(gòu)成，每個數(shù)據(jù)結(jié)點包括數(shù)據(jù)域和指針域兩部分。其中，指針域保存了數(shù)據(jù)結(jié)構(gòu)中下一個元素存放的地址。鏈表結(jié)構(gòu)中數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序來實現(xiàn)的。 https://zhuanlan.zhihu.com/p/140769626/edit

樹( Tree)

樹是典型的非線性結(jié)構(gòu)，它是包括，2個結(jié)點的有窮集合K。在樹結(jié)構(gòu)中，有且僅有一個根結(jié)點，該結(jié)點沒有前驅(qū)結(jié)點。在樹結(jié)構(gòu)中的其他結(jié)點都有且僅有一個前驅(qū)結(jié)點，而且可以有兩個后繼結(jié)點，m≥0。 https://zhuanlan.zhihu.com/p/140769626/edit

圖(Graph)

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

堆(Heap)

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，一般討論的堆都是二叉堆。堆的特點是根結(jié)點的值是所有結(jié)點中最小的或者最大的，并且根結(jié)點的兩個子樹也是一個堆結(jié)構(gòu)。 https://zhuanlan.zhihu.com/p/140769626/edit

散列表(Hash)

散列表源自于散列函數(shù)(Hash function)，其思想是如果在結(jié)構(gòu)中存在關(guān)鍵字和T相等的記錄，那么必定在F(T)的存儲位置可以找到該記錄，這樣就可以不用進(jìn)行比較操作而直接取得所查記錄。 https://zhuanlan.zhihu.com/p/140769626/edit

常用算法

數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容：就是如何按一定的邏輯結(jié)構(gòu)，把數(shù)據(jù)組織起來，并選擇適當(dāng)?shù)拇鎯Ρ硎痉椒ò堰壿嫿Y(jié)構(gòu)組織好的數(shù)據(jù)存儲到計算機(jī)的存儲器里。算法研究的目的是為了更有效的處理數(shù)據(jù)，提高數(shù)據(jù)運算效率。數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，但運算的具體實現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。一般有以下幾種常用運算：

(1)檢索。檢索就是在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的節(jié)點。一般是給定一個某字段的值，找具有該字段值的節(jié)點。

(2)插入。往數(shù)據(jù)結(jié)構(gòu)中增加新的節(jié)點。

(3)刪除。把指定的結(jié)點從數(shù)據(jù)結(jié)構(gòu)中去掉。

(4)更新。改變指定節(jié)點的一個或多個字段的值。

(5)排序。把節(jié)點按某種指定的順序重新排列。例如遞增或遞減。