全書共分8章, 圍繞線性表、棧、隊列、串、矩陣、廣義表、樹、二叉樹、圖等常用的數據結構, 介紹了基本概念、邏輯結構、存儲結構、操作運算以及實現算法、案例應用; 還介紹了多種常用的查找算法和排序算法, 并對各種算法的性能進行分析。
前言
數據結構在計算機科學中是一門綜合性的專業基礎課，是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。數據結構不僅是一般程序設計的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序的重要基礎。目前比較權威的數據結構教材大多是考研指定教材，難度比較大，不太適合應用型本科、三本及專科學生使用。為此，我們編寫了這本教材，通過引入大量案例，將復雜的理論問題直觀化，案例驅動式教學，更有利于這個層次的學生接受。
我們基于多年的豐富的教學經驗及素材積累，精心編寫此書，目的是讓初學者能循序漸進地掌握各種數據結構及操作，力求透徹、全面、易學、易用，充分調動學生的學習積極性。書中使用C語言定義各種數據結構、描述算法。本書對每種數據結構和算法的剖析都遵循由淺入深的原則，并配以實用的案例和圖示，配有相應的C語言源代碼，適合具有C語言基礎的數據結構初學者。
全書共分8章，對于常用的數據結構，如線性表、棧、隊列、串、矩陣、廣義表、樹、二叉樹、圖等進行深入講解，使讀者能夠全面地理解基本概念、邏輯結構、存儲結構、操作運算、實現算法以及案例應用，進而利用比較法講解各種查找和排序的方法，并對各種算法的性能進行分析，以便在不同的應用場合選取合適的方法。
本書由梁海英博士和王鳳領教授任主編，譚曉東、巫湘林、張波和胡元闖任副主編，全書由賀州學院梁海英教授統稿。在本書編寫過程中，得到了所在學院的同事的熱心幫助和支持，參加本書內容編寫、程序調試、課件制作、習題收集、答案制作、內容審校等工作的老師有趙方珍、羅蘭花、李立信、千文、黃華升、陳冠萍、袁淑丹等，在此向他們表示衷心的感謝！
由于水平有限，書中難免存在不妥之處，敬請讀者諒解，并提出寶貴意見。我們的電話是010-62796045，信箱是huchenhao@263.net。
本書對應的電子課件、習題答案和源代碼可以到http://www.tupwk.com.cn網站下載。
編者
2017年5月
目錄
第1章緒論1
1.1數據結構概述1
1.2常用術語和基本概念3
1.3數據類型6
1.3.1數據類型概述6
1.3.2抽象數據類型7
1.4算法和算法復雜度8
1.4.1算法的重要性9
1.4.2時間復雜度10
1.4.3空間復雜度12
1.5本章實戰練習13
1.6本章小結15
1.7習題116
第2章線性表19
2.1線性表概述19
2.1.1線性表的定義及特點19
2.1.2線性表的抽象數據類型的
定義20
2.2線性表的順序存儲及運算的
實現21
2.2.1線性表的順序存儲21
2.2.2順序表的基本操作22
2.3線性表的鏈式存儲及運算的
實現28
2.3.1單鏈表28
2.3.2循環鏈表37
2.3.3雙向鏈表38
2.4本章實戰練習41
2.4.1順序表的常用操作41
2.4.2單鏈表的常用操作45
2.4.3通訊錄管理47
2.5本章小結53
2.6習題254
第3章棧和隊列59
3.1棧59
3.1.1棧的定義59
3.1.2棧的順序存儲與操作61
3.1.3棧的鏈式存儲與操作65
3.2隊列66
3.2.1隊列的定義67
3.2.2隊列的順序存儲與操作68
3.2.3隊列的鏈式存儲與操作71
3.3本章實戰練習73
3.3.1top為指針且指向棧頂
元素的下一個位置73
3.3.2top為整數且指向棧頂
元素的下一個位置75
3.3.3棧的應用——數制轉換77
3.3.4順序隊列的基本操作79
3.3.5循環隊列設置不同隊空與
隊滿條件的解決方案82
3.3.6鏈隊列的基本操作85
3.4本章小結88
3.5習題389
第4章串、數組、矩陣和廣義表94
4.1串的定義95
4.1.1串的基本概念95
4.1.2串的抽象數據類型的定義96
4.2串的存儲與操作97
4.2.1串的順序存儲與操作97
4.2.2串的鏈式存儲與操作99
4.3數組100
4.3.1數組的定義100
4.3.2數組的順序存儲101
4.4矩陣的壓縮存儲102
4.4.1特殊矩陣的壓縮存儲102
4.4.2稀疏矩陣及其壓縮存儲105
4.5廣義表111
4.5.1廣義表的定義111
4.5.2廣義表的存儲結構及
實現112
4.6本章實戰練習114
4.6.1串的常見操作114
4.6.2串的基本操作及應用117
4.6.3數組應用——方陣126
4.6.4數組應用——稀疏矩陣126
4.7本章小結130
4.8習題4131
第5章樹134
5.1樹的概念134
5.1.1樹的定義134
5.1.2樹的基本術語135
5.2二叉樹137
5.2.1二叉樹的定義137
5.2.2二叉樹的性質139
5.3二叉樹的存儲結構141
5.3.1二叉樹的順序存儲141
5.3.2二叉樹的鏈式存儲與
操作142
5.4二叉樹的遍歷145
5.4.1遍歷算法145
5.4.2線索二叉樹148
5.4.3遍歷算法的應用舉例152
5.5樹與森林153
5.5.1樹和森林的存儲154
5.5.2二叉樹、樹和森林的
轉換157
5.5.3樹和森林的遍歷158
5.6哈夫曼樹159
5.6.1哈夫曼樹的定義159
5.6.2哈夫曼樹的構造算法159
5.6.3哈夫曼編碼161
5.7本章實戰練習162
5.7.1二叉樹的基本操作162
5.7.2線索二叉樹的操作167
5.7.3樹的應用——模擬資源
管理器171
5.7.4哈夫曼樹構造178
5.8本章小結180
5.9習題5180
第6章圖189
6.1圖的定義和基本術語189
6.1.1圖的定義189
6.1.2圖的基本術語190
6.2圖的存儲與操作194
6.2.1鄰接矩陣194
6.2.2鄰接表197
6.2.3十字鏈表200
6.3圖的遍歷201
6.3.1深度優先遍歷算法202
6.3.2廣度優先遍歷算法204
6.4圖與最小生成樹206
6.4.1生成樹和森林的算法206
6.4.2最小生成樹208
6.5最短路徑212
6.5.1單源點到其余各頂點的
最短路徑212
6.5.2任意源點之間的最短
路徑217
6.6AOV網與拓撲排序218
6.6.1AOV網219
6.6.2拓撲排序220
6.7AOE網與關鍵路徑222
6.7.1AOE網222
6.7.2關鍵路徑223
6.8本章實戰練習226
6.8.1圖的鄰接矩陣操作226
6.8.2圖的鄰接表操作230
6.8.3利用鄰接矩陣實現連通圖
的深度優先遍歷234
6.8.4利用鄰接表實現連通圖
的深度優先遍歷237
6.8.5利用鄰接矩陣實現連通圖
的廣度優先遍歷239
6.8.6利用鄰接表實現連通圖
的廣度優先遍歷242
6.8.7普里姆最小生成樹算法245
6.8.8迪杰斯特拉最短路徑
算法248
6.9本章小結251
6.10習題6251
第7章查找260
7.1查找的定義260
7.2靜態查找算法262
7.2.1順序查找262
7.2.2折半查找265
7.2.3分塊查找268
7.3動態查找算法270
7.3.1二叉排序樹270
7.3.2平衡二叉樹275
7.4哈希表279
7.4.1哈希表的定義279
7.4.2哈希函數的構造280
7.4.3處理沖突的方法283
7.4.4哈希表的查找和性能285
7.5本章實戰練習286
7.5.1順序查找算法286
7.5.2折半查找算法287
7.5.3二叉排序樹查找算法289
7.6本章小結291
7.7習題7292
第8章排序296
8.1排序的定義296
8.2插入排序算法297
8.2.1直接插入排序298
8.2.2折半插入排序299
8.2.3二路插入排序301
8.2.4表插入排序303
8.2.5希爾排序304
8.3交換排序算法305
8.3.1冒泡排序305
8.3.2快速排序306
8.4選擇排序算法309
8.4.1直接選擇排序309
8.4.2堆排序310
8.5歸并排序算法314
8.6排序算法的比較316
8.7本章實戰練習317
8.8本章小結322
8.9習題8323
參考文獻327
新書資訊