占用網(wǎng)格計(jì)算問題-課程設(shè)計(jì)(共13頁)

1、 蘭州理工大學(xué)課程設(shè)計(jì)報(bào)告(bogo)課程名稱：算法(sun f)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(shj)題目： 占用網(wǎng)格計(jì)算問題 系 別： 計(jì)算機(jī)與通信 專 業(yè)： 軟件工程 學(xué)生姓名: 朱晨光 學(xué) 號(hào): 1416270236 起止日期: 2015年 12月26日2016年1月10日 指導(dǎo)教師: 張永，李睿 摘要(zhiyo)：考慮一個(gè)N*N的網(wǎng)格，其中(qzhng)某些方格已被占用。如果兩個(gè)方格共用公共的邊，就說它們屬于同一個(gè)組，如圖示，一組為4個(gè)被占用的方格，3組為兩個(gè)被占用的方格，2個(gè)方格被單獨(dú)占用。假設(shè)格子用二維數(shù)組來表示。關(guān)鍵字：C+，二維數(shù)組，占用(zhn yn)網(wǎng)格計(jì)算 序言占用網(wǎng)格計(jì)算問題。考

2、慮一個(gè)N*N的網(wǎng)格，其中某些方格已被占用。如果兩個(gè)方格共用公共的邊，就說它們屬于同一個(gè)組，如圖示，一組為4個(gè)被占用的方格，3組為兩個(gè)被占用的方格，2個(gè)方格被單獨(dú)占用。假設(shè)格子用二維數(shù)組來表示。請(qǐng)編寫實(shí)現(xiàn)下列目的程序：給定組中的某個(gè)方格，計(jì)算組的大小；計(jì)算不同組的數(shù)目；3）列出所有的組。（4）相關(guān)(xinggun)的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)類型）#define N 10using namespace std;int aNN;int b3N*N;各問題處理的流程圖或偽碼描述(mio sh)的算法4.1計(jì)算(j sun)組的大小搜索某組中的一個(gè)格子（以坐標(biāo)確定）Y判斷該格子是否為空（即二維數(shù)組是否被賦0）N訪

3、問這個(gè)格子（visit函數(shù)），計(jì)數(shù)器加1遞歸訪問(fngwn)周圍四個(gè)格子4.2計(jì)算不同(b tn)組的數(shù)目4.3列出所有(suyu)的組輸入所有網(wǎng)格信息顯示網(wǎng)格信息(display函數(shù))描述實(shí)現(xiàn)(shxin)函數(shù)的調(diào)用關(guān)系圖占用網(wǎng)格計(jì)算（主函數(shù)main）網(wǎng)格初始(empty函數(shù))輸入占用網(wǎng)格信息（enter）搜索指定網(wǎng)格（search函數(shù)）顯示網(wǎng)格信息（display函數(shù)）訪問，遞歸訪問（visit函數(shù)）6.調(diào)試(dio sh)分析：6.1調(diào)試(dio sh)中遇到的問題及對(duì)問題的解決方法輸入大于網(wǎng)格邊長的數(shù)會(huì)導(dǎo)致數(shù)組越界(yu ji)問題，以致程序出錯(cuò)。在輸出的信息中提醒操作者輸入合適的坐

4、標(biāo)。6.2算法的時(shí)間復(fù)雜度和空間復(fù)雜度空間復(fù)雜度：O（f（n）時(shí)間復(fù)雜度:0(n)輸出典型數(shù)據(jù)，獲得測試結(jié)果源程序（帶注釋(zhsh)）#define N 10using namespace std;int aNN;int b3N*N;int enter(int m)/輸入(shr)網(wǎng)格中被占用的格子的信息 int i,j,k,n,flag; cout請(qǐng)輸入N*N的網(wǎng)格的N值n; for(k=1;k=m;k+) flag=1; cout輸入網(wǎng)絡(luò)(wnglu)第 k個(gè)被占用所在行和列(小于等于N):ij;if(i=n|j=n|i0|j0) cout!ERROR!endl; cout坐標(biāo)越界end

5、l; flag=0;if(flag=1) aij=1;else k-; return n;int empty(int &h,int &l,int n)/判斷網(wǎng)格是否為空 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)/若方格被占用則把它賦值為并訪問它四周的四個(gè)方格 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)某一方格的組數(shù) int i,j,k; cout輸入網(wǎng)絡(luò)要查詢的方格所在(suzi)行和列(小于等于N):ij;if(i=n|j=n|i0|j0) cout!ERROR!endl; cout坐標(biāo)(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個(gè)組.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個(gè)點(diǎn),他們分別是: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個(gè)格子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請(qǐng)輸入N*N的網(wǎng)格被占用格子總數(shù):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)、乏味的事情，但是經(jīng)歷了這次程序的編輯之后，發(fā)現(xiàn)其實(shí)里面還是充滿樂趣的，一旦真的專研下去什么事情都可以放下，來認(rèn)真研究。只有把所學(xué)習(xí)的知識(shí)用起來，才能真正體會(huì)學(xué)習(xí)的目的，在應(yīng)用中去學(xué)習(xí)，理論和實(shí)際結(jié)合才是好的學(xué)習(xí)方法，這次的課程設(shè)計(jì)也讓我對(duì)自己所學(xué)的數(shù)據(jù)結(jié)構(gòu)的知識(shí)有了更加進(jìn)一步的了解。在這次設(shè)計(jì)過程(guchng)中，我得到老師的精心指導(dǎo)，在此，我由衷地感謝張永老師和李睿老師參考文獻(xiàn) C+ Primer Plus中文版第5版 作者: HYPERLINK /search/Stanley B. Lippman 美 Stanley B. Lippman/ HYPERLINK /search/Jos%C3%A9e Lajoie 美