数据结构实验与实训教程
2011-1
清华大学
邓文华 编
182
无
本书为独立学院三本《数据结构》一书的配套教材，结合独立学院三本的特点，在原来第2版的基础上进行了修改与补充。其任务是通过实践，让学生进一步掌握常用数据结构的基本概念及其不同的实现方法，并对在不同存储结构上实现不同的运算方法和技巧有所体会。本教材是专门针对独立学院三本学生的实际情况，为学习“数据结构”课程而编写的实验教材。本书共分成4部分：第一部分为概述，包括C语言的数据输入、结构体概念、函数的传址调用概念及预备知识实验；第二部分为基础实验部分，在内容安排上给出了11个实验，包括线性结构、树形结构（二叉树的二叉链表存储方式、结点结构、类型定义、基本运算及应用）、图形结构（图的两种存储结构的表示方法）、查找（顺序查找、树表查找、散列表查找的基本思想及存储、运算的实现）、排序（插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想及实现）以及数组和字符串的操作；第三部分为课程设计部分，包括航空客运订票系统、汉诺塔游戏程序、全屏幕编辑程序设计、旅游路线安排模拟系统、停车场管理及最小生成树Kruaskal6个综合性实验，这组实验的综合性比较强，此部分可作为《数据结构》课程的课程设计之用；第四部分安排了12套模拟试题及其参考解答，目的是为了帮助学生进一步巩固所学的理论知识。本教材具有以下几个特点：（1）每个实验题目都给出相应的C程序模板，在模板中填写关键语句或子程序即可上机运行，便于学生集中精力于主要的算法。（2）实验内容安排多样性。包括基础题和提高题，便于满足不同层次学生的需求。形式包括：给出程序框架要求填写关键算法的形式；给出类似函数要求独立编写程序的形式；给出主程序要求编写子程序的形式以及给出算法要求编写程序等形式。（3）第四部分安排了12套模拟试题，并给出详细的参考解答，有利学生的自学、复习。本书由邓文华任主编，胡智文任副主编。其中第二、三部分由邓文华修改、编写；第四部分由胡智文修改、编写；第一部分由毕保祥编写。全书由邓文华统稿。本书中的所有程序都在BorlandC++软件开发环境下调试运行通过。编写独立学院三本的教材是一项新的尝试，难免存在疏漏，恳请读者赐教指正。
本书是用于“数据结构”课程的辅助教材。根据教学内容及针对独立学院三本学生的实际情况，本书在内容编排上共分成4部分： 第一部分为概述，包括c语言的数据输入、结构体概念、函数的传址调用概念及预备知识实验； 第二部分为基础实验部分，给出了11个实验，包括线性结构、树形结构、图形结构、查找、排序以及数组和字符串等操作； 第三部分为课程设计部分，包括航空客运订票系统、汉诺塔游戏程序、全屏幕编辑程序设计、旅游路线安排模拟系统、停车场管理及最小生成树kruskal 6个综合性实验，此部分实验可作为数据结构的课程设计； 第四部分为满足教学和各类学生学习课程与考前复习的需要，安排了12套模拟试题，并给出了详细的解答。 本书内容丰富、概念清晰、实用性强。它与《数据结构》的主要内容紧密结合，可供普通高等院校计算机及相关专业学生学习、实验、课程设计与考前复习使用，也可供教师或其他专业技术人员参考。
第一部分 概述 预备知识 预备知识实验 预备知识实验参考答案 第二部分 基础实验 实验1 线性表的基本操作 实验2 链表的基本操作 实验3 栈的基本操作 实验4 队列的基本操作 实验5 数组的基本操作 实验6 字符串的基本操作 实验7 二叉树的基本操作 实验8 树的遍历和哈夫曼树 实验9 图的基本操作 实验10 排序 实验11 查找 基础实验参考答案 第三部分 课程设计实验 实验1 航空客运订票系统 实验2 汉诺塔游戏程序 实验3 全屏幕编辑程序设计 实验4 旅游路线安排模拟系统 实验5 停车场管理 实验6 最小生成树kruskal算法 第四部分 模拟试题 模拟试题1 模拟试题2 模拟试题3 模拟试题4 模拟试题5 模拟试题6 模拟试题7 模拟试题8 模拟试题9 模拟试题10 模拟试题11 模拟试题12 模拟试题参考答案 附录 附录a 实验报告参考规范 附录b borland c++上机基本操作 参考文献
插图：1.排序的基本概念排序（Sorting）是计算机程序设计中的重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的位置关系与排序前不一定能保持一致。若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。排序分为两类：内排序和外排序。
《数据结构实验与实训教程(第3版)》：案例驱动的教学模式，一线优秀教师担纲编写，立体化教学资源解决方案。
无