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

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