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

出版者的話(huà)
專(zhuān)家指導(dǎo)委員會(huì)
譯者序
前言
第1章 C＋＋中的類(lèi)
1.1 類(lèi)
1.1.1 方法接口
1.1.2 對(duì)象
1.1.3 數(shù)據(jù)抽象
1.1.4 構(gòu)造器
1.1.5 一個(gè)Employee類(lèi)
1.1.6 Employee類(lèi)的定義
實(shí)驗(yàn)1：Company項(xiàng)目
1.1.7 繼承
1.1.8 受保護(hù)的訪問(wèn)
1.1.9 HourlyEmployee類(lèi)
實(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類(lèi)
第2章 容器類(lèi)的存儲(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 容器類(lèi)
2.3.1 容器類(lèi)的存儲(chǔ)結(jié)構(gòu)
2.3.2 鏈?zhǔn)浇Y(jié)構(gòu)
2.3.3 迭代器
2.3.4 Iteratror類(lèi)的設(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類(lèi)
第3章 軟件工程簡(jiǎn)介
3.1 軟件開(kāi)發(fā)生命周期
3.2 問(wèn)題分析
3.3 程序設(shè)計(jì)
3.3.1 方法接口和字段
3.3.2 依賴(lài)關(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 類(lèi)型轉(zhuǎn)換
3.5 程序維護(hù)
總結(jié)
習(xí)題
編程項(xiàng)目3.1：Linked類(lèi)的進(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類(lèi)的方法接口
5.2.2 向量迭代器
5.2.3 向量和其他容器的對(duì)比
5.2.4 vector類(lèi)可能的字段
5.2.5 vector類(lèi)的一個(gè)實(shí)現(xiàn)
實(shí)驗(yàn)12：vector類(lèi)的更多的實(shí)現(xiàn)細(xì)節(jié)
5.3 向量的一個(gè)應(yīng)用：高精度算法
5.3.1 very＿long＿int類(lèi)的設(shè)計(jì)
5.3.2 very＿long＿int類(lèi)的一個(gè)實(shí)現(xiàn)
實(shí)驗(yàn)13：擴(kuò)展very＿long＿int類(lèi)
5.4 雙端隊(duì)列
實(shí)驗(yàn)14：惠普的deque類(lèi)實(shí)現(xiàn)的更多細(xì)節(jié)
5.5 雙端隊(duì)列的一個(gè)應(yīng)用：非常長(zhǎng)的整數(shù)
總結(jié)
習(xí)題
編程項(xiàng)目5.1：擴(kuò)展very＿long＿int類(lèi)
編程項(xiàng)目5.2：deque類(lèi)的另一種實(shí)現(xiàn)
第6章 表
6.1 表
6.1.1 list類(lèi)的方法接口
6.1.2 迭代器接口
6.1.3 鏈表方法和向量或雙端隊(duì)列方法的差別
6.1.4 list類(lèi)的字段和實(shí)現(xiàn)
6.1.5 list節(jié)點(diǎn)的存儲(chǔ)
實(shí)驗(yàn)15：更多l(xiāng)ist類(lèi)的實(shí)現(xiàn)細(xì)節(jié)
實(shí)驗(yàn)16：計(jì)時(shí)順序容器
實(shí)驗(yàn)17：迭代器，第二部分
6.1.6 list類(lèi)的其他實(shí)現(xiàn)
6.2 鏈表應(yīng)用：一個(gè)行編輯器
6.2.1 Editor類(lèi)的設(shè)計(jì)
6.2.2 Editor類(lèi)的實(shí)現(xiàn)
總結(jié)
習(xí)題
編程項(xiàng)目6.1：擴(kuò)展Editor類(lèi)
編程項(xiàng)目6.2：list類(lèi)的另一種設(shè)計(jì)和實(shí)現(xiàn)
第7章 隊(duì)列和堆棧
7.1 隊(duì)列
7.1.1 queue類(lèi)的方法接口
7.1.2 使用queue類(lèi)
7.1.3 容器配接器
7.1.4 一個(gè)接近的設(shè)計(jì)
7.2 計(jì)算機(jī)仿真
7.3 隊(duì)列應(yīng)用：洗車(chē)仿真
7.3.1 程序設(shè)計(jì)
7.3.2 CarWash類(lèi)的實(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類(lèi)的方法接口
7.4.2 使用stack類(lèi)
7.4.3 stack類(lèi)是一個(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ò)展洗車(chē)仿真
編程項(xiàng)目7.2：求一個(gè)條件的值
編程項(xiàng)目7.3：一個(gè)迭代的迷宮搜索
編程項(xiàng)目7.4：queue類(lèi)的另一個(gè)設(shè)計(jì)
第8章 二叉樹(shù)和折半查找樹(shù)
8.1 定義和屬性
8.1.1 二叉樹(shù)定理
8.1.2 外部路徑長(zhǎng)度
8.1.3 二叉樹(shù)的遍歷
8.2 折半查找樹(shù)
8.2.1 BinSearchTree類(lèi)
8.2.2 BinSearchTree類(lèi)的Iterator類(lèi)
8.2.3 BinSearchTree類(lèi)的字段和實(shí)現(xiàn)
8.2.4 遞歸方法
8.2.5 BinSearchTree迭代器
實(shí)驗(yàn)20：BinSearchTree的平均高度
總結(jié)
習(xí)題
編程項(xiàng)目8.1：BinSearchTree類(lèi)的另一種實(shí)現(xiàn)
第9章 AVL樹(shù)
9.1 平衡的折半查找樹(shù)
9.2 旋轉(zhuǎn)
9.3 AVL樹(shù)
9.3.1 AVL樹(shù)的高度
9.3.2 函數(shù)對(duì)象
實(shí)驗(yàn)21：更多的函數(shù)對(duì)象的細(xì)節(jié)
9.3.3 AVLTree類(lèi)
9.3.4 fixAfterInsertion方法
9.3.5 insert方法的正確性
9.4 AVL樹(shù)的應(yīng)用：一個(gè)簡(jiǎn)單的拼寫(xiě)檢查器
總結(jié)
習(xí)題
編程項(xiàng)目9.1：AVLTree類(lèi)的erase方法
編程項(xiàng)目9.2：改進(jìn)的SpellChecker項(xiàng)目
第10章 紅黑樹(shù)
10.1 紅黑樹(shù)
10.1.1 紅黑樹(shù)的高度
10.1.2 惠普的rb_tree類(lèi)
10.1.3 rb_tree類(lèi)中的insert方法
實(shí)驗(yàn)22：使用全部三種情況的紅黑樹(shù)插入
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)用：再次討論拼寫(xiě)檢查器
10.3.1 multiset類(lèi)
實(shí)驗(yàn)24：更多與set和multiset類(lèi)相關(guān)的知識(shí)
10.3.2 map類(lèi)
10.3.3 multimap類(lèi)
實(shí)驗(yàn)25：更多與map和multimap類(lèi)相關(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類(lèi)
11.1.2 priority_queue類(lèi)的字段和實(shí)現(xiàn)
11.1.3 堆
實(shí)驗(yàn)26：優(yōu)先隊(duì)列中的公平性
11.1.4 priority_queue類(lèi)的另一種設(shè)計(jì)及實(shí)現(xiàn)
11.2 優(yōu)先隊(duì)列的應(yīng)用：霍夫曼編碼
11.2.1 huffman類(lèi)的設(shè)計(jì)
11.2.2 huffman類(lèi)的實(shí)現(xiàn)
總結(jié)
習(xí)題
編程項(xiàng)目11.1：解碼一個(gè)消息
第12章 排序
12.1 介紹
12.2 排序能有多快
12.3 快速排序
12.3.1 樹(shù)排序
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章 查找和散列類(lèi)
13.1 分析查找的框架
13.2 查找方式復(fù)習(xí)
13.2.1 順序查找
13.2.2 折半查找
13.2.3 紅黑樹(shù)查找
13.3 hash_map類(lèi)
13.3.1 hash_map類(lèi)中的字段
13.3.2 散列
13.3.3 鏈?zhǔn)?br />13.3.4 iterator類(lèi)的字段和實(shí)現(xiàn)
13.3.5 hash_map類(lèi)的實(shí)現(xiàn)
13.3.6 鏈?zhǔn)缴⒘蟹治?br />13.3.7 value_type類(lèi)
13.3.8 應(yīng)用
實(shí)驗(yàn)28：hash_map計(jì)時(shí)
13.4 hash_set類(lèi)
13.5 開(kāi)放地址散列
13.5.1 erase方法
13.5.2 主聚類(lèi)
13.5.3 雙散列
13.5.4 開(kāi)放地址散列分析
總結(jié)
習(xí)題
編程項(xiàng)目13.1：使用鏈?zhǔn)胶碗p散到構(gòu)造一個(gè)符號(hào)表的運(yùn)行時(shí)間比較
第14章 圖、樹(shù)和網(wǎng)絡(luò)
14.1 無(wú)向圖
14.2 有向圖
14.3 樹(shù)
14.4 網(wǎng)絡(luò)
14.5 圖算法
14.5.1 迭代器
14.5.2 連通性
14.5.3 產(chǎn)生最小生成樹(shù)
14.5.4 尋找網(wǎng)絡(luò)中的最短路徑
14.6 開(kāi)發(fā)一個(gè)網(wǎng)絡(luò)類(lèi)
14.7 network類(lèi)
14.7.1 network類(lèi)中的字段
14.7.2 network類(lèi)的實(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類(lèi)的另一種設(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類(lèi)
附錄3 多態(tài)性
參考文獻(xiàn)
索引