《数据结构案例教程（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