數(shù)據(jù)結(jié)構(gòu)課設(shè)網(wǎng)組識別

1、 題目 ： 網(wǎng)組識別 題目描述 基本要求表述基本要求： 1.N輸入指定后，隨機生成一個初始網(wǎng)格。初始網(wǎng)格以圖形的方式顯示。 2.當(dāng)給出一個方格時，計算其所在組的大小，一個組的大小是該組含有 的黑圓的個數(shù)。 3.計算網(wǎng)格中不同組的個數(shù)。 4.列出網(wǎng)格中所有的組。網(wǎng)組基本表述 設(shè)二維數(shù)組 m來表示網(wǎng)組。 且該網(wǎng)組為N*N的正方形。 類似于迷宮的表述，用1表示網(wǎng)格中有黑點，用0表示為空網(wǎng)格。 另設(shè)二維數(shù)組n，表示是否遍歷過該方格，用1表示已經(jīng)遍歷過的方格，0則為未遍歷過。網(wǎng)組呈現(xiàn)例如，如示例中的表格，則可以表示為 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設(shè)計系統(tǒng)機構(gòu)設(shè)計 程序主要功能模塊 輸入模塊 遍歷模塊 搜查模塊 輸出模塊 位置表示 m 用行號和列號表示網(wǎng)格的位置 n 同 黑子的有無 ： 用隨機數(shù) mxy=ran()%2; 或者 有黑子的方格位置x,y隨機 如果要實現(xiàn)有隨機的固定數(shù)目的有黑點的方格 數(shù)目=ran()%(n-0+1)+0或者用戶輸入 遍歷（計算組的大小、組的總數(shù)和給出指定組） 1.方向：優(yōu)先性，右，下，左，上。（已經(jīng)遍歷過的不再遍歷。） 2.對于每一個方格，f

3、or循環(huán)到該方格， 針對每一個有黑子的方格：遞歸。輸入模塊 輸入網(wǎng)格的行數(shù)/列數(shù) 用戶輸入n 表示為n*n的網(wǎng)格 輸入網(wǎng)組方格的黑點 目前暫定為隨機設(shè)置 或者實現(xiàn) 用戶自定義輸入，以行為單位，0、1為黑子的有無。 每輸入一行就顯示在屏幕上以供用戶檢查正確性。（若采用此種方法，還要有改正功能）遍歷模塊設(shè)計 設(shè)計思路 把方格的左上作為初始位置， 如果只有網(wǎng)格為1*1網(wǎng)格，則遍歷結(jié)束。 否則，將該方格標(biāo)記1，表示已經(jīng)遍歷過，然后檢查相鄰位置中是否有黑點，若有則移動到下一個位置，再開始相鄰位置的遍歷，如果相鄰位置都沒有，則優(yōu)先向右；若整行都無，則進行下一行的遍歷。 當(dāng)某一個方格帶有黑點時，（因為最后要

4、輸出各組）可在遍歷中（遞歸中）輸出位置信息。 具體細節(jié) 原網(wǎng)格展示 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 改進后的網(wǎng)格展示 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遍歷方向 按優(yōu)先性 右 下 左 上。進行依次遍歷。對于網(wǎng)組的邊界 采用迷宮的拓展方法，在四周的邊界加一行空的方格，則邊界的遍歷方法可采用同中間部分相同，不再只有三個方向可以遍歷。下一個移動位置的選擇 以一種固定的方式選擇可行的相鄰位置，使問題得到簡化。 向右、下、左、上遍歷沒有標(biāo)記過的方格。 對于空的方格和單個有黑點的方格，可以進行四個方向的遍歷之后，跳到下一個方格。 對于黑點相連的方格，采用遞歸，依次遍歷，當(dāng)某方格四周沒有黑點時，可以返回上一個方格。 在

6、遞歸中實現(xiàn)組的大小的計數(shù)。搜查模塊設(shè)計 具體思路類似于遍歷模塊，具體實現(xiàn)時可以調(diào)用遍歷模塊。 更改點在于起始點，不再從網(wǎng)格的左上開始遍歷，從用戶指定的地點，開始依次遍歷。 對于遍歷的具體演示，以任一有黑點的網(wǎng)格為起點。輸出模塊設(shè)計 按照題目要求，需要輸出的數(shù)據(jù)有 1,以圖形方式顯示的初始網(wǎng)格。 2.指定方格，給出其組的大小。 3.計算不同組個數(shù)和4.列出所有的組。 對1，最簡單方法為cout ;輸出。 對2，可在搜查模塊中采取計數(shù)。 對3，在整體遍歷中采取計數(shù)。 對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 );

8、if ( axy - 1 = 1 & bxy - 1 != 1)count += bianli(a, b, n, x, y - 1);return count; int main()int* a;int n = 1;cout 輸入格子大?。∟*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 (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