“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)學(xué)科研究的主題之一。本書采用類C語言描述，系統(tǒng)地介紹了各種數(shù)據(jù)結(jié)構(gòu)和排序、查找算法。全書共分為9章，主要內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)與算法簡介、線性表、棧和隊(duì)列、串、數(shù)組及廣義表、樹和二叉樹、圖、查找和排序等。對(duì)于各種數(shù)據(jù)結(jié)構(gòu)，本書給出了基本概念、抽象數(shù)據(jù)類型以及相關(guān)的操作，并且對(duì)各種算法的運(yùn)行時(shí)間進(jìn)行了分析。
本書對(duì)數(shù)據(jù)結(jié)構(gòu)中的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行了深入的剖析，著重培養(yǎng)學(xué)生的動(dòng)手能力，對(duì)經(jīng)典算法、重點(diǎn)算法及應(yīng)用算法進(jìn)行了詳細(xì)的講解，以使學(xué)生更好地掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。
本書可作為計(jì)算機(jī)及相關(guān)專業(yè)的大學(xué)本科教材，也可作為應(yīng)用型專業(yè)以及成人教育、工程技術(shù)人員的培訓(xùn)教材。
本書訂正了第2版中的筆誤、描述不規(guī)范等問題，簡化了使用不多的內(nèi)容；每章的編程項(xiàng)目都有完整的C程序?qū)崿F(xiàn)代碼，并都在VC++6.0環(huán)境下編譯通過，運(yùn)行正確。
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。它側(cè)重于體系和思想上的訓(xùn)練，是程序設(shè)計(jì)的靈魂，為計(jì)算機(jī)語言課程設(shè)計(jì)提供了方法性的理論指導(dǎo)，所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。算法與數(shù)據(jù)結(jié)構(gòu)之間存在著相輔相成的關(guān)系。解決一個(gè)問題既可以選擇不同的數(shù)據(jù)結(jié)構(gòu)，也可以選擇不同的算法。數(shù)據(jù)結(jié)構(gòu)的選擇決定了算法執(zhí)行所需要的時(shí)間與空間，影響算法的效率；反之，算法的優(yōu)劣又決定了某個(gè)數(shù)據(jù)結(jié)構(gòu)是否適合解決這個(gè)問題。
全書共分為9章，由淺入深、系統(tǒng)地討論了各種數(shù)據(jù)結(jié)構(gòu)的基本概念和相關(guān)操作，還介紹了查找和排序算法。各章的具體內(nèi)容介紹如下。
第1章是緒論，介紹了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的意義、數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，并且指出了數(shù)據(jù)結(jié)構(gòu)和算法之間的關(guān)系，給出了分析算法的方法。
第2章主要介紹了線性表的概念、抽象數(shù)據(jù)類型及其基本操作，最后列舉了一些線性表的應(yīng)用實(shí)例。
第1章 緒論 1
1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義 1
1.2 數(shù)據(jù)結(jié)構(gòu) 3
1.3 抽象數(shù)據(jù)類型 5
1.4 算法 6
1.5 算法分析 9
小結(jié) 15
自測題答案 16
編程項(xiàng)目 17
第2章 線性表 18
2.1 線性表的定義 18
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 22
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 29
2.4 線性表的應(yīng)用 43
小結(jié) 46
自測題答案 47
編程項(xiàng)目 48
第3章 棧和隊(duì)列 49
3.1 棧 49
3.2 棧的應(yīng)用 55
3.3 隊(duì)列 67
3.4 隊(duì)列的應(yīng)用 76
小結(jié) 79
自測題答案 79
編程項(xiàng)目 81
第4章 串 82
4.1 串的定義 82
4.2 串的存儲(chǔ)實(shí)現(xiàn) 84
4.3 串的模式匹配 88
小結(jié) 96
自測題答案 97
編程項(xiàng)目 98
第5章 數(shù)組及廣義表 99
5.1 數(shù)組的定義 99
5.2 數(shù)組的順序存儲(chǔ) 101
5.3 矩陣的壓縮存儲(chǔ) 104
5.4 廣義表 115
小結(jié) 122
自測題答案 123
編程項(xiàng)目 125
第6章 樹和二叉樹 126
6.1 樹的定義與基本操作 126
6.2 二叉樹 129
6.3 樹和森林 144
6.4 哈夫曼樹與哈夫曼編碼 149
小結(jié) 157
自測題答案 158
編程項(xiàng)目 160
第7章 圖 161
7.1 圖的定義 161
7.2 圖的存儲(chǔ)方式 166
7.3 圖的遍歷 175
7.4 圖的連通性 180
7.5 最小生成樹 184
7.6 最短路徑 189
7.7 有向無環(huán)圖的應(yīng)用 195
小結(jié) 204
自測題答案 205
編程項(xiàng)目 209
第8章 查找 210
8.1 線性表上的查找 210
8.2 樹上的查找 218
8.3 哈希表 241
小結(jié) 252
自測題答案 254
編程項(xiàng)目 257
第9章 排序 258
9.1 插入排序 258
9.2 交換排序 266
9.3 選擇排序 271
9.4 歸并排序 278
9.5 基數(shù)排序 281
9.6 各種內(nèi)部排序方法比較 283
9.7 外部排序 286
小結(jié) 292
自測題答案 293
編程項(xiàng)目 296
附錄 各章編程項(xiàng)目參考答案 297
參考文獻(xiàn) 391
第1章 緒 論
Data Structure + Algorithm=Program.
Nikiklaus Wirth (1976)
本章初步講解數(shù)據(jù)結(jié)構(gòu)與算法，主要明確為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、數(shù)據(jù)結(jié)構(gòu)與算法的基本概念以及如何進(jìn)行算法分析。
1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義
1.1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義
“為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？”這是每個(gè)初學(xué)者都會(huì)提出的問題，為了能更好地回答這個(gè)問題，首先來看下面兩個(gè)例子。
例1.1 八皇后問題。這是一個(gè)古老而著名的問題。該問題是19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。問題描述：在8×8格的國際象棋盤上擺放著8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
這個(gè)問題的求解過程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯技術(shù)求解。為了能得到合理的布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。為了方便起見，以四皇后為例，圖1.1給出了計(jì)算機(jī)存儲(chǔ)這些布局的方式。
新書資訊