•由淺入深，深入淺出

本教材在基本概念、基本理論闡述方面注重科學嚴謹。同時對新概念的引入均以應用實例開始，對各種基本算法描述盡量詳細，敘述清晰。

•循序漸進，通俗易懂

內容簡明，圖文并茂；案例講解通俗易懂；步驟詳盡，方便操作；知識點明確，方便查閱。

•資源開放，網站支撐

門戶網站提供教學內容、教學設計、教學資源、實踐教學、案例庫、在線考試等功能，方便師生利用網絡環境進行學習與交流。

隨著信息技術的發展和普及，作為高等教育的一種類型，高職高專教育更強調工程化和職業化教育——學生不僅應具有基本的專業理論知識，更重要的是應具有過硬的專業技能和工程能力。目前學生對數據結構知識的掌握和應用能力與企業用人的需求還存在很大差異，傳統的教學模式和教學內容無法滿足學生職業發展的需要。因此，有必要加強在校大學生對計算機編程能力的訓練，最終達到提高學生職業素質的目的。

鑒于此，編者聯合組織十余所院校的多位計算機教育一線專家及企業行業一線工程人員，共同編寫了這本《數據結構》（C語言版）（第三版）。

本書主要培養學生分析數據、組織數據的能力，告訴學生如何編寫效率高、結構好的程序。本書在內容的選取、概念的引入、文字的敘述以及例題和習題的選擇等方面，都力求遵循面向應用、結構合理、由淺入深、循序漸進、便于自學的原則，突出其實用性與應用性。

一、教材特色

 由淺入深，深入淺出

本書在基本概念、基本理論闡述方面注重科學嚴謹，同時對新概念的引入均以應用實例開始，對各種基本算法描述盡量詳細，敘述清晰。

 循序漸進，通俗易懂

內容簡明，圖文并茂；案例講解通俗易懂；步驟詳盡，方便操作；知識點明確，方便查閱。

 資源開放，網站支撐

門戶網站提供教學內容、教學設計、教學資源、實踐教學、案例庫、在線考試等功能，方便師生利用網絡環境進行學習與交流。

二、內容介紹與教學建議

全書共分9章。第1章主要講述數據結構和算法的基本概念。第2～7章分別講述線性表、棧和隊列、串、遞歸、樹和圖這幾種基本數據結構的特點、存儲方法和基本運算，書中安排了相當多的篇幅來介紹這些基本數據結構的實際應用。第8章和第9章講述查找和排序的基本原理與方法。各章中所涉及的數據結構與算法，均給予了C語言描述，以便于讀者鞏固和提高運用C語言進行程序設計的能力與技巧。

本書的內容結構如下：

第1章：主要介紹數據結構基礎知識；

第2章：主要介紹線性表；

第3章：主要介紹棧和隊列；

第4章：主要介紹串及其基本操作；

第5章：主要介紹遞歸；

第6章：主要介紹樹及二叉樹的基本操作；

第7章：主要介紹圖的基本操作；

第8章：主要通過案例的實現介紹查找方法基本操作；

第9章：主要通過案例的實現介紹排序方法及基本操作。

本書建議以理論課與實踐課相結合的方式進行講授，培養學生的實際動手能力。各院校可以根據自己的實際情況適當調整教學內容。

三、案例說明

 單一案例

包括驗證哥德巴赫猜想、順序表與鏈表的應用、棧與隊列的應用、迷宮問題、哈夫曼編碼應用等。

 綜合案例

包括成績管理系統、學生成績修改系統、排序系統等。

四、讀者對象

 高職高專計算機相關專業的學生；

 應用型本科院校計算機相關專業的學生；

 計算機相關專業培訓機構的學生；

 廣大計算機愛好者。

本書編寫團隊集中了武漢軟件工程職業學院計算機學院和企業行業的優勢力量，編者都是具有多年一線教學實踐經驗和工程經歷的資深專家。本書由工業和信息化職業教育教學指導委員會委員王路群教授主持并通覽全稿，庫波對本書的編寫思路與項目設計進行了總體策劃，參與編寫的還有曹靜、汪曉青、袁曉曦、秦培煜、郭俐、江駿、楊國勛、余恒芳、張克斌、張波。

本書在編寫的過程中得到了湖北省職教信息集團、武漢市服務外包行業協會、武漢佰均成技術股份有限公司、武漢支點信息技術有限公司、武漢數陣信息集成技術有限公司、武漢光谷科技技術股份有限公司、武漢厚薄信息技術有限公司、武漢軟帝信息技術有限公司、武漢優易酷科技有限公司、上海睿亞訊軟件技術服務有限公司、武漢軟件工程職業學院、武漢商學院、武漢信息傳播職業技術學院的大力支持，在此表示衷心的感謝！

由于時間倉促，水平有限，書中難免有疏漏之處，敬請廣大讀者不吝指正。

編 者

2015年6月

再版前言
課程導學

第1章 緒論 1
1.1 引言 1
1.2 數據結構的發展簡史及其在計算機科學中
所處的地位 2
1.3 什么是數據結構 3
1.4 基本概念和術語 4
1.5 算法和算法的描述 6
1.5.1 算法 6
1.5.2 算法的描述 6
1.5.3 算法評價 9
1.6 實訓項目一 驗證哥德巴赫猜想 11
本章小結 13
習題一 13
第2章 線性表 14
2.1 線性表的邏輯結構 14
2.2 線性表的順序存儲結構 16
2.2.1 線性表的順序存儲結構 16
2.2.2 線性表在順序存儲結構下的運算 17
2.3 線性表的鏈式存儲結構 20
2.3.1 線性鏈表 21
2.3.2 循環鏈表 28
2.3.3 雙向鏈表 30
2.4 一元多項式的表示及相加 33
2.5 實訓項目二 順序表與鏈表的應用 35
本章小結 37
習題二 37
第3章 棧和隊列 39
3.1 棧 39
3.1.1 棧的定義及其運算 39
3.1.2 棧的順序存儲結構 40
3.1.3 多棧共享鄰接空間 42
3.1.4 棧的鏈式存儲結構 44
3.2 算術表達式求值 46
3.3 隊列 50
3.3.1 隊列的定義及其運算 51
3.3.2 隊列的順序存儲結構 51
3.3.3 隊列的鏈式存儲結構 56
3.3.4 其他隊列 57
3.4 實訓項目三 棧與隊列的應用 58
本章小結 60
習題三 61
第4章 串 63
4.1 串的基本概念 63
4.1.1 串的定義 63
4.1.2 主串和子串 64
4.2 串的存儲結構 64
4.2.1 串值的存儲 64
4.2.2 串名的存儲映像 67
4.3 串的基本運算及其實現 67
4.3.1 串的基本運算 67
4.3.2 串的基本運算及其實現 68
4.4 文本編輯 70
4.5 實訓項目四 成績管理系統 72
本章小結 80
習題四 81
第5章 遞歸 82
5.1 遞歸的定義 82
5.2 階乘問題 84
5.3 背包問題 87
5.4 漢諾塔問題 92
5.5 實訓項目五 迷宮問題 101
本章小結 110
習題五 110
第6章 樹 112
6.1 樹的結構定義與基本操作 112
6.1.1 樹的定義及相關術語 112
6.1.2 樹的存儲結構 113
6.1.3 樹的基本操作 114
6.2 二叉樹 115
6.2.1 二叉樹的定義與基本操作 115
6.2.2 二叉樹的性質 117
6.2.3 二叉樹的存儲結構 119
6.2.4 樹與二叉樹的相互轉換 121
6.3 遍歷二叉樹 122
6.3.1 先序遍歷 123
6.3.2 中序遍歷 123
6.3.3 后序遍歷 124
6.3.4 層次遍歷 125
6.3.5 遍歷算法的應用 125
6.4 線索二叉樹 127
6.4.1 中序次序線索化算法 129
6.4.2 在中根線索樹上檢索某結點的
前驅算法 130
6.4.3 在中根線索樹上檢索某結點的
后繼算法 130
6.5 二叉排序樹 131
6.5.1 二叉排序樹的定義 131
6.5.2 二叉排序樹的生成 132
6.5.3 刪除二叉排序樹上的結點 133
6.6 哈夫曼樹和哈夫曼算法 134
6.6.1 哈夫曼樹的定義 134
6.6.2 構造哈夫曼樹—哈夫曼算法 136
6.6.3 哈夫曼樹的應用 136
6.7 實訓項目六 哈夫曼編碼應用 139
本章小結 142
習題六 143
第7章 圖 144
7.1 基本定義和術語 144
7.2 圖的存儲結構 148
7.2.1 鄰接矩陣 148
7.2.2 鄰接表 150
7.3 圖的遍歷 153
7.3.1 深度優先遍歷 153
7.3.2 廣度優先遍歷 156
7.4 最小生成樹 158
7.5 最短路徑 164
7.5.1 單源點最短路徑 164
7.5.2 所有頂點對之間的最短路徑 167
7.6 拓撲排序 170
7.7 實訓項目七 無向圖的遍歷 172
本章小結 176
習題七 177
第8章 查找 179
8.1 順序查找 179
8.2 折半查找 181
8.3 分塊查找 184
8.4 哈希表 186
8.4.1 哈希表和哈希函數的概念 186
8.4.2 哈希函數的構造方法 187
8.4.3 沖突處理 190
8.5 實訓項目八 學生成績修改系統 194
本章小結 200
習題八 201
第9章 排序 202
9.1 插入排序 202
9.1.1 線性插入排序 202
9.1.2 折半插入排序 204
9.2 希爾排序 205
9.3 選擇排序 208
9.4 堆排序 209
9.5 快速排序 215
9.6 歸并排序 217
9.7 基數排序 220
9.8 外部排序 223
9.9 各種排序方法的比較 225
9.10 實訓項目九 排序系統 226
本章小結 233
習題九 234
參考文獻 235

1. C程序設計實踐教程 [劉衛國]
2. C程序設計（慕課版） [劉衛國]
3. 程序設計基礎實踐教程（C/C++語言版） [張桂芬 葛麗娜]
4. C++案例項目精講 [主編 楊國興]
5. SwiftUI完全開發 [李智威 著]
6. MySQL數據庫項目式教程 [陳亞峰]
7. C語言程序設計習題與實驗指導（第二版） [主編 甄增榮 張賓]
8. C語言程序設計（第二版） [主編 甄增榮 田云霞]
9. Unity3D虛擬現實應用開發實踐 [主 編 劉龍]
10. Python程序設計 [主編 姜春磊 陳虹潔]
11. C語言程序設計實踐教程（活頁式） [主編 鄭茵 陳巍 滕泓虬]
12. 面向對象程序設計 [主編 張勇 張平華 趙小龍]
13. 數據結構（Python語言描述） [曹岳輝　劉衛國　康松林　編著]
14. Python程序設計基礎及實戰 [主編　劉健]
15. C語言程序設計 [姜雪]
16. Python程序設計實踐教程 [王鶴琴 蔡正保]
17. C++程序設計實踐教程（第三版） [主編 劉衛國 曹岳輝]
18. C++程序設計（第三版） [主編 曹岳輝 劉衛國]
19. C語言程序設計項目化教程（活頁式） [主編 張利華 潘曉利]
20. 機器人流程自動化（RPA）實戰——基于UiPath [主編　金鑫]
21. Python 語言程序設計實踐指導 [主編　張雙獅]
22. Python程序設計案例教程 [主編 毛錦庚 鐘肖英 周賢來 ]
23. 基于.NET Core框架的分布式系統架構設計 [湯佳 著]
24. Python語言程序設計教程 [郭其標 房宜汕]
25. C語言同步案例習題精解 [主編 肖朝暉]
26. Python程序設計 [李國燕 王新強 劉佳 等編著]
27. Python程序設計項目化教程（活頁式） [主編　盧鳳偉]
28. Java編程基礎案例式教程 [主編 陳艷華 唐春蘭]
29. Python語言同步案例習題精解 [主編 肖朝暉]
30. Unity應用開發與實戰（微課版） [主 編 程永恒]