《2022版《资料结构A》课程实验指导书.docx》由会员分享，可在线阅读，更多相关《2022版《资料结构A》课程实验指导书.docx（13页珍藏版）》请在金锄头文库上搜索。
1、 2022版资料结构A课程实验指导书 data structure course design 课程编号：06311360学时： 15 学分：1 先修课程：程式设计基础、物件导向程式设计 适用专业：电脑科学与技术、网路工程、软体工程 一、实验目的 资料结构a课程是电脑科学与技术及其相关专业的一门重要的专业基础课。在课堂教学中，比较全面、概括性地讲述资料结构学科中一些基础性知识、重要概念及各种演算法，通过该实验教学和学生的上机实践，将这些基础性知识、重要概念及各种演算法，在计算机上程式设计实现，使学生能够达到以下实验教学目标： 1.把握计算机处理资料的根本方法； 2.了解演算法的时间及空间分析方
2、法； 3.能够为实际应用所涉及的资料选择适当的逻辑结构、储存结构及相应的演算法； 4.通过在计算机上程式设计实现课程中介绍的各种演算法，在程式设计力量方面得到提升。 二、上机实验总体要求 1.每位同学準备一个实验本，上机前作好充分的準备工作，预习本次实验的内容，事先熟识与实验有关的软硬体环境，编写好程式，供上机时使用。 2.实验时遵守实验室的规章制度，爱护实验装置，原则上每人固定实验装置，对于实验装置出现的问题，要及时向指导老师彙报。 3.程式设计序过程中要留意多存档，避开由于宕机等缘由造成的不必要的重複录入。 4.内部文件要求： 每个原始档和标头档案都必须在档案首部的注释中注明设计者姓名，专
3、案名（即我们的上机题目名），建立日期和最近一次修改日期。包含main()函式的原始档必须在首部注释后另加一段注释，简要描述一下程式的目的和用到的主要资料结构。档案注释格式如下： 档名称： 专案名称： 建立者： 建立时间： 最后修改时间： 功能：档案中的函式名称和简单功能描述： 档案中定义的全域性变数和简单功能描述： 档案中用到的他处定义的全域性变数及其出处： 与其他档案的依赖关係： 每个类必须包含首部注释块，适度地描述这个类的目的。类的首部注释应该紧挨着放在类的宣告（一般在标头档案里）前面。类的注释格式如下： 类名称： 定义该类的目的： 类属性： 类中函式及功能： 与其他类的关係（呼叫/被呼叫
4、哪类物件中的什么函式）： 每个函式必须有首部注释块，描述该函式的简要功能，每个引数的逻辑含义(包括它是输入还是输出或者输入/输出)，函式呼叫之前的预备条件，返回后的处理，返回值（假如有的话），该函式要呼叫到的函式列表（假如有）。这些函式头注释可能和函式原型或函式实现放在一起。应该留意到： 这项要求不仅适合于单独的函式，同样适合于类的成员函式。函式的注释格式如下： 函式名称： 函式功能描述： 函式呼叫之前的预备条件： 返回后的处理： 返回值（假如有的话）： 函式的输入引数： 函式的输出引数： 函式的抽象演算法（伪码）： 函式与其他物件中函式的呼叫和被呼叫关係： 全部区域性变数或常量的宣告后应该简
5、要说明一下他们的含义和用途。 主要的掌握结构，例如迴圈或分支结构，应该在前面注明将要完成什么功能。 採用清楚全都的缩排格式和其他格式化风格（例如括号的定位）来提高可读性。 5.过程要求 识别符号名称（常量、变数、函式、类等等）应该具有描述性，便于理解。 要用到某个常数时，最好设定一个常量来代替这个数字。 採用列举型别来表示内部标籤和状态的分类。 任何情况下都不要用全域性或档案範围变数。但是允许採用全域性範围内的型别定义（包括类定义）。 採用适当的途径传递函式引数。当被呼叫函式需要修改实参的值时一般只採用引用传参。当被呼叫函式只需改变形参（呼叫内部）而保持实参不变时採用传值传参。 採用strin
6、g物件来储存字串资料（除了单个字元），而不用字元阵列来表示。 採用i/o流代替c风格的i/o。 6. 物件导向的要求 儘量採用类。不要用成员函式来实现结构型别。 一般来讲，建议採用类别範本来表示容器型结构，如列表、树等，以提高可重用性。 设计类时，每个类都具有比较好的完整性（即该类的资料成员和函式成员具有比较好的内聚性和全都性，不要把不相干的东西凑合在一起，也不要把相关的东西生生拆散）。 类的全部资料成员都应该是私有的。 许多情况下，类的某些成员函式应该也是私有的。视情况而定。 全部访问型指标都儘可能加const修饰（以区别于引用型指标）。 假如一个类资料成员是一个指向动态安排记忆体的指标，要
7、求写出解构函式来释放记忆体；并写出一个用于複製物件的建构函式（copy constructor），而且写出赋值操作的过载运算（assignment operator overload）。 仅当有必要时才採用继承机制。 儘量少使用mfc库中的类，可以适当地使用stl的类（但是，假如同学们对于最根本的资料结构，例如栈、伫列等还不熟识的情况下，还是儘量自己来编写根本类）。假如要编图形介面，请儘量把与编译环境（如vc、c+ builder）有关的类限制在少数几个档案中。也就是说，儘量把演算法局部和介面局部的源程式分割开来。 当然，string类例外，大多数情况下同学们可以用它来替代chat *型别。
8、三、上机实验报告提交要求 按时完成各个实验，实验结束后应完成实验报告，并以列印或电子文件的形式提交。实习报告内容参见各实验。 实验报告提交时打一个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
9、 (4)软体工程rj zip（或rar）压缩包中应含有： (1)readme.txt档案，把你的程式执行环境、编译执行步骤、程式功能等等简单说明一下。 (2)附加了足够注释的源程式以及相关的专案和资原始档。 四、实验安排 实验一单连结串列操作 （一）实验内容 单连结串列的建立、合併和输出。 （二）实验目的 1.熟识用visual c+进行程式设计的方法。 2.把握单连结串列的建立、查询、插入和合并等运算。 （三）实验题目 本实验要求实现以下功能： 1.从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单连结串列，将该连结串列输出显示。 2.再从键盘输入顺序任意的5个整数，按有序插入的
10、要求生成其次个有序单连结串列，将该连结串列输出显示。 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
11、.程式主要模组的功能说明。 5.程式执行时的初值和执行结果。 6.源程式并附上注释。 7.收穫及体会。 实验二二叉树操作 （一）实验内容 二叉树的建立和遍历。 （二）实验目的 1.进一步把握指标变数的使用。 2.把握二叉树的结构特徵以及各种储存结构的特点及使用範围。 3.把握用指标型别描述、访问和处理二叉树的运算。 4.把握栈或伫列的使用。 （三）实验题目 本实验要求实现以下功能： 1.按前序次序建立一棵二叉树，以表示空。 2.中序、后序遍历该二叉树，输出遍历序列。 3.求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。 4.试以栈为辅助储存结构实现二叉树的前序非递迴演算法或以伫列为辅
12、助储存结构实现二叉树的层次遍历演算法。 【测试资料】 输入以下字串，建立二叉树：abc#de#g#f# 输出中序遍历序列应为：cbegdfa 输出后序遍历序列应为：cgefdba 输出二叉树的深度应为：5 输出二叉树的叶子数目应为：3 （四）实验报告 1.实验题目。 2.程式中使用的资料结构及符号说明。 3.程式的主要流程图。 4.程式主要模组的功能说明。 5.程式执行时的初值和执行结果，画出该二叉树的形态。 6.源程式并附上注释。 7.收穫及体会。 实验三图的操作 （一）实验内容 图的生成和图的遍历。 （二）实验目的 1.把握图的根本储存方法邻接表和邻接矩阵。 2.熟练把握图的两种遍历方法。
13、 （三）实验题目 本实验要求实现以下功能： 1.以邻接矩阵或邻接表作为储存结构建立一个无向图。 2.按深度优先遍历该无向图，输出遍历序列。 3.按广度优先遍历该无向图，输出遍历序列。 【测试资料】无向图如下所示。 （四）实验报告 1.实验题目。 2.程式中使用的资料结构及符号说明。 3.程式的主要流程图。 4.程式主要模组的功能说明。 5.程式执行时的初值和执行结果，画出该无向图的形态，写出其邻接矩阵或邻接表。 6.源程式并附上注释。 7.收穫及体会。 实验四查询操作 （一）实验内容 二叉排序树的建立、二叉排序树中结点的查询 （二）实验目的 1.熟识二叉排序树的定义。 2.理解二叉排序树的建立过程。 3.把握二叉排序树中查询结点的演算法。
