數(shù)據(jù)結(jié)構(gòu)與算法：面向?qū)ο蟮腃++設(shè)計模式

第1章  概要                  
 1. 1  本書的主要內(nèi)容                  
 1. 2  面向?qū)ο蟮脑O(shè)計                  
 1. 3  對象分級與設(shè)計方法                  
 1. 4  需要了解的C++特性                  
 1. 5  本書是如何組織的？                  
 第2章  算法分析                  
 2. 1  一個細(xì)化的計算機模型                  
 2. 1. 1  基本公理                  
 2. 1. 2  例豆：算術(shù)級數(shù)求和                  
 2. 1. 3  數(shù)組下標(biāo)操作                  
 2. 1. 4  例2：霍納（Horner）法則                  
 2. 1. 5  分析遞歸函數(shù)                  
 2. 1. 6  例3：找出數(shù)組中最大元素                  
 2. 1. 7  平均運行時間                  
 2. 1. 8  關(guān)于調(diào)和數(shù)                  
 2. 1. 9  最佳情況與最差情況的運行時間                  
 2. 1. 10  最后的公理                  
 2. 2  一個簡化的計算機模型                  
 2. 2. 1  例l, 求幾何級數(shù)之和                  
 2. 2. 2  關(guān)于算術(shù)級數(shù)求和                  
 2. 2. 3  例2：再次求幾何級數(shù)之和                  
 2. 2. 4  關(guān)于幾何級數(shù)求和                  
 2. 2. 5  例3：冪計算                  
 2. 2. 6  例4：再三求幾何級數(shù)之和                  
 習(xí)題                  
 設(shè)計項目                  
 第3章  漸近表示法                  
 3. 1  漸近上界--大O表示法                  
 3. 1. 1  一個簡單的例子                  
 3. 1. 2  大O表示法中的錯誤與陷阱                  
 3. 1. 3  大O的特性                  
 3. 1. 4  多項式                  
 3. 1. 5  對數(shù)                  
 3. 1. 6  緊湊大O界                  
 3. 1. 7  大O表示法中更多的錯誤與陷阱                  
 3. 1. 8  常用的大O表達(dá)式                  
 3. 2  漸近下界--Ω表示法                  
 3. 2. 1  一個簡單的例子                  
 3. 2. 2  再次關(guān)于多項式                  
 3. 3  更多的表示法--θ及小o表示法                  
 3. 4  算法漸近分析                  
 3. 4. 1  運行時間分析的大O規(guī)則                  
 3. 4. 2  例1：求級數(shù)的前項和                  
 3. 4. 3  例2：Fibonacci數(shù)                  
 3. 4. 4  例3：桶式排序                  
 3. 4. 5  現(xiàn)實檢查                  
 3. 4. 6  檢查你的分析                  
 習(xí)題                  
 設(shè)計項目                  
 第4章  基本數(shù)據(jù)結(jié)構(gòu)                  
 4. 1  動態(tài)數(shù)組                  
 4. 1. 1  缺省構(gòu)造函數(shù)                  
 4. 1. 2  數(shù)組構(gòu)造函數(shù)                  
 4. 1. 3  備份構(gòu)造函數(shù)                  
 4. 1. 4  析構(gòu)函數(shù)                  
 4. 1. 5  數(shù)組成員函數(shù)                  
 4. 1. 6  數(shù)組下標(biāo)操作符                  
 4. l. 7  數(shù)組大小的重調(diào)                  
 4. 2  單鏈表                  
 4. 2. 1  鏈表的實現(xiàn)                  
 4. 2. 2  鏈表元素                  
 4. 2. 3  缺省構(gòu)造函數(shù)                  
 4. 2. 4  析構(gòu)函數(shù)與Purge成員函數(shù)                  
 4. 2. 5  存取器                  
 4. 2. 6  First與Last函數(shù)                  
 4. 2. 7  前插                  
 4. 2. 8  添加                  
 4. 2. 9  備份構(gòu)造函數(shù)與賦值操作符                  
 4. 2. 10  析取函數(shù)                  
 4. 2. 11  InsertAfter與InsertBefore函數(shù)                  
 4. 3  多維數(shù)組                  
 4. 3. 1  數(shù)組下標(biāo)計算                  
 4. 3. 2  二維數(shù)組的實現(xiàn)                  
 4. 3. 3  C＋十中多維數(shù)組的下標(biāo)                  
 4. 3. 4  例：規(guī)范矩陣相乘                  
 習(xí)題                  
 設(shè)計項目                  
 第5章  數(shù)據(jù)類型與抽象                  
 5. 1  抽象數(shù)據(jù)類型                  
 5. 2  設(shè)計模式                  
 5. 2. 1  類層次                  
 5. 2. 2  對象                  
 5. 2. 3  NullObject單元集類                  
 5. 2. 4  內(nèi)嵌類型的對象包裝                  
 5. 2. 5  容器                  
 5. 2. 6  訪問者                  
 5. 2. 7  迭代器                  
 5. 2. 8  NullIterator類                  
 5. 2. 9  直接存儲與間接存儲                  
 5. 2. 10  被包含對象的所有權(quán)                  
 5. 2. 11  關(guān)聯(lián)                  
 5. 2. 12  可搜索容器                  
 習(xí)題                  
 設(shè)計項目                  
 第6章  棧. 隊列及雙端隊列                  
 6. 1  棧                  
 6. 1. 1  棧的數(shù)組表示法                  
 6. 1. 2  棧的鏈表表示法                  
 6. 1. 3  應(yīng)用                  
 6. 2  隊列                  
 6. 2. 1  隊列的數(shù)組表示法                  
 6. 2. 2  隊列的鏈表表示法                  
 6. 2. 3  應(yīng)用                  
 6. 3  雙端隊列                  
 6. 3. l  雙端隊列的數(shù)組表示法                  
 6. 3. 2  雙端隊列的鏈表表示法                  
 6. 3. 3  雙向鏈表及循環(huán)鏈表                  
 習(xí)題                  
 設(shè)計項目                  
 第7章  有序線性表與排序表                  
 7. 1  有序線性表                  
 7. 1. 1  有序線性表的數(shù)組表示法                  
 7. 1. 2  有序線性表的鏈表表示法                  
 7. 1. 3  比較ListAsArray和ListAsLinkedList                  
 7. 1. 4  應(yīng)用                  
 7. 2  排序表                  
 7. 2. 1  排序表的數(shù)組表示法                  
 7. 2. 2  排序表的鏈表表示法                  
 7. 2. 3  比較SortedListAsArrny和SortedListAsLinkedList                  
 7. 2. 4  應(yīng)用                  
 習(xí)題                  
 設(shè)計項目                  
 第8章  散列. 哈希表及分散表                  
 8. 1  散列的基本知識                  
 8. 1. 1  關(guān)鍵字和散列函數(shù)                  
 8. 2  散列法                  
 8. 2. 1  相除散列法                  
 8. 2. 2  平方取中散列法                  
 8. 2. 3  相乘散列法                  
 8. 2. 4  Fibonacci散列法                  
 8. 3  散列函數(shù)的實現(xiàn)                  
 8. 3. 1  整型關(guān)鍵字                  
 8. 3. 2  浮點型關(guān)鍵字                  
 8. 3. 3  字符串關(guān)鍵字                  
 8. 3. 4  散列對象                  
 8. 3. 5  散列容器                  
 8. 3. 6  使用關(guān)聯(lián)                  
 8. 4  哈希表                  
 8. 4. 1  拉鏈法                  
 8. 4. 2  平均情況分析                  
 8. 5  分散表                  
 8. 5. 1  鏈?zhǔn)椒稚⒈?nbsp;                 
 8. 5. 2  平均情況分析                  
 8. 6  使用開地址法的分散表                  
 8. 6. 1  線性探查                  
 8. 6. 2  二次探查                  
 8. 6. 3  雙散列法                  
 8. 6. 4  開地址法的實現(xiàn)                  
 8. 6. 5  平均情況分析                  
 8. 7  應(yīng)用                  
 習(xí)題                  
 設(shè)計項目                  
 第9章  樹                  
 9. 1  基礎(chǔ)                  
 9. 2  N叉樹                  
 9. 3  二叉樹                  
 9. 4  樹的遍歷                  
 9. 5  表達(dá)式樹                  
 9. 6  樹的實現(xiàn)                  
 9. 6. 1  樹的遍歷                  
 9. 6. 2  樹迭代器                  
 9. 6. 3  廣義樹                  
 9. 6. 4  N叉樹                  
 9. 6. 5  二叉樹                  
 9. 6. 6  二叉樹的遍歷                  
 9. 6. 7  樹的比較                  
 9. 6. 8  應(yīng)用                  
 習(xí)題                  
 設(shè)計項目                  
 第10章  查找樹                  
 10. 1  基礎(chǔ)知識                  
 10. 1. 1  M路查找樹                  
 10. 1. 2  二叉查找樹                  
 10. 2  搜索查找樹                  
 10. 2. 1  搜索M路查找樹                  
 1O. 2. 2  搜索二叉樹                  
 10. 3  平均情況分析                  
 10. 3. 1  搜索成功                  
 10. 3. 2  遞歸關(guān)系的求解--拓展速歸法                  
 10. 3. 3  搜索失敗                  
 10. 3. 4  查找樹的遍歷                  
 10. 4  查找樹的實現(xiàn)                  
 10. 4. 1  二叉查找樹                  
 10. 4. 2  在二叉查找樹中插入數(shù)據(jù)項                  
 10. 4. 3  從二叉查找樹中刪除數(shù)據(jù)項                  
 10. 5  AVL查找樹                  
 10. 5. 1  AVL樹的實現(xiàn)                  
 10. 5. 2  在AVL樹中插人數(shù)據(jù)項                  
 10. 5. 3  從AVL樹中刪除數(shù)據(jù)項                  
 10. 6  M路查找樹                  
 10. 6. 1  M路查找樹的實現(xiàn)                  
 10. 6. 2  在M路查找樹中查找數(shù)據(jù)項                  
 10. 6. 3  在M路查找樹中插人數(shù)據(jù)項                  
 10. 6. 4  從M路查找樹中刪除數(shù)據(jù)項                  
 10. 7  B樹                  
 10. 7. 1  B樹的實現(xiàn)                  
 10. 7. 2  在B樹中插人數(shù)據(jù)項                  
 10. 7. 3  從B樹中刪除數(shù)據(jù)項                  
 10. 8  應(yīng)用                  
 習(xí)題                  
 設(shè)計項目                  
 第11章  堆和優(yōu)先隊列                  
 11. 1  基礎(chǔ)知識                  
 11. 2  二叉堆                  
 11. 2. 1  完全樹                  
 11. 2. 2  二叉堆的實現(xiàn)                  
 11. 2. 3  在二叉堆中插入數(shù)據(jù)項                  
 11. 2. 4  從二叉堆中刪除數(shù)據(jù)項                  
 11. 3  左翼堆                  
 11. 3. 1  左翼樹                  
 11. 3. 2  左翼堆的實現(xiàn)                  
 11. 3. 3  左翼堆的合并                  
 11. 3. 4  在左翼堆中插入數(shù)據(jù)項                  
 11. 3. 5  從左翼堆中刪除數(shù)據(jù)項                  
 11. 4  二項隊列                  
 11. 4. 1  二項樹                  
 11. 4. 2  二項隊列                  
 11. 4. 3  實現(xiàn)                  
 11. 4. 4  二項隊列的合并                  
 11. 4. 5  在二項隊列中插入數(shù)據(jù)項                  
 11. 4. 6  從二項隊列中刪除數(shù)據(jù)項                  
 11. 5  應(yīng)用                  
 11. 5. 1  離散事件模擬                  
 11. 5. 2  實現(xiàn)                  
 習(xí)題                  
 設(shè)計項目                  
 第12章  集合. 多重集和分區(qū)                  
 12. 1  基礎(chǔ)知識                  
 12. 1. 1  集合的實現(xiàn)                  
 12. 2  數(shù)組和位矢量集合                  
 12. 2. 1  位矢量集合                  
 12. 3  多重集                  
 12. 3. 1  多重集的數(shù)組表示法                  
 12. 3. 2  多重集的鏈表表示法                  
 12. 4  分區(qū)                  
 12. 4. 1  用森林表示分區(qū)                  
 12. 4. 2  折疊查找                  
 12. 4. 3  按大小合并                  
 12. 4. 4  按高度或?qū)犹柡喜?nbsp;                 
 12. 5  應(yīng)用                  
 習(xí)題                  
 設(shè)計項目                  
 第13章  動態(tài)存儲分配：另一種堆                  
 13. 1  基礎(chǔ)                  
 13. 1. 1  C++ Magic                  
 13. 1. 2  堆                  
 13. 2  單鏈自由存儲器                  
 13. 2. 1  實現(xiàn)                  
 13. 3  雙鏈自由存儲器                  
 13. 3. 1  實現(xiàn)                  
 13. 4  伙伴存儲管理系統(tǒng)                  
 13. 4. 1  實現(xiàn)                  
 13. 5  應(yīng)用                  
 13. 5. 1  實現(xiàn)                  
 習(xí)題                  
 設(shè)計項目                  
 第14章  算法模式和問題求解                  
 14. 1  蠻干算法和貪心算法                  
 14. 1. 1  例1：數(shù)錢                  
 14. 1. 2  例2：0／l背包問題                  
 14. 2  回溯算法                  
 14. 2. 1  例1：平衡稱                  
 14. 2. 2  解空間的表示                  
 14. 2. 3  抽象回溯求解程序                  
 14. 2. 4  分支界限求解程序                  
 14. 2. 5  例2：再次分析0/1背包問題                  
 14. 3  自頂向下算法：分治算法                  
 14. 3. 1  例1：二分法查找                  
 14. 3. 2  例2：求解Fibonacci數(shù)                  
 14. 3. 3  例3：歸并排序                  
 14. 3. 4  分治算法的運行時間                  
 14. 3. 5  例個矩陣相乘                  
 14. 4  自底向上算法：動態(tài)程序設(shè)計                  
 14. 4. 1  例1：廣義Fibonacci數(shù)                  
 14. 4. 2  例2：求解二項式系數(shù)                  
 14. 4. 3  應(yīng)用：排版問題                  
 14. 5  隨機化算法                  
 14. 5. 1  產(chǎn)生隨機數(shù)                  
 14. 5. 2  隨機變量                  
 14. 5. 3  蒙特卡羅法                  
 14. 5. 4  模擬退火法                  
 習(xí)題                  
 設(shè)計項目                  
 第15章  排序算法和排序器                  
 15. 1  基礎(chǔ)知識                  
 15. 2  排序和排序器                  
 15. 3  插入排序                  
 15. 3. 1  直接插入排序                  
 15. 3. 2  平均運行時間                  
 15. 3. 3  二分法插入排序                  
 15. 4  交換排序                  
 15. 4. 1  冒泡排序                  
 15. 4. 2  快速排序                  
 15. 4. 3  運行時間分析                  
 15. 4. 4  平均運行時間                  
 15. 4. 5  軸值的選擇                  
 15. 5  選擇排序                  
 15. 5. 1  直接選擇排序                  
 15. 5. 2  堆排序                  
 15. 5. 3  堆的建立                  
 15. 6  歸并排序                  
 15. 7  排序算法的下界                  
 15. 8  分配排序                  
 15. 8. 1  桶式排序                  
 15. 8. 2  基數(shù)排序                  
 15. 9  算法性能分析                  
 習(xí)題                  
 設(shè)計項目                  
 第16章  圖和圖算法                  
 16. 1  基礎(chǔ)知道                  
 16. 1. 1  圖的表示法                  
 16. 2  圖的實現(xiàn)                  
 16. 2. 1  頂點的實現(xiàn)                  
 16. 2. 3  抽象圖和有向圖                  
 16. 2. 4  無向圖的實現(xiàn)                  
 16. 2. 5  邊帶權(quán)圖和頂點帶權(quán)圖                  
 16. 2. 6  圖表示法的比較                  
 16. 3  圖的遍歷                  
 16. 3. 1  深度優(yōu)先遍歷                  
 16. 3. 2  廣度優(yōu)先遍歷                  
 16. 3. 3  拓?fù)渑判?nbsp;                 
 16. 3. 4  圖遍歷的應(yīng)用：檢查圖的回路及連通性                  
 16. 4  最短路徑算法                  
 16. 4. 1  單源最短路徑                  
 16. 4. 2  每對頂點間的最短路徑                  
 16. 5  最小支撐樹                  
 16. 5. 1  Prim算法                  
 16. 5. 2  Kruskal算法                  
 16. 6  應(yīng)用：關(guān)鍵路徑分析                  
 習(xí)題                  
 設(shè)計項目                  
 附錄A  C++與面向?qū)ο缶幊?nbsp;                 
 附錄B  類層次圖                  
 附錄C  字符碼                  
 參考答案