數(shù)據結構與STL

出版者的話
專家指導委員會
譯者序
前言
第1章 C＋＋中的類
1.1 類
1.1.1 方法接口
1.1.2 對象
1.1.3 數(shù)據抽象
1.1.4 構造器
1.1.5 一個Employee類
1.1.6 Employee類的定義
實驗1：Company項目
1.1.7 繼承
1.1.8 受保護的訪問
1.1.9 HourlyEmployee類
實驗2：關于繼承的更多的細節(jié)
1.1.10 運算符的重載
1.1.11 友元
實驗3：重載運算符“＝”和運算符“＞＞”
1.1.12 信息隱藏
總結
習題
編程項目1.1：一個Sequence類
第2章 容器類的存儲結構
2.1 指針
2.1.1 堆和堆棧的對比
2.1.2 引用參數(shù)
2.1.3 指針字段
2.1.4 數(shù)組和指針
實驗4：指針變量賦值與動態(tài)變量賦值的對比
2.1.5 動態(tài)變量的存儲空間釋放
2.2 數(shù)組
2.3 容器類
2.3.1 容器類的存儲結構
2.3.2 鏈式結構
2.3.3 迭代器
2.3.4 Iteratror類的設計和實現(xiàn)
實驗5：定義其他的選代器運算符
2.3.5 pop_front方法
2.3.6 析構器
實驗6：重載運算符operator=
2.3.7 通用型算法
實驗7：更多關于通用型算法的知識
2.3.8 數(shù)據結構和標準模板庫
總結
習題
編程項目2.1：擴展Linked類
第3章 軟件工程簡介
3.1 軟件開發(fā)生命周期
3.2 問題分析
3.3 程序設計
3.3.1 方法接口和字段
3.3.2 依賴關系圖
3.4 程序實現(xiàn)
3.4.1 方法驗證
實驗8：驅動器
3.4.2 正確性實現(xiàn)的可行性
3.4.3 方法效率評估
3.4.4 大O表示法
3.4.5 快速獲取大O估算
3.4.6 平衡折中
3.4.7 運行時間分析
3.4.8 隨機性
實驗9：計時和隨機性
3.4.9 類型轉換
3.5 程序維護
總結
習題
編程項目3.1：Linked類的進一步擴充
第4章 遞歸
4.1 簡介
4.2 階乘
4.3 十進制到二進制的轉換
實驗10：斐波納契數(shù)
4.4 漢諾塔
4.5 回溯
4.6 折半查找
實驗11：迭代折半查找
4.7 生成置換
4.8 間接遞歸
4.9 遞歸的代價
總結
習題
編程項目4.1：漢諾塔的選代版本
編程項目4.2：八皇后問題
編程項目4.3：馬的遍歷問題
第5章 向量和雙端隊列
5.1 標準模板庫
5.2 向量
5.2.1 vector類的方法接口
5.2.2 向量迭代器
5.2.3 向量和其他容器的對比
5.2.4 vector類可能的字段
5.2.5 vector類的一個實現(xiàn)
實驗12：vector類的更多的實現(xiàn)細節(jié)
5.3 向量的一個應用：高精度算法
5.3.1 very＿long＿int類的設計
5.3.2 very＿long＿int類的一個實現(xiàn)
實驗13：擴展very＿long＿int類
5.4 雙端隊列
實驗14：惠普的deque類實現(xiàn)的更多細節(jié)
5.5 雙端隊列的一個應用：非常長的整數(shù)
總結
習題
編程項目5.1：擴展very＿long＿int類
編程項目5.2：deque類的另一種實現(xiàn)
第6章 表
6.1 表
6.1.1 list類的方法接口
6.1.2 迭代器接口
6.1.3 鏈表方法和向量或雙端隊列方法的差別
6.1.4 list類的字段和實現(xiàn)
6.1.5 list節(jié)點的存儲
實驗15：更多l(xiāng)ist類的實現(xiàn)細節(jié)
實驗16：計時順序容器
實驗17：迭代器，第二部分
6.1.6 list類的其他實現(xiàn)
6.2 鏈表應用：一個行編輯器
6.2.1 Editor類的設計
6.2.2 Editor類的實現(xiàn)
總結
習題
編程項目6.1：擴展Editor類
編程項目6.2：list類的另一種設計和實現(xiàn)
第7章 隊列和堆棧
7.1 隊列
7.1.1 queue類的方法接口
7.1.2 使用queue類
7.1.3 容器配接器
7.1.4 一個接近的設計
7.2 計算機仿真
7.3 隊列應用：洗車仿真
7.3.1 程序設計
7.3.2 CarWash類的實現(xiàn)
7.3.3 CarWash方法的分析
7.3.4 隨機化到達時間
實驗18：隨機化到達時間
7.4 堆棧
7.4.1 Stack類的方法接口
7.4.2 使用stack類
7.4.3 stack類是一個容器配接器
7.5 堆棧應用1：遞歸是如何實現(xiàn)的
7.6 堆棧應用2：將中綴轉換成后綴
7.6.1 后綴表示法
7.6.2 轉換矩陣
7.6.3 記號
實驗19：將中綴轉化成后綴
7.6.4 前綴表示法
總結
習題
編程項目7.1：擴展洗車仿真
編程項目7.2：求一個條件的值
編程項目7.3：一個迭代的迷宮搜索
編程項目7.4：queue類的另一個設計
第8章 二叉樹和折半查找樹
8.1 定義和屬性
8.1.1 二叉樹定理
8.1.2 外部路徑長度
8.1.3 二叉樹的遍歷
8.2 折半查找樹
8.2.1 BinSearchTree類
8.2.2 BinSearchTree類的Iterator類
8.2.3 BinSearchTree類的字段和實現(xiàn)
8.2.4 遞歸方法
8.2.5 BinSearchTree迭代器
實驗20：BinSearchTree的平均高度
總結
習題
編程項目8.1：BinSearchTree類的另一種實現(xiàn)
第9章 AVL樹
9.1 平衡的折半查找樹
9.2 旋轉
9.3 AVL樹
9.3.1 AVL樹的高度
9.3.2 函數(shù)對象
實驗21：更多的函數(shù)對象的細節(jié)
9.3.3 AVLTree類
9.3.4 fixAfterInsertion方法
9.3.5 insert方法的正確性
9.4 AVL樹的應用：一個簡單的拼寫檢查器
總結
習題
編程項目9.1：AVLTree類的erase方法
編程項目9.2：改進的SpellChecker項目
第10章 紅黑樹
10.1 紅黑樹
10.1.1 紅黑樹的高度
10.1.2 惠普的rb_tree類
10.1.3 rb_tree類中的insert方法
實驗22：使用全部三種情況的紅黑樹插入
10.1.4 erase方法
實驗23：erase的調用，其中應用了全部四種情況
10.2 標準模板庫的關聯(lián)容器
10.3 集合應用：再次討論拼寫檢查器
10.3.1 multiset類
實驗24：更多與set和multiset類相關的知識
10.3.2 map類
10.3.3 multimap類
實驗25：更多與map和multimap類相關的知識
總結
習題
編程項目10.1：一個簡單的辭典
編程項目10.2：創(chuàng)建一個詞匯索引
第11章 優(yōu)先隊列和堆
11.1 介紹
11.1.1 priority_queue類
11.1.2 priority_queue類的字段和實現(xiàn)
11.1.3 堆
實驗26：優(yōu)先隊列中的公平性
11.1.4 priority_queue類的另一種設計及實現(xiàn)
11.2 優(yōu)先隊列的應用：霍夫曼編碼
11.2.1 huffman類的設計
11.2.2 huffman類的實現(xiàn)
總結
習題
編程項目11.1：解碼一個消息
第12章 排序
12.1 介紹
12.2 排序能有多快
12.3 快速排序
12.3.1 樹排序
12.3.2 堆排序
12.3.3 歸并排序
12.3.4 快速排序
12.3.5 分治法算法
實驗27：排序算法的運行時間
總結
習題
編程項目12.1：排序一個文件
第13章 查找和散列類
13.1 分析查找的框架
13.2 查找方式復習
13.2.1 順序查找
13.2.2 折半查找
13.2.3 紅黑樹查找
13.3 hash_map類
13.3.1 hash_map類中的字段
13.3.2 散列
13.3.3 鏈式
13.3.4 iterator類的字段和實現(xiàn)
13.3.5 hash_map類的實現(xiàn)
13.3.6 鏈式散列分析
13.3.7 value_type類
13.3.8 應用
實驗28：hash_map計時
13.4 hash_set類
13.5 開放地址散列
13.5.1 erase方法
13.5.2 主聚類
13.5.3 雙散列
13.5.4 開放地址散列分析
總結
習題
編程項目13.1：使用鏈式和雙散到構造一個符號表的運行時間比較
第14章 圖、樹和網絡
14.1 無向圖
14.2 有向圖
14.3 樹
14.4 網絡
14.5 圖算法
14.5.1 迭代器
14.5.2 連通性
14.5.3 產生最小生成樹
14.5.4 尋找網絡中的最短路徑
14.6 開發(fā)一個網絡類
14.7 network類
14.7.1 network類中的字段
14.7.2 network類的實現(xiàn)
14.7.3 與邊相關的方法的實現(xiàn)
14.7.4 全局方法的實現(xiàn)
14.7.5 get_minimum_spanning_tree方法
14.7.6 get_shortest_path方法
14.7.7 網絡方法的時間花費估算
實驗29：貨郎擔問題
14.7.8 network類的另一種設計和實現(xiàn)
14.8 回溯通過網絡
總結
習題
編程項目14.1：完成鄰接矩陣的實現(xiàn)
編程項目14.2：回溯通過一個網絡
附錄1 數(shù)學背景
附錄2 string類
附錄3 多態(tài)性
參考文獻
索引