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

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

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

3、問這個格子（visit函數(shù)），計數(shù)器加1遞歸訪問(fngwn)周圍四個格子4.2計算不同(b tn)組的數(shù)目4.3列出所有(suyu)的組輸入所有網(wǎng)格信息顯示網(wǎng)格信息(display函數(shù))描述實現(xiàn)(shxin)函數(shù)的調(diào)用關系圖占用網(wǎng)格計算（主函數(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)中遇到的問題及對問題的解決方法輸入大于網(wǎng)格邊長的數(shù)會導致數(shù)組越界(yu ji)問題，以致程序出錯。在輸出的信息中提醒操作者輸入合適的坐

4、標。6.2算法的時間復雜度和空間復雜度空間復雜度：O（f（n）時間復雜度:0(n)輸出典型數(shù)據(jù)，獲得測試結果源程序（帶注釋(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請輸入N*N的網(wǎng)格的N值n; for(k=1;k=m;k+) flag=1; cout輸入網(wǎng)絡(wnglu)第 k個被占用所在行和列(小于等于N):ij;if(i=n|j=n|i0|j0) cout!ERROR!endl; cout坐標越界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)/若方格被占用則把它賦值為并訪問它四周的四個方格 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)絡要查詢的方格所在(suzi)行和列(小于等于N):ij;if(i=n|j=n|i0|j0) cout!ERROR!endl; cout坐標(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個組.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個點,他們分別是: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個格子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請輸入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ù)據(jù)結構的知識有了更加進一步的了解。在這次設計過程(guchng)中，我得到老師的精心指導，在此，我由衷地感謝張永老師和李睿老師參考文獻 C+ Primer Plus中文版第5版 作者: HYPERLINK /search/Stanley B. Lippman 美 Stanley B. Lippman/ HYPERLINK /search/Jos%C3%A9e Lajoie 美