數(shù)據(jù)結(jié)構(gòu)與算法：C++版

第1章 C++面向?qū)ο蟪绦蛟O(shè)計
1.1 抽象數(shù)據(jù)類型
1.2 封裝
1.3 繼承
1.4 指針
1.4.1 指針和數(shù)組
1.4.2 指針和復(fù)制構(gòu)造函數(shù)
1.4.3 指針和析構(gòu)函數(shù)
1.4.4 指針和引用變量
1.4.5 函數(shù)指針
1.5 多態(tài)性
1.6 C++和面向?qū)ο蟪绦蛟O(shè)計
1.7 標(biāo)準(zhǔn)模板庫
1.7.1 容器
1.7.2 迭代器
1.7.3 算法
1.7.4 數(shù)對象
1.8 標(biāo)準(zhǔn)模板庫中的向量
1.9 數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο缶幊?br />1.10 案例分析：隨機(jī)訪問文件
1.1l 習(xí)題
1.12 程序設(shè)計作業(yè)
第2章 復(fù)雜度分析
2.1 計算復(fù)雜度和漸近復(fù)雜度
2.2 大O符號
2.3 大0符號的性質(zhì)
2.4 符號與@符號
2.5 可能的問題
2.6 復(fù)雜度舉例
2.7 確定漸近復(fù)雜度舉例
2.8 最好、平均和最壞情況
2.9 阻尼復(fù)雜度
2.10 NP完整性
2.11 習(xí)題
第3章 鏈表
3.1 單鏈表
3.1.1 插入
3.1.2 刪除
3.1.3 查找
3.2 雙鏈表
3.3 循環(huán)鏈表
3.4 跳躍鏈表
3.5 自組織鏈表
3.6 稀疏表
3.7 標(biāo)準(zhǔn)模板庫中的鏈表
3.8 標(biāo)準(zhǔn)模板庫中的雙端隊列
3.9 小結(jié)
3.10 案例分析：圖書館
3.11 習(xí)題
3.12 程序設(shè)計作業(yè)
第4章 棧與隊列
4.1 棧
4.2 隊列
4.3 優(yōu)先隊列
4.4 標(biāo)準(zhǔn)模板庫中的棧
4.5 標(biāo)準(zhǔn)模板庫中的隊列
4.6 標(biāo)準(zhǔn)模板庫中的優(yōu)先隊列
4.7 案例分析：迷宮問題
4.8 習(xí)題
4.9 程序設(shè)計作業(yè)
第5章 遞歸
5.1 遞歸定義
5.2 函數(shù)調(diào)用與遞歸實現(xiàn)
5.3 遞歸調(diào)用的剖析
5.4 尾部遞歸
5.5 非尾部遞歸
5.6 間接遞歸
5.7 嵌套遞歸
5.8 不合理遞歸
5.9 回溯
5.10 小結(jié)
5.11 案例分析：遞歸下降解釋器
5.12 習(xí)題
5.13 程序設(shè)計作業(yè)
第6章 二叉樹
6.1 樹、二叉樹和二叉搜索樹
6-2 二叉樹的實現(xiàn)
6-3 二叉搜索樹的查找
6.4 樹的遍歷
6.4.1 廣度優(yōu)先遍歷
6.4.2 深度優(yōu)先遍歷
6.4.3 不用棧實現(xiàn)的深度優(yōu)先遍歷
6.5 插入
6.6 刪除
6.6.1 合并刪除
6.6.2 通過復(fù)制進(jìn)行刪除
6.7 樹的平衡
6.7.1 DSW算法
6.7.2 AVL樹
6.8 自調(diào)整樹
6.8.1 自重新構(gòu)造樹
6.8.2 “張開”策略
6.9 堆
6.9.1 將堆作為優(yōu)先隊列
6.9.2 將數(shù)組組織為堆
6.10 波蘭記號和表達(dá)式樹
6.11 案例分析：計算單詞出現(xiàn)的頻率
6.12 習(xí)題
6.13 程序設(shè)計作業(yè)
第7章 多叉樹
7.1 B樹家族
7.1.1 B樹
7.1.2 B*樹
7.1.3 B+樹
7.1.4 前綴B+樹
7.1.5 位樹
7.1.6 R樹
7.1.7 2-4樹
7.1.8 標(biāo)準(zhǔn)模板庫中的集和多集
7.1.9 標(biāo)準(zhǔn)模板庫中的映射和多映射
7.2 trie
7.3 小結(jié)
7.4 案例分析：拼寫檢查器
7.5 習(xí)題
7.6 程序設(shè)計作業(yè)
第8章 圖
8.1 圖的表示法
8.2 圖的遍歷
8-3 最短路徑
8.4 環(huán)的檢測
8.5 生成樹
8.6 連通性
8.6.1 無向圖中的連通性
8.6.2 有向圖中的連通性
8.7 拓?fù)渑判?br />8.8 網(wǎng)絡(luò)
8.8.1 最大流
8.8.2 成本最低的最大流
8.9 匹配
8.9.1 穩(wěn)定匹配問題
8.9.2 分配問題
8.9.3 非二分圖中的匹配集合
8.10 歐拉(Eulerian)圖與漢密爾頓(Harlliltonian)圖
8.11 給圖加上顏色
8.12 圖理論中的NP完整性問題
8.12.1 派系問題
8.12.2 三色問題
8.12.3 頂點覆蓋問題
8.12.4 漢密爾頓環(huán)問題
8.13 案例分析：惟一代表
8.14 習(xí)題
8.10.1 歐拉圖
8.10.2 漢密爾頓圖
8.15 程序設(shè)計作業(yè)
第9章 排序
9.1 基本的排序算法
9.1.1 插入排序
9.1.2 選擇排序
9.1.3 冒泡排序
9.2 決策樹
9-3 高效排序算法
9.3.1 希爾排序
9.3.2 堆排序
9.3.3 快速排序
9.3.4 歸并排序
9.3.5 基數(shù)排序
9.4 標(biāo)準(zhǔn)模板庫中的排序
9.5 小結(jié)
9.6 案例分析：多項式相加
9.7 習(xí)題
9.8 程序設(shè)計作業(yè)
第10 章散列
10.1 散列函數(shù)
10.1.1 除余法
10.1.2 折疊法
10.1.3 平方取中法
10.1.4 提取法
10.1.5 基數(shù)轉(zhuǎn)換法
10.2 沖突解決方法
10.2.1 開放定址法
10.2.2 鏈接法
10.2.3 桶定址
10.3 刪除
l0.4 理想散列函數(shù)
10.4.1 Cichelli方法
10.4.2 FHCD算法
10.5 可擴(kuò)展文件的散列函數(shù)
10.5.1 可擴(kuò)展散列
10.5.2 線性散列
10.6 案例分析：使用桶的散列
10.7 習(xí)題
10.8 程序設(shè)計作業(yè)
第11章 數(shù)據(jù)壓縮
11.1 數(shù)據(jù)壓縮的條件
11.2  Huffman編碼
11.3  Run-Length編碼方式
11.4  Ziv-Lempel編碼方式
11.5  案例分析：Huffman方法和Run-Length編碼方式
11.6  習(xí)題
11.7 程序設(shè)計作業(yè)
第12章 內(nèi)存管理
12.1 sequential-fit方法
12.2 Nonsequential.fit方法
12-3 無用單元回收
12.3.1 標(biāo)記和清除
12.3.2 復(fù)制方法
12.3.3 遞增的無用單元回收
12.4 小結(jié)
12.5 案例分析
12.6 習(xí)題-
12.7 程序設(shè)計作業(yè)
第13章 字符串匹配
13.1字符串的精確匹配
13.1.1簡單的算法
13.1.2 Knuth-Morris-Pratt算法
13.1.3 Boyer-Moore算法-
13.1.4 多次搜索
13.1.5 面向位的方法
13.1.6 單詞集合的匹配
13.1.7 正則表達(dá)式的匹配
13.1.8 后綴tile和樹
13.1.9 后綴數(shù)組
13.2 字符串的模糊匹配
13.2.1 字符串的近似性
13.2.2 有k個錯誤的字符串匹配
13.3 案例分析：最長的共有子字符串
13.4習(xí)題
13.5程序設(shè)計作業(yè)
附錄A 計算大O
A.1 調(diào)和數(shù)序列n
A.2 函靈敏lg（N！）的近似值
A.3 快速排序中平均情況的大O
A.4 隨機(jī)二叉樹中的平均路徑長度
A.5 AVL樹中的節(jié)點數(shù)
附錄B 標(biāo)準(zhǔn)模板庫中的算法
附錄C NP完整性