《數據抽象和問題求解》是2005年清華大學出版社出版的圖書，作者是Frank M.Carr。
基本介紹
- 書名：數據抽象和問題求解
- 作者：(美)Frank M.Carr
- 譯者：郭平、張敏
- ISBN：9787302118695
- 頁數：706
- 定價：79.80元
- 出版社：清華大學出版社
- 出版時間：2005-11
- 副標題：C++語言描述
內容簡介,目錄,
內容簡介
本書主要論述數據抽象和其他解決問題的工具，是計算機科學的第二門課。
本書旨在使學生切實了解和掌握數據抽象、面向對象編程及其他主流的問題解決技術。本書分兩部分。第I部分是問題解決技術，主要介紹了編程和軟體工程的主要問題，分析了遞歸、數據抽象和鍊表。第II部分用ADT解決問題。這部分主要介紹了棧、佇列、樹、表、堆和優先佇列的基本ADT，還討論了數量階分析和大O表示法，規範了以前討論的算法效率。第II部分還包括平衡查找樹(2-3樹、2-3-4樹、紅-黑樹和AVL樹)和散列等高級主題，並用它們實現表。最後分析外部直接訪問檔案的數據存儲。
本書列舉了大量實例，範圍很廣，既可用作初級數據結構教材，也可用作高級編程和問題解決教材。
本書旨在使學生切實了解和掌握數據抽象、面向對象編程及其他主流的問題解決技術。本書分兩部分。第I部分是問題解決技術，主要介紹了編程和軟體工程的主要問題，分析了遞歸、數據抽象和鍊表。第II部分用ADT解決問題。這部分主要介紹了棧、佇列、樹、表、堆和優先佇列的基本ADT，還討論了數量階分析和大O表示法，規範了以前討論的算法效率。第II部分還包括平衡查找樹(2-3樹、2-3-4樹、紅-黑樹和AVL樹)和散列等高級主題，並用它們實現表。最後分析外部直接訪問檔案的數據存儲。
本書列舉了大量實例，範圍很廣，既可用作初級數據結構教材，也可用作高級編程和問題解決教材。
目錄
第1部分 問題解決技術
第1章 編程原理與軟體工程
1.1 問題求解與軟體工程
1.1.1 問題求解的含義
1.1.2 軟體的生命周期
1.1.3 優秀解決方案的含義
1.2 模組化設計
1.2.1 抽象與信息隱藏
1.2.2 面向對象的設計
1.2.3 自上面下的設計
1.2.4 一般設計原則
1.2.5 使用UML為面向對象的設計建模
1.2.6 面向對象方式的優點
1.3 關鍵編程問題
1.3.1 模組化
1.3.2 可修改
1.3.3 易用
1.3.4 防故障編程
1.3.5 風格
1.3.6 調試
1.4 小結
1.5 提示
1.6 自我測試題
1.7 練習題
1.8 編程問題
第2章 遞歸：鏡子
2.1 遞歸解決方案
2.1.1 遞歸值函式：n的階乘
2.1.2 遞歸void函式：逆置字元串
2.2 計數
2.2.1 兔子繁殖（Fibonacci序列）
2.2.2 組織遊行隊伍
2.2.3 Spock的困惑
2.3 數組查找
2.3.1 查找數組的最大項
2.3.2 折半查找
2.3.3 查的數組中的第k個最小項
2.4 組織數據
2.5 遞歸與效率
2.6 小結
2.7 提示
2.8 自我測試題
2.9 練習題
2.10 編程問題
第3章 數據抽象：牆
3.1 抽象數據類型
3.2 指定ADT
3.2.1 ADT列表
3.2.2 ADT有序表
3.2.3 設計ADT
3.2.4 公理
3.3 實現ADT
3.3.1 C++類
3.3.2 C++命名空間
3.3.3 基於數組的ADT列表實現
3.3.4 C++異常
3.3.5 使用異常的ADT列表實現
3.4 小結
3.5 提示
3.6 自我測試題
3.7 練習題
3.8 編程問題
第4章 鍊表
4.1 預備知識
4.1.1 指針
4.1.2 數組的動態分配
4.1.3 基於指針的鍊表
4.2 鍊表編程
4.2.1 顯示鍊表的內容
4.2.2 從鍊表中刪除指定的節點
4.2.3 往鍊表的指定位置插入節點
4.2.4 ADT列表的基於指針的實現
4.2.5 比較基於數組的實現和基於引用的實現
4.2.6 使用檔案存儲和恢復鍊表
4.2.7 將鍊表傳給函式
4.2.8 遞歸地處理鍊表
4.2.9 把對象作為鍊表的數據
4.3 鍊表的各種變化
4.3.1 循環鍊表
4.3.2 虛擬頭節點
4.3.3 雙向鍊表
4.4 清單應用程式
4.5 C++標準模板庫
4.5.1 容器
4.5.2 疊代器
4.5.3 標準模板庫類list
4.6 小結
4.7 提示
4.8 自我測試題
4.9 練習題
4.10 編程問題
第5章 遞歸問題解決技術
5.1 回溯
5.1.1 八皇后問題
5.1.2 使用STL類vector解決八皇后問題
5.2 定義語言
5.2.1 語法知識基礎
5.2.2 兩種簡單語言
5.2.3 代數表達式
5.3 遞歸和數學歸納法的關係
5.3.1 factorial遞歸算法的正確性
5.3.2 Hanoi塔的成本
5.4 小結
5.5 提示
5.6 自我測試題
5.7 練習題
5.8 編程問題
第2部分 使用抽象數據類型解決問題
第6章 棧
6.1 抽象數據類型
6.2 ADT棧的簡單套用
6.2.1 檢查括弧匹配
6.2.2 識別語言中的字元串
6.3 ADT棧的實現
6.3.1 ADT棧的基本數組的實現
6.3.2 ADT棧的基於指針的實現
6.3.3 使用ADT列表的實現
6.3.4 各種實現方式的比較
6.3.5 標準模板庫類stack
6.4 套用：代數表達式
6.4.1 計算後綴表達式
6.4.2 中綴表達式與後綴表達式的等價轉換
6.5 套用：查找問題
6.5.1 使用棧的非遞歸解決方案
6.5.2 遞歸解決方案
6.6 棧和遞歸的關係
6.7 小結
6.8 提示
6.9 自我測試題
6.10 練習題
6.11 編程問題
第7章 隊例
7.1 ADT佇列
7.2 ADT佇列的簡單套用
7.2.1 讀取字元串
7.2.2 識別回文
7.3 實現ADT佇列
7.3.1 基於指針的實現
7.3.2 基於數組的實現
7.3.3 使用ADT列表的實現
7.3.4 標準模板庫類queue
7.3.5 實現的比較
7.4 基於位置的ADT總覽
7.5 模擬套用
7.6 小結
7.7 提示
7.8 自我測試題
7.9 練習題
7.10 編程問題
第8章 類關係
8.1 繼承
8.1.1 公有、私有和受保護的繼承
8.1.2 is-a、has-a和As-a關係
8.2 虛函式和後期綁定
8.3 友元
8.4 ADT列表和有序表
8.5 類模板
8.6 重載運算符
8.7 疊代器
8.8 小結
8.9 提示
8.10 自我測試題
8.11 練習題
8.12 編程問題
第9章 算法效率和排序
9.1 確定算法效率
9.1.1 算法的執行時間
9.1.2 算法增率
9.1.3 數量階分析和大O表示法
9.1.4 正確分析問題
9.1.5 查找算法的效率
9.2 排序算法及其效率
9.2.1 選擇排序
9.2.2 起泡排序
9.2.3 插入排序
9.2.4 歸併排序
9.2.5 快速排序
9.2.6 基數排序
9.2.7 各種排序算法的比較
9.2.8 標準模板庫排序算法
9.3 小結
9.4 提示
9.5 自我測試題
9.6 練習題
9.7 練程問題
第10章 樹
10.1 術語
10.2 ADT二叉樹
10.2.1 二叉樹的遍歷
10.2.2 二叉樹的表示
10.2.3 ADT二叉樹的基於指針的實現
10.3 ADT二叉查找樹
10.3.1 ADT二叉查找樹操作的算法
10.3.2 ADT二叉查找樹的基於指針的實現
10.3.3 二叉查找樹操作的效率
10.3.4 樹排序
10.3.5 將二叉查找樹保存到檔案
10.3.6 STL查找算法
10.4 一般樹
10.5 小結
10.6 提示
10.7 自我測試題
10.8 練習題
10.9 編程問題
第11章 表和優先佇列
11.1 ADT表
11.1.1 選擇實現
11.1.2 ADT表的基於數組的有序實現
11.1.3 ADT表的二叉查找樹實現
11.2 ADT優先佇列：ADT表的變體
11.2.1 堆
11.2.2 ADT優先佇列的堆實現
11.2.3 堆排序
11.3 STL中的表和優先佇列
11.3.1 STL關聯容器
11.3.2 STL的priority_queue類和堆算法
11.3 小結
11.4 提示
11.5 自我測試題
11.6 練習題
11.7 編程問題
第12章 表的高級實現
12.1 平衡查找樹
12.1.1 2-3樹
12.1.2 2-3-4樹
12.1.3 紅-黑樹
12.1.4 AVL樹
12.2 散列
12.2.1 散列函式
12.2.2 解決衝突
12.2.3 散列的效率
12.2.4 如何確立散列函式
12.2.5 表遍歷：散列的低效操作
12.2.6 使用STL實現HashMap類
12.3 按多種形式組織數據
12.4 小結
12.5 提示
12.6 自我測試題
12.7 練習題
12.8 編程問題
第13章 圖
13.1 述語
13.2 將圖作為ADT
13.2.1 實現圖
13.2.2 使用STL實現Graph類
13.3 圖的遍歷
13.3.1 深度優先查找
13.3.2 廣度優先查找
13.3.3 使用STL實現BFS類
13.4 圖的套用
13.4.1 拓撲排序
13.4.2 生成樹
13.4.3 最小生成樹
13.4.4 最短路徑
13.4.5 迴路
13.4.6 一些複雜問題
13.5 小結
13.6 提示
13.7 自我測試題
13.8 練習題
13.9 編程問題
第14章 外部方法
14.1 了解外部存儲
14.2 排序外部檔案的數據
14.3 外部表
14.3.1 確定外部檔案的索引
14.3.2 外部散列
14.3.3 B-樹
14.3.4 遍歷
14.3.5 多索引
14.4 小結
14.5 提示
14.6 自我測試題
14.7 練習題
14.8 編程問題
附錄A ++基礎
附錄B ASCII字答代碼
附錄C C++頭檔案和標準函式
附錄D 數學歸納法
附錄E 標準模板庫
術語表
自我測試題答案
第1章 編程原理與軟體工程
1.1 問題求解與軟體工程
1.1.1 問題求解的含義
1.1.2 軟體的生命周期
1.1.3 優秀解決方案的含義
1.2 模組化設計
1.2.1 抽象與信息隱藏
1.2.2 面向對象的設計
1.2.3 自上面下的設計
1.2.4 一般設計原則
1.2.5 使用UML為面向對象的設計建模
1.2.6 面向對象方式的優點
1.3 關鍵編程問題
1.3.1 模組化
1.3.2 可修改
1.3.3 易用
1.3.4 防故障編程
1.3.5 風格
1.3.6 調試
1.4 小結
1.5 提示
1.6 自我測試題
1.7 練習題
1.8 編程問題
第2章 遞歸：鏡子
2.1 遞歸解決方案
2.1.1 遞歸值函式：n的階乘
2.1.2 遞歸void函式：逆置字元串
2.2 計數
2.2.1 兔子繁殖（Fibonacci序列）
2.2.2 組織遊行隊伍
2.2.3 Spock的困惑
2.3 數組查找
2.3.1 查找數組的最大項
2.3.2 折半查找
2.3.3 查的數組中的第k個最小項
2.4 組織數據
2.5 遞歸與效率
2.6 小結
2.7 提示
2.8 自我測試題
2.9 練習題
2.10 編程問題
第3章 數據抽象：牆
3.1 抽象數據類型
3.2 指定ADT
3.2.1 ADT列表
3.2.2 ADT有序表
3.2.3 設計ADT
3.2.4 公理
3.3 實現ADT
3.3.1 C++類
3.3.2 C++命名空間
3.3.3 基於數組的ADT列表實現
3.3.4 C++異常
3.3.5 使用異常的ADT列表實現
3.4 小結
3.5 提示
3.6 自我測試題
3.7 練習題
3.8 編程問題
第4章 鍊表
4.1 預備知識
4.1.1 指針
4.1.2 數組的動態分配
4.1.3 基於指針的鍊表
4.2 鍊表編程
4.2.1 顯示鍊表的內容
4.2.2 從鍊表中刪除指定的節點
4.2.3 往鍊表的指定位置插入節點
4.2.4 ADT列表的基於指針的實現
4.2.5 比較基於數組的實現和基於引用的實現
4.2.6 使用檔案存儲和恢復鍊表
4.2.7 將鍊表傳給函式
4.2.8 遞歸地處理鍊表
4.2.9 把對象作為鍊表的數據
4.3 鍊表的各種變化
4.3.1 循環鍊表
4.3.2 虛擬頭節點
4.3.3 雙向鍊表
4.4 清單應用程式
4.5 C++標準模板庫
4.5.1 容器
4.5.2 疊代器
4.5.3 標準模板庫類list
4.6 小結
4.7 提示
4.8 自我測試題
4.9 練習題
4.10 編程問題
第5章 遞歸問題解決技術
5.1 回溯
5.1.1 八皇后問題
5.1.2 使用STL類vector解決八皇后問題
5.2 定義語言
5.2.1 語法知識基礎
5.2.2 兩種簡單語言
5.2.3 代數表達式
5.3 遞歸和數學歸納法的關係
5.3.1 factorial遞歸算法的正確性
5.3.2 Hanoi塔的成本
5.4 小結
5.5 提示
5.6 自我測試題
5.7 練習題
5.8 編程問題
第2部分 使用抽象數據類型解決問題
第6章 棧
6.1 抽象數據類型
6.2 ADT棧的簡單套用
6.2.1 檢查括弧匹配
6.2.2 識別語言中的字元串
6.3 ADT棧的實現
6.3.1 ADT棧的基本數組的實現
6.3.2 ADT棧的基於指針的實現
6.3.3 使用ADT列表的實現
6.3.4 各種實現方式的比較
6.3.5 標準模板庫類stack
6.4 套用：代數表達式
6.4.1 計算後綴表達式
6.4.2 中綴表達式與後綴表達式的等價轉換
6.5 套用：查找問題
6.5.1 使用棧的非遞歸解決方案
6.5.2 遞歸解決方案
6.6 棧和遞歸的關係
6.7 小結
6.8 提示
6.9 自我測試題
6.10 練習題
6.11 編程問題
第7章 隊例
7.1 ADT佇列
7.2 ADT佇列的簡單套用
7.2.1 讀取字元串
7.2.2 識別回文
7.3 實現ADT佇列
7.3.1 基於指針的實現
7.3.2 基於數組的實現
7.3.3 使用ADT列表的實現
7.3.4 標準模板庫類queue
7.3.5 實現的比較
7.4 基於位置的ADT總覽
7.5 模擬套用
7.6 小結
7.7 提示
7.8 自我測試題
7.9 練習題
7.10 編程問題
第8章 類關係
8.1 繼承
8.1.1 公有、私有和受保護的繼承
8.1.2 is-a、has-a和As-a關係
8.2 虛函式和後期綁定
8.3 友元
8.4 ADT列表和有序表
8.5 類模板
8.6 重載運算符
8.7 疊代器
8.8 小結
8.9 提示
8.10 自我測試題
8.11 練習題
8.12 編程問題
第9章 算法效率和排序
9.1 確定算法效率
9.1.1 算法的執行時間
9.1.2 算法增率
9.1.3 數量階分析和大O表示法
9.1.4 正確分析問題
9.1.5 查找算法的效率
9.2 排序算法及其效率
9.2.1 選擇排序
9.2.2 起泡排序
9.2.3 插入排序
9.2.4 歸併排序
9.2.5 快速排序
9.2.6 基數排序
9.2.7 各種排序算法的比較
9.2.8 標準模板庫排序算法
9.3 小結
9.4 提示
9.5 自我測試題
9.6 練習題
9.7 練程問題
第10章 樹
10.1 術語
10.2 ADT二叉樹
10.2.1 二叉樹的遍歷
10.2.2 二叉樹的表示
10.2.3 ADT二叉樹的基於指針的實現
10.3 ADT二叉查找樹
10.3.1 ADT二叉查找樹操作的算法
10.3.2 ADT二叉查找樹的基於指針的實現
10.3.3 二叉查找樹操作的效率
10.3.4 樹排序
10.3.5 將二叉查找樹保存到檔案
10.3.6 STL查找算法
10.4 一般樹
10.5 小結
10.6 提示
10.7 自我測試題
10.8 練習題
10.9 編程問題
第11章 表和優先佇列
11.1 ADT表
11.1.1 選擇實現
11.1.2 ADT表的基於數組的有序實現
11.1.3 ADT表的二叉查找樹實現
11.2 ADT優先佇列：ADT表的變體
11.2.1 堆
11.2.2 ADT優先佇列的堆實現
11.2.3 堆排序
11.3 STL中的表和優先佇列
11.3.1 STL關聯容器
11.3.2 STL的priority_queue類和堆算法
11.3 小結
11.4 提示
11.5 自我測試題
11.6 練習題
11.7 編程問題
第12章 表的高級實現
12.1 平衡查找樹
12.1.1 2-3樹
12.1.2 2-3-4樹
12.1.3 紅-黑樹
12.1.4 AVL樹
12.2 散列
12.2.1 散列函式
12.2.2 解決衝突
12.2.3 散列的效率
12.2.4 如何確立散列函式
12.2.5 表遍歷：散列的低效操作
12.2.6 使用STL實現HashMap類
12.3 按多種形式組織數據
12.4 小結
12.5 提示
12.6 自我測試題
12.7 練習題
12.8 編程問題
第13章 圖
13.1 述語
13.2 將圖作為ADT
13.2.1 實現圖
13.2.2 使用STL實現Graph類
13.3 圖的遍歷
13.3.1 深度優先查找
13.3.2 廣度優先查找
13.3.3 使用STL實現BFS類
13.4 圖的套用
13.4.1 拓撲排序
13.4.2 生成樹
13.4.3 最小生成樹
13.4.4 最短路徑
13.4.5 迴路
13.4.6 一些複雜問題
13.5 小結
13.6 提示
13.7 自我測試題
13.8 練習題
13.9 編程問題
第14章 外部方法
14.1 了解外部存儲
14.2 排序外部檔案的數據
14.3 外部表
14.3.1 確定外部檔案的索引
14.3.2 外部散列
14.3.3 B-樹
14.3.4 遍歷
14.3.5 多索引
14.4 小結
14.5 提示
14.6 自我測試題
14.7 練習題
14.8 編程問題
附錄A ++基礎
附錄B ASCII字答代碼
附錄C C++頭檔案和標準函式
附錄D 數學歸納法
附錄E 標準模板庫
術語表
自我測試題答案
