一、架構梳理

• 線性（1:1)

  • 線性表

    • 順序存儲 –>?arr

    • 鏈式存儲 –> 指針 （有頭，無頭）

      有頭是指有一個不存數據的頭，始終作為這個鏈表的起點。

      會更加簡單，無頭的話，更改首部節點會麻煩。

      頭節點不僅可以作為起點，還可以作為存儲信息的倉庫，因為頭節點只有*next是必須的。

      • 單鏈表

        • 循環
        • 不循環

      • 雙向鏈表

        lib四個版本，第一個最基礎完善，第二個改成了變長結構體，第三個在第二個的基礎上封裝了函數指針，第四個在第二個的基礎上隱藏了數據結構，只暴露接口。

        學到這里可以去讀一下內核有關list的實現，主要都是宏和內聯函數。

        • 循環
        • 不循環

  • 棧

  • 隊列

    練習：

    1. 表達式計算

    2. 球鐘算法
       三個棧，1h，5min，1min。27個球，過了多久隊列里又是1到27的順序。

• 樹狀（1:N）

  遞歸。遞歸轉非遞歸。

  • 深度：層數

  • 度：子樹的個數

  • 葉子：邊緣節點

  • 孩子：與父節點對應

  • 兄弟：相同父節點

  • 堂兄弟：相同爺節點

  • 二叉樹：

    • 滿二叉樹：深度為k且節點為2^k-1的二叉樹
    • 完全二叉樹：一顆二叉樹，只有倒數兩層可以存在不滿兩個孩子的節點，且單個孩子時只能是左孩子

  • 存儲：

    • 順序：直觀，但是浪費空間
      滿二叉樹：父節點n，左孩子2n，右孩子2n+1
    • 鏈式：靈活，空間利用率高

  • 遍歷

    先加中，或者，中加后，都可以逆推出樹。先加后不行。

    • 按行
    • 先序（根，左，右）
    • 中序（左，根，右）
    • 后序（左，右，根）

  • 平衡：

    有很多種條件判定。

    這棵樹的左右子樹個數差值為1。

  • 廣義表

    ( root ( left ) ( right) )，進行嵌套。

  • 搜索樹

    空間換時間，查找是**o(1)**。

    課后作業：詞頻統計

• 圖（N:M)