## 數據結構 數據結構具體指同一類數據元素中，各元素之間的相互關系，包括三個組成成分，**數據的邏輯結構**，**數據的存儲結構**和**數據運算結構**。 ### 數據(Data) - 數據是客觀事物的符號表示，在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。 - 數據元素(Data Element) :是數據的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數據元素可由若干個數據項(Data Item)組成。 - 數據項(Data Item) : 是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。 - 數據對象(Data Object) :是性質相同的數據元素的集合，是數據的一個子集。如字符集合C={‘A’,’B’,’C,…} 。 - 數據結構 :相互之間具有一定聯系的數據元素的集合。 - 數據的邏輯結構 : 數據元素之間的相互關系稱為邏輯結構。 - 數據操作 : 對數據要進行的運算 - 數據類型(Data Type):指的是一個值的集合和定義在該值集上的一組操作的總稱。 ### 數據的邏輯結構 - 集合：結構中數據元素之間除了“屬于同一個集合"外,再也沒有其他的關系 - 線性結構：結構中的數據元素存在一對一的關系 - 樹形結構：結構中的數據元素存在一對多的關系 - 網狀或者圖狀結構：結構中的數據元素存在多對多的關系 ### 數據的存儲結構 由數據元素之間的關系在計算機中有兩種不同的表示方法——順序表示和非順序表示，從則導出兩種儲存方式，順序儲存結構和鏈式儲存結構 - 順序存儲結構：用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯結構(關系)，數據元素存放的地址是連續的 - 鏈式存儲結構：在每一個數據元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數據元素之間的邏輯結構(關系)，數據元素存放的地址是否連續沒有要求 - 索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址 數據的邏輯結構和物理結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構 ## 常見數據結構 ### 數組 > 把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數據元素的集合稱為數組 兩個特點：相同類型、有序 這個數組不等于PHP的數組。PHP數組本質是一個哈希表。通過數組實現  ### 鏈表 鏈表是一種物理存儲單元上非連續、非順序的存儲結構 ，由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 PHP SPL標準庫中有SplDoublyLinkedList （雙向鏈表）  鏈表的操作：插入、遍歷、查找、刪除 ```php $dlist=new SplDoublyLinkedList(); $dlist->push(1);//追加到末端 $dlist->add(1,3);//在index=1添加 //遍歷 for($dlist->rewind();$dlist->valid();$dlist->next()){ echo $dlist->current()."<br/>"; } ``` ### 棧 > 是只能在某一端插入和刪除的特殊[**線性表**]。它按照**先進后出**的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最后一個數據被第一個讀出來）。 PHP中SPL標準庫中有對應的實現 [SplStack ](http://php.net/manual/zh/class.splstack.php) 棧的兩個操作 出棧pop、入棧push ```php $q = new SplStack(); $q[] = 1; $q[] = 2; $q[] = 3; $q->push(4); $q->push(5); echo $q->pop();//5 ``` ### 隊列 > 一種特殊的[線性表]，它只允許在表的[前端]（front）進行刪除操作，而在表的末端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列是按照“先進先出”或“后進后出”FIFO的原則組織數據的。隊列中沒有元素時，稱為空隊列。 PHP SPL標準庫中有[SplQueue ](http://php.net/manual/zh/class.splqueue.php) 隊列的兩個操作 入隊列enqueue、出隊列dequeue ```php $q = new SplQueue(); $q->enqueue(array("FooBar", "foo")); $q->enqueue(array("FooBar", "bar")); $q->enqueue(array("FooBar", "msg", "Hi there!")); $f = $q->dequeue(); ``` ### 樹 它是由n（n>=1）個有限節點組成一個具有層次關系的[集合]。是一對多的關系。 （1）有且僅有一個結點 K0，他對于關系N來說沒有前驅，稱K0為樹的根結點。簡稱為根（root)）。　 （2）除K0外，K中的每個結點，對于關系N來說有且僅有一個前驅。 （3）K中各結點，對關系N來說可以有m個后繼（m>=0）。  #### 1. 二叉樹 除了葉以外的結點，都有兩個子。（葉就是在它和根的路徑上，沒有比他更遠的結點了，也可以理解為，只有一個結點和它相連，并且它不是根，那么他就是葉） #### 2. 二叉搜索樹 二叉搜索樹，也稱有序二叉樹,排序二叉樹，是指一棵空樹或者具有下列性質的二叉樹： 1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 3. 任意節點的左、右子樹也分別為二叉查找樹。 4. 沒有鍵值相等的節點。 #### 3. 樹的遍歷 - 先序遍歷 訪問根結點——》訪問左子樹——》訪問右子樹 - 中序遍歷 先訪問左子樹，再訪問根，再訪問右子樹。 - 后序遍歷 訪問根結點——》訪問右子樹——》訪問左子樹 ### 堆 堆是一種特殊的樹形數據結構，每個結點都有一個值。通常我們所說的堆的數據結構，是指二叉堆。堆的特點是根結點的值最小（或最大），且根結點的兩個子樹也是一個堆。 比如我們查找top N 就可以用堆  PHP中有堆的實現SplMaxHeap (大端堆)、SplMaxHeap （小端堆） ### 散列表【HashTable】 K=>V結構。若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(Hash function)，按這個思想建立的表為[散列表]。 #### 沖突 若 key1 ≠ key2 ，而 f(key1) = f(key2)，這種情況稱為**沖突**(Collision)。 #### 構造哈希函數 常見的構造哈希表的方法有 5 種： **（1）直接定址法** 說白了，就是小學時學過的**一元一次方程**。 即 f(key) = a * key + b。其中，a和b 是常數。 **（2）數字分析法** 假設關鍵字是R進制數（如十進制）。并且哈希表中**可能出現的關鍵字都是事先知道的**，則可選取關鍵字的若干數位組成哈希地址。 選取的原則是使得到的哈希地址盡量避免沖突，即所選數位上的數字盡可能是隨機的。 **（3）平方取中法** 取關鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數時不一定能知道關鍵字的全部情況，僅取其中的幾位為地址不一定合適； 而一個數平方后的中間幾位數和數的每一位都相關， 由此得到的哈希地址隨機性更大。取的位數由表長決定。 **（4）除留余數法** 取關鍵字被某個**不大于哈希表表長** m 的數 p 除后所得的余數為哈希地址。 即 f(key) = key % p (p ≤ m) 這是一種**最簡單、最常用**的方法，它不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模。 注意：p的選擇很重要，如果選的不好，容易產生沖突。根據經驗，**一般情況下可以選p為素數**。 ### 沖突解決 **1）開放定址法** 如果兩個數據元素的哈希值相同，則在哈希表中為后插入的數據元素另外選擇一個表項。 當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程序就會繼續往后查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項 **2）拉鏈法** 將哈希值相同的數據元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須采用線性查找方法。在這種方法中，哈希表中每個單元存放的不再是記錄本身，而是相應同義詞單鏈表的頭指針。 ### 圖 圖是由結點的有窮集合V和邊的集合E組成。其中，為了與樹形結構加以[區別]，在圖結構中常常將結點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。  學習資料: - [https://visualgo.net/en](https://visualgo.net/en) - [http://www.cnblogs.com/jingmoxukong/p/4329079.html](http://www.cnblogs.com/jingmoxukong/p/4329079.html) - [https://www.studytonight.com/data-structures/introduction-to-data-structures](https://www.studytonight.com/data-structures/introduction-to-data-structures) - [https://www.tutorialspoint.com/data_structures_algorithms/index.htm](https://www.tutorialspoint.com/data_structures_algorithms/index.htm)