《数据结构A》课程实验指导书Data Structure Course Design课程编号：学时：15 学分：1先修课程：程序设计基础、面向对象程序设计适用专业：计算机科学与技术、网络工程、软件工程一、实验目的《数据结构A》课程是计算机科学与技术及其相关专业的一门重要的专业基础课。
在课堂教学中，比较全面、概括性地讲述数据结构学科中一些基础性知识、重要概念及各种算法，通过该实验教学和学生的上机实践，将这些基础性知识、重要概念及各种算法，在计算机上编程实现，使学生能够达到以下实验教学目标：1.掌握计算机处理数据的基本方法；2.了解算法的时间及空间分析方法；3.能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法；4.通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。
二、上机实验总体要求1.每位同学准备一个实验本，上机前作好充分的准备工作，预习本次实验的内容，事先熟悉与实验有关的软硬件环境，编写好程序代码，供上机时使用。
2.实验时遵守实验室的规章制度，爱护实验设备，原则上每人固定实验设备，对于实验设备出现的问题，要及时向指导老师汇报。
3.编程序过程中要注意多存盘，避免由于死机等原因造成的不必要的重复录入。
4.内部文档要求：每个源文件和头文件都必须在文件首部的注释中注明设计者姓名，项目名（即我们的上机题目名），创建日期和最近一次修改日期。
包含main()函数的源文件必须在首部注释后另加一段注释，简要描述一下程序的目的和用到的主要数据结构。
文件注释格式如下：文件名称：项目名称：创建者：创建时间：最后修改时间：功能：文件中的函数名称和简单功能描述：文件中定义的全局变量和简单功能描述：文件中用到的他处定义的全局变量及其出处：与其他文件的依赖关系：◆每个类必须包含首部注释块，适度地描述这个类的目的。
类的首部注释应该紧挨着放在类的声明（一般在头文件里）前面。
类的注释格式如下：类名称：定义该类的目的：类属性：类中函数及功能：与其他类的关系（调用/被调用哪类对象中的什么函数）：◆每个函数必须有首部注释块，描述该函数的简要功能，每个参数的逻辑含义(包括它是输入还是输出或者输入/输出)，函数调用之前的预备条件，返回后的处理，返回值（如果有的话），该函数要调用到的函数列表（如果有）。
这些函数头注释可能和函数原型或函数实现放在一起。
应该注意到：这项要求不仅适合于单独的函数，同样适合于类的成员函数。
函数的注释格式如下：函数名称：函数功能描述：函数调用之前的预备条件：返回后的处理：返回值（如果有的话）：函数的输入参数：函数的输出参数：函数的抽象算法（伪码）：函数与其他对象中函数的调用和被调用关系：◆所有局部变量或常量的声明后应该简要说明一下他们的含义和用途。
◆主要的控制结构，例如循环或分支结构，应该在前面注明将要完成什么功能。
◆采用清晰一致的缩进格式和其他格式化风格（例如括号的定位）来提高代码可读性。
5.过程代码要求◆标识符名称（常量、变量、函数、类等等）应该具有描述性，便于理解。
◆要用到某个常数时，最好设置一个常量来代替这个数字。
◆采用枚举类型来表示内部标签和状态的分类。
◆任何情况下都不要用全局或文件范围变量。
但是允许采用全局范围内的类型定义（包括类定义）。
◆采用适当的途径传递函数参数。
当被调用函数需要修改实参的值时一般只采用引用传参。
当被调用函数只需改变形参（调用内部）而保持实参不变时采用传值传参。
◆采用string对象来存储字符串数据（除了单个字符），而不用字符数组来表示。
◆采用I/O流代替C风格的I/O。
6.面向对象的代码要求◆尽量采用类。
不要用成员函数来实现结构类型。
◆一般来讲，建议采用类模板来表示容器型结构，如列表、树等，以提高可重用性。
◆设计类时，每个类都具有比较好的完整性（即该类的数据成员和函数成员具有比较好的内聚性和一致性，不要把不相干的东西凑合在一起，也不要把相关的东西生生拆散）。
◆类的所有数据成员都应该是私有的。
◆很多情况下，类的某些成员函数应该也是私有的。
视情况而定。
◆所有访问型指针都尽可能加const修饰（以区别于引用型指针）。
◆如果一个类数据成员是一个指向动态分配内存的指针，要求写出析构函数来释放内存；并写出一个用于复制对象的构造函数（copy constructor），而且写出赋值操作的重载运算（assignment operator overload）。
◆仅当有必要时才采用继承机制。
◆尽量少使用MFC库中的类，可以适当地使用STL的类（但是，如果同学们对于最基本的数据结构，例如栈、队列等还不熟悉的情况下，还是尽量自己来编写基本类）。
如果要编图形界面，请尽量把与编译环境（如VC、C++ Builder）有关的类限制在少数几个文件中。
也就是说，尽量把算法部分和界面部分的源程序分割开来。
当然，string类例外，大多数情况下同学们可以用它来替代chat *类型。
三、上机实验报告提交要求按时完成各个实验，实验结束后应完成实验报告，并以打印或电子文档的形式提交。
实习报告内容参见各实验。
实验报告提交时打一个zip（或rar）压缩包，zip（或rar）压缩包文件名统一采用以下格式命名：班级-学号-姓名-实验题号-版本号.zip（或为：班级-学号-姓名-实验题号-版本号.rar）例：计算机科学与技术专业2002级1班学号为03的姓名是王三的学生的第4个实验的第1个版本的文件名为：jsj021-03-王三-4-1.zip（或为j021-03-王三-4-1.rar）。
各专业对应的缩写如下：(1)计算机科学与技术—jsj(2)信息安全—xa(3)网络工程—wl(4)软件工程—rjzip（或rar）压缩包中应含有：(1)readme.txt文件，把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。
(2)附加了足够注释的源程序以及相关的项目和资源文件。
四、实验安排实验一单链表操作（一）实验内容单链表的创建、合并和输出。
（二）实验目的1.熟悉用Visual C++进行程序设计的方法。
2.掌握单链表的创建、查找、插入和合并等运算。
（三）实验题目本实验要求实现以下功能：1.从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单链表，将该链表输出显示。
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.程序中使用的数据结构及符号说明。
3.程序的主要流程图。
4.程序主要模块的功能说明。
5.程序运行时的初值和运行结果。
6.源程序并附上注释。
7.收获及体会。
实验二二叉树操作（一）实验内容二叉树的建立和遍历。
（二）实验目的1.进一步掌握指针变量的使用。
2.掌握二叉树的结构特征以及各种存储结构的特点及使用范围。
3.掌握用指针类型描述、访问和处理二叉树的运算。
4.掌握栈或队列的使用。
（三）实验题目本实验要求实现以下功能：1.按前序次序建立一棵二叉树，以‘＃’表示空。
2.中序、后序遍历该二叉树，输出遍历序列。
3.求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。
4.试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅助存储结构实现二叉树的层次遍历算法。
【测试数据】输入以下字符串，建立二叉树：ABC##DE#G##F###输出中序遍历序列应为：CBEGDFA输出后序遍历序列应为：CGEFDBA输出二叉树的深度应为：5输出二叉树的叶子数目应为：3（四）实验报告1.实验题目。
2.程序中使用的数据结构及符号说明。
3.程序的主要流程图。
4.程序主要模块的功能说明。
5.程序运行时的初值和运行结果，画出该二叉树的形态。
6.源程序并附上注释。
7.收获及体会。
实验三图的操作（一）实验内容图的生成和图的遍历。
（二）实验目的1.掌握图的基本存储方法——邻接表和邻接矩阵。
2.熟练掌握图的两种遍历方法。
（三）实验题目本实验要求实现以下功能：1.以邻接矩阵或邻接表作为存储结构建立一个无向图。
2.按深度优先遍历该无向图，输出遍历序列。
3.按广度优先遍历该无向图，输出遍历序列。
【测试数据】无向图如下所示。
1.实验题目。
2.程序中使用的数据结构及符号说明。
3.程序的主要流程图。
4.程序主要模块的功能说明。
5.程序运行时的初值和运行结果，画出该无向图的形态，写出其邻接矩阵或邻接表。
6.源程序并附上注释。
7.收获及体会。
实验四查找操作（一）实验内容二叉排序树的建立、二叉排序树中结点的查找（二）实验目的1.熟悉二叉排序树的定义。
2.理解二叉排序树的建立过程。
3.掌握二叉排序树中查找结点的算法。
（三）实验题目本实验要求实现以下功能：1.对从键盘输入的顺序任意的若干个正整数建立一颗二叉排序树，以-1作为结束。
2.按先序、中序和后序遍历该二叉排序树，输出每种遍历的结果。
3.从键盘输入一个整数，在二叉排序树中查找，给出是否查找成功的结果。
【测试数据】输入序列：67 13 11 88 45 9 60 20 -1输出先序遍历序列应为：67 13 11 9 45 20 60 88输出中序遍历序列应为：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.理解快速排序算法。
（三）实验题目本实验要求实现以下功能：对从键盘输入的顺序任意的8个正整数，通过快速排序使之成为有序的序列。
输出每一趟排序的结果。
【测试数据】输入序列：49 38 65 97 76 13 50 27输出的每一趟排序的结果应为：初始序列: 49 38 65 97 76 13 50 27第1趟结果: 27 38 13 49 76 97 50 65第2趟结果: 13 27 38 49 76 97 50 65第3趟结果: 13 27 38 49 65 50 76 97第4趟结果:13 27 38 49 50 65 76 97（四）实验报告1.实验题目。