算法与数据结构课程设计-占用网格计算问题

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. 相关的数据结构（数据类型）#def ine n 10us ing namesp ace std;in t ann;int b3n*n;4. 各问题处理的流程图或伪码描述的算法4. 1计算组的大小判断该格子是否为空（即己维数组是否被赋0）n访问这个格子（vi sit函数）"计数器加14. 2计算不同组的数冃4.3列出所有的组输入所有网格信息显示网格信息（dis play曲数）5.描

3、述实现函数的调用关系图占用网格计算（主函数m ain）网格袒始（e mpty函数）笹入占用网格信息（ente r）搜索指定网格（s earch函数） 显示向格信息（displ ay函数）访问，递归访问（visit函数）6.调试分析：6. 1调试中遇到的问题及对问题的解决方法输入大于网格边长的数会导致数组越界问题，以致程序出错。在输出的信息中提醒操作者输入合适的坐标。6. 2算法的时间复杂度和空间复杂度空间复杂度：0 （f （n）时间复杂度：0（n）1.输岀典型数据，获得测试结果2.源程序（带注释）#def ine n 10us ing namesp ace std; in t ann;int

4、b3n*n;int enter (int m)/输入网格中被占用的格子的信息 int i，j，k, n，flag;输入n*n的网格的n /输入网格额外大小 cin>>n;for(k=l;kflag=l;cout所在行和列(小于等于； cin>>i>>j;if (i>=n|j>=n|cou endl;coufl ag=0;if (f lag=l) aij二 1;elsek一;ret urn n;int empty (in 1, int n)/判断网格是否为空for (h=0for (1 )if (a h1!=0)retu rn 1;/非空返回ret

5、urn 0;/空则返回v oid visit(int h, int 1, int coun , int n)/递归 搜索一组if(ahl =1)/若方格被占用则把它赋值为并访 问它四周的四个方格ah 1=0;b0 num=h;b 1num=l ;b2 num=count;nu m+;if (h+1visit (h +1, 1, count , num，n);1vi sit (h, 1+1, count, num, n); if (h-1 >=0)visit (hl, 1, coun t, num, n); if(l-l>=0)visit (h, 11, count, nu m, n

6、);i nt search(intm, int n)/查询某一方格的组数in t i, j, k;入网络要查询的方格所在行和列(小于等于ncin>>i >> j;if(i二n|j二n|i cout ndl;cout endl;for(+)if (b0 1 k=j)return b2 k;return 0 ;,int n)/显示每void dis play(int c ount, int m 组的具体信息int i, j,cn*n/2二0;count一一;c ；for(j=l; j +)for(i=0;if (bi二二j) cj+;=count;j+)个点，他们分别是:c

7、oum;i+)if (b 2 i二二j)cout dl;wh ile(1)i=s earch (m, n);if (i=0)elseint main()int n, m, h, 1, count=l, num=0, i, j ;for (i )for (j=0;ai j=0 ;请输入n*n的网格占用方格的数量cin>>m;n二enter(m);while (empty (h, 1，n)=l)visit (h, 1, count，num，n);count+;displ ay ( count，m, n);re turn 0;9.致谢编程看起来似乎是一件很枯燥、乏味的事情，但是经历了这次程序的编辑 z后，发现其实里面还是充满乐趣的，一旦真的专研下去什么事情都可以放下, 来认真研究。只有把所学习的知识用起来，才能真正体会学习的目的，在应用 中去学习，理论和实际结合才是好的学习方法，这次的课程设计也让我对自己 所学的数据结构的知识有了更加进一步的了解。