一、 题目要求：返回二维数组的最大连通数组，并输出到文件。
随机产生整形数组，数组里有正数也有负数。输出其中最大的连通数组。
二、 设计思路：
这次实验要用连通图来实现，通过对图的遍历来实现求连通数组的最大值；
//按一维数组输入
void input(array_a &A,int row,int col)
//遍历函数：
void bianli(array_a &A,int v,int array_b[],int &k,int &max,int row)
//按行和列输出
void output(array_a A)
主函数调用并将最大的将最大数组输出到文件里。
#include <iostream>
#include<fstream>
#define N 100
#include<ctime>
using namespace std;
ofstream outfile("input.txt",ios::binary);
typedef struct
{
int arrayOfone[N];
int arrayOftwo[N][N];
int row;
}array_a;
//row代表行数，col代表列数
void input(array_a &A,int row,int col)
{
int positive,negtive;
cout<<"Please input the positive and negtive(positive>negtive):"<<endl;
cin>>positive>>negtive;
if(positive<negtive)
{
cout<<"error!";
exit(0);
}
A.row =row*col;//将二维数组变为一维数组
srand((unsigned)time(NULL));
for(int i=1;i<=A.row;i++)
{
A.arrayOfone[i]=rand()%positive+negtive;//产生数字数字可以为正数也可以为负数
}
//将生成的一维数组转化为图的形式
for(int i=1;i<=A.row;i+=col)
{
for(int j=i;j<=i+col-2;j++)
{
A.arrayOftwo[j][j+1]=1;
A.arrayOftwo[j+1][j]=1;
}
}
for(int i=1+col;i<A.row ;i+=col)
{
for(int j=i;j<=i+row-1;j++)
{
A.arrayOftwo [j][j-col]=1;
A.arrayOftwo [j-col][j]=1;
}
}
}
void output(array_a A)
{
for(int i=1;i<=A.row;i++)
{
if(!outfile)//如果文件不能打开
{
cerr<<"open error!"<<endl;
exit(0);
}
else
{
outfile<<A.arrayOfone[i];
if(A.arrayOftwo[i][i+1]==1)
outfile<<" ";//数与数字之间有空格
else
outfile<<"\r\n";//换行
}
}
}
void bianli(array_a &A,int v,int array_b[],int &k,int &max,int row)
{
array_b[v]=1;//数组定义为1
max+=A.arrayOfone[v];//求最大值
if(max>=k)
k=max;
int a=0,b=0;
for(int n=1;n<=A.row;n++)
{
for(int m=1;m<=A.row;m++)
{
if((array_b[n]==0)&&(A.arrayOftwo[m][n]==1)&&(array_b[m]==1))
{
a=n;
b=1;
break;
}
}
if(b==1)break;
}
for(int n=1;n<=A.row;n++)
{
for(int m=1;m<=A.row;m++)
{
if((array_b[n]==0)&&(A.arrayOftwo[m][n]==1)&&(array_b[m]==1))
{
if(A.arrayOfone[a]<A.arrayOfone[n])
a=n;
}
}
}
//结果为负置为零
if((k+A.arrayOfone[a])<0)
{
A.arrayOftwo[v][a]=0;
}
else
//否则继续遍历
bianli(A,a,array_b,k,max,row);
}
int arrayOfb(int array_b[],array_a A)
{
int q=0,i;
for(i=1;i<=A.row;i++)
{
if(array_b[i]==0)
{
q=i;
break;
}
}
return q;
}
int main()
{
int row,col;
cout<<"Please input the row and the col:"<<endl;
cin>>row>>col;
outfile<<"The row:"<<row<<"\r\n";
outfile<<"The col:"<<col<<"\r\n";
array_a A;
//随机产生数组
input(A,row,col);
//将数组按行，列输出
output(A);
int v=1,array_c[N]={0};//定义新的数组用来存放结果的最大值
for(int i=1;i<=A.row;i++)
{
if(A.arrayOfone[i]<0)//如果第i个数字为负则将数字放到array_c数组中去
{
array_c[i]=A.arrayOfone[i];
}
else
{//大于零则重新遍历
int array_b[N]={0};
int max=0;
bianli(A,i,array_b,array_c[i],max,row);
}
}
int max=array_c[1];//将数组array_c的第一个值赋给max
for(int i=2;i<=A.row ;i++)//继续比较一直更新array_c的值将最后结果赋给max输出最大值
{
if(array_c[i]>max)
max=array_c[i];
}
outfile<<"The max array is:"<<max<<endl;
}
运行结果：
总结：
之前只有数据结构做了一个校园景点遍历的实验用到了图的知识，几乎都忘了，这一次再一次使用既巩固了同时也学到了一些新的知识，感觉收获很多。