數(shù)據(jù)結(jié)構(gòu)——C語言描述(第四版)
定 價(jià):48 元
- 作者:陳慧南
- 出版時(shí)間:2022/2/25
- ISBN:9787560663012
- 出 版 社:西安電子科技大學(xué)出版社
- 中圖法分類:TP311.12
- 頁碼:
- 紙張:
- 版次:4
- 開本:16開
本書第三版及其配套的學(xué)習(xí)指導(dǎo)教材為普通高等教育“十一五”國家級(jí)規(guī)劃教材。本次修訂除保留前三版中的經(jīng)典數(shù)據(jù)結(jié)構(gòu)知識(shí)外,還增加了紅黑樹等新內(nèi)容。本書結(jié)構(gòu)嚴(yán)謹(jǐn),內(nèi)容深入淺出,反映了抽象、封裝和信息隱蔽等現(xiàn)代軟件設(shè)計(jì)理念,重視算法的時(shí)間和空間分析,包括搜索和排序時(shí)間的下界分析。本書使用C語言描述。
本書重視實(shí)踐性和程序設(shè)計(jì)。書中算法都有完整的C程序,程序代碼構(gòu)思精巧、結(jié)構(gòu)清晰、注釋詳細(xì),所有程序都已在TC 2.01下編譯通過并能正確運(yùn)行。這些程序既是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的很好示例,也是很好的C程序設(shè)計(jì)示例。本書最后一章是實(shí)習(xí)指導(dǎo)和實(shí)習(xí)題,指導(dǎo)學(xué)生按軟件工程學(xué)的方法設(shè)計(jì)算法、編寫程序和書寫文檔。本書配有大量的實(shí)例和圖示,并有豐富的習(xí)題,易教易學(xué)。本書涵蓋計(jì)算機(jī)學(xué)科專業(yè)考研大綱數(shù)據(jù)結(jié)構(gòu)部分的考查內(nèi)容。
本書可作為計(jì)算機(jī)類、電子信息類、電氣類、自動(dòng)化類、電子商務(wù)、信息管理與信息系統(tǒng)等相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程的教材和考研參考書,也可供從事計(jì)算機(jī)軟件和應(yīng)用工作的工程技術(shù)人員參考。
全書條理清晰,內(nèi)容詳實(shí),深入淺出;配有大量的實(shí)例和圖示,有利于讀者理解算法的實(shí)質(zhì)和編程思想。
作者在南京郵電大學(xué)的從教生涯中,編寫出版了多本教材,其中《數(shù)據(jù)結(jié)構(gòu)—使用C++語言描述》《數(shù)據(jù)結(jié)構(gòu)—C語言描述》《〈數(shù)據(jù)結(jié)構(gòu)—C語言描述〉學(xué)習(xí)指導(dǎo)和習(xí)題解析》以及《算法設(shè)計(jì)與分析》均為普通高等教育“十一五”國家級(jí)規(guī)劃教材。本書初次出版是在2003年,此次第四版依據(jù)ACM/IEEE的《計(jì)算機(jī)科學(xué)課程體系規(guī)范2013》,對(duì)教材內(nèi)容作了更新和增添。
“數(shù)據(jù)結(jié)構(gòu)”作為計(jì)算機(jī)學(xué)科的一門基礎(chǔ)課,不僅講授經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法,而且強(qiáng)調(diào)在現(xiàn)代編程環(huán)境中實(shí)現(xiàn)這些算法,此外,還應(yīng)讓學(xué)生學(xué)習(xí)和理解問題分解、抽象、封裝和信息隱蔽、規(guī)范與實(shí)現(xiàn)分離、遞歸和算法效率等概念和方法,為學(xué)生進(jìn)一步學(xué)習(xí)計(jì)算機(jī)科學(xué)技術(shù)打下良好的基礎(chǔ)。
本次再版秉承作者以往的做法,采用抽象數(shù)據(jù)類型討論數(shù)據(jù)結(jié)構(gòu),并直接采用C程序設(shè)計(jì)語言描述數(shù)據(jù)結(jié)構(gòu)和算法。書中算法有完整的C程序,程序結(jié)構(gòu)清晰,構(gòu)思精巧。所有C程序都在Dev-C++環(huán)境下編譯通過并能正確運(yùn)行。它們既是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的很好示例,也是很好的C程序設(shè)計(jì)示例。同時(shí),本書強(qiáng)化了算法分析,書中多數(shù)算法作了時(shí)空效率分析,對(duì)超出本書范圍的也不加證明地給出了結(jié)論,還引入了更多實(shí)用的高級(jí)數(shù)據(jù)結(jié)構(gòu)。
本書條理清晰,內(nèi)容翔實(shí),深入淺出,書中對(duì)算法作了較詳細(xì)的解釋,盡可能做到可讀易懂,并配有大量的實(shí)例和圖示,有利于讀者理解算法的實(shí)質(zhì)和編程思想。每章引言和結(jié)尾處的小結(jié)可幫助讀者了解本章的要點(diǎn),每章后還配有豐富的習(xí)題,有助于讀者對(duì)重點(diǎn)知識(shí)及時(shí)復(fù)習(xí)鞏固。
本書滿足高等院校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)和其他相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程84學(xué)時(shí)的教學(xué)安排。對(duì)于學(xué)時(shí)數(shù)少于84學(xué)時(shí)的授課計(jì)劃,可根據(jù)實(shí)際學(xué)時(shí)對(duì)書中內(nèi)容加以取舍。作者已在目錄中對(duì)難度較大或非基本的章節(jié)標(biāo)注*號(hào),供讀者選取時(shí)參考。除標(biāo)*號(hào)部分外的基本內(nèi)容適合48~56學(xué)時(shí)授課計(jì)劃。
書中若有不當(dāng)之處,敬請(qǐng)讀者批評(píng)指正。
編 者
2021年7月于上海
第1章 概論 1
1.1 問題求解方法 1
1.1.1 問題和問題求解 1
1.1.2 問題求解過程 2
1.1.3 計(jì)算機(jī)求解問題的過程 2
1.1.4 算法與數(shù)據(jù)結(jié)構(gòu) 2
1.2 什么是數(shù)據(jù)結(jié)構(gòu) 3
1.2.1 基本概念 3
1.2.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 4
1.2.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 5
1.2.4 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 6
1.3 數(shù)據(jù)抽象和抽象數(shù)據(jù)類型 7
1.3.1 抽象、數(shù)據(jù)抽象和過程抽象 7
1.3.2 封裝和信息隱蔽 7
1.3.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 7
1.3.4 數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類型 8
1.4 描述數(shù)據(jù)結(jié)構(gòu) 9
1.4.1 數(shù)據(jù)結(jié)構(gòu)的規(guī)范 9
1.4.2 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu) 9
1.5 算法和算法分析 11
1.5.1 算法及其性能標(biāo)準(zhǔn) 11
1.5.2 算法的時(shí)間復(fù)雜度 12
1.5.3 漸近時(shí)間復(fù)雜度 14
1.5.4 最壞、最好和平均情況時(shí)間
復(fù)雜度 15
1.5.5 算法的空間復(fù)雜度 15
小結(jié) 15
習(xí)題1 16
第2章 數(shù)組和鏈表 18
2.1 結(jié)構(gòu)與聯(lián)合 18
2.1.1 結(jié)構(gòu) 18
2.1.2 聯(lián)合 19
2.2 數(shù)組 20
2.2.1 一維數(shù)組 20
2.2.2 二維數(shù)組 20
2.2.3 多維數(shù)組 22
2.3 鏈表 22
2.3.1 指針 22
2.3.2 單鏈表 26
2.3.3 帶表頭結(jié)點(diǎn)的單鏈表 32
2.3.4 循環(huán)鏈表 32
2.3.5 雙向鏈表 33
2.4 采用模擬指針的鏈表 35
2.4.1 結(jié)點(diǎn)結(jié)構(gòu) 35
2.4.2 可用空間表 35
小結(jié) 37
習(xí)題2 37
第3章 堆棧和隊(duì)列 39
3.1 堆棧 39
3.1.1 堆棧ADT 39
3.1.2 堆棧的順序表示 40
3.1.3 堆棧的鏈接表示 42
3.2 隊(duì)列 43
3.2.1 隊(duì)列ADT 43
3.2.2 隊(duì)列的順序表示 44
3.2.3 隊(duì)列的鏈接表示 47
*3.3 表達(dá)式的計(jì)算 47
3.3.1 表達(dá)式 47
3.3.2 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 48
3.3.3 計(jì)算后綴表達(dá)式的值 52
*3.4 遞歸和遞歸過程 54
3.4.1 遞歸的概念 54
3.4.2 遞歸的實(shí)現(xiàn) 55
*3.5 演示和測(cè)試 57
小結(jié) 59
習(xí)題3 59
第4章 線性表和數(shù)組ADT 61
4.1 線性表 61
4.1.1 線性表ADT 61
4.1.2 線性表的順序表示 62
4.1.3 線性表的鏈接表示 65
4.1.4 兩種存儲(chǔ)表示的比較 69
*4.2 多項(xiàng)式的算術(shù)運(yùn)算 69
4.2.1 多項(xiàng)式ADT 69
4.2.2 多項(xiàng)式的鏈接表示 70
4.2.3 多項(xiàng)式的輸入和輸出 71
4.2.4 多項(xiàng)式相加 73
4.3 數(shù)組作為抽象數(shù)據(jù)類型 74
4.4 特殊矩陣 75
4.4.1 對(duì)稱矩陣 75
*4.4.2 帶狀矩陣 76
4.5 稀疏矩陣 77
4.5.1 稀疏矩陣ADT 77
4.5.2 稀疏矩陣的順序表示 78
4.5.3 稀疏矩陣轉(zhuǎn)置 79
4.5.4 稀疏矩陣的正交鏈表表示 82
小結(jié) 84
習(xí)題4 84
第5章 字符串和廣義表 86
5.1 字符串 86
5.1.1 字符串ADT 86
5.1.2 字符串的存儲(chǔ)表示 87
5.1.3 簡單模式匹配算法 88
*5.1.4 模式匹配的KMP算法 91
*5.2 廣義表 95
5.2.1 廣義表的概念 95
5.2.2 廣義表ADT 96
5.2.3 廣義表的存儲(chǔ)表示 97
5.2.4 廣義表的算法 98
小結(jié) 99
習(xí)題5 99
第6章 樹 100
6.1 樹的基本概念 100
6.1.1 樹的定義 100
6.1.2 基本術(shù)語 101
6.2 二叉樹 102
6.2.1 二叉樹的定義和性質(zhì) 102
6.2.2 二叉樹ADT 104
6.2.3 二叉樹的存儲(chǔ)表示 105
6.2.4 二叉樹的遍歷 108
*6.2.5 二叉樹遍歷的非遞歸算法 112
*6.2.6 二叉樹遍歷的應(yīng)用實(shí)例 114
*6.2.7 線索二叉樹 116
6.3 樹和森林 120
6.3.1 森林與二叉樹的轉(zhuǎn)換 120
6.3.2 樹和森林的存儲(chǔ)表示 121
6.3.3 樹和森林的遍歷 123
*6.4 堆和優(yōu)先權(quán)隊(duì)列 124
6.4.1 堆 124
6.4.2 優(yōu)先權(quán)隊(duì)列 127
6.5 哈夫曼樹和哈夫曼編碼 130
6.5.1 樹的路徑長度 130
6.5.2 哈夫曼樹和哈夫曼算法 131
6.5.3 哈夫曼編碼 133
*6.6 并查集和等價(jià)關(guān)系 135
6.6.1 并查集 135
6.6.2 并查集的實(shí)現(xiàn) 135
6.6.3 集合按等價(jià)關(guān)系分組 138
小結(jié) 139
習(xí)題6 139
第7章 集合和搜索 141
7.1 集合及其表示 141
7.1.1 集合和搜索 141
7.1.2 集合ADT 142
7.1.3 集合的表示 143
7.2 順序搜索 143
7.3 二分搜索 145
7.3.1 對(duì)半搜索 146
7.3.2 二叉判定樹 147
*7.3.3 斐波那契搜索 149
7.3.4 插值搜索 150
7.4 分塊搜索 151
*7.5 搜索算法的時(shí)間下界 152
小結(jié) 153
習(xí)題7 153
第8章 搜索樹 154
8.1 二叉搜索樹 154
8.1.1 二叉搜索樹的定義 154
8.1.2 二叉搜索樹的搜索 154
8.1.3 二叉搜索樹的插入 155
8.1.4 二叉搜索樹的刪除 157
*8.1.5 二叉搜索樹的高度 159
8.2 二叉平衡樹 160
8.2.1 二叉平衡樹的定義 160
8.2.2 二叉平衡樹的平衡旋轉(zhuǎn) 161
8.2.3 二叉平衡樹的插入 167
8.2.4 二叉平衡樹的刪除 170
8.2.5 二叉平衡樹的高度 173
8.3 B-樹 173
8.3.1 m叉搜索樹 173
8.3.2 B-樹的定義 175
8.3.3 B-樹的高度 175
8.3.4 B-樹的搜索 176
8.3.5 B-樹的插入 176
8.3.6 B-樹的刪除 179
*8.4 鍵樹 181
8.4.1 鍵樹的定義 181
8.4.2 雙鏈樹 182
8.4.3 Trie樹 183
8.5 伸展樹 184
8.5.1 自調(diào)節(jié)樹和伸展樹 184
8.5.2 伸展樹的伸展操作 184
8.5.3 分?jǐn)倳r(shí)間分析 187
8.6 紅黑樹 187
8.6.1 紅黑樹的定義 188
8.6.2 紅黑樹的搜索 188
8.6.3 紅黑樹的插入 188
8.6.4 紅黑樹的刪除 192
8.6.5 紅黑樹的高度 192
小結(jié) 192
習(xí)題8 193
第9章 跳表和散列表 195
9.1 字典 195
*9.2 跳表 195
9.2.1 什么是跳表 196
9.2.2 跳表的搜索 199
9.2.3 跳表的插入 200
9.2.4 跳表的刪除 201
9.3 散列表 202
9.3.1 散列技術(shù) 202
9.3.2 散列函數(shù) 203
9.3.3 解決沖突的拉鏈法 204
9.3.4 解決沖突的線性探查法 205
9.3.5 解決沖突的其他開地址法 209
9.3.6 性能分析 211
小結(jié) 212
習(xí)題9 212
第10章 圖 213
10.1 圖的基本概念 213
10.1.1 圖的定義與術(shù)語 213
10.1.2 圖ADT 215
10.2 圖的存儲(chǔ)結(jié)構(gòu) 216
10.2.1 矩陣表示法 216
10.2.2 鄰接表表示法 220
*10.2.3 正交鏈表和多重表表示法 223
10.3 圖的遍歷 225
10.3.1 深度優(yōu)先遍歷 225
10.3.2 寬度優(yōu)先遍歷 227
10.4 拓?fù)渑判蚝完P(guān)鍵路徑 229
10.4.1 拓?fù)渑判?229
*10.4.2 關(guān)鍵路徑 233
10.5 最小代價(jià)生成樹 236
10.5.1 普里姆算法 237
*10.5.2 克魯斯卡爾算法 238
*10.6 最短路徑 240
10.6.1 單源最短路徑 241
10.6.2 所有頂點(diǎn)之間的最短路徑 244
小結(jié) 246
習(xí)題10 247
第11章 內(nèi)排序 249
11.1 排序的基本概念 249
11.2 插入排序 250
11.2.1 直接插入排序 250
*11.2.2 希爾排序 254
11.2.3 對(duì)半插入排序 255
11.3 交換排序 255
11.3.1 冒泡排序 256
11.3.2 快速排序 257
11.4 合并排序 262
11.4.1 兩路合并排序 262
11.4.2 合并排序的迭代算法 262
*11.4.3 鏈表上的合并排序 264
11.5 選擇排序 267
11.5.1 簡單選擇排序 268
*11.5.2 堆排序 269
*11.6 排序算法的時(shí)間下界 270
*11.7 基數(shù)排序 271
小結(jié) 275
習(xí)題11 275
第12章 文件和外排序 277
*12.1 輔助存儲(chǔ)器簡介 277
12.1.1 主存儲(chǔ)器和輔助存儲(chǔ)器 277
12.1.2 磁盤存儲(chǔ)器 277
12.2 文件 279
12.2.1 文件的基本概念 279
12.2.2 文件的組織方式 279
12.2.3 C語言文件 283
12.3 文件的索引結(jié)構(gòu) 284
12.3.1 靜態(tài)索引結(jié)構(gòu) 284
12.3.2 動(dòng)態(tài)索引結(jié)構(gòu) 285
*12.4 外排序 286
12.4.1 外排序的基本過程 286
12.4.2 初始游程的生成 286
12.4.3 多路合并 288
12.4.4 最佳合并樹 290
小結(jié) 291
習(xí)題12 292
第13章 實(shí)習(xí)指導(dǎo)和實(shí)習(xí)題 293
13.1 實(shí)習(xí)目的和要求 293
13.1.1 實(shí)習(xí)目的 293
13.1.2 實(shí)習(xí)要求 293
13.2 實(shí)習(xí)步驟 294
13.3 實(shí)習(xí)報(bào)告 294
13.4 實(shí)習(xí)題 295
13.5 實(shí)習(xí)報(bào)告范例 303
13.5.1 實(shí)習(xí)題:表達(dá)式計(jì)算 303
13.5.2 實(shí)習(xí)報(bào)告 303
13.6 上機(jī)考核 309
附錄A 軟件工程概述 311
附錄B 考研大綱和教材內(nèi)容 318
參考文獻(xiàn) 322