摘要：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。不同類型的數(shù)據(jù)結(jié)構(gòu)編程世界中存在許多不同類型的數(shù)據(jù)結(jié)構(gòu)?？梢詫⒓蠑?shù)據(jù)結(jié)構(gòu)進(jìn)行排序，并將其稱為有序集合。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常將其作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。

數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，是數(shù)據(jù)記錄中最基本的，不可分的數(shù)據(jù)單位。

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括3方面的內(nèi)容：邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)和對數(shù)據(jù)的運(yùn)算

數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，它與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)，同一種邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。歸納起來數(shù)據(jù)的邏輯結(jié)構(gòu)主要有兩大類。

線性結(jié)構(gòu) 簡單地說，線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集合。它有四個基本特征：

存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素

存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素

除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”。

除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前驅(qū)”。

數(shù)據(jù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。如（a1,a2,a3,.....,an）,a1為第一個元素，an為最后一個元素，此集合即為一個線性結(jié)構(gòu)的集合。

非線性結(jié)構(gòu) 與線性結(jié)構(gòu)不同，非線性結(jié)構(gòu)中的結(jié)點存在著一對多的關(guān)系，它又可以細(xì)分為樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。

數(shù)據(jù)的物理結(jié)構(gòu)又稱為存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示（又稱映像）。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。當(dāng)數(shù)據(jù)元素是由若干數(shù)據(jù)項構(gòu)成的時候，數(shù)據(jù)項的表示稱為數(shù)據(jù)域；比如一個鏈表結(jié)點，結(jié)點包含值域和指針域，這里結(jié)點可以看做一個數(shù)據(jù)元素，其中的值域和指針域都是這個數(shù)據(jù)元素的數(shù)據(jù)域。

數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有兩種不同的表示方法：順序映像和非順序映像。對應(yīng)的兩種不同的存儲結(jié)構(gòu)分別是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序映像是借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；非順序映像是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

順序存儲方法 順序存儲結(jié)構(gòu)是存儲結(jié)構(gòu)類型中的一種，該結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元中，結(jié)點之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲結(jié)構(gòu)為順序存儲結(jié)構(gòu)，通常順序存儲結(jié)構(gòu)式借助于計算機(jī)程序設(shè)計語言（例如C/C++）的數(shù)組來描述的。

鏈?zhǔn)酱鎯Ψ椒?該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)，通常借助于計算機(jī)程序設(shè)計語言（例如C/C++）的指針類型來描述它。

編程世界中存在許多不同類型的數(shù)據(jù)結(jié)構(gòu)。 其中，以下是最常用的：

Struct(結(jié)構(gòu)體)

Array(數(shù)組)

Linked list(鏈表)

Doubly linked list(雙鏈表)

Stack(棧)

Queue(隊列)

Priority Queue(優(yōu)先隊列)

Set(集合)

Map(映射)

Tree(樹)

Graph(圖)

Heap(堆)

通常，變量可以存儲單個數(shù)據(jù)類型，單個標(biāo)量數(shù)據(jù)類型只能存儲單個值。在許多情況下，我們可能需要將一些數(shù)據(jù)類型組合在一起作為單個復(fù)雜數(shù)據(jù)類型。例如，我們希望將一些學(xué)生信息存儲在學(xué)生數(shù)據(jù)類型中。 我們需要學(xué)生姓名，地址，電話號碼，電子郵件，出生日期，學(xué)生所在班級等。 為了將每個學(xué)生記錄存儲到一個獨特的學(xué)生數(shù)據(jù)類型，我們需要一個特殊的結(jié)構(gòu)。 這可以通過結(jié)構(gòu)體輕松實現(xiàn)。 換句話說，結(jié)構(gòu)體是值的容器，通常使用名稱訪問。 結(jié)構(gòu)體在C編程語言中非常流行，我們也可以在PHP中使用類似的概念。

雖然數(shù)組被認(rèn)為是PHP中的數(shù)據(jù)類型，但數(shù)組實際上是一種被所有編程平臺都使用的數(shù)據(jù)結(jié)構(gòu)。 在PHP中，數(shù)組實際上是一個有序的映射(ordered map)，我們將在稍后了解映射(map)。我們可以將多個值作為單個變量存儲在單個數(shù)組中。矩陣類型數(shù)據(jù)易于存儲在數(shù)組中，因此數(shù)組在所有編程平臺中得到廣泛使用。通常，數(shù)組是固定大小的集合，可通過順序數(shù)字索引訪問。在PHP中，數(shù)組的實現(xiàn)方式不同，您可以定義動態(tài)數(shù)組，而無需定義任何固定大小的數(shù)組。數(shù)組可以有不同的維度。 如果一個數(shù)組只有一個索引來訪問一個元素，我們稱之為單維數(shù)組。 但是如果需要兩個或更多索引來訪問元素，我們分別稱它為二維或多維數(shù)組。 以下是兩個數(shù)組數(shù)據(jù)結(jié)構(gòu)圖：

鏈表是線性數(shù)據(jù)結(jié)構(gòu)，它是數(shù)據(jù)元素的集合，也稱為節(jié)點，可以具有不同的大小。通常，列出的數(shù)據(jù)元素通過稱為鏈接的指針鏈接，因此稱為鏈接列表。在鏈表中，一個列表元素通過指針鏈接到下一個元素。從下圖中，我們可以看到鏈表實際上維護(hù)了一個有序集合。 鏈表是編程語言使用的最常見和最簡單的數(shù)據(jù)結(jié)構(gòu)形式。 在單個鏈表中，我們只能前進(jìn)。

注意：指針存儲變量地址。

雙向鏈表是一種特殊類型的鏈表，不僅存儲下一個節(jié)點的指針，還將前一個節(jié)點指針存儲在節(jié)點結(jié)構(gòu)。因此，它可以在列表中前后移動。 它通過同時包含前一個和下一個指針，提供比單鏈表更多的靈活性。下圖描述了一個雙向鏈表。

棧是一個具有后進(jìn)先出（last in first out）原理的線性數(shù)據(jù)結(jié)構(gòu)。因此，棧只在一端添加新元素或刪除元素。 它是計算機(jī)技術(shù)中最古老，最常用的數(shù)據(jù)結(jié)構(gòu)之一。我們總是使用名為棧頂?shù)膯蝹€點在棧中添加或刪除元素。 術(shù)語“入棧（push）”用于指示添加元素到棧頂，“出棧（pop）”是從棧頂頂刪除元素。下圖描述了棧。

隊列是遵循先進(jìn)先出(first in first out)原理的另一種線性數(shù)據(jù)結(jié)構(gòu)。隊列允許對集合進(jìn)行兩個基本操作。 第一個是入隊（enqueue），它允許我們將一個元素添加到隊列的后面。 第二個是（出隊）dequeue，它允許我們從隊列的前面刪除一個元素。 隊列是計算機(jī)技術(shù)中最常用的數(shù)據(jù)結(jié)構(gòu)之一。下圖描述了隊列。

集合(Set)是一種抽象數(shù)據(jù)類型，用于存儲某些值。集合(Set)不像我們從中檢索特定值的集合(Collection)那樣使用; 集合(Set)用于檢查其中是否存在值。這些值不以任何特定順序存儲，且集合中不應(yīng)有任何重復(fù)值?？梢詫⒓蠑?shù)據(jù)結(jié)構(gòu)進(jìn)行排序，并將其稱為有序集合(Ordered Set)。

映射是鍵值對的集合(Collection)，其中所有鍵都是唯一的。我們可以將映射視為一個所有鍵都是唯一的關(guān)聯(lián)數(shù)組。實際上，PHP數(shù)組是有序映射的實現(xiàn)。

樹是計算領(lǐng)域中使用最廣泛的非線性數(shù)據(jù)結(jié)構(gòu)。 它高度用于分層數(shù)據(jù)結(jié)構(gòu)。樹由節(jié)點組成，并且有一個特殊節(jié)點，稱為樹根，它是樹結(jié)構(gòu)的開始。其他節(jié)點派生于根節(jié)點。樹數(shù)據(jù)結(jié)構(gòu)是遞歸的，這意味著樹可以包含許多子樹。節(jié)點通過邊緣相互連接。下圖描述了樹。

圖數(shù)據(jù)結(jié)構(gòu)是一種特殊類型的非線性數(shù)據(jù)結(jié)構(gòu)，由有限數(shù)量的頂點或節(jié)點以及邊或弧組成。圖表既可以是有向的，也可以是無向的。 有向圖清楚地表示邊緣的方向，而無向圖提示邊緣而不是方向。 結(jié)果，在無向圖中，邊緣的兩個方向都被認(rèn)為是單個邊緣。 換句話說，我們可以說圖是一對集合（V，E），其中V是頂點集，E是邊集：

V = {A, B, C, D, E, F}
  E = {AB, BC, CE, ED, EF, DB}

在有向圖中，邊AB不同于邊BA，而在無向圖中，AB和BA都相同。 圖數(shù)據(jù)結(jié)構(gòu)可以很方便地解決計算機(jī)領(lǐng)域中的許多復(fù)雜問題。下圖描述了圖數(shù)據(jù)結(jié)構(gòu)。

堆是一種特殊的基于樹的數(shù)據(jù)結(jié)構(gòu)，它滿足堆屬性。最大的鍵是根，較小的鍵是葉子，稱為最大堆?；蛘撸钚〉逆I是根，較大的鍵是葉子，稱為最小堆。雖然堆結(jié)構(gòu)的根是樹的最大或最小鍵，但它不一定是排序結(jié)構(gòu)。 堆用于解決圖算法的效率和排序。下圖描述了最大堆。

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記（一）