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

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

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

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

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

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

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

7、;p>　　3.4、將鄰接矩陣存儲(chǔ)偽碼算法- 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è)計(jì)總結(jié)- 12 -</p><p>

8、;　　6、附錄 著色后的中國(guó)地圖- 13 -</p><p>　　7、參考文獻(xiàn)- 14 -</p><p>　　8、程序源代碼- 15 -</p><p>　　1、地圖著色問(wèn)題設(shè)計(jì)</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ū)域的代碼，鄰接可只寫(xiě)一次，區(qū)域的代碼為0～N,N個(gè)為區(qū)域，一個(gè)為外部區(qū)域，或輸入N-1,則可不包括外部區(qū)域，N個(gè)區(qū)域由用戶定義。</p><p>　　1.3、輸出時(shí)，采用一一對(duì)應(yīng)的方法，一個(gè)區(qū)域?qū)?yīng)一種顏色形式：區(qū)域代

10、碼＝＝》顏色代碼（1～4）＝》顏色。</p><p>　　1.4、本程序可為任意一張的地圖染色，并且至多只染四種顏色。</p><p>　　1.5、測(cè)試數(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）存儲(chǔ)地圖 </b></p><p><b>

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

14、;<b>　　ADT list{</b></p><p>　　數(shù)據(jù)對(duì)象：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、本程序包括兩個(gè)模塊</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）地圖模塊――實(shí)現(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è)計(jì)</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; //圖的頂點(diǎn)數(shù)和邊數(shù)</p><p><b>　　}Graph;</b><

20、;/p><p>　　4）功能模塊的劃分及模塊間調(diào)用關(guān)系</p><p><b>　　3、詳細(xì)設(shè)計(jì)</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、兩點(diǎn)是否鄰接的偽碼算法</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>　　//遇到一個(gè)區(qū)域，給它最小的顏色，看他是否與該種顏色的區(qū)域鄰接，是則另賦</p><p>　　//顏色，否則找下個(gè)區(qū)域，如果還不能著色，則前面區(qū)域另設(shè)顏色，直到成功</

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

25、+)</p><p><b>　　{</b></p><p>　　如果第k種顏色還未有地區(qū)，則將其賦予第i個(gè)區(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、將鄰接矩陣存儲(chǔ)偽碼算法</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); //讀入一個(gè)操作命令符</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é)》的解決方法，但在測(cè)試中國(guó)地圖中出錯(cuò)，因?yàn)榕判虿⒉荒芙鉀Q遞歸調(diào)用的問(wèn)題，后來(lái)省掉了排序，在使用開(kāi)始那個(gè)例子時(shí)，第8</p><p>　　個(gè)區(qū)域不能著色，因此，改采用遞歸的方法</p><p>　　4.2、算法的時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(N*N);</p><p>　　4.3、通過(guò)本次試

33、驗(yàn)，我認(rèn)識(shí)到采用遞歸方法比較快捷，實(shí)現(xiàn)方便</p><p>　　4.4、由于地圖上各省連接關(guān)系太多，所以這里只給出簡(jiǎn)單的測(cè)試數(shù)據(jù)，來(lái)測(cè)試該程序的功能，如下：</p><p>　　給出如下示意圖，省份抽象為點(diǎn)，接壤抽象為有邊相連。</p><p>　　頂點(diǎn)為：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>　　圖（一） 進(jìn)入程序界面 </p><p>　　圖（二） 輸入頂點(diǎn)數(shù)、邊數(shù)及頂點(diǎn)</p><p>　　圖（三） 輸入每條邊的兩個(gè)頂點(diǎn)

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

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

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

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

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

40、lt;/p><p>　　［4］《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 //兩點(diǎn)之間的權(quán)值</p><p>　　int color[30]={0}

42、;//來(lái)存儲(chǔ)對(duì)應(yīng)塊的對(duì)應(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; //圖的頂點(diǎn)數(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("依次輸入頂點(diǎn)數(shù)和邊數(shù):\n");</p><p>　　scanf("%d%d&quo

49、t;,&G.vnum,&G.arcnum);</p><p>　　getchar();</p><p>　　printf("圖的各個(gè)頂點(diǎn)分別為：\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("輸入每條邊的兩個(gè)頂點(diǎn)(權(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("此圖的頂點(diǎn)

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)//判斷這個(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為開(kāi)始圖色的頂點(diǎn)，本算法從1開(kāi)始</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++)//對(duì)每一種色彩逐個(gè)測(cè)試</p><p><b>　　{</b></p&

65、gt;<p>　　color[s]=i;</p><p>　　if(colorsame(s,G)==0)</p><p>　　trycolor(s+1,G);//進(jìn)行下一塊的著色</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>