数据结构实验指导书学生正式秋Word下载.docx
《数据结构实验指导书学生正式秋Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书学生正式秋Word下载.docx（65页珍藏版）》请在冰点文库上搜索。
（2）分析并确定要实现的功能是什么。
也就是说要对输入的数据进行什么样的处理。
对问题中描述的需要实现的功能，应避开算法（具体的实现方法）和所涉及的数据类型，仅需对所需完成的任务做出明确的定义。
（3）分析并确定处理后的结果如何显示。
这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据；
以及相应的输出结果。
（二）数据类型和系统设计
当需求分析结束，明确问题要求后，开始为编写程序设计合适的数据结构和算法。
本步骤分概要设计和详细设计两步实现。
概要设计指的是，对问题描述中涉及的操作对象定义相应的抽象数据类型，并设计合适的算法；
以及定义程序各个功能模块和模块之间的关系。
在这个过程中，要根据问题的功能需求综合考虑，设计时空复杂度最优的抽象数据结构和算法（注意：
实现提示和给出的部分代码中以及给出了建议）。
抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体，算法思想和过程明确有效，程序结构清晰、合理、简单和易于调试。
作为概要设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），主要模块的算法思想，并画出模块之间的调用关系图。
详细设计则定义相应的物理存储结构（抽象数据类型的物理实现）并写出各基本操作的伪码算法，以及主要模块算法的具体步骤。
详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，算法书写规范（采用文字性的步骤描述或者算法流程图的形式都行）。
在求精的过程中，应尽量避免陷入语言细节，不必过早描述辅助数据结构和局部变量。
（三）编码实现和静态检查
在实验过程中，题目中会给出程序的部分源代码，根据实习第二步的设计结果以及源代码的提示，编码实现程序的其余部分。
编码是把详细设计的结果进一步求精为程序设计语言程序。
对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。
写出编码的程序后，在上机（编译和调试）之前，认真的静态检查是必不可少的。
多数初学者在编好程序后处于以下两种状态之一：
一种是对自己的“精心作品”的正确性确信不疑；
另一种是认为纠查错误是编译器的工作。
这两种态度是极为有害的。
事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。
上机动态调试决不能代替静态检查，否则调试效率是极低的。
静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；
二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。
如果程序中逻辑概念清楚，后者将比前者有效。
（四）上机准备和上机调试
上机准备包括一下几个方面：
（1）熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。
（2）上机调试程序时要带一本高级语言教材或手册。
（3）掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。
“磨刀不误砍柴工”。
计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG调试程序。
上机调试程序时要带一本高级语言教材或手册。
调试最好分模块进行，自底向上，即先调试底层函数。
必要时可以另写一个调用驱动程序。
这种表面上的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。
在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。
调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想”，而应动手确定疑点，通过修改程序来证实它或绕过它。
调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。
（五）总结和整理实习报告
按照实习报告的格式完成整个实习报告。
同时总结和思考，回味设计的过程，体会调试的过程，总结编程中的收获，记录实习过程的体会，交流程序设计各个步骤的心得。
“学而不思则罔，思而不学则殆。
”在程序设计中，只有做到勤思考、善总结，才能不断进步。
实习报告规范
实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1．需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？
明确规定：
（1）输入的形式和输入值的范围；
（2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：
包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2．概要设计
说明本程序中用到的所有抽象数据类型的定义、算法的基本思想、主程序的流程以及各程序模块之间的层次（调用）关系。
3．详细设计
（1）实现概要设计中定义的所有数据类型（物理数据结构），对每个操作只需要写出伪码算法；
（2）算法的具体步骤；
（3）算法的时空分析和改进设想；
（4）画出函数的调用关系图。
（5）输入和输出的格式。
4．调试分析
调试过程中遇到的问题，以及如何解决的；
5．测试结果
根据实验提供的测试数据，列出你所编写的程序的测试结果。
6．用户使用说明（可选）
说明如何使用编写的程序，详细列出每一步的操作步骤。
7．实验心得（可选）
对实验设计与实现过程的回顾和分析，以及经验和体会。
8．附录（可选）
带注释的源程序。
如果是提交源程序电子版，只需列出程序文件名的清单。
实习报告样例1最大公因数
题目部分
背景
因数分解，求最大公因数和公倍数等问题都是数学中古老而又重要德问题，这些问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。
问题描述
两个整数的最大公因数是同时整除二者的最大整数。
试设计一个计算两个整数的最大公因数的程序。
基本要求
（1）用户输入两个正整数，其取值范围为（0，216），
（2）要求采用欧几里德算法，计算最大公因数。
测试数据
输入
7591035
输出
69
实现提示
（1）注意题目给出的正整数的取值范围，定义变量时，选择合适的数据类型。
（2）欧几里德算法计算最大公因数，编写成一个独立的函数，并注意该算法对两个数据的大小关系有要求，在设计函数的输入参数以及函数处理代码时要注意处理。
选作内容
（1）设计一个求取n个正整数的最大公因数的函数。
（2）如果用户输入的正整数的取值范围为（0,232）、（0,264），请设计求取两个大的正整数的最大公因数的函数。
源程序及填空部分
#include“stdio.h”
typedeflongelemtype;
//欧几里德算法计算最大公因数函数
elemtypegcd（elemtypeM,elemtypeN）
{
//填空
}
main（）
elemtypea,b,g;
//输入
printf（“\n本程序可以求取两个正整数的最大公因数\n”）;
printf（“\n请输入第一个正整数（注意输入的数要小于2100000000）：
”）;
scanf（“%ld”,&
a）;
printf（“\n请输入第二个正整数（注意输入的数要小于2100000000）：
b）;
g=gcd（a,b）;
//输出
printf（“\n两者的最大公因数是：
%ld”,g）;
实验报告部分
HUNANUNIVERSITY
课程实习报告
题目：
最大公因数
学生姓名
学生学号
专业班级
指导老师
完成日期
一、需求分析
1．本程序要求采用欧几里德算法，计算并输出用户输入的两个正整数的最大公因数。
2．两个正整数由用户通过键盘输入，其取值范围为（0，216）。
不对非法输入做处理，即假设输入都是合法的。
3．在Dos界面输出最大公因数。
4．测试数据
69
二、概要设计
抽象数据类型
为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。
算法的基本思想
根据题目要求，采用欧几里德算法计算两个正整数的最大公因数。
该算法的基本思想是辗转相除法。
设两数为a、b（b＜a），求它们最大公约数（a、b）的步骤如下：
1.a÷
b，令r为所得余数（0≤r＜b）
若r=0，算法结束；
b即为答案。
2.互换：
置a←b，b←r，并返回第一步。
程序的流程
程序由三个模块组成：
（1）输入模块：
完成两个正整数的输入，存入变量a和b中。
（2）计算模块：
设计一个最大公因数函数，elemtypegcd（elemtypeM,elemtypeN），两个整数作为函数参数，计算结果通过函数名返回。
（3）输出模块：
屏幕上显示计算的最大公因数。
三、详细设计
物理数据类型
题目要求输入的正整数的取值范围在（0，216）之间，为了能够存储，采用C语言中的长整型定义变量。
typedeflongelemtype
算法的具体步骤
欧几里德算法计算两个正整数的最大公因数的算法流程图如下
算法的时空分析
算法的运行时间依赖与确定余数序列有多长。
可以证明，在两次迭代后，余数最多是原始值的一半。
则迭代次数是2logN＝O（logN）。
输入和输出的格式
输入
本程序可以求取两个正整数的最大公因数//提示
请输入第一个正整数（注意输入的数要小于2100000000）：
//提示
等待输入
请输入第二个正整数（注意输入的数要小于2100000000）：
输出
//提示
两者的最大公因数是：
//输出结果的位置
四、调试分析
略。
五、测试结果
输入5015输出5
输入19891590输出3
六、用户使用说明（可选）
1、本程序的运行环境为DOS操作系统，执行文件为gcd.exe
2、运行程序时
提示输入两个整数
本程序可以求取两个正整数的最大公因数
两者的最大公因数是：
七、实验心得（可选）
略。
七、附录（可选）
Gcd.c主程序
实习报告样例2进制转换
机制转换是计算机实现计算的基本问题。
十进制数N和其他d进制数的转换是计算机实现计算的基本问题。
请编制一个满足下列要求的进制转换程序。
（1）用户输入一个非负的十进制整数，其取值范围为（0，216），
（2）打印输出与其等值的八进制数。
1000
1750
（1）利用求模取余法，N＝（Ndivd）×
d＋Nmodd公式实现。
（2）由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出正好相反，利用堆栈的后进先出的特性正好实现。
（1）设计一个能处理小数的进制转换程序。
（2）设计一个能处理负数的进制转换程序。
#include<
stdio.h>
malloc.h>
/*包含动态内存分配函数的头文件*/
typedefintElemType;
typedefstructNodeType{
ElemTypedata;
structNodeType*next;
}Node;
typedefstruct{
Node*top;
intlen;
}LinkStack;
voidInitStack（LinkStack*S）//构造一个空栈S。
S->
top=NULL;
len=0;
intStackEmpty（LinkStack*S）//若栈S为空栈，则返回TRUE，否则返回FALSE
if（S->
len==0）
return1;
else
return0;
//返回1表示TRUE，否则返回0表示FALSE
intPush（LinkStack*S,ElemTypee）//新元素e入栈
intPop（LinkStack*S,ElemType*e）//栈顶元素出栈，并以e返回其值
voidconversion（LinkStack*S,intN）//进制转换，保存（入栈）在S中
voiddisplay（LinkStack*S）//输出，把S中元素出栈，并显示
main（）
structLinkStack*LS;
intN;
intd;
LS=（LinkStack*）malloc（sizeof（LinkStack））;
//关键的初始化
scanf（"
%d"
&
N）;
InitStack（LS）;
conversion（LS,N）;
display（LS）;
进制转换
1．本程序要求对用户输入一个非负的十进制整数，打印输出与其等值的八进制数。
2．十进制整数由用户通过键盘输入，其取值范围为（0，28）。
3．在Dos界面输出其等值的八进制数。
1348
2504
为实现上述程序的功能，应以整数存储用户的输入。
为了实现求模取余法，利用堆栈保存计算的结果。
堆栈定义如下：
ADTstack
数据对象：
整数
基本操作：
InitStack（&
S）//构造一个空栈S。
StackEmpty（S）//若栈S为空栈，则返回TRUE，否则返回FALSE
Push（S，&
e）//新元素e入栈
Pop（&
S，&
e）//栈顶元素出栈，并以e返回其值
根据题目要求，用求模取余法，N＝（Ndivd）×
由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出正好相反，利用堆栈的后进先出的特性正好实现。
完成正整数的输入，存入变量N中。
（2）转换模块：
实现求模取余法，余数依次入堆栈中。
从堆栈中取数，并显示在屏幕上。
题目要求输入的正整数的取值范围在（0，28）之间，为了能够存储，变量N采用C语言中的int定义变量。
因为堆栈需存储的元素个数和十进制数N的大小直接相关，其长度变化很大，所以堆栈采用单链表来实现其物理数据结构。
堆栈的每个元素只需存储0－8的字符，所以栈中元素类型定义为字符型。
typedefintElemType
VoidInitStack（LinkStack*S）//构造一个空栈S。
top=NULL;
若S->
len==0//返回1表示TRUE，否则返回0表示FALSE
intPush（LinkStack*S，ElemTypee）//新元素e入栈
{
//分配新空间，建立一个新结点
L＝（Node*）malloc（sizeof（Node））;
若L＝＝NULL返回0表示FALSE；
入栈失败
L->
data=e;
L->
next=S->
top;
//插入
S->
top=L;
len++;
返回1表示TRUE，入栈成功
intPop（LinkStack&
S，ElemType*e）//栈顶元素出栈，并以e返回其值
若栈空，返回0表示FALSE；
出栈失败
*e=S->
top->
data;
L=S->
top=S->
next；
free（L）；
len--;
返回1表示TRUE，出栈成功
求模取余法流程图如下：
函数名conversion（*S,N）
输出的算法（函数Display（*S））：
栈顶元素出栈，转换为字符的Ascii码，然后用字符格式输出。
算法的执行，主要是每次N除8，以及入栈，出栈显示，由于采用链表实现，入栈和出栈的时间复杂度都是O
（1），那么进制转换的时间复杂度，主要由N的大小决定，具体来说是要除8几次，即8k>
=N。
由此可知上述设计的时间复杂度是O（log8N）。
函数的调用关系图
InitStack//堆栈初始化
输入十进制数N
Conversion（）//进制转换
Push//入堆栈
主程序
StackEmpty//判定栈空
Display（）//显示结果
Pop//出堆栈
本程序可以把输入的十进制数转换为八进制的数//提示
请输入十进制的正整数（注意输入的数要小于2100000000）：
八进制数数是：
1、本程序的运行环境为DOS操作系统，执行文件为conversion.exe
提示输入
本程序可以把输入的十进制数转换为八进制的数
八进制数数是：
conversion.c主程序
stack.h堆栈实现（数据结构）
DEVC++调试方法简介
一、DEVC++下的调试的几个基本步骤。
1.把“生成调试信息”设置为Yes。
方法如下：
Tools（工具）-->
CompilerOptions（编译器选项）-->
Settings（设置）
2.编译程序。
程序“编译”编译后会出来这个对话框。
点击“关闭”，关闭该按钮。
3.设置断点（Breakpoint）
把光标移动到您想暂停执行的那一行，按ctrl+F5，或者直接用鼠标点击下图红线标明的区域。
（如下图）
4.开始调试（Debug）
按F8开始调试，或者点击“调试”选项（Debug）后就弹出下拉菜单（如下图）。
如果您没有把“生成调试信息”设置为Yes，Dev-C++会提示说您的工程中没有调试信息。
点击Yes，Dev-C++会自动把“生成调试信息”设置为Yes，并且重新编译您的工程。
程序运行到断点处会暂停；
按F7执行当前行，并跳到下一行；
ctrl+F7跳到下一断点，shift+F4跳到光标所在行，并在该行设置断点。
注意一点。
比如。
设置的“断点”是printf语句处。
那执行只执行到scanf语句后就不会显示答案了。
如下图。
大家看到那蓝条，这是做什么的呢，这是因为设置的“断点”是printf语句后，但又显示不出答案。
如果想得到答案。
可以按左下角的。
“下一步”如下图。
5.查看变量的值
开始调试后，在图示区域按右键（如果您使用的是左手习惯，则是左键），选择“添加监测（AddWatch）”；
或者直接按F4。
在弹出窗口中输入您想查看的变量名，然后按确定（OK），就可以看到该变量的值：
用鼠标选择源文件中的变量名，然后按F4也可以查看变量的值，该变量会出现在左边的监测列表中：
如果在环境选项（EnvironmentOptions）中选择了“通过鼠标监测变量（Watchvariableundermouse）”，用鼠标指向您想要查看的变量一段时间，该变量也会被添加到监测列表中。
重要提示：
1）当您想查看指针指向的变量的值的时候，按F4，然后输入星号及指针的名字（如*pointer）。
如果没加*，看到的将会是一个地址，也就是指针的值。
2）有时，调试器（Debugger）可能不知道某个指针的类型，从而不能显示该指针指向的变量的值。
此时，我们需要手动输入该指针的类型。
按F4后，以*（type*）pointer形式输入。
例如，*（int*）pointer。
6.最后点击“停止执行”就退出调试了。
二、调式例子
下面这个程序，编译能正常通过，但是运行时计算结果无法显示，通过调式可以找出存在死循环。
stdlib.h>
intmain（intargc,char*argv[]）
inti=1,sum=0;
while（i<
=100）
sum+=i;
i++;
printf（"
1到10
升级会员 