“數據結構與算法”是計算機學(xué)科研究的主題之一。本書(shū)采用類(lèi)C語(yǔ)言描述,系統地介紹了各種數據結構和排序、查找算法。全書(shū)共分為9章,主要內容包括數據結構與算法簡(jiǎn)介、線(xiàn)性表、棧和隊列、串、數組及廣義表、樹(shù)和二叉樹(shù)、圖、查找和排序等。對于各種數據結構,本書(shū)給出了基本概念、抽象數據類(lèi)型以及相關(guān)的操作,并且對各種算法的運行時(shí)間進(jìn)行了分析。
本書(shū)對數據結構中的重點(diǎn)和難點(diǎn)內容進(jìn)行了深入的剖析,著(zhù)重培養學(xué)生的動(dòng)手能力,對經(jīng)典算法、重點(diǎn)算法及應用算法進(jìn)行了詳細的講解,以使學(xué)生更好地掌握數據結構的應用。
本書(shū)可作為計算機及相關(guān)專(zhuān)業(yè)的大學(xué)本科教材,也可作為應用型專(zhuān)業(yè)以及成人教育、工程技術(shù)人員的培訓教材。
第1章 緒論 1
1.1 學(xué)習數據結構與算法的意義 1
1.2 數據結構 3
1.3 抽象數據類(lèi)型 5
1.4 算法 6
1.5 算法分析 9
小結 15
自測題答案 16
編程項目 17
第2章 線(xiàn)性表 18
2.1 線(xiàn)性表的定義 18
2.2 線(xiàn)性表的順序存儲結構 22
2.3 線(xiàn)性表的鏈式存儲結構 29
2.4 線(xiàn)性表的應用 43
小結 46
自測題答案 47
編程項目 48
第3章 棧和隊列 49
3.1 棧 49
3.2 棧的應用 55
3.3 隊列 67
3.4 隊列的應用 76
小結 79
自測題答案 79
編程項目 81
第4章 串 82
4.1 串的定義 82
4.2 串的存儲實(shí)現 84
4.3 串的模式匹配 88
小結 96
自測題答案 97
編程項目 98
第5章 數組及廣義表 99
5.1 數組的定義 99
5.2 數組的順序存儲 101
5.3 矩陣的壓縮存儲 104
5.4 廣義表 115
小結 122
自測題答案 123
編程項目 125
第6章 樹(shù)和二叉樹(shù) 126
6.1 樹(shù)的定義與基本操作 126
6.2 二叉樹(shù) 129
6.3 樹(shù)和森林 144
6.4 哈夫曼樹(shù)與哈夫曼編碼 149
小結 157
自測題答案 158
編程項目 160
第7章 圖 161
7.1 圖的定義 161
7.2 圖的存儲方式 166
7.3 圖的遍歷 175
7.4 圖的連通性 180
7.5 最小生成樹(shù) 184
7.6 最短路徑 189
7.7 有向無(wú)環(huán)圖的應用 195
小結 204
自測題答案 205
編程項目 209
第8章 查找 210
8.1 線(xiàn)性表上的查找 210
8.2 樹(shù)上的查找 218
8.3 哈希表 241
小結 252
自測題答案 254
編程項目 257
第9章 排序 258
9.1 插入排序 258
9.2 交換排序 266
9.3 選擇排序 271
9.4 歸并排序 278
9.5 基數排序 281
9.6 各種內部排序方法比較 283
9.7 外部排序 286
小結 292
自測題答案 293
編程項目 296
附錄 各章編程項目參考答案 297
參考文獻 391