????結(jié)合王道輔導(dǎo)書總結(jié)了幾點(diǎn)數(shù)據(jù)結(jié)構(gòu)里需要理解的應(yīng)用題型，算是作為最后幾天復(fù)習(xí)應(yīng)用題時(shí)的一個(gè)引導(dǎo)吧（并沒有詳細(xì)的解釋過程 只能算是一個(gè)清單略加幾點(diǎn)備注說明而已），

????如有錯(cuò)誤，歡迎指正（這是 篇總結(jié) 張草稿紙，23333，自用留檔）

1. 二叉排序樹的刪除操作

   ⑴右子樹空，用左子女填補(bǔ)

   ⑵左子樹空，用右子女填補(bǔ)

   ⑶左右均不空，用右子樹中序遍歷第一個(gè)子女結(jié)點(diǎn)填補(bǔ)
   

2. 平衡二叉樹

   各種昏天黑地的旋轉(zhuǎn)：

   LL（右單旋轉(zhuǎn)）：由結(jié)點(diǎn)A的左孩子（L）的左孩子（L）引起的不平衡

   RR（左單旋轉(zhuǎn)）：由結(jié)點(diǎn)A的右孩子（R）的右孩子（R）引起的不平衡

   LR（先左后右雙旋轉(zhuǎn)）：由結(jié)點(diǎn)A的左孩子（L）的右孩子（R）引起的不平衡

   RL（先右后左雙旋轉(zhuǎn)）：由結(jié)點(diǎn)A的右孩子（R）的左孩子（L）引起的不平衡
   

3. 平均查找長(zhǎng)度

   二叉樹 的平均查找長(zhǎng)度（ASL）應(yīng)注意的是查找失敗時(shí)候的ASL的計(jì)算易錯(cuò)的地方：

   每一層上失敗結(jié)點(diǎn)的個(gè)數(shù) * 失敗結(jié)點(diǎn)上一個(gè)結(jié)點(diǎn)（因?yàn)槭〗Y(jié)點(diǎn)實(shí)際上是不存在的）到跟結(jié)點(diǎn)的路徑長(zhǎng)度

   注：注意折半查找和分塊查找
   

4. 鄰接矩陣，鄰接表的畫法

   這個(gè)很簡(jiǎn)單了，翻下資料注意下細(xì)節(jié)就可以了。
   

5. 圖的遍歷

   圖的遍歷有兩種，一個(gè)是廣度優(yōu)先（BFS），一個(gè)是深度優(yōu)先（DFS）：

   I.廣度優(yōu)先就是先找完一個(gè)結(jié)點(diǎn)的所有相鄰結(jié)點(diǎn)（直連的，一步到位的結(jié)點(diǎn)，不用轉(zhuǎn)車）然后查找相鄰結(jié)點(diǎn)的相鄰結(jié)點(diǎn)，過程同二叉樹的層次遍歷

   II.深度優(yōu)先就是一條道走到黑，不到死胡同不回來，有回退，退回到死胡同的上一個(gè)路口換條路繼續(xù)走（并不是回退到根結(jié)點(diǎn)）
   

6. 最小生成樹

   Prim（普里姆）算法和Kruskal（克魯斯卡爾）算法：

   P：從已有點(diǎn)集（已經(jīng)選中的點(diǎn)）中找與這些點(diǎn)相連的權(quán)值最小的邊，由點(diǎn)找邊

   K：從所有邊中找權(quán)值最小的邊和兩端的結(jié)點(diǎn)（保證不會(huì)與已有的邊構(gòu)成回路），由邊找點(diǎn)
   

7. 最短路徑

   ⊙? 一個(gè)是單源最短路徑，Dijkstra算法

   每一輪中路徑最小的值對(duì)應(yīng)的結(jié)點(diǎn)作為新的中轉(zhuǎn)站，同時(shí)確定了結(jié)點(diǎn)的最短路徑

   ⊙? 一個(gè)是多源（我是這么記得，王道上好像沒這個(gè)詞）路徑最短，F(xiàn)loyd算法
   

8. 拓?fù)渑判?/span>

   AOV網(wǎng) ，V頂點(diǎn)集? 頂點(diǎn)表示活動(dòng)

   注：拓?fù)湫蛄形ㄒ?，圖不一定唯一
   

9. 關(guān)鍵路徑

   AOE網(wǎng)，E邊集? 邊表示活動(dòng)

   I.事件的最早發(fā)生時(shí)間Ve(i)????? 前提事件完成用的最短時(shí)間
   

   II.事件的最遲發(fā)生時(shí)間Vl(i） ?? 從后往前推
   

   III.活動(dòng)的最早發(fā)生時(shí)間e(i) ?????? 弧尾的Ve（i）
   

   IV.活動(dòng)的最遲發(fā)生時(shí)間l(i)????? 弧頭的Vl(i)-weight
   

10. B樹的插入和刪除

    刪除分為分為被刪結(jié)點(diǎn)在終端結(jié)點(diǎn)和非終端結(jié)點(diǎn)兩種情況

    插入和刪除的難點(diǎn)在于分裂和合并，實(shí)際操作一下就明白了
    

11. Hash函數(shù)

    構(gòu)造散列表比較簡(jiǎn)單，需要理解的是ASL的求解，可以參看一下王道書上P269頁(yè)的第三題
    

12. KMP算法

    搞懂一次忘一次，我太難了。。。。。
    

13. 各種排序算法每一趟的結(jié)果

    主要就是三類：插入，交換，選擇；外加一個(gè)歸并

    
    

原來打字也好麻煩啊，敲不動(dòng)了