數(shù)據(jù)結構：C++與面向對象的途徑（修訂版）

第一章 緒論
1.1 問題求解
1.1.1 問題
1.1.2 問題的分析
1.].3 算法的選擇
1.1.4 解的精化
1.2 數(shù)據(jù)結構
1.3 算法
1.3.1 算法的設計
1.3.2 算法的分析
1.4 抽象數(shù)據(jù)類型
1.5 程序設計方法和語言
小結
習題
第二章 C++與面向對象初步
2.1 C++語言對C的基本擴充
2.1.1 注釋
2.1.2 函數(shù)原型說明
2.1.3 引用和引用參數(shù)
2.1.4 重載
2.1.5 缺省參數(shù)
2.1.6 變量說明
2.1.7 輸入和輸出
2.1.8 動態(tài)存儲分配
2.1.9 類型定義
2.1.10 強制類型轉換
2.2 對象和類
2.3 類的界面描述和實現(xiàn)
2.3.1 類的數(shù)據(jù)域
2.3.2 對象的行為——成員函數(shù)
2.3.3 運算符作為成員函數(shù)
2.3.4 用構造函數(shù)進行實例的初始化
2.4 普通運算符和普通函數(shù)
2.4.1 普通運算符
2.4.2 普通函數(shù)
2.4.3 輸入和輸出
2.5 類的合成、繼承和多態(tài)性
2.5.1 合成
2.5.2 繼承
2.5.3 多態(tài)性
小結
習題
第三章 字符串——數(shù)據(jù)封裝技術
3.1 C語言的字符和字符串
3.2 字符串數(shù)據(jù)抽象的描述和實現(xiàn)
3.2.1 字符串類的定義
3.2.2 構造函數(shù)的定義
3.2.3 析構函數(shù)
3.2.4 基本成員函數(shù)的實現(xiàn)
3.2.5 比較運算符
3.2.6 串連接
3.2.7 輸入和輸出
3.3 子串
3.4 模式匹配
3.4.1 簡單字符串匹配
3.4.2 Knuth-Morris.Pratt模式匹配算法
3.4.3 Boycr－Moom字符串匹配算法
小結
習題
第四章 向量——類的重用技術
4.1 模板類
4.2 向量的實現(xiàn)
4.3 定界向量和枚舉向量、——繼承方式的重用
4.3.1 定界向量
4.3.2 枚舉向量
4.4 排序向量和矩陣——合成方式的重用
4.4.1 排序向量和二分法檢索
4.4.2 矩陣
4.5 向量遍歷器
4.5.1 遍歷器的抽象
4.5.2 向量遍歷器
4.6 向量的排序——模板函數(shù)
4.6.1 插入排序
4.6.2 起泡排序
4.6.3 選擇排序
4.6.4 快速排序算法
4.7 繼承和多態(tài)的若干討論
4.7.1 父類與子類
4.7.2 靜態(tài)類型和動態(tài)類型
4.7.3 框架和框架類
4.7.4 蔽和虛函數(shù)
4.7.5 虛遮蔽和非虛遮蔽
4.7.6 兩類繼承
4.7.7 多態(tài)的主要形式
4.7.8 參數(shù)多態(tài)性——歸約
4.7.9 切割問題
小結
習題
第五章 動態(tài)數(shù)據(jù)結構——鏈表
5.1 單鏈表的定義
5.1.1 表類
5.1.2 鏈類
5.2 單鏈表的實現(xiàn)
5.2.1 鏈類的實現(xiàn)
5.2.2 表類的實現(xiàn)
5.3 表遍歷器
5.3.1 表遍歷器類
5.3.2 表遍歷器類的實現(xiàn)表的應用：多項式處理
5.4.1 項類
5.4.2 多項式類
5.5 排序表
5.5.1 排序表類
5.5.2 排序表類的實現(xiàn)
5.5.3 排序表的應用——表插入排序
5.6 其他鏈表
5.6.1 自組織表
5.6.2 雙端表
5.6.3 循環(huán)表
5.6.4 雙鏈表
5.7 可利用空間表
小結
習題
第六章 棧和隊列
6.1 抽象類棧和隊列
6.2 棧的實現(xiàn)
6.2.1 棧的向量實現(xiàn)
6.2.2 棧的鏈表實現(xiàn)
6.3 棧的應用——表達式計算
6.3.1 后綴表達式的求值
6.3.2 中綴表達式到后綴表達式的轉換
6.4 隊列的實現(xiàn)
6.4.1 隊列的向量實現(xiàn)
6.4.2 隊列的鏈表實現(xiàn)
6.5 隊列的應用——農(nóng)夫過河問題
小結
習題
第七章 樹和二叉樹
7.1 基本概念
7.1.1 樹
7.1.2 二叉樹山
7.1.3 樹與二叉樹的關系
7.2 二叉樹的實現(xiàn)
7.2.1 二叉樹結點類
7.2.2 基本二叉樹類
7.2.3 可構造二叉樹類
7.3 二叉樹的周游
7.3.1 周游的遞歸實現(xiàn)
7.3.2 通過遍歷器實現(xiàn)周游
7.3.3 前序周游器類
7.3.4 中序周游器類
7.3.5 后序周游器類
7.3.6 層次周游算法(按寬度方向周游)
7.4 二叉樹的向量表示
7.4.1 二叉樹向量表示的一種基本方法
7.4.2 記錄結構信息的二叉樹向量表示
7.5 二叉排序樹
7.6 平衡的二叉排序樹
7.6.1 AVL樹上的操作
7.6.2 AVL樹的設計與實現(xiàn)
7.7 二叉樹的應用——哈夫曼樹
小結
習題
第八章 優(yōu)先隊列
8.1 優(yōu)先隊列的抽象
8.2 堆
8.3 堆排序
8.4 斜堆
8.5 離散事件模擬
8.5.1 模擬類的結構
8.5.2 冰淇淋店的模擬
8.5.3 隨機數(shù)
小結
習題
第九章 集合與字典
9.1 集合及其運算
9.1.1 集合運算
9.1.2 集合類
9.2 位向量集合
9.2.1 位向量
9.2.2 位向量集合
9.2.3 字符集合
9.2.4 字符集類的應用——將字符串分解為單詞
9.3 集合的表實現(xiàn)
9.4 關聯(lián)與字典
9.5 字典的關聯(lián)表實現(xiàn)
9.6 字典的應用
9.6.1 稀疏矩陣
9.6.2 排序字典
9.6.3 索引的實現(xiàn)
小結
習題
第十章 散列結構
10.1 散列結構
10.2 散列函數(shù)
10.3 開地址散列向量
10.4 桶散列——用桶解決碰撞
10.4.1 桶散列的抽象模板類
10.4.2 用樹作為桶的實現(xiàn)
10.4.3 桶散列結構操作時間的分析
10.5 桶散列結構的遍歷器
10.6 用散列表實現(xiàn)集合
10.6.1 應用——拼寫檢查器
10.7 用桶散列表實現(xiàn)字典
小結
習題
第十一章 圖
11.1 基本概念
11.2 圖的鄰接矩陣表示和Warshall算法
11.2.1 圖的鄰接矩陣表示
11.2.2 圖結點的可達性問題
11.3 鄰接表方式的圖表示和深度優(yōu)先搜索
11.3.1 鄰接表表示中的結點類
11.3.2 用深度優(yōu)先方式求解可達性問題
11.4 帶權圖的矩陣表示和Floyd算法
11.4.1 帶權圖的鄰接矩陣
11.4.2 帶權圖最短路徑問題Floyd算法
11.5 帶權圖的鄰接表表示與Dijkstra算法
11.5.1 帶權圖的鄰接表表示
11.5 ，2從一個結點出發(fā)的最短路徑和Dijkstra算法
11.6 連通性、帶權連通無向圖與最小生成樹
11.7 有限自動機
11.8 拓撲排序
小結
習題
第十二章 文件
12.1 外存、文件及其問題
12.1.1 外存儲器的特點與信息組織
12.1.2 文件基本結構和操作
12.1.3 文件與字典
12.1.4 文件組織
12.2 C++的字符流文件及其操作
12.3 歸并排序
12.4 文件的隨機訪問
12.5 文件索引結構
12.5.1 索引向量
12.5.2 樹形索引結構
12.5.3 B樹
12.5.4 B+樹
12.6 樹索引文件的實現(xiàn)
小結
習題
附錄
附錄A 主要抽象數(shù)據(jù)類及其相互關系
附錄B BorlandC++集成開發(fā)環(huán)境使用入門
附錄C “多叉路口的交通管理系統(tǒng)
上機報告