數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告地圖著色問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：地圖著色問題專業(yè)：xxxxxxxxx班級(jí)：xxxxxxxxx姓名：xxxxxxxxx一：需求分析：已知中國地圖，對(duì)各省進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少；將各省進(jìn)行編號(hào)，然后利用無向圖個(gè)頂點(diǎn)之間的邊來表示各省的相鄰關(guān)系；演示程序以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行；最后對(duì)結(jié)果做出簡(jiǎn)單分析。二：概要設(shè)計(jì)一：設(shè)計(jì)思路把34個(gè)省看成34個(gè)頂點(diǎn)，從選定的第一個(gè)頂點(diǎn)開始著色，先試第一種顏色，如果這個(gè)顏色與這個(gè)頂點(diǎn)的其他鄰接頂點(diǎn)的顏色不

2、重復(fù)，則這個(gè)頂點(diǎn)就是用這種顏色，程序開始對(duì)下一個(gè)頂點(diǎn)著色；如果著色重復(fù)，則使用下一種顏色重復(fù)上面的操作。著色過程就是一個(gè)遞歸的過程，直到所有的頂點(diǎn)都處理完后結(jié)束著色。二：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)因?yàn)檫@個(gè)程序是對(duì)圖的操作，所以程序采用的邏輯結(jié)構(gòu)是圖狀，存儲(chǔ)結(jié)構(gòu)選用鄰接表，考慮用鄰接表是因?yàn)橐话愕牡貓D的某一個(gè)頂點(diǎn)并不會(huì)與很多的頂點(diǎn)相鄰接，如果用鄰接矩陣會(huì)浪費(fèi)很多的存儲(chǔ)空間，所以我選擇的鄰接表來存儲(chǔ)。其中：typedef struct ArcNodeint x; （表示與當(dāng)前頂點(diǎn)所表示省份相鄰的省份的位置信息）struct ArcNode *next; （指向下一個(gè)弧結(jié)點(diǎn)）ArcNode; （表示省份之間相鄰關(guān)

3、系的弧結(jié)點(diǎn)）typedef structchar *name; （頂點(diǎn)所表示的省份的名稱）int color; （省份的顏色，用數(shù)字表示不同的顏色）ArcNode *firstnext; （指向第一個(gè)?。﹕hengfen35;三：詳細(xì)設(shè)計(jì)該程序一共包含三個(gè)模版：分別為初始化模版、著色模版和輸出模版。1.初始化模塊聲明表示省份的頂點(diǎn)信息、省份之間相鄰關(guān)系的弧的信息，并為其賦值。2.著色模塊為各個(gè)省份著色。for(i=1;i=34;i+)shengi.color=0;for(i=1;ix.color)p=p-next;if(p!=NULL)j+;shengi.color=j;3.輸出模塊輸出各個(gè)省

4、份的顏色信息。for(i=1;i=34;i+)printf(%s:,);printf(%dn,shengi.color); printf(/n0表示白色,1表示藍(lán)色,2表示紅色,3表示綠色,4表示黃色);return 0;四：調(diào)試分析因?yàn)槲覀兊某绦蛞阎侵袊貓D，為中國地圖染色，所以程序沒有輸入，只有輸出信息。從輸出的信息來看，我們最多使用了4種顏色。關(guān)于程序測(cè)試時(shí)存在的問題，我們程序在寫完之后，出現(xiàn)了沒有錯(cuò)誤但是無法輸出信息的問題，從網(wǎng)上查找發(fā)現(xiàn)是對(duì)警告沒處理好的原因，隨后我們參考了網(wǎng)上的解決方案把問題解決了。關(guān)于程序的改進(jìn)，我們的程序使用的是有向圖，但省份之間的相鄰關(guān)

5、系用無向圖就可以表示，這是程序可以改進(jìn)的地方。其次，我們的程序輸出結(jié)果描述省份顏色的是數(shù)字，也可以改進(jìn)后使之輸出具體的顏色。五：源程序清單#include #include typedef struct ArcNodeint x;struct ArcNode *next;ArcNode;typedef structchar *name;int color;ArcNode *firstnext;shengfen35;int main()shengfen sheng;int i,j;ArcNode *p,*hu1,*hu2,*hu3,*hu4,*hu5,*hu6,*hu7,*hu8,*hu9,*h

6、u10,*hu11,*hu12,*hu13,*hu14,*hu15,*hu16,*hu17,*hu18;ArcNode *hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu31,*hu32,*hu33,*hu34,*hu35;ArcNode *hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu48,*hu49,*hu50,*hu51,*hu52;ArcNode *hu53,*hu54,*hu55,*h

7、u56,*hu57,*hu58,*hu59,*hu60,*hu61,*hu62,*hu63,*hu64,*hu65,*hu66;ArcNode *hu67,*hu68,*hu69,*hu70,*hu71,*hu72,*hu73,*hu74,*hu75,*hu76,*hu77,*hu78,*hu79,*hu80,*hu81,*hu82,*hu83,*hu84;ArcNode *hu85,*hu86,*hu87,*hu88,*hu89,*hu90,*hu91,*hu92,*hu93,*hu94,*hu95,*hu96,*hu97,*hu98,*hu99,*hu100;ArcNode *hu101,

8、*hu102,*hu103,*hu104,*hu105,*hu106,*hu107,*hu108,*hu109,*hu110,*hu111,*hu112,*hu113,*hu114,*hu115,*hu116,*hu117;ArcNode *hu118,*hu119,*hu120,*hu121,*hu122,*hu123,*hu124,*hu125,*hu126,*hu127,*hu128,*hu129;ArcNode *hu130,*hu131,*hu132,*hu133,*hu134,*hu135,*hu136,*hu137,*hu138,*hu139,*hu140,*hu141,*hu1

9、42;hu1=(ArcNode *)malloc(sizeof(ArcNode);hu2=(ArcNode *)malloc(sizeof(ArcNode);hu3=(ArcNode *)malloc(sizeof(ArcNode);hu4=(ArcNode *)malloc(sizeof(ArcNode);hu5=(ArcNode *)malloc(sizeof(ArcNode);hu6=(ArcNode *)malloc(sizeof(ArcNode);hu7=(ArcNode *)malloc(sizeof(ArcNode);hu8=(ArcNode *)malloc(sizeof(Ar

10、cNode);hu9=(ArcNode *)malloc(sizeof(ArcNode);hu10=(ArcNode *)malloc(sizeof(ArcNode);hu11=(ArcNode *)malloc(sizeof(ArcNode);hu12=(ArcNode *)malloc(sizeof(ArcNode);hu13=(ArcNode *)malloc(sizeof(ArcNode);hu14=(ArcNode *)malloc(sizeof(ArcNode);hu15=(ArcNode *)malloc(sizeof(ArcNode);hu16=(ArcNode *)mallo

11、c(sizeof(ArcNode);hu17=(ArcNode *)malloc(sizeof(ArcNode);hu18=(ArcNode *)malloc(sizeof(ArcNode);hu19=(ArcNode *)malloc(sizeof(ArcNode);hu20=(ArcNode *)malloc(sizeof(ArcNode);hu21=(ArcNode *)malloc(sizeof(ArcNode);hu22=(ArcNode *)malloc(sizeof(ArcNode);hu23=(ArcNode *)malloc(sizeof(ArcNode);hu24=(Arc

12、Node *)malloc(sizeof(ArcNode);hu25=(ArcNode *)malloc(sizeof(ArcNode);hu26=(ArcNode *)malloc(sizeof(ArcNode);hu27=(ArcNode *)malloc(sizeof(ArcNode);hu28=(ArcNode *)malloc(sizeof(ArcNode);hu29=(ArcNode *)malloc(sizeof(ArcNode);hu30=(ArcNode *)malloc(sizeof(ArcNode);hu31=(ArcNode *)malloc(sizeof(ArcNod

13、e);hu32=(ArcNode *)malloc(sizeof(ArcNode);hu33=(ArcNode *)malloc(sizeof(ArcNode);hu34=(ArcNode *)malloc(sizeof(ArcNode);hu35=(ArcNode *)malloc(sizeof(ArcNode);hu36=(ArcNode *)malloc(sizeof(ArcNode);hu37=(ArcNode *)malloc(sizeof(ArcNode);hu38=(ArcNode *)malloc(sizeof(ArcNode);hu39=(ArcNode *)malloc(s

14、izeof(ArcNode);hu40=(ArcNode *)malloc(sizeof(ArcNode);hu41=(ArcNode *)malloc(sizeof(ArcNode);hu42=(ArcNode *)malloc(sizeof(ArcNode);hu43=(ArcNode *)malloc(sizeof(ArcNode);hu44=(ArcNode *)malloc(sizeof(ArcNode);hu45=(ArcNode *)malloc(sizeof(ArcNode);hu46=(ArcNode *)malloc(sizeof(ArcNode);hu47=(ArcNod

15、e *)malloc(sizeof(ArcNode);hu48=(ArcNode *)malloc(sizeof(ArcNode);hu49=(ArcNode *)malloc(sizeof(ArcNode);hu50=(ArcNode *)malloc(sizeof(ArcNode);hu51=(ArcNode *)malloc(sizeof(ArcNode);hu52=(ArcNode *)malloc(sizeof(ArcNode);hu53=(ArcNode *)malloc(sizeof(ArcNode);hu54=(ArcNode *)malloc(sizeof(ArcNode);

16、hu55=(ArcNode *)malloc(sizeof(ArcNode);hu56=(ArcNode *)malloc(sizeof(ArcNode);hu57=(ArcNode *)malloc(sizeof(ArcNode);hu58=(ArcNode *)malloc(sizeof(ArcNode);hu59=(ArcNode *)malloc(sizeof(ArcNode);hu60=(ArcNode *)malloc(sizeof(ArcNode);hu61=(ArcNode *)malloc(sizeof(ArcNode);hu62=(ArcNode *)malloc(size

17、of(ArcNode);hu63=(ArcNode *)malloc(sizeof(ArcNode);hu64=(ArcNode *)malloc(sizeof(ArcNode);hu65=(ArcNode *)malloc(sizeof(ArcNode);hu66=(ArcNode *)malloc(sizeof(ArcNode);hu67=(ArcNode *)malloc(sizeof(ArcNode);hu68=(ArcNode *)malloc(sizeof(ArcNode);hu69=(ArcNode *)malloc(sizeof(ArcNode);hu70=(ArcNode *

18、)malloc(sizeof(ArcNode);hu71=(ArcNode *)malloc(sizeof(ArcNode);hu72=(ArcNode *)malloc(sizeof(ArcNode);hu73=(ArcNode *)malloc(sizeof(ArcNode);hu74=(ArcNode *)malloc(sizeof(ArcNode);hu75=(ArcNode *)malloc(sizeof(ArcNode);hu76=(ArcNode *)malloc(sizeof(ArcNode);hu77=(ArcNode *)malloc(sizeof(ArcNode);hu7

19、8=(ArcNode *)malloc(sizeof(ArcNode);hu79=(ArcNode *)malloc(sizeof(ArcNode);hu80=(ArcNode *)malloc(sizeof(ArcNode);hu81=(ArcNode *)malloc(sizeof(ArcNode);hu82=(ArcNode *)malloc(sizeof(ArcNode);hu83=(ArcNode *)malloc(sizeof(ArcNode);hu84=(ArcNode *)malloc(sizeof(ArcNode);hu85=(ArcNode *)malloc(sizeof(

20、ArcNode);hu86=(ArcNode *)malloc(sizeof(ArcNode);hu87=(ArcNode *)malloc(sizeof(ArcNode);hu88=(ArcNode *)malloc(sizeof(ArcNode);hu89=(ArcNode *)malloc(sizeof(ArcNode);hu90=(ArcNode *)malloc(sizeof(ArcNode);hu91=(ArcNode *)malloc(sizeof(ArcNode);hu92=(ArcNode *)malloc(sizeof(ArcNode);hu93=(ArcNode *)ma

21、lloc(sizeof(ArcNode);hu94=(ArcNode *)malloc(sizeof(ArcNode);hu95=(ArcNode *)malloc(sizeof(ArcNode);hu96=(ArcNode *)malloc(sizeof(ArcNode);hu97=(ArcNode *)malloc(sizeof(ArcNode);hu98=(ArcNode *)malloc(sizeof(ArcNode);hu99=(ArcNode *)malloc(sizeof(ArcNode);hu100=(ArcNode *)malloc(sizeof(ArcNode);hu101

22、=(ArcNode *)malloc(sizeof(ArcNode);hu102=(ArcNode *)malloc(sizeof(ArcNode);hu103=(ArcNode *)malloc(sizeof(ArcNode);hu104=(ArcNode *)malloc(sizeof(ArcNode);hu105=(ArcNode *)malloc(sizeof(ArcNode);hu106=(ArcNode *)malloc(sizeof(ArcNode);hu107=(ArcNode *)malloc(sizeof(ArcNode);hu108=(ArcNode *)malloc(s

23、izeof(ArcNode);hu109=(ArcNode *)malloc(sizeof(ArcNode);hu110=(ArcNode *)malloc(sizeof(ArcNode);hu111=(ArcNode *)malloc(sizeof(ArcNode);hu112=(ArcNode *)malloc(sizeof(ArcNode);hu113=(ArcNode *)malloc(sizeof(ArcNode);hu114=(ArcNode *)malloc(sizeof(ArcNode);hu115=(ArcNode *)malloc(sizeof(ArcNode);hu116

24、=(ArcNode *)malloc(sizeof(ArcNode);hu117=(ArcNode *)malloc(sizeof(ArcNode);hu118=(ArcNode *)malloc(sizeof(ArcNode);hu119=(ArcNode *)malloc(sizeof(ArcNode);hu120=(ArcNode *)malloc(sizeof(ArcNode);hu121=(ArcNode *)malloc(sizeof(ArcNode);hu122=(ArcNode *)malloc(sizeof(ArcNode);hu123=(ArcNode *)malloc(s

25、izeof(ArcNode);hu124=(ArcNode *)malloc(sizeof(ArcNode);hu125=(ArcNode *)malloc(sizeof(ArcNode);hu126=(ArcNode *)malloc(sizeof(ArcNode);hu127=(ArcNode *)malloc(sizeof(ArcNode);hu128=(ArcNode *)malloc(sizeof(ArcNode);hu129=(ArcNode *)malloc(sizeof(ArcNode);hu130=(ArcNode *)malloc(sizeof(ArcNode);hu131

26、=(ArcNode *)malloc(sizeof(ArcNode);hu132=(ArcNode *)malloc(sizeof(ArcNode);hu133=(ArcNode *)malloc(sizeof(ArcNode);hu134=(ArcNode *)malloc(sizeof(ArcNode);hu135=(ArcNode *)malloc(sizeof(ArcNode);hu136=(ArcNode *)malloc(sizeof(ArcNode);hu137=(ArcNode *)malloc(sizeof(ArcNode);hu138=(ArcNode *)malloc(s

27、izeof(ArcNode);hu139=(ArcNode *)malloc(sizeof(ArcNode);hu140=(ArcNode *)malloc(sizeof(ArcNode);hu141=(ArcNode *)malloc(sizeof(ArcNode);hu142=(ArcNode *)malloc(sizeof(ArcNode);=heilongjiang;hu1-x=2;hu2-x=4;sheng1.firstnext=hu1;hu1-next=hu2;hu2-next=NULL;=jilin;hu3-x=4;hu4-x=3;hu

28、141-x=1;sheng2.firstnext=hu3;hu3-next=hu4;hu4-next=hu141;hu141-next=NULL;=liaoning;hu5-x=4;hu6-x=10;hu142-x=2;sheng3.firstnext=hu5;hu5-next=hu6;hu6-next=hu142;hu142-next=NULL;=neimenggu;hu7-x=1;hu8-x=2;hu9-x=3;hu10-x=10;hu11-x=9;hu12-x=8;hu13-x=7;hu14-x=6;hu15-x=5;sheng4.firstn

29、ext=hu7;hu7-next=hu8;hu8-next=hu9;hu9-next=hu10;hu10-next=hu11;hu11-next=hu12;hu12-next=hu13;hu13-next=hu14;hu14-next=hu15;hu15-next=NULL;=xinjiang;hu16-x=6;hu17-x=13;hu18-x=16;sheng5.firstnext=hu16;hu16-next=hu17;hu17-next=hu18;hu18-next=NULL;=gansu;hu19-x=4;hu20-x=7;hu21-x=8;

30、hu22-x=17;hu23-x=13;hu24-x=5;sheng6.firstnext=hu19;hu19-next=hu20;hu20-next=hu21;hu21-next=hu22;hu22-next=hu23;hu23-next=hu24;hu24-next=NULL;=ningxia;hu25-x=4;hu26-x=8;hu27-x=6;sheng7.firstnext=hu25;hu25-next=hu26;hu26-next=hu27;hu27-next=NULL;=shanxi1;hu28-x=4;hu29-x=9;hu30-x=

31、14;hu31-x=19;hu32-x=18;hu33-x=17;hu34-x=6;hu35-x=7;sheng8.firstnext=hu28;hu28-next=hu29;hu29-next=hu30;hu30-next=hu31;hu31-next=hu32;hu32-next=hu33;hu33-next=hu34;hu34-next=hu35;hu35-next=NULL;=shanxi2;hu36-x=4;hu37-x=10;hu38-x=14;hu39-x=8;sheng9.firstnext=hu36;hu36-next=hu37;hu37-next=hu

32、38;hu38-next=hu39;hu39-next=NULL;=hebei;hu40-x=4;hu41-x=3;hu42-x=11;hu43-x=12;hu44-x=15;hu45-x=14;hu46-x=9;sheng10.firstnext=hu40;hu40-next=hu41;hu41-next=hu42;hu42-next=hu43;hu43-next=hu44;hu44-next=hu45;hu45-next=hu46;hu46-next=NULL;=beijing;hu47-x=10;sheng11.firstnext=hu47

33、;hu47-next=NULL;=tianjin;hu48-x=10;sheng12.firstnext=hu48;hu48-next=NULL;=qinghai;hu49-x=5;hu50-x=6;hu51-x=17;hu52-x=16;sheng13.firstnext=hu49;hu49-next=hu50;hu50-next=hu51;hu51-next=hu52;hu52-next=NULL;=henan;hu53-x=9;hu54-x=10;hu55-x=15;hu56-x=21;hu57-x=20;hu58-

34、x=19;hu59-x=8;sheng14.firstnext=hu53;hu53-next=hu54;hu54-next=hu55;hu55-next=hu56;hu56-next=hu57;hu57-next=hu58;hu58-next=hu59;hu59-next=NULL;=shandong;hu60-x=10; hu61-x=14;hu62-x=21;sheng15.firstnext=hu60;hu60-next=hu61;hu61-next=hu62;hu62-next=NULL;=xizang;hu63-x=5;hu64-x=1

35、3;hu65-x=17;hu66-x=23;sheng16.firstnext=hu63;hu63-next=hu64;hu64-next=hu65;hu65-next=hu66;hu66-next=NULL;=sichuan;hu67-x=13;hu68-x=6;hu69-x=8;hu70-x=18;hu71-x=24;hu72-x=23;hu73-x=16;sheng17.firstnext=hu67;hu67-next=hu68;hu68-next=hu69;hu69-next=hu70;hu70-next=hu71;hu71-next=hu72;hu72-nex

36、t=hu73;hu73-next=NULL;=chongqing;hu74-x=17;hu75-x=8;hu76-x=19;hu77-x=25;hu78-x=24;sheng18.firstnext=hu74;hu74-next=hu75;hu75-next=hu76;hu76-next=hu77;hu77-next=hu78;hu78-next=NULL;=hubei;hu79-x=8;hu80-x=14;hu81-x=20;hu82-x=26;hu83-x=25;hu84-x=18;sheng19.firstnext=hu79;hu79-ne

37、xt=hu80;hu80-next=hu81;hu81-next=hu82;hu82-next=hu83;hu83-next=hu84;hu84-next=NULL;=anhui;hu85-x=14;hu86-x=21;hu87-x=27;hu88-x=26;hu89-x=19;sheng20.firstnext=hu85;hu85-next=hu86;hu86-next=hu87;hu87-next=hu88;hu88-next=hu89;hu89-next=NULL;=jiangsu;hu90-x=15;hu91-x=14;hu92-x=20

38、;hu93-x=27;hu94-x=22;sheng21.firstnext=hu90;hu90-next=hu91;hu91-next=hu92;hu92-next=hu93;hu93-next=hu94;hu94-next=NULL;=shanghai;hu95-x=21;hu96-x=27;sheng22.firstnext=hu95;hu95-next=hu96;hu96-next=NULL;=yunnan;hu97-x=16;hu98-x=17;hu99-x=24;hu100-x=29;sheng23.firstnext=hu97;hu

39、97-next=hu98;hu98-next=hu99;hu99-next=hu100;hu100-next=NULL;=guizhou;hu101-x=17;hu102-x=24;hu103-x=29;hu104-x=23;hu105-x=18;sheng24.firstnext=hu101;hu101-next=hu102;hu102-next=hu103;hu103-next=hu104;hu104-next=hu105;hu105-next=NULL;=hunan;hu106-x=18;hu107-x=19;hu108-x=26;hu109-x=30;hu110-x=29;hu111-x=24;sheng25.firstnext=hu106;hu106-next=hu107;hu107-next=hu108;hu108-next=hu109;hu109-next=hu110;hu110-next=hu111;hu111-next=NULL;=jiangxi;hu112-x=25;hu113-x=19;hu114-x=20;hu115-x=27;hu116-x=28;hu117-x