數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言（微課版）

內(nèi)容精準(zhǔn)、結(jié)構(gòu)合理、深入淺出

精選案例、步驟清晰、圖文并茂

資源豐富、微課視頻、程序源碼

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)類(lèi)、電子信息類(lèi)及相關(guān)專(zhuān)業(yè)的核心課程，是專(zhuān)業(yè)技術(shù)基礎(chǔ)課，在整個(gè)課程體系中處于承上啟下的核心位置：一方面擴(kuò)展和深化學(xué)生在離散數(shù)學(xué)、程序設(shè)計(jì)語(yǔ)言等課程中學(xué)到的基本技術(shù)和方法；另一方面為學(xué)生進(jìn)一步學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)等專(zhuān)業(yè)知識(shí)奠定堅(jiān)實(shí)的理論與實(shí)踐基礎(chǔ)。

目前比較權(quán)威的“數(shù)據(jù)結(jié)構(gòu)”教材大多是考研指定教材，難度比較大，不太適合應(yīng)用型本科和專(zhuān)科學(xué)生使用。為此，我們編寫(xiě)了本書(shū)，通過(guò)引入大量案例，將復(fù)雜的理論問(wèn)題直觀化，采取案例驅(qū)動(dòng)式教學(xué)，更有利于各個(gè)層次的學(xué)生接受。

本書(shū)在教授學(xué)生數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)的同時(shí)，還培養(yǎng)了學(xué)生的邏輯推理能力，增強(qiáng)學(xué)生分析問(wèn)題、解決問(wèn)題和總結(jié)問(wèn)題的能力，更重要的是培養(yǎng)學(xué)生的專(zhuān)業(yè)興趣，樹(shù)立創(chuàng)新意識(shí)。本書(shū)在內(nèi)容選取上符合人才培養(yǎng)目標(biāo)的要求及教學(xué)規(guī)律和認(rèn)知規(guī)律，在結(jié)構(gòu)編排上按照“先理論、后應(yīng)用、理論與應(yīng)用相結(jié)合”的原則，并兼顧學(xué)科的廣度和深度，力求適用面廣。

全書(shū)共分8章，對(duì)常用的數(shù)據(jù)結(jié)構(gòu)，如線性表、棧、隊(duì)列、稀疏矩陣、廣義表、樹(shù)、二叉樹(shù)、圖等進(jìn)行深入講解，使學(xué)生能夠全面地理解基本概念、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作運(yùn)算、實(shí)現(xiàn)算法以及案例應(yīng)用。本書(shū)還利用比較法講解各種查找和排序的方法，并對(duì)各種算法的性能進(jìn)行分析，以便學(xué)生可以在不同的應(yīng)用場(chǎng)合選取合適的方法。本書(shū)對(duì)每種數(shù)據(jù)結(jié)構(gòu)和算法的剖析遵循由淺入深的原則，并配以實(shí)用的案例和圖示，還配有相應(yīng)的C語(yǔ)言源代碼，適合具有C語(yǔ)言基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)初學(xué)者。

本書(shū)由梁海英任主編（負(fù)責(zé)全書(shū)統(tǒng)稿），曾霖、樊艷英和殷玉玲任副主編。在本書(shū)編寫(xiě)過(guò)程中，編者得到了賀州學(xué)院的大力支持，參加本書(shū)部分內(nèi)容編寫(xiě)、程序調(diào)試、課件制作、習(xí)題收集、答案制作、內(nèi)容審校等工作的還有何巧萍、李曉欣、李玲、黃江鑫、劉威、梁海鵬、林芳雨、黃夢(mèng)丹、劉凱、黎未然、王熙棠、李鳳、高燁林、羅天揚(yáng)、肖思愛(ài)等，在此表示感謝。

由于編者水平有限，書(shū)中難免存在不當(dāng)之處，敬請(qǐng)讀者批評(píng)和提出建議。

前言

第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)概述 1
1.2 常用術(shù)語(yǔ)和基本概念 3
1.3 數(shù)據(jù)類(lèi)型 5
1.4 算法和算法復(fù)雜度 6
1.4.1 算法的重要性 6
1.4.2 算法的時(shí)間復(fù)雜度 8
1.4.3 算法的空間復(fù)雜度 9
1.5 本章實(shí)戰(zhàn)練習(xí) 10
1.6 本章小結(jié) 11
1.7 習(xí)題1 12
第2章 線性表 14
2.1 線性表概述 14
2.2 線性表的順序存儲(chǔ)及運(yùn)算的實(shí)現(xiàn) 15
2.2.1 線性表的順序存儲(chǔ) 15
2.2.2 順序表的基本操作 16
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)及運(yùn)算的實(shí)現(xiàn) 20
2.3.1 單鏈表 21
2.3.2 循環(huán)鏈表 29
2.3.3 雙向鏈表 30
2.4 本章實(shí)戰(zhàn)練習(xí) 32
2.4.1 順序表的常用操作 32
2.4.2 單鏈表的常用操作 35
2.4.3 通訊錄管理 38
2.5 本章小結(jié) 44
2.6 習(xí)題2 45
第3章 棧和隊(duì)列 50
3.1 棧 50
3.1.1 棧的定義 50
3.1.2 棧的順序存儲(chǔ)與操作 50
3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)與操作 54
3.2 隊(duì)列 55
3.2.1 隊(duì)列的定義 56
3.2.2 隊(duì)列的順序存儲(chǔ)與操作 56
3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)與操作 59
3.3 本章實(shí)戰(zhàn)練習(xí) 61
3.3.1 top為指針且指向棧頂元素的
下一個(gè)位置 61
3.3.2 top為整數(shù)且指向棧頂元素的
當(dāng)前位置 64
3.3.3 棧的應(yīng)用—數(shù)制轉(zhuǎn)換 66
3.3.4 順序隊(duì)列的基本操作 67
3.3.5 循環(huán)隊(duì)列設(shè)置不同隊(duì)空與隊(duì)滿條件的
解決方案 70
3.3.6 鏈隊(duì)列的基本操作 73
3.4 本章小結(jié) 76
3.5 習(xí)題3 76
第4章 特殊矩陣和廣義表 81
4.1 特殊矩陣的壓縮存儲(chǔ) 81
4.1.1 特殊矩陣及其壓縮存儲(chǔ) 81
4.1.2 稀疏矩陣及其壓縮存儲(chǔ) 84
4.2 廣義表 86
4.2.1 廣義表的定義 86
4.2.2 廣義表的表示及運(yùn)算 87
4.3 本章實(shí)戰(zhàn)練習(xí) 88
4.4 本章小結(jié) 92
4.5 習(xí)題4 92
第5章 樹(shù) 94
5.1 樹(shù)的概念 94
5.1.1 樹(shù)的定義 94
5.1.2 樹(shù)的基本術(shù)語(yǔ) 95
5.2 二叉樹(shù) 96
5.2.1 二叉樹(shù)的定義 97
5.2.2 二叉樹(shù)的性質(zhì) 99
5.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 100
5.3.1 二叉樹(shù)的順序存儲(chǔ) 100
5.3.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)與操作 101
5.4 二叉樹(shù)的遍歷 103
5.4.1 遍歷算法 103
5.4.2 線索二叉樹(shù) 106
5.5 樹(shù)與森林 109
5.5.1 樹(shù)和森林的存儲(chǔ) 110
5.5.2 二叉樹(shù)、樹(shù)和森林的轉(zhuǎn)換 113
5.5.3 樹(shù)和森林的遍歷 114
5.6 哈夫曼樹(shù) 114
5.6.1 哈夫曼樹(shù)的定義 114
5.6.2 哈夫曼樹(shù)的構(gòu)造算法 115
5.6.3 哈夫曼編碼 117
5.7 本章實(shí)戰(zhàn)練習(xí) 118
5.7.1 二叉樹(shù)的基本操作 118
5.7.2 線索二叉樹(shù)的操作 122
5.7.3 哈夫曼樹(shù)構(gòu)造 126
5.8 本章小結(jié) 128
5.9 習(xí)題5 128
第6章 圖 137
6.1 圖的定義和基本術(shù)語(yǔ) 137
6.1.1 圖的定義 137
6.1.2 圖的基本術(shù)語(yǔ) 137
6.2 圖的存儲(chǔ)與操作 140
6.2.1 鄰接矩陣 141
6.2.2 鄰接表 143
6.3 圖的遍歷 146
6.3.1 深度優(yōu)先遍歷算法 146
6.3.2 廣度優(yōu)先遍歷算法 148
6.4 圖與最小生成樹(shù) 150
6.4.1 生成樹(shù)和森林的概念 150
6.4.2 最小生成樹(shù) 151
6.5 最短路徑 155
6.5.1 單源點(diǎn)到其余各頂點(diǎn)的最短路徑 156
6.5.2 任意源點(diǎn)之間的最短路徑 159
6.6 AOV網(wǎng)與拓?fù)渑判?159
6.6.1 AOV網(wǎng) 159
6.6.2 拓?fù)渑判?160
6.7 AOE網(wǎng)與關(guān)鍵路徑 161
6.7.1 AOE網(wǎng) 161
6.7.2 關(guān)鍵路徑 162
6.8 本章實(shí)戰(zhàn)練習(xí) 164
6.8.1 圖的鄰接矩陣操作 164
6.8.2 圖的鄰接表操作 169
6.8.3 利用鄰接矩陣實(shí)現(xiàn)圖的深度
優(yōu)先遍歷 173
6.8.4 利用鄰接表實(shí)現(xiàn)圖的深度
優(yōu)先遍歷 175
6.8.5 利用鄰接矩陣實(shí)現(xiàn)圖的廣度
優(yōu)先遍歷 177
6.8.6 利用鄰接表實(shí)現(xiàn)圖的廣度
優(yōu)先遍歷 180
6.8.7 普里姆最小生成樹(shù)算法 184
6.8.8 迪杰斯特拉最短路徑算法 186
6.9 本章小結(jié) 189
6.10 習(xí)題6 190
第7章 查找 197
7.1 查找的基本概念 197
7.2 靜態(tài)查找表 198
7.2.1 順序查找 198
7.2.2 折半查找 200
7.3 動(dòng)態(tài)查找表 203
7.3.1 二叉排序樹(shù) 203
7.3.2 平衡二叉樹(shù) 206
7.4 哈希表 209
7.4.1 哈希表的定義 209
7.4.2 哈希函數(shù)的構(gòu)造 210
7.4.3 處理沖突的方法 211
7.4.4 哈希表的查找和性能 213
7.5 本章實(shí)戰(zhàn)練習(xí) 214
7.5.1 順序查找算法 214
7.5.2 折半查找算法 215
7.5.3 二叉排序樹(shù)查找算法 216
7.6 本章小結(jié) 218
7.7 習(xí)題7 219
第8章 排序 222
8.1 排序的基本概念 222
8.2 插入排序算法 223
8.2.1 直接插入排序 223
8.2.2 折半插入排序 224
8.2.3 希爾排序 225
8.3 交換排序算法 226
8.3.1 冒泡排序 226
8.3.2 快速排序 227
8.4 選擇排序算法 230
8.4.1 直接選擇排序 230
8.4.2 堆排序 231
8.5 歸并排序算法 233
8.6 排序算法的比較 235
8.7 本章實(shí)戰(zhàn)練習(xí) 235
8.8 本章小結(jié) 241
8.9 習(xí)題8 242
參考文獻(xiàn) 245

1. Java面向?qū)ο蟪绦蛟O(shè)計(jì) [主編 姜春磊 陳虹潔]
2. C語(yǔ)言程序設(shè)計(jì)實(shí)驗(yàn)指導(dǎo)與實(shí)訓(xùn)（第二版） [主編 倪燃]
3. 程序思維與C語(yǔ)言實(shí)現(xiàn) [張祎 王俊海 呂波]
4. Python程序設(shè)計(jì)及實(shí)踐教程 [肖朝暉]
5. C語(yǔ)言程序設(shè)計(jì) [魏琴 劉祖珉 趙仕波 肖陽(yáng)春]
6. C語(yǔ)言程序設(shè)計(jì)實(shí)驗(yàn)教程 [張小剛 司春景]
7. 電氣控制與PLC程序設(shè)計(jì)（第二版） [胡冠山]
8. Java Web項(xiàng)目化設(shè)計(jì)實(shí)踐教程 [邱云 曾陳萍]
9. C語(yǔ)言程序設(shè)計(jì)（第三版） [主編 丁紅 王立新 蔡開(kāi)立]
10. Python數(shù)據(jù)分析 [主編　馮志輝　趙磊　李放]
11. Python程序設(shè)計(jì)與應(yīng)用（第二版） [主編 張廣淵]
12. C程序設(shè)計(jì)實(shí)踐教程 [劉衛(wèi)國(guó)]
13. C程序設(shè)計(jì)（慕課版） [劉衛(wèi)國(guó)]
14. 程序設(shè)計(jì)基礎(chǔ)實(shí)踐教程（C/C++語(yǔ)言版） [張桂芬 葛麗娜]
15. C++案例項(xiàng)目精講 [主編 楊國(guó)興]
16. SwiftUI完全開(kāi)發(fā) [李智威 著]
17. MySQL數(shù)據(jù)庫(kù)項(xiàng)目式教程 [陳亞峰]
18. C語(yǔ)言程序設(shè)計(jì)習(xí)題與實(shí)驗(yàn)指導(dǎo)（第二版） [主編 甄增榮 張賓]
19. C語(yǔ)言程序設(shè)計(jì)（第二版） [主編 甄增榮 田云霞]
20. Unity3D虛擬現(xiàn)實(shí)應(yīng)用開(kāi)發(fā)實(shí)踐 [主 編 劉龍]
21. Python程序設(shè)計(jì) [主編 姜春磊 陳虹潔]
22. C語(yǔ)言程序設(shè)計(jì)實(shí)踐教程（活頁(yè)式） [主編 鄭茵 陳巍 滕泓虬]
23. 面向?qū)ο蟪绦蛟O(shè)計(jì) [主編 張勇 張平華 趙小龍]
24. 數(shù)據(jù)結(jié)構(gòu)（Python語(yǔ)言描述） [曹岳輝　劉衛(wèi)國(guó)　康松林　編著]
25. Python程序設(shè)計(jì)基礎(chǔ)及實(shí)戰(zhàn) [主編　劉健]
26. C語(yǔ)言程序設(shè)計(jì) [姜雪]
27. Python程序設(shè)計(jì)實(shí)踐教程 [王鶴琴 蔡正保]
28. C++程序設(shè)計(jì)實(shí)踐教程（第三版） [主編 劉衛(wèi)國(guó) 曹岳輝]
29. C++程序設(shè)計(jì)（第三版） [主編 曹岳輝 劉衛(wèi)國(guó)]
30. C語(yǔ)言程序設(shè)計(jì)項(xiàng)目化教程（活頁(yè)式） [主編 張利華 潘曉利]