數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述（第三版）

第1章 引論. 1  
1.1 本書(shū)討論的內(nèi)容    
1.2 數(shù)學(xué)知識(shí)復(fù)習(xí)    
1.2.1 指數(shù) 2  
1.2.2 對(duì)數(shù) 2  
1.2.3 級(jí)數(shù) 3  
1.2.4 模運(yùn)算 4  
1.2.5 證明方法 4  
1.3 遞歸的簡(jiǎn)單介紹 6  
1.4 C++類    
1.4.1 基本class語(yǔ)法 9  
1.4.2 特別的構(gòu)造函數(shù)語(yǔ)法與訪問(wèn)函數(shù) 10  
1.4.3 接口與實(shí)現(xiàn)的分離 11  
1.4.4 vector和string    
1.5 C++細(xì)節(jié)    
1.5.1 指針 14  
1.5.2 參數(shù)傳遞 15  
1.5.3 返回值傳遞 16  
1.5.4 引用變量 16  
1.5.5 三大函數(shù)：析構(gòu)函數(shù). 復(fù)制構(gòu)造函數(shù)和operator= 17  
1.5.6 C風(fēng)格的數(shù)組和字符串    
1.6 模板    
1.6.1 函數(shù)模板    
1.6.2 類模板 22  
1.6.3 Object. Comparable和例子    
1.6.4 函數(shù)對(duì)象    
1.6.5 類模板的分離編譯    
1.7 使用矩陣    
1.7.1 數(shù)據(jù)成員. 構(gòu)造函數(shù)和基本訪問(wèn)函數(shù) 27  
1.7.2 operator[] 28  
1.7.3 析構(gòu)函數(shù). 復(fù)制賦值和復(fù)制構(gòu)造函數(shù) 29  
小結(jié) 29  
練習(xí) 29  
參考文獻(xiàn) 30  
第2章 算法分析 32  
2.1 數(shù)學(xué)基礎(chǔ) 32  
2.2 模型 34  
2.3 要分析的問(wèn)題 34  
2.4 運(yùn)行時(shí)間計(jì)算 36  
2.4.1 一個(gè)簡(jiǎn)單的例子 37  
2.4.2 一般法則 37  
2.4.3 最大子序列和問(wèn)題的解 39  
2.4.4 運(yùn)行時(shí)間中的對(duì)數(shù) 44  
2.4.5 檢驗(yàn)?zāi)愕姆治?46  
2.4.6 分析結(jié)果的準(zhǔn)確性 47  
小結(jié) 48  
練習(xí) 48  
參考文獻(xiàn) 52  
第3章 表. 棧和隊(duì)列 53  
3.1 抽象數(shù)據(jù)類型（ADT） 53  
3.2 表ADT 53  
3.2.1 表的簡(jiǎn)單數(shù)組實(shí)現(xiàn) 54  
3.2.2 簡(jiǎn)單鏈表 54  
3.3 STL中的向量和表 55  
3.3.1 迭代器 56  
3.3.2 示例：對(duì)表使用erase 57  
3.3.3 const_iterator 58  
3.4 向量的實(shí)現(xiàn) 59  
3.5 表的實(shí)現(xiàn) 63  
3.6 棧ADT 71  
3.6.1 棧模型 71  
3.6.2 棧的實(shí)現(xiàn) 72  
3.6.3 應(yīng)用 72  
3.7 隊(duì)列ADT 78  
3.7.1 隊(duì)列模型 78  
3.7.2 隊(duì)列的數(shù)組實(shí)現(xiàn) 78  
3.7.3 隊(duì)列的應(yīng)用 80  
小結(jié) 81  
練習(xí) 81  
第4章 樹(shù) 85  
4.1 預(yù)備知識(shí) 85  
4.1.1 樹(shù)的實(shí)現(xiàn) 86  
4.1.2 樹(shù)的遍歷及應(yīng)用 87  
4.2 二叉樹(shù) 90  
4.2.1 實(shí)現(xiàn) 90  
4.2.2 一個(gè)例子——表達(dá)式樹(shù) 91  
4.3 查找樹(shù)ADT——二叉查找樹(shù) 93  
4.3.1 contains 94  
4.3.2 findMin和findMax 96  
4.3.3 insert 97  
4.3.4 remove 98  
4.3.5 析構(gòu)函數(shù)和復(fù)制賦值操作符 99  
4.3.6 平均情況分析 99  
4.4 AVL樹(shù) 102  
4.4.1 單旋轉(zhuǎn) 104  
4.4.2 雙旋轉(zhuǎn) 106  
4.5 伸展樹(shù) 111  
4.5.1 一個(gè)簡(jiǎn)單的想法（不能直接使用） 112  
4.5.2 伸展 113  
4.6 樹(shù)的遍歷 118  
4.7 B樹(shù) 119  
4.8 標(biāo)準(zhǔn)庫(kù)中的set和map 123  
4.8.1 set 123  
4.8.2 map 124  
4.8.3 set和map的實(shí)現(xiàn) 125  
4.8.4 使用幾個(gè)map的例子 126  
小結(jié) 130  
練習(xí) 130  
參考文獻(xiàn) 135  
第5章 散列 137  
5.1 基本思想 137  
5.2 散列函數(shù) 137  
5.3 分離鏈接法 139  
5.4 不使用鏈表的散列表 142  
5.4.1 線性探測(cè) 142  
5.4.2 平方探測(cè) 144  
5.4.3 雙散列 148  
5.5 再散列 148  
5.6 標(biāo)準(zhǔn)庫(kù)中的散列表 150  
5.7 可擴(kuò)散列 151  
小結(jié) 153  
練習(xí) 154  
參考文獻(xiàn) 156  
第6章 優(yōu)先隊(duì)列（堆） 158  
6.1 模型 158  
6.2 一些簡(jiǎn)單的實(shí)現(xiàn) 159  
6.3 二叉堆 159  
6.3.1 結(jié)構(gòu)性質(zhì) 159  
6.3.2 堆序性質(zhì) 160  
6.3.3 基本的堆操作 161  
6.3.4 堆的其他操作 164  
6.4 優(yōu)先隊(duì)列的應(yīng)用 167  
6.4.1 選擇問(wèn)題 167  
6.4.2 事件模擬 168  
6.5 d堆 169  
6.6 左式堆 170  
6.6.1 左式堆性質(zhì).. 170  
6.6.2 左式堆操作 171  
6.7 斜堆 175  
6.8 二項(xiàng)隊(duì)列 177  
6.8.1 二項(xiàng)隊(duì)列結(jié)構(gòu) 177  
6.8.2 二項(xiàng)隊(duì)列操作 178  
6.8.3 二項(xiàng)隊(duì)列的實(shí)現(xiàn) 180  
6.9 標(biāo)準(zhǔn)庫(kù)中的優(yōu)先隊(duì)列 183  
小結(jié) 185  
練習(xí) 185  
參考文獻(xiàn) 189  
第7章 排序 191  
7.1 預(yù)備知識(shí) 191  
7.2 插入排序 192  
7.2.1 算法 192  
7.2.2 插入排序的STL實(shí)現(xiàn) 192  
7.2.3 插入排序的分析 194  
7.3 一些簡(jiǎn)單排序算法的下界 194  
7.4 謝爾排序 195  
7.5 堆排序 198  
7.6 歸并排序 200  
7.7 快速排序 204  
7.7.1 選取樞紐元 206  
7.7.2 分割策略 206  
7.7.3 小數(shù)組 208  
7.7.4 實(shí)際的快速排序例程 208  
7.7.5 快速排序的分析 209  
7.7.6 選擇問(wèn)題的線性期望時(shí)間算法 213  
7.8 間接排序 213  
7.8.1 vector＜Comparable*＞不運(yùn)行 215  
7.8.2 智能指針類 216  
7.8.3 重載operator＜ 217  
7.8.4 使用“*”解引用指針 217  
7.8.5 重載類型轉(zhuǎn)換操作符 217  
7.8.6 隨處可見(jiàn)的隱式類型轉(zhuǎn)換 217  
7.8.7 雙向隱式類型轉(zhuǎn)換會(huì)導(dǎo)致歧義 218  
7.8.8 指針減法是合法的 218  
7.9 排序算法的一般下界 218  
7.10 桶排序 220  
7.11 外部排序 220  
7.11.1 為什么需要新算法 220  
7.11.2 外部排序模型 221  
7.11.3 簡(jiǎn)單算法 221  
7.11.4 多路合并 222  
7.11.5 多相合并 223  
7.11.6 替換選擇 223  
小結(jié) 224  
練習(xí) 225  
參考文獻(xiàn) 229  
第8章 不相交集類 231  
8.1 等價(jià)關(guān)系 231  
8.2 動(dòng)態(tài)等價(jià)性問(wèn)題 231  
8.3 基本數(shù)據(jù)結(jié)構(gòu) 233  
8.4 靈巧求并算法 235  
8.5 路徑壓縮 237  
8.6 按秩求并和路徑壓縮的最壞情形 239  
8.7 一個(gè)應(yīng)用 243  
小結(jié) 245  
練習(xí) 245  
參考文獻(xiàn) 246  
第9章 圖論算法 248  
9.1 若干定義 248  
9.2 拓?fù)渑判?250  
9.3 最短路徑算法 252  
9.3.1 無(wú)權(quán)最短路徑 254  
9.3.2 Dijkstra算法 257  
9.3.3 具有負(fù)邊值的圖 262  
9.3.4 無(wú)環(huán)圖 263  
9.3.5 所有頂點(diǎn)對(duì)的最短路徑 265  
9.3.6 最短路徑舉例 266  
9.4 網(wǎng)絡(luò)流問(wèn)題 267  
9.5 最小生成樹(shù) 271  
9.5.1 Prim算法 272  
9.5.2 Kruskal算法 273  
9.6 深度優(yōu)先搜索的應(yīng)用 275  
9.6.1 無(wú)向圖 276  
9.6.2 雙連通性 276  
9.6.3 歐拉回路 279  
9.6.4 有向圖 282  
9.6.5 查找強(qiáng)分支 283  
9.7 NP完全性介紹 284  
9.7.1 難與易 285  
9.7.2 NP類 286  
9.7.3 NP完全問(wèn)題 286  
小結(jié) 288  
練習(xí) 288  
參考文獻(xiàn) 293  
第10章 算法設(shè)計(jì)技巧 296  
10.1 貪心算法 296  
10.1.1 一個(gè)簡(jiǎn)單的調(diào)度問(wèn)題 297  
10.1.2 赫夫曼編碼 299  
10.1.3 近似裝箱問(wèn)題 303  
10.2 分治算法 310  
10.2.1 分治算法的運(yùn)行時(shí)間 310  
10.2.2 最近點(diǎn)問(wèn)題 312  
10.2.3 選擇問(wèn)題 315  
10.2.4 一些算術(shù)問(wèn)題的理論改進(jìn) 317  
10.3 動(dòng)態(tài)規(guī)劃 320  
10.3.1 用表代替遞歸 320  
10.3.2 矩陣乘法的順序安排 322  
10.3.3 最優(yōu)二叉查找樹(shù) 325  
10.3.4 所有點(diǎn)對(duì)最短路徑 327  
10.4 隨機(jī)化算法 329  
10.4.1 隨機(jī)數(shù)生成器 330  
10.4.2 跳躍表 333  
10.4.3 素性測(cè)試 335  
10.5 回溯算法 337  
10.5.1 公路收費(fèi)點(diǎn)重建問(wèn)題 337  
10.5.2 博弈 341  
小結(jié) 346  
練習(xí) 346  
參考文獻(xiàn) 351  
第11章 攤還分析 355  
11.1 一個(gè)無(wú)關(guān)的智力問(wèn)題 355  
11.2 二項(xiàng)隊(duì)列 356  
11.3 斜堆 359  
11.4 斐波那契堆 361  
11.4.1 切除左式堆中的結(jié)點(diǎn) 362  
11.4.2 二項(xiàng)隊(duì)列的懶惰合并 364  
11.4.3 斐波那契堆操作 366  
11.4.4 時(shí)間界的證明 367  
11.5 伸展樹(shù) 368  
小結(jié) 371  
練習(xí) 371  
參考文獻(xiàn) 372  
第12章 高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn) 374  
12.1 自頂向下伸展樹(shù) 374  
12.2 紅黑樹(shù) 379  
12.2.1 自底向上插入 380  
12.2.2 自頂向下紅黑樹(shù) 381  
12.2.3 自頂向下刪除 385  
12.3 確定性跳躍表 387  
12.4 AA樹(shù) 392  
12.5 treap樹(shù) 396  
12.6 k-d樹(shù) 399  
12.7 配對(duì)堆 401  
小結(jié) 405  
練習(xí) 406  
參考文獻(xiàn) 408  
附錄 類模板的分離編譯 411  
索引... 414