內容簡介
《數據結構與算法(C++版)》共分11章，第1章是基礎知識，介紹了基本概念及其術語，並討論了實用程式軟體包；第2章引入線性表；第3章介紹了棧和佇列，用棧實現了表達式求值；第4章介紹串，詳細討論了串的存儲結構與模式匹配算法；第5章介紹數組和廣義表，首次提出了廣義表的使用空間表存儲結構；第6章介紹了樹結構，套用哈夫曼編碼實現了壓縮軟體；第7章介紹圖結構，實現了圖的常用存結構，討論了圖的相關套用，並實現了相應算法；第8章介紹查找，討論了靜態查找表、
數據結構與算法(C++版)動態查找表與散列表，實現了所有算法；第9章介紹排序，以簡潔方式實現各種排序算法；第10章介紹了檔案，討論了各種常用檔案結構；第11章介紹了算法設計技術、分析技術與可計算問題。
通過《數據結構與算法(C++版)》的學習，不但能迅速提高數據結構與算法的水平，同時還能提高C++程式設計的能力，經過適當的選擇，《數據結構與算法(C++版)》能作為高等院校計算機及相關專業“數據結構”、“數據結構與算法”、“數據結構與算法分析”和“數據結構與算法設計”等課程的教材，也可供其他從事軟體開發工作的讀者參考。
目錄
第1章緒論1
1.1數據結構的概念和學習數據結構的必要性1
1.2數據結構的基本概念2
1.2.1數據2
1.2.2數據元素和數據項2
1.2.3數據結構3
1.3抽象數據類型及其實現4
1.3.1數據類型4
1.3.2抽象數據類型4
1.3.3C++程式的典型構架5
1.3.4C++的類和對象6
1.3.5C++的友元函式7
1.3.6運算符重載9
1.3.7C++的參數傳遞12
1.3.8C++的輸入輸出14
1.3.9有關C++的動態存儲分配15
1.3.10結構與類17
1.3.11C++的模板17
1.4算法和算法分析19
1.4.1算法19
1.4.2算法分析20
1.5實用程式軟體包23
1.6實例研究31
1.6.1生命遊戲31
1.6.2計算任意位數的π31
1.7深入學習導讀38
習題138
上機實驗題139
第2章線性表41
2.1線性表的邏輯結構41
2.2線性表的順序存儲結構42
2.3線性表的鏈式存儲結構51
2.3.1單鍊表51
2.3.2循環鍊表59
2.3.3雙向鍊表63
2.3.4在鍊表結構中保存當前位置和元素個數66
2.4實例研究78
2.4.1一元多項式的表示78
2.4.2計算任意大整數的階乘83
2.5深入學習導讀86
習題287
上機實驗題287
第3章棧和佇列88
3.1棧88
3.1.1棧的基本概念88
3.1.2順序棧89
3.1.3鏈式棧94
3.2佇列100
3.2.1佇列的基本概念100
3.2.2鏈佇列102
3.2.3循環佇列——佇列的順序存儲結構106
3.2.4佇列套用——顯示二項式?(a+b)?i?的係數111
3.3優先佇列112
3.4實例研究116
3.4.1表達式求值116
3.4.2事件驅動模擬119
3.5深入學習導讀124
習題3125
上機實驗題3125
第4章串127
4.1串類型的定義127
4.2字元串的實現128
4.3字元串模式匹配算法134
4.3.1簡單字元串模式匹配算法134
4.3.2首尾字元串模式匹配算法136
4.3.3KMP字元串模式匹配算法136
4.4實例研究141
4.4.1文本編輯141
4.4.2查找子序列142
4.5深入學習導讀143
習題4143
上機實驗題4143
第5章數組和廣義表144
5.1數組144
5.1.1數組的基本概念144
5.1.2數組的順序存儲方式144
5.1.3數組的類定義147
5.2矩陣150
5.2.1矩陣的定義和操作150
5.2.2特殊矩陣152
5.2.3稀疏矩陣157
5.3廣義表167
5.3.1基本概念167
5.3.2廣義表的存儲結構169
5.4實例研究179
5.4.1穩定伴侶問題179
5.4.2?m?元多項式的表示179
5.5深入學習導讀182
習題5183
上機實驗題5183
第6章樹和二叉樹184
6.1樹的基本概念184
6.1.1樹的定義184
6.1.2基本術語184
6.2二叉樹186
6.2.1二叉樹的定義186
6.2.2二叉樹的性質188
6.2.3二叉樹的存儲結構190
6.3二叉樹遍歷199
6.3.1遍歷的定義199
6.3.2遍歷算法200
6.3.3二叉樹遍歷套用舉例206
6.4線索二叉樹211
6.4.1線索的概念211
6.4.2線索二叉樹的實現213
6.5樹和森林221
6.5.1樹的存儲表示221
6.5.2樹的顯示228
6.5.3森林的存儲表示228
6.5.4樹和森林的遍歷233
6.5.5樹和森林與二叉樹的轉換235
6.6哈夫曼樹與哈夫曼編碼238
6.6.1哈夫曼樹的基本概念238
6.6.2哈夫曼樹構造算法239
6.6.3哈夫曼編碼239
6.6.4哈夫曼樹的實現241
6.7樹的計數245
6.8實例研究247
6.8.1樹與等價關係247
6.8.2Huffman壓縮算法251
6.9深入學習導讀256
習題6256
上機實驗題6257
第7章圖258
7.1圖的定義和術語258
7.2圖的存儲表示262
7.2.1鄰接矩陣262
7.2.2鄰接表267
7.3圖的遍歷274
7.3.1深度優先搜尋275
7.3.2廣度優先搜尋276
7.4圖的最小代價生成樹277
7.4.1Prim算法278
7.4.2Kruskal算法280
7.5有向無環圖及套用284
7.5.1拓撲排序284
7.5.2關鍵路徑287
7.6最短路徑291
7.6.1單源點最短路徑問題291
7.6.2所有頂點之間的最短路徑294
7.7實例研究296
7.7.1週遊世界問題——哈密爾頓圈296
7.7.2一筆畫問題——歐拉問題298
7.8深入學習導讀299
習題7299
上機實驗題7301
第8章查找302
8.1查找的基本概念302
8.2靜態表的查找305
8.2.1順序查找305
8.2.2有序表的查找306
8.3動態查找表309
8.3.1二叉排序樹309
8.3.2二叉平衡樹319
8.3.3B樹和B?+樹343
8.4散列表345
8.4.1散列表的概念345
8.4.2構造散列函式的方法345
8.4.3處理衝突的方法346
8.4.4散列表的實現347
8.5實例研究352
8.5.1查找3個數組的最小共同元素352
8.5.2查找最小元素353
8.6深入學習導讀354
習題8354
上機實驗題8355
第9章排序356
9.1概述356
9.2插入排序357
9.2.1直接插入排序357
9.2.2Shell排序358
9.3交換排序360
9.3.1起泡排序360
9.3.2快速排序361
9.4選擇排序364
9.4.1簡單選擇排序364
9.4.2堆排序365
9.5歸併排序368
9.6基數排序373
9.6.1多關鍵排序373
9.6.2基數排序373
9.7各種內部排序方法討論376
9.8外部排序378
9.8.1外部排序基礎378
9.8.2外部排序的方法378
9.9實例研究380
9.9.1宴會中來賓數目的最大值380
9.9.2各種排序算法運行時間測試382
9.9.3用堆實現優先佇列385
9.10深入學習導讀388
習題9388
上機實驗題9389
第10章檔案390
10.1主存儲器和輔助存儲器390
10.2各種常用檔案結構390
10.2.1順序檔案390
10.2.2索引檔案391
10.2.3散列檔案392
10.3實例研究392
10.3.1VSAM檔案392
10.3.2多關鍵字檔案393
10.4深入學習導讀395
習題10395
上機實驗題10395
第11章算法設計與分析397
11.1算法設計397
11.1.1遞歸算法397
11.1.2分治算法401
11.1.3動態規划算法407
11.1.4貪心算法422
11.1.5回溯算法425
11.1.6分支限界法430
11.2算法分析440
11.2.1遞歸分析440
11.2.2利用生成函式進行分析443
11.3可計算性問題445
11.3.1歸約445
11.3.2難解問題、N問題、NP問題和NP完全性問題446
11.3.3不可程式問題447
11.4實例研究449
11.4.1圖著色問題449
11.4.2多邊形遊戲451
11.5深入學習導讀455
習題11456
上機實驗題11456
附錄A調和級數458
附錄B泊松分布459
附錄C配套的軟體包460
附錄D課程設計項目466
附錄E實驗報告格式471
附錄F課程設計報告格式472
參考文獻473
……
