本书是配合计算机及相关专业“数据结构”课程而编写的。根据教学内容，并针对学生的实际情况，本教材在内容编排上共分三部分。第一部分为基础实验，给出了11个实验，包括线性结构、树型结构、图状结构、查找、排序，以及数组和字符串的操作。第二部分为综合实验，该部分实验的综合性比较强，可作为“数据结构”课程的课程设计，包括航空客运订票系统、迷宫问题、全屏幕编辑程序设计、旅游路线安排模拟系统和短信促销活动5个综合性实验。为了满足教学和各类学生学习与考前复习的需要，第三部分安排了10套模拟试题，并给出详细的解答。

本书内容丰富、概念清晰、实用性强，与“数据结构”课程的主要内容紧密结合，可供高职高专院校各专业学生学习、实验、课程设计和考前复习使用，也可供教师和其他专业技术人员参考。

数据结构实验与实训教程（第2版）本教材第一版自2004年出版发行以来，受到了广大师生、读者的热烈欢迎，至今已出版发行两万余册，在此对广大师生、读者表示衷心的感谢。为了更好地适应新形势的发展与需要，我们在广泛收集读者意见的基础上对本书进行了修订再版。本版在保留原版特点的基础上主要作了以下修改： 

 (1)  对原书的第二部分综合实验作了较大的调整。删除了通用函数曲线作图程序和保龄球记分系统，保留了迷宫问题、全屏幕编辑程序设计和短信促销活动，补充了航空客运订票系统与旅游路线安排模拟系统，使本部分的实验更具时代性与实用性。

 (2)  为了使本书能够自成体系，在第一部分基础实验中，每个实验均增加了基本知识与概念一节，使学生在做实验之前能够对理论部分有一个温故复习的机会。

 (3)  对第三部分模拟试题进行了修改与更新，使之更合理。

本教材中的所有程序都在Borland C++软件开发环境下调试运行通过。本书由邓文华、戴大蒙及梅志红编写，其中第一部分、第二部分及附录由邓文华老师和戴大蒙老师编写，第三部分由梅志红老师编写。浙江大学计算机学院孔繁胜教授任主审。本书的程序均由戴大蒙老师上机调试通过, 全书由邓文华老师最后修改定稿。

由于作者水平有限，本次修订错误和不当之处仍然在所难免，敬请广大读者批评指正。

编 者2007年4 月数据结构实验与实训教程（第2版）（第2版）前 言

数据结构实验与实训教程（第2版）数据结构课程是计算机专业中一门重要的专业基础课程。用计算机解决实际问题时，就要涉及数据的表示及数据的处理，而这正是数据结构课程的主要研究对象。通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。

要学好“数据结构”，仅仅通过课堂教学或自学获取理论知识是远远不够的，还必须加强实际动手训练。只有通过上机输入、编辑、检查、调试和运行已有的各种典型算法和已编写的程序，从成功和失败的经验中得到锻炼，才能熟练掌握和运用理论知识解决软件开发中的实际问题，达到学以致用的目的。

本书与《数据结构》一书配套使用，其目的是通过实践，进一步掌握常用数据结构的基本概念及其不同的实现方法，并对在不同存储结构上实现不同的运算方法和技巧有所体会。本教材主要是为学习“数据结构”课程而编写的实训教材。本书共分三部分，第一部分为基础实验，在内容安排上给出了11个实验，包括了线性结构（线性结构的定义、组织形式、结构特征和类型说明，以及在两种存储方式下实现的插入、删除和按值查找的算法，循环链表、双(循环)链表的结构特点和在其上的插入、删除等操作），树型结构（二叉树的二叉链表存储方式、结点结构和类型定义，二叉树的基本运算及应用），图状结构（图的两种存储结构的表示方法），查找（顺序查找、树表查找、散列表查找的基本思想及存储、运算的实现），排序（插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想及实现），以及数组和字符串的操作。第二部分为综合实验，这部分实验的综合性比较强，包括通用函数曲线作图程序、迷宫问题和全屏幕编辑程序设计等5个综合性实验，此部分可作为“数据结构”的课程设计。第三部分给出了10套模拟试题及其解答，目的是进一步巩固所学的理论知识。

本教材具有以下特点：  1. 每个实验题目都给出相应的C程序模板，在模板中填写关键语句或子程序即可上机通过，便于集中精力在算法上。

2. 实验内容多样性。习题包括基础题和提高题，以满足不同层次读者的需求。形式包括：给出程序框架要求填写关键算法，给出类似函数要求独立编写程序，给出主程序要求编写子程序，以及给出算法要求编写程序等。

3. 标准的编程风格，逐步培养良好的编程习惯。

本教材中的所有程序都在Borland C++软件开发环境下调试运行通过。本书由邓文华、戴大蒙和梅志红编写。其中第一部分、第二部分及附录由邓文华和戴大蒙老师编写，第三部分由梅志红老师编写；由浙江大学计算机学院孔繁胜教授审稿。本书的程序均由戴大蒙老师上机调试通过, 全书由邓文华老师最后修改定稿。

由于作者水平有限，加之编写时间仓促，错误和不当之处在所难免，敬请读者批评指正。

编 者2004年5 月数据结构实验与实训教程（第2版）（第1版）

第一部分 基础实验1

实验1 线性表的基本操作3

实验2 链表的基本操作10

实验3 栈的基本操作18

实验4 队列的基本操作26

实验5 数组的基本操作39

实验6 字符串的基本操作45

实验7 二叉树的基本操作52

实验8 树的遍历和Huffman树59

实验9 图的基本操作71

实验10 排序80

实验11 查找87

基础实验答案94

第二部分 综合实验107

实验1 航空客运订票系统109

实验2 迷宫问题116

实验3 全屏幕编辑程序设计130

实验4 旅游路线安排模拟系统143

实验5 短信促销活动148

第三部分 模拟试题159

模拟试题1161

模拟试题2167

模拟试题3171

模拟试题4174

模拟试题5178

模拟试题6184

模拟试题7188

模拟试题8192

模拟试题9197

模拟试题10202

模拟试题参考答案207

附录234

附录A 实验报告参考规范234

附录B Borland C++上机基本操作235

参考文献239

数据结构实验与实训教程（第2版）目  录