数据结构课设网组识别汇编
题目 : 网组识别 题目描述 基本要求表述 基本要求: 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 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.对于每一个方格,for循环到该方格, 针对每一个有黑子的方格:递归。 输入模块 输入网格的行数/列数 用户输入n 表示为n*n的网格 输入网组方格的黑点 目前暂定为随机设置 或者实现 用户自定义输入,以行为单位,0、1为黑子的有无。 每输入一行就显示在屏幕上以供用户检查正确性。(若采用此种 方法,还要有改正功能) 遍历模块设计 设计思路 把方格的左上作为初始位置, 如果只有网格为1*1网格,则遍历结束。 否则,将该方格标记1,表示已经遍历过,然后检查相邻位置中 是否有黑点,若有则移动到下一个位置,再开始相邻位置的遍历 ,如果相邻位置都没有,则优先向右;若整行都无,则进行下一 行的遍历。 当某一个方格带有黑点时,(因为最后要输出各组)可在遍历中 (递归中)输出位置信息。 具体细节 原网格展示 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 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 遍历方向 按优先性 右 下 左 上。进行 依次遍历。 对于网组的边界 采用迷宫的拓展方法 ,在四周的边界加一行空的方格 ,则边界的遍历方法可采用同中 间部分相同,不再只有三个方向 可以遍历。 下一个移动位置的选择 以一种固定的方式选择可行的相邻位置,使问题得到简化。 向右、下、左、上遍历没有标记过的方格。 对于空的方格和单个有黑点的方格,可以进行四个方向的遍历之 后,跳到下一个方格。 对于黑点相连的方格,采用递归,依次遍历,当某方格四周没有 黑点时,可以返回上一个方格。 在递归中实现组的大小的计数。 搜查模块设计 具体思路类似于遍历模块,具体实现时可以调用遍历模块。 更改点在于起始点,不再从网格的左上开始遍历,从用户指定 的地点,开始依次遍历。 对于遍历的具体演示,以任一有黑点的网格为起点。 输出模块设计 按照题目要求,需要输出的数据有 1,以图形方式显示的初始网格。 2.指定方格,给出其组的大小。 3.计算不同组个数和4.列出所有的组。 对1,最简单方法为cout 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 (int 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 cout “ endl; cout “第“ JiShu “组“ endl; cout “黑球个数为“ bianli(a, b, n, i, j) endl; system(“pause“);