數(shù)據(jù)結(jié)構(gòu)與STL

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