數(shù)據(jù)結構與算法設計

第1章  結論                  
     1. 1　問題求解                  
     1. 2　算法表達中的抽象機制                  
     1. 3　抽象數(shù)據(jù)類型                  
         1. 3. 1　抽象數(shù)據(jù)類型的基本概念                  
         1. 3. 2　使用抽象數(shù)據(jù)類型的好處                  
         1. 3. 3　數(shù)據(jù)結構. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型                  
     1. 4　用C＋＋描述數(shù)據(jù)結構與算法                  
         1. 4. 1　變量. 指針和引用                  
         1. 4. 2　函數(shù)與參數(shù)傳遞                  
         1. 4. 3　C＋＋的類                  
         1. 4. 4　類的對象                  
         1. 4. 5　構造函數(shù)與橋構函數(shù)                  
         1. 4. 6　運算符重載                  
         1. 4. 7　友元函數(shù)                  
         1. 4. 8　內聯(lián)函數(shù)                  
         1. 4. 9　結構                  
         1. 4. 10  聯(lián)合                  
         1. 4. 11　異常                  
         1. 4. 12　模板                  
         1. 4. 13　動態(tài)存儲分配                  
     1. 5　算法復雜性分析                  
         1. 5. 1　算法與程序                  
         1. 5. 2　算法復雜性的概念                  
         1. 5. 3　算法復雜性的漸近性態(tài)                  
     習題一                  
 第2章　表                  
     2. 1　ADT表                  
     2. 2　用數(shù)組實現(xiàn)表                  
     2. 3　用指針實現(xiàn)表                  
     2. 4　用間接尋址方法實現(xiàn)表                  
     2. 5　用游標實現(xiàn)表                  
     2. 6　循環(huán)鏈表                  
     2. 7　雙鏈表                  
     習題二                  
 第3章　棧                  
     3. 1  ADT棧                  
     3. 2  用數(shù)組實現(xiàn)棧                  
     3. 3　用指針實現(xiàn)棧                  
     3. 4　等價類劃分問題                  
     習題三                  
 第4章　隊列                  
     4. 1  ADT隊列                  
     4. 2　用指針實現(xiàn)隊列                  
     4. 3　用循環(huán)數(shù)組實現(xiàn)隊列                  
     4. 4　電路布線問題                  
     習題四                  
 第5章  串                  
     5. 1  ADT串                  
 　  5. 2　用數(shù)組實現(xiàn)串                  
   　5. 3　用指針實現(xiàn)串                  
 　  5. 4　串的塊鏈表示法                  
   　5. 5　串的堆結構                  
   　5. 6　模式匹配                  
 　      5. 6. 1　樸素的模式匹配算法                  
   　    5. 6. 2　模式匹配的KMP算法                  
   　習題五                  
 第6章　排序與選擇                  
 　  6. 1　簡單排序算法                  
   　    6. 1. 1　冒泡排序                  
     　  6. 1. 2　插入排序                  
       　6. 1. 3　選擇排序                  
 　      6. 1. 4　簡單排序算法的計算復雜性                  
   　6. 2　快速排序算法                  
     　  6. 2. 1  算法基本思想及實現(xiàn)                  
       　6. 2. 2　算法的性能                  
 　      6. 2. 3　隨機快速排序算法                  
   　6. 3　合并排序算法                  
     　  6. 3. 1　算法基本思想及實現(xiàn)                  
       　6. 3. 2　消除遞歸                  
 　      6. 3. 3　自然合并排序                  
   　6. 4　線性時間排序算法                  
     　  6. 4. 1  計數(shù)排序                  
       　6. 4. 2　桶排序                  
 　  6. 5　中位數(shù)與第是小元素                  
   　    6. 5. 1　平均情況下的線性時間選擇算法                  
     　  6. 5. 2　最壞情況下的線性時間選擇算法                  
 　  習題六                  
 第7章　樹                  
 　  7. 1　樹的定義                  
     7. 2　樹的遍歷                  
     7. 3　樹的表示法                  
         7. 3. 1　父結點數(shù)組表示法                  
         7. 3. 2　兒子鏈表表示法                  
         7. 3. 3　在兒子右兄弟表示法                  
     7. 4  二叉樹                  
     7. 5  ADT二叉樹                  
     7. 6　二叉樹的實現(xiàn)                  
         7. 6. 1　二叉樹的順序存儲結構                  
         7. 6. 2　二叉樹的結點度表示法                  
         7. 6. 3　用指針實現(xiàn)二叉樹                  
     7. 7  線索二叉樹                  
     習題七                  
 第8章  圖                  
     8. 1　圖的基本概念                  
     8. 2　抽象數(shù)據(jù)類型ADT圖                  
     8. 3　圖的表示法                  
         8. 3. 1　鄰接矩陣表示法                  
         8. 3. 2　鄰接表表示法                  
         8. 3. 3　緊縮鄰接表                  
     8. 4　用鄰接矩陣實現(xiàn)圖                  
         8. 4. 1　用鄰接矩陣實現(xiàn)賦權有向圖                  
         8. 4. 2　用鄰接矩陣實現(xiàn)賦權無向圖                  
         8. 4. 3　用鄰接矩陣實現(xiàn)有向圖                  
         8. 4. 4　用鄰接矩陣實現(xiàn)無向圖                  
     8. 5　用鄰接表實現(xiàn)圖                  
         8. 5. 1　鄰接表基類                  
         8. 5. 2　用鄰接表實現(xiàn)有向圖                  
         8. 5. 3　用鄰接表實現(xiàn)無向圖                  
         8. 5. 4　用鄰接表實現(xiàn)賦權有向圖                  
         8. 5. 5　用鄰接表實現(xiàn)賦權無向圖                  
     8. 6　圖的退伍                  
         8. 6. 1　圖的搜索游標                  
         8. 6. 2　廣度優(yōu)先搜索                  
         8. 6. 3　深度優(yōu)先搜索                  
     8. 7　最短路徑                  
         8. 7. 1　單源最短路徑                  
         8. 7. 2　所有頂點對之間的最短路徑                  
     8. 8　最小生成樹                  
         8. 8. 1  最小生成樹性質                  
         8. 8. 2  Prim算法                  
         8. 8. 3  Kruskal算法                  
     8. 9　圖匹配                  
     習題八                  
 第9章　集合                  
     9. 1　以集合為基礎的抽象數(shù)據(jù)類型                  
         9. 1. 1　集合的定義和記號                  
         9. 1. 2　定義在集合上的基本運算                  
         9. 1. 3　集合的簡單表示法                  
     9. 2　字典                  
         9. 2. 1　實現(xiàn)字典的簡單方法                  
         9. 2. 2　用散列表實現(xiàn)字典                  
     9. 3　有序字典                  
         9. 3. 1　有序字典的定義                  
         9. 3. 2　用數(shù)組實現(xiàn)有序字典                  
         9. 3. 3　用二叉搜索樹實現(xiàn)有序字典                  
         9. 3. 4　AVL樹                  
         9. 3. 5　紅黑樹                  
     9. 4　優(yōu)先隊列                  
         9. 4. 1  優(yōu)先隊列的定義                  
         9. 4. 2　用字典實現(xiàn)代先隊列                  
         9. 4. 3　優(yōu)先級樹和堆                  
         9. 4. 4　用數(shù)組實現(xiàn)推                  
         9. 4. 5　可并優(yōu)先隊列                  
     9. 5　并查集                  
         9. 5. 1　并查集的定義及其簡單實現(xiàn)                  
         9. 5. 2　用父親數(shù)組實現(xiàn)并查集                  
     習題九                  
 第10章　算法設計策略                  
     10. 1　遞歸與分治策略                  
         10. 1. 1　遞歸的概念                  
         10. 1. 2　分治法的基本思想                  
         10. 1. 3　二分搜索技術                  
         10. 1. 4　棋盤覆蓋問題                  
     10. 2　動態(tài)規(guī)劃                  
         10. 2. 1　矩陣連乘問題                  
         10. 2. 2　動態(tài)規(guī)劃算法的基本要素                  
         10. 2. 3　最大子段和問題                  
     10. 3　貪心算法                  
         10. 3. 1　活動安排問題                  
         10. 3. 2　貪心算法的基本要素                  
         10. 3. 3　哈夫曼編碼算法                  
     10. 4　回溯法                  
         10. 4. 1　回溯法的算法框架                  
         10. 4. 2　符號三角形問題                  
         10. 4. 3　圓排列問題                  
         10. 4. 4　連續(xù)郵資問題                  
         10. 4. 5　回溯法的效率分析                  
     10. 5　分支限界法                  
         10. 5. 1　分支限界法的基本思想                  
         10. 5. 2　裝載問題                  
         10. 5. 3　批處理作業(yè)調度問題                  
     習題十                  
 參考文獻