數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--- 地圖著色問題求解

1、<p>　　學(xué)生課程設(shè)計（論文）</p><p>　　題 目： 地圖著色問題求解 </p><p>　　2012年 6月14日</p><p>　　本科學(xué)生課程設(shè)計任務(wù)書</p><p>　　注：任務(wù)書由指導(dǎo)教師填寫。</p><p>　題　目地圖著色問題求解</p><

2、;p>　1、課程設(shè)計的目的使學(xué)生進一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法。使學(xué)生掌握軟件設(shè)計的基本內(nèi)容和設(shè)計方法，并培養(yǎng)學(xué)生進行規(guī)范化軟件設(shè)計的能力。3） 使學(xué)生掌握使用各種計算機資料和有關(guān)參考資料，提高學(xué)生進行程序設(shè)計的基本能力。</p><p>　2、課程設(shè)計的內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)要求、工作要求等）已知中國地圖，對各省進行著色

3、，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少。</p><p>　3、主要參考文獻［1］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2003．［2］《數(shù)據(jù)結(jié)構(gòu)題集》，嚴(yán)蔚敏，清華大學(xué)出版社，2005．［3］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），劉大有，高等教育出版社，2004．［4］《Data Structure with C++》，William Ford．William Topp，清華大學(xué)出版社，2003

4、．</p><p>　4、課程設(shè)計工作進度計劃第1天 完成方案設(shè)計與程序框圖 第2、3天 編寫程序代碼第4天 程序調(diào)試分析和結(jié)果第5天 課程設(shè)計報告和總結(jié)</p><p>　指導(dǎo)教師（簽字）日期年 月 日</p><p>　教研室意見：年 月 日</p><p>　學(xué)生（簽字）： 接受

5、任務(wù)時間： 年 月 日</p><p><b>　　目錄</b></p><p>　　1、地圖著色問題設(shè)計- 2 -</p><p>　　1．1、需求分析- 2 -</p><p>　　2、概要設(shè)計- 4 -</p><p>　　2.1、設(shè)定地圖的抽象數(shù)據(jù)類型- 4

6、-</p><p>　　2.2、本程序包括兩個模塊- 4 -</p><p>　　3、詳細(xì)設(shè)計- 6 -</p><p>　　3.1、地圖數(shù)據(jù)類型的操作設(shè)置- 6 -</p><p>　　3.2、兩點是否鄰接的偽碼算法- 6 -</p><p>　　3.3、著色偽碼算法- 6 -</p><

7、;p>　　3.4、將鄰接矩陣存儲偽碼算法- 7 -</p><p>　　3.5、主程序和其他函數(shù)的偽碼算法- 7 -</p><p>　　3.6、函數(shù)調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)- 7 -</p><p>　　4、調(diào)試分析- 8 -</p><p>　　5、課程設(shè)計總結(jié)- 12 -</p><p>

8、;　　6、附錄 著色后的中國地圖- 13 -</p><p>　　7、參考文獻- 14 -</p><p>　　8、程序源代碼- 15 -</p><p>　　1、地圖著色問題設(shè)計</p><p><b>　　1．1、需求分析</b></p><p>　　1.1、以二維數(shù)組list[N+1

9、][N+1]表示地圖，N表示區(qū)域數(shù)目，數(shù)組中以元素值為0表示不鄰接，1表示鄰接，限定區(qū)域數(shù)目N<=50。</p><p>　　1.2、用戶先輸入?yún)^(qū)域數(shù)目N，再輸入鄰接區(qū)域的代碼，鄰接可只寫一次，區(qū)域的代碼為0～N,N個為區(qū)域，一個為外部區(qū)域，或輸入N-1,則可不包括外部區(qū)域，N個區(qū)域由用戶定義。</p><p>　　1.3、輸出時，采用一一對應(yīng)的方法，一個區(qū)域?qū)?yīng)一種顏色形式：區(qū)域代

10、碼＝＝》顏色代碼（1～4）＝》顏色。</p><p>　　1.4、本程序可為任意一張的地圖染色，并且至多只染四種顏色。</p><p>　　1.5、測試數(shù)據(jù)：當(dāng)區(qū)域數(shù)目N=8,地圖如下：</p><p>　　輸出為 0=>1=>red</p><p>　　1=>2=>green</p><p>

11、　　2=>3=>blue</p><p>　　3=>4=>yellow</p><p><b>　　4=>1=>red</b></p><p>　　5=>2=>green</p><p>　　6=>2=>green</p><p>　　7

12、=>4=>yellow</p><p>　　8=>3=>blue</p><p>　　1.6、程序執(zhí)行的命令為：</p><p><b>　　1）創(chuàng)建地圖 </b></p><p><b>　　2）存儲地圖 </b></p><p><b>

13、　　3）獲取地圖 </b></p><p><b>　　4）地圖著色 </b></p><p><b>　　5）退出</b></p><p><b>　　2、概要設(shè)計</b></p><p>　　2.1、設(shè)定地圖的抽象數(shù)據(jù)類型</p><p>

14、;<b>　　ADT list{</b></p><p>　　數(shù)據(jù)對象：D={ai,j|ai,jε{’0’、‘1’}，0 <=i<=N,0<=j<=N</p><p>　　數(shù)據(jù)關(guān)系：R={ROW,COL}</p><p>　　ROW={<ai-1,j,ai,j>|ai-1,j,ai,jεD,i=1,…N,j=

15、0,…,N}</p><p>　　COL={<ai,j-1,ai,j>|ai,j-1,ai,jεD,i=0,…N,j=1,…,N} </p><p>　　2.2、本程序包括兩個模塊</p><p><b>　　1）主程序模塊：</b></p><p>　　void main()</p><

16、p><b>　　{</b></p><p><b>　　初始化；</b></p><p><b>　　while</b></p><p><b>　　{</b></p><p><b>　　接受命令；</b></p>

17、<p><b>　　處理命令；</b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　2）地圖模塊――實現(xiàn)地圖抽象數(shù)據(jù)類型</p><p>　　各模塊之間的調(diào)用關(guān)系如下：</p><

18、p><b>　　主程序模塊</b></p><p><b>　　地圖模塊</b></p><p><b>　　3）數(shù)據(jù)結(jié)構(gòu)的設(shè)計</b></p><p>　　typedef struct //定義圖</p><p><b>　　{</b>&l

19、t;/p><p>　　vextype vexs[MAXedg]; //存放邊的矩陣</p><p>　　adjtype arcs[MAXedg][MAXedg]; //圖的鄰接矩陣</p><p>　　int vnum,arcnum; //圖的頂點數(shù)和邊數(shù)</p><p><b>　　}Graph;</b><

20、;/p><p>　　4）功能模塊的劃分及模塊間調(diào)用關(guān)系</p><p><b>　　3、詳細(xì)設(shè)計</b></p><p>　　3.1、地圖數(shù)據(jù)類型的操作設(shè)置</p><p>　　int creat(int N,int list[][MAX+1])</p><p>　　//初始化并創(chuàng)建地圖的鄰接矩陣&l

21、t;/p><p>　　3.2、兩點是否鄰接的偽碼算法</p><p>　　int link(int x,int *dc,int n,int list[][MAX+1])</p><p><b>　　{</b></p><p>　　//從1到n看是否與x相鄰，是返回‘1’</p><p>　　// 否則

22、，返回‘0’</p><p>　　for(i=0;i<n;i++)</p><p>　　if(list[dc[i]][x])return(1);</p><p>　　return(0);</p><p><b>　　}</b></p><p>　　3.3、著色偽碼算法</p>

23、<p>　　int *fco(int *color,int N,int list[][MAX+1])</p><p><b>　　{</b></p><p>　　//遇到一個區(qū)域，給它最小的顏色，看他是否與該種顏色的區(qū)域鄰接，是則另賦</p><p>　　//顏色，否則找下個區(qū)域，如果還不能著色，則前面區(qū)域另設(shè)顏色，直到成功</

24、p><p><b>　　初始化顏色</b></p><p>　　for(i=0;i<N+1;i++)</p><p><b>　　{</b></p><p><b>　　為第一個區(qū)域著色；</b></p><p>　　for(k=0;k<4;k+

25、+)</p><p><b>　　{</b></p><p>　　如果第k種顏色還未有地區(qū)，則將其賦予第i個區(qū)域；</p><p>　　否則，看他是否與第k種顏色的地區(qū)相鄰</p><p>　　if(!link(i,dc[k],mcd[k],list))</p><p><b>　　{&

26、lt;/b></p><p>　　dc[k][mcd[k]]=i;</p><p>　　color[i]=k+1;</p><p>　　mcd[k]=mcd[k]+1;</p><p><b>　　break;</b></p><p><b>　　}</b></p

27、><p><b>　　}</b></p><p>　　if(color[i]==0)i=reset(i,color,mcd,dc,list);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>

28、　　}</b></p><p>　　3.4、將鄰接矩陣存儲偽碼算法</p><p>　　int save(int N,int list[][MAX+1])</p><p><b>　　{</b></p><p>　　//將鄰接矩陣存成文件</p><p><b>　　}<

29、;/b></p><p>　　3.5、主程序和其他函數(shù)的偽碼算法</p><p>　　void main </p><p><b>　　{</b></p><p><b>　　//主程序</b></p><p><b>　　while(1)</b>

30、</p><p><b>　　{</b></p><p>　　//系統(tǒng)初始化，主界面</p><p>　　clrscr();//清屏</p><p><b>　　顯示清單</b></p><p>　　ReadCommand(cmd); //讀入一個操作命令符</p>

31、;<p>　　Interpret(cmd) ; //執(zhí)行操作</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3.6、函數(shù)調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)</p><p><b>　　4、調(diào)試分析</b>&l

32、t;/p><p>　　4.1、首先使用了《離散數(shù)學(xué)》的解決方法，但在測試中國地圖中出錯，因為排序并不能解決遞歸調(diào)用的問題，后來省掉了排序，在使用開始那個例子時，第8</p><p>　　個區(qū)域不能著色，因此，改采用遞歸的方法</p><p>　　4.2、算法的時間復(fù)雜度為O(N),空間復(fù)雜度為O(N*N);</p><p>　　4.3、通過本次試

33、驗，我認(rèn)識到采用遞歸方法比較快捷，實現(xiàn)方便</p><p>　　4.4、由于地圖上各省連接關(guān)系太多，所以這里只給出簡單的測試數(shù)據(jù)，來測試該程序的功能，如下：</p><p>　　給出如下示意圖，省份抽象為點，接壤抽象為有邊相連。</p><p>　　頂點為：a b c d e f g</p><p>　　相鄰邊：a-b a-f b-c

34、b-e b-f c-d c-e c-f d-e e-f e-g f-g</p><p>　　圖（一） 進入程序界面 </p><p>　　圖（二） 輸入頂點數(shù)、邊數(shù)及頂點</p><p>　　圖（三） 輸入每條邊的兩個頂點

35、</p><p>　　圖（四） 輸出運行結(jié)果著色方案</p><p>　　圖（五） 整體截圖</p><p><b>　　5、課程設(shè)計總結(jié)</b></p><p>　　本次課程設(shè)計時間是為期一個星期，然而經(jīng)過一個星期的課程設(shè)計上機實驗操作，而我所選擇的課程設(shè)計題目是“地圖著色問題求解”。在本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的過

36、程，每天下午都是對著電腦不停地分析問題解決問題寫代碼實驗，不然就是翻閱資料、問同學(xué)老師。在完成此項課程設(shè)計任務(wù)期間，我煩惱過、失落過、沒有方向感過，也曾一度熱情高漲。其中的點點滴滴現(xiàn)在想起來都是讓我我回味無窮的。從本次的課程設(shè)計實驗中讓我體會到只有專業(yè)知識過硬基礎(chǔ)扎牢了，同時設(shè)計的是時候做到細(xì)心、耐心、恒心才能運行出你所要的滿意的結(jié)果。</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗的目的不僅僅是為了加強了我們動手，思

37、考分析和解決問題的能力，也讓我們體會學(xué)以致用的過程，同時也對我們鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，有關(guān)思想的認(rèn)識有所提高和加深，并也提高綜合運用本課程所學(xué)知識到實踐中的能力，培養(yǎng)了我們怎樣</p><p>　　選參考書、怎樣用參考書、怎樣查閱相關(guān)手冊以及文獻資料的能力，讓我們逐漸培養(yǎng)獨立思考，深入研究，分析問題，解決問題的能力。</p><p>　　課程設(shè)計實驗課使我認(rèn)識到理論與實際的差別，懂

38、得了怎樣有效高效把理論與實際相結(jié)合的，因而在本次課程設(shè)計實驗課中讓我看到自己的理論知識掌握的程度，對理論知識的認(rèn)識高度，雖然我在構(gòu)思是很花費時間的，調(diào)試時也經(jīng)常遇到這樣或那樣的低級錯誤，然而最終我還是比較順利的完成了自己所選的課程設(shè)計題目，同時也在設(shè)計的過程中不斷的積累自己的實戰(zhàn)經(jīng)驗，為以后的學(xué)習(xí)以及編程打下了一個良好的基礎(chǔ)，其中課程設(shè)計中的不足之處還希望老師能多多指點與建議。</p><p>　　6、附錄 著

39、色后的中國地圖</p><p><b>　　7、參考文獻</b></p><p>　?。?］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2003．</p><p>　　［2］《數(shù)據(jù)結(jié)構(gòu)題集》，嚴(yán)蔚敏，清華大學(xué)出版社，2005．</p><p>　?。?］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），劉大有，高等教育出版社，2004．&

40、lt;/p><p>　?。?］《Data Structure with C++》，William Ford．William Topp，清華大學(xué)出版社，2003．</p><p><b>　　8、程序源代碼</b></p><p>　　#include <stdio.h></p><p>　　#include &l

41、t;stdlib.h></p><p>　　#define MAXedg 100</p><p>　　#define MAX 0</p><p>　　#define N 4 //著色的顏色數(shù)</p><p>　　#define w 1 //兩點之間的權(quán)值</p><p>　　int color[30]={0}

42、;//來存儲對應(yīng)塊的對應(yīng)顏色</p><p>　　typedef char vextype;</p><p>　　typedef int adjtype;</p><p>　　typedef struct //定義圖</p><p><b>　　{</b></p><p>　　vextyp

43、e vexs[MAXedg]; //存放邊的矩陣</p><p>　　adjtype arcs[MAXedg][MAXedg]; //圖的鄰接矩陣</p><p>　　int vnum,arcnum; //圖的頂點數(shù)和邊數(shù)</p><p><b>　　}Graph;</b></p><p>　　//*****

44、******************************************************</p><p>　　int LocateVex(Graph G,char u)</p><p><b>　　{ </b></p><p><b>　　int i;</b></p><p>　

45、　for(i=1;i<=G.vnum;i++)</p><p><b>　　{ </b></p><p>　　if(u==G.vexs[i]) </p><p><b>　　return i;</b></p><p><b>　　}</b></p><

46、p>　　if(i==G.vnum) </p><p><b>　　{ </b></p><p>　　printf("Error u!\n");</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p&

47、gt;<p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　//**********************************************************</p><p>　　Graph CreateGraph(Graph G)

48、 //輸入圖</p><p><b>　　{</b></p><p>　　int i,j,k;</p><p>　　vextype v1,v2;</p><p>　　printf("依次輸入頂點數(shù)和邊數(shù):\n");</p><p>　　scanf("%d%d&quo

49、t;,&G.vnum,&G.arcnum);</p><p>　　getchar();</p><p>　　printf("圖的各個頂點分別為：\n");</p><p>　　for(i=1;i<=G.vnum;i++)</p><p><b>　　{</b></p>

50、<p>　　scanf("%c",&G.vexs[i]); </p><p>　　getchar();</p><p><b>　　} </b></p><p>　　for(i=0;i<=G.vnum;i++)</p><p>　　for(j=0;j<=G.vnum;

51、j++)</p><p>　　G.arcs[i][j]=MAX;</p><p>　　printf("輸入每條邊的兩個頂點(權(quán)值默認(rèn)為1):\n");</p><p>　　for(k=0;k<G.arcnum;k++)</p><p><b>　　{</b></p><p&g

52、t;　　scanf("%c", &v1);getchar();</p><p>　　scanf("%c", &v2);getchar();</p><p>　　i=LocateVex(G,v1);</p><p>　　j=LocateVex(G,v2);</p><p>　　G.arcs

53、[i][j]=G.arcs[j][i]=w;</p><p><b>　　}</b></p><p><b>　　return G;</b></p><p><b>　　}</b></p><p>　　//************************************

54、****************************</p><p>　　void PrintGraph(Graph G) //輸出圖的信息</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　printf("此圖的頂點

55、為：\n");</p><p>　　for(i=1;i<=G.vnum;i++)</p><p>　　printf("%c ",G.vexs[i]);</p><p>　　printf("\n");</p><p>　　printf("此圖的鄰接矩陣為：\n");&l

56、t;/p><p>　　for(i=1;i<=G.vnum;i++)</p><p><b>　　{</b></p><p>　　for(j=1;j<=G.vnum;j++)</p><p>　　printf("%d ",G.arcs[i][j]);</p><p>　

57、　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//******************************************************************</p><p&g

58、t;　　int colorsame(int s,Graph G)//判斷這個顏色能不能滿足要求</p><p><b>　　{</b></p><p>　　int i,flag=0;</p><p>　　for(i=1;i<=s-1;i++)//分別與前面已經(jīng)著色的幾塊比較</p><p>　　if(G.arcs[

59、i][s]==w&&color[i]==color[s])</p><p><b>　　{</b></p><p>　　flag=1;break;</p><p><b>　　}</b></p><p>　　return flag;</p><p><b

60、>　　}</b></p><p>　　//******************************************************************</p><p>　　void output(Graph G)//輸出函數(shù)</p><p><b>　　{</b></p><p>

61、;<b>　　int i;</b></p><p>　　for(i=1;i<=G.vnum;i++)</p><p>　　printf("%d ",color[i]);</p><p>　　printf("\n");</p><p><b>　　}</b>

62、;</p><p>　　//******************************************************************</p><p>　　void trycolor(int s,Graph G)//s為開始圖色的頂點，本算法從1開始</p><p><b>　　{</b></p><

63、;p><b>　　int i;</b></p><p>　　if(s>G.vnum)//遞歸出口</p><p><b>　　{</b></p><p>　　output(G);</p><p><b>　　exit(1);</b></p><p

64、><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(i=1;i<=N;i++)//對每一種色彩逐個測試</p><p><b>　　{</b></p&

65、gt;<p>　　color[s]=i;</p><p>　　if(colorsame(s,G)==0)</p><p>　　trycolor(s+1,G);//進行下一塊的著色</p><p><b>　　}</b></p><p><b>　　}</b></p>&l

66、t;p><b>　　}</b></p><p>　　//*****************************************************************</p><p>　　void main()</p><p><b>　　{ </b></p><p>&l

67、t;b>　　Graph G;</b></p><p>　　G = CreateGraph(G);</p><p>　　PrintGraph(G);</p><p>　　printf("本次的著色方案為:\n"); </p><p>　　trycolor(1,G);</p><p>