摘要：數據結構數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。不同類型的數據結構編程世界中存在許多不同類型的數據結構。可以將集合數據結構進行排序，并將其稱為有序集合。

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

數據項是數據結構中討論的最小單位，是數據記錄中最基本的，不可分的數據單位。

數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。數據結構包括3方面的內容：邏輯結構，存儲結構和對數據的運算

數據的邏輯結構是對數據之間關系的描述，它與數據的存儲結構無關，同一種邏輯結構可以有多種存儲結構。歸納起來數據的邏輯結構主要有兩大類。

線性結構 簡單地說，線性結構是一個數據元素的有序（次序）集合。它有四個基本特征：

存在唯一的一個被稱做“第一個”的數據元素

存在唯一的一個被稱做“最后一個”的數據元素

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

除第一元素之外，其它數據元素均有唯一的“前驅”。

數據據結構中線性結構指的是數據元素之間存在著“一對一”的線性關系的數據結構。如（a1,a2,a3,.....,an）,a1為第一個元素，an為最后一個元素，此集合即為一個線性結構的集合。

非線性結構 與線性結構不同，非線性結構中的結點存在著一對多的關系，它又可以細分為樹形結構和圖形結構。

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

數據元素之間的關系在計算機中有兩種不同的表示方法：順序映像和非順序映像。對應的兩種不同的存儲結構分別是順序存儲結構和鏈式存儲結構。順序映像是借助數據元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；非順序映像是借助指針表示數據元素之間的邏輯關系。

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

鏈式存儲方法 該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構，通常借助于計算機程序設計語言（例如C/C++）的指針類型來描述它。

編程世界中存在許多不同類型的數據結構。 其中，以下是最常用的：

Struct(結構體)

Array(數組)

Linked list(鏈表)

Doubly linked list(雙鏈表)

Stack(棧)

Queue(隊列)

Priority Queue(優先隊列)

Set(集合)

Map(映射)

Tree(樹)

Graph(圖)

Heap(堆)

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

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

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

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

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

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

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

集合(Set)是一種抽象數據類型，用于存儲某些值。集合(Set)不像我們從中檢索特定值的集合(Collection)那樣使用; 集合(Set)用于檢查其中是否存在值。這些值不以任何特定順序存儲，且集合中不應有任何重復值。可以將集合數據結構進行排序，并將其稱為有序集合(Ordered Set)。

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

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

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

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

在有向圖中，邊AB不同于邊BA，而在無向圖中，AB和BA都相同。 圖數據結構可以很方便地解決計算機領域中的許多復雜問題。下圖描述了圖數據結構。

堆是一種特殊的基于樹的數據結構，它滿足堆屬性。最大的鍵是根，較小的鍵是葉子，稱為最大堆。或者，最小的鍵是根，較大的鍵是葉子，稱為最小堆。雖然堆結構的根是樹的最大或最小鍵，但它不一定是排序結構。 堆用于解決圖算法的效率和排序。下圖描述了最大堆。

數據結構學習筆記（一）