內 容 簡介數據結構是計算機專業的基礎和核心課程。本書內容全面，語言通俗易懂，案例典型、豐富，結構清晰，重點難點突出，所有算法都有完整程序，能直接運行。本書內容包括數據結構概述、常用的C程序開發環境、線性表、棧、隊列、串、數組、廣義表、樹、圖、查找、排序。本書可作為從事計算機軟件開發、準備考取計算機專業研究生和參加軟考的人員學習數據結構與算法的參考書，也可以作為計算機及相關專業的數據結構課程教材。前 言
數據結構是計算機專業基礎課，在所有計算機課程中占據舉足輕重的地位，也是一門不太容易掌握的課程。但是，不要因此而氣餒，本書將采用通俗的語言，教你掌握好數據結構的相關知識。
如果你的學習目的是將來成為一名優秀的程序員，向微軟、谷歌、百度的工程師們看齊，那么你應該努力學好數據結構知識，不僅要看懂書中的程序和算法，還要完成課后的習題，并上機實踐。
如果你的學習目的是為了考取計算機專業的研究生，數據結構作為計算機專業考研的重頭戲，也是今后繼續深造的必備基礎，你需要認真研讀這本書，真正領會每一個算法思想，做到給出任何一個題目，都能自己動手寫出算法。
當然，如果你僅僅是為了混學分，順利通過考試，那么也需要認真看完這本書，這本書可以作為你學習遇到困難時的參考書，方便隨時查閱，可在本書中找到你需要的答案。
在寫作本書之前，我曾寫過幾本關于數據結構方面的著作，得到了一些讀者的厚愛，收到了熱心讀者的來信，他們提出了寶貴的建議。本書吸取了過去的一些經驗，修訂了其中的錯誤，努力寫得更好，希望有更多的讀者喜歡。本書適用于在讀的計算機專業學生、準備考取計算機專業研究生的人員和從事教學科學研究的人員閱讀。但如果您覺得這本書并不適合您，請將本書放回書架比較顯眼的位置，我們在此表示感謝。
本書是一本難得的內容完整、語言通俗、案例豐富的數據結構自學圖書和教材。本書致力于將數據結構這個原本抽象的東西盡可能地通俗化，讓每位希望掌握數據結構知識的朋友都能盡快輕松地掌握它，因此本書在表述方面采用了通俗的語言，并選取了豐富的案例，以滿足讀者的需要。
本書全面地介紹數據結構的基本知識，通過理論和實踐并重的方式，站在初學者的角度，從最基礎的知識開始，由淺入深，對每一個概念都通過通俗的語言進行講解，對每一個抽象的概念，對都拿現實生活中的例子進行類比，以方便讀者理解和掌握。另外，本書案例豐富、典型，所有算法都直接利用C語言描述，所有程序都可以直接運行。本書內容全面，不僅詳細介紹了C語言的基礎知識，還涉及C語言相關的高級技術和理論知識，是一本難得的技術參考書和自學教材，主要內容包括數據結構概述、常用的程序開發環境、線性表、棧、隊列、串、數組、廣義表、樹與二叉樹、圖、查找、排序。
通過學習本書，您會體驗到學習數據結構時從未有過的簡單易學，本書將幫您輕松掌握數據結構中的每一個知識點，攻克數據結構知識堡壘中的任何一個重點和難點。
1. 本書的特點
(1) 內容全面，講解詳細：為了方便讀者學習，本書首先對數據結構課程的目標和描述方式進行介紹，并對算法使用的語言——C語言的重點和難點進行復習。本書覆蓋了數據結構中線性表、樹和圖的所有知識點，對于每一種數據結構，都使用所有可能的邏輯結構和存儲結構進行描述，并對算法盡量采用多種實現方式，如遞歸和非遞歸、順序存儲和鏈式存儲，從而使讀者對算法的理解更加深刻。
(2) 層次清晰，結構合理：本書將數據結構分篇、章、節和小節劃分知識點，將知識點細化，易于讀者理解。每一個知識點單獨作為一個小節，專門講解。在知識點的講解過程中，循序漸進，由淺入深，先引出概念，再用例子說明，然后是算法描述，最后是具體程序實現。這樣的層次十分易于讀者理解和消化。
(3) 結合圖表，語言通俗：在每個概念提出后，都結合圖表和例子以方便讀者理解。在語言的敘述上，普遍采用短句子、易于理解的語言，而避免使用復雜句子和晦澀難懂的語言。通過以上方式的描述，讀者可以更加容易和輕松地學習數據結構。
(4) 例子典型，深入剖析：在講解每一個算法時，結合具體例子進行剖析。在例子的選取上，結合歷年考研試題，選取的例子涵蓋知識點比較全面，具有代表性。在每一章的最后或比較大的知識點后面，都給出了一個完整的程序，給出程序的同時，還對算法通過圖進行具體講解，深入分析，并在程序的最后給出運行結果。讀者在學習的過程中，可以結合例子和運行結果以驗證算法的正確性。
(5) 配有習題，鞏固知識：從第2章開始，在每一章的最后，都有一個小結，對該章的知識點進行總結。為了讓讀者熟練編寫算法，本書在每一章的最后都配有一定數量的實踐題目，在學習了每一章的內容之后，可以通過這些習題試著編寫算法，以鞏固該章的學習內容。在本書配套的下載資料中，提供了每一個例子的程序代碼和課后習題代碼。
2. 本書的內容
第1章：如果讀者剛接觸數據結構，該章將從什么是數據結構講起，介紹本書的學習目標、學習方法和學習內容，作者還將現身說法，告訴讀者如何學好數據結構知識。
第2章：對本書的描述語言和使用工具進行介紹。該章主要介紹C語言的開發環境，然后復習C語言中的重點和難點——指針、數組、函數、遞歸和結構體。通過對該章內容的學習，讀者在以后數據結構的學習過程中將會得心應手。
第3章：主要介紹線性表。首先講解線性表的邏輯結構，然后介紹線性表的兩種常用存儲結構，并講解各種鏈表結構，包括靜態鏈表，在每一節均給出算法的具體應用。通過對該章內容的學習，讀者將掌握順序表和各種鏈表的操作。
第4章：主要介紹一種特殊的線性表——棧。首先介紹棧的定義，然后介紹棧的應用及棧與遞歸的關系、轉化。通過對該章內容的學習，讀者將學會棧的使用并深入理解遞歸和棧的知識。
第5章：主要介紹另一種特殊的線性表——隊列。首先介紹隊列的概念，然后介紹順序隊列、循環隊列和鏈式隊列，并給出各種隊列的實現算法。該章在最后結合具體的例子分析隊列的具體使用。
第6章：主要介紹另一種特殊的線性表——串。首先介紹串的概念，然后介紹串的各種存儲表示，并介紹串的模式匹配算法。通過串的模式匹配可以提高求子串的效率。
第7章：主要介紹數組。首先介紹數組的概念，然后介紹數組(矩陣)的順序存儲、鏈式存儲及矩陣的運算，最后介紹幾種特殊的矩陣。通過對該章內容的學習，讀者將掌握矩陣的一些算法操作。
第8章：主要介紹廣義表。首先介紹廣義表的概念，然后介紹廣義表的兩種存儲方式，最后給出廣義表的操作實現。
第9章：主要介紹一種非線性數據結構——樹和二叉樹。首先介紹樹和二叉樹的概念，然后介紹樹和二叉樹的存儲表示、二叉樹的性質、二叉樹的遍歷和線索化、樹和森林與二叉樹的轉換及哈夫曼樹。該章在講解這些知識點時，均給出具體例子以增強對這些知識的理解。在該章的最后，專門給出樹的具體應用。
第10章：主要介紹另一種非線性數據結構——圖。首先介紹圖的概念和存儲結構，然后介紹圖的遍歷、最小生成樹、拓撲排序、關鍵路徑及最短路徑。在講解這些知識點時，都給出相應的算法和例子，以加強對知識點的理解。
第11章：主要介紹一種數據結構的常用技術——查找。查找是數據結構非數值運算中非常常用的技術，該章首先介紹查找的概念，然后介紹各種查找算法，并結合具體實例進行詳細的講解，并給出完整程序。通過對該章內容的學習，讀者將掌握程序設計中非常重要的查找技術。
第12章：主要介紹另一種數據結構的常用技術——排序。排序是數據結構中最為常用的技術，該章首先介紹排序的相關概念，然后介紹多種排序技術，并結合實例講解這些算法的實現，在每一節都給出完整的程序。通過對該章內容的學習，讀者將掌握程序設計中最為常用的排序技術。
由于作者水平有限，書中難免存在一些不足之處，懇請讀者批評指正。讀者可以通過電子郵箱nwuchenrui@126.com與作者聯系。
3. 適合的讀者
本書適合下列讀者閱讀和學習使用：
* 大中專院校的學生。
* 準備考取計算機專業研究生的人員。
* 準備參加軟考的人員。
* 軟件開發人員。
* 計算機相關的科研工作者。
3. 致謝
感謝我的導師張蕾教授，她豐富的知識儲備及敏銳的洞察力極大地影響了我的學習態度和認識能力，使我在職業生涯中受益，也為本書的編寫奠定了良好的基礎。
感謝我的家人，是因為有他們默默的付出和鼓勵，我才能順利地做好各項工作。
最后特別感謝溫縣教育局及所有支持我寫作的朋友們！
陳 銳
目 錄第1章 概述 1
1.1 數據結構的基本概念 2
1.2 抽象數據類型 5
1.2.1 抽象數據類型的定義 5
1.2.2 抽象數據類型的描述 6
1.3 算法的特性與算法的描述 7
1.3.1 算法的定義 7
1.3.2 算法的特性 7
1.3.3 算法的描述 8
1.4 算法分析 9
1.4.1 算法設計的要求 9
1.4.2 算法效率評價 10
1.4.3 時間復雜度 11
1.4.4 空間復雜度 13
1.5 如何學好數據結構 14
1.5.1 數據結構課程的地位 14
1.5.2 數據結構課程的重要性 14
1.5.3 如何學好數據結構 15
第2章 C語言基礎 17
2.1 開發環境介紹 18
2.1.1 Turbo C 2.0開發環境介紹 18
2.1.2 Visual C++ 6.0開發環境
介紹 20
2.2 遞歸與非遞歸 24
2.2.1 函數的遞歸調用 24
2.2.2 遞歸函數應用舉例 25
2.2.3 一般遞歸轉化為非遞歸
(使用迭代) 27
2.3 指針 28
2.3.1 指針變量 28
2.3.2 指針變量的引用 29
2.3.3 指針與數組 30
2.3.4 函數指針與指針函數 35
2.4 參數傳遞 42
2.4.1 傳值調用 42
2.4.2 傳地址調用 43
2.5 結構體與共用體 46
2.5.1 結構體的定義 46
2.5.2 指向結構體的指針 48
2.5.3 共用體及應用 49
2.6 動態內存分配與釋放 50
2.6.1 內存動態分配與釋放 50
2.6.2 鏈表 51
2.7 小結 56
2.8 習題 57
第3章 線性表 59
3.1 線性表的概念及抽象數據類型 60
3.1.1 線性表的定義 60
3.1.2 線性表的抽象數據類型 61
3.2 線性表的順序表示與實現 62
3.2.1 線性表的順序存儲結構 62
3.2.2 順序表的基本運算 63
3.2.3 順序表基本運算的
算法分析 66
3.3 順序表的應用舉例 67
3.4 線性表的鏈式表示與實現 72
3.4.1 單鏈表的存儲結構 72
3.4.2 單鏈表上的基本運算 74
3.5 單鏈表應用舉例 79
3.6 循環單鏈表 87
3.6.1 循環鏈表的鏈式存儲 87
3.6.2 循環單鏈表的應用 88
3.7 雙向鏈表 93
3.7.1 雙向鏈表的存儲結構 93
3.7.2 雙向鏈表的插入操作和
刪除操作 94
3.8 雙向鏈表的應用 96
3.9 靜態鏈表 99
3.9.1 靜態鏈表的存儲結構 99
3.9.2 靜態鏈表的實現 100
3.9.3 靜態鏈表的應用 102
3.10 各種線性表的操作 104
3.11 一元多項式的表示與相乘 111
3.11.1 一元多項式的表示 112
3.11.2 一元多項式相乘 113
3.12 小結 117
3.13 習題 118
第4章 棧 121
4.1 棧的表示與實現 122
4.1.1 棧的定義 122
4.1.2 棧的抽象數據類型 123
4.2 棧的順序表示與實現 124
4.2.1 棧的順序存儲結構 124
4.2.2 順序棧的基本運算 125
4.2.3 共享棧的問題 127
4.3 棧的應用舉例 129
4.4 棧的鏈式表示與實現 132
4.4.1 棧的存儲結構 133
4.4.2 棧的基本運算 133
4.4.3 鏈棧的應用 136
4.5 棧的應用舉例 137
4.5.1 數制轉換 137
4.5.2 括號配對 139
4.5.3 行編輯程序 141
4.6 棧與遞歸的實現 143
4.6.1 遞歸 143
4.6.2 消除遞歸 146
4.7 棧的應用舉例 152
4.7.1 表達式的轉換與運算 152
4.7.2 表達式的運算舉例 154
4.8 小結 158
4.9 習題 159
第5章 隊列 161
5.1 隊列的定義 162
5.1.1 隊列的定義 162
5.1.2 隊列的抽象數據類型 162
5.2 隊列的順序存儲及實現 163
5.2.1 順序隊列的表示 163
5.2.2 順序隊列的“假溢出” 166
5.2.3 順序循環隊列的表示 167
5.2.4 順序循環隊列的實現 168
5.2.5 順序循環隊列實例 170
5.3 隊列的鏈式存儲及實現 173
5.3.1 鏈式隊列的表示 173
5.3.2 鏈式隊列的實現 175
5.3.3 鏈式隊列實例 177
5.4 雙端隊列 181
5.4.1 雙端隊列的定義 181
5.4.2 雙端隊列的應用 181
5.5 隊列在楊輝三角中的應用 184
5.5.1 楊輝三角 184
5.5.2 楊輝三角的隊列構造 185
5.5.3 楊輝三角隊列的實現 185
5.6 小結 189
5.7 習題 190
第6章 串 191
6.1 串 192
6.1.1 串的定義 192
6.1.2 串的抽象數據類型 192
6.2 串的順序表示與實現 195
6.2.1 串的順序存儲結構 195
6.2.2 串的基本運算 196
6.3 串的應用舉例 201
6.4 串的堆分配表示與實現 202
6.4.1 堆分配的存儲結構 202
6.4.2 堆串的基本運算 203
6.5 堆串的應用舉例 209
6.6 串的鏈式存儲表示與實現 210
6.6.1 串的鏈式存儲結構 210
6.6.2 鏈串的基本運算 212
6.7 鏈串的應用舉例 217
6.8 串的模式匹配 219
6.8.1 經典的模式匹配算法
Brute-Force 219
6.8.2 KMP算法 220
6.8.3 模式匹配應用舉例 226
6.9 小結 230
6.10 習題 230
第7章 數組 233
7.1 數組 234
7.1.1 數組的定義 234
7.1.2 數組的抽象數據類型 235
7.2 數組的順序表示與實現 235
7.2.1 數組的順序存儲結構 236
7.2.2 數組的基本運算 237
7.2.3 數組的應用舉例 239
7.3 特殊矩陣的壓縮存儲 241
7.3.1 對稱矩陣的壓縮存儲 241
7.3.2 三角矩陣的壓縮存儲 242
7.3.3 對角矩陣的壓縮存儲 243
7.4 稀疏矩陣的壓縮存儲 243
7.4.1 稀疏矩陣的定義 244
7.4.2 稀疏矩陣抽象數據類型 244
7.4.3 稀疏矩陣的三元組表示 245
7.4.4 稀疏矩陣的三元組實現 246
7.5 稀疏矩陣的應用舉例 252
7.5.1 稀疏矩陣相乘的三元組
表示 252
7.5.2 稀疏矩陣的相乘三元組
實現 254
7.6 稀疏矩陣的十字鏈表表示與實現 257
7.6.1 稀疏矩陣的十字鏈表表示 257
7.6.2 十字鏈表的實現 258
7.7 稀疏矩陣的十字鏈表實現應用
舉例 261
7.8 小結 266
7.9 習題 267
第8章 廣義表 269
8.1 廣義表 270
8.1.1 廣義表的定義 270
8.1.2 廣義表的抽象數據類型 271
8.2 廣義表的頭尾鏈表表示與實現 271
8.2.1 廣義表的頭尾鏈表存儲
結構 272
8.2.2 廣義表的基本運算 273
8.2.3 廣義表的應用舉例 275
8.3 廣義表的擴展線性鏈表表示與
實現 278
8.3.1 廣義表的擴展線性鏈表
存儲 278
8.3.2 廣義表的基本運算 279
8.3.3 采用擴展線性鏈表存儲結構的
廣義表應用舉例 282
8.4 小結 284
8.5 習題 285
第9章 樹 287
9.1 樹 288
9.1.1 樹的定義 288
9.1.2 樹的邏輯表示 289
9.1.3 樹的抽象數據類型 290
9.2 二叉樹 291
9.2.1 二叉樹的定義 291
9.2.2 二叉樹的性質 293
9.2.3 二叉樹的抽象數據類型 294
9.3 二叉樹的存儲表示與實現 295
9.3.1 二叉樹的順序存儲 296
9.3.2 二叉樹的鏈式存儲 296
9.3.3 二叉樹的基本運算 297
9.4 二叉樹的遍歷 301
9.4.1 二叉樹遍歷的定義 301
9.4.2 二叉樹的先序遍歷 301
9.4.3 二叉樹的中序遍歷 303
9.4.4 二叉樹的后序遍歷 305
9.5 二叉樹的遍歷的應用舉例 307
9.5.1 二叉樹的創建 308
9.5.2 二叉樹的輸出 311
9.5.3 二叉樹的計數 315
9.6 二叉樹的線索化 318
9.6.1 二叉樹的線索化定義 318
9.6.2 二叉樹的線索化 319
9.6.3 線索二叉樹的遍歷 321
9.6.4 線索二叉樹的應用舉例 323
9.7 樹、森林與二叉樹 326
9.7.1 樹的存儲結構 326
9.7.2 樹轉換為二叉樹 328
9.7.3 森林轉換為二叉樹 330
9.7.4 二叉樹轉換為樹和森林 330
9.7.5 樹和森林的遍歷 331
9.8 哈夫曼樹 332
9.8.1 哈夫曼樹的定義 332
9.8.2 哈夫曼編碼 334
9.8.3 哈夫曼編碼算法的實現 334
9.9 樹與二叉樹的應用舉例 340
9.9.1 相似二叉樹 340
9.9.2 由先序和中序、中序和后序
確定二叉樹 341
9.9.3 樹的孩子兄弟鏈表應用
舉例 347
9.10 小結 350
9.11 習題 350
第10章 圖 353
10.1 圖的定義與相關概念 354
10.1.1 圖的定義 354
10.1.2 圖的相關概念 354
10.1.3 圖的抽象數據類型 357
10.2 圖的存儲結構 358
10.2.1 鄰接矩陣表示法 358
10.2.2 鄰接表表示法 360
10.2.3 十字鏈表表示法 361
10.2.4 鄰接多重鏈表表示法 362
10.3 圖的應用舉例 364
10.3.1 采用鄰接矩陣創建圖 364
10.3.2 采用鄰接表創建圖 367
10.4 圖的遍歷 370
10.4.1 圖的深度優先遍歷 370
10.4.2 圖的廣度優先遍歷 373
10.4.3 圖的遍歷應用舉例 375
10.5 圖的連通性問題 377
10.5.1 無向圖的連通分量與
生成樹 378
10.5.2 最小生成樹 379
10.6 有向無環圖 384
10.6.1 AOV網與拓撲排序 384
10.6.2 AOE網與關鍵路徑 387
10.6.3 關鍵路徑應用舉例 392
10.7 最短路徑 396
10.7.1 從某個頂點到其余各頂點的
最短路徑 397
10.7.2 每一對頂點之間的
最短路徑 402
10.8 圖的應用舉例 406
10.8.1 距離某個頂點的最短路徑
長度為k的所有頂點 406
10.8.2 求圖中頂點u到頂點v的
簡單路徑 409
10.9 小結 411
10.10 習題 412
第11章 查找 413
11.1 查找的基本概念 414
11.2 靜態查找 414
11.2.1 順序表的查找 415
11.2.2 有序順序表的查找 416
11.2.3 索引順序表的查找 418
11.2.4 靜態查找應用舉例 420
11.3 動態查找 422
11.3.1 二叉排序樹 423
11.3.2 平衡二叉樹 430
11.4 B-樹與B+樹 438
11.4.1 B-樹 438
11.4.2 B+樹 446
11.5 哈希表 447
11.5.1 哈希表的定義 447
11.5.2 哈希函數的構造方法 448
11.5.3 處理沖突的方法 449
11.5.4 哈希表應用舉例 451
11.6 小結 454
11.7 習題 455
第12章 排序 457
12.1 排序的基本概念 458
12.2 插入排序 459
12.2.1 直接插入排序 459
12.2.2 折半插入排序 460
12.2.3 希爾排序 461
12.2.4 插入排序應用舉例 462
12.3 選擇排序 464
12.3.1 簡單選擇排序 464
12.3.2 堆排序 465
12.3.3 選擇排序應用舉例 470
12.4 交換排序 471
12.4.1 冒泡排序 471
12.4.2 快速排序 473
12.4.3 交換排序應用舉例 475
12.5 歸并排序 479
12.5.1 歸并排序算法 479
12.5.2 歸并排序應用舉例 481
12.6 基數排序 482
12.6.1 基數排序算法 483
12.6.2 基數排序應用舉例 486
12.7 各種排序算法的比較 489
12.8 排序算法應用舉例 490
12.9 小結 494
12.10 習題 495
參考文獻 496
