C++和數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 中南大學(xué)

C++和數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目名稱:地圖著色問(wèn)題TOC\o"1-5"\h\z姓 名學(xué) 號(hào)專 業(yè)班 級(jí)指導(dǎo)教師編寫日期2017?7?1二、目錄TOC\o"1-5"\h\z問(wèn)題描述 2系統(tǒng)設(shè)計(jì) 4\o"CurrentDocument"源代碼清單 7\o"CurrentDocument"運(yùn)行結(jié)果測(cè)試與分析 10結(jié)論與心得 12三、正文部分1、問(wèn)題描述（1） 題目：設(shè)計(jì)地圖著色軟件，對(duì)湖南省地圖中的地級(jí)市進(jìn)行著色，要求相鄰地級(jí)市所使用的顏色不同，并保證使用的顏色最少。（2） 題目分析：由地圖著色問(wèn)題很容易想到圖的著色問(wèn)題，因此可以把地圖抽象為無(wú)向圖來(lái)解決地圖的著色問(wèn)題。題目以湖南省地圖為實(shí)際應(yīng)用載體，其本質(zhì)是圖著色問(wèn)題（GraphColoringProblem,GCP）又稱著色問(wèn)題，是最著名的NP-完全問(wèn)題之一。對(duì)地圖的抽象相當(dāng)于對(duì)圖的抽象，即以鄰接矩陣來(lái)實(shí)現(xiàn)地圖的區(qū)域相鄰的描繪，而對(duì)地圖的區(qū)域數(shù)即以圖的頂點(diǎn)數(shù)來(lái)描繪。具體是將湖南省各個(gè)地級(jí)市進(jìn)行編號(hào)，然后利用無(wú)向圖各個(gè)頂點(diǎn)之間的邊來(lái)表示各省的相鄰關(guān)系。地圖著色問(wèn)題與著名四色定理：四色定理是一個(gè)著名的數(shù)學(xué)定理：如果在平面上劃出一些鄰接的有限區(qū)域，那么可以用四種顏色來(lái)給這些區(qū)域染色，使得每?jī)蓚€(gè)鄰接區(qū)域染的顏色都不一樣；另一個(gè)通俗簡(jiǎn)潔的說(shuō)法是：每個(gè)地圖都可以用不多于四種顏色來(lái)染色，而且不會(huì)有兩個(gè)鄰接的區(qū)域顏色相同。這就是著名的四色定理，由四色定理可以想到只需要四種顏色就可以為一個(gè)區(qū)域的地圖著上顏色，而且相鄰區(qū)域的顏色不相同。（3） 基本要求：地圖采用圖型數(shù)據(jù)結(jié)構(gòu)，每個(gè)地級(jí)市為一個(gè)節(jié)點(diǎn)，邊表示對(duì)應(yīng)的兩個(gè)地級(jí)市相鄰；設(shè)計(jì)著色算法，保證鄰接點(diǎn)不是同一種顏色；演示程序以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。（4） 問(wèn)題解決：計(jì)算機(jī)中，圖主要可以用兩種方法表示：鄰接矩陣和鄰接鏈表。N個(gè)頂點(diǎn)的鄰接矩陣是一個(gè)N*N的布爾矩陣，圖中的每一個(gè)頂點(diǎn)都由一行或者一列來(lái)表示，如果從第i個(gè)頂點(diǎn)和第j個(gè)頂點(diǎn)之間有邊連接，則矩陣第i行，第j列的元素等于1，如果沒有邊連接，則等于0，這就是圖的鄰接矩陣表示，那么地圖也可以抽象為一個(gè)圖，其可以用鄰接矩陣來(lái)進(jìn)行模擬：對(duì)于每一個(gè)地圖，我們可以把每一個(gè)區(qū)〔區(qū)域或國(guó)家）看作一個(gè)點(diǎn)，而區(qū)與區(qū)之間的鄰接關(guān)系看作點(diǎn)與點(diǎn)之間的連線。從而將地圖抽象為一個(gè)圖，然后就可以用鄰接矩陣抽象。如下圖：AB

AB其鄰接矩陣為:ABCDEA01100B10111C11001D01001E01111目的：掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解遞歸的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)習(xí)使用圖解決實(shí)際問(wèn)題的能力。2、系統(tǒng)設(shè)計(jì)（1） 總體分析設(shè)計(jì)：已知湖南省地圖，將各地級(jí)市進(jìn)行編號(hào)，然后利用無(wú)向圖頂點(diǎn)之間的邊來(lái)表示各省的相鄰關(guān)系，創(chuàng)建圖的操作，采用圖狀的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)選用鄰接矩陣。首先把14個(gè)地級(jí)市看成14個(gè)頂點(diǎn)，從選定的一號(hào)頂點(diǎn)開始著色，先試第一種顏色，如果這個(gè)顏色與這個(gè)頂點(diǎn)的其他鄰接頂點(diǎn)的顏色不重復(fù)，則這個(gè)頂點(diǎn)就是用這種顏色，程序開始對(duì)下一個(gè)頂點(diǎn)著色；如果著色重復(fù)，則使用下一種顏色重復(fù)上面的操作。著色過(guò)程以一個(gè)遞歸的過(guò)程進(jìn)行，直到所有的頂點(diǎn)都處理完后結(jié)束著色。（2） 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：typedefstruct//定義圖（vextypevexs[MAXedg];//存放邊的矩陣adjtypearcs[MAXedg][MAXedg];//圖的鄰接矩陣intvnum,arcnum; //圖的頂點(diǎn)數(shù)和邊數(shù)}Graph;（3） 給出如下湖南省地圖，省份抽象為點(diǎn)，接壤抽象為有邊相連。得到如下頂點(diǎn)的邊關(guān)系：（注：a為湘西土家族苗族自治州，b為張家界市，c為常德市，d為岳陽(yáng)市，e為懷化市，f為益陽(yáng)市，g為長(zhǎng)沙市，h為婁底市，i為湘潭市，j為邵陽(yáng)市，k為株洲市，l為衡陽(yáng)市，m為永州市，n為郴州市）ab1ae1be1bc1ec1cd1cf1df1dg1ef1fg1eh1ej1hf1hg1hj1hi1hl1gi1ik1gk1il1jl1kl1jm1ml1kn1ln1mn1功能模塊的劃分及模塊間調(diào)用關(guān)系:dpQ~eateGraphD—,PrintGraphOLLocateVeocCtrJtmlQirO-i s^G.vnum，-s-^G.vnumoutput^colorsarneO著色模塊：intcolorsame(ints,GraphG)//判斷這個(gè)顏色能不能滿足要求(inti,flag=0;for(i=1;i<=s-1;i++)//分別與前面已經(jīng)著色的幾塊比較if(G.arcs[i][s]==1&&color[i]==color[s])(flag=1;break;}returnflag;voidoutput(GraphG)//輸出函數(shù)(inti;for(i=1;i<=G.vnum;i++)printf("%d",color[i]);printf(〃\n〃)；}voidtrycolor(ints,GraphG)//s為開始圖色的頂點(diǎn)(inti;if(s>G.vnum)//遞歸出口(output(G);exit(1);}else(for(i=1;i<=N;i++)//對(duì)每一種色彩逐個(gè)測(cè)試(color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//進(jìn)行下一塊的著色}}}3、源代碼清單#include<stdio.h>#include<stdlib.h>#defineMAXedg100#defineMAX0#defineN4//著色的顏色數(shù)intcolor[30]={0};//來(lái)存儲(chǔ)對(duì)應(yīng)塊的對(duì)應(yīng)顏色typedefcharvextype;typedefintadjtype;typedefstruct//定義圖(vextypevexs[MAXedg];//存放邊的矩陣adjtypearcs[MAXedg][MAXedg];//圖的鄰接矩陣intvnum,arcnum; //圖的頂點(diǎn)數(shù)和邊數(shù)}Graph;intLocateVex(GraphG,charu)(inti;for(i=1;i<=G.vnum;i++)(if(u==G.vexs[i])returni;}if(i==G.vnum)(printf("Erroru!\n〃)；exit(1);}return0;}voidCreateGraph(Graph&G) //輸入圖(inti,j,k,w;vextypev1,v2;printf(-輸入湖南省的地級(jí)市數(shù)和相鄰關(guān)系數(shù):\n〃);scanf(〃％d%d〃，&G.vnum,&G.arcnum);getchar();printf("輸入湖南省各地級(jí)市：\n");for(i=1;i<=G.vnum;i++)(scanf("%c",&G.vexs[i]);getchar();}for(i=0;i<=G.vnum;i++)for(j=0;j<=G.vnum;j++)G.arcs[i][j]=MAX;printf(-輸入兩個(gè)相鄰地級(jí)市和權(quán)值(均用1表示)：\n〃)；for(k=0;k<G.arcnum;k++)(scanf("%c",&v1);getchar();scanf("%c",&v2);getchar();scanf("%d",&w);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=w;}}voidPrintGraph(GraphG) //輸出圖的信息(inti,j;printf("湖南省的各地級(jí)市：\n");for(i=1;i<=G.vnum;i++)printf("%c〃,G.vexs[i]);printf(〃\n〃)；printf("圖的鄰接矩陣：\n");for(i=1;i<=G.vnum;i++)(for(j=1;j<=G.vnum;j++)printf("%d〃,G.arcs[i][j]);printf(〃\n〃)；}}intcolorsame(ints,GraphG)//判斷這個(gè)顏色能不能滿足要求(inti,flag=0;for(i=1;i<=s-1;i++)//分別與前面已經(jīng)著色的幾塊比較if(G.arcs[i][s]==1&&color[i]==color[s])(flag=1;break;}returnflag;}voidoutput(GraphG)//輸出函數(shù)(inti;for(i=1;i<=G.vnum;i++)printf("%d",color[i]);printf(〃\n〃)；}voidtrycolor(ints,GraphG)//s為開始圖色的頂點(diǎn)，本算法從1開始inti;if(s>G.vnum)//遞歸出口(output(G);exit(1);}else(for(i=1;i<=N;i++)//對(duì)每一種色彩逐個(gè)測(cè)試(color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//進(jìn)行下一塊的著色}}}intmain()(GraphG;CreateGraph(G);PrintGraph(G);printf("湖南省地圖的著色方案為:\n");trycolor(1,G);return0;}4、運(yùn)行結(jié)果測(cè)試與分析e1e1'C:\Users\AdministratorXDe§lrtop\-果程設(shè)計(jì)Debug\l.exe'QQQQn180QQ00QQ0010Q1110111010101111110Q011001001100110001S10Q101001010000001i~11000000010100000000114e1e1'C:\Users\AdministratorXDe§lrtop\-果程設(shè)計(jì)Debug\l.exe'QQQQn180QQ00QQ0010Q1110111010101111110Q011001001100110001S10Q101001010000001i~11000000010100000000114*注1：a為湘西土家族苗族自治州，b為張家界市，c為常德市，d為岳陽(yáng)市，e為懷化市，f為益陽(yáng)市，g為長(zhǎng)沙市，h為婁底市，i為湘潭市，j為邵陽(yáng)市，k為株洲市，l為衡陽(yáng)市，m為永州市，n為郴州市*注2：1為黃色，2為紅色，3為綠色，4為藍(lán)色輸入邊的關(guān)系，分別用黃紅綠藍(lán)四色為湖南省地圖著色，根據(jù)程序輸出結(jié)果手動(dòng)為湖南省第十頁(yè)共十三頁(yè)地圖作色，得到簡(jiǎn)易著色圖如下所示，如圖所示可知程序運(yùn)行結(jié)果為正確:五、結(jié)論與心得用最少的顏色對(duì)地圖進(jìn)行著色，達(dá)到相鄰區(qū)域的顏色不相同，本次課設(shè)利用了無(wú)向圖頂點(diǎn)之間的邊來(lái)表示各省的相鄰關(guān)系，創(chuàng)建圖的操作，采用圖狀的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)選用鄰接矩陣，著色過(guò)程以一個(gè)遞歸的過(guò)程進(jìn)行，直到所有的頂點(diǎn)都處理完后結(jié)束著色，完成問(wèn)題的解決。通過(guò)此次課程設(shè)計(jì)，對(duì)圖的操作與理解