占用网格计算问题-课程设计(共13页)

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

2、虑一个N*N的网格，其中某些方格已被占用。如果两个方格共用公共的边，就说它们属于同一个组，如图示，一组为4个被占用的方格，3组为两个被占用的方格，2个方格被单独占用。假设格子用二维数组来表示。请编写实现下列目的程序：给定组中的某个方格，计算组的大小；计算不同组的数目；3）列出所有的组。（4）相关(xinggun)的数据结构（数据类型）#define N 10using namespace std;int aNN;int b3N*N;各问题处理的流程图或伪码描述(mio sh)的算法4.1计算(j sun)组的大小搜索某组中的一个格子（以坐标确定）Y判断该格子是否为空（即二维数组是否被赋0）N访

3、问这个格子（visit函数），计数器加1递归访问(fngwn)周围四个格子4.2计算不同(b tn)组的数目4.3列出所有(suyu)的组输入所有网格信息显示网格信息(display函数)描述实现(shxin)函数的调用关系图占用网格计算（主函数main）网格初始(empty函数)输入占用网格信息（enter）搜索指定网格（search函数）显示网格信息（display函数）访问，递归访问（visit函数）6.调试(dio sh)分析：6.1调试(dio sh)中遇到的问题及对问题的解决方法输入大于网格边长的数会导致数组越界(yu ji)问题，以致程序出错。在输出的信息中提醒操作者输入合适的坐

4、标。6.2算法的时间复杂度和空间复杂度空间复杂度：O（f（n）时间复杂度:0(n)输出典型数据，获得测试结果源程序（带注释(zhsh)）#define N 10using namespace std;int aNN;int b3N*N;int enter(int m)/输入(shr)网格中被占用的格子的信息 int i,j,k,n,flag; cout请输入N*N的网格的N值n; for(k=1;k=m;k+) flag=1; cout输入网络(wnglu)第 k个被占用所在行和列(小于等于N):ij;if(i=n|j=n|i0|j0) cout!ERROR!endl; cout坐标越界end

5、l; flag=0;if(flag=1) aij=1;else k-; return n;int empty(int &h,int &l,int n)/判断网格是否为空 for(h=0;hn;h+) for(l=0;ln;l+) if(ahl!=0) return 1;/非空返回(fnhu)return 0;/空则返回(fnhu) void visit(int h,int l,int count,int &num,int n)/递归搜索(su su)一组 if(ahl=1)/若方格被占用则把它赋值为并访问它四周的四个方格 ahl=0; b0num=h;b1num=l;b2num=count;

6、num+;if(h+1n)visit(h+1,l,count,num,n); if(l+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)/查询(chxn)某一方格的组数 int i,j,k; cout输入网络要查询的方格所在(suzi)行和列(小于等于N):ij;if(i=n|j=n|i0|j0) cout!ERROR!endl; cout坐标(zubio)越界endl;for(k=0;km;k+) if(b0k=i&b1k=j) return b2k; return

7、 0;void display(int count,int m,int n)/显示每组的具体信息 int i,j,cN*N/2=0;count-;cout一共有count个组.endl;for(j=1;j=count;j+)for(i=0;im;i+)if(b2i=j) cj+;for(j=1;j=count;j+)cout第j组包含(bohn)cj个点,他们分别是:endl;coutitjtendl;for(i=0;im;i+)if(b2i=j) coutb0itb1itendl;coutendlendl; while(1)i=search(m,n); if(i=0)cout该格子(g zi

8、)未被占用。endl;else cout该格子(g zi)位于第i组，该组共用ci个格子endl;int main()int n,m,h,l,count=1,num=0,i,j; for(i=0;iN;i+) for(j=0;jN;j+) aij=0; cout请输入N*N的网格被占用格子总数:m; n=enter(m); while(empty(h,l,n)=1) visit( h,l,count,num,n); count+; display( count,m,n); return 0;9.致谢(zh xi)编程看起来似乎是一件很枯燥(kzo)、乏味的事情，但是经历了这次程序的编辑之后，发现其实里面还是充满乐趣的，一旦真的专研下去什么事情都可以放下，来认真研究。只有把所学习的知识用起来，才能真正体会学习的目的，在应用中去学习，理论和实际结合才是好的学习方法，这次的课程设计也让我对自己所学的数据结构的知识有了更加进一步的了解。在这次设计过程(guchng)中，我得到老师的精心指导，在此，我由衷地感谢张永老师和李睿老师参考文献 C+ Primer Plus中文版第5版 作者: HYPERLINK /search/Stanley B. Lippman 美 Stanley B. Lippman/ HYPERLINK /search/Jos%C3%A9e Lajoie 美