數據結構（C語言版）（ 第4版 ）（微課版）
李雲清 楊慶紅 揭安全
- 出版商: 人民郵電
- 出版日期: 2023-07-01
- 售價: $419
- 語言: 簡體中文
- 頁數: 324
- ISBN: 7115603200
- ISBN-13: 9787115603203
-
相關分類:
Algorithms-data-structures
下單後立即進貨 (約4週~6週)
相關主題
商品描述
本書介紹了數據結構的基本概念和基本算法。全書共分為10章，包括概論，線性表及其順序存儲，線性表的鏈式存儲，字符串、集合和特殊數組，遞歸，樹型結構，二叉樹，圖，檢索，排序等內容。
本書內容豐富，邏輯性強，文字清晰流暢，既註重理論知識，又強調工程實用。書中既體現了抽象數據類型的觀點，又對每個算法的具體實現給出了完整的C語言源代碼描述。本書配套資源豐富，包含代碼、PPT課件、教案、教學大綱、實驗詳細指導、習題答案及解析等教學資源，同時重點內容錄制了微課視頻，支持線上線下混合教學。
本書可作為高等院校計算機專業及相關專業本科生“數據結構”課程的教材，也可以作為從事計算機工程與應用的廣大讀者的參考書。
作者簡介
李雲清， 教授，碩士研究生導師。江西省高等學校中、青年骨幹教師，江西省教育廳認定的江西省高等學校首批首級優質精品課程《數據結構》課程負責人。獨立系統地為計算機本科專業的學生開設了《數據結構》、《程序設計方法學》、《高級程序設計語言》（如BASIC語言、PASCAL語言）、《程序設計選講》等專業課程。獨立系統地講授了《面向對象技術》和《軟件自動化》等計算機專業碩士研究生課程。為研究課程進修班和助教進修班講授《人工智能》、《面向對象技術》和《軟件自動化》等課程。（合作）主持完成教育部教改項目1項，主持（完成）江西省教育廳科技項目2項，並且作為第二成員完成了3項國家級科研項目（1項國家863計劃，2項國家自然科學基金）和1項江西省跨世紀人才項目。另外，主持完成江西省教育廳省級教學研究項目1項，主持完成3項江西師大科研和教學研究課題。合編出版教材三部。 獲得省級優秀教學成果二等獎1次，三等獎2次。獲得校級優秀教學成果一等獎1次、二等獎1次，校首屆教師CAI課件大賽一等獎1次。
目錄大綱
第 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 抽象數據類型.............................................................6
1.2.3 抽象數據類型的描述和實現........................................7
1.3 算法和算法分析 ................................................ 8
1.3.1 算法的基本概念和基本特征........................................8
1.3.2 算法的時間復雜度和空間復雜度.................................8
本章小結 ................................................................ 9
習題.....................................................................10
第 2 章 線性表及其順序存儲.......................... 12
2.1 線性表...........................................................12
2.2 順序表 ..........................................................12
2.2.1 順序表的基本概念及描述 .........................................12
2.2.2 順序表的實現...........................................................13
2.3 棧 ................................................................17
2.3.1 棧的基本概念及描述 ................................................17
2.3.2 順序棧及其實現 .......................................................18
2.3.3 棧的應用之一——括號匹配......................................20
2.3.4 棧的應用之二——算術表達式求值 ...........................22
2.4 隊列 .............................................................26
2.4.1 隊列的基本概念及描述.............................................26
2.4.2 順序隊列及其實現....................................................27
2.4.3 順序循環隊列及其實現.............................................30
2.4.4 隊列的應用..............................................................31
本章小結 ...............................................................32
習題.....................................................................32
第 3 章 線性表的鏈式存儲 ............................ 34
3.1 鏈式存儲........................................................34
3.2 單鏈表 ..........................................................35
3.2.1 單鏈表的基本概念及描述 .........................................35
3.2.2 單鏈表的實現...........................................................36
3.3 帶頭節點的單鏈表 ........................................... 39
3.3.1 帶頭節點的單鏈表的基本概念及描述........................39
3.3.2 帶頭節點的單鏈表的實現 .........................................40
3.4 循環單鏈表.....................................................43
3.4.1 循環單鏈表的基本概念及描述..................................43
3.4.2 循環單鏈表的實現....................................................44
3.5 雙鏈表 ......................................................... 49
3.5.1 雙鏈表的基本概念及描述.........................................49
3.5.2 雙鏈表的實現...........................................................49
3.6 鏈式棧 ......................................................... 54
3.6.1 鏈式棧的基本概念及描述.........................................54
3.6.2 鏈式棧的實現...........................................................54
3.7 鏈式隊列........................................................57
3.7.1 鏈式隊列的基本概念及描述......................................57
3.7.2 鏈式隊列的實現 .......................................................57
本章小結 .............................................................. 60
習題.....................................................................61
第 4 章 字符串、集合和特殊數組.................... 63
4.1 字符串...........................................................63
4.1.1 字符串的基本概念....................................................63
4.1.2 字符串類的定義.......................................................64
4.1.3 字符串的存儲結構及其實現......................................65
4.2 字符串的模式匹配 ............................................71
4.2.1 樸素模式匹配算法....................................................71
4.2.2 快速模式匹配算法....................................................72
4.3 集合 .............................................................75
4.3.1 集合的定義和性質....................................................75
4.3.2 集合類的定義...........................................................76
4.3.3 集合的存儲結構及其實現.........................................76
4.4 數組 ............................................................ 84
4.4.1 數組和數組元素.......................................................84
4.4.2 數組類的定義...........................................................85
4.4.3 數組的順序存儲及其實現.........................................86
4.5 特殊矩陣....................................................... 89
4.5.1 對稱矩陣的壓縮存儲................................................89
2
4.5.2 三角矩陣的壓縮存儲................................................90
4.5.3 帶狀矩陣的壓縮存儲................................................92
4.6 稀疏矩陣....................................................... 93
4.6.1 稀疏矩陣類的定義....................................................93
4.6.2 稀疏矩陣的順序存儲及其實現..................................94
4.6.3 稀疏矩陣的鏈式存儲及其實現..................................96
本章小結 .............................................................100
習題...................................................................100
第 5 章 遞歸 ........................................... 102
5.1 遞歸的基本概念與遞歸程序設計 .........................102
5.2 遞歸程序執行過程的分析..................................104
5.3 遞歸程序到非遞歸程序的轉換 ............................106
5.3.1 簡單遞歸程序到非遞歸程序的轉換.........................107
5.3.2 復雜遞歸程序到非遞歸程序的轉換 .........................109
5.4 遞歸程序設計的應用實例.................................. 114
本章小結 ............................................................. 116
習題...................................................................116
第 6 章 樹狀結構...................................... 118
6.1 樹的基本概念 ................................................ 118
6.2 樹類的定義...................................................120
6.3 樹的存儲結構................................................120
6.3.1 雙親表示法............................................................120
6.3.2 孩子表示法............................................................121
6.3.3 孩子兄弟表示法.....................................................124
6.4 樹的遍歷......................................................125
6.5 樹的線性表示................................................128
6.5.1 樹的括號表示.........................................................128
6.5.2 樹的層號表示.........................................................130
6.6 並查集 ........................................................ 131
6.6.1 並查集的定義.........................................................131
6.6.2 並查集的構建.........................................................132
6.6.3 基於樹狀結構的並查集實現....................................132
本章小結 .............................................................137
習題...................................................................138
3
第 7 章 二叉樹 ........................................ 139
7.1 二叉樹的基本概念 ..........................................139
7.2 二叉樹的基本操作 .......................................... 141
7.3 二叉樹的存儲結構 .......................................... 141
7.3.1 順序存儲結構.........................................................142
7.3.2 鏈式存儲結構.........................................................143
7.4 二叉樹的遍歷................................................145
7.4.1 二叉樹遍歷的定義..................................................145
7.4.2 二叉樹遍歷的遞歸實現...........................................145
7.4.3 二叉樹遍歷的非遞歸實現.......................................147
7.5 二叉樹其他運算的實現.....................................150
7.6 線索二叉樹...................................................152
7.6.1 線索二叉樹的定義..................................................152
7.6.2 中序線索二叉樹的基本操作....................................153
7.6.3 中序線索二叉樹的存儲結構及其實現......................154
7.7 樹、森林和二叉樹的轉換..................................156
7.7.1 樹、森林到二叉樹的轉換.......................................156
7.7.2 二叉樹到樹、森林的轉換 .......................................157
本章小結 .............................................................158
習題...................................................................158
第 8 章 圖 .............................................. 160
8.1 圖的基本概念 ................................................160
8.2 圖的基本操作................................................163
8.3 圖的基本存儲結構 ..........................................164
8.3.1 鄰接矩陣及其實現..................................................164
8.3.2 鄰接表及其實現.....................................................167
8.3.3 鄰接多重表............................................................169
8.4 圖的遍歷......................................................170
8.4.1 深度優先遍歷 ........................................................170
8.4.2 廣度優先遍歷.........................................................172
8.5 生成樹與最小生成樹 .......................................173
8.5.1 最小生成樹的定義 .................................................175
8.5.2 最小生成樹的 Prim 算法 ........................................176
8.5.3 最小生成樹的 Kruskal 算法 ...................................179
8.6 最短路徑......................................................182
8.6.1 單源最短路徑 ........................................................182
4
8.6.2 所有頂點對的最短路徑...........................................185
8.7 拓撲排序......................................................188
8.8 關鍵路徑...................................................... 191
本章小結 .............................................................196
習題...................................................................196
第 9 章 查找 ........................................... 200
9.1 查找的基本概念 .............................................200
9.2 線性表的查找................................................201
9.2.1 順序查找................................................................201
9.2.2 二分查找................................................................203
9.2.3 分塊查找................................................................205
9.3 二叉排序樹...................................................207
9.4 豐滿樹和平衡樹 .............................................213
9.4.1 豐滿樹...................................................................214
9.4.2 平衡二叉排序樹.....................................................215
9.4.3 擴充二叉樹............................................................222
9.5 紅黑樹 ........................................................223
9.5.1 紅黑樹的定義.........................................................224
9.5.2 紅黑樹的插入.........................................................224
9.5.3 紅黑樹的刪除.........................................................227
9.6 最佳二叉排序樹和 Huffman 樹 .........................230
9.6.1 最佳二叉排序樹.....................................................230
9.6.2 Huffman 樹...........................................................235
9.7 B 樹 ...........................................................238
9.7.1 B-樹的定義 ...........................................................238
9.7.2 B-樹的基本操作 ....................................................239
9.7.3 B+樹 .....................................................................243
9.8 散列表查找...................................................245
9.8.1 散列存儲 ...............................................................245
9.8.2 散列函數的構造.....................................................246
9.8.3 沖突處理 ...............................................................247
本章小結 .............................................................251
習題...................................................................251
第 10 章 排序.......................................... 255
10.1 排序的基本概念 ...........................................255
5
10.2 插入排序....................................................256
10.2.1 直接插入排序 ......................................................256
10.2.2 二分法插入排序...................................................259
10.2.3 表插入排序..........................................................260
10.2.4 Shell 插入排序 ....................................................262
10.3 選擇排序....................................................263
10.3.1 直接選擇排序 ......................................................263
10.3.2 樹狀選擇排序 ......................................................265
10.3.3 堆排序.................................................................267
10.4 交換排序....................................................271
10.4.1 冒泡排序 .............................................................271
10.4.2 快速排序 .............................................................272
10.5 歸並排序....................................................274
10.6 基數排序....................................................278
10.6.1 多排序碼的排序...................................................278
10.6.2 靜態鏈式基數排序 ...............................................278
10.7 外部排序....................................................281
10.7.1 磁盤排序 .............................................................282
10.7.2 多路平衡歸並 ......................................................283
10.7.3 置換-選擇排序.....................................................285
10.7.4 最佳歸並樹..........................................................288
本章小結 .............................................................290
習題...................................................................291
附錄 1 基礎實驗 ...................................... 294
實驗 1 線性表的順序存儲實現 .................................294
實驗 2 不帶頭節點的單鏈表....................................297
實驗 3 帶頭節點的單鏈表.......................................301
實驗 4 棧與字符串 ...............................................303
實驗 5 遞歸........................................................306
實驗 6 樹...........................................................310
實驗 7 二叉樹.....................................................312
實驗 8 圖...........................................................315
實驗 9 查找........................................................317
實驗 10 排序 ......................................................318
附錄 2 綜合實驗
