数据结构与算法实验S1

1、安徽财经大学管工学院计算机系数据结构与算法实验报告实验1算法的时间复度和空间复杂度分析实验室：广学楼软件工程实验室实验日期:2015.3.2 周次、节次：第1周/周1第 1大节 班级： 13计科1学号：20132649姓名：江振平l 开发环境及工具：1. 实验软件系统配置：操作系统：windows 8开发工具：visual c+ 6.02. 硬件环境：主屏：intel core i53230m，2.6ghz内存：4.00gb 硬盘空间大小：750gb l 实验目的：1. 熟悉开发工具的编程环境。2. 熟悉算法语言并完成简单的算法。3. 熟悉c语言的语法，将算法上机编程实现。4. 区别算法和源程

2、序。5. 体会用不同算法解决同一个问题，体会存储结构不同对实现算法的影响。6. 学习对算法进行时空分析的基本方法。7. 了解评价一个算法的基本准则。一. 在下列题目中选择一个完成（可以多选）。选题1：试编写求k阶（k>=2）裴波那契序列的第m项值的不同算法，并编程实现。k和m均以值调用的形式在函数参数中表现。要求：使用两种不同的算法（如，递推、递归等）。分析对比二种算法的时间复杂度、空间复杂度。提示：当k=2时，裴波那契序列的初始两项为0、1，此后序列的每个值都是前两项之和。当k=3时，裴波那契序列的初始三项为0、0、1，此后序列的每个值都是前三项之和，以此类推。可以先完成2 阶的，再完

3、成k阶的。选题2：试编写算法（递推算法）完成n行杨辉三角的输出，并编程实现。要求：先采用一维数组为存储结构实现，再采用二维数组为存储结构实现，对比分析二种算法的时间复杂度、空间复杂度。选题3：试编写算法求n！，并编程实现。要求：用递推和递归的方法分别实现。对比分析二种算法的时间复杂度、空间复杂度。二存储结构说明和定义： 数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。 任何一个算法的设计取决于选定的数据结构，

4、而算法的实现依赖于采用的存储结构。三主要算法概要3.1int main() int i;cin>>n; if(n<0) cout<<"n<0,错误"<<endl; /如果输入负数，则报错else for(i=1;i<=n;i+) s=s*i; cout<<n<<"!="<<s<<endl; return 0; /main3.2. long fac(int);/函数声明int main() int n; /n为需要求阶乘的整数long y; /y为存放n!

5、的变量cout<<"请输入数字：" cin>>n; /输入ny=fac(n);/调用fac函数求n!cout<<n<<"!="<<y<<endl;/输出n!的值return 0; long fac(int n)/递归函数 long f; if(n<0) cout<<"n<0,错误"<<endl; /输入负数时，报错并以-1作为返回值f=-1; else if (n=0|n=1) f=1; /0！和1！的值为1else f=fac

6、(n-1)*n;/n>1时，进行递归调用return f;/将f的值作为函数值返回4 程序运行结果截图：3.13.2五 本次实验的总结1. 分析自己的算法时间复杂试行空间复杂度。3.1的时间复杂度为t（n)=n3.2的时间复杂度为t（n)=n-12. 说明编程并上机调试实现算法时遇到的问题参数类型不对，导致数据溢出语句后漏掉分号导致编译错误3. 算法与源程序的书写有哪些不同？ 算法的书写使用的是一种“类c语言”的伪代码（介于自然语言和计算机语言之间的文字和符号）；而源程序的书写使用的是符合该编程语言规范的代码4. 对本次实验的完成情况自我评价并小结对程序设计相关的知识遗忘较多，编程时都是

7、对照着书本完成的；甚至有些内容可能时间久了，居然又搞不懂了，看来课后还要多花些时间把程序设计再看一遍，复习一下以前的所学，以便能够更好地学习数据结构等学科。六附录： （主要的源程序代码段落）请将源程序随报告一同打包备查！这里可以只给出主要的代码段并加上注释说明。七请列出你在实验中使用的参考资料：列举格式：书名资料名、作者、出版社、出版时间1. 数据结构实验教程（c语言版）、王国钧 唐国民、清华大学出版社、2009年9 月第1 版；2. 数据结构（用面向对象方法与c+描述）、殷人昆等、清华大学出版社、1999年7月附言：1. 本次实验所有文件（实验报告、源程序）放在以“学号姓名班级数据结构与算法实验s1”为名称的文件夹中，注意，学号放在名称前面，再打包成.rar的压缩格式。如“2011xxxx张三11计科2数据结构与算法实验s1.rar”，第二个实验报告文件名后缀改为s2，以此类推2. 报告在二周内提交，不要拖拉，以附件形式发到我的邮箱：bbwhs，主题标注“数据结构实验报告s1”字样。3. 请