數(shù)據(jù)結(jié)構(gòu)

•講解精煉，突出實(shí)用。本書精選基礎(chǔ)理論內(nèi)容，降低了概念的抽象性和理論的難度，突出實(shí)用性，增加了數(shù)據(jù)結(jié)構(gòu)研究?jī)?nèi)容的應(yīng)用實(shí)例，抽象數(shù)據(jù)類型定義實(shí)例，并以具體實(shí)例說明算法的優(yōu)化等。

•結(jié)構(gòu)合理，重點(diǎn)突出。本書講述了數(shù)據(jù)結(jié)構(gòu)的重要內(nèi)容，體系結(jié)構(gòu)合理，重點(diǎn)難點(diǎn)突出，為方便讀者理解某些易產(chǎn)生疑問的知識(shí)點(diǎn)，還給出了額外的分析；每章節(jié)的例子和習(xí)題較為豐富；最后一章列舉了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)例，通過綜合訓(xùn)練，培養(yǎng)學(xué)生分析問題、解決問題、編程和動(dòng)手操作等多方面的能力。

•創(chuàng)新思維，培養(yǎng)能力。本書注重啟發(fā)創(chuàng)新思維，培養(yǎng)能力；概念準(zhǔn)確，邏輯性強(qiáng)；書中內(nèi)容都經(jīng)過編者深入研究，且在教學(xué)實(shí)踐中反復(fù)驗(yàn)證，因而較易理解，旨在提高學(xué)生的實(shí)際分析問題的能力和解決問題的能力，增強(qiáng)算法分析的能力。

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)中一門綜合性的專業(yè)基礎(chǔ)課。主要介紹如何合理地組織數(shù)據(jù)，有效地存儲(chǔ)和處理數(shù)據(jù)，正確地設(shè)計(jì)算法以及對(duì)算法的分析和評(píng)價(jià)。通過對(duì)本課程的學(xué)習(xí)，使學(xué)生深入透徹地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，培養(yǎng)基本的、良好的程序設(shè)計(jì)技能，編制高效可靠的程序，為學(xué)習(xí)操作系統(tǒng)、編譯原理和數(shù)據(jù)庫(kù)等課程奠定基礎(chǔ)。

目前，“數(shù)據(jù)結(jié)構(gòu)”不僅是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)基礎(chǔ)課程，而且大多數(shù)高等院校的非計(jì)算機(jī)專業(yè)也將“數(shù)據(jù)結(jié)構(gòu)”作為主干課程。“數(shù)據(jù)結(jié)構(gòu)”不僅是計(jì)算機(jī)專業(yè)考研的必考科目之一，還是全國(guó)計(jì)算機(jī)等級(jí)考試、軟件資格（水平）考試的主要考試內(nèi)容。

本書內(nèi)容豐富，邏輯性強(qiáng)，選材精練，圖文并茂，對(duì)基本理論的敘述深入淺出、通俗易懂，既注重理論知識(shí)，又強(qiáng)調(diào)工程實(shí)用，所精選的應(yīng)用實(shí)例涉及領(lǐng)域相當(dāng)廣泛，給讀者提供了思路與方法，有助于提高讀者分析問題和解決問題的能力。全書采用類C語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言，每章后進(jìn)行小結(jié)并配有適量習(xí)題，便于讀者掌握各章的重點(diǎn)和難點(diǎn)并進(jìn)行必要的訓(xùn)練，既便于教學(xué)，又便于自學(xué)。

本書主要內(nèi)容如下：

第1章：如果讀者剛接觸數(shù)據(jù)結(jié)構(gòu)，這一章將告訴您數(shù)據(jù)結(jié)構(gòu)是什么，以及本書的學(xué)習(xí)目標(biāo)、學(xué)習(xí)方法和學(xué)習(xí)內(nèi)容；另外，還介紹了本書對(duì)算法的描述方法。

第2章：主要介紹了線性表。首先講解線性表的邏輯結(jié)構(gòu)，然后介紹線性表的各種常用存儲(chǔ)結(jié)構(gòu)，在每一節(jié)均給出了算法的具體應(yīng)用。通過這一章的學(xué)習(xí)，讀者可以掌握順序表、動(dòng)態(tài)鏈表和靜態(tài)鏈表的操作。

第3章：主要介紹操作受限的線性表—棧和隊(duì)列，內(nèi)容包括棧的定義，棧的基本操作及棧與遞歸的轉(zhuǎn)化，隊(duì)列的概念，順序隊(duì)列和鏈?zhǔn)疥?duì)列的運(yùn)算。

第4章：主要介紹一種特殊的線性表—串，內(nèi)容包括串的概念，串的各種存儲(chǔ)表示，以及串的模式匹配算法。

第5章：主要介紹數(shù)組與廣義表，內(nèi)容包括數(shù)組的概念，數(shù)組（矩陣）的存儲(chǔ)結(jié)構(gòu)及運(yùn)算，幾種特殊矩陣；廣義表的概念，廣義表的兩種存儲(chǔ)方式，廣義表的操作實(shí)現(xiàn)。

第6章：主要介紹非線性數(shù)據(jù)結(jié)構(gòu)—樹和二叉樹，內(nèi)容包括樹和二叉樹的概念，樹和二叉樹的存儲(chǔ)表示，二叉樹的性質(zhì)，二叉樹的遍歷和線索化，樹、森林與二叉樹的轉(zhuǎn)換及哈夫曼樹。

第7章：主要介紹非線性數(shù)據(jù)結(jié)構(gòu)—圖，內(nèi)容包括圖的概念和存儲(chǔ)結(jié)構(gòu)、圖的遍歷、最小生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑及最短路徑。

第8章：主要介紹數(shù)據(jù)結(jié)構(gòu)的常用技術(shù)—查找。首先介紹查找的概念，然后結(jié)合具體實(shí)例介紹各種查找算法，并給出了完整程序。

第9章：主要介紹數(shù)據(jù)結(jié)構(gòu)的常用技術(shù)—排序。首先介紹排序的相關(guān)概念，然后介紹各種內(nèi)外排序技術(shù)，并給出了具體實(shí)現(xiàn)算法。

第10章：通過對(duì)本章的學(xué)習(xí)，可以復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本算法，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)系統(tǒng)開發(fā)的全過程，了解系統(tǒng)設(shè)計(jì)的一般要求；掌握文件包含處理的基本方法；提高程序編寫和程序調(diào)試的能力。

本書由西安文理學(xué)院韓利凱、朱浩悅擔(dān)任主編，高寅生、楊彩霖?fù)?dān)任副主編。其中第1章由李向軍編寫；第2章、第3章、第7章由韓旭編寫；第4章、第8章由朱浩悅編寫；第5章、第6章由王昭陽(yáng)編寫；第9章由劉光軍、韓利凱編寫；第10章由韓利凱編寫。

在教材編寫過程中，編者參考了國(guó)內(nèi)外眾多數(shù)據(jù)結(jié)構(gòu)與算法方面的優(yōu)秀教材，其中大多列舉在書后的參考文獻(xiàn)中。在此，我們對(duì)這些教材的編著者表示衷心感謝。

中國(guó)水利水電出版社的領(lǐng)導(dǎo)和編審老師給予本書編寫以很大的支持與細(xì)心指導(dǎo)，在此也表示衷心的感謝！

由于編者水平有限，時(shí)間倉(cāng)促，書中難免存在一些不足之處，殷切希望廣大讀者批評(píng)指正。

前言

第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容 1
1.2 基本概念和術(shù)語(yǔ) 4
1.2.1 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)和
數(shù)據(jù)對(duì)象 4
1.2.2 數(shù)據(jù)結(jié)構(gòu) 4
1.2.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 8
1.3 算法與數(shù)據(jù)結(jié)構(gòu) 12
1.3.1 數(shù)據(jù)結(jié)構(gòu)上的基本運(yùn)算 13
1.3.2 算法的定義及特性 14
1.3.3 算法分析 14
1.4 本章小結(jié) 25
習(xí)題1 26
第2章 線性表 29
2.1 線性表的概念及其抽象數(shù)據(jù)類型定義 29
2.1.1 線性表的邏輯結(jié)構(gòu) 29
2.1.2 線性表的抽象數(shù)據(jù)類型定義 30
2.2 線性表的順序存儲(chǔ) 31
2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu) 31
2.2.2 線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算 33
2.3 線性表的鏈?zhǔn)酱鎯?chǔ) 36
2.3.1 單鏈表 36
2.3.2 單鏈表上的基本運(yùn)算 37
2.3.3 循環(huán)鏈表 43
2.3.4 雙向鏈表 44
2.3.5 靜態(tài)鏈表 46
2.4 線性表應(yīng)用—一元多項(xiàng)式的表示
及相加 47
2.5 順序表與鏈表的綜合比較 50
2.5.1 順序表和鏈表的比較 50
2.5.2 線性表鏈?zhǔn)酱鎯?chǔ)方式的比較 51
2.6 本章小結(jié) 51
習(xí)題2 52
第3章 限定性線性表—棧與隊(duì)列 55
3.1 棧 55
3.1.1 棧的定義 55
3.1.2 棧的表示和實(shí)現(xiàn) 57
3.1.3 棧的應(yīng)用舉例 61
3.2 隊(duì)列 63
3.2.1 隊(duì)列的定義 63
3.2.2 隊(duì)列的表示和實(shí)現(xiàn) 65
3.2.3 隊(duì)列的應(yīng)用舉例 70
3.3 本章小結(jié) 73
習(xí)題3 74
第4章 串 76
4.1 串的基本概念 76
4.1.1 串的定義 76
4.1.2 串的基本操作 77
4.2 串的存儲(chǔ)實(shí)現(xiàn) 79
4.2.1 定長(zhǎng)順序串表示 79
4.2.2 堆分配存儲(chǔ)表示 82
4.2.3 串的鏈接存儲(chǔ)表示 84
4.2.4 子串定位運(yùn)算的實(shí)現(xiàn) 86
4.3 串的應(yīng)用舉例 88
4.4 本章小結(jié) 89
習(xí)題4 90
第5章 數(shù)組和廣義表 92
5.1 數(shù)組的定義與基本操作 92
5.1.1 數(shù)組的定義 92
5.1.2 數(shù)組的基本操作 93
5.2 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 93
5.2.1 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 93
5.2.2 數(shù)組的順序存儲(chǔ)的實(shí)現(xiàn) 95
5.3 特殊矩陣的壓縮存儲(chǔ) 96
5.3.1 規(guī)律分布的特殊矩陣 96
5.3.2 稀疏矩陣 98
5.4 廣義表 100
5.4.1 廣義表的概念 101
5.4.2 廣義表的存儲(chǔ)結(jié)構(gòu) 102
5.4.3 廣義表的操作實(shí)現(xiàn) 104
5.5 本章小結(jié) 106
習(xí)題5 106
第6章 樹與二叉樹 109
6.1 樹的定義與基本術(shù)語(yǔ) 109
6.2 二叉樹 111
6.2.1 二叉樹的定義與基本操作 112
6.2.2 二叉樹的性質(zhì) 112
6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 114
6.3 二叉樹的遍歷與線索化 116
6.3.1 二叉樹的遍歷 116
6.3.2 遍歷算法應(yīng)用 119
6.3.3 線索二叉樹 122
6.3.4 由遍歷序列確定二叉樹 126
6.4 樹、森林和二叉樹的關(guān)系 127
6.4.1 樹的存儲(chǔ)結(jié)構(gòu) 127
6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換 129
6.4.3 樹與森林的遍歷 132
6.5 哈夫曼樹及其應(yīng)用 134
6.5.1 哈夫曼樹 134
6.5.2 哈夫曼編碼 136
6.6 本章小結(jié) 138
習(xí)題6 138
第7章 圖 141
7.1 圖的定義與基本術(shù)語(yǔ) 141
7.1.1 圖的定義 141
7.1.2 圖的基本術(shù)語(yǔ) 141
7.2 圖的存儲(chǔ)結(jié)構(gòu) 143
7.2.1 鄰接矩陣表示法 143
7.2.2 鄰接表表示法 145
7.2.3 十字鏈表 146
7.2.4 鄰接多重表 148
7.3 圖的遍歷 149
7.3.1 深度優(yōu)先搜索 149
7.3.2 廣度優(yōu)先搜索 150
7.4 圖的應(yīng)用 152
7.4.1 圖的連通性問題 152
7.4.2 有向無環(huán)圖的應(yīng)用 156
7.4.3 最短路徑問題 160
7.5 本章小結(jié) 162
習(xí)題7 162
第8章 查找 164
8.1 查找的基本概念 164
8.2 順序查找法 165
8.3 折半查找法 166
8.4 散列表及其查找 169
8.4.1 常用的散列函數(shù) 170
8.4.2 處理沖突的方法 171
8.4.3 散列表的查找分析 175
8.5 本章小結(jié) 177
習(xí)題8 177
第9章 內(nèi)部排序 179
9.1 排序的概念 179
9.1.1 排序的穩(wěn)定性 179
9.1.2 排序用到的結(jié)構(gòu)與操作 179
9.2 插入排序 180
9.2.1 直接插入排序 180
9.2.2 直接插入排序復(fù)雜度分析 181
9.2.3 其他插入排序 181
9.3 交換排序 184
9.3.1 最簡(jiǎn)單的交換排序 184
9.3.2 冒泡排序 184
9.3.3 冒泡排序的優(yōu)化 185
9.3.4 快速排序 186
9.4 選擇排序 189
9.4.1 簡(jiǎn)單選擇排序 189
9.4.2 樹形選擇排序 190
9.4.3 堆排序 191
9.5 歸并排序 196
9.6 基數(shù)排序 196
9.6.1 多關(guān)鍵字排序 196
9.6.2 鏈?zhǔn)交鶖?shù)排序 197
9.7 內(nèi)部排序算法的分析和比較 198
9.8 本章小結(jié) 199
習(xí)題9 200
第10章 數(shù)據(jù)結(jié)構(gòu)課程實(shí)訓(xùn) 202
10.1 系統(tǒng)設(shè)計(jì)的要求 202
10.1.1 系統(tǒng)總體結(jié)構(gòu)設(shè)計(jì) 202
10.1.2 系統(tǒng)詳細(xì)設(shè)計(jì) 204
10.1.3 系統(tǒng)調(diào)試和維護(hù) 205
10.2 文件的包含處理 206
10.2.1 什么是文件包含 206
10.2.2 如何對(duì)“數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)系統(tǒng)”
進(jìn)行文件包含 208
10.2.3 “數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)系統(tǒng)”主控模塊 209
10.3 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 210
10.3.1 課程設(shè)計(jì)的目的 210
10.3.2 課程設(shè)計(jì)的內(nèi)容 210
10.3.3 課程設(shè)計(jì)報(bào)告 211
10.3.4 課程設(shè)計(jì)的考核 212
10.4 課程設(shè)計(jì)的要求 212
10.5 課程設(shè)計(jì)題目 213
參考文獻(xiàn) 220

1. 數(shù)據(jù)結(jié)構(gòu)（Python語(yǔ)言描述） [曹岳輝　劉衛(wèi)國(guó)　康松林　編著]
2. 數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言（微課版） [主編 梁海英]
3. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）習(xí)題解答及實(shí)訓(xùn)指導(dǎo) [李根強(qiáng) 謝月娥]
4. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [主編 李根強(qiáng) 劉浩 謝月娥]
5. 數(shù)據(jù)結(jié)構(gòu)（Java版） [主編 李云平]
6. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版） [主編 庫(kù)波 曹靜]
7. 數(shù)據(jù)結(jié)構(gòu)（Java版） [孫琳 張宇]
8. 數(shù)據(jù)結(jié)構(gòu) [許繪香 段明義]
9. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述） [李素若 陳萬華 游明坤 編著]
10. 數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及上機(jī)指導(dǎo) [李素若 琚輝 嚴(yán)永松 編著]
11. 數(shù)據(jù)結(jié)構(gòu)（C++描述）習(xí)題解答及實(shí)習(xí)指導(dǎo) [李根強(qiáng) 謝月娥 主編]
12. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）學(xué)習(xí)指導(dǎo)與習(xí)題解答 [趙堅(jiān) 姜梅 主編]
13. 數(shù)據(jù)結(jié)構(gòu) [陸勤 主編 ]
14. 數(shù)據(jù)結(jié)構(gòu)（C++描述） [李根強(qiáng) 主 編]
15. 數(shù)據(jù)結(jié)構(gòu)（C++版）--習(xí)題解答及實(shí)習(xí)指導(dǎo) [李根強(qiáng) 主編]
16. 數(shù)據(jù)結(jié)構(gòu)算法--Visual C++ 6.0程序集 [侯識(shí)忠 等編著]
17. 數(shù)據(jù)結(jié)構(gòu)算法--C++ Builder 6.0程序集 [侯識(shí)忠 等編著]
18. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）學(xué)習(xí)指導(dǎo)與習(xí)題解答 [趙堅(jiān) 姜梅 主編]
19. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [趙堅(jiān) 姜梅 主編]
20. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述） [斯慶巴拉 主編]
21. 數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版） [李根強(qiáng)]
22. 數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）習(xí)題解答及實(shí)訓(xùn)指導(dǎo) [李根強(qiáng)]
23. 數(shù)據(jù)結(jié)構(gòu)——用C語(yǔ)言描述 [蔡明志 編著]
24. 數(shù)據(jù)結(jié)構(gòu)（C++版） [李根強(qiáng) 主編]
25. 數(shù)據(jù)結(jié)構(gòu)--用C語(yǔ)言描述（第二版） [寧正元 易金聰 編著]
26. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述） [馬秋菊 主編]
27. 數(shù)據(jù)結(jié)構(gòu)（C/C++描述） [阮宏一 主編]
28. 數(shù)據(jù)結(jié)構(gòu)--C語(yǔ)言描述（第二版） [王路群 主編]
29. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用（Java語(yǔ)言描述） [[美]Sartaj Sahni（薩爾塔杰.薩]
30. 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)程序 [智東杰 主 編]