一、線性結構

1.1 順序表

1. 定義和特性：順序表是一種線性表的存儲結構，它采用一段地址連續的存儲單元依次存儲線性表中的元素。順序表具有隨機訪問的特性，即可以通過元素的下標直接訪問元素。

2. 實現方式：順序表可以通過數組來實現，數組的下標即為順序表中元素的位置。實現方式簡單高效，支持常數時間的隨機訪問。

3. 操作與復雜度：順序表支持基本的插入、刪除、查找等操作。其中，隨機訪問的時間復雜度為O(1)，順序查找的時間復雜度為O(n)，插入和刪除操作的時間復雜度為O(n)。順序表的空間復雜度為O(n)。

4. 適用場景：順序表適用于元素個數固定或變化不大的情況，以及需要經常進行隨機訪問而不太頻繁插入和刪除操作時效果較好。由于對內存的連續性要求，對于較大的動態數據集合，可能需要頻繁擴展內存并進行數據移動，會影響性能。

5. 相關算法：順序表的算法包括順序查找、二分查找等，這些算法可以利用順序表的特性進行實現，提高查找效率。

6. 應用實例：順序表廣泛應用于程序開發中，例如在一些編程語言中的數組就是采用順序表的方式實現的。在內存中，數組也是一種順序表的典型表示方式。

【數據結構和算法】順序表（動態順序表、頭插、尾插、任意位置插入、頭刪、尾刪、任意位置刪除、遍歷查找、二分查找）_順序表頭部插入-CSDN博客

1.2 鏈表

1. 定義和特性：鏈表是一種線性表的存儲結構，它由一系列節點組成，每個節點包含數據元素和指向下一個節點的指針。鏈表可以分為單向鏈表、雙向鏈表和循環鏈表等不同類型。鏈表的特點是不要求內存空間連續，可以動態地分配和回收內存，因此適用于頻繁插入和刪除的場景。

2. 實現方式：鏈表通過節點之間的指針來實現元素之間的連接。每個節點包含一個數據元素和一個指向下一個節點的指針（雙向鏈表還包含指向前一個節點的指針）。鏈表的實現方式相對靈活，可以隨時動態改變鏈表的結構。

3. 操作與復雜度：鏈表支持基本的插入、刪除、查找等操作。插入和刪除操作的時間復雜度為O(1)，查找操作的時間復雜度為O(n)。鏈表的空間復雜度為O(n)，每個節點需要額外的存儲空間來存儲指針。

4. 適用場景：鏈表適用于頻繁插入和刪除操作的場景，以及對內存空間要求不連續的場景。在實際應用中，例如在實現隊列、棧、哈希表等數據結構時，常常會使用鏈表來實現。

5. 相關算法：鏈表的相關算法包括反轉鏈表、合并兩個有序鏈表、檢測鏈表是否有環等。這些算法都是基于鏈表特性的實現，對于某些問題提供了較為高效的解決方案。

6. 應用實例：鏈表廣泛應用于計算機科學中，例如在操作系統中的進程調度、在數據庫中的存儲結構、在圖形學中的多邊形表示等都有鏈表的影子。此外，許多編程語言的標準庫中也包含了鏈表的實現。

【數據結構和算法】鏈表（順序表 VS 鏈表、8種鏈表結構、單鏈表、雙向鏈表）-CSDN博客

【數據結構和算法】單鏈表（無頭單向非循環鏈表、單鏈表的增、刪、查、改等基本操作、單鏈表的圖形表示、帶哨兵位的單鏈表）_帶哨兵的單鏈表的示意圖-CSDN博客

【數據結構和算法】雙向鏈表（帶頭雙向循環鏈表、“增、刪、查、改”基本操作）_循環雙鏈表的插入刪除-CSDN博客

1.3 棧 & 隊列

1. 定義和特性：

   • 棧（Stack）是一種后進先出（LIFO）的數據結構，只允許在棧頂進行插入（入棧）和刪除（出棧）操作。

   • 隊列（Queue）是一種先進先出（FIFO）的數據結構，允許在隊列的一端插入元素（入隊），另一端刪除元素（出隊）。

2. 實現方式：

   • 棧可以使用數組或鏈表來實現。數組實現的棧稱為順序棧，鏈表實現的棧稱為鏈式棧。

   • 隊列同樣可以使用數組或鏈表來實現。數組實現的隊列稱為順序隊列（循環隊列），鏈表實現的隊列稱為鏈式隊列。

3. 操作與復雜度：

   • 棧的基本操作包括入棧和出棧操作。入棧和出棧的時間復雜度均為O(1)。

   • 隊列的基本操作包括入隊和出隊操作。入隊和出隊的時間復雜度均為O(1)。

4. 適用場景：

   • 棧適用于需要后進先出的場景，例如函數的調用棧、表達式求值、括號匹配等。

   • 隊列適用于需要先進先出的場景，例如任務調度、消息傳遞等。

5. 相關算法：

   • 棧的相關算法包括中綴表達式轉后綴表達式、非遞歸函數的實現、深度優先搜索等。

   • 隊列的相關算法包括廣度優先搜索、實現緩存、任務調度等。

6. 應用實例：

   • 棧的應用場景包括瀏覽器的歷史記錄、編輯器的撤銷操作、系統調用的存儲等。

   • 隊列的應用場景包括消息隊列、生產者消費者模式、打印任務隊列等。

【數據結構和算法】棧和隊列_-CSDN博客

1.4 雙端隊列

1. 定義和特性：在C++ STL（Standard Template Library）中，deque（雙端隊列）是一種動態數組，類似于 vector，但它允許在隊列的任意一端進行插入和刪除操作。deque可以根據需要動態增長和收縮。

2. 實現方式：deque在內部使用了一片連續的存儲空間，并使用分段連續內存塊的方式來實現。每個內存塊中包含多個元素，并且內存塊之間通過指針進行鏈接，形成一個鏈式結構。這種實現方式使得在隊頭和隊尾進行插入和刪除操作的時間復雜度都是O(1)。

3. 操作與復雜度：deque支持的基本操作包括在隊頭插入元素（push_front）、在隊尾插入元素（push_back）、在隊頭刪除元素（pop_front）、在隊尾刪除元素（pop_back）、獲取隊頭元素（front）和獲取隊尾元素（back）等。這些操作的時間復雜度都是O(1)。

4. 適用場景：deque適用于需要在隊列的兩端高效地進行插入和刪除操作的場景。與vector相比，deque在隊頭插入和刪除元素的性能更好。例如，在需要頻繁地在隊頭和隊尾進行插入和刪除操作的情況下，使用deque可以提高效率。

5. 相關算法：deque可以與其他算法結合使用，例如排序算法、搜索算法等。在排序算法中，可以使用deque作為臨時存儲空間，進行歸并排序等操作。在搜索算法中，可以使用deque作為搜索路徑的存儲結構。

6. 應用實例：deque在實際應用中有廣泛的應用，例如實現棧和隊列、實現滑動窗口等。在實現棧和隊列時，可以使用deque作為底層數據結構，實現在隊頭和隊尾進行插入和刪除操作。在滑動窗口算法中，可以使用deque來存儲窗口中的元素，并進行插入和刪除操作，以便高效地計算窗口內的特定結果。

【STL】stack & queue & priority_queue {棧，隊列，優先級隊列的介紹及使用；仿函數/函數對象；容器適配器，雙端隊列deque}_容器link、隊列、棧、優先隊列、bitset的使用方法-CSDN博客

---

二、樹形結構

2.1 堆

1. 定義和特性：堆（Heap）是一種特殊的樹形數據結構，它滿足堆屬性：對于堆中任意節點i的值都要大于等于（或小于等于）其子樹中每個節點的值。根據堆屬性的不同，堆可以分為最大堆（每個節點的值大于等于其子節點的值）和最小堆（每個節點的值小于等于其子節點的值）。

2. 實現方式：堆通常使用數組來實現，將父節點和子節點的關系映射到數組的索引上。這種實現方式可以較為高效地進行插入和刪除操作，并且能夠滿足堆的性質。

3. 操作與復雜度：堆主要支持插入元素、刪除元素、查找堆頂元素等操作。插入和刪除的時間復雜度為O(log n)，其中n為堆中元素的個數。查找堆頂元素的時間復雜度為O(1)。

4. 適用場景：堆適用于需要快速找到最大值或最小值的場景，例如優先級隊列、堆排序、定時器事件等。

5. 相關算法：堆的相關算法包括向下調整建堆O(n)、堆排序O(nlogn)、Top k 問題（尋找前k大或前k小的元素）等。

6. 應用實例：堆廣泛應用于計算機科學中，例如操作系統的進程調度、網絡通信的數據包傳輸、圖算法中的Dijkstra算法等都可能用到堆結構。

【數據結構和算法】樹和二叉樹（樹的概念及結構、二叉樹概念及結構）_二叉樹和樹的結構-CSDN博客

【數據結構與算法】二叉樹的順序結構—堆（堆的基本實現，TopK問題，堆排序）-CSDN博客

2.2 AVL樹

1. 定義和特性：AVL樹是一種自平衡二叉搜索樹，它滿足平衡因子的限制：對于AVL樹的任意節點，其左子樹高度與右子樹高度之差的絕對值不超過1。通過維持平衡因子的要求，AVL樹能夠保持樹的高度較小，以提高查找等操作的效率。

2. 實現方式：AVL樹的實現方式與普通的二叉搜索樹類似，每個節點包含一個關鍵字和左右子節點的指針。當進行插入或刪除操作時，需要通過對節點進行旋轉和調整，使樹保持平衡。

3. 操作與復雜度：AVL樹支持插入、刪除、查找等基本操作，這些操作的時間復雜度為O(log n)，其中n為樹中節點的數量。由于AVL樹的平衡性質，對于平衡的AVL樹，查找操作的平均時間復雜度為O(log n)。

4. 適用場景：AVL樹適用于需要頻繁執行插入、刪除和查找操作，并且對查詢性能要求較高的場景。例如，在數據庫的索引結構、編譯器中的符號表、字典等應用中常使用AVL樹以提高查詢效率。

5. 相關算法：AVL樹的相關算法包括插入操作、刪除操作、平衡操作等。這些算法通過對樹的旋轉、調整和重平衡等操作來維持樹的平衡性。

6. 應用實例：AVL樹在計算機科學中有廣泛的應用，例如在數據庫系統中用于索引，以提高查詢和排序的效率。此外，在編程語言的標準庫中，也常常包含AVL樹的實現。

【數據結構和算法】二叉樹的鏈式結構（二叉樹的創建、銷毀；二叉樹的前中后序遍歷；求二叉樹的高度；求二叉樹節點、葉子節點、第K層節點的個數；查找二叉樹節點；判斷是否是完全二叉樹）-CSDN博客

【高階數據結構】二叉搜索樹 {概念；實現：核心結構，增刪查，默認成員函數；應用：K模型和KV模型；性能分析；相關練習}-CSDN博客

【高階數據結構】AVL樹 {概念及實現；節點的定義；插入并調整平衡因子；旋轉操作：左單旋，右單旋，左右雙旋，右左雙旋；AVL樹的驗證及性能分析}-CSDN博客

2.3 紅黑樹

1. 定義和特性：紅黑樹是一種自平衡的二叉搜索樹，它在滿足二叉搜索樹的性質的同時，引入了顏色標記和一些額外的規則來保持樹的平衡。紅黑樹具有以下特性：

   • 每個節點都有一個顏色，可以是紅色或黑色。
   • 根節點是黑色的。
   • 所有NIL結點都是黑色的。（NIL節點即空結點，空樹也是紅黑樹）
   • 如果一個節點是紅色的，則它的兩個子節點都是黑色的。
   • 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

2. 實現方式：紅黑樹的實現方式基于二叉搜索樹的基本結構，同時引入顏色標記和旋轉操作，以確保樹始終保持平衡。在插入或刪除節點時，需要對樹進行調整，通過變換節點的顏色和進行旋轉來維持紅黑樹的性質。

3. 操作與復雜度：紅黑樹支持插入、刪除、查找等基本操作，這些操作的最壞情況下的時間復雜度為O(log n)，其中n為樹中節點的數量。由于紅黑樹的平衡性質，查找操作的平均時間復雜度也為O(log n)。

4. 適用場景：紅黑樹適用于需要頻繁執行插入、刪除和查找操作，并且對平衡性能要求較高的場景。例如在STL中的map和set容器的實現中，通常會采用紅黑樹作為底層數據結構。

5. 相關算法：紅黑樹的相關算法包括插入節點、刪除節點、旋轉操作、顏色翻轉等。這些算法通過對節點進行旋轉和顏色變換來維護紅黑樹的平衡性。

6. 應用實例：紅黑樹在計算機科學中有廣泛的應用，如在數據庫系統中用于索引、在編程語言的標準庫中用于實現map、set等容器等。

【高階數據結構】紅黑樹 {概念及性質；紅黑樹的結構；帶頭結點的紅黑樹；紅黑樹的實現；紅黑樹插入操作詳細解釋；紅黑樹的驗證}_紅黑樹抽象數據結構-CSDN博客

2.4 哈夫曼樹

1. 定義和特性：哈夫曼樹是一種特殊的二叉樹，它是一種最優二叉樹，用于編碼和解碼一組字符。哈夫曼樹的特性是：權值越大的節點離根節點越近，而權值越小的節點離根節點越遠。這種特性保證了哈夫曼樹的前綴碼性質，使得編碼和解碼過程簡單高效。

2. 實現方式：哈夫曼樹通常通過貪心算法構建。構建過程中，首先創建一個只包含單個字符節點的森林，然后選擇兩個權值最小的節點合并為一個新的節點，并把新節點的權值設為兩個被合并節點的權值之和。重復此過程，直到森林中只剩下一個樹，即為哈夫曼樹。

3. 操作與復雜度：哈夫曼樹的主要操作是構建和編解碼。構建哈夫曼樹的時間復雜度為O(nlogn)（使用優先級隊列選取最小權重的節點），其中n為字符集的大小。編解碼的時間復雜度為O(m)（取決于字符在哈夫曼樹中的深度），其中m為待編解碼的字符串長度。

4. 適用場景：哈夫曼樹適用于需要對一組字符進行編碼和解碼的場景。例如在數據壓縮算法中，哈夫曼樹被廣泛應用于無損壓縮，將出現頻率高的字符使用較短的編碼表示，從而減小文件的大小。

5. 相關算法：哈夫曼樹的相關算法包括構建算法（如貪心算法）、編碼算法和解碼算法。構建算法通過合并節點來構建哈夫曼樹，編碼算法將字符映射到哈夫曼樹上的路徑，解碼算法通過遍歷哈夫曼樹來還原字符。

6. 應用實例：哈夫曼樹在計算機科學中有廣泛的應用。例如，在數據壓縮算法中，如ZIP和GZIP等，使用哈夫曼樹進行編碼和解碼以減小文件的大小。此外，在通信領域中，哈夫曼樹也被用于數據傳輸的壓縮和解壓縮。

終于把哈夫曼樹搞明白了(一)_哈夫曼樹的引入_嗶哩嗶哩_bilibili

終于把哈夫曼樹搞明白了(二)_什么是哈夫曼樹？_嗶哩嗶哩_bilibili

終于把哈夫曼樹搞明白了(三)_如何構造哈夫曼樹?_嗶哩嗶哩_bilibili

終于把哈夫曼樹搞明白了(四)_哈夫曼樹的應用_哈夫曼編碼_嗶哩嗶哩_bilibili

2.5 B樹系列

B樹

B+樹

B*樹

1. 定義和特性：

   • B樹：B樹是一種自平衡的多路搜索樹，其節點可以包含多個子節點。根節點至少有1個鍵，2個孩子；每個分支節點都包含k-1個鍵和k個孩子，其中 ceil(m/2) ≤ k ≤ m（ceil是向上取整函數）；所有的葉子節點都在同一層；節點中的鍵按升序排列，節點當中k-1個鍵正好是k個孩子包含的元素的值域劃分
   • B+樹：B+樹是在B樹基礎上做了改進的一種多路搜索樹。分支節點的子樹指針與關鍵字個數相同；B+樹的分支節點只存儲key不存儲value，分支節點相當于是葉子節點的索引，葉子節點才是存儲數據的數據層；分支節點中的關鍵字其實是對應子樹中的最小值；所有葉子節點按照鍵的升序連接起來形成一個有序鏈表，方便范圍查詢和遍歷。
   • B*樹：B*樹是在B+樹基礎上做了改進的一種多路搜索樹。B*樹對于非葉子節點的分裂不像B+樹那樣簡單地將一半分裂給新節點，將中間鍵提升到上層節點（最少m/2）。而是在插入過程中如果當前節點滿了，就將一部分數據移動到兄弟結點中，如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各移動1/3的數據到新結點（最少2/3m)，以充分利用節點的空間，減少樹的深度。

2. 實現方式：B樹、B+樹和B*樹的實現方式相似，基于多路搜索樹的結構，節點中的鍵值對有序排列，并且保持樹的平衡性質。在插入或刪除節點時，需要對樹進行調整，通過節點的分裂或合并來維持樹的平衡。

3. 操作與復雜度：這三種樹結構的操作包括插入、刪除、查找等，具有相似的時間復雜度。對于一棵節點為N，度為M的B樹，查找和插入需要最少log{M}N次 ~ 最多log{M/2}N + 1次比較（M/2向上取整）。由于B+樹和B*樹葉子節點之間建立了有序鏈表，所以范圍查詢更加高效。

4. 適用場景：B樹（系列）是一種適合外查找的樹，他通過提高節點度數、增加關鍵字個數，來壓縮高度、減少查找次數，從而達到減少磁盤I/O操作的目的

5. 相關算法：B樹、B+樹和B*樹的相關算法包括插入、刪除、節點分裂和合并等。這些算法通過調整節點的結構來保持樹的平衡，并提高樹的性能。

6. 應用實例：B樹、B+樹和B*樹在數據庫系統、文件系統和操作系統等領域中有廣泛的應用。

【高階數據結構】B樹 {B樹的概念；B樹的實現：節點設計，查找，插入，遍歷，刪除；B樹的性能分析；B+樹和B*樹；B樹的應用}-CSDN博客

2.6 并查集

1. 定義和特性：并查集是一種數據結構，用于管理元素的分組和連接性。并查集中的每個元素都被視為一個節點，可以根據節點間的連接關系將它們分為若干個不相交的集合。并查集具有以下特性：

   • 支持兩種操作：查找（find）和合并（union）。
   • 查找操作用于確定元素所屬的集合，即找到元素的根節點。
   • 合并操作用于將兩個集合合并成一個集合，即將其中一個集合的根節點指向另一個集合的根節點。

2. 實現方式：并查集通常使用數組或樹結構來實現。使用數組實現時，可以通過記錄每個元素的根節點來表示集合的連接關系。使用樹結構實現時，可以使用樹的根節點表示集合，并按需連接不相交的集合。

3. 操作與復雜度：并查集支持查找操作和合并操作，這兩種操作的時間復雜度都可以達到接近O(1)的水平。這是因為在合并時，可以通過路徑壓縮和按秩合并等技術來盡量降低樹的深度，從而提高查找和合并操作的效率。

4. 適用場景：并查集適用于需要快速判斷元素之間連接性的場景，比如在圖論中用于判斷圖的連通性、Kruskal算法中用于最小生成樹的構建、集合合并的問題等。

5. 相關算法：并查集的相關算法包括查找操作、合并操作、路徑壓縮和按秩合并等。這些算法可以有效提高并查集的查詢和合并性能。

6. 應用實例：并查集在各種離散數學問題、圖論問題和算法設計中有廣泛的應用，如Kruskal算法、社交網絡中的好友關系判斷等。

【高階數據結構】并查集 {并查集原理；并查集優化；并查集實現；并查集應用}_并查集，10w個人組成的多少個朋友圈-CSDN博客

---

三、哈希結構

3.1 哈希表

1. 定義和特性：哈希表是一種數據結構，通過計算哈希函數，將鍵映射到存儲桶中。它具有快速的查找、插入和刪除操作，并且在理想情況下具有常數時間復雜度。哈希表由鍵值對組成，每個鍵唯一對應一個值。

2. 實現方式：哈希表內部通常由一個數組和對應的哈希函數組成。哈希函數將鍵映射到數組的特定位置（存儲桶）。在哈希沖突時，通常采用鏈表、平衡樹等方式解決。

3. 操作與復雜度：哈希表支持的基本操作包括插入（put）、查找（get）、刪除（remove）等。在理想情況下，這些操作的時間復雜度為O(1)，但在存在哈希沖突時，復雜度可能會退化。

4. 適用場景：哈希表適用于需要快速查找、插入和刪除操作，并且鍵值唯一的場景中。它在處理大規模數據中通常具有很高的性能。

5. 相關算法：哈希表與哈希函數相關聯，其設計和優化都與哈希函數密切相關。另外，哈希表也與哈希沖突解決算法相關，如拉鏈法、線性探測法等。

6. 應用實例：哈希表在實際工程中廣泛應用。例如，在編程語言中的哈希表數據結構，用于實現關聯數組或字典；在數據庫系統中的哈希索引，用于加速數據檢索等。

【高階數據結構】哈希表 {哈希函數和哈希沖突；哈希沖突的解決方案：開放定址法，鏈地址法；紅黑樹結構 VS 哈希結構}-CSDN博客

3.2 位圖

1. 定義和特性：位圖是一種數據結構，它由一個二進制位數組或者比特數組組成，每個位（bit）只能存儲 0 或 1。位圖通常被用來表示大量整數的集合，通過位的狀態來表示該整數是否出現在集合中。位圖支持高效的位操作（如按位與、按位或、按位異或等），適合用于高效地存儲和操作大量的布爾型數據。

2. 實現方式：位圖可以被實現為一個數組，其中每個元素都是一個字節，而每個字節又包含8個位。對于很大的位圖，可以使用多個數組進行分段存儲。位圖通常不僅僅用于表示整數的集合，還可以用于標記某個特定值是否存在。

3. 操作與復雜度：位圖支持的基本操作包括設置某一位為 1，清除某一位為 0，或者測試某一位的狀態等。因為位圖的底層數據結構是二進制數組，所以這些基本操作可以在常數時間內完成。

4. 適用場景：位圖通常在需要高效地表示大規模的布爾型數據集合時使用。舉例來說，它可以應用于網絡流量分析、數據庫索引、壓縮算法、密碼學等領域。

5. 相關算法：位圖與位運算相關緊密，通過位運算可以高效地對位圖進行操作。這包括與、或、非、異或等操作。另外，位圖所涉及的算法還包括位圖的壓縮算法、位圖的搜索算法等。

6. 應用實例：位圖在實際工程中有多種應用。例如，在搜索引擎中，位圖被用來表示網頁的索引；在數據庫系統中，位圖索引可以用來加速查詢操作；在計算機網絡中，位圖可以用于IP地址的查找。

【高階數據結構】哈希的其他應用 {位圖的介紹及實現，位圖的組合應用；布隆過濾器的介紹及實現，布隆過濾器的應用；哈希切分}-CSDN博客

3.3 布隆過濾器

1. 定義和特性：布隆過濾器是一種空間高效的數據結構，用于判斷一個元素是否屬于一個集合。它由一個位數組和多個哈希函數組成。插入元素時，將元素經過多個哈希函數映射到位數組上；查詢元素時，通過同樣的哈希函數映射到位數組上，如果所有對應位都為1，則可能存在該元素，如果有一個為0則一定不存在。因此布隆過濾器可能存在一定的誤判率。

2. 實現方式：布隆過濾器通常使用一個位數組表示，同時使用多個哈希函數來映射元素到位數組上。當插入元素時，對應的位被標記為1；當查詢元素時，檢查對應的位，如果所有位都為1，則可能存在該元素。

3. 操作與復雜度：布隆過濾器支持的基本操作包括插入元素和查詢元素。插入和查詢的時間復雜度都是O(k)，其中k為哈希函數的個數。布隆過濾器的空間復雜度與位數組的大小有關，但通常情況下是與預期容量和誤判率相關的。

4. 適用場景：布隆過濾器適合用于處理大量數據集合的成員關系查詢，并且可以容忍一定的誤判率。它在緩存、數據庫查詢、垃圾郵件過濾等領域有廣泛的應用。

5. 相關算法：布隆過濾器涉及的算法主要是哈希函數的選擇和位數組的操作。另外，還有一些改進的布隆過濾器，如Counting Bloom Filter和Scalable Bloom Filter等。

6. 應用實例：布隆過濾器在實際工程中有多種應用。例如，網絡路由器使用布隆過濾器來快速決定一個給定IP地址是否合法；在分布式系統中，布隆過濾器可以用于降低分布式緩存中的緩存穿透問題。

【高階數據結構】哈希的其他應用 {位圖的介紹及實現，位圖的組合應用；布隆過濾器的介紹及實現，布隆過濾器的應用；哈希切分}-CSDN博客

---

四、圖形結構

4.1 概括總結

1. 定義和特性：圖是一種由節點（頂點）和節點之間的連接（邊）組成的數據結構。圖可以表示各種關系和網絡結構，比如社交網絡、道路網絡等。圖可以是有向的（邊有方向）或無向的（邊沒有方向），可以是帶權的（邊有權值）或無權的（邊沒有權值）。

2. 實現方式：圖可以用多種方式來實現，常見的方式有鄰接矩陣和鄰接表。鄰接矩陣是一個二維數組，其中數組的行和列代表圖中的節點，矩陣中的元素表示節點之間的連接關系；鄰接表是使用鏈表或數組來表示每個節點的鄰居節點。

3. 操作與復雜度：圖支持的基本操作包括添加節點和邊、刪除節點和邊、查找節點和邊等。圖的操作復雜度取決于具體的實現方式和操作類型。

4. 適用場景：圖是用于表示和解決各種復雜關系和網絡問題的重要數據結構。它在網絡分析、推薦系統、路徑規劃等領域有廣泛的應用。

5. 相關算法：圖涉及的算法包括最短路徑算法（如Dijkstra算法、Bellman-Ford算法）、最小生成樹算法（如Prim算法、Kruskal算法）、圖遍歷算法（如深度優先搜索和廣度優先搜索）等。

6. 應用實例：圖在實際工程中有多種應用。例如，在社交網絡中，圖可以用于表示用戶之間的關系；在地圖導航系統中，圖可以用于表示道路網絡和計算最短路徑。

【高階數據結構】圖 {圖的基本概念；圖的存儲結構：鄰接矩陣，鄰接表；圖的遍歷：BFS，DFS}-CSDN博客

4.2 圖遍歷算法

圖遍歷算法是用于在圖結構中訪問和處理所有節點的算法。常見的圖遍歷算法包括深度優先搜索（DFS）和廣度優先搜索（BFS）。

1. 深度優先搜索（DFS）:

   • DFS是一種用于圖遍歷的算法，它從起始節點開始，一直沿著路徑直到到達最深的節點，然后再回溯到上一個節點，繼續探索下一個路徑。DFS可以通過遞歸或者使用棧來實現。
   • 優點：實現簡單，適用于尋找連通分量、拓撲排序等任務。
   • 缺點：不一定能得到最短路徑，可能會陷入深層次的路徑，不適合用于尋找最短路徑的問題。

2. 廣度優先搜索（BFS）:

   • BFS是一種用于圖遍歷的算法，它從起始節點開始，首先訪問其所有相鄰節點，然后再依次訪問這些相鄰節點的鄰居節點。BFS可以使用隊列來實現。
   • 優點：能夠搜索最短路徑，適用于尋找最短路徑的問題。
   • 缺點：需要額外的空間來存儲節點的信息，實現稍微復雜一些。

【高階數據結構】圖 {圖的基本概念；圖的存儲結構：鄰接矩陣，鄰接表；圖的遍歷：BFS，DFS}-CSDN博客

4.3 最小生成樹算法

最小生成樹算法主要有Prim算法和Kruskal算法兩種。

1. Prim算法：

   • 從任意一個頂點開始，將其加入生成樹中。
   • 選擇與生成樹相連的最短邊，將其連接的頂點加入生成樹中。
   • 重復以上步驟，直到所有頂點都已加入生成樹為止。

2. Kruskal算法：

   • 將所有邊按照權值從小到大進行排序。
   • 依次取出權值最小的邊，若該邊連接的兩個頂點不在同一連通分量中，則將其加入生成樹中。
   • 重復以上步驟，直到生成樹中包含了所有頂點。

這兩種算法都是貪心算法，通過不斷選擇當前狀態下的最優解來構建最小生成樹。它們的時間復雜度分別為O(V^2)和O(ElogE)，其中V為頂點數，E為邊數。在實際應用中，選取合適的算法取決于圖的規模和邊的數量等因素。

【高階數據結構】圖 {最小生成樹：Kruskal算法，Prim算法；最短路徑：Dijkstra算法，Bellman-Ford算法，Floyd算法}-CSDN博客

4.4 最短路徑算法

最短路徑算法主要有Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法三種。

首先初始化兩個數組，一個用來存儲源點和任意頂點之間的最短路徑的父節點，一個用來存儲最短路徑的長度。

1. Dijkstra算法（單源）：
   • 從起始頂點開始，將其加入已訪問的頂點集合，并初始化起始頂點到其他頂點的距離。
   • 選擇與起始頂點直接相連的頂點中距離最短的頂點，將其加入已訪問的頂點集合。
   • 更新起始頂點到其他頂點的距離，若經過當前已訪問的頂點到其他頂點的距離比原先的距離短，則更新距離。
   • 重復以上步驟，直到所有頂點都已加入已訪問的頂點集合。
2. Bellman-Ford算法（單源）：
   • 初始化距離數組，將起始頂點的距離設置為0，其余頂點的距離設置為無窮大。
   • 通過對所有邊進行|V|-1次松弛操作，其中|V|為頂點的數量。
   • 檢查每條邊的兩個頂點，如果經過當前邊可以獲得更短的路徑，則更新路徑長度。
   • 最后再次遍歷所有邊，檢查是否存在負權回路。
3. Floyd-Warshall算法（多源）：
   • 初始化兩個二維數組，一個用來存儲任意兩個頂點之間的最短路徑的父節點，一個用來存儲最短路徑的長度。
   • 通過三重循環，逐步嘗試將中間頂點納入考慮，即假設中間頂點k是當前考慮的點，則對于任意兩個頂點i和j，如果通過頂點k可以使得從i到j的路徑長度變短，則更新dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
   • 重復以上操作直到所有頂點都被考慮為中間節點為止。最終得到一個二維數組，其中存儲了任意兩個頂點之間的最短路徑距離。

Dijkstra算法和Bellman-Ford算法適用于單源最短路徑問題，它們的時間復雜度分別為O(V^2)和O(V*E)，其中V為頂點數，E為邊數，Bellman-Ford算法的性能較Dijkstra算法略差，但是它可以處理帶有負權邊的圖，并且能夠檢測負權回路。Floyd-Warshall算法適用于多源最短路徑問題，它的時間復雜度為O(V^3)，其中V為頂點數。選擇合適的算法取決于具體的問題需求和圖的規模等因素。

【高階數據結構】圖 {最小生成樹：Kruskal算法，Prim算法；最短路徑：Dijkstra算法，Bellman-Ford算法，Floyd算法}-CSDN博客

4.5 有向無環圖的應用

有向無環圖的應用—描述表達式、AOV網、拓撲排序、AOE網、關鍵路徑-CSDN博客

圖-拓撲排序_嗶哩嗶哩_bilibili

圖-AOE網和關鍵路徑_嗶哩嗶哩_bilibili

怎么求關鍵路徑？先求點，再求邊

源點和匯點的ve, vl相等，工程的開始和結束不能拖延

求ve：先將所有事件的ve初始化為源點的ve(0)，按照拓撲序從源點求到匯點，其他事件的ve取所有路徑活動最早開始時間的最大值（所用時間的最大值），因為要保證所有的活動都完成事件才能發生。

求vl：先將所有事件的vl初始化為匯點的vl(ve)，按照逆拓撲序從匯點求到源點，其他事件的vl取所有路徑活動最晚開始時間的最小值（結束時間-所用時間的最大值），因為要保證所有路徑活動都有足夠的時間完成。

求e：活動的最早開始時間就是開始事件的最早開始時間。

求l：活動的最晚開始時間就是結束事件的最晚開始時間-活動所用時間。

關鍵活動：e和l相等的活動

關鍵路徑：由關鍵活動連接而成的路徑，耗時最長的路徑。關鍵路徑可能不是唯一的。

時間余量：每個活動的最晚開始時間l - 最早開始時間e = 時間余量；表示該活動可以拖延的時間。關鍵活動的時間余量是0，是不能拖延的活動。

---

五、其他

5.1 跳表

1. 定義和特性：跳表是一種有序的數據結構，是一種空間換時間的設計思想。跳表通過添加多層索引來加速查詢操作，使得查詢的時間復雜度接近于O(log n)。在一層索引中，每個節點都具有指向同層下一個節點的指針。跳表可以用于替代有序鏈表和平衡二叉樹，它在某些情況下比平衡二叉樹的查詢操作更快。

2. 實現方式：跳表由一個有序鏈表組成，同時使用多層索引來加速查詢操作。每一層索引都是原始鏈表的一個子集，且節點之間的鏈接關系保持有序。通過增加層數，跳表的查詢效率逐漸提高。

3. 操作與復雜度：跳表支持的基本操作包括插入、刪除和查詢。在跳表中插入和刪除一個元素的時間復雜度為O(log n)，其中n為跳表中的元素個數。查詢操作的時間復雜度也為O(log n)。

4. 適用場景：跳表適用于需要高效的查詢操作，并且對添加和刪除操作的效率要求相對較低的場景。跳表在Redis等內存數據庫中經常被使用來提高查詢效率。

5. 相關算法：跳表涉及的算法主要是層級索引的建立和維護。常見的一種算法是跳表的插入算法，它通過隨機生成層數來建立索引，使得查詢操作的效率更高。

6. 應用實例：跳表在實際工程中有多種應用。例如，在區塊鏈技術中，跳表可以用于實現快速的交易確認；在網絡中，跳表可以用于路由表的構建和維護。

【高階數據結構】跳表 {什么是跳表-skiplist；skiplist的效率如何保證；skiplist的實現；skiplist跟平衡搜索樹和哈希表的對比}-CSDN博客