內容介紹
本書根據計算機專業“資料庫原理”課程的教學大綱編寫，全書共分10章，分別介紹資料庫的基礎知識、關係資料庫、SQL語言、關係系統及其查詢最佳化、關係數據理論、資料庫設計、資料庫保護、對象關係和面
向對象資料庫系統、分散式資料庫系統以及數據倉庫概述。每章由基本知識點和例題分析組成，前者高度概
括和疏理本章應重點掌握的相關知識；後者則詳盡地解析精選的典型習題。本書將使讀者充分掌握“資料庫
原理”課程求解問題的技巧與方法，深化對基本概念的理解，切實提高分析問題和解決問題的能力。
本書內容豐富，習題覆蓋面廣，不僅可以作為計算機專業本、專科資料庫原理課程的學習參考書，也
是報考計算機專業碩士研究生的考生複習必讀材料（複試），對資料庫原理和套用課程的自學者以及計算
機等級（三級或四級）應試者也頗有助益。
作者介紹
李春葆，1986年7月畢業於華中工學院（現為華中科技大學）計算機軟體專業，1989年7月畢業於中國科學院瀋陽自動化研究所，1989年7月分配到武漢大學計算機系工作至今，2000年評為教授。主要研究方向：數據挖掘和算法設計。先後主持和參加3S系統集成關鍵技術的研究（國家自然科學基金重點科技攻關項目，49631050）、城市地理信息系統標準規範的研究（國家測繪局項目）、湖北省財政廳三查管理信息系統、湖北省財政廳外匯管理信息系統、湖北省財政廳財政監督管理信息系統、武漢英華ERP系統等項目。在武漢大學學報、華中理工大學學報、計算機工程與套用、計算機套用研究等刊物上發表論文40餘篇，在清華大學出版社、人民郵電出版社和機械工業出版社等出版社出版教材和論著60餘本。作品目錄
第1章緒論 11.1知識點1：數據結構的基本概念 1
1.1.1要點歸納 1
1.1.2例題解析 3
1.2知識點2：算法和算法分析 9
1.2.1要點歸納 9
1.2.2例題解析 12
第2章線性表 22
2.1知識點1：線性表的基本概念 22
2.1.1要點歸納 22
2.1.2例題解析 25
2.2知識點2：順序表的算法 29
2.2.1要點歸納 29
2.2.2例題解析 32
2.3知識點3：單鍊表的算法 42
2.3.1要點歸納 42
2.3.2例題解析 46
2.4知識點4：雙鍊表的算法 67
2.4.1要點歸納 67
2.4.2例題解析 71
2.5知識點5：循環鍊表的算法 78
2.5.1要點歸納 78
2.5.2例題解析 81
第3章棧和遞歸 87
3.1知識點1：棧的基本概念 87
3.1.1要點歸納 87
3.1.2例題解析 88
3.2知識點2：順序棧的算法 94
3.2.1要點歸納 94
3.2.2例題解析 103
3.3知識點3：鏈棧的算法 111
3.3.1要點歸納 111
3.3.2例題解析 112
3.4知識點4：遞歸 116
3.4.1要點歸納 116
3.4.2例題解析 124
第4章佇列 142
4.1知識點1：佇列的基本概念 142
4.1.1要點歸納 142
4.1.2例題解析 143
4.2知識點2：順序隊的算法 146
4.2.1要點歸納 146
4.2.2例題解析 150
4.3知識點3：鏈隊的算法 162
4.3.1要點歸納 162
4.3.2例題解析 164
第5章串 171
5.1知識點1：串的基本概念 171
5.1.1要點歸納 171
5.1.2例題解析 172
5.2知識點2：順序串的算法 174
5.2.1要點歸納 174
5.2.2例題解析 176
5.3知識點3：鏈串的算法 179
5.3.1要點歸納 179
5.3.2例題解析 183
5.4知識點4：模式匹配的算法 187
5.4.1要點歸納 187
5.4.2例題解析 194
第6章數組和稀疏矩陣 201
6.1知識點1：數組和特殊矩陣 201
6.1.1要點歸納 201
6.1.2例題解析 203
6.2知識點2：稀疏矩陣 211
6.2.1要點歸納 211
6.2.2例題解析 214
第7章樹和二叉樹 217
7.1知識點1：樹的基本概念 217
7.1.1要點歸納 217
7.1.2例題解析 222
7.2知識點2：二叉樹的基本概念 227
7.2.1要點歸納 227
7.2.2例題解析 233
7.3知識點3：二叉樹的算法 242
7.3.1要點歸納 242
7.3.2例題解析 253
7.4知識點4：線索二叉樹 281
7.4.1要點歸納 281
7.4.2例題解析 285
7.5知識點5：哈夫曼樹 287
7.5.1要點歸納 287
7.5.2例題解析 290
第8章廣義表 293
8.1知識點1：廣義表的基本概念 293
8.1.1要點歸納 293
8.1.2例題解析 295
8.2知識點2：廣義表的算法設計 298
8.2.1要點歸納 298
8.2.2例題解析 301
第9章圖 307
9.1知識點1：圖的基本概念 307
9.1.1要點歸納 307
9.1.2例題解析 312
9.2知識點2：圖的遍歷算法 324
9.2.1要點歸納 324
9.2.2例題解析 326
9.3知識點3：最小生成樹 346
9.3.1要點歸納 346
9.3.2例題解析 350
9.4知識點4：最短路徑 355
9.4.1要點歸納 355
9.4.2例題解析 361
9.5知識點5：AOV網和拓撲排序 366
9.5.1要點歸納 366
9.5.2例題解析 368
9.6知識點6：AOE網與關鍵路徑 370
9.6.1要點歸納 370
9.6.2例題解析 372
第10章查找 377
10.1知識點1：線性表的查找 377
10.1.1要點歸納 377
10.1.2例題解析 382
10.2知識點2：樹表的查找 390
10.2.1要點歸納 390
10.2.2例題解析 399
10.3知識點3：哈希表的查找 419
10.3.1要點歸納 419
10.3.2例題解析 422
第11章內排序 437
11.1知識點1：插入排序算法 437
11.1.1要點歸納 437
11.1.2例題解析 440
11.2知識點2：選擇排序算法 446
11.2.1要點歸納 446
11.2.2例題解析 449
11.3知識點3：交換排序算法 457
11.3.1要點歸納 457
11.3.2例題解析 459
11.4知識點4：歸併排序算法 469
11.4.1要點歸納 469
11.4.2例題解析 470
11.5知識點5：基數排序算法 474
11.5.1要點歸納 474
11.5.2例題解析 475
第12章外排序和檔案 480
12.1知識點1：外排序 480
12.1.1要點歸納 480
12.1.2例題解析 482
12.2知識點2：檔案 486
12.2.1要點歸納 486
12.2.2例題解析 488
附錄A兩份重點大學本科“數據結構”考試試題 494
附錄B2009年～2012年全國計算機專業碩士學位研究生入學考試數據結構部分試題及參考答案 506
參考文獻 528
