版《数据结构A》课程实验指导书

1、数据结构A课程实验指导书 Data Structure Course Desig n 课程编号：06311360学时：15学分：1 先修课程：程序设计基础、面向对象程序设计 适用专业：计算机科学与技术、网络工程、软件工程 一、实验目的 数据结构A课程是计算机科学与技术及其相关专业的一门重要的专业基础 课。在课堂教学中，比较全面、概括性地讲述数据结构学科中一些基础性知识、重 要概念及各种算法，通过该实验教学和学生的上机实践，将这些基础性知识、重要 概念及各种算法，在计算机上编程实现，使学生能够达到以下实验教学目标： 1. 掌握计算机处理数据的基本方法； 2. 了解算法的时间及空间分析方法； 3.

2、 能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法； 4. 通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提 升。 二、上机实验总体要求 1. 每位同学准备一个实验本，上机前作好充分的准备工作，预习本次实验的内容， 事先熟悉与实验有关的软硬件环境，编写好程序代码，供上机时使用。 2. 实验时遵守实验室的规章制度，爱护实验设备，原则上每人固定实验设备，对 于实验设备出现的问题，要及时向指导老师汇报。 3. 编程序过程中要注意多存盘，避免由于死机等原因造成的不必要的重复录入。 4. 内部文档要求： 每个源文件和头文件都必须在文件首部的注释中注明设计者姓名，项目

3、名 (即我们的上机题目名)，创建日期和最近一次修改日期。包含 mai n()函数 的源文件必须在首部注释后另加一段注释，简要描述一下程序的目的和用到 的主要数据结构。文件注释格式如下： 文件名称： 项目名称： 创建者： 创建时间： 最后修改时间： 功能： 文件中的函数名称和简单功能描述： 文件中定义的全局变量和简单功能描述： 文件中用到的他处定义的全局变量及其出处： 与其他文件的依赖关系： 每个类必须包含首部注释块，适度地描述这个类的目的。类的首部注释应该 紧挨着放在类的声明（一般在头文件里）前面。类的注释格式如下： 类名称： 定义该类的目的： 类属性： 类中函数及功能： 与其他类的关系（调用

4、/被调用哪类对象中的什么函数）： 每个函数必须有首部注释块，描述该函数的简要功能，每个参数的逻辑含义 （包括它是输入还是输出或者输入/输出），函数调用之前的预备条件，返回后 的处理，返回值（如果有的话），该函数要调用到的函数列表（如果有）。这 些函数头注释可能和函数原型或函数实现放在一起。应该注意到：这项要求 不仅适合于单独的函数，同样适合于类的成员函数。函数的注释格式如下： 函数名称： 函数功能描述： 函数调用之前的预备条件： 返回后的处理： 返回值（如果有的话）： 函数的输入参数： 函数的输出参数： 函数的抽象算法（伪码）： 函数与其他对象中函数的调用和被调用关系： 所有局部变量或常量的声

5、明后应该简要说明一下他们的含义和用途。 主要的控制结构，例如循环或分支结构，应该在前面注明将要完成什么功能。 采用清晰一致的缩进格式和其他格式化风格（例如括号的定位）来提高代码 可读性 5. 过程代码要求 标识符名称（常量、变量、函数、类等等）应该具有描述性，便于理解。 要用到某个常数时，最好设置一个常量来代替这个数字。 采用枚举类型来表示内部标签和状态的分类。 任何情况下都不要用全局或文件范围变量。 但是允许采用全局范围内的类型 定义（包括类定义）。 采用适当的途径传递函数参数。当被调用函数需要修改实参的值时一般只采 用引用传参。当被调用函数只需改变形参（调用内部）而保持实参不变时采 用传值

6、传参。 采用string对象来存储字符串数据（除了单个字符），而不用字符数组来表示。 采用I/O流代替C风格的I/O。 6. 面向对象的代码要求 尽量采用类。不要用成员函数来实现结构类型。 一般来讲，建议采用类模板来表示容器型结构，如列表、树等，以提高可重 用性。 设计类时，每个类都具有比较好的完整性（即该类的数据成员和函数成员具 有比较好的内聚性和一致性，不要把不相干的东西凑合在一起，也不要把相 关的东西生生拆散）。 类的所有数据成员都应该是私有的。 很多情况下，类的某些成员函数应该也是私有的。视情况而定。 所有访问型指针都尽可能加cons修饰（以区别于引用型指针）。 如果一个类数据成员是一

7、个指向动态分配内存的指针， 要求写出析构函数来 释放内存；并写出一个用于复制对象的构造函数（ copy constructor），而且 写出赋值操作的重载运算（ assignment operator overload。 仅当有必要时才采用继承机制。 尽量少使用MFC库中的类，可以适当地使用STL的类（但是，如果同学们对 于最基本的数据结构，例如栈、队列等还不熟悉的情况下，还是尽量自己来 编写基本类）。如果要编图形界面，请尽量把与编译环境（如VC、C+ Builder） 有关的类限制在少数几个文件中。也就是说，尽量把算法部分和界面部分的 源程序分割开来。当然，stri ng类例外，大多数情况下

8、同学们可以用它来替 代chat *类型。 三、上机实验报告提交要求 按时完成各个实验，实验结束后应完成实验报告，并以打印或电子文档的形式提 交。实习报告内容参见各实验。 实验报告提交时打一个zip （或rar）压缩包，zip （或rar）压缩包文件名统一采用 以下格式命名： 班级-学号-姓名-实验题号-版本号.zip （或为：班级-学号-姓名-实验题号-版本号.rar） 例：计算机科学与技术专业2002级1班学号为03的姓名是王三的学生的第4个实验 的第1个版本的文件名为：jsj021-03-王三-4-1.zip （或为j021-03-王三-4-1.rar）。 各专业对应的缩写如下： （1）计

9、算机科学与技术一jsj （2）信息安全一xa （3）网络工程一wl （4）软件工程一rj zip （或rar）压缩包中应含有： （1）readme.txt文件，把你的程序运行环境、编译运行步骤、程序功能等等简 单说明一下。 （2）附加了足够注释的源程序以及相关的项目和资源文件。 四、实验安排 实验一单链表操作 （一）实验内容 单链表的创建、合并和输出。 （二）实验目的 1. 熟悉用Visual C+进行程序设计的方法。 2. 掌握单链表的创建、查找、插入和合并等运算。 （三）实验题目 本实验要求实现以下功能： 1. 从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单链表, 将该链表

10、输出显示 2. 再从键盘输入顺序任意的5个整数，按有序插入的要求生成第二个有序单链 表，将该链表输出显示。 3. 将这两个有序单链表合并成一个有序单链表，要求使用两个单链表的原有空 间进行合并，将生成的有序单链表输出显示。 【测试数据】 输入第一组整数：23 45 11 78 34 输出的有序单链表应为：11，23, 34, 45，78 输入第二组整数：90 13 45 66 10 输出的有序单链表应为：10，13, 45, 66，90 合并两个单链表，输出合并后的结果应为： 10，11，13，23，34，45，45，66，78，90 （四）实验报告 1. 实验题目。 2. 程序中使用的数据结

11、构及符号说明。 3. 程序的主要流程图。 4. 程序主要模块的功能说明。 5. 程序运行时的初值和运行结果。 6. 源程序并附上注释。 7. 收获及体会。 实验二二叉树操作 （一）实验内容 二叉树的建立和遍历。 （二）实验目的 1. 进一步掌握指针变量的使用。 2. 掌握二叉树的结构特征以及各种存储结构的特点及使用范围 3. 掌握用指针类型描述、访问和处理二叉树的运算。 4. 掌握栈或队列的使用。 （三）实验题目 本实验要求实现以下功能： 1. 按前序次序建立一棵二叉树，以非表示空。 2. 中序、后序遍历该二叉树，输出遍历序列。 3. 求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。

12、 4. 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅助存储 结构实现二叉树的层次遍历算法。 【测试数据】 输入以下字符串，建立二叉树：ABC#DE#G#F# 输出中序遍历序列应为：CBEGDFA 输出后序遍历序列应为：CGEFDBA 输出二叉树的深度应为：5 输出二叉树的叶子数目应为：3 （四）实验报告 1. 实验题目。 2. 程序中使用的数据结构及符号说明。 3. 程序的主要流程图。 4. 程序主要模块的功能说明。 5. 程序运行时的初值和运行结果，画出该二叉树的形态。 6. 源程序并附上注释。 7. 收获及体会。 实验三图的操作 （一）实验内容 图的生成和图的遍历。 （二）实

13、验目的 1. 掌握图的基本存储方法一一邻接表和邻接矩阵。 2. 熟练掌握图的两种遍历方法。 （三）实验题目 本实验要求实现以下功能： 1. 以邻接矩阵或邻接表作为存储结构建立一个无向图 2. 按深度优先遍历该无向图，输出遍历序列。 3. 按广度优先遍历该无向图，输出遍历序列。 【测试数据】无向图如下所示 VI VI （四）实验报告 1. 实验题目。 2. 程序中使用的数据结构及符号说明。 3. 程序的主要流程图。 4. 程序主要模块的功能说明。 5. 程序运行时的初值和运行结果，画出该无向图的形态，写出其邻接矩阵或邻 接表。 6. 源程序并附上注释。 7. 收获及体会。 实验四查找操作 （一）

14、实验内容 二叉排序树的建立、二叉排序树中结点的查找 （二）实验目的 1. 熟悉二叉排序树的定义。 2. 理解二叉排序树的建立过程。 3. 掌握二叉排序树中查找结点的算法。 （三）实验题目 本实验要求实现以下功能： 1. 对从键盘输入的顺序任意的若干个正整数建立一颗二叉排序树，以-1作为结 束。 2. 按先序、中序和后序遍历该二叉排序树，输出每种遍历的结果。 3. 从键盘输入一个整数，在二叉排序树中查找，给出是否查找成功的结果。 【测试数据】 输入序列：67 13 11 88 45 9 60 20 -1 输出先序遍历序列应为： 67 13 11 9 45 20 60 88 输出中序遍历序列应为：

15、 9 11 13 20 45 60 67 88 输出后序遍历序列应为： 9 11 20 60 45 13 88 67 输入要查找的整数：45 输出查找结果：查找成功 输入要查找的整数：55 输出查找结果：查找失败 （四）实验报告 1. 实验题目。 2. 程序中使用的数据结构及符号说明。 3. 程序的主要流程图。 4. 程序主要模块的功能说明。 5. 程序运行时的初值和运行结果，画出该二叉排序树的形态。 6. 源程序并附上注释。 7. 收获及体会。 实验五内部排序操作 （一）实验内容 快速排序。 （二）实验目的 1. 熟悉各种内部排序算法的思想。 2. 理解快速排序算法。 （三）实验题目 本实验

16、要求实现以下功能：对从键盘输入的顺序任意的 8个正整数，通过快速排 序使之成为有序的序列。输出每一趟排序的结果。 【测试数据】 输入序列：49 38 65 97 76 13 50 27 输出的每一趟排序的结果应为： 初始序列：49 38 65 97 7613 50 27 第 1 趟结果：27 3813 49 76 97 50 65 第2趟结果：13 2738 497697 5065 第3趟结果：13 2738 496550 7697 第4趟结果:13 27 38 49 50 65 76 97 （四） 实验报告 1. 实验题目。 2. 程序中使用的数据结构及符- 号说明。 3. 程序的主要流程图

17、。 4. 程序主要模块的功能说明。 5. 写出程序运行时的初值和每- 一趟排序结果。 6. 源程序并附上注释。 7. 收获及体会。 制定人：施化吉 审定人: 批准人： 2012年12月8日 人与人之间的距离虽然摸不着，看不见，但的的确确是一杆实实在在的秤。真与假，善与恶，美与丑，尽在秤杆上可以看出；人心的大小，胸怀的宽窄，拨一拨秤砣全然知晓。 人与人之间的距离，不可太近 与人太近了，常常看人不清。一个人既有优点，也有缺点，所谓人无完人，金无赤足是也。初识时，走得太近就会模糊了不足，宠之；时间久了，原本的美丽之处也成了瑕疵，嫌之。 与人太近了，便随手可得，有时得物，据为己有，太过贪财；有时得人，

18、为己所用，也许贪色。贪财也好，贪色亦罢，都是一种贪心。 与人太近了，最可悲的就是会把自己丢在别人身上，找不到自己的影子，忘了回家的路。 这世上，根本没有零距离的人际关系，因为人总是有一份自私的，人与人之间太近的距离，易滋生事端，恩怨相随。所以，人与人相处的太近了，便渐渐相远。 人与人之间的距离也不可太远。 太远了，就像放飞的风筝，过高断线。 太远了，就像南徙的大雁，失群哀鸣。 太远了，就像失联的旅人，形单影只。 人与人之间的距离，有时，先远后近；有时，先近后远。这每次的变化之中，总是有一个难以忘记的故事或者一段难以割舍的情。 有时候，人与人之间的距离，忽然间近了，其实还是远；忽然间远了，肯定是

19、伤了谁。 人与人之间的距离，如果是一份信笺，那是思念；如果是一个微笑，那是宽容；如果是一句问候，那是友谊；如果是一次付出，那是责任。这样的距离，即便是远，但也很近。 最怕的，人与人之间的距离就是一句失真的谗言，一个不屑的眼神，一叠诱人的纸币，或者是一条无法逾越的深谷。这样的距离，即便是近，但也很远。 人与人之间最美的距离，就是不远不近，远中有近，近中有远，远而不离开，近而不相丢。 太远的距离，只需要一份宽容，就不会走得太远而行同陌人；太近的距离，只需要一份自尊，就不会走得太近而丢了自己。不远不近的距离，多像一朵艳丽的花，一首悦耳的歌，一首优美的诗。 人生路上，每个人的相遇、相识，都是一份缘，我们都是相互之间不可或缺的伴。 人与人之间的距离虽然摸不着，看不见，但的的确确是一杆实实在在的秤。真与假，善与恶，美与丑，尽在秤杆上可以看出；人心的大小，胸怀的宽窄，拨一拨秤砣全然知晓。 人与人之间的距离，不可太近 与人太近了，常常看人不清。一个人既有优点，也有缺点，所谓人无完人，金无赤足是也。初识时，走得太近就会模糊了不足，宠之；时间久了，原本的美丽之处也成了