基本介紹
內容簡介
《數據結構與面向對象程式設計(C++版)(第4版)》是為計算機科學專業的第二門課程CS2編寫的，《數據結構與面向對象程式設計(C++版)(第4版)》系統全面介紹了數據結構與面向對象程式設計相關知識，《數據結構與面向對象程式設計(C++版)(第4版)》不僅非常適合於作為計算機及相關專業“數據結構”和“C++面向對象程式設計”的教材，也是計算機軟體開發人員的常備參考書。
作者簡介
作者:(美國)梅因(Michael Main) (美國)薩維特奇(Walter Savitch) 譯者：金名 等
圖書目錄
第1章 軟體開發的階段
1.1 規範說明、設計與實現
1.1.1 概念設計：問題分解
1.1.2 前置條件與後置條件
1.1.3 使用由其他程式設計師提供的函式
1.1.4 有關ANSI/SOC++標準的實現問題
1.1.5 本節自測練習
1.2 運行時間分析
1.2.1 台階計數問題
1.2.2 大O表示法
1.2.3 C++函式的時間分析
1.2.4 最壞情況、平均情況以及最好情況下的時間分析
1.2.5 本節自測練習
1.3 測試與調試
1.3.1 選擇測試數據
1.3.2 邊界值
1.3.3 完全代碼測試
1.3.4 調試
1.3.5 本節自測練習
1.4 本章小結
本章自測練習參考答案
第2章 抽象數據類型與C++類
2.1 類與成員
2.1.1 編程示例：節流閥類throttle
2.1.2 使用類
2.1.3 throtde類的演示小程式
2.1.4 實現成員函式
2.1.5 可以調用其他成員的成員函式
2.1.6 本節自測練習
2.2 構造函式
2.2.1 throttle類的構造函式
2.2.2 修訂throttle類的成員函式
2.2.3 內聯成員函式
2.2.4 本節自測練習
2.3 使用名稱空間、頭檔案與實現檔案
2.3.1 創建名稱空間
2.3.2 頭檔案
2.3.3 實現檔案
2.3.4 使用名稱空間裡的數據項
2.3.5 本節自測練習
2.4 類與參數
2.4.1 編程示例：point類
2.4.2 參數默認值
2.4.3 參數
2.4.4 當函式的返回值的數據類型為類時
2.4.5 本節自測練習
2.5 操作符重載
2.5.1 二元比較操作符重載
2.5.2 二元算術操作符重載
2.5.3 輸入輸出操作符重載
2.5.4 友元函式
2.5.5 point類匯總
2.5.6 操作符重載小結
2.5.7 本節自測練習
2.6 標準模板庫與pair類
2.7 本章小結
本章自測練習參考答案
編程項目
第3章 容器類
3.1 bag類
3.1.1 bag類的規範說明
3.1.2 bag類的文檔說明
3.1.3 bag類的演示程式
3.1.4 bag類的設計
3.1.5 類的不變式
3.1.6 bag類的實現
3.1.7 bag類的集成
3.1.8 bag類的測試
3.1.9 bag類的分析：
3.1.10本節自測練習
3.2 編程項目：sequence類
3.2.1 sequence類的規範說明
3.2.2 sequence類的文檔說明
3.2.3 sequence類的設計
3.2.4 sequence類的偽代碼實現
3.2.5 本節自測練習
3.3 互動式測試程式
本節自測練習
3.4 STL中的multiset類及其疊代器
3.4.1 multiset模板類
3.4.2 multiset類的一些成員
3.4.3 疊代器與（…）模式
3.4.4 測試疊代器的相等性
3.4.5 multiset類的其他操作符
3.4.6 不合法的疊代器
3.4.7 本節自測練習
3.5 本章小結
本章自測練習參考答案
編程項目
第4章 指針與動態數組
4.1 指針與動態記憶體
4.1.1 指針變數
4.1.2 指針與賦值操作符一起使用
4.1.3 動態變數與new操作符
4.1.4 使用new操作符為動態數組分配記憶體
4.1.5 記憶體堆與badalloc異常
4.1.6 delete操作符
4.1.7 本節自測練習
4.2 把指針與數組作為參數
4.2.1 以指針作為值參數
4.2.2 數組參數
4.2.3 以指針或數組作為常量參數
4.2.4 以指針作為引用參數
4.2.5 本節自測練習
4.3 具有動態數組的bag類
4.3.1 指針成員變數
4.3.2 成員函式按需分配記憶體
4.3.3 值語義
4.3.4 析構函式
4.3.5 修訂後的bag類定義
4.3.6 修訂後的bag類實現
4.3.7 修訂後的bag類集成
4.3.8 本節自測練習
4.4 有關動態類的說明
4.4.14條規則
4.4.2 複製構造函式的特殊重要性
4.4.3 本節自測練習
4.5 STL的string類與編程項目
4.5.1 以null結尾的字元串
4.5.2 初始化字元串變數
4.5.3 空字元串
4.5.4 讀寫字元串變數
4.5.5 strcpy函式
4.5.6 strcat函式
4.5.7 strlen函式
4.5.8 strcmp函式
4.5.9 string類的規範說明
4.5.10 string類的構造函式
4.5.11 重載operator（）
4.5.12 其他重載成員
4.5.13 string類的其他操作
4.5.14 string類的設計
4.5.15 string類的實現
4.5.16 string類的演示程式
4.5.17 串聯輸出操作符
4.5.18 聲明常量對象
4.5.19 由構造函式產生的類型轉換
4.5.20 在表達式中使用已重載的操作符
4.5.21 本章設計的string類與C++庫的string類
4.5.22 本節自測練習
4.6 編程項目：polynomial類
4.7 本章小結
本章自測練習參考答案
編程項目
第5章 鍊表
5.1 鍊表的基本節點類
5.1.1 為節點聲明類
5.1.2 在鍊表節點中使用typedef語句
5.1.3 頭指針和尾指針
5.1.4 空指針NULL
5.1.5 頭指針或尾指針為NULL的含義
5.1.6 節點類構造函式
5.1.7 節點類成員函式
5.1.8 成員選擇操作符
5.1.9 本節自測練習
5.2 鍊表工具包
5.2.1 鍊表工具包的頭檔案
5.2.2 計算鍊表的長度
5.2.3 鍊表的參數
5.2.4 在鍊表頭插入新節點
5.2.5 在非鍊表頭的其他位置插入新節點
5.2.6 在鍊表中查找節點
5.2.7 根據節點的位置在鍊表中尋找節點
5.2.8 鍊表複製
5.2.9 在鍊表頭刪除節點
5.2.10 在非鍊表頭刪除節點
5.2.11 清空鍊表
5.2.12 鍊表工具包的集成
5.2.13 使用鍊表工具包
5.2.14 本節自測練習
5.3 用鍊表實現bag類
5.3.1 第3個bag類的規範說明
5.3.2 第3個bag類的類定義
5.3.3 如何使bag類的value_type與節點類的value_type相匹配
5.3.4 在類中使用動態記憶體應遵循的規則
5.3.5 第3個bag類的實現
5.3.6 第3個bag類的集成
5.3.7 本節自測練習
5.4 編程項目：用鍊表實現sequence類
5.4.1 關於修訂後的sequence類的設計建議
5.4.2 關於修訂後的sequence類的值語義
5.4.3 本節自測練習
5.5 動態數組、鍊表與雙向鍊表
5.5.1 做出抉擇
5.5.2 本節自測練習
5.6 標準模板庫的vector、list和deque類
本節測試練習
5.7 本章小結
本章自測練習參考答案
編程項目
第6章 用模板、疊代器和STL進行軟體開發
6.1 模板函式
6.1.1 模板函式的語法
6.1.2 使用模板函式
6.1.3 交換兩個值的模板函式
6.1.4 模板函式的參數匹配
6.1.5 在數組中查找最大項的模板函式
6.1.6 在已排序數組中插入一個數據項的模板函式
6.1.7 本節自測練習
6.2 模板類
6.2.1 模板類的語法
6.2.2 進一步了解模板類實現檔案
6.2.3 模板類成員函式的參數匹配
6.2.4 使用模板類
6.2.5 詳細討論上一個演示程式
6.2.6 本節自測練習
6.3 STL算法與疊代器的使用
6.3.1 STL算法
6.3.2 標準疊代器的類型
6.3.3 數組的疊代器
6.3.4 本節自測習題
6.4 節點模板類
6.4.1 返回引用類型的函式
6.4.2 將引用返回值複製到別處時會發生什麼
6.4.3 這裡成員函式data需要兩個版本
6.4.4 新節點類的頭檔案和實現檔案
6.4.5 本節自測練習
6.5 鍊表的疊代器
6.5.1 節點疊代器
6.5.2 從std：：iterator派生而來的節點疊代器
6.5.3 節點疊代器的私有成員變數
6.5.4 節點疊代器的構造函式
6.5.5 節點疊代器的*操作符
6.5.6 節點疊代器兩個版本的++操作符
6.5.7 節點疊代器的相等和不相等比較
6.5.8 常量集合的疊代器
6.5.9 本節自測練習
6.6 含疊代器的鍊表版bag模板類
6.6.1 如何為容器類提供疊代器
6.6.2 bag類疊代器
6.6.3 將疊代器定義在bag類中的原因
6.6.4 本節自測練習
6.7 本章小結與5個bag類的小結
本章自測練習答案
編程項目
第7章 棧
7.1 STL的stack類
7.1.1 標準庫的stack類
7.1.2 編程示例：翻轉單詞
7.1.3 本節自測練習
7.2 棧的套用
7.2.1 編程示例：括弧的匹配
7.2.2 編程示例：算術表達式求值
7.2.3 算術表達式求值的規範說明
7.2.4 算術表達式求值的設計
7.2.5 算術表達式求值的實現
7.2.6 計算器程式使用的函式
7.2.7 算術表達式求值的測試與分析
7.2.8 算術表達式求值的改進
7.2.9 本節自測練習
7.3 stack類的實現
7.3.1 棧的數組實現
7.3.2 棧的鍊表實現
7.3.3 Koenig查找
7.3.4 本節自測練習
7.4 更複雜的棧套用
7.4.1 後綴表達式求值
7.4.2 將中綴表示法轉換成後綴表示法
7.4.3 在中綴表達式中使用優先權規則
7.4.4 中綴轉換為後綴的正確性
7.4.5 本節自測練習
7.5 本章小結
本章自測練習答案
編程項目
第8章 佇列
8.1 STL佇列
8.1.1 標準庫的佇列類
8.1.2 佇列的使用
8.1.3 本節自測練習
8.2 佇列的套用
8.2.1 編程示例：識別回文
8.2.2 本節自測練習
8.2.3 編程示例：洗車模擬程式
8.2.4 洗車模擬程式的規範說明
8.2.5 洗車模擬程式的設計
8.2.6 實現洗車類
8.2.7 實現模擬函式
8.2.8 本節自測練習
8.3 佇列類的實現
8.3.1 佇列的數組實現
8.3.2 有關佇列中環形數組實現的討論
8.3.3 佇列的鍊表實現
8.3.4 實現細節
8.3.5 本節自測練習
8.4 實現STL的雙端佇列
8.4.1 為雙端佇列的value_type項調用析構函式和構造函式
8.4.2 棧和佇列的其他變體
8.4.3 本節自測練習
8.5 棧、佇列和優先佇列類的引用返回值
8.6 本章小結
本章自測練習答案
編程項目
第9章 遞歸思想
9，1 遞歸函式
9.1.1 遞歸思想的第一個例子
9.1.2 跟蹤遞歸調用
9.1.3 編程示例：write_vertical的一個擴展
9.1.4 深入分析遞歸
9.1.5 成功遞歸函式的一般形式
9.1.6 本節自測練習
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.2.9 運用回溯窮舉搜尋的遞歸模式
9.2.10 編程示例：玩具熊遊戲
9.2.11 本節自測練習
9.3 推導遞歸
9.3.1 如何確保沒有無限遞歸
9.3.2 歸納推導遞歸函式的正確性
9.3.3 本節自測練習
9.4 本章小結
本章自測練習答案
編程項目
第10章 樹
10.1樹的簡介
10.1.1 二叉樹
10.1.2 二叉分類樹
10.1.3 一般樹
10.1.4 本節自測練習
10.2 樹的表示法
10.2.1 完全二叉樹的數組表示法
10.2.2 使用節點類表示二叉樹
10.2.3 本節自測練習
10.3 二叉樹節點類
10.3.1 編程示例：猜測動物程式
10.3.2 猜測動物程式的設計與實現
10.3.3 猜測動物程式的改進
10.3.4 本節自測練習
10.4 樹的遍歷
10.4.1 二叉樹的遍歷
10.4.2 從樹的節點中輸出數據
10.4.3 遍歷中的問題
10.4.4 函式作為參數
10.4.5 apply函式的一個模板版本
10.4.6 使apply模板函式更具有通用性
10.4.7 樹遍歷的模板函式
10.4.8 本節自測練習
10.5 二叉查找樹
10.5.1 二叉查找樹存儲機制
10.5.2 第6個bag類的定義
10.5.3 第6個bag類的某些簡單函式的實現
10.5.4 計算某個元素在二叉查找樹中出現的次數
10.5.5 添加一個新元素到二叉查找樹中
10.5.6 從二叉查找樹中刪除某個元素
10.5.7 二叉查找樹的組合操作符
10.5.8 時間分析和疊代器
10.5.9 本節自測練習
10.6 本章小結
本章自測練習答案
編程項目
……
第11章 平衡樹
第12章 查找
第13章 排序
第14章 派生類與繼承
第15章 圖
附錄
