《數據結構案例教程（C/C++版）》依據高職學生學習的特點，經過長期高職教學實踐成型。全書包括數據結構與算法、線性表、棧和隊列、串、遞歸、樹、圖、查找和內排序9部分內容，剔除了數組、矩陣、廣義表、外排序和文件等內容，并將較難的內容編排到了“知識與技能擴展”部分，以供讀者作為選修內容學習。同時，對于實際工作中應用較少的知識點（如線段樹、并查集等）進行了精簡。
全書緊緊圍繞9部分內容，精心設計了9個有趣的“大話”形式的開場白，旨在通過輕快的類比，幫助學生宏觀理解對應的知識點。同時，每章均精選了相對應的經典案例，借助這些案例的講解和分析，使學生在解決問題的過程中逐步掌握結構設計與算法，并提高學生的通識素養和專業興趣。
《數據結構案例教程（C/C++版）》可作為高職學院和中職學校計算機相關專業的數據結構和算法教程，同時也可作為程序設計開發者和愛好者的學習參考用書。
數據結構是一門訓練編程思維、提高問題解決能力的課程。從謀生角度來看，其效果
可能不會立竿見影；但從長遠來看，思維培養比技能訓練對學生未來的發展更具深遠意義。
本書參考中國高職院校計算機教育課程體系提出的“新的教學三部曲：提出問題→
解決問題→歸納分析”設計全書架構；按照“目標→問題→任務→方法→結論→擴展”組
織目錄結構；并根據“定位準確、取舍合理”的指導思想，對課程內容進行了合理的調整
和改進。全書包括數據結構與算法、線性表、棧和隊列、串、遞歸、樹、圖、查找和內排
序9 部分內容，剔除了數組、矩陣、廣義表、外排序和文件等內容，并將較難的內容（如
KMP、Floyd 等算法）編排到了“知識與技能擴展”部分，以作為選修內容。此外，教材
中的程序盡量減少了對指針的使用；并對實際工作中應用得較少的知識點，如線段樹、并
查集、樹表查找等，進行了精簡。
全書緊緊圍繞這9 部分內容，精心設計了9 個有趣的“大話”形式的開場白，旨在通
過輕快的類比，幫助學生宏觀理解對應的知識點。同時，每章均精選了相對應的經典案例，
借助這些案例的講解和分析，既可以使學生在解決問題的過程中掌握結構設計方法與算法；
又能提高學生的通識素養和專業興趣。
考慮到高職三年的課程安排和面向對象的復雜性，本書特采用C++ 兼容方式編寫，
所提供的程序代碼均可在Visual C++ 6.0 和Visual Studio 2008/2010 等C++ 環境中運行。
本書由湖南信息職業技術學院的鄧銳主編，趙莉和朱清妍任副主編，參與教材編寫、
代碼測試和技術支持的還有彭順生、張四平、方麗和楊麗等。感謝學校同事和清華大學出
版社編輯部的朋友們，特別是朱英彪、賈小紅老師，你們是本書的支持者和首批讀者，感
謝你們提供的寶貴意見和建議；感謝峨眉山青天工作室的9 幅精美插圖創作；感謝軟件專
業的小伙伴們，特別是楊成、何聰、唐衡龍、曹志雄、郭軍宏、王小林等同學，正是與你
們的開心交流，才激發出這些“大話”素材，并促使我們不斷改進教學，在三尺講臺上享
受那充滿創造力的感覺。
本書是湖南省職業教育與成人教育學會科研規劃課題“高職計算機專業教材中引入‘大
話’模式研究”（XHB2013052）、湖南省職業教育“十二五”省級重點建設項目（高職
特色專業軟件技術）、湖南省職業院校生產性實習實訓基地項目、湖南省教育科學“十二五”
規劃課題“高職軟件技術專業在雙元課程體系模塊化的探究”（XJK012CZJ015）等項目
的階段性研究成果。
本書配有相應的教學資源，如案例源程序和相關視頻教學素材等，可以通過清華大
學出版社的教學資料網站（www.tup.tsinghua.edu.cn）下載，也可通過dengrui 2008@163.
com 或rkyyt@163.com 直接與作者聯系獲取，還可以通過“世界大學城”（http://www.
worlduc.com/UserShow/default.aspx?uid=212249） 或超星慕課（http://mooc.chaoxing.com/
mycourse/teachercourse?moocId=629135andclazzid=11770）訪問更多資源。
在編寫本書的過程中，參考了相關教材和參考書，但由于水平有限，書中不妥和疏漏
之處在所難免，希望廣大讀者批評指正。
編者
2014 年10 月
第1 章 數據結構與算法 ............................................................................................... 1
開場白 ..........................................................................................................................1
1.1 案例提出——高斯的巧妙解題 .........................................................................2
1.2 知識點學習 .........................................................................................................3
1.2.1 數據結構 ................................................................................................3
1.2.2 算法 ......................................................................................................12
1.2.3 數據結構+ 算法= 程序 ......................................................................17
1.3 案例問題解決 ...................................................................................................17
1.3.1 1787 年高斯算法——比較算法優劣 .................................................17
1.3.2 2014 年高斯算法——比較結構優劣 .................................................18
1.4 知識與技能擴展 ...............................................................................................18
課后習題 ....................................................................................................................19
上機實戰 ....................................................................................................................20
第2 章 線性表 ............................................................................................................. 22
開場白 ........................................................................................................................22
2.1 案例提出——約瑟夫與海盜 ...........................................................................23
2.2 知識點學習 .......................................................................................................23
2.2.1 線性表 ..................................................................................................23
2.2.2 線性表的順序存儲結構 ......................................................................25
2.2.3 線性表的鏈式存儲結構 ......................................................................30
2.2.4 靜態鏈表 ..............................................................................................42
2.3 案例問題解決 ...................................................................................................42
2.3.1 用順序表解決約瑟夫問題 ..................................................................43
2.3.2 用循環鏈表解決約瑟夫問題 ..............................................................44
2.4 知識與技能擴展 ...............................................................................................47
課后習題 ....................................................................................................................48
上機實戰 ....................................................................................................................48
第3 章 棧和隊列 ......................................................................................................... 50
開場白 ........................................................................................................................50
3.1 案例提出——迷宮問題 ...................................................................................51
3.2 知識點學習 .......................................................................................................52
3.2.1 棧 ..........................................................................................................52
3.2.2 隊列 ......................................................................................................63
3.3 案例問題解決 ...................................................................................................71
3.3.1 用棧來解決迷宮問題 ..........................................................................71
3.3.2 用隊列來解決迷宮問題 ......................................................................75
3.4 知識與技能擴展 ...............................................................................................79
課后習題 ....................................................................................................................80
上機實戰 ....................................................................................................................81
第4 章 串 ...................................................................................................................... 83
開場白 ........................................................................................................................83
4.1 案例提出——埃特巴什碼 ...............................................................................84
4.2 知識點學習 .......................................................................................................85
4.2.1 串的基本概念 ......................................................................................85
4.2.2 串的存儲結構 ......................................................................................86
4.2.3 串的模式匹配 ....................................................................................100
4.3 案例問題解決 .................................................................................................102
4.3.1 順序結構埃特巴什碼 ........................................................................102
4.3.2 鏈式結構埃特巴什碼 ........................................................................105
4.4 知識與技能擴展——KMP 算法 ...................................................................109
課后習題 ..................................................................................................................112
上機實戰 ..................................................................................................................113
第5 章 遞歸 ................................................................................................................ 115
開場白 ......................................................................................................................115
5.1 案例提出——驗證黃金分割 .........................................................................116
5.2 知識點學習 .....................................................................................................117
5.2.1 什么是遞歸 ........................................................................................117
5.2.2 遞歸調用的過程 ................................................................................120
5.2.3 遞歸算法的設計 ................................................................................120
5.3 案例問題解決——驗證黃金分割 .................................................................122
5.4 知識與技能擴展——遞歸轉換 .....................................................................123
課后習題 ..................................................................................................................125
上機實戰 ..................................................................................................................126
第6 章 樹 .................................................................................................................... 128
開場白 ......................................................................................................................128
6.1 案例提出——高效的電文編譯 .....................................................................129
6.2 知識點學習 .....................................................................................................129
6.2.1 樹的基本概念 ....................................................................................129
6.2.2 二叉樹 ................................................................................................136
6.2.3 哈夫曼樹 ............................................................................................153
6.3 案例問題解決 .................................................................................................158
6.4 知識與技能擴展——二叉樹遍歷非遞歸算法 .............................................162
課后習題 ..................................................................................................................169
上機實戰 ..................................................................................................................170
第7 章 圖 .................................................................................................................... 172
開場白 ......................................................................................................................172
7.1 案例提出——道路暢通與傷員急救問題的解決 .........................................173
7.2 知識點學習 .....................................................................................................175
7.2.1 圖的基本概念 ....................................................................................175
7.2.2 圖的存儲結構 ....................................................................................177
7.2.3 圖的遍歷 ............................................................................................183
7.2.4 最小生成樹 ........................................................................................187
7.2.5 有向無環圖及其應用 ........................................................................191
7.2.6 單源最短路徑——迪杰斯特拉算法 ................................................197
7.3 案例問題解決 .................................................................................................201
7.3.1 省政府“暢通工程”——普里姆算法 ............................................201
7.3.2 傷員急需運送——迪杰斯特拉算法 ................................................203
7.4 知識與技能擴展——弗洛伊德算法 .............................................................205
課后習題 ..................................................................................................................207
上機實戰 ..................................................................................................................208
第8 章 查找 ................................................................................................................ 210
開場白 ......................................................................................................................210
8.1 案例提出——詞典中查找單詞 .....................................................................211
8.2 知識點學習 .....................................................................................................211
8.2.1 查找的基本概念 ................................................................................211
8.2.2 線性表的查找 ....................................................................................212
8.2.3 樹表查找——二叉排序樹 ................................................................218
8.3 案例問題解決 .................................................................................................226
8.4 知識與技能擴展——哈希表查找 .................................................................227
課后習題 ..................................................................................................................231
上機實戰 ..................................................................................................................232
第9 章 內排序 ........................................................................................................... 234
開場白 ......................................................................................................................234
9.1 案例提出——光棍節的排序活動 .................................................................235
9.2 知識點學習 .....................................................................................................236
9.2.1 排序的基本概念 ................................................................................236
9.2.2 插入排序 ............................................................................................237
9.2.3 交換排序 ............................................................................................240
9.2.4 選擇排序 ............................................................................................244
9.2.5 歸并排序 ............................................................................................249
9.2.6 基數排序 ............................................................................................252
9.3 案例問題解決 .................................................................................................253
9.4 知識與技能擴展——各種內排序方法的比較和選擇 .................................256
課后習題 ..................................................................................................................257
上機實戰 ..................................................................................................................258
參考文獻 ........................................................................................................................ 260
新書資訊