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

2020-03-03 05:35:51 来源：范文大全收藏下载本文

课程设计报告

课程设计题目：地图着色问题

专业：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(\"%d\\n\",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