占用网格计算问题-课程设计

1、 兰州理工大学课程设计报告课程名称：算法与数据结构设计题目： 占用网格计算问题 系 别： 计算机与通信 专 业： 软件工程 学生姓名: 朱晨光 学 号: 1416270236 起止日期: 2015年 12月26日2016年1月10日 指导教师: 张永，李睿 1. 摘要：考虑一个N*N的网格，其中某些方格已被占用。如果两个方格共用公共的边，就说它们属于同一个组，如图示，一组为4个被占用的方格，3组为两个被占用的方格，2个方格被单独占用。假设格子用二维数组来表示。关键字：C+，二维数组，占用网格计算2. 序言占用网格计算问题。考虑一个N*N的网格，其中某些方格已被占用。如果两个方格共用公共的边，就

2、说它们属于同一个组，如图示，一组为4个被占用的方格，3组为两个被占用的方格，2个方格被单独占用。假设格子用二维数组来表示。请编写实现下列目的程序：1) 给定组中的某个方格，计算组的大小；2) 计算不同组的数目；3）列出所有的组。（4）3. 相关的数据结构（数据类型）#define N 10using namespace std;int aNN;int b3N*N;4. 各问题处理的流程图或伪码描述的算法4.1计算组的大小搜索某组中的一个格子（以坐标确定）Y判断该格子是否为空（即二维数组是否被赋0）N访问这个格子（visit函数），计数器加1递归访问周围四个格子4.2计算不同组的数目4.3列出所

3、有的组输入所有网格信息显示网格信息(display函数)5. 描述实现函数的调用关系图占用网格计算（主函数main）网格初始(empty函数)输入占用网格信息（enter）搜索指定网格（search函数）显示网格信息（display函数）访问，递归访问（visit函数）6.调试分析：6.1调试中遇到的问题及对问题的解决方法输入大于网格边长的数会导致数组越界问题，以致程序出错。在输出的信息中提醒操作者输入合适的坐标。6.2算法的时间复杂度和空间复杂度空间复杂度：O（f（n）时间复杂度:0(n)7. 输出典型数据，获得测试结果8. 源程序（带注释）#define N 10using namespa

4、ce std;int aNN;int b3N*N;int enter(int m)/输入网格中被占用的格子的信息 int i,j,k,n,flag; cout<<"请输入N*N的网格的N值"<<endl;/输入网格额外大小 cin>>n; for(k=1;k<=m;k+) flag=1; cout<<"输入网络第 "<<k<<"个被占用所在行和列(小于等于N):"<<endl; cin>>i>>j;if(i>=n|j

5、>=n|i<0|j<0) cout<<"!ERROR!"<<endl; cout<<"坐标越界"<<endl; flag=0;if(flag=1) aij=1;else k-; return n;int empty(int &h,int &l,int n)/判断网格是否为空 for(h=0;h<n;h+) for(l=0;l<n;l+) if(ahl!=0) return 1;/非空返回return 0;/空则返回 void visit(int h,int l,

6、int count,int &num,int n)/递归搜索一组 if(ahl=1)/若方格被占用则把它赋值为并访问它四周的四个方格 ahl=0; b0num=h;b1num=l;b2num=count; num+;if(h+1<n)visit(h+1,l,count,num,n); if(l+1<n)visit(h,l+1,count,num,n); if(h-1>=0)visit(h-1,l,count,num,n); if(l-1>=0)visit(h,l-1,count,num,n); int search(int m,int n)/查询某一方格的组数

7、int i,j,k; cout<<"输入网络要查询的方格所在行和列(小于等于N):"<<endl; cin>>i>>j;if(i>=n|j>=n|i<0|j<0) cout<<"!ERROR!"<<endl; cout<<"坐标越界"<<endl;for(k=0;k<m;k+) if(b0k=i&&b1k=j) return b2k; return 0;void display(int coun

8、t,int m,int n)/显示每组的具体信息 int i,j,cN*N/2=0;count-;cout<<"一共有"<<count<<"个组."<<endl;for(j=1;j<=count;j+)for(i=0;i<m;i+)if(b2i=j) cj+;for(j=1;j<=count;j+)cout<<"第"<<j<<"组包含"<<cj<<"个点,他们分别是:"&

9、lt;<endl;cout<<"i"<<'t'<<"j"<<'t'<<endl;for(i=0;i<m;i+)if(b2i=j) cout<<b0i<<'t'<<b1i<<'t'<<endl;cout<<endl<<endl; while(1)i=search(m,n); if(i=0)cout<<"该格子未被占用。

10、"<<endl;else cout<<"该格子位于第"<<i<<"组，该组共用"<<ci<<"个格子"<<endl;int main()int n,m,h,l,count=1,num=0,i,j; for(i=0;i<N;i+) for(j=0;j<N;j+) aij=0; cout<<"请输入N*N的网格被占用格子总数:"<<endl;/输入占用方格的数量 cin>>m; n=enter(m); while(empty(h,l,n)=1) visit( h,l,count,num,n); count+; display( count,m,n); return 0;9.致谢编程看起来似乎是一件很枯燥、乏味的事情，但是经历了这次程序的编辑之后，发现其实里面还是充满乐趣的，一旦真的专研下去什么事情都可以放下，来认真研究。只有把所学习的知识用起来，才能真正体会学习的目的，在应用中去学习，理论和实际结合才是好的学习方法，这次的课程设计也让我对自己所学的数据结构的知识有了更加进一步