數據結構與算法分析

前言                  
   第一部分  預備知識                  
   第1章  數據結構和算法                  
     1. 1  數據結構的原則                  
     1. 1. 1  學習數據結構的必要性                  
     1. 1. 2  代價與效益                  
     1, 1. 3  本書的日的                  
     1. 2  抽象數據類型和數據結構                  
     l. 3  問題. 算法和程序                  
     1. 4  算法的效率                  
     1. 5  深入學習導讀                  
     1. 6  習題                  
   第2章  數學預備知識                  
     2. 1  集合                  
     2. 2  常用數學術語                  
     2. 3  對數                  
     2. 4  遞歸                  
     2. 5  級數求和與遞歸                  
     2. 6  數學證明方法                  
     2. 6. 1  反證法                  
     2. 6. 2  數學歸納法                  
     2. 7  評估                  
     2. 8  深入學習導讀                  
     2. 9  習題                  
   第3章  算法分析                  
     3. 1  概述                  
     3. 2  最佳. 最差和平均情況                  
     3. 3  換一臺更快的計算機, 還是換一種更快的算法?                  
     3. 4  漸近分析                  
     3. 4. 1  上限                  
     3. 4. 2  廠限                  
     3. 4. 3  表示法                  
     3. 4. 4  簡化法則                  
     3. 5  程序運行時間的計算                  
     3. 6  問題的分析                  
     3. 7  多參數問題                  
     3. 8  空間代價                  
     3. 9  實際操作中的一些因素                  
     3. 10  深入學習導讀                  
     3. 11  習題                  
     3. 12  項目設計                  
   第二部分  基本數據結構                  
   第4章  線性表. 棧和隊列                  
     4. 1  線性表                  
     4. 1. 1  順序表的表示法                  
     4. 1. 2  鏈表                  
     4. 1. 3  線性表實現方法的比較                  
     4. 1. 4  元素的表示                  
     4. 1. 5  雙鏈表                  
     4. 1. 6  循環(huán)鏈表                  
     4. 2  棧                  
     4. 2. 1  順序棧                  
     4. 2. 2  鏈式棧                  
     4. 2. 3  順序棧與鏈式棧的比較                  
     4. 2. 4  遞歸的實現                  
     4. 3  隊列                  
     4. 3. 1  順序隊列                  
     4. 3. 2  鏈式隊列                  
     4. 2. 3  順序隊列與鏈式隊列的比較                  
     4. 4  習題                  
     4. 5  項目設計                  
   第5章  二叉樹                  
     5. 1  定義及主要特性                  
     5. 1. 1  滿二叉樹定理                  
     5. 1. 2  二叉樹結點的抽象數據類型                  
     5. 2  周游二叉樹                  
     5. 3  二叉樹的實現                  
     5. 3. 1  使用指針實現二叉樹                  
     5. 3. 2  空間開銷                  
     5. 3. 3  使用數組實現完全二叉樹                  
     5. 4  Huffman編碼樹                  
     5. 4. 1  建立Huffman編碼樹                  
     5. 4. 2  Huffman編碼及其用法                  
     5. 5  二叉檢索樹                  
     5. 6  堆與優(yōu)先隊列                  
     5. 7  深入學習導讀                  
     5. 8  習題                  
     5. 9  項目設計                  
   第6章  樹                  
     6. 1  樹的定義與術語                  
     6. 1. 1  樹結點的抽象數據類型                  
     6. 1. 2  樹的周游                  
     6. 2  父指針表示法                  
     6. 3  樹的實現                  
     6. 3. 1  子結點表表示法                  
     6. 3. 2  左子結點／右兄弟結點表示法                  
     6. 3. 3  動態(tài)結點表示法                  
     6. 3. 4  動態(tài)“左子結點／右兄弟結點”表示法                  
     6. 4  K叉樹                  
     6. 5  樹的順序表示法                  
     6. 6  深入學習導讀                  
     6. 7  習題                  
     6. 8  項目設計                  
   第7章  圖                  
     7. 1  術語和表示法                  
     7. 2  圖的實現                  
     7. 3  圖的周游                  
     7. 3. 1  深度優(yōu)先搜索                  
     7. 3. 2  廣度優(yōu)先搜索                  
     7. 3. 3  拓撲排序                  
     7. 4  最短路徑問題                  
     7. 4. 1  單源最短路徑                  
     7. 4. 2  每對頂點間的最短路徑                  
     7. 5  最小支撐樹                  
     7. 5. 1  Prim算泌                  
     7. 5. 2  Kruskal算法                  
     7. 6  深入學習導讀                  
     7. 7  習題                  
     7. 8  項目設計                  
   第三部分  排序和檢索                  
   第8章  內排序                  
     8. 1  排序的術語及記號                  
     8. 2  三種代價為(n)的排序算法                  
     8. 2. 1  插入排序                  
     8. 2. 2  起泡排序                  
     8. 2. 3  選擇排序                  
     8. 2. 4  交換排序算法的時間代價                  
     8. 3  Shell排序                  
     8. 4  快速排序                  
     8. 5  歸并排序                  
     8. 6  堆排序                  
     8. 7  分配排序和基數排序                  
     8. 8  對各種排序算法的實驗比較                  
     8. 9  排序算法的下限                  
     8. 10  深入學習導讀                  
     8. 11  習題                  
     8. 12  項目設計                  
   第9章  文件管理和外排序                  
     9. 1  主存儲器和輔助存儲器                  
     9. 2  磁盤和磁帶                  
     9. 2. 1  磁盤訪問開銷                  
     9. 2. 2  磁帶                  
     9. 3  緩沖區(qū)和緩沖池                  
     9. 4  程序員的文件視圖                  
     9. 5  外排序                  
     9. 6  外排序的簡單方法                  
     9. 7  置換選擇排序                  
     9. 8  多路歸并                  
     9. 9  深入學習導讀                  
     9. 10  習題                  
     9. 11  項目設計                  
   第10章  檢索                  
     10. 1  檢索已排序的數組                  
     l0. 2  自組織線性表                  
     l0. 3  集合的檢索                  
     10. 4  散列方法                  
     l0. 4. 1  散列函數                  
     10. 4. 2  開散列方法                  
     10. 4. 3  閉散列方法                  
     10. 5  深入學習導讀                  
     10. 6  習題                  
     10. 7  項日設計                  
   第ll章  索引技術                  
     11. 1  線性索引                  
     11. 2  ISAM                  
     11. 3  樹形索引                  
     11. 4  2—3樹                  
     11. 5  B樹                  
     11. 5. 1  B村                  
     11. 5. 2  B樹分析                  
     11. 6  深入學習導讀                  
     11. 7  習題                  
     11. 8  2  項目設計                  
   第四部分  應用與高級技術                  
   第12章  線性表和數組的深入研究                  
     12. 1  跳躍表                  
     12. 2  廣義表                  
     12. 3  矩陣的表示方法                  
     12. 4  存儲管理                  
     12. 4. 1  動態(tài)存儲分配                  
     12. 4. 2  失敗策略和無用單元收集                  
     12. 5  深入學習導讀                  
     12. 6  習題                  
     12. 7  項目設計                  
   第13章  高級樹結構                  
     13. 1  Trie結構                  
     13. 2  伸展樹                  
     13. 3  空間數據結構                  
     13. 3. 1  k—d樹                  
     13. 3. 2  PR四分樹                  
     t3. 3. 3  其他空間數據結構                  
     13. 4  深入學習導讀                  
     13. 5  習題                  
     13. 6  項目設計                  
     第14章  算法分析技術                  
     14. 1  求和技術                  
     14. 2  遞歸關系                  
     14. 2. 1  估計上下限                  
     14. 2. 2  擴展遞歸                  
     14. 2. 3  分治法遞歸                  
     14. 2. 4  快速排序平均情況分析                  
     14. 3  緩沖分析                  
     14. 4  深入學習導讀                  
     14. 5  習題                  
     14. 6  項目設計                  
   第15章  計算的限制                  
     15. 1  概述                  
     15. 2  歸約                  
     15. 3  難解問題                  
     15. 3. 1  NP完全性                  
     15. 3. 2  繞過NP完全性問題                  
     15. 4  不可解問題                  
     15. 4. 1  不可數性                  
     15. 4. 2  停機問題的不可解性                  
     15. 4. 3  確定程序行為是不可解的                  
     15. 5  深入學習導讀                  
     15. 6  習題                  
     15. 7  項目設計                  
   附錄A  C和Pascal程序員的C十十導引                  
     A. 1  例1：線性表的ADT                  
     A. 2  例2：順序表的實現                  
     A. 3  例3：鏈表的實現                  
     A. 4  例4：可利用空間表                  
     A. 5  例5：轉化為模板                  
     A. 6  例6：虛函數                  
   附錄B  參考書目