第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
数据结构课设地图着色问题.doc
一：需求分析：
二：概要设计
一：设计思路
二：数据结构设计
三：详细设计
1.初始化模块
2.着色模块
3.输出模块
四：调试分析
五：源程序清单
课 程 设 计 报 告
课 程 设 计 题 目 ： 地 图 着 色 问 题
专 业 ： xxxxxxxxx
班 级 ： xxxxxxxxx
姓 名 ： xxxxxxxxx
1
一：需求分析：
1) 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使
用的颜色总数最少；
2) 将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；
3) 演示程序以用户和计算机的对话方式进行；
4) 最后对结果做出简单分析。
二：概要设计
一：设计思路
把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，
如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种
颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面
的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。
二：数据结构设计
因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选
用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相
邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。
其中：
typedef struct ArcNode
{
（表示与当前顶点所表示省份相邻的省份的位置信息）
int x;
struct ArcNode *next; （指向下一个弧结点）
（表示省份之间相邻关系的弧结点）
}ArcNode;
typedef struct
{
}shengfen[35];
char *name; （顶点所表示的省份的名称）
int color;
ArcNode *firstnext; （指向第一个弧）
（省份的颜色，用数字表示不同的颜色）
2
三：详细设计
该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。
1.初始化模块
声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。
2.着色模块
while(p!=NULL&&j!=sheng[p->x].color)
{
为各个省份着色。
for(i=1;i<=34;i++)
{
sheng[i].color=0;
}
for(i=1;i<=34;i++)
{
j=1;
p=sheng[i].firstnext;
while(p!=NULL)
{
p=p->next;
}
if(p!=NULL)
j++;
}
sheng[i].color=j;
}
}
3.输出模块
输出各个省份的颜色信息。
for(i=1;i<=34;i++)
{
printf("%s:",sheng[i].name);
printf("%d\n",sheng[i].color);
printf("/n0 表示白色,1 表示蓝色,2 表示红色,3 表示绿色,4 表示黄色");
return 0;
3
四：调试分析
因为我们的程序已知是中国地图，为中国地图染色，所以程序没有输入，只
有输出信息。从输出的信息来看，我们最多使用了 4 种颜色。关于程序测试时存
在的问题，我们程序在写完之后，出现了没有错误但是无法输出信息的问题，从
网上查找发现是对警告没处理好的原因，随后我们参考了网上的解决方案把问题
解决了。关于程序的改进，我们的程序使用的是有向图，但省份之间的相邻关系
用无向图就可以表示，这是程序可以改进的地方。其次，我们的程序输出结果描
述省份颜色的是数字，也可以改进后使之输出具体的颜色。
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,*hu1
4,*hu15,*hu16,*hu17,*hu18;
*hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu
31,*hu32,*hu33,*hu34,*hu35;
*hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu
48,*hu49,*hu50,*hu51,*hu52;
*hu53,*hu54,*hu55,*hu56,*hu57,*hu58,*hu59,*hu60,*hu61,*hu62,*hu63,*hu64,*hu
65,*hu66;
*hu67,*hu68,*hu69,*hu70,*hu71,*hu72,*hu73,*hu74,*hu75,*hu76,*hu77,*hu78,*hu
79,*hu80,*hu81,*hu82,*hu83,*hu84;
*hu85,*hu86,*hu87,*hu88,*hu89,*hu90,*hu91,*hu92,*hu93,*hu94,*hu95,*hu96,*hu
97,*hu98,*hu99,*hu100;
ArcNode
ArcNode
ArcNode
ArcNode
ArcNode
ArcNode
ArcNode
ArcNode
*hu101,*hu102,*hu103,*hu104,*hu105,*hu106,*hu107,*hu108,*hu109,*hu110,*hu1
11,*hu112,*hu113,*hu114,*hu115,*hu116,*hu117;
*hu118,*hu119,*hu120,*hu121,*hu122,*hu123,*hu124,*hu125,*hu126,*hu127,*hu1
28,*hu129;
*hu130,*hu131,*hu132,*hu133,*hu134,*hu135,*hu136,*hu137,*hu138,*hu139,*hu1
5
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));
6
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));
7
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));
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
