《数据结构课设网组识别ppt课件.pptx》由会员分享，可在线阅读，更多相关《数据结构课设网组识别ppt课件.pptx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 题目 ： 网组识别 题目描述 基本要求表述基本要求： 1.N输入指定后，随机生成一个初始网格。初始网格以图形的方式显示。 2.当给出一个方格时，计算其所在组的大小，一个组的大小是该组含有 的黑圆的个数。 3.计算网格中不同组的个数。 4.列出网格中所有的组。网组基本表述 设二维数组 m来表示网组。 且该网组为N*N的正方形。 类似于迷宫的表述，用1表示网格中有黑点，用0表示为空网格。 另设二维数组n，表示是否遍历过该方格，用1表示已经遍历过的方格，0则为未遍历过。网组呈现例如，如示例中的表格，则可以表示为 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0
2、 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0设计系统机构设计 程序主要功能模块 输入模块 遍历模块 搜查模块 输出模块 位置表示 m 用行号和列号表示网格的位置 n 同 黑子的有无 ： 用随机数 mxy=ran()%2; 或者 有黑子的方格位置x,y随机 如果要实现有随机的固定数目的有黑点的方格 数目=ran()%(n-0+1)+0或者用户输入 遍历（计算组的大小、组的总数和给出指定组） 1.方向：优先性，右，下，左，上。（已经遍历过的不再遍历。） 2.对于每一个方格，f
3、or循环到该方格， 针对每一个有黑子的方格：递归。输入模块 输入网格的行数/列数 用户输入n 表示为n*n的网格 输入网组方格的黑点 目前暂定为随机设置 或者实现 用户自定义输入，以行为单位，0、1为黑子的有无。 每输入一行就显示在屏幕上以供用户检查正确性。（若采用此种方法，还要有改正功能）遍历模块设计 设计思路 把方格的左上作为初始位置， 如果只有网格为1*1网格，则遍历结束。 否则，将该方格标记1，表示已经遍历过，然后检查相邻位置中是否有黑点，若有则移动到下一个位置，再开始相邻位置的遍历，如果相邻位置都没有，则优先向右；若整行都无，则进行下一行的遍历。 当某一个方格带有黑点时，（因为最后要
4、输出各组）可在遍历中（递归中）输出位置信息。 具体细节 原网格展示 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 改进后的网格展示 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0
5、 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0遍历方向 按优先性 右 下 左 上。进行依次遍历。对于网组的边界 采用迷宫的拓展方法，在四周的边界加一行空的方格，则边界的遍历方法可采用同中间部分相同，不再只有三个方向可以遍历。下一个移动位置的选择 以一种固定的方式选择可行的相邻位置，使问题得到简化。 向右、下、左、上遍历没有标记过的方格。 对于空的方格和单个有黑点的方格，可以进行四个方向的遍历之后，跳到下一个方格。 对于黑点相连的方格，采用递归，依次遍历，当某方格四周没有黑点时，可以返回上一个方格。 在
6、递归中实现组的大小的计数。搜查模块设计 具体思路类似于遍历模块，具体实现时可以调用遍历模块。 更改点在于起始点，不再从网格的左上开始遍历，从用户指定的地点，开始依次遍历。 对于遍历的具体演示，以任一有黑点的网格为起点。输出模块设计 按照题目要求，需要输出的数据有 1,以图形方式显示的初始网格。 2.指定方格，给出其组的大小。 3.计算不同组个数和4.列出所有的组。 对1，最简单方法为cout ;输出。 对2，可在搜查模块中采取计数。 对3，在整体遍历中采取计数。 对4，在整体遍历中输出组以及位置。已完成部分代码展示 int bianli(int* a, int* b, int n, int x
7、, int y)int count = 0;if (axy=1 & bxy!=1)count = 1;cout 第 x 行，第 y 列 = 0 & x = n) if (axy + 1 = 1 & bxy + 1 != 1)count += bianli(a, b, n, x, y + 1);if ( ax + 1y = 1 & bx + 1y != 1)count += bianli(a, b, n, x+ 1, y );if ( ax - 1y = 1 & bx - 1y != 1)count += bianli(a, b, n, x-1, y );if ( axy - 1 = 1 & b
8、xy - 1 != 1)count += bianli(a, b, n, x, y - 1);return count; int main()int* a;int n = 1;cout 输入格子大小（N*N） n;a= new int*n+2;for (int i = 0; i=n+1; i+)ai = new intn+2;int* b;b= new int*n+2;for (int i = 0; i=n+1; i+)bi = new intn+2; for (int i = 0; i = n+1; i+)for (int j = 0; j = n+1; j+)aij = 0;for (in
9、t i = 0; i =n+1; i+)for (int j = 0; j =n+1; j+)bij = 0;srand(unsigned)time(NULL);for (int i = 1; i = n; i+)for(int j=1;j=n;j+) aij=rand()%2; for (int i = 1; i =n; i+)for (int j = 1; j =n; j+)cout aij ;cout n endl;int JiShu = 0;for (int i = 1; i =n; i+)for (int j = 1; j = n; j+)if (aij = 1 & bij != 1)JiShu+; cout endl;cout 第 JiShu 组 endl; cout 黑球个数为 bianli(a, b, n, i, j) endl;system(pause);