数据结构实习报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构程序实习报告”。
数据结构实习报告
班级：13软件二班
姓名：殷健 学号：1345536225
子集和数问题
1：问题描述
子集和数问题1：子集和问题的为〈W,c〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0
2：问题分析
程序中设计了函数void computeSumofSub(int s,int k,int r)，其意义是从第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])，即选择当前结点的右分支。
算法展示：
#include using namespace std;#include #include #define M 50 cla SumOfSub{ private: int w[M];
int m;int x[M];public: SumOfSub(int a[], int b, int n){
for(int i=0;i=m&&s+w[k+1]
};void main(){ int sum=0;int w[M];srand((unsigned)time(NULL));
for(int i=0;i
} cout
cout
} 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子集。
算法演示
#include using namespace std;#include #include #define M 50 cla SumOfSub{ private: int w[M];int p[M];int m;int x[M];
int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){
max=0;j=0;
for(int i=0;i
w[i]=a[i];
p[i]=a[i]+10;
}
m = b;
x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout
} else if(s+w[k]+w[k+1] =m&&s+w[k+1]
int S=0;int i;
cout
for(i=0;i
S=S+p[i];
cout
}
cout
cout
if(S>max){
max=S;
int J=0;
for(i=0;i
if(x[i]==1){
N[J]=w[i];
J++;
}
}
j=J;
} } void special(){
cout
for(int i=0;i
cout
}
cout
for(int i=0;i
w[i]=rand();
if(w[i]==0){
w[i]=rand();
}
sum=sum+w[i];} cout
cout>m;sum=m*sum;cout
r += 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子集。
算法演示
#include using namespace std;#include #include #define M 50 cla SumOfSub{ private: int w[M];int p[M];int m;
int x[M];int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){
max=0;
j=0;
cout
for(int i=0;i
w[i]=a[i];
p[i]=rand();
cout
}
cout
m = b;
x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout
} else if(s+w[k]+w[k+1] =m&&s+w[k+1]
int S=0;int i;
cout
for(i=0;i
S=S+p[i];
cout
}
cout
cout
if(S>max){
max=S;
int J=0;
for(i=0;i
if(x[i]==1){
N[J]=w[i];
J++;
}
}
j=J;
} } void special(){
cout
for(int i=0;i
cout
}
cout
for(int i=0;i
w[i]=rand();
if(w[i]==0){
w[i]=rand();
}
sum=sum+w[i];} cout
cout>m;sum=m*sum;cout
r += w[i];} sumOfSub.computeSumOfSub(0, 0, r);
sumOfSub.special();}
运行结果
复杂性分析
对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。
一、概述软件开发的流程二、回顾C语言的基本语法：1、常量（类型）2、变量（类型、定义）3、表达式（例子：三位数的拆分）4、控制语句（if条件语句，例子：饿了吗？for循环语句，例子：做好事问题求解）5......
附件：实习报告格式，如下：数据结构实习报告班级： 姓名：xxx（20121514101）xxx（20121514101） xxx（20121514101） 指导教师：日期： 题目一、问题描述（把你所选的题目及要求说一下）二、概要设计（抽......
数据结构第六次作业p134——11411203张玉24.template void SeqQueue::EnQueue(const T& x){//插入函数if(IsFull()==true){maxSize=2*maxSize;elements[rear]=x;rear=(rear+......
数据结构课程设计的实习报告怎么写呀，请求做过课设的同学发一篇范文过来谢谢-_-规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：1、需求分析以......
一、需求分析1、程序所实现的功能；2、程序的输入，包含输入的数据格式和说明；3、程序的输出，程序输出的形式；4、测试数据，如果程序输入的数据量比较大，需要给出测试数据；5、合作人及......
