在新世紀(jì)計(jì)算機(jī)的高速發(fā)展和廣泛應(yīng)用，使得計(jì)算機(jī)成為一門熱門專業(yè)，并迫切要求人們使用計(jì)算機(jī)來處理各項(xiàng)工作和日常事務(wù)。

“數(shù)據(jù)結(jié)構(gòu)”是一門綜合性的計(jì)算機(jī)專業(yè)基礎(chǔ)課，它涉及數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件等三方面的知識(shí)，與高級(jí)編程語言、離散數(shù)學(xué)和軟件工程有著密切聯(lián)系。學(xué)習(xí)本課程的目的就是形成一種如何將現(xiàn)實(shí)生活中的問題用計(jì)算機(jī)來解決的思路、方法。對(duì)于具體的問題，先對(duì)它進(jìn)行分析，抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)解此數(shù)學(xué)模型的相應(yīng)算法，最后給出源程序，經(jīng)過調(diào)整、測(cè)試得到最終結(jié)果。

本書采用C語言作為描述數(shù)據(jù)結(jié)構(gòu)和算法的工具，利用了C語言的語言簡(jiǎn)潔、緊湊，使用方便、靈活和生成目標(biāo)代碼質(zhì)量高，程序執(zhí)行效率高等特點(diǎn)。還有一點(diǎn)就是C語言編寫的程序在C++中運(yùn)行時(shí)程序本身不需要做很大的改動(dòng)。

本書是按照教材的體例編寫的，在內(nèi)容的組織和描述上遵循了學(xué)習(xí)的規(guī)律。其知識(shí)點(diǎn)與本科院校保持一致，注重學(xué)科體系完整性。全書共10章，布局上共分三大部分，主要以邏輯結(jié)構(gòu)為主線。第一部分：第1章，交代了學(xué)習(xí)本課程的意義、數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)及本課程的主體框架。第二部分：第2章、第3章、第4章、第5章、第6章和第7章，介紹了線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)三種結(jié)構(gòu)的特征、存儲(chǔ)結(jié)構(gòu)及各種操作的實(shí)現(xiàn)。第三部分：第8章、第9章和第10章，給出了典型的查找、排序算法和一些案例分析，應(yīng)用前面章節(jié)所學(xué)知識(shí)解決實(shí)際問題。每章都有小結(jié)，作為本章內(nèi)容的總結(jié)。除了總結(jié)每章還配有習(xí)題，分為選擇題、填空題、應(yīng)用題、寫算法和上機(jī)實(shí)踐題等多種題型。選擇題和填空題是對(duì)基本知識(shí)的考核，應(yīng)用題是對(duì)基本知識(shí)的應(yīng)用，寫算法題包含各章節(jié)中所學(xué)數(shù)據(jù)結(jié)構(gòu)的各種操作的實(shí)現(xiàn)，上機(jī)實(shí)踐題主要作為實(shí)踐環(huán)節(jié)內(nèi)容。通過多種類型的習(xí)題達(dá)到對(duì)本章所學(xué)知識(shí)鞏固的目的。

本教材的講授學(xué)時(shí)可為54至72學(xué)時(shí)，實(shí)踐學(xué)時(shí)可為16學(xué)時(shí)左右。教師可根據(jù)實(shí)際情況選講或不講目錄頁中帶*號(hào)的章節(jié)。

本書由斯慶巴拉主編，孫沛任副主編。各章主要編寫人員分工如下：第1章、第2章和第10章由斯慶巴拉編寫，第6章由孫沛編寫，第3章和第4章由劉威編寫，第5章和第7章由肖宏濤編寫，第8章和第9章由孫琦編寫。參與本書大綱討論、部分內(nèi)容編寫、實(shí)例程序調(diào)試等工作的還有安志遠(yuǎn)、李建義、李杰、王靜、王慧瑩、張保國(guó)、張宏偉等。

在本書的編寫過程中，閱讀了大量的參考資料，從中吸取了許多寶貴經(jīng)驗(yàn)，在此表示感謝。盡管已經(jīng)盡了最大的努力來避免錯(cuò)誤的發(fā)生，但限于水平和時(shí)間，書中不妥和錯(cuò)誤在所難免，懇請(qǐng)各位專家、讀者批評(píng)指正。筆者的E-mail為：siqing@nciae.edu.cn。

編者

2005年7月

序
前言
第1章 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的意義 1
本章學(xué)習(xí)目標(biāo) 1
1.1 實(shí)例：高校選修課程管理 1
1.1.1 問題描述 1
1.1.2 問題的分析 2
1.1.3 學(xué)習(xí)本課程的意義 3
1.2 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容 3
1.2.1 基本概念和術(shù)語 3
1.2.2 數(shù)據(jù)結(jié)構(gòu)定義 4
1.2.3 邏輯結(jié)構(gòu)的表示方法 5
1.3 算法和算法分析 7
1.3.1 算法定義 7
1.3.2 算法分析 8
本章小結(jié) 10
習(xí)題 10
第2章 線性表 14
本章學(xué)習(xí)目標(biāo) 14
2.1 實(shí)例：學(xué)生信息的存儲(chǔ) 14
2.1.1 問題描述 14
2.1.2 問題的分析 14
2.1.3 實(shí)現(xiàn)算法 15
2.2 線性表的邏輯結(jié)構(gòu) 16
2.2.1 線性表的邏輯結(jié)構(gòu) 16
2.2.2 線性表的基本操作 17
2.3 線性表的順序存儲(chǔ) 17
2.3.1 順序存儲(chǔ)方式 17
2.3.2 各種操作的實(shí)現(xiàn) 18
2.4 線性表的鏈?zhǔn)酱鎯?chǔ) 23
2.4.1 鏈?zhǔn)酱鎯?chǔ)方式 23
2.4.2 各種操作的實(shí)現(xiàn) 25
2.4.3 循環(huán)單鏈表 28
2.4.4 雙向鏈表 28
2.5 動(dòng)態(tài)存儲(chǔ)管理 30
2.5.1 存儲(chǔ)管理的任務(wù) 30
2.5.2 內(nèi)存的動(dòng)態(tài)分配和回收 31
2.6 應(yīng)用舉例：線性表的建立與合并 34
2.6.1 線性表的建立 34
2.6.2 線性表的合并 36
2.6.3 線性表的逆置 37
2.6.4 線性表各種操作的綜合實(shí)踐 39
本章小結(jié) 44
習(xí)題 45
第3章 棧和隊(duì)列 47
本章學(xué)習(xí)目標(biāo) 47
3.1 實(shí)例：藥店藥品柜的管理 47
3.1.1 問題描述 47
3.1.2 問題分析 47
3.2 邏輯結(jié)構(gòu)及特征 47
3.2.1 棧的基本概念 48
3.2.2 隊(duì)列的基本概念 49
3.3 棧的存儲(chǔ)結(jié)構(gòu) 50
3.3.1 棧的順序存儲(chǔ) 50
3.3.2 棧的鏈?zhǔn)酱鎯?chǔ) 52
3.4 隊(duì)列的存儲(chǔ)結(jié)構(gòu) 55
3.4.1 隊(duì)列的順序存儲(chǔ) 55
3.4.2 隊(duì)列的鏈?zhǔn)酱鎯?chǔ) 58
3.5 應(yīng)用舉例 61
3.5.1 表達(dá)式中的括號(hào)匹配的檢驗(yàn) 61
3.5.2 遞歸 61
3.5.3 棧和隊(duì)列的各種操作的綜合實(shí)踐 63
本章小結(jié) 67
習(xí)題 68
第4章 串 70
本章學(xué)習(xí)目標(biāo) 70
4.1 串類型的定義 70
4.2 串的存儲(chǔ)結(jié)構(gòu) 70
4.2.1 串的順序存儲(chǔ) 71
4.2.2 串的鏈?zhǔn)酱鎯?chǔ) 72
4.2.3 串的索引存儲(chǔ) 72
4.3 串的操作 73
4.3.1 串常用操作的實(shí)現(xiàn) 74
4.3.2 模式匹配操作 82
本章小結(jié) 87
習(xí)題 87
第5章 數(shù)組 89
本章學(xué)習(xí)目標(biāo) 89
5.1 數(shù)組 89
5.1.1 一維數(shù)組 89
5.1.2 多維數(shù)組 89
5.2 數(shù)學(xué)中的應(yīng)用 91
5.2.1 稀疏矩陣 91
*5.2.2 特殊矩陣 97
5.3 廣義表 99
5.3.1 基本概念 99
5.3.2 廣義表的存儲(chǔ)結(jié)構(gòu) 100
*5.3.3 廣義表的運(yùn)算 102
本章小結(jié) 107
習(xí)題 107
第6章 樹 110
本章學(xué)習(xí)目標(biāo) 110
6.1 實(shí)例1：文件目錄管理 110
6.1.1 問題描述 110
6.1.2 問題分析 110
6.1.3 實(shí)現(xiàn)算法 111
6.2 樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 112
6.2.1 樹的邏輯結(jié)構(gòu) 112
6.2.2 樹的相關(guān)術(shù)語 113
6.3 樹的遍歷 113
6.3.1 先根遍歷 114
6.3.2 后根遍歷 114
6.3.3 按層遍歷 114
6.4 實(shí)例2：通信中電文編碼 115
6.4.1 問題描述 115
6.4.2 問題分析 115
6.4.3 實(shí)現(xiàn)算法 116
6.5 二叉樹的定義和存儲(chǔ)結(jié)構(gòu) 117
6.5.1 二叉樹的定義 117
6.5.2 二叉樹的性質(zhì) 118
6.5.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 119
6.6 二叉樹遍歷 121
6.6.1 先根遍歷 121
6.6.2 中根遍歷 123
6.6.3 后根遍歷 124
6.6.4 按層遍歷 125
6.6.5 二叉樹遍歷的應(yīng)用 126
6.7 樹與二叉樹的轉(zhuǎn)換 127
6.7.1 樹的存儲(chǔ)結(jié)構(gòu) 127
6.7.2 樹與二叉樹的轉(zhuǎn)換 129
6.7.3 森林與二叉樹的轉(zhuǎn)換 131
6.8 應(yīng)用舉例 132
*6.8.1 線索二叉樹 132
6.8.2 二叉排序樹 134
6.8.3 哈夫曼樹 136
6.8.4 二叉樹的綜合實(shí)例 137
本章小結(jié) 141
習(xí)題 142
第7章 圖 146
本章學(xué)習(xí)目標(biāo) 146
7.1 實(shí)例：求城市間最短路徑 146
7.1.1 問題描述 146
7.1.2 問題分析 146
7.2 圖的邏輯結(jié)構(gòu)和特征 148
7.2.1 圖的邏輯結(jié)構(gòu) 148
7.2.2 圖的特征 149
7.3 圖的存儲(chǔ)結(jié)構(gòu) 151
7.3.1 鄰接矩陣 151
7.3.2 鄰接表 153
*7.3.3 十字鏈表 155
*7.3.4 邊集數(shù)組 156
*7.3.5 鄰接多重表 157
7.4 圖的遍歷 158
7.4.1 深度優(yōu)先搜索 158
7.4.2 廣度優(yōu)先搜索 159
7.5 最小生成樹 160
7.5.1 克魯斯卡爾算法 161
7.5.2 普里姆算法 163
7.6 應(yīng)用舉例 166
7.6.1 求源點(diǎn)到其余各頂點(diǎn)間的最短路徑 166
7.6.2 拓?fù)渑判?168
本章小結(jié) 172
習(xí)題 173
第8章 典型查找算法 176
本章學(xué)習(xí)目標(biāo) 176
8.1 實(shí)例：學(xué)生分配座位 176
8.1.1 問題描述 176
8.1.2 問題分析 176
8.1.3 實(shí)現(xiàn)算法 177
8.1.4 基本概念 178
8.2 靜態(tài)查找 178
8.2.1 順序查找 179
8.2.2 折半查找 179
8.2.3 分塊查找 182
8.3 動(dòng)態(tài)查找 183
8.3.1 二叉排序樹查找 183
8.3.2 二叉平衡樹 185
8.4 散列查找 186
8.4.1 散列存儲(chǔ)和散列函數(shù)的構(gòu)造方法 186
8.4.2 解決沖突的方法 188
8.4.3 散列查找實(shí)現(xiàn)算法和性能分析 190
本章小結(jié) 192
習(xí)題 193
第9章 典型排序算法 195
本章學(xué)習(xí)目標(biāo) 195
9.1 實(shí)例：統(tǒng)計(jì)學(xué)生成績(jī)表 195
9.1.1 問題描述 195
9.1.2 問題分析 196
9.1.3 實(shí)現(xiàn)算法 196
9.1.4 排序定義及相關(guān)概念 197
9.2 插入排序 198
9.2.1 直接插入排序 198
9.2.2 折半插入排序 199
*9.2.3 希爾排序 199
9.3 選擇排序 201
9.3.1 直接選擇排序 201
9.3.2 堆排序 202
9.4 交換排序 205
9.4.1 冒泡排序 205
9.4.2 快速排序 206
9.5 歸并排序和基數(shù)排序 208
9.5.1 歸并排序 208
*9.5.2 基數(shù)排序 211
9.6 比較各種內(nèi)排序方法 214
9.6.1 各種內(nèi)排序方法的比較 214
9.6.2 各種內(nèi)排序方法的選擇 215
9.7 外排序 216
9.7.1 外排序的基本過程 216
*9.7.2 多路歸并排序 217
本章小結(jié) 218
習(xí)題 219
第10章 案例分析 222
本章學(xué)習(xí)目標(biāo) 222
10.1 約瑟夫問題 222
10.1.1 問題描述 222
10.1.2 問題分析 222
10.1.3 函數(shù)設(shè)計(jì) 223
10.1.4 上機(jī)調(diào)試 224
10.2 迷宮求解 225
10.2.1 問題描述 225
10.2.2 問題分析 225
10.2.3 函數(shù)設(shè)計(jì) 226
10.2.4 上機(jī)調(diào)試 229
10.3 排隊(duì)問題 230
10.3.1 問題描述 230
10.3.2 問題分析 231
10.3.3 函數(shù)設(shè)計(jì) 231
10.3.4 上機(jī)調(diào)試 234
10.4 教學(xué)計(jì)劃中的課程編排 236
10.4.1 問題描述 236
10.4.2 問題分析 237
10.4.3 函數(shù)設(shè)計(jì) 237
10.4.4 上機(jī)調(diào)試 240
10.5 簡(jiǎn)單的學(xué)籍管理系統(tǒng) 241
10.5.1 問題描述 241
10.5.2 問題分析 242
10.5.3 函數(shù)設(shè)計(jì) 242
10.5.4 上機(jī)調(diào)試 246
本章小結(jié) 248
習(xí)題 249
參考文獻(xiàn) 250

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