第一章 緒論

1. 數(shù)據(jù)結構包含三個方面的內(nèi)容：
   • 數(shù)據(jù)的邏輯結構：描述數(shù)據(jù)之間邏輯關系的、與數(shù)據(jù)的存儲無關的數(shù)學模型。相同的邏輯結構可使用不同的存儲結構存儲，如線性表既可順序存儲，也可鏈式存儲
     • 線性結構：一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列
       • 一般線性表
       • 受限線性表：棧、隊列、串
       • 線性表推廣：數(shù)組
     • 非線性結構
       • 集合
       • 樹形結構：一般樹、二叉樹
       • 圖狀結構：有向圖、無向圖
   • 數(shù)據(jù)的物理結構：指數(shù)據(jù)的邏輯結構在計算機中的存儲實現(xiàn)。如順序表、散列表、單鏈表都是既描述了邏輯結構，又描述了數(shù)據(jù)運算和物理（存儲）結構，但不歸為邏輯結構的范疇
     • 順序存儲結構：邏輯上相鄰的元素在物理上也相鄰。可隨機存取，但只能使用相鄰的一整塊存儲單元
     • 鏈式存儲結構
     • 索引存儲結構：在存儲元素信息的同時，還建立附加的索引表。優(yōu)點是檢索速度快，缺點是附加的索引表額外占用存儲空間
     • 散列存儲結構
   • 數(shù)據(jù)的運算：指對數(shù)據(jù)實施的操作。如對數(shù)據(jù)進行增刪改查、排序等
     • 例如棧和隊列的運算就不同，棧由同側進出（后進先出），隊列由異側進出（先進先出）
2. 抽象數(shù)據(jù)類型：（數(shù)據(jù)對象，數(shù)據(jù)關系，基本操作集），用于描述數(shù)據(jù)的邏輯結構和抽象運算。
3. 分析算法效率時的一些術語：
   • 問題規(guī)模：指算法的輸入量，可理解為數(shù)據(jù)量的大小。如在排序算法中，問題規(guī)模n指參與排序的數(shù)據(jù)個數(shù)；在樹相關運算中，問題規(guī)模n指樹中節(jié)點的個數(shù)。是與空間復雜度有關的
   • 基本語句：指對算法運行時間影響最大的語句
4. 算法原地工作的意思是需要常量級別的輔助空間，而不是不需要任何額外輔助空間
5. 分析時間復雜度總是考慮該算法在最壞情況下的時間復雜度
6. 同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率越低
7. 算法的健壯性是指：算法能考慮到各種邊界異常條件，并作出相應的處理判斷。即當輸入非法錯誤時，算法也能進行適當處理
8. 算法的五大特性：有窮性、確定性、可行性、輸入和輸出
9. 定義邏輯結構時可以不考慮存儲結構

第二章 線性表

第三章 棧、隊列和數(shù)組

1. 卡特蘭數(shù)$\frac{1}{n+1}{C}_{2n}^n$：可算出n個元素的輸入序列總共有可能出現(xiàn)多少種合法的出棧序列。
2. 棧和隊列的應用
   • 括號匹配問題（棧）
   • 表達式求值（棧）
     • 中綴表達式轉后綴表達式：一個棧，用于暫存還不能確定運算順序的運算符
     • 后綴表達式的計算：一個棧，用于暫存操作數(shù)
     • 中綴表達式的計算：兩個棧，操作數(shù)棧和運算符棧。若掃描到操作數(shù)則直接壓入操作數(shù)棧，若掃描到運算符或界限符，則按照“中綴轉后綴”相同的邏輯壓入運算符棧（每當彈出運算符，就需要再彈出兩個操作數(shù)棧的棧頂元素并執(zhí)行相應運算，運算結果再壓回操作數(shù)棧）
   • 遞歸（棧）
   • 樹的層次遍歷（隊列）
   • 圖的廣度優(yōu)先遍歷（隊列）
   • 操作系統(tǒng)中，F(xiàn)CFS策略的實現(xiàn)（隊列）（場景為多個進程爭搶有限的系統(tǒng)資源時，如CPU資源的分配、打印數(shù)據(jù)緩沖區(qū)）
3. 隊列的判空判滿
   • 順序隊列：
     • 隊尾指針Q.rear指向隊尾元素的下一個位置
       • 犧牲一個存儲空間作為代價（還剩一個存儲空間時，Q.rear指向空的這個存儲空間，此時判定隊滿。因為若把這個存儲空間占了，同時Q.rear后移一位，就會導致Q.rear和Q.front指向同一個位置，這就和隊空時的判定條件重復了）
         • 隊空條件：$Q.rear==Q.front$，
         • 隊滿條件：$(Q.rear+1)\%MaxSize==Q.front$
       • 使用一個變量size表示隊列中存放了幾個數(shù)據(jù)元素
         • 隊空條件：$Q.rear==Q.front,size==0$
         • 隊滿條件：$Q.rear==Q.front,size==MaxSize$
     • 隊尾指針Q.rear指向隊尾元素
       • 隊空條件：$(Q.rear+1)\%MaxSize==Q.front$（因為Q.rear指向隊尾元素時，插入節(jié)點時是先Q.rear+1，再讓Q.data[Q.rear]=x）
         
       • 隊滿條件：和“隊尾指針Q.rear指向隊尾元素的下一個位置”中的情況一樣，若不犧牲一個位置，隊空和隊滿的條件一樣。方法也同樣有兩種，要么就是犧牲一個存儲單元，要么就是增加一個輔助變量
         
   • 鏈式隊列：在上述的順序隊列中，用了很大篇幅解決如何判斷隊滿隊空；而在鏈式存儲的隊列中，可以不用關心這個問題，因為鏈式存儲一般不會隊滿，除非內(nèi)存不足。
     • 特殊情況：用非循環(huán)單鏈表存儲的隊列進行刪除操作時，頭尾指針可能都要修改（頭指針是因為要出隊；修改尾指針是因為當隊列僅有一個元素時，刪除操作后隊列為空，需要修改尾指針為rear=front，表示隊空狀態(tài)）
   • 中綴轉后綴
4. 隊列元素個數(shù)公式（rear表示隊尾節(jié)點的后一個位置；front表示隊頭節(jié)點）：$(rear+MaxSize?front)\%MaxSize$
5. 任何遞歸過程都可以通過迭代或利用棧等方式轉化為非遞歸過程，在算法中消除遞歸不一定使用棧
   在遞歸過程轉換為非遞歸過程時是否使用棧和局部變量的存在沒有必然關系。
   棧是實現(xiàn)過程和函數(shù)等子程序調(diào)用時所必需的結構

第五章 樹與二叉樹

1. 并查集：
   • 并查集的應用：
     • 可用于實現(xiàn)Kruskal算法（找邊）求最小生成樹
     • 可用于判斷無向圖的連通性
     • 可用于判斷無向圖中是否有環(huán)
     • （X）并查集不可以用于迪杰斯特拉算法求最短路徑
     • （X）并查集不可以用于Prim算法（找點）求最小生成樹
   • 并查集的存儲方式
     • 邏輯：雙親表示法的樹
     • 存儲：數(shù)組
   • 并查集的時間復雜度（m為并查集長度）
     • find：優(yōu)化前為$O(m)$；優(yōu)化后為$O(lo{g}_{2}n)$
     • union：$O(1)$
     • 總復雜度：優(yōu)化前$O(m^2)$；優(yōu)化后$O(m)$
2. 樹、森林、二叉樹遍歷序列的關系

   樹	森林	二叉樹
   先根遍歷	先序遍歷	先序遍歷
   后根遍歷	中序遍歷	中序遍歷

   關于森林的中序遍歷/后序遍歷叫法問題：二者指森林的同一種遍歷方法，都是先遍歷第一棵樹的子節(jié)點，然后是第一棵樹的根節(jié)點，然后是第二棵樹… 之所以稱為中序遍歷，是因為要先處理完一棵樹再處理另一棵樹。文章來源地址http://www.zghlxwxcb.cn/news/detail-632183.html

3. 前綴編碼：沒有任何一個編碼是其他某個編碼的前綴

第六章 圖

1. DFS與BFS算法的應用：
   • DFS：
     • 判斷圖的（強）連通性
       • 無向圖的連通性：若從任意一個節(jié)點出發(fā)，僅需一次DFS就可以訪問圖中所有節(jié)點，則該無向圖就是連通的
       • 有向圖的強連通性：從任意一個節(jié)點v出發(fā)DFS，若可以遍歷該有向圖的所有節(jié)點，則此時將該有向圖的所有邊反向，再次從節(jié)點v出發(fā)進行DFS，若能夠再次遍歷該有向圖的所有節(jié)點，則表示該有向圖是強連通圖
     • 判斷圖中是否有環(huán)（回路）
     • 歐拉回路求解：若一條路徑能不重復的包含圖中所有邊，則稱該路徑為歐拉路徑。若一條回路（從一個節(jié)點出發(fā)又能回到該節(jié)點的路徑）是歐拉路徑，則稱為歐拉回路。DFS可以判斷圖中是否存在歐拉回路
     • 迷宮
     • 判斷二分圖
   • BFS：
     • 求解單源最短路徑問題（只適用于無權圖）
     • 迷宮
     • 判斷二分圖
2. 最短路徑
   • 有無環(huán)（回路）對Dijkstra算法并無影響，但Dijkstra算法不能求解存在負權值邊的圖；Floyd算法可以求帶有負權值邊的圖，但圖中不能存在負權回路（因為帶有負權回路的圖沒有最短路徑）
   • Dijkstra算法是解決單源最短路徑類問題，floyd算法是解決多源最短路徑（指圖中任意兩個頂點之間的最短路徑）類問題
   • Dijkstra算法屬于貪心算法，floyd算法屬于動態(tài)規(guī)劃算法
3. 判斷有向圖是否有環(huán)（回路）的幾種方法：
   • 深度優(yōu)先遍歷：若在遍歷過程中遇到要訪問的節(jié)點已在棧中就是有環(huán)
   • 拓撲排序：找不到拓撲序列必定有環(huán)
4. 拓撲排序
   • 在拓撲排序算法中，為暫存入度為零的頂點可以使用棧，也可以使用隊列。（因為只要入了棧/隊列，就都是入度為零的，從哪個入度為零的先開始都無所謂）
   • 采用深度優(yōu)先遍歷也可實現(xiàn)拓撲排序
5. 圖的四種存儲數(shù)據(jù)結構
   • 存有向圖：
     • 鄰接矩陣：空間復雜度太高
     • 鄰接表：找某一個頂點的入邊很不容易，必須要遍歷整個鄰接表
     • 十字鏈表：解決了上面兩個數(shù)據(jù)結構的問題
   • 存無向圖
     • 鄰接矩陣：空間復雜度太高
     • 鄰接表：每條邊會對應兩個邊節(jié)點（因為一條邊連著兩個節(jié)點，兩個節(jié)點都會各自指向一個代表這條邊的邊節(jié)點）。這就導致若要刪除某條邊，就要對應刪除兩個節(jié)點，若要刪除某個節(jié)點，除了刪除本節(jié)點和該節(jié)點指出的若干邊外，還要到其他節(jié)點那里刪除和這些邊重復表示的那些邊節(jié)點。所以刪除一個頂點或刪除一條邊時會很不方便
     • 鄰接多重表：解決了上面兩個數(shù)據(jù)結構的問題

第七章 查找

1. 紅黑樹插入最多兩次旋轉，刪除最多三次旋轉（記憶即可）
2. 紅黑樹和AVL樹都屬于自平衡的二叉樹
3. 關于平衡二叉樹的轉化中，刪除節(jié)點再還原，無論是刪除非葉還是刪除葉節(jié)點，都有可能導致還原后的樹與原來的樹相同或不同
   對于普通二叉樹，刪除葉節(jié)點再還原，與原樹一定相同；刪除非葉節(jié)點再還原，與原樹一定不同
4. B+樹支持順序查找（因為它葉子節(jié)點存有所有數(shù)據(jù)）和隨機查找；而B樹只能支持隨機查找。B+樹的葉節(jié)點是通過指針相互鏈接的，導致B+樹不僅可以從上往下，按照樹的方式向下遍歷，也可以通過葉節(jié)點那層的指針進行順序遍歷
5. B樹和B+樹都是平衡的多叉樹，二者都可以用于文件索引結構
6. B+樹產(chǎn)生的原因就是源于操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引
7. 存儲結構與查找方法的對應關系：
   • 順序查找法：適用于符合線性且可以按順序訪問下一個節(jié)點的存儲結構。如順序存儲結構與鏈式存儲結構
   • 折半查找法：僅適合于順序存儲結構（因為折半查找需要獲取一段數(shù)據(jù)的中間元素，也就是需要隨機存取，鏈式結構的話需要從頭一個個遍歷到中間元素，不適合）
   • 樹型查找法：適用于樹型存儲結構
   • 散列查找法：適用于散列表
8. 在采用開放定址法解決沖突的散列查找中，發(fā)生聚集的原因主要是“解決沖突的方法選擇不當”。（因為這樣就會導致非同義詞與同義詞的沖突變多，正是聚集的主要原因）
9. B樹中，“終端節(jié)點”指正常節(jié)點的最下面一層節(jié)點，“葉子節(jié)點”指那些查找失敗的節(jié)點。所有的葉節(jié)點都出現(xiàn)在同一層次上，且不帶信息（實際上這些葉節(jié)點并不存在，指向這些節(jié)點的指針為空）；B+樹中，“葉子節(jié)點”是有值的最后一層節(jié)點，其指向自己對應的記錄
   
   
10. B+樹中葉子節(jié)點包含信息，所有非葉節(jié)點僅起索引作用，且非葉節(jié)點中的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針，不含有該關鍵字對應記錄的存儲地址；而B樹的節(jié)點中都包含了關鍵字對應記錄的存儲地址
11. B+樹都典型應用：關系型數(shù)據(jù)庫的“索引”（如MySQL）
    由于B+樹的非葉節(jié)點不含有該關鍵字對應記錄的存儲地址，因此可以使一個磁盤塊包含更多關鍵字，使得B+樹的階更大，樹高更矮（一塊磁盤即為一個節(jié)點），讀磁盤次數(shù)更少，查找更快
12. B樹和B+樹的對比
    
13. 折半查找的判定樹中，若$mid=?(low+high)/2?$，則對于任何一個節(jié)點，必有：右子樹節(jié)點數(shù)-左子樹節(jié)點數(shù)=0或1
14. 折半查找判定樹一定是平衡二叉樹

第七章 排序

1. 排序算法的穩(wěn)定性與優(yōu)劣無關，沒有“穩(wěn)定的排序方法優(yōu)于不穩(wěn)定的排序方法”這一說
2. 排序算法中有部分算法不能應用在鏈表上（如折半插入），這是因為沒有了隨機存取特性。但仍有部分算法是可以完美使用的，如直接插入排序
3. 對任意n個關鍵字排序的比較次數(shù)至少為$?lo{g}_2(n!)?$
4. 快排中，遞歸的次數(shù)其實就是分界的次數(shù)，根本影響因素就是基準元素的左右劃分情況。因此和初始排列次序有關。而每次劃分后，會出現(xiàn)兩個長度可能不同的分區(qū)，先處理長的還是先處理短的對整體遞歸次數(shù)都沒有影響
5. 由于鏈式存儲無隨機存取特性、只能正向訪問，因此導致對絕大部分內(nèi)部排序而言，鏈式存儲無法實現(xiàn)其功能。而內(nèi)部排序算法都可以使用順序存儲。
6. 排序方法是“穩(wěn)定的”：假設兩個元素相等，若在排序后的序列中，排序前就在前面的元素仍在前面，則稱所用的排序方法是穩(wěn)定的；反之，若排序后兩個相等元素調(diào)換相對位置，則稱所用的排序方法是不穩(wěn)定的

到了這里，關于數(shù)據(jù)結構中一些零碎且易忘的知識點的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！