本書介紹了數據結構的基本概念和基本算法。全書共分為10章，包括概論、線性表及其順序存儲、線性表的鏈式存儲、字符串、數組和特殊矩陣、遞歸、樹型結構、二叉樹、圖、檢索、內排序等內容，附錄給出了較為詳細的基礎實驗和幾類綜合課程設計題。
本書內容豐富，邏輯性強，文字清晰流暢，既注重理論知識，又強調工程實用。書中既體現了抽像數據類型的概念，又對每個算法的具體實現給出了完整的C語言源代碼描述。
與本書配套的電子教案、書中所有算法的源代碼和習題參考答案均可從人民郵電出版社教學服務與資源網(www.ptpedu.com.cn)上免費下載。
本書可作為高等院校計算機專業及相關專業本科生“數據結構”課程的教材，也可作為從事計算機工程與應用的廣大讀者的參考書。

• 
• 
• 
• 
• 

目錄

第1章概論1
1．1數據結構的基本概念與術語1
1．1．1數據結構的基本概念1
1．1．2數據的邏輯結構2
1．1．3數據的存儲結構3
1．1．4數據的運算集合5
1．2數據類型和抽像數據類型5
1．2．1數據類型6
1．2．2抽像數據類型7
1．2．3抽像數據類型的描述和實現7
1．3算法和算法分析8
1．3．1算法的基本概念和基本特征8
1．3．2算法的時間復雜度和空間復雜度8
習題10

第2章線性表及其順序存儲11
2．1線性表11
2．2順序表11
2．2．1順序表的基本概念及描述11
2．2．2順序表的實現12
2．3棧16
2．3．1棧的基本概念及描述16
2．3．2順序棧及其實現18
2．3．3棧的應用之一——括號匹配20
2．3．4棧的應用之二——算術表達式求值21
2．4隊列26
2．4．1隊列的基本概念及描述26
2．4．2順序隊列及其實現27
2．4．3順序循環隊列及其實現30
習題32

第3章線性表的鏈式存儲34
3．1鏈式存儲34
3．2單鏈表35
3．2．1單鏈表的基本概念及描述35
3．2．2單鏈表的實現36
3．3帶頭結點的單鏈表40
3．3．1帶頭結點的單鏈表的基本概念及描述40
3．3．2帶頭結點的單鏈表的實現40
3．4循環單鏈表44
3．4．1循環單鏈表的基本概念及描述44
3．4．2循環單鏈表的實現44
3．5雙鏈表50
3．5．1雙鏈表的基本概念及描述50
3．5．2雙鏈表的實現50
3．6鏈式棧55
3．6．1鏈式棧的基本概念及描述55
3．6．2鏈式棧的實現56
3．7鏈式隊列58
3．7．1鏈式隊列的基本概念及描述58
3．7．2鏈式隊列的實現59
習題62

第4章字符串、數組和特殊矩陣64
4．1字符串64
4．1．1字符串的基本概念64
4．1．2字符串類的定義64
4．1．3字符串的存儲及其實現65
4．2字符串的模式匹配72
4．2．1樸素的模式匹配算法73
4．2．2快速模式匹配算法73
4．3數組76
4．3．1數組素76
4．3．2數組類的定義77
4．3．3數組的順序存儲及實現78
4．4特殊矩陣81
4．4．1對稱矩陣的壓縮存儲82
4．4．2三角矩陣的壓縮存儲83
4．4．3帶狀矩陣的壓縮存儲84
4．5稀疏矩陣86
4．5．1稀疏矩陣類的定義86
4．5．2稀疏矩陣的順序存儲及其實現87
4．5．3稀疏矩陣的鏈式存儲及實現89
習題93

第5章遞歸94
5．1遞歸的基本概念與遞歸程序設計94
5．2遞歸程序執行過程的分析96
5．3遞歸程序到非遞歸程序的轉換99
5．3．1簡單遞歸程序到非遞歸程序的轉換99
5．3．2復雜遞歸程序到非遞歸程序的轉換102
5．4遞歸程序設計的應用實例107
習題109

第6章樹型結構110
6．1樹的基本概念110
6．2樹類的定義112
6．3樹的存儲結構112
6．3．1雙親表示法112
6．3．2孩子表示法113
6．3．3孩子兄弟表示法116
6．4樹的遍歷117
6．5樹的線性表示120
6．5．1樹的括號表示120
6．5．2樹的層號表示122
習題124

第7章二叉樹125
7．1二叉樹的基本概念125
7．2二叉樹的基本運算127
7．3二叉樹的存儲結構128
7．3．1順序存儲結構128
7．3．2鏈式存儲結構130
7．4二叉樹的遍歷131
7．4．1二叉樹遍歷的定義131
7．4．2二叉樹遍歷的遞歸實現131
7．4．3二叉樹遍歷的非遞歸實現133
7．5二叉樹其他運算的實現137
7．6穿線二叉樹139
7．6．1穿線二叉樹的定義139
7．6．2中序穿線二叉樹的基本運算140
7．6．3中序穿線二叉樹的存儲結構及其實現140
7．7樹、森林和二叉樹的轉換143
7．7．1樹、森林到二叉樹的轉換143
7．7．2二叉樹到樹、森林的轉換144
習題144

第8章圖146
8．1圖的基本概念146
8．2圖的基本運算149
8．3圖的基本存儲結構150
8．3．1鄰接矩陣及其實現150
8．3．2鄰接表及其實現153
8．3．3鄰接多重表155
8．4圖的遍歷156
8．4．1深度優先遍歷156
8．4．2廣度優先遍歷158
8．5生成樹與最小生成樹160
8．5．1最小生成樹的定義161
8．5．2最小生成樹的普裡姆(Prim)算法163
8．5．3最小生成樹的克魯斯卡爾(Kruskal)算法166
8．6最短路徑169
8．6．1單源最短路徑169
8．6．2所有頂點對的最短路徑172
8．7拓撲排序174
8．8關鍵路徑177
習題182
第
9章檢索186
9．1檢索的基本概念186
9．2線性表的檢索187
9．2．1順序檢索187
9．2．2二分法檢索188
9．2．3分塊檢索191
9．3二叉排序樹193
9．4豐滿樹和平衡樹200
9．4．1豐滿樹200
9．4．2平衡二叉排序樹201
9．5最佳二叉排序樹和Huffman樹207
9．5．1擴充二叉樹207
9．5．2最佳二叉排序樹208
9．5．3Huffman樹213
9．6B樹216
9．6．1B-樹的定義217
9．6．2B-樹的基本操作217
9．6．3B+樹222
9．7散列表檢索224
9．7．1散列存儲224
9．7．2散列函數的構造225
9．7．3衝突處理226
習題230

第10章內排序233
10．1排序的基本概念233
10．2插入排序234
10．2．1直接插入排序234
10．2．2二分法插入排序237
10．2．3表插入排序238
10．2．4Shell插入排序240
10．3選擇排序241
10．3．1直接選擇排序241
10．3．2樹型選擇排序243
10．3．3堆排序245
10．4交換排序249
10．4．1冒泡排序249
10．4．2快速排序250
10．5歸並排序253
10．6基數排序256
10．6．1多排序碼的排序256
10．6．2靜態鏈式基數排序256
習題260

附錄1基礎實驗262
實驗1線性表的順序實現262
實驗2不帶頭結點的單鏈表265
實驗3帶頭結點的單鏈表269
實驗4棧與字符串271
實驗5遞歸275
實驗6樹278
實驗7二叉樹280
實驗8圖283
實驗9檢索285
實驗10排序286
附錄2綜合實驗289

參考文獻295