《[工学]数据结构实验指导书2011秋预备试验》由会员分享，可在线阅读，更多相关《[工学]数据结构实验指导书2011秋预备试验（34页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程实验指导书 1 目 录实习步骤 .2实习报告规范 .4实习报告样例 1 最大公因数 .5实习报告样例 2 进制转换 .11DEV C+ 调试方法简介 .18Visual C+6.0 调试方法简介 .24实验用书推荐 .28预备实验 1 字符串处理 .30预备实验 2 文件读取 .31预备实验 3 随机数生成 .32预备实验 4 递归函数 .33预备实验 5 字符串数组的查找 .34数据结构课程实验指导书 2 实习步骤（一）问题分析和任务定义在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什么。注意：本步骤强调的是做什么？而不是怎么做。主要完成三个方面的工
2、作：（1） 分析并确定问题要处理的对象（数据）是什么。例如：输入数据的类型、值的范围以及输入的形式。（2） 分析并确定要实现的功能是什么。也就是说要对输入的数据进行什么样的处理。注意：对问题中描述的需要实现的功能，应避开算法（具体的实现方法）和所涉及的数据类型，仅需对所需完成的任务做出明确的定义。（3） 分析并确定处理后的结果如何显示。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据；以及相应的输出结果。（二）数据类型和系统设计当需求分析结束，明确问题要求后，开始为编写程序设计合适的数据结构和算法。本步骤分概要设计和详细设计两步实现。概要设计指的是，对问题描述中涉及
3、的操作对象定义相应的抽象数据类型，并设计合适的算法；以及定义程序各个功能模块和模块之间的关系。在这个过程中，要根据问题的功能需求综合考虑，设计时空复杂度最优的抽象数据结构和算法（注意：实现提示和给出的部分代码中以及给出了建议） 。抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体，算法思想和过程明确有效，程序结构清晰、合理、简单和易于调试。作为概要设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明） ，主要模块的算法思想，并画出模块之间的调用关系图。详细设计则定义相应的物理存储结构（抽象数据类型的物理实现）并写出各基本操作的伪码算法，以及主
4、要模块算法的具体步骤。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，算法书写规范（采用文字性的步骤描述或者算法流程图的形式都行） 。在求精的过程中，应尽量避免陷入语言细节，不必过早描述辅助数据结构和局部变量。（三）编码实现和静态检查在实验过程中，题目中会给出程序的部分源代码，根据实习第二步的设计结果以及源代码的提示，编码实现程序的其余部分。编码是把详细设计的结果进一步求精为程序设计语言程序。对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之
5、前直接用键盘输入。写出编码的程序后，在上机（编译和调试）之前，认真的静态检查是必不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为纠查错误是编译器的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过 50 行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查） ；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效
6、。数据结构课程实验指导书 3 （四）上机准备和上机调试上机准备包括一下几个方面：（1） 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。（2） 上机调试程序时要带一本高级语言教材或手册。（3） 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。 “磨刀不误砍柴工” 。计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG 调试程序。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试底层函数。必要时可以另写一个调用驱动程序。这种表面上的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。在调
7、试过程中可以不断借助 DEBUG 的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想” ，而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。（五）总结和整理实习报告按照实习报告的格式完成整个实习报告。同时总结和思考，回味设计的过程，体会调试的过程，总结编程中的收获，记录实习过程的体会，交流程序设计各个步骤的心得。 “学而不思则罔，思而不学则殆。 ”在程序设计中，只有做到勤思考、善总结，才能不断进步。数据结构课程实验指导书 4 实习报告规范实习报告的开头应给出题目、班级、姓名、学
8、号和完成日期，并包括以下七个内容：1 需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：（1） 输入的形式和输入值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2 概要设计说明本程序中用到的所有抽象数据类型的定义、算法的基本思想、主程序的流程以及各程序模块之间的层次（调用）关系。3 详细设计（1） 实现概要设计中定义的所有数据类型（物理数据结构） ，对每个操作只需要写出伪码算法；（2） 算法的具体步骤；（3） 算法的时空分析和改进设想；（4） 画出函数的调用关系图。（5） 输入和输出的格
9、式。4 调试分析调试过程中遇到的问题，以及如何解决的；5 测试结果根据实验提供的测试数据，列出你所编写的程序的测试结果。6 用户使用说明（可选）说明如何使用编写的程序，详细列出每一步的操作步骤。7 实验心得（可选）对实验设计与实现过程的回顾和分析，以及经验和体会。8 附录（可选）带注释的源程序。如果是提交源程序电子版，只需列出程序文件名的清单。数据结构课程实验指导书 5 实习报告样例 1 最大公因数题目部分背景因数分解，求最大公因数和公倍数等问题都是数学中古老而又重要德问题，这些问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。问题描述两个整数的最大公因数是同时整除二者的最大
10、整数。试设计一个计算两个整数的最大公因数的程序。基本要求（1） 用户输入两个正整数，其取值范围为（0， 216） ，（2） 要求采用欧几里德算法，计算最大公因数。测试数据输入759 1035输出69实现提示（1） 注意题目给出的正整数的取值范围，定义变量时，选择合适的数据类型。（2） 欧几里德算法计算最大公因数，编写成一个独立的函数，并注意该算法对两个数据的大小关系有要求，在设计函数的输入参数以及函数处理代码时要注意处理。选作内容（1） 设计一个求取 n 个正整数的最大公因数的函数。（2） 如果用户输入的正整数的取值范围为（0, 232） 、 （0, 264） ，请设计求取两个大的正整数的最大
11、公因数的函数。源程序及填空部分#include “stdio.h”typedef long elemtype; /欧几里德算法计算最大公因数函数elemtype gcd (elemtype M, elemtype N)/填空main ()elemtype a, b, g;/输入printf(“n 本程序可以求取两个正整数的最大公因数 n”);printf(“n 请输入第一个正整数（注意输入的数要小于 2100000000）：”);scanf(“%ld”, printf(“n 请输入第二个正整数（注意输入的数要小于 2100000000）：”);scanf(“%ld”, 数据结构课程实验指导书 6 g=gcd(a, b);/输出printf(“n 两者的最大公因数是： %ld”, g);数据结构课程实验指导书 7 实验报告部分HUNAN UNIVERSITY课程实习报告题 目： 最大公因数 学 生 姓 名 学 生 学 号 专 业 班 级
