《数据结构课程设计地图着色问题》由会员分享，可在线阅读，更多相关《数据结构课程设计地图着色问题（17页珍藏版）》请在金锄头文库上搜索。
1、1课课程程设设计计报报告告课课程程设设计计题题目目：地地图图着着色色问问题题专专业业： xxxxxxxxx班班级级： xxxxxxxxx姓姓名名： xxxxxxxxx2一：需求分析：一：需求分析：1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证 使用的颜色总数最少； 2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；3)演示程序以用户和计算机的对话方式进行； 4)最后对结果做出简单分析。二：概要设计二：概要设计一：设计思路把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色， 如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就
2、是用这 种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复 上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束 着色。二：数据结构设计因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构 选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶 点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存 储。 其中： typedef struct ArcNode int x; （表示与当前顶点所表示省份相邻的省份的位置信息） struct ArcNode *next; （指向下一个弧结点） ArcNode; （表示省份之间相
3、邻关系的弧结点） typedef struct char *name; （顶点所表示的省份的名称） int color; （省份的颜色，用数字表示不同的颜色） ArcNode *firstnext; （指向第一个弧） shengfen35;3三：详细设计三：详细设计该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。1.初始化模块声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。2.着色模块为各个省份着色。 for(i=1;ix.color) p=p-next; if(p!=NULL) j+; shengi.color=j; 3.输出模块输出各个省份的颜色信息。 for
4、(i=1;i #include typedef struct ArcNode int x; struct ArcNode *next; ArcNode; typedef struct char *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,*hu1 4,*hu15,*hu16,*hu17,*hu18; ArcNo
5、de *hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu 31,*hu32,*hu33,*hu34,*hu35; ArcNode *hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu 48,*hu49,*hu50,*hu51,*hu52; ArcNode *hu53,*hu54,*hu55,*hu56,*hu57,*hu58,*hu59,*hu60,*hu61,*hu62,*hu63,*hu64,*
6、hu 65,*hu66; ArcNode *hu67,*hu68,*hu69,*hu70,*hu71,*hu72,*hu73,*hu74,*hu75,*hu76,*hu77,*hu78,*hu 79,*hu80,*hu81,*hu82,*hu83,*hu84; ArcNode *hu85,*hu86,*hu87,*hu88,*hu89,*hu90,*hu91,*hu92,*hu93,*hu94,*hu95,*hu96,*hu 97,*hu98,*hu99,*hu100; ArcNode *hu101,*hu102,*hu103,*hu104,*hu105,*hu106,*hu107,*hu10
7、8,*hu109,*hu110,*hu1 11,*hu112,*hu113,*hu114,*hu115,*hu116,*hu117; ArcNode *hu118,*hu119,*hu120,*hu121,*hu122,*hu123,*hu124,*hu125,*hu126,*hu127,*hu1 28,*hu129; ArcNode *hu130,*hu131,*hu132,*hu133,*hu134,*hu135,*hu136,*hu137,*hu138,*hu139,*hu1640,*hu141,*hu142; hu1=(ArcNode *)malloc(sizeof(ArcNode);
8、 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(ArcNode); hu9=(ArcNode *)malloc(size
9、of(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 *)malloc(sizeof(ArcNode); hu17=(A
10、rcNode *)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=(ArcNode *)malloc(size
11、of(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(ArcNode); hu32=(A
12、rcNode *)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(size
13、of(ArcNode); hu40=(ArcNode *)malloc(sizeof(ArcNode); hu41=(ArcNode *)malloc(sizeof(ArcNode); hu42=(ArcNode *)malloc(sizeof(ArcNode); hu43=(ArcNode *)malloc(sizeof(ArcNode);7hu44=(ArcNode *)malloc(sizeof(ArcNode); hu45=(ArcNode *)malloc(sizeof(ArcNode); hu46=(ArcNode *)malloc(sizeof(ArcNode); hu47=(A
14、rcNode *)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(size
15、of(ArcNode); 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=(A
16、rcNode *)malloc(sizeof(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 *)malloc(sizeof(ArcNode); hu71=(ArcNode *)mal
