本书共分为16个数据结构实验，内容涵盖线性表、栈、队列、树、图、查询和排序，理论联系实际、深入浅出地给出了详细的解题思路，在强调基本理论的基础上，运用大量的实例来阐明数据结构与算法的应用，力求做到知识性、实用性和综合性的有机结合，方便读者灵活掌握并达到举一反三的效果。本书适合作为普通高等院校计算机信息类专业的数据结构、算法基础等课程的实验教材，也可作为成人数据结构与算法的培训教材以及编程爱好者的参考用书。

“数据结构”是计算机及相关专业的一门重要的专业基础课程，也是计算机专业一门必修的核心课程。在计算机科学、网络工程、大数据、人工智能和通信工程等领域，都会运用到数据结构的知识和方法，而且“数据结构”是大多数高等学校计算机专业研究生入学考试的必考科目，也是软件和电信企业入职考试的常考科目，所以学好这门课非常重要。
　　由于数据结构的原理和算法比较抽象，熟悉和掌握其相关的原理就比较困难，把数据结构的理论转化为实践的最简捷的方式就是进行上机编程实验，上机编程实验是理解原理的最佳途径。为了帮助读者更好地学习数据结构课程，编者根据多年的教学实践，收集和整理相关的材料后编写了本书。希望通过上机编程实验，读者能加强对数据结构理论的理解，能够举一反三地运用数据结构的知识分析和解决实际问题。
　　本书根据数据结构课程的培养方案，有针对性地设计了16个数据结构实验，每个实验都给出了程序项目的框架和部分源代码，避免了读者把大量的时间花费在琐碎的代码输入中，读者只需要设计核心的算法代码即可。每个实验都包括实验目的、实验环境、实验准备、实验要求、实验分析、代码实现和思考题这几部分，所有程序都可在Eclipse 4.9和Visual Studio 2010或2015环境下编译执行。通过这些实验，读者能够运用数据结构的知识去解决现实世界的一些实际问题。
　　本书适合作为高等学校计算机相关专业数据结构与算法课程的上机实验指导教材，也可以作为计算机相关专业自学考试、研究生入学考试、计算机等级考试（二级）和计算机技术与软件专业技术资格考试的考试辅导用书。
　　本书由陶骏、霍清华任主编，余婉风、李骏任副主编，周鸣争、张云玲和伍岳参与编写，全书由陶骏和霍清华负责统稿、定稿。其中：陶骏编写了实验10、实验11和实验16，霍清华编写了实验12、实验14和实验15，余婉风编写了实验1和实验2，李骏编写了实验3和实验4，周鸣争编写了实验5和实验6，张云玲编写了实验7和实验8，伍岳编写了实验9和实验13。在本书的编写过程中，得到了安徽信息工程学院计算机与软件工程学院、人工智能与大数据学院相关老师的大力协助，2016级本科生赵慧慧、2017级本科生杜敏和2018级本科生侯逸飞、应沈静同学对全部实验的代码做了验证查错，在此深表感谢。另外，本书得到2019芜湖市科技项目“基于北斗的ADS-B网络系统研制”（基金号：2019yf49）和安徽信息工程学院核心专业课程建设项目“数据结构与算法”（基金号：2018xjkcjs02）的资金资助。
　　由于时间仓促，编者水平有限，书中难免存在疏漏与不妥之处，恳请同行和读者批评指正。本书编者电子邮箱：1052537573@qq.com。实验代码分成学生和教师两部分，可以从中国铁道出版社有限公司的网站http://www.tdpress.com/51eds/下载。
　　
　　
　　 编 者
　　 2019年8月于安徽省芜湖市
　　

实验1 顺序表插入 1
实验目的 1
实验环境 1
实验准备 1
实验要求 2
实验分析 2
代码实现 4
思考题 10
实验2 顺序表合并 11
实验目的 11
实验环境 11
实验准备 11
实验要求 11
实验分析 12
代码实现 13
思考题 19
实验3 链表建立 21
实验目的 21
实验环境 21
实验准备 21
实验要求 24
实验分析 24
代码实现 24
思考题 29
实验4 循环链表分离 31
实验目的 31
实验环境 31
实验准备 31
实验要求 31
实验分析 32
代码实现 33
思考题 41
实验5　栈的应用：进制转换 42
实验目的 42
实验环境 42
实验准备 42
实验要求 43
实验分析 43
代码实现 44
思考题 50
实验6　栈的应用：括号匹配 52
实验目的 52
实验环境 52
实验准备 52
实验要求 52
实验分析 52
代码实现 54
思　考　题 61
实验7 队列的应用：约瑟夫环问题 62
实验目的 62
实验环境 62
实验准备 62
实验要求 65
实验分析 65
代码实现 66
思考题 74
实验8　二叉树的建立 75
实验目的 75
实验环境 75
实验准备 75
实验要求 77
实验分析 77
代码实现 77
思考题 82
实验9　求二叉树的非叶子结点个数 83
实验目的 83
实验环境 83
实验准备 83
实验要求 83
实验分析 83
代码实现 84
思考题 89
实验10 二叉树遍历（非递归） 90
实验目的 90
实验环境 90
实验准备 90
实验要求 90
实验分析 90
代码实现 92
思考题 99
实验11 树的建立和遍历 101
实验目的 101
实验环境 101
实验准备 101
实验要求 102
实验分析 102
代码实现 103
思考题 112
实验12 图的建立和遍历 113
实验目的 113
实验环境 113
实验准备 113
实验要求 114
实验分析 114
代码实现 115
思考题 124

实验13 求无向图的连通分量个数 126
实验目的 126
实验环境 126
实验准备 126
实验要求 126
实验分析 127
代码实现 127
思考题 141
实验14 查找应用：哈希表的构造 142
实验目的 142
实验环境 142
实验准备 142
实验要求 143
实验分析 143
代码实现 143
思考题 148
实验15 改进的冒泡排序 149
实验目的 149
实验环境 149
实验准备 149
实验要求 150
实验分析 150
代码实现 150
思考题 156
实验16 关键值为序列平均值的快速
排序 157
实验目的 157
实验环境 157
实验准备 157
实验要求 157
实验分析 157
代码实现 160
思考题 168

陶骏，男，安徽芜湖人，高级工程师，工学硕士，安徽信息工程学院网络工程教研室主任，主要研究方向为网络管理和网络安全，执教以来主要从事《计算机网络》、《信息安全》、《数据结构》和《Java程序设计》等课程的教学，发表论文10余篇，多次主持省市级科研和教研项目。 霍清华，女，工学硕士，安徽信息工程学院讲师。毕业于中国科学技术大学计算机科学与技术学院。执教以来主要从事《数据结构与算法》、《C语言程序设计》、《面向对象程序设计》等课程的教学，一直致力于数据结构与算法课程的教学改革工作，参与多个教学研究项目，发表教学研究论文若干篇。