在新世紀計算機的高速發展和廣泛應用，使得計算機成為一門熱門專業，并迫切要求人們使用計算機來處理各項工作和日常事務。

“數據結構”是一門綜合性的計算機專業基礎課，它涉及數學、計算機軟件和計算機硬件等三方面的知識，與高級編程語言、離散數學和軟件工程有著密切聯系。學習本課程的目的就是形成一種如何將現實生活中的問題用計算機來解決的思路、方法。對于具體的問題，先對它進行分析，抽象出一個適當的數學模型，然后設計解此數學模型的相應算法，最后給出源程序，經過調整、測試得到最終結果。

本書采用C語言作為描述數據結構和算法的工具，利用了C語言的語言簡潔、緊湊，使用方便、靈活和生成目標代碼質量高，程序執行效率高等特點。還有一點就是C語言編寫的程序在C++中運行時程序本身不需要做很大的改動。

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

本教材的講授學時可為54至72學時，實踐學時可為16學時左右。教師可根據實際情況選講或不講目錄頁中帶*號的章節。

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

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

編者

2005年7月

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

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