数据结构实习报告.docx

数据结构实习报告

第一篇：数据结构实习报告数据结构实习报告班级：13软件二班姓名：殷健学号：1345536225子集和数问题1：问题描述子集和数问题1：子集和问题的为〈W,c〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0程序中设计了函数voidcomputeSumofSub(ints,intk,intr)，其意义是从第k项开始，如果s（已经决策的和数）和w[k]（当前元素）之和为和数，就把结果输出来，否则如果s与，w[k],w[k+1]之和小于和数，则调用computeSumofsub(s+w[k],k+1,r-w[k])，意为选择此结点的左分支，再判断s和后面所有元素之和是否不小于M（所有的加起来都小，必定无解），并且s+w[k+1]M，也是无解），若条件符合即调用computeSumofSub(s,k+1,r-w[k])，即选择当前结点的右分支。算法展示：#includeusingnamespacestd;#include#include#defineM50classSumOfSub{private:intw[M];intm;intx[M];public:SumOfSub(inta[],intb,intn){for(inti=0;i=m&&s+w[k+1]};voidmain(){intsum=0;intw[M];srand((unsigned)time(NULL));for(inti=0;i}coutcout}cout>m;sum=m*sum;cout复杂性分析:对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。其它说明:按书中所讲的约束条件，程序中所有变量都是整型，输入的各元素要从小到大输入，而且不能有重复的元素。若是想要无序输入，可以程序中加入程序1.c的归并排序算法，对输入的数组排序即可。拓展一问题描述:子集和数问题拓展一：子集和问题的为〈W,c，p〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0问题分析：增加一个数组p,使得p的每个元素与w对应元素关系为pi=Wi+10;最后结果W子集中元素个数越多，则p和最大，但也可以将每个符合条件子集对应P集合的元素和计算出做个比较，然后输出最大的再对应原W子集。算法演示#includeusingnamespacestd;#include#include#defineM50classSumOfSub{private:intw[M];intp[M];intm;intx[M];intN[M];intmax;intj;public:SumOfSub(inta[],intb,intn){max=0;j=0;for(inti=0;iw[i]=a[i];p[i]=a[i]+10;}m=b;x[0]=n;}voidcomputeSumOfSub(ints,intk,intr){x[k]=1;if(s+w[k]==m){printResult(k);cout}elseif(s+w[k]+w[k+1]=m&&s+w[k+1]intS=0;inti;coutfor(i=0;iS=S+p[i];cout}coutcoutif(S>max){max=S;intJ=0;for(i=0;iif(x[i]==1){N[J]=w[i];J++;}}j=J;}}voidspecial(){coutfor(inti=0;icout}coutfor(inti=0;iw[i]=rand();if(w[i]==0){w[i]=rand();}sum=sum+w[i];}coutcout>m;sum=m*sum;coutr+=w[i];}sumOfSub.computeSumOfSub(0,0,r);sumOfSub.special();}运行结果复杂性分析对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。拓展二问题描述子集和数问题拓展一：子集和问题的为〈W,c，P〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0问题分析增加一个数组随机数组P，每个符合条件子集对应P集合的元素和计算出做个比较，然后输出最大的再对应原W子集。算法演示#includeusingnamespacestd;#include#include#defineM50classSumOfSub{private:intw[M]