数据结构与算法设计课程设计.doc

《数据结构与算法设计课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构与算法设计课程设计.doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构与算法设计课程设计数据结构实验报告一内江师范学院数据结构与算法设计课程设计实 验 报 告 册编制 算法设计课题组 审定 曾意专业： 信息与计算科学 班级： 2012 级 6 班学号： 20120241242 姓名： 杨浩天 数学与信息科学学院2014年9月-说 明1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软

2、件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告；2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D；3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告；4. 实验成绩评定分为A+、A、A-、B+、B、C、D各等级。根据实验准备、实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基

3、本符合、不符合、完全不符合。实验名称： 算法设计基础实验（实验一） 指导教师： 牟廉明，刘芳 实验时数： 4 实验设备：安装了VC+计算机实验日期： 年 月 日 实验地点： 第五教学楼北802实验目的：掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。实验准备：1. 在开始本实验之前，请复习相关实验内容；2. 需要一台准备安装Windows XP Professional操作系统和装有VC+6.0的计算机。实验内容：求n至少为多大时，n个1组成的整数能被2013整除。实验过程：1.1算法思想2013=61*33,6个1能够整除33，寻找满足n个1能够整除61的n即可。1.2 算法步骤

4、1.定义变量y储存余数，i储存1的个数，m为被除数，初始化为111111；2.如果被除数能够除尽61，输出i; 如果被除数不能够除尽61，while继续循环,m=y*1000000+111111,i+;3.重复2，直到找到满足条件的m为止，输出i;1.3算法实现（C+程序代码）#includeusing namespace std;int main() int y,m,i; i=6; m=111111; while(y!=0) m=y*1000000+111111; y=m%61; i=i+6; coutiendl; return 0;1.4 算法分析时间复杂度为O(n);实验总结（由学生填写

5、）：通过该实验发现，任何问题不要盲目的使用蛮力法，一定要化蛮力为巧力，这样既可以减少程序的时间复杂度，也能得到较精确的结果。并且在以后的解决问题的过程中，一定要多分析，多思考。 实验等级评定： 实验名称： 蛮力法实验分式化简（实验二） 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC+的计算机实验日期： 年 月 日 实验地点： 第五教学楼北802 实验目的：掌握蛮力法的基本思想和方法，熟悉搜索法的软件实现。实验准备：1在开始本实验之前，请回顾教材的相关内容；2需要一台准备安装Windows XP Professional操作系统和装有数学软件的计算机。实验内容：设计算法，将一个给定的

6、真分数化简为最简分数形式，例如，将6/8化简为3/4。实验过程：1.1算法思想首先对于普通整数；可以先利用欧几里得算法求出最大公约数，然后再讲分子分母用最大公约数作除，即可求出最简真分数。1.2 算法步骤输入：约分前的两个整数分子和分母输出：约分后的分子分母1.r=m%n;2.循环直到r=0;3.m=n;n=r;r=m%n;4.a/n;b/n;5.输出b/a;1.3算法实现（C+程序代码）#includeusing namespace std;int main() long int a, b, r;coutab;long int m=a;long int n=b;r = a % b;while

7、 (r!=0) a = b;b= r;r = a%b;a=m/b;b=n/b;cout原分数的最简分数为:b/aendl;return 0;1.4 算法分析时间复杂度为o(n).实验总结（由学生填写）： 此次实验较为简单，也较为基础。但需注意的是，即使是很简单的问题，也需要注意细节，尤其是在定义长整型的时候，不要单独的只定义为整型。 实验等级评定： 实验名称： 分治法实验循环移位（实验三） 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC+的计算机 实验日期： 年 月 日 实验地点：第五教学楼北802 实验目的：通过本次实验，让学生掌握分治法的基本思想和技巧，并学会如何用C+软件来实

8、现实验准备：1在开始本实验之前，请回顾教科书的相关内容；2需要一台准备安装Windows XP Professional操作系统和装有C+软件的计算机。实验内容：设计分治算法，实现将数组An中所有元素循环左移k个位置，要求时间复杂度为O（n），空间复杂度为O（1）。例如，对abcdefgh循环左移3位得到defghabc。实验过程：1.1算法思想对于第6题，用分治法进行求解的话，若是采用循环赋值的方式，如果字符的个数和左移的位数成倍数关系，那么算法就比较容易实现，但是如果不成比例关系，算法写起来就比较麻烦，所以，用了另一种方式，进行三次对称交换就可以完成算法。1.2 算法步骤1.输入：一个数组

9、和左移位数2.编写两个函数，一个是对称交换函数1，另一个是调用函数2，用函数2三次调用函数1，完成整个对称交换过程。3.调用函数24.输出：左移后的数组1.3算法实现（C+程序代码）#includeusing namespace std;void fun(char *a,int m,int k) int temp;int i,j;for(i=m,j=k;i=k;i+,j-) if(i=(m+k)/2)temp=ai;ai=aj;aj=temp;void xun(char a,int k,int n)/（函数2）第二个调用函数，调用函数1fun(a,0,k-1);/第一次调用函数1，将(abc)

10、对称交换得到(cba),最后a为(cbadefgh)fun(a,k,n-1);/第二次调用函数1，将(defgh)对称交换得到(hgfed),最后a为(cbahgfed)fun(a,0,n-1);/第三次调用函数1，将(cbadefgh)对称交换得到(defghabc),即最后a为(defghabc)int main()char a1000; cout请输入一个数组:a;也可以哟，不过配套的比较好看！int k;cout请输入左移位数:k; int n=strlen(a);xun(a,k,n);puts(a);/用coutaendl;也可以哟，不过配套的比较好看！return 0;1.4 算法

11、分析存在如下递推式，T(n)=2T(n/2)+n, 时间复杂性为O(nlog2n) 实验总结（由学生填写）： 分治法的主要思想是分而治之，在遇到一个规模比较大问题时，我们不应该直接入手，通过简单的循环语句解决，而应该对其分段对局部进行考虑，通过对局部得到整体的结果。但在此次实验中，学会了对分治法的简单应该，但要对其加深巩固，还应该对此类问题的相关习题多多去练习，多多去领悟。 实验等级评定： 实验名称： 回溯法0/1背包问题（实验四） 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC+的计算机 实验日期： 年 月 日 实验地点：第五教学楼北802 实验目的：熟悉回溯法的基本思想和实现方

12、法，掌握如何用C+实现相关算法。实验准备：1. 在开始本实验之前，请回顾教科书的相关内容；2. 需要一台准备安装Windows XP Professional操作系统和装有C+的计算机。实验内容：给定背包容量W=20，以及6个物品，重量分别为（5，3，2，10，4，2），价值分别为（11，8，15，18，12，6）。请用回溯法求解上述0/1背包问题。实验过程：1.1算法思想首先把物品单价价值排序，并确定上界函数，在搜索二叉树中利用上界函数对其进行剪枝，最终确定最优解。1.2 算法步骤1.定义变量2.编写函数 knapsack() ，用于将物品按单位价值排序编写函数 bound(int i)，用

13、于计算上界函数编写函数 backtrack(int i) ，回溯函数，用于搜索二叉树。3.输出解决方案1.3算法实现（C+程序代码）#include/这个是只找到了一个可行解就返回了值(其实还可能有其他的解)using namespace std;#include/计算程序运行时间的头函数int n;/物品数量double c;/背包容量double v100;/各个物品的价值double w100;/各个物品的重量double cw = 0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值double bestp = 0.0;/当前最优价值double perp100;

14、/单位物品价值排序后int order100;/物品编号int put100;/设置是否装入/按单位价值排序void knapsack() int i,j; int temporder = 0; double temp = 0.0; for(i=1;i=n;i+) perpi=vi/wi; for(i=1;i=n-1;i+)/冒泡排序思想：比较n-1次，第一次从第一个数到最后一个数，第二次从第二个数到最后一个数. for(j=i+1;j=n;j+)/按照单位重量价值进行冒泡排序，同时要将重量，价值，序号进行相同排序 if(perpiperpj)/冒泡排序perp,order,sortv,sor

15、tw temp = perpi; perpi=perpi; perpj=temp; temporder=orderi; orderi=orderj; orderj=temporder; temp = vi; vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; /计算上界函数double bound(int i) double leftw= c-cw;/leftw = 背包容量 - 当前背包容量 double b = cp; /b = 当前背包中物品价值 while(i=n&wi=leftw) leftw-=wi;/将第i件物品装入背包 b+=vi; i+; if(

16、in) bestp = cp; return; if(cw+wibestp)/符合条件搜索右子数 backtrack(i+1);int main()clock_t nTimeStart;/开始时间clock_t nTimeStop;/结束时间nTimeStart=clock(); int i; /printf(请输入物品的数量和容量：); /scanf(%d %lf,&n,&c);coutnc; / printf(请输入物品的重量和价值：);cout请输入物品的重量和价值：endl; for(i=1;i=n;i+) /printf(第%d个物品的重量：,i); / scanf(%lf,&wi)

17、;cout第iwivi;/ printf(价值是：); /scanf(%lf,&vi); orderi=i; knapsack(); backtrack(1); printf(最大价值为：%lfn,bestp); printf(需要装入的物品编号是：); for(i=1;i=n;i+) if(puti=1)coutorderi ; /printf(%d ,orderi); coutendl;nTimeStop=clock();cout 程序耗时：(double)(nTimeStop - nTimeStart)/CLOCKS_PER_SEC秒 endl; return 0;1.4 算法分析回溯法实际上属于蛮力穷举法，遍历具有指数阶个节点的空间树，在最坏的情况下，时间代价肯定为指数阶。回溯法的有效性往往体现在当问题规模n很大时，在搜索过程中对问题的解空间树实行大量剪枝。但是，对于具体的问题实例，很难预测回溯法的搜索行为，特别是很难估计在搜索过程中所产生的节点数，这是分析回溯法的时间性能的主要困难。实验总结（由学生填写）：0/1背包属于找最优解问题，用回溯法需要构造解的子集树。在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去，剪枝。实验等级评定：