数据结构课程设计地图着色问题
数据结构课程设计地图着色问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便”。
课程设计报告
课程设计题目：地图着色问题
专业：xxxxxxxxx 班级：xxxxxxxxx 姓名：xxxxxxxxx
一：需求分析：
1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；
2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系； 3)演示程序以用户和计算机的对话方式进行；
4)最后对结果做出简单分析。
二：概要设计
一：设计思路
把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。
二：数据结构设计
因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。
其中：
typedef struct ArcNode { int x;
（表示与当前顶点所表示省份相邻的省份的位置信息）
struct ArcNode *next;
（指向下一个弧结点）}ArcNode;
（表示省份之间相邻关系的弧结点）typedef struct { char *name;（顶点所表示的省份的名称）
int color;
（省份的颜色，用数字表示不同的颜色）
ArcNode *firstnext;（指向第一个弧）}shengfen[35];
三：详细设计
该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。
1.初始化模块
声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。
2.着色模块
为各个省份着色。for(i=1;i
sheng[i].color=0;} for(i=1;i
j=1;
p=sheng[i].firstnext;
while(p!=NULL)
{
while(p!=NULL&&j!=sheng[p->x].color)
{
p=p->next;
}
if(p!=NULL)
j++;
}
sheng[i].color=j;} 3.输出模块
输出各个省份的颜色信息。
for(i=1;i
printf(“%s:”,sheng[i].name);
printf(“%dn”,sheng[i].color);}
printf(“/n0表示白色,1表示蓝色,2表示红色,3表示绿色,4表示黄色”);return 0;
四：调试分析
因为我们的程序已知是中国地图，为中国地图染色，所以程序没有输入，只有输出信息。从输出的信息来看，我们最多使用了4种颜色。关于程序测试时存在的问题，我们程序在写完之后，出现了没有错误但是无法输出信息的问题，从网上查找发现是对警告没处理好的原因，随后我们参考了网上的解决方案把问题解决了。关于程序的改进，我们的程序使用的是有向图，但省份之间的相邻关系用无向图就可以表示，这是程序可以改进的地方。其次，我们的程序输出结果描述省份颜色的是数字，也可以改进后使之输出具体的颜色。
五：源程序清单
#include #include typedef struct ArcNode{ int x;struct ArcNode *next;}ArcNode;typedef struct{ char *name;int color;ArcNode *firstnext;}shengfen[35];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,*hu35;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,*hu81,*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,*hu123,*hu124,*hu125,*hu126,*hu127,*hu128,*hu129;ArcNode *hu130,*hu131,*hu132,*hu133,*hu134,*hu135,*hu136,*hu137,*hu138,*hu139,*hu1
40,*hu141,*hu142;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(ArcNode));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 *)malloc(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=(ArcNode *)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(ArcNode));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(sizeof(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=(ArcNode *)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));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(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 *)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));hu78=(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(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 *)malloc(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=(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(sizeof(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=(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(sizeof(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=(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(sizeof(ArcNode));hu139=(ArcNode *)malloc(sizeof(ArcNode));hu140=(ArcNode *)malloc(sizeof(ArcNode));hu141=(ArcNode *)malloc(sizeof(ArcNode));hu142=(ArcNode *)malloc(sizeof(ArcNode));sheng[1].name=“heilongjiang”;hu1->x=2;hu2->x=4;sheng[1].firstnext=hu1;hu1->next=hu2;hu2->next=NULL;sheng[2].name=“jilin”;hu3->x=4;hu4->x=3;hu141->x=1;sheng[2].firstnext=hu3;hu3->next=hu4;hu4->next=hu141;hu141->next=NULL;sheng[3].name=“liaoning”;hu5->x=4;hu6->x=10;hu142->x=2;sheng[3].firstnext=hu5;hu5->next=hu6;hu6->next=hu142;hu142->next=NULL;sheng[4].name=“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;sheng[4].firstnext=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;sheng[5].name=“xinjiang”;hu16->x=6;hu17->x=13;hu18->x=16;sheng[5].firstnext=hu16;hu16->next=hu17;hu17->next=hu18;hu18->next=NULL;sheng[6].name=“gansu”;hu19->x=4;hu20->x=7;hu21->x=8;hu22->x=17;hu23->x=13;hu24->x=5;sheng[6].firstnext=hu19;hu19->next=hu20;hu20->next=hu21;hu21->next=hu22;hu22->next=hu23;hu23->next=hu24;hu24->next=NULL;sheng[7].name=“ningxia”;hu25->x=4;hu26->x=8;hu27->x=6;sheng[7].firstnext=hu25;hu25->next=hu26;hu26->next=hu27;hu27->next=NULL;sheng[8].name=“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;sheng[8].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;sheng[9].name=“shanxi2”;hu36->x=4;hu37->x=10;hu38->x=14;hu39->x=8;sheng[9].firstnext=hu36;hu36->next=hu37;hu37->next=hu38;hu38->next=hu39;hu39->next=NULL;sheng[10].name=“hebei”;hu40->x=4;hu41->x=3;hu42->x=11;hu43->x=12;hu44->x=15;hu45->x=14;hu46->x=9;sheng[10].firstnext=hu40;hu40->next=hu41;hu41->next=hu42;hu42->next=hu43;hu43->next=hu44;hu44->next=hu45;hu45->next=hu46;hu46->next=NULL;sheng[11].name=“beijing”;hu47->x=10;sheng[11].firstnext=hu47;hu47->next=NULL;sheng[12].name=“tianjin”;
hu48->x=10;sheng[12].firstnext=hu48;hu48->next=NULL;sheng[13].name=“qinghai”;hu49->x=5;hu50->x=6;hu51->x=17;hu52->x=16;sheng[13].firstnext=hu49;hu49->next=hu50;hu50->next=hu51;hu51->next=hu52;hu52->next=NULL;sheng[14].name=“henan”;hu53->x=9;hu54->x=10;hu55->x=15;hu56->x=21;hu57->x=20;hu58->x=19;hu59->x=8;sheng[14].firstnext=hu53;hu53->next=hu54;hu54->next=hu55;hu55->next=hu56;hu56->next=hu57;hu57->next=hu58;hu58->next=hu59;hu59->next=NULL;sheng[15].name=“shandong”;hu60->x=10;hu61->x=14;hu62->x=21;sheng[15].firstnext=hu60;hu60->next=hu61;hu61->next=hu62;hu62->next=NULL;sheng[16].name=“xizang”;hu63->x=5;hu64->x=13;hu65->x=17;hu66->x=23;sheng[16].firstnext=hu63;hu63->next=hu64;
hu64->next=hu65;hu65->next=hu66;hu66->next=NULL;sheng[17].name=“sichuan”;hu67->x=13;hu68->x=6;hu69->x=8;hu70->x=18;hu71->x=24;hu72->x=23;hu73->x=16;sheng[17].firstnext=hu67;hu67->next=hu68;hu68->next=hu69;hu69->next=hu70;hu70->next=hu71;hu71->next=hu72;hu72->next=hu73;hu73->next=NULL;sheng[18].name=“chongqing”;hu74->x=17;hu75->x=8;hu76->x=19;hu77->x=25;hu78->x=24;sheng[18].firstnext=hu74;hu74->next=hu75;hu75->next=hu76;hu76->next=hu77;hu77->next=hu78;hu78->next=NULL;sheng[19].name=“hubei”;hu79->x=8;hu80->x=14;hu81->x=20;hu82->x=26;hu83->x=25;hu84->x=18;sheng[19].firstnext=hu79;hu79->next=hu80;hu80->next=hu81;hu81->next=hu82;hu82->next=hu83;hu83->next=hu84;
hu84->next=NULL;sheng[20].name=“anhui”;hu85->x=14;hu86->x=21;hu87->x=27;hu88->x=26;hu89->x=19;sheng[20].firstnext=hu85;hu85->next=hu86;hu86->next=hu87;hu87->next=hu88;hu88->next=hu89;hu89->next=NULL;sheng[21].name=“jiangsu”;hu90->x=15;hu91->x=14;hu92->x=20;hu93->x=27;hu94->x=22;sheng[21].firstnext=hu90;hu90->next=hu91;hu91->next=hu92;hu92->next=hu93;hu93->next=hu94;hu94->next=NULL;sheng[22].name=“shanghai”;hu95->x=21;hu96->x=27;sheng[22].firstnext=hu95;hu95->next=hu96;hu96->next=NULL;sheng[23].name=“yunnan”;hu97->x=16;hu98->x=17;hu99->x=24;hu100->x=29;sheng[23].firstnext=hu97;hu97->next=hu98;hu98->next=hu99;hu99->next=hu100;hu100->next=NULL;sheng[24].name=“guizhou”;hu101->x=17;hu102->x=24;
hu103->x=29;hu104->x=23;hu105->x=18;sheng[24].firstnext=hu101;hu101->next=hu102;hu102->next=hu103;hu103->next=hu104;hu104->next=hu105;hu105->next=NULL;sheng[25].name=“hunan”;hu106->x=18;hu107->x=19;hu108->x=26;hu109->x=30;hu110->x=29;hu111->x=24;sheng[25].firstnext=hu106;hu106->next=hu107;hu107->next=hu108;hu108->next=hu109;hu109->next=hu110;hu110->next=hu111;hu111->next=NULL;sheng[26].name=“jiangxi”;hu112->x=25;hu113->x=19;hu114->x=20;hu115->x=27;hu116->x=28;hu117->x=30;sheng[26].firstnext=hu112;hu112->next=hu113;hu113->next=hu114;hu114->next=hu115;hu115->next=hu116;hu116->next=hu117;hu117->next=NULL;sheng[27].name=“zhejiang”;hu118->x=22;hu119->x=21;hu120->x=20;hu121->x=26;hu122->x=28;sheng[27].firstnext=hu118;
hu118->next=hu119;hu119->next=hu120;hu120->next=hu121;hu121->next=hu122;hu122->next=NULL;sheng[28].name=“fujian”;hu123->x=27;hu124->x=26;hu125->x=30;sheng[28].firstnext=hu123;hu123->next=hu124;hu124->next=hu125;hu125->next=NULL;sheng[29].name=“guangxi”;hu126->x=23;hu127->x=24;hu128->x=25;hu129->x=30;sheng[29].firstnext=hu126;hu126->next=hu127;hu127->next=hu128;hu128->next=hu129;hu129->next=NULL;sheng[30].name=“guangdong”;hu130->x=29;hu131->x=25;hu132->x=26;hu133->x=28;hu134->x=31;hu135->x=32;hu136->x=34;sheng[30].firstnext=hu130;hu130->next=hu131;hu131->next=hu132;hu132->next=hu133;hu133->next=hu134;hu134->next=hu135;hu135->next=hu136;hu136->next=NULL;sheng[31].name=“aomen”;hu137->x=30;sheng[31].firstnext=hu137;hu137->next=NULL;sheng[32].name=“xianggang”;
hu138->x=30;sheng[32].firstnext=hu138;hu138->next=NULL;sheng[33].name=“taiwan”;hu139->x=28;sheng[33].firstnext=hu139;hu139->next=NULL;sheng[34].name=“hainan”;hu140->x=30;sheng[34].firstnext=hu140;hu140->next=NULL;for(i=1;i
sheng[i].color=0;} for(i=1;i
j=1;
p=sheng[i].firstnext;
while(p!=NULL)
{
while(p!=NULL&&j!=sheng[p->x].color)
{
p=p->next;
}
if(p!=NULL)
j++;
}
sheng[i].color=j;} for(i=1;i
printf(“%s:”,sheng[i].name);
printf(“%dn”,sheng[i].color);}
printf(“/n0表示白色,1表示蓝色,2表示红色,3表示绿色,4表示黄色”);return 0;}
分类号编号华北水利水电大学North China Institute of Water Conservancy and Hydroelectric Power课程设计题目舞伴问题院系信息工程学院 专业计算机科学与技术姓名贾宁指......
数据结构课程设计报 告设计题目：学生搭配问题专 业： 计算机科学与技术 学生姓名： 班级学号： 分组成员： 指导教师： 学生搭配问题课程设计报告一、设计时间二、设计地点三、......
课 程 设 计 任 务 书信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目： 迷宫求解、一元多项式 课程设计主要参考资料： 数据结构（C语言版） 严蔚敏、吴伟......
数据结构课程设计题目（2013年）一、必做题 1、图书管理系统（线性表） [问题描述]设计一个程序，记录并统计图书使用情况。 [基本要求] （1）图书信息包括图书ID号，图书名，出版社名，出版年月......
课程设计题目1、运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或......
