保研復習 | 數據結構

- - CH1?緒論
  - - ☆ 數據項、數據元素、數據結構
    - ☆ 邏輯結構和存儲結構的區別
    - ☆ 順序存儲結構和鏈式存儲結構的比較
    - ☆ 算法的重要特性
    - ☆ 算法的復雜度
  - CH2?線性表
  - - ☆ 單鏈表
  - CH3?棧、隊列和數組
  - - ☆ 棧和堆是什么？
    - ☆ 棧在括號匹配中的應用
    - ☆ 棧在表達式求值中的應用
    - ☆ 為什么循環隊列要犧牲一個空間？
    - ☆ 循環隊列的長度？
    - ☆ 順序表和鏈表的比較
    - ☆ 遞歸
  - CH4?串
  - - ☆ 字符串的定義
    - ☆ KMP 算法
  - CH5?樹與二叉樹
  - - ☆ 二叉樹的性質
    - ☆ 滿二叉樹和完全二叉樹的區別
    - ☆ 二叉排序樹和平衡二叉樹的區別？
    - ☆ 二叉排序樹的查找、插入與刪除過程？
    - ☆ 平衡二叉樹的插入與刪除過程？
    - ☆ B 樹和 B+ 樹的區別
    - ☆ B 樹和 B+ 樹在數據庫中的應用
    - ☆ 能不能簡單聊聊紅黑樹？
    - ☆ 哈夫曼樹
    - ☆ 樹的存儲結構
    - ☆ 二叉樹的存儲結構
  - CH6?圖
  - - ☆ 圖的定義及其類型
    - ☆ 遍歷算法
    - ☆ 最小生成樹
    - ☆ 最短路徑
    - ☆ 最小生成樹算法和最短路徑算法的優化
    - ☆ AOV 網和拓撲排序
    - ☆ 介紹一下 AOE 網？
    - ☆ 什么是關鍵路徑？
    - ☆ 如何求解關鍵路徑？
  - CH7?查找
  - - ☆ 哈希表？構造方法？
  - CH8?排序
  - - ☆ 十種排序算法
    - ☆ 快速排序的復雜度分析？
    - ☆ 構建堆的過程？堆排序的過程？
    - ☆ 歸并排序和快排的比較
  - 其他問題
  - - ○ 循環的效率一定比遞歸的高嗎？
    - ○ 貪心算法、動態規劃、分治法的區別

前言：

由于在面試中通常都是口頭進行敘述，因此我是按照怎么說怎么方便的方式來寫的，當然與那些對算法原理進行介紹的博客不能相提并論。
目前 5 拒夏 1 營還是本校營真是好痛苦 😇

參考：

保研面試復習之數據結構篇
計算機保研專業課復習 - 數據結構（更新中）
《王道 2025 年數據結構考研復習指導》

CH1?緒論

☆ 數據項、數據元素、數據結構

數據項：是構成數據元素的、不可分割的最小單位。
數據元素：是數據的基本單位。
數據結構：是相互之間存在特定關系的數據元素的集合。

數據結構的三要素是：邏輯結構、存儲結構、數據的運算。

比如：學生記錄是一個數據元素，它是由學號、姓名、性別等數據項組成的。

☆ 邏輯結構和存儲結構的區別

邏輯結構

定義：是指數據元素之間的邏輯關系，它與數據的存儲無關，是獨立于計算機的。
分類：線性結構（線性表）和非線性結構（集合、樹、圖）

存儲結構

定義：是指數據結構在計算機中的表示，即我們是如何使用計算機語言來實現邏輯結構的。
分類
- 順序存儲結構：在邏輯上相鄰的元素在物理位置上也是相鄰的。
- 鏈式存儲結構：在邏輯上相鄰的元素在物理位置上不一定相鄰。
- 索引存儲結構：在存儲元素信息的同時建立附加的索引表，索引表包括關鍵字和存儲地址。
- 散列存儲結構：根據元素的關鍵字，可以直接計算出元素的存儲地址。

☆ 順序存儲結構和鏈式存儲結構的比較

順序存儲：是一種地址空間連續、支持隨機訪問的線性結構。
- 優點：支持隨機訪問；
- 缺點：插入或刪除某個元素需要移動大量的元素；
鏈式存儲：是一種不需要地址空間連續，只需要在邏輯上通過指針連接各個元素的線性結構。
- 優點：插入或刪除元素簡單；
- 缺點：不支持隨機訪問。

☆ 算法的重要特性

算法的 5 個重要特性：

有窮性
確定性
可行性
輸入零個或多個
輸出一個或多個

☆ 算法的復雜度

時間復雜度：是指算法中基本運算的執行次數的數量級。
- 不僅取決于問題的規模 $n$ ；
- 還取決于待處理數據的初始狀態，比如：查找 $1$ 次就找到了和查找 $n$ 次都沒找到。
- 量級排序： $O(log^n)<O(n)<O(nlog^n)<O(n^2)<O(2^n)<O(n!)$
空間復雜度：是指算法所需的存儲空間的大小。

CH2?線性表

☆ 單鏈表

定義：單鏈表本質上是線性表的鏈式存儲，它是指通過一組任意的存儲單元來存儲線性表中的數據元素。
組成：一個單鏈表的結點包括數據域和指針域，指針域用于建立數據元素之間的關系。
鏈表增加頭結點的作用：
- 頭結點的指針域中存儲了第一個結點的位置，便于對第一個結點的處理；
- 無論鏈表是否為空，它的頭指針都是指向頭結點的非空指針，便于對空表和非空表的統一處理。

CH3?棧、隊列和數組

☆ 棧和堆是什么？

棧：是一個只允許在一端進行插入或刪除操作的線性表。

我只能想到大根堆和小根堆 😇

☆ 棧在括號匹配中的應用

如果出現的是左括號，則壓棧；
如果出現的是右括號，則檢查棧是否為空：
- 若為空則表示右括號多余，表明不匹配，結束。
- 若不為空，則彈出棧頂元素，繼續。

表達式檢驗結束時，若棧為空，匹配正確，否則表明左括號有余。

原博客說在出現右括號且棧不為空時，需要先檢查棧頂元素是否為左括號，然后再進行彈出操作。個人認為沒有檢查的必要，因為我們只會讓左括號入棧，所以棧頂元素必為左括號。

☆ 棧在表達式求值中的應用

中綴表達式

A+B*(C-D)-E/F

后綴表達式

ABCD-*+EF/-

中綴表達式轉后綴表達式：

遇到操作數，直接加入后綴表達式。
遇到左括號，直接入棧；遇到右括號，依次彈出棧中的運算符，并加入后綴表達式，直到彈出左括號為止。注意：左、右括號都是不加入后綴表達式的。
遇到運算符，如果它的優先級高于除左括號外的棧頂運算符，那么直接加入后綴表達式；否則，從棧頂開始，依次彈出棧中優先級高于或等于當前運算符的所有運算符，直到遇到優先級低于它的運算符或者左括號，之后將當前運算符加入后綴表達式。

后綴表達式求值

從左往右依次掃描后綴表達式的每一項，如果是操作數則入棧，如果是操作符則連續彈出兩個操作數，并進行運算，然后將運算結果入棧。當表達式的所有操作數都被處理完后，棧頂存放的就是表達式的計算結果。

注意：中綴表達式和后綴表達式都是字符串。

☆ 為什么循環隊列要犧牲一個空間？

答：犧牲一個空間是為了區分隊空還是隊滿。

在這里插入圖片描述
詳細的原因：

在循環隊列中通常有隊頭和隊尾兩個指針。其中，隊頭指針指向隊列的第一個元素，隊尾指針指向隊列的最后一個元素的下一個位置。
假設沒有犧牲這個空間，那么不管隊列是在執行判空還是判滿操作，判定條件都是隊頭指針等于隊尾指針，容易造成混淆。
而通過犧牲一個空間，就可以把這兩種操作分開。分開后，判空的條件是 “隊頭指針等于隊尾指針”，判滿的條件是 “隊尾指針的下一個位置是隊頭指針”。

數學表達式：

判空的條件是： $Q . re a r == Q . f o n t$
判滿的條件是： $\% MaxSize == Q.font$

☆ 循環隊列的長度？

問：有一個循環隊列 $Q$ ，編號為 $0$ 到 $n ? 1$ ，頭尾指針分別為 $f$ 和 $r$ ，求該隊列的元素個數？
答： $\% n$

☆ 順序表和鏈表的比較

存取方式：順序表可以隨機存取，而鏈表只能從表頭開始依次順序存取。
邏輯結構和物理結構：采用順序存儲時，邏輯上相鄰的元素，對應的物理存儲位置也相鄰。而采用鏈式存儲時，邏輯上相鄰的元素，物理存儲位置不一定相鄰，對應的邏輯關系是通過指針鏈接來表示的。
查找、插入和刪除操作
- 對于順序表，如果是按值查找，那么當順序表無序時，時間復雜度為 $O (n)$ ；當順序表有序時，可采用折半查找，時間復雜度為 $O(log_2^n)$ ；對于按序號查找，由于順序表支持隨機訪問，因此時間復雜度為 $O (1)$ 。而鏈表的平均復雜度始終為 $O (n)$ 。
- 順序表的插入和刪除操作，平均需要移動半個表長的元素，而鏈表的插入和刪除操作，只需要修改相關結點的指針域即可。
空間分配：順序存儲在靜態存儲分配的情況下，需要預先分配足夠大的存儲空間。否則在加入新元素時，可能出現內存溢出的情況。動態存儲分配雖然可以擴充存儲空間，但是需要移動大量得元素，導致操作效率降低。而鏈式存儲只在需要時申請分配存儲空間，只要內存有空間就可以分配。但由于鏈表的每個結點都帶有指針域，因此存儲的密度不夠大。

☆ 遞歸

遞歸：是指在一個函數的定義中又應用了它自身。
遞歸的條件：遞歸表達式（遞歸體）和邊界條件（遞歸出口）

CH4?串

☆ 字符串的定義

定義：字符串是由零個或多個字符組成的有限序列。
字符串的數據元素是單個字符。

☆ KMP 算法

在這里插入圖片描述

什么是 KMP 算法？
- KMP 算法是一種字符串匹配算法，通常用于查找主串中模式串出現的位置。對于樸素的字符串匹配算法，匹配失敗時需要主串和模式串同時回溯，而 KMP 算法只需要模式串回溯而不需要主串回溯，從而提高了查找的效率。
如何實現 KMP 算法？
- KMP 算法的實現需要借助于 next 數組，該數組記錄了匹配失敗時，模式串需要回溯到什么位置以開始重新匹配。next 數組的本質是模式串子串的最長相同前后綴。
如何計算 next 數組？
- 初始化 next 數組為模式串的大小，令 i 和 j 指針分別為 -1 和 0。當 i 等于 -1 或者 $p [i]$ 等于 $p [j]$ 時，i 和 j 同時加 1，否則 i 回溯到 next[i] 指向的位置。重復上述操作，直到 next 數組被填充完畢。
如何進行字符串匹配？
- 初始化 i 和 j 指針為 0，i 指向主串，j 指向模式串。當匹配失敗時，i 不需要回溯，只需要將 j 回溯到 next[j] 指向的位置便可繼續進行匹配。如果最后 j 指向模式串的最后一個字符之后，則代表匹配成功，否則代表匹配失敗。

回溯的本質：既然這個前后綴的長度滿足不了，那么我們就考慮較短的前后綴。

CH5?樹與二叉樹

☆ 二叉樹的性質

回顧等比數列的求和：
$=\frac{a_1(1-q^n)}{1-q}=1\times(2^n-1)=2^n-1$
假設二叉樹的高度為 $n$ ，那么共有 $2^n-1$ 個結點。

高度為 $h$ 的二叉樹至多有 $2^h-1$ 個結點，第 $i$ 層上至多有 $2^{i-1}$ 個結點。
非空二叉樹上的葉結點數等于度為 $2$ 的結點數加 $1$ ，即 $n_0=n_2+1$ （度是指一個結點的子結點的個數）
具有 $n$ 個結點的完全二叉樹的高度為 $log_2^{n}$ 向下取整再加 $1$ 。

對完全二叉樹按從上到下、從左到右的順序依次編號 $1, 2, ..., n$ ，則有以下關系：

若 $i = 1$ ，則結點 $i$ 為根，沒有父結點；若 $i > 1$ ，則結點 $i$ 的父結點為結點 $\frac{i}{2}$ ；
若 $2\times i\le n$ ，那么結點 $i$ 的左子結點為結點 $2\times i$ ；
若 $2\times i\le n$ ，那么結點 $i$ 的右子結點為結點 $2\times i+1$ ；
若 $i$ 為奇數，且 $i\ne 1$ ，則它處于右兄弟位置，它的左兄弟為結點 $i ? 1$ ；
若 $i$ 為偶數，且 $i\ne 1$ ，則它處于左兄弟位置，它的右兄弟為結點 $i + 1$ ；
結點 $i$ 所處在的層數為 $\left \lfloor log_2^i \right \rfloor + 1$

注意：上述坐標關系僅適用于二叉樹的順序存儲，即采用數組存儲二叉樹時。

☆ 滿二叉樹和完全二叉樹的區別

在這里插入圖片描述

滿二叉樹

假設一個二叉樹的高度為 $h$ ，如果它的結點數是 $2^h-1$ ，那么這個二叉樹就是一個滿二叉樹。它表現為，除了最后一層的葉結點以外，其他結點都有兩個子結點，即每一層都是滿的。

完全二叉樹

完全二叉樹是在滿二叉樹的基礎上，在最后一層從右向左依次刪除了一定數量葉結點所形成的二叉樹。它表現為，葉結點只出現在倒數第一層和倒數第二層。并且，如果一個分支結點只有一個子結點，那么這個子結點只能是左子結點。

☆ 二叉排序樹和平衡二叉樹的區別？

在這里插入圖片描述
二叉排序樹

二叉排序樹是具有以下特征的二叉樹

左子樹上所有結點的值均小于根結點的值；
右子樹上所有結點的值均大于根結點的值；
左、右子樹也分別是一棵二叉排序樹。

平衡二叉樹

平衡二叉樹是一種特殊的二叉排序樹，其中任意結點的左、右子樹高度差的絕對值不超過 $1$ 。平衡因子是指左、右子樹的高度差。在平衡二叉樹中，每個結點的平衡因子只能是 $? 1$ 、 $0$ 或 $1$ 。

見參考圖，二叉排序樹中的 $4$ 結點是一個最小不平衡點，以其為支點進行旋轉后才能得到平衡二叉樹。

☆ 二叉排序樹的查找、插入與刪除過程？

查找過程

如果二叉排序樹非空，那么先將給定值和根結點的關鍵字比較。如果相等，那么查找成功。如果不相等且小于根結點的關鍵字，那么在根結點的左子樹上查找；否則，在根結點的右子樹上查找。重復上述操作，直到查找成功。

插入和刪除過程都會使用到查找過程。

插入過程

先按查找的步驟進行查找，直至找到葉結點這一層。如果待插入的關鍵字大于該葉結點的關鍵字，那么就插入為該葉結點的右子結點；否則，插入為該葉結點的左子結點。特別地，如果二叉排序樹為空，那么直接插入為根結點。如果待插入的關鍵字已經存在，那么就插入失敗。

在這里插入圖片描述

刪除過程

先按查找的步驟進行查找，直至找到待刪除的結點。如果待刪除的結點是葉結點，那么可以直接刪去；如果待刪除的結點只有左子結點或者右子結點，那么用它的子結點代替它；如果待刪除的結點既有左子結點又有右子結點，那么首先查找該結點在中序遍歷結果中的直接前驅或者直接后繼，然后用它的直接前驅或者直接后繼代替它，并刪除這個直接前驅或者直接后繼。

在這里插入圖片描述

什么是該結點的直接前驅和直接后繼？

直接前驅：是待刪除結點的左子樹的最右的那個葉結點，即參考圖中的 $3$ 結點。
直接后繼：是待刪除結點的右子樹的最左的那個葉結點，即參考圖中的 $5$ 結點。

☆ 平衡二叉樹的插入與刪除過程？

平衡二叉樹的插入與刪除操作與二叉排序樹相同，但如果出現不平衡的現象，我們需要進行調整。我們需要尋找最小的不平衡點，也就是距離插入結點最近的、平衡因子大于 $1$ 或者小于 $? 1$ 的結點，然后對其進行調整。

🪐 四種調整思路

① LL 型：插入結點位于最小不平衡點的左子結點的左子樹中。

a. 最小不平衡點的左指針指向其左子結點的右子結點；
b. 其左子結點的右指針指向最小不平衡點；
c. 再將其左子結點的父結點更換為最小不平衡點的父結點；

② RR 型：插入結點位于最小不平衡點的右孩子的右子樹中，與 LL 型類似。

在這里插入圖片描述

旋轉的本質：最小不平衡點和自己的某個子結點交換父結點和子樹（倒轉天罡），即最小不平衡點接管子結點的娃，并成為子結點的娃，子結點接管最小不平衡點的父結點。

③ LR 型：插入結點位于最小不平衡點的左孩子的右子樹中。

a. 按照 RR 型的調整方式對最小不平衡點的左子結點進行調整使其變成 LL 型；
b. 再按照 LL 型的調整方式對最小不平衡點進行調整。

④ RL 型：插入結點位于最小不平衡點的右孩子的左子樹中，與 LR 型類似。

在這里插入圖片描述

見參考圖，插入 $6$ 結點后形成 LR 型。雖然 $5$ 結點不是最小不平衡點，但仍然需要以其為支點進行 RR 型旋轉，使整個二叉樹變為 LL 型，然后再對最小不平衡點 $8$ 結點進行 LL 型旋轉。

☆ B 樹和 B+ 樹的區別

在這里插入圖片描述

B 樹是所有結點的平衡因子都等于 $0$ 的多路平衡查找樹。

多路是指對于一棵 $m$ 階的 B 樹，每個結點最多有 $m$ 棵子樹，即結點最多有 $m ? 1$ 個關鍵字。
在一棵子樹中，根結點的左子樹中的所有結點的關鍵字都小于根結點的關鍵字，根結點的右子樹中的所有結點的關鍵字都大于根結點的關鍵字。
B 樹中的大部分操作所需的磁盤存取次數與 B 樹的高度成正比。由于每個結點中的關鍵字個數越多，容納同樣多關鍵字的 B 樹的高度越小，因此 B 樹要求所有結點的關鍵碼個數不能少于 $\left \lceil m/2 \right \rceil - 1$ 個。

在這里插入圖片描述

$m$ 階 B+ 樹與 $m$ 階 B 樹的主要差異：

在 B+ 樹中，具有 $n$ 個關鍵字的結點只含有 $n$ 棵子樹；而在 B 樹中，具有 $n$ 個關鍵字的結點含有 $n + 1$ 棵子樹。
在 B+ 樹中，每個結點的關鍵字個數 $n$ 的范圍是 $\left \lceil m/2 \right \rceil \le n \le m$ ；而在 B 樹中，每個結點的關鍵字個數 $n$ 的范圍是 $\left \lceil m/2 \right \rceil-1 \le n \le m-1$ 。
在 B+ 樹中，葉結點包含了全部關鍵字，非葉結點中出現的關鍵字也會出現在葉結點中；而在 B 樹中，最外層的終端結點包含的關鍵字和其他結點包含的關鍵字是不重復的。
在 B+ 樹中，葉結點包含信息，所有非葉結點僅起索引作用，非葉結點的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針，不含有對應記錄的存儲地址。這樣能使一個磁盤塊存儲更多的關鍵字，使得磁盤讀/寫次數更少，查找速度更快。
在 B+ 樹中，用一個指針指向關鍵字最小的葉結點，將所有葉結點串成一個線性鏈表。

☆ B 樹和 B+ 樹在數據庫中的應用

在數據庫系統中，通常以樹形結構存儲數據，其中 B 樹和 B+ 樹是最常見的索引結構。在這些樹結構中，每個結點包含的關鍵字對應著一個磁盤塊。查詢過程從根結點開始，系統將根結點的磁盤塊加載到內存中，并根據內存中的信息逐級向下訪問，直到找到對應的關鍵字所指向的磁盤塊。由于每訪問一次都要從磁盤中讀取一個結點到內存中，因此樹的高度直接影響著所需的 I/O 操作次數；樹的高度越低，表示需要進行的磁盤訪問次數越少，從而提高了查詢效率。

如果使用平衡二叉樹來存儲數據，那么當數據量較大時，平衡二叉樹的高度也會較大。而 B 樹和 B+ 樹在一個結點中存儲多個值，并且每次是將整個結點讀取到內存中再進行處理的，因此減少了磁盤 I/O 操作的次數，提高了查詢效率。B 樹不擅長范圍查找，因為數據記錄分散在各個結點中，而 B+ 樹由于有索引結點和葉結點鏈表結構的存在，因此可以通過鏈表的遍歷來實現范圍查找。

☆ 能不能簡單聊聊紅黑樹？

為了保持平衡二叉樹的平衡性，在插入和刪除操作后，會非常頻繁地調整全樹整體的拓撲結構，代價較大。為此在平衡二叉樹的平衡標準上進一步放寬條件，引入了紅黑樹的結構。

紅黑樹的介紹

在這里插入圖片描述

一棵紅黑樹是滿足如下性質的二叉排序樹：

① 每個結點或是黑色，或是紅色。
② 根節點是黑色。
③ 葉結點都是黑色（即虛擬的外部結點、NULL 結點）
④ 不存在兩個相鄰的紅結點（即紅結點的父結點和子結點均是黑色）
⑤ 對于每個結點，從該結點到任意一個葉結點的簡單路徑上，所含黑結點的數量相同。

結論：⑤ 確保了從根到葉結點的最長路徑不大于最短路徑的兩倍，即紅黑樹是適度平衡的二叉樹。

紅黑樹的應用

紅黑樹在數據結構中應用廣泛，尤其在需要保持數據有序性的場景，其平均時間復雜度為 $O(\mathrm{log} n)$ 。

Java 中的 TreeSet 和 TreeMap 是用紅黑樹來實現的；
C++ 中的 set 和 map 容器也是用紅黑樹來實現的；
在 Linux 虛擬內存管理中，紅黑樹被用來管理頁表，從而優化內存訪問效率和系統性能。

自平衡的策略

自平衡的策略可以簡單概括為三種：左旋、右旋、變色。

紅黑樹和平衡二叉樹的區別？

紅黑樹不像平衡二叉樹那樣要求任意一個結點左右子樹的高度差不超過 $1$ ，紅黑樹只要求任意一個結點左右子樹的高度差不超過 $2$ 倍，因此紅黑樹只是追求樹的大致平衡。
因為對樹的平衡程度的要求不同，平衡二叉樹在插入和刪除的過程中會花費較大的代價來維護樹的平衡，所以平衡二叉樹不適合插入、刪除太多的場景。而紅黑樹只要求適度平衡，它做到了在插入和刪除時，最多只需旋轉 $3$ 次就能實現一定程度的平衡，所以能將插入和刪除的時間復雜度維持在對數級別。

☆ 哈夫曼樹

定義

哈夫曼樹是指，在含有 $n$ 個帶權葉結點的二叉樹中，其中帶權路徑長度之和最小的二叉樹。

帶權路徑長度之和是指，所有葉結點的帶權路徑長度之和；
帶權路徑長度是指，從根結點到葉結點的路徑長度與該結點的權值的乘積。

注意：在哈夫曼樹中只有葉結點具有權值！

構造

假設這 $n$ 個葉結點分別作為 $n$ 棵僅含一個結點的二叉樹，構成一個集合；
先創建一個新結點，再從集合中選取并刪除兩棵根結點權值最小的樹，作為新結點的左、右子樹，從而得到一棵新的樹；
然后將新結點的權值置為左、右子樹的根節點的權值之和，并將新得到的樹加入到集合當中；
重復上述兩個步驟，直到集合中只剩下一棵樹為止。

特點

假設有 $n$ 個葉結點，那么哈夫曼樹中的雙分支結點有 $n ? 1$ 個，共有 $2 n ? 1$ 個結點。

應用：設計二進制前綴編碼 → 數據壓縮編碼

可變長度編碼方式，即允許不同的字符使用不同長度的二進制位進行表示。對頻率高的字符賦以短編碼，對頻率低的字符賦以長編碼，從而使字符的平均編碼長度變短，從而起到壓縮數據的作用。
我們把字符視作葉結點，將它們的使用頻率視作葉結點的權值。我們令左分支為 $0$ ，右分支為 $1$ ，然后構建哈夫曼樹，從根到葉結點的路徑上的分支標記的字符串作為該字符的編碼。

在《2025 年王道》中，分支是指兩個相鄰結點之間的路徑。

☆ 樹的存儲結構

在這里插入圖片描述
對于普通的樹來說，存儲結構通常分順序存儲與鏈式存儲，并且再細分為以下三種存儲結構：

雙親表示法（本結點 + 父結點）
- 采用的是順序存儲結構；
- 每個結點有數據域和指針域，指針域存儲的是該結點的父結點的下標；
- 特點：可以很快地找到每個結點的父結點，但是找子結點的時候需要遍歷整個數據結構。
孩子表示法（本結點 + 子結點）
- 采用的是順序存儲結構與鏈式存儲結構的結合體；
- 每個結點有數據域和指針域，指針域存儲的是第一個子結點的下標；
- 以鏈表的形式存儲該結點所有子結點的下標；
- 特點：可以很快地找到每個結點的所有子結點，但是找父結點的時候需要遍歷整個數據結構。
孩子兄弟表示法
- 采用的是鏈式存儲結構；
- 每個結點有數據域和兩個指針域，一個是指向第一個子結點的指針，另一個是指向第一個右兄弟的指針；
- 特點：便于實現樹轉二叉樹的操作；易于查找子結點，不易查找父結點。

樹轉換為二叉樹的規則：每個結點的左指針指向它的第一個孩子，右指針指向它在樹中的相鄰右兄弟。由于根結點沒有兄弟，因此樹轉換得到的二叉樹沒有右子樹。

☆ 二叉樹的存儲結構

對于二叉樹來說，存儲結構可以分為順序存儲與鏈式存儲：

順序存儲結構
- 按照二叉樹層序遍歷的順序將結點存儲于順序表中，其中空結點也需要占有位置。在這種存儲結構中，結點的序號可以反映結點之間的邏輯關系。比如，如果某個結點的下標為 $i$ ，那么它的左子結點的下標為 $2 i$ ，右子結點的下標為 $2 i + 1$ ，父結點的下標為 $i /2$ 并向下取整。
- 特點：該存儲結構適合于存儲滿二叉樹和完全二叉樹。
鏈式存儲結構
- 每個結點通常有一個數據域和兩個指針域，指針域分別指向該結點的左子結點和右子結點。
- 升級：為了充分利用左右子結點，可以讓左子結點指向自己的先序、中序或者后序遍歷的直接前序，右子結點指向自己的直接后繼，從而形成二叉排序樹以方便查找。

CH6?圖

☆ 圖的定義及其類型

定義

圖是由頂點集和邊集組成的，頂點集是指圖中頂點的有限非空集合，邊集是指圖中頂點之間的關系集合。

類型

無向圖：圖中的邊都是無向邊。
有向圖：圖中的邊都是有向邊。
完全圖：具有 $n (n ? 1) /2$ 條邊的無向圖，或者具有 $n (n ? 1)$ 條邊的有向圖。
連通圖：無向圖中任意兩個頂點之間都有路徑存在，否則就是非連通圖。
強連通圖：有向圖中任意兩個頂點之間都有路徑存在，頂點 A 到頂點 B 有路徑，頂點 B 到頂點 A 也有路徑。

☆ 遍歷算法

二叉樹的遍歷算法分為：

先序遍歷 —— 深度遍歷
中序遍歷
后序遍歷
層序遍歷 —— 廣度遍歷

圖遍歷算法分為：

深度優先搜索遍歷
廣度優先搜索遍歷

圖的深度遍歷等價于二叉樹的先序遍歷，圖的廣度遍歷等價于二叉樹的層序遍歷。

☆ 最小生成樹

生成樹是指包含圖中所有頂點的一個極小連通子圖。一個圖可以有多個生成樹，而其中權值之和最小的那棵生成樹就是該圖的最小生成樹。最小生成樹的算法有普里姆算法和克魯斯卡爾算法。

每棵樹的權是指樹中所有邊上的權值之和。

普里姆算法（加點法）
- ① 初始時從圖中任取一個頂點加入到樹中，此時樹中只有一個頂點；
- ② 每次選擇一個與當前樹中頂點集合距離最近的頂點，將該頂點和相應的邊加入樹中；
- ③ 重復上述步驟直到圖中的所有結點都已加入樹中，從而完成了最小生成樹的構建。
- 特點：歸并點，時間復雜度為 $O(|V|^2)$ ，適用于稠密網。
克魯斯卡爾算法（加邊法）
- ① 初始時是一個擁有 $n$ 個頂點但是沒有邊的非連通圖；
- ② 每次選取之前沒有被選取過的并且權值最小的邊，如果這條邊兩端的頂點落在圖中的不同連通分量上，那么將這條邊加入圖中，否則舍棄這條邊而選擇下一條權值最小的邊；
- ③ 重復上述步驟直到圖變為了連通圖，從而完成了最小生成樹的構建。
- 特點：歸并邊，時間復雜度為 $O(|E|log_2^{|E|})$ ，適用于稀疏網。

構造最小生成樹的本質：需要選擇 $n$ 個頂點和 $n ? 1$ 條最小的邊。

☆ 最短路徑

帶權路徑長度是指從一個頂點到圖中其余任意一個頂點的路徑所經過的邊的權值之和，其中帶權路徑長度最短的那條路徑被稱為最短路徑。

比如：從頂點 A 到頂點 B 有一條路徑，那么這條路徑所經過的邊的權值之和，就是帶權路徑長度。

Dijkstra 迪杰斯特拉算法
- 本質：求解從某個源點到其余各頂點的最短路徑。
- 算法：每次找出距離源點最近且未歸入集合的頂點，把它歸入集合，同時以這個頂點為基礎更新從源點到其他所有頂點的距離。重復上述步驟，直到所有頂點都被歸入集合為止。
- 特點：上述過程不需遍歷圖中的所有頂點；迪杰斯特拉算法不適用于帶有負權值的邊。
Floyd 弗洛伊德算法
- 本質：求解每一對頂點之間的最短路徑。
- 算法：初始時，對于任意兩個頂點，如果它們之間存在邊，則這條邊的權值作為它們之間的最短路徑長度；如果它們之間不存在邊，則設置它們之間的最短路徑長度為無窮。之后，逐步嘗試在原路徑中加入其他頂點作為中間頂點。如果加入中間頂點后，得到的路徑比原來的路徑長度短，則用這個新路徑代替原路徑。迭代 $n$ 次后，得到每一對頂點之間的最短路徑。

回想一下計網里面是怎么教的就行了 😇

☆ 最小生成樹算法和最短路徑算法的優化

最小生成樹中的普里姆算法與克魯斯卡爾算法都需要排序。前者需要對點到集合的路徑進行排序，后者需要對邊的權值進行排序。因此二者都可以利用堆來進行優化，通過訪問堆頂元素以及調整堆來實現對最短邊的快速訪問。與此類似，最短路徑中的迪杰斯特拉算法也可以利用堆進行優化。

☆ AOV 網和拓撲排序

定義：拓撲排序是對有向無環圖的頂點的一種排序，它使得若存在一條從頂點 A 到頂點 B 的路徑，那么在排序中 B 一定出現在 A 的后面。每個 AOV 網都有一個或多個拓撲排序序列。

應用：① 獲得拓撲排序序列；② 檢查圖中是否有環。

AOV 網是一個有向無環圖，其中的頂點表示一個活動，有向邊表示兩個活動之間的先后關系。

拓撲排序的具體步驟是：利用棧或者隊列，

① 將圖中入度為 0 的結點入棧，同時在圖中將該結點進行刪除；
② 再將刪除該結點之后入度變為 0 的結點入棧；
③ 重復上述步驟即可獲得拓撲序列序列。

如果算法結束時，序列的長度不等于圖中結點的個數，那么說明圖中存在環。

☆ 介紹一下 AOE 網？

定義：AOE 網是一個帶權有向圖，其中的頂點表示事件，有向邊表示活動，邊的權值表示完成該活動的開銷。
區別：AOE 網中的邊有權值，而 AOV 網中的邊沒有權值，僅表示頂點之間的先后關系。

☆ 什么是關鍵路徑？

關鍵路徑和關鍵活動：在 AOE 網中，從源點到匯點的有向路徑可能有多條。但是只有路徑上的所有活動都已完成，整個工程才算結束。因此，從源點到匯點的所有路徑中，具有最大路徑長度的路徑被稱為關鍵路徑，關鍵路徑上的活動被稱為關鍵活動。
最短完成時間：完成整個工程的最短時間就是關鍵路徑的長度，也就是關鍵路徑上各活動花費開銷的總和。如果關鍵活動不能按時完成，那么整個工程的完成時間就會延長。

源點是指 AOE 網中唯一的入度為 $0$ 的頂點，匯點是指 AOE 網中唯一的出度為 $0$ 的頂點。

☆ 如何求解關鍵路徑？

① 從源點出發，令源點的最早發生時間為 $0$ ，按拓撲排序的順序求解其余頂點的最早發生時間；
② 從匯點出發，令匯點的最遲發生時間等于它的最早發生時間，按逆拓撲排序的順序求解其余頂點的最遲發生時間；
③ 根據各頂點的最早發生時間求解所有弧的最早開始時間；
④ 根據各頂點的最遲發生時間求解所有弧的最遲開始時間；
⑤ 求解 AOE 網中所有活動的差額，找出所有差額為 $0$ 的活動構成關鍵路徑。

CH7?查找

☆ 哈希表？構造方法？

定義

散列表：哈希表又稱散列表，是能夠根據關鍵字直接進行訪問的數據結構。也就是說，哈希表建立了關鍵字和存儲地址之間的一種直接映射關系。
散列函數：哈希函數又稱散列函數，它是一個把關鍵字映射成該關鍵字對應的地址的函數。

構造方法

直接定址法：直接取關鍵字的某個線性函數值作為散列地址，散列函數為 $a\times key+b$ 。
除留余數法：假設散列表的表長為 $m$ ，取一個不大于 $m$ 但最接近或等于 $m$ 的質數 $p$ ，散列函數為 $key\%p$ 。
數字分析法：假設關鍵字是 $r$ 進制數，而 $r$ 個數碼在各位上出現的頻率不一定相同，可能在某些位上分布均勻一些，每種數碼出現的機會均等，我們選取數碼分布均勻的若干位作為散列地址。
平方取中法：取關鍵字的平方值的中間幾位作為散列地址。

解決沖突

① 開放定址法：核心思想為 $H_i=(H(key)+d_i)\%m$ ，其中 $m$ 為散列表表長。

線性探測法：增量 $d_i=1,2,..,m-1$ 。當沖突發生時，順序查看表中下一個單元，直到找出一個空閑單元或查遍全表。但是容易造成大量元素在相鄰的散列地址上堆積，導致查找效率下降。
平方探測法：在線性探測法的基礎上，增量變為 $d_i=1^2,-1^2,2^2,-2^2,,..,k^2,-k^2$ 。可以避免出現堆積問題，但是不能探測到散列表上的所有單元。
雙散列法：使用兩個散列函數，當通過第一個散列函數得到的地址發生沖突時，利用第二個散列函數計算該關鍵字的地址增量，即 $H_i=(H_1(key)+i\times H_2(key))\%m$ ，其中 $i$ 是沖突次數。
偽隨機序列法：增量 $d_i$ 是為偽隨機數列。

上述四個方法的核心思想都是：如果當前位置發生沖突，那么就后移幾個位置進行存放。至于往后偏移幾個位置，不同的方法有不同的策略。

② 拉鏈法：將所有的同義詞存儲在同一線性鏈表中，這個線性鏈表由其散列地址唯一標識。

裝填因子

等于哈希表中記錄的長度除以哈希表的長度。裝填因子越大，表示裝填的記錄越滿，發生沖突的可能性越大；反之發生沖突的可能性越小。

CH8?排序

☆ 十種排序算法

插入排序：直接插入排序、折半插入排序、希爾排序

直接插入排序：每次將一個待排序的記錄按其關鍵字的大小插入到前面已經排好序的子序列中，直到全部記錄插入完成。特點：令第 $0$ 個元素作為哨兵，暫存待插入的元素；邊比較邊移動元素。
折半插入排序：在直接插入排序的基礎上，將比較和移動操作分離。先折半查找出元素的待插入位置，然后統一地移動待插入位置之后的所有元素。
希爾排序：首先，取一個小于 $m$ 的增量 $d_1$ ，把表中的全部記錄分成 $d_1$ 組，也就是說，將所有距離為 $d_1$ 的倍數的記錄放在同一組，再在各組內進行直接插入排序；然后，取一個小于 $d_1$ 的增量 $d_2$ ，重復上述過程。直到取到 $d_t$ 等于 $1$ 時，即所有記錄已放在同一組中，再進行直接插入排序。

交換排序：冒泡排序、快速排序

冒泡排序：從前往后兩兩比較相鄰元素的值，如果是逆序，那么就交換它們，直到序列比較完。第一趟冒泡，結果是將最小的元素交換到待排序序列的第一個位置。下一趟冒泡時，前一趟確定的最小元素不再參與比較。特點：設置一個是否發生交換的標志，如果一趟結束后沒有發生交換，那么說明排序結束。
快速排序：在待排序表中任取一個元素作為樞軸，通過一趟排序將待排序表劃分為兩個部分，使得樞軸之前的部分的所有元素小于樞軸的值，樞軸之后的部分的所有元素大于等于樞軸的值。然后分別對樞軸左、右兩側的子表重復上述操作，直到每個部分中只有一個元素或者為空為止。

int partition(int A[], int left, int right) {int temp = A[left];  // 暫存樞軸的值while (left < right) {while (left < right && A[right] > temp) --right;A[left] = A[right];while (left < right && A[left] <= temp) ++left;A[right] = A[left];}A[left] = temp;return left;
}void quickSort(int A[], int left, int right) {if (left < right) {// 確定樞軸的位置int pos = partition(A, left, right);// 遞歸對左右側子表進行排序quickSort(A, left, pos - 1);quickSort(A, pos + 1, right);}
}

由于本人對快排不太熟悉，因此給出了算法結構 😇

選擇排序：簡單選擇排序、堆排序

簡單選擇排序：第 $i$ 趟從后面 $n ? i + 1$ 個待排序元素中選取關鍵字最小的元素，作為有序子序列的第 $i$ 個元素，直到做完 $n ? 1$ 趟，算法結束。
堆排序：首先將 $n$ 個元素建成初始堆，因為大頂堆的堆頂元素是最大值，所以我們每次直接輸出堆頂元素。輸出堆頂元素后，通常將堆底元素送入堆頂，然后將堆頂元素向下調整以繼續保持大頂堆的性質。

二路歸并排序

歸并的含義是將兩個或兩個以上的有序表合并成一個新的有序表。假定待排序表含有 $n$ 個記錄，那么可以將其視為 $n$ 個有序的子表，每個子表的長度為 $1$ ，然后兩兩合并。重復上述操作，直到合并成一個長度為 $n$ 的有序表為止。

const int  maxn = 100;
void merge(int A[], int L1, int R1, int L2, int R2) {int i = L1, j = L2;int temp[maxn], index = 0;while (i <= R1 && j <= R2) {if (A[i] <= A[j]) {temp[index++] = A[i++];} else {temp[index++] = A[j++];}}while (i <= R1) temp[index++] = A[i++];while (j <= R2) temp[index++] = A[j++];for (i = 0; i < index; ++i) {A[L1 + i] = temp[i];}
}void mergeSort(int A[], int left, int right) {if (left < right) {int mid = (left + right) + 2;mergeSort(A, left, mid);mergeSort(A, mid + 1, right);merge(A, left, mid, mid + 1, right);}
}

遞歸的思想：將待排序表平分為兩部分，分別完成排序后再進行合并。

基數排序

基數排序的排序過程分為分配和收集兩個操作。假設關鍵字的基數是 $r$ ，分配是指，設置 $r$ 個空隊列，然后依次考察線性表中的每個結點，如果結點的關鍵字和某個隊列相匹配，那么將結點放入該隊列中。處理完畢后，將各個隊列中的結點依次首尾相接，得到新的結點序列，從而組成新的線性表。

外部排序

外部排序是指，將待排序的記錄存儲在外存上，排序時再把數據一部分一部分地調入內存進行排序，在排序過程中需要多次進行內存和外存之間的交換。

不太懂最后三種排序 😇

☆ 快速排序的復雜度分析？

快速排序中的遞歸樹是一棵二叉樹。這棵二叉樹的最大高度為 $n$ ，最低高度為 $log_2^n$ 向下取整再加 $1$ 。因此快速排序的最好時間復雜度為 $O(nlog_2^n)$ ，最壞時間復雜度為 $O(n^2)$ 。

☆ 構建堆的過程？堆排序的過程？

堆的存儲結構：

使用數組來存儲堆的元素。由于堆是一棵完全二叉樹，因此對于下標為 $i$ 的結點，它的左子結點的下標為 $2 i + 1$ ，右子結點的下標為 $2 i + 2$ 。

構建堆的過程：

① 首先將待排序的序列按照先后順序存儲在數組中；
② 從最后一個分支結點開始調整。如果該結點的值小于其左子結點和右子結點中較大的一個，那么就讓它和這個較大的子結點進行交換；然后再對其余分支結點進行相同的調整，由于結點的交換可能會破壞下一級的堆，因此需要重新對下一級的堆進行調整。
③ 重復上述操作，直到完成對根結點的調整，算法結束。

這里以大根堆為例，小根堆請自行腦補。

堆排序的過程：

每次輸出堆頂元素，然后將堆的最后一個元素與堆頂元素進行交換。此時堆的性質被破壞，需要向下進行調整；
重復上述操作，直到所有的結點都被輸出，即可得到已排序的序列。

☆ 歸并排序和快排的比較

由于歸并排序分割子序列的過程與初始序列的排序無關，因此它的最好、最壞和平均時間復雜度均為 $O(nlog_2^n)$ 。快速排序雖然最壞情況下的時間復雜度會達到 $O(n^2)$ ，但是它的平均性能可以達到 $O(nlog_2^n)$ 。此外，由于歸并排序在合并操作中需要借助較多的輔助空間用于元素賦值，因此它的空間復雜度為 $O (n)$ 。而快速排序的平均空間復雜度只有 $O(log_2^n)$ 。