算法與數(shù)據(jù)結(jié)構(gòu)（第二版）

第一章　緒論                  
     　第一節(jié)　算法的復雜性                  
         一. 比較兩對算法的效率                  
         二. 復雜性的計量                  
         三. 復雜性的漸近性態(tài)及其階                  
         四. 復雜性漸近階的重要性                  
         五. 算法復雜性漸近階的分析                  
         六. 遞歸方程解的漸近階的求法                  
 　  　第二節(jié)　算法表達中的抽象機制                  
         一. 從機器語言到高級語言的抽象                  
         二. 抽象數(shù)據(jù)類型                  
         三. 使用抽象數(shù)據(jù)類型帶來的好處                  
         四. 數(shù)據(jù)結(jié)構(gòu). 數(shù)據(jù)類型和抽象數(shù)據(jù)類型                  
         習題                  
       第二章　表                  
     　第一節(jié)　ADT表                  
     　第二節(jié)　表的實現(xiàn)                  
         一. 表的數(shù)組實現(xiàn)                  
         二. 表的指針實現(xiàn)                  
         三. 表的游標實現(xiàn)                  
         四. 循環(huán)鏈表                  
         五. 雙鏈表                  
     　第三節(jié)　棧                  
         一. ADT棧                  
         二. 棧的數(shù)組實現(xiàn)                  
         三. 棧的指針實現(xiàn)                  
     　第四節(jié)　隊列                  
         一. ADT隊列                  
         二. 用指針實現(xiàn)隊列                  
         三. 用循環(huán)數(shù)組實現(xiàn)隊列                  
     　第五節(jié)　映射                  
         一. ADT映射                  
         二. 用數(shù)組實現(xiàn)映射                  
         三. 用表實現(xiàn)映射                  
       習題                  
       第三章　串                  
     　第一節(jié)　ADT串                  
 　    第二節(jié)　串的實現(xiàn)                  
         一. 串的數(shù)組實現(xiàn)                  
         二. 串的指針實現(xiàn)                  
         三. 串的塊鏈表示法                  
         四. 串的堆結(jié)構(gòu)                  
   　  第三節(jié)　模式匹配                  
         一. 樸素的模式匹配算法                  
         二. 模式匹配的KMP算法                  
   　    習題                  
       第四章　樹                  
 　    第一節(jié)　樹的定義                  
  　   第二節(jié)　二叉樹                  
  　   第三節(jié)　樹的遍歷                  
   　  第四節(jié)　ADT樹                  
   　  第五節(jié)　樹的實現(xiàn)方法                  
         一. 父親數(shù)組表示法                  
         二. 兒子鏈表表示法                  
         三. 左兒子右兄弟表示法                  
   　  第六節(jié)　二叉樹的實現(xiàn)及其應用                  
         一. 二叉樹的順序存儲結(jié)構(gòu)                  
         二. 二叉樹的結(jié)點度表示法                  
         三. 二叉樹的鏈式存儲結(jié)構(gòu)                  
         四. 果園或森林的二叉樹表示                  
         五. 線索二叉樹                  
         六. 二叉樹的應用                  
         習題                  
       第五章　集會                  
       第一節(jié)　以集合為基礎(chǔ)的抽象數(shù)據(jù)類型                  
         一. 集合的定義和記號                  
         二. 定義在集合上的基本運算                  
         三. 集合的簡單表示法                  
       第二節(jié)　字典                  
         一 . 實現(xiàn)字典的簡單方法                  
         二. 用散列表實現(xiàn)字典                  
         三. 用散列表實現(xiàn)映射                  
       第三節(jié)　有序字典                  
         一. 有序字典的定義                  
         二. 用數(shù)組實現(xiàn)有序字典                  
         三. 用二叉搜索樹實現(xiàn)有序字典                  
       第四節(jié)　平衡樹                  
         一. 紅黑樹                  
         二. 2－3樹                  
       第五節(jié)　優(yōu)先隊列                  
         一. 優(yōu)先隊列的定義                  
         二. 優(yōu)先隊列的字典式實現(xiàn)                  
         三. 優(yōu)先級樹和堆                  
         四. 用數(shù)組實現(xiàn)堆                  
   　  第六節(jié)　并查集                  
         一. 并查集的定義及其簡單實現(xiàn)                  
         二. 并查集的快速實現(xiàn)                  
         三. 并查集的構(gòu)實現(xiàn)                  
       第七節(jié)　檢索樹                  
         一. 檢索樹與檢索樹結(jié)點                  
         二. 用數(shù)組表示檢索樹結(jié)點                  
         三. 用鏈接表表示檢索樹結(jié)點                  
         四. 檢索樹的效率                  
     　  習題                  
       第六章　算法設(shè)計策略與技巧                  
       第一節(jié)　遞歸技術(shù)與分治法                  
         一. 遞歸技術(shù)                  
         二. 分治法的基本思想                  
         三. 大整數(shù)的乘法                  
         四. Strassen矩陣乘法                  
         五. 最接近點對問題                  
         六. 循環(huán)賽日程表                  
   　  第二節(jié)　動態(tài)規(guī)劃                  
         一. 計算矩陣連乘積                  
         二. 動態(tài)規(guī)劃算法的基本要素                  
         三. 最長公共子序列                  
   　  　四. 凸多邊形的最優(yōu)三角剖分                  
       第三節(jié)　貪心算法                  
         一. 活動安排問題                  
         二. 貪心算法的基本要素                  
 　　  　三. 哈夫曼編碼                  
         四. 貪心算法的理論基礎(chǔ)                  
       第四節(jié)　回溯法                  
         一. 回溯法的一般描述                  
         二. n后問題                  
         三. 子集和問題                  
         四. 圖的m－著色問題                  
         五. 回溯法的效率分析                  
       第五節(jié)　限界剪枝法                  
         一. 最小耗費搜索法                  
         二. 限界與剪枝                  
         三. 旅行售貨員問題                  
 　      習題                  
       第七章　排序與選擇                  
   　  第一節(jié)　簡單排序算法                  
         一. 冒泡排序                  
         二. 插入排序                  
         三. 選擇排序                  
         四. 簡單排序算法的計算復雜性                  
       第二節(jié)　快速排序                  
         一. 算法的基本思想及其實現(xiàn)                  
         二. 快速排序的性能                  
         三. 隨機快速排序算法                  
       第三節(jié)　堆排序                  
         一. 堆排序算法的基本思想及其實現(xiàn)                  
         二. 堆排序算法的計算復雜性                  
       第四節(jié)　線性時間排序                  
         一. 計數(shù)排序                  
         二. 桶排序                  
         三. 基數(shù)排序                  
       第五節(jié)　中位數(shù)與第k小元素                  
         一. 平均情況下的線性時間選擇算法                  
         二. 最壞情況下的線性時間選擇算法                  
     　　習題                  
       第八章　圈                  
       第一節(jié)　圖的基本概念                  
         一. 圖及其相關(guān)術(shù)語                  
         二. 抽象數(shù)據(jù)類型ADT圖                  
       第二節(jié)　圖的表示法                  
         一. 鄰接矩陣表示法                  
         二. 鄰接表表示法                  
       第三節(jié)　圖的遍歷                  
         一. 深度優(yōu)先搜索                  
         二. 廣度優(yōu)先搜索                  
       第四節(jié)　圖的連通性                  
         一. 深度優(yōu)先生成森林                  
         二. 無圈有向圖                  
         三. 有向圖的強連通分支                  
         四. 無向圖的割點和雙連通分支                  
       第五節(jié)　最小生成樹                  
         一. 最小生成樹性質(zhì)                  
         二. Prim算法                  
         三. Kruskal算法                  
       第六節(jié)　最短路徑                  
         一. 單源最短路徑                  
         二. 所有頂點對之間的最短路徑                  
       第七節(jié)　圖匹配                  
       　習題                  
       第九章　問題的計算復雜性                  
       第一節(jié)　計算模型                  
         一. 隨機存取機RAM                  
         二. 隨機存取存儲程序機RASP                  
         三. RAM模型的變形與簡化                  
         四. 圖靈機                  
         五. 圖靈機模型與RAM模型的關(guān)系                  
       第二節(jié)　問題的計算時間下界                  
         一. 問題的輸入. 輸出及平凡下界                  
         二. 信息論下界                  
         三. 對手論證方法                  
         四. Ben＿Or下界定理                  
         五. 問題變換與計算復雜性歸約                  
       第三節(jié)　P類與NP類                  
         一. 非確定性圖靈機                  
         二. P類與NP類語言                  
         三. “證書’與VP類語言                  
         四. 問題和語言                  
       第四節(jié)　NP－完全性                  
         一. 多項式時間變換與NP完全問題                  
         二. Cook定理                  
         三. 幾個典型的NP-完全問題                  
       第五節(jié)  NP－完全問題的近似解法                  
         一. 近似算法的性能                  
         二. 頂點覆蓋問題的近似算法                  
         三. 旅行售貨員問題的近似算法                  
         四. 集合覆蓋問題的近似算法                  
 　      五. 子集和問題的近似算法                  
     　  習題                  
       第十章　并行算法                  
       第一節(jié)　并行計算模型                  
         一. PRAM模型                  
         二. 同步與控制                  
         三. 并行算法的表達                  
         四. 并行算法的性能指標                  
         五. 運行時間和工作量有效性                  
       第二節(jié)　并行算法的基本設(shè)計技術(shù)                  
         一. 平衡樹方法                  
         二. 指針跳越技術(shù)                  
         三. 歐拉回路技術(shù)                  
         四. 并行分治法                  
         五. 劃分原理                  
         六. 流水線技術(shù)                  
         七. 接力技術(shù)                  
         八. 遞歸的并行隨機消元法                  
         九. 確定性破對稱技術(shù)                  
       第三節(jié)　EREW算法與CRCW算法的速度比較                  
         一. 并發(fā)讀對提高速度的作用                  
         二. 并發(fā)寫對提高速度的作用                  
         三. CRCW算法速度的上界                  
 　　    習題                  
       第十一章　高級專題                  
       第一節(jié)　算法的分攤時間分析                  
         一. 累計方法                  
         二. 記賬方法                  
         三. 勢能方法                  
         四. 自適應二叉搜索樹                  
       第二節(jié)　可并優(yōu)先隊列                  
         一. 可并優(yōu)先隊列的定義                  
         二. 用二項堆實現(xiàn)可并優(yōu)先隊列                  
         三. 用Fibonacci堆實現(xiàn)可并優(yōu)先隊列                  
       第三節(jié)　數(shù)據(jù)結(jié)構(gòu)的擴充與聯(lián)合                  
         一. 動態(tài)選擇樹——紅黑樹的擴充                  
         二. 數(shù)據(jù)結(jié)構(gòu)擴充的方法                  
         三. 區(qū)間樹                  
         四. 數(shù)據(jù)結(jié)構(gòu)的聯(lián)合                  
       第四節(jié)　靜態(tài)數(shù)據(jù)結(jié)構(gòu)的動態(tài)化方法                  
         一. 可分解搜索問題                  
         二. 靜態(tài)數(shù)據(jù)結(jié)構(gòu)的半動態(tài)化                  
         三. 靜態(tài)數(shù)據(jù)結(jié)構(gòu)的另一種半動態(tài)化劑                  
         四. 靜態(tài)數(shù)據(jù)結(jié)構(gòu)的全動態(tài)變換                  
         五. 其他動態(tài)化方法                  
        習題                  
     參考文獻