数据结构课程设计地图着色问题Word版

1、传播优秀word版文档 ，希望对您有帮助，可双击去除！课程设计报告课程设计题目：地图着色问题专业：xxxxxxxxx班级：xxxxxxxxx姓名：xxxxxxxxx一：需求分析：1) 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；2) 将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；3) 演示程序以用户和计算机的对话方式进行；4) 最后对结果做出简单分析。二：概要设计一：设计思路把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个

2、顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。二：数据结构设计因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。其中：typedef struct arcnodeint x; （表示与当前顶点所表示省份相邻的省份的位置信息）struct arcnode *next; （指向下一个弧结点）arcnode; （表示省份之间相邻关系的弧结点）typedef structchar

3、 *name; （顶点所表示的省份的名称）int color; （省份的颜色，用数字表示不同的颜色）arcnode *firstnext; （指向第一个弧）shengfen35;三：详细设计该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。1.初始化模块声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。2.着色模块为各个省份着色。for(i=1;i<=34;i+)shengi.color=0;for(i=1;i<=34;i+)j=1;p=shengi.firstnext;while(p!=null)while(p!=null&&j!=she

4、ngp->x.color)p=p->next;if(p!=null)j+;shengi.color=j;3.输出模块输出各个省份的颜色信息。for(i=1;i<=34;i+)printf("%s:",);printf("%dn",shengi.color); printf("/n0表示白色,1表示蓝色,2表示红色,3表示绿色,4表示黄色");return 0;四：调试分析因为我们的程序已知是中国地图，为中国地图染色，所以程序没有输入，只有输出信息。从输出的信息来看，我们最多使用了4种颜色。关于程

5、序测试时存在的问题，我们程序在写完之后，出现了没有错误但是无法输出信息的问题，从网上查找发现是对警告没处理好的原因，随后我们参考了网上的解决方案把问题解决了。关于程序的改进，我们的程序使用的是有向图，但省份之间的相邻关系用无向图就可以表示，这是程序可以改进的地方。其次，我们的程序输出结果描述省份颜色的是数字，也可以改进后使之输出具体的颜色。五：源程序清单#include <stdio.h>#include <stdlib.h>typedef struct arcnodeint x;struct arcnode *next;arcnode;typedef structch

6、ar *name;int color;arcnode *firstnext;shengfen35;int main()shengfen sheng;int i,j;arcnode *p,*hu1,*hu2,*hu3,*hu4,*hu5,*hu6,*hu7,*hu8,*hu9,*hu10,*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,*hu3

7、5;arcnode *hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu48,*hu49,*hu50,*hu51,*hu52;arcnode *hu53,*hu54,*hu55,*hu56,*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,*hu8

8、1,*hu82,*hu83,*hu84;arcnode *hu85,*hu86,*hu87,*hu88,*hu89,*hu90,*hu91,*hu92,*hu93,*hu94,*hu95,*hu96,*hu97,*hu98,*hu99,*hu100;arcnode *hu101,*hu102,*hu103,*hu104,*hu105,*hu106,*hu107,*hu108,*hu109,*hu110,*hu111,*hu112,*hu113,*hu114,*hu115,*hu116,*hu117;arcnode *hu118,*hu119,*hu120,*hu121,*hu122,*hu12

9、3,*hu124,*hu125,*hu126,*hu127,*hu128,*hu129;arcnode *hu130,*hu131,*hu132,*hu133,*hu134,*hu135,*hu136,*hu137,*hu138,*hu139,*hu140,*hu141,*hu142;hu1=(arcnode *)malloc(sizeof(arcnode);hu2=(arcnode *)malloc(sizeof(arcnode);hu3=(arcnode *)malloc(sizeof(arcnode);hu4=(arcnode *)malloc(sizeof(arcnode);hu5=(

10、arcnode *)malloc(sizeof(arcnode);hu6=(arcnode *)malloc(sizeof(arcnode);hu7=(arcnode *)malloc(sizeof(arcnode);hu8=(arcnode *)malloc(sizeof(arcnode);hu9=(arcnode *)malloc(sizeof(arcnode);hu10=(arcnode *)malloc(sizeof(arcnode);hu11=(arcnode *)malloc(sizeof(arcnode);hu12=(arcnode *)malloc(sizeof(arcnode

11、);hu13=(arcnode *)malloc(sizeof(arcnode);hu14=(arcnode *)malloc(sizeof(arcnode);hu15=(arcnode *)malloc(sizeof(arcnode);hu16=(arcnode *)malloc(sizeof(arcnode);hu17=(arcnode *)malloc(sizeof(arcnode);hu18=(arcnode *)malloc(sizeof(arcnode);hu19=(arcnode *)malloc(sizeof(arcnode);hu20=(arcnode *)malloc(si

12、zeof(arcnode);hu21=(arcnode *)malloc(sizeof(arcnode);hu22=(arcnode *)malloc(sizeof(arcnode);hu23=(arcnode *)malloc(sizeof(arcnode);hu24=(arcnode *)malloc(sizeof(arcnode);hu25=(arcnode *)malloc(sizeof(arcnode);hu26=(arcnode *)malloc(sizeof(arcnode);hu27=(arcnode *)malloc(sizeof(arcnode);hu28=(arcnode

13、 *)malloc(sizeof(arcnode);hu29=(arcnode *)malloc(sizeof(arcnode);hu30=(arcnode *)malloc(sizeof(arcnode);hu31=(arcnode *)malloc(sizeof(arcnode);hu32=(arcnode *)malloc(sizeof(arcnode);hu33=(arcnode *)malloc(sizeof(arcnode);hu34=(arcnode *)malloc(sizeof(arcnode);hu35=(arcnode *)malloc(sizeof(arcnode);h

14、u36=(arcnode *)malloc(sizeof(arcnode);hu37=(arcnode *)malloc(sizeof(arcnode);hu38=(arcnode *)malloc(sizeof(arcnode);hu39=(arcnode *)malloc(sizeof(arcnode);hu40=(arcnode *)malloc(sizeof(arcnode);hu41=(arcnode *)malloc(sizeof(arcnode);hu42=(arcnode *)malloc(sizeof(arcnode);hu43=(arcnode *)malloc(sizeo

15、f(arcnode);hu44=(arcnode *)malloc(sizeof(arcnode);hu45=(arcnode *)malloc(sizeof(arcnode);hu46=(arcnode *)malloc(sizeof(arcnode);hu47=(arcnode *)malloc(sizeof(arcnode);hu48=(arcnode *)malloc(sizeof(arcnode);hu49=(arcnode *)malloc(sizeof(arcnode);hu50=(arcnode *)malloc(sizeof(arcnode);hu51=(arcnode *)

16、malloc(sizeof(arcnode);hu52=(arcnode *)malloc(sizeof(arcnode);hu53=(arcnode *)malloc(sizeof(arcnode);hu54=(arcnode *)malloc(sizeof(arcnode);hu55=(arcnode *)malloc(sizeof(arcnode);hu56=(arcnode *)malloc(sizeof(arcnode);hu57=(arcnode *)malloc(sizeof(arcnode);hu58=(arcnode *)malloc(sizeof(arcnode);hu59

17、=(arcnode *)malloc(sizeof(arcnode);hu60=(arcnode *)malloc(sizeof(arcnode);hu61=(arcnode *)malloc(sizeof(arcnode);hu62=(arcnode *)malloc(sizeof(arcnode);hu63=(arcnode *)malloc(sizeof(arcnode);hu64=(arcnode *)malloc(sizeof(arcnode);hu65=(arcnode *)malloc(sizeof(arcnode);hu66=(arcnode *)malloc(sizeof(a

18、rcnode);hu67=(arcnode *)malloc(sizeof(arcnode);hu68=(arcnode *)malloc(sizeof(arcnode);hu69=(arcnode *)malloc(sizeof(arcnode);hu70=(arcnode *)malloc(sizeof(arcnode);hu71=(arcnode *)malloc(sizeof(arcnode);hu72=(arcnode *)malloc(sizeof(arcnode);hu73=(arcnode *)malloc(sizeof(arcnode);hu74=(arcnode *)mal

19、loc(sizeof(arcnode);hu75=(arcnode *)malloc(sizeof(arcnode);hu76=(arcnode *)malloc(sizeof(arcnode);hu77=(arcnode *)malloc(sizeof(arcnode);hu78=(arcnode *)malloc(sizeof(arcnode);hu79=(arcnode *)malloc(sizeof(arcnode);hu80=(arcnode *)malloc(sizeof(arcnode);hu81=(arcnode *)malloc(sizeof(arcnode);hu82=(a

20、rcnode *)malloc(sizeof(arcnode);hu83=(arcnode *)malloc(sizeof(arcnode);hu84=(arcnode *)malloc(sizeof(arcnode);hu85=(arcnode *)malloc(sizeof(arcnode);hu86=(arcnode *)malloc(sizeof(arcnode);hu87=(arcnode *)malloc(sizeof(arcnode);hu88=(arcnode *)malloc(sizeof(arcnode);hu89=(arcnode *)malloc(sizeof(arcn

21、ode);hu90=(arcnode *)malloc(sizeof(arcnode);hu91=(arcnode *)malloc(sizeof(arcnode);hu92=(arcnode *)malloc(sizeof(arcnode);hu93=(arcnode *)malloc(sizeof(arcnode);hu94=(arcnode *)malloc(sizeof(arcnode);hu95=(arcnode *)malloc(sizeof(arcnode);hu96=(arcnode *)malloc(sizeof(arcnode);hu97=(arcnode *)malloc

22、(sizeof(arcnode);hu98=(arcnode *)malloc(sizeof(arcnode);hu99=(arcnode *)malloc(sizeof(arcnode);hu100=(arcnode *)malloc(sizeof(arcnode);hu101=(arcnode *)malloc(sizeof(arcnode);hu102=(arcnode *)malloc(sizeof(arcnode);hu103=(arcnode *)malloc(sizeof(arcnode);hu104=(arcnode *)malloc(sizeof(arcnode);hu105

23、=(arcnode *)malloc(sizeof(arcnode);hu106=(arcnode *)malloc(sizeof(arcnode);hu107=(arcnode *)malloc(sizeof(arcnode);hu108=(arcnode *)malloc(sizeof(arcnode);hu109=(arcnode *)malloc(sizeof(arcnode);hu110=(arcnode *)malloc(sizeof(arcnode);hu111=(arcnode *)malloc(sizeof(arcnode);hu112=(arcnode *)malloc(s

24、izeof(arcnode);hu113=(arcnode *)malloc(sizeof(arcnode);hu114=(arcnode *)malloc(sizeof(arcnode);hu115=(arcnode *)malloc(sizeof(arcnode);hu116=(arcnode *)malloc(sizeof(arcnode);hu117=(arcnode *)malloc(sizeof(arcnode);hu118=(arcnode *)malloc(sizeof(arcnode);hu119=(arcnode *)malloc(sizeof(arcnode);hu120

25、=(arcnode *)malloc(sizeof(arcnode);hu121=(arcnode *)malloc(sizeof(arcnode);hu122=(arcnode *)malloc(sizeof(arcnode);hu123=(arcnode *)malloc(sizeof(arcnode);hu124=(arcnode *)malloc(sizeof(arcnode);hu125=(arcnode *)malloc(sizeof(arcnode);hu126=(arcnode *)malloc(sizeof(arcnode);hu127=(arcnode *)malloc(s

26、izeof(arcnode);hu128=(arcnode *)malloc(sizeof(arcnode);hu129=(arcnode *)malloc(sizeof(arcnode);hu130=(arcnode *)malloc(sizeof(arcnode);hu131=(arcnode *)malloc(sizeof(arcnode);hu132=(arcnode *)malloc(sizeof(arcnode);hu133=(arcnode *)malloc(sizeof(arcnode);hu134=(arcnode *)malloc(sizeof(arcnode);hu135

27、=(arcnode *)malloc(sizeof(arcnode);hu136=(arcnode *)malloc(sizeof(arcnode);hu137=(arcnode *)malloc(sizeof(arcnode);hu138=(arcnode *)malloc(sizeof(arcnode);hu139=(arcnode *)malloc(sizeof(arcnode);hu140=(arcnode *)malloc(sizeof(arcnode);hu141=(arcnode *)malloc(sizeof(arcnode);hu142=(arcnode *)malloc(s

28、izeof(arcnode);="heilongjiang"hu1->x=2;hu2->x=4;sheng1.firstnext=hu1;hu1->next=hu2;hu2->next=null;="jilin"hu3->x=4;hu4->x=3;hu141->x=1;sheng2.firstnext=hu3;hu3->next=hu4;hu4->next=hu141;hu141->next=null;="liaonin

29、g"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.firstnext=hu7;hu7->

30、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->

31、next=null;="gansu"hu19->x=4;hu20->x=7;hu21->x=8;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;h

32、u26->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=14;hu31->x=19;hu32->x=18;hu33->x=17;hu34->x=6;hu35->x=7;sheng8.firstnext=hu28;hu28->next=hu29;hu29->next=hu

33、30;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=hu38;hu38->next=hu39;hu39->next=null;

34、="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;="

35、beijing"hu47->x=10;sheng11.firstnext=hu47;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=h

36、u51;hu51->next=hu52;hu52->next=null;="henan"hu53->x=9;hu54->x=10;hu55->x=15;hu56->x=21;hu57->x=20;hu58->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=

37、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=13;hu65->x=17;hu66->x=23;sheng16.firstnext=hu63;hu63->ne

38、xt=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->

39、;next=hu72;hu72->next=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"

40、hu79->x=8;hu80->x=14;hu81->x=20;hu82->x=26;hu83->x=25;hu84->x=18;sheng19.firstnext=hu79;hu79->next=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->

41、;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;hu93->x=27;hu94->x=22;sheng21.firstnext=hu90;hu90->next=hu91;hu91->next=hu92

42、;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;hu97->

43、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=n

44、ull;="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&

45、quot;hu112->x=25;hu113->x=19;hu114->x=20;hu115->x=27;hu116->x=28;hu117->x=30;sheng26.firstnext=hu112;hu112->next=hu113;hu113->next=hu114;hu114->next=hu115;hu115->next=hu116;hu116->next=hu117;hu117->next=null;="zhejiang"hu118->x=22;hu119->x=21;hu120->x=20;hu121->x=26;hu122