数据结构课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目：地图着色
一、需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1.问题描述
现在有一张地图，为了便于区别各个地图上的版块，地图上相邻的颜色块应该是不同颜色。现在的任务是给定一张地图，要对其进行着色，相邻版块之间颜色不能相同，输出最后的着色
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。
2.基本功能：
功能一：为了程序的灵活性，可以让程序自由建立图。
功能二：对建好的图进行着色。
3.输入输出
输入一张图的信息，正数输入边数和顶点数，输入边的关系，输入边的关系就是输入一条边的两个顶点。颜色只用四种，所以每个结点的颜色域值只能取1到4
输出时根据每个顶点不同的标号输出着色的结果。
二、 概要设计
1.设计思路
给定四种颜色，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，知道所有的顶点都处理完后结束着色。
2.数据结构设计：
因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。
抽象数据类型图的定义如下：
数据对象V:V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：
R={VR}
VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在的路径}
基本操作P:
CreateGraph(&G)
操作结果：创建一张需要操作的无向图G
Destroy(Graph &G)
初始条件：无向图G存在
操作结果：销毁图G
Locate(&G,i)
初始条件：无向图G存在
操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息
Traverse(current, &G, store[])
初始条件：无向图G存在，在图中有第current个顶点
操作结果：对图开始遍历，并且用他们的序号在store数组的相应位置上存储所染上的颜色
print(&G)
初始条件：无向图G存在
操纵结果：打印图G中每个顶点的颜色着色情况
is_different(test, G )
初始条件：无向图G存在，test为图中的一个顶点
操作结果：如果图G中test的邻接顶点颜色都不与test相同，则返回真，否则返回假
3.软件结构设计：
本程序分为两 个模块：
1. 主程序模块
int main()
{
建立一张图G
建立存储最终着色结果的数组
对地图进行着色
打印地图着色的情况
销毁图
退出
}
无向操作图模块 ----------无向图中结点的赋值，遍历
三、 详细设计
#define MAX_NUM 30
struct ArcNode{
int data;
ArcNode *arcnext;
};
typedef struct{
int vexdata;
Colour clo;
ArcNode *firstnext;
}VNode,Adjlist[MAX_NUM];
typedef struct {
Adjlist vexlist;
int arcnum,vexnum;
}Graph;
图的基本操作：
void CreateGraph(Graph& MyGraph)
//创建一个要求的无向图
int is_different(VNode test,Graph G )
//如果结点test中的颜色和图G中和他相邻的结点颜色不同，返回TRUE，否则返回FALSE
void Traverse(int current,Graph &G,int store[])
//对图G进行遍历，并且将分配的颜色按他在邻接表中的位置赋值到store中相应的位置
void Destroy(Graph &G)
//销毁已经存在的无向图G
int Locate(Graph MyGraph,int signal)
寻找无向图中顶点为i的结点，返回其位置
以上重要函数的的伪码算法
int is_different(VNode test,Graph G )
{
i=text.clo
for(j=0;j
arcnext;
free(p);
p=q;
}
}
}
函数调用关系图：
四、调试分析
1.本程序的主要功能是自己建立一个图，然后对图进行着色，支持的数据类型是整形，用不同的数字表示不同的颜色。
2.程序中完成着色的函数利用递归，从第一个结点开始判断，顺序判断
如果有n个顶点，应该能够进入n层递归。因为利用的是邻接表，所以比邻接矩阵消耗的数据空间小得多，如果有n个顶点，邻接数组占用O(n)的空间。
3.在写着色函数的时候，刚开始不知道怎么控制递归的出口，即如何判断最后一个元素已经被着上色了。后来查阅资料后，如果有n个顶点，则第n+1层递归就应该停止，所以可以用当前递归层数与图的结点个数比较来控制出口。程序中由于设计动态分配，最后销毁空间的时候把销毁顺序弄错，导致程序总是崩溃，细细调试一阵后终于完成了任务。
4.程序中的关系结构应为是手动输入，所以对于大的图输入起来比较麻烦，应该可以把文件读取部分加入到程序里，减少输入程序的工作量。
5.地图着色中只是着色方案中的一种，我们可以试着将所有的着色方案都能够列出来，这样在真正的工程应用中可以提供更多的可选方案，程序也能更加灵活。
五、测试结果
测试数据1：
对下图进行着色。
测试数据二：
对下图着色
六、用户手册
1.进入操作界面
2.按照屏幕的指令进行建图
输入边数和顶点数
3.输入边数后系统会显示输入的边数和顶点数,输入边的关系
4.输入完毕后系统会以邻接表的方式显示出整个表，供用户核对
5.最后系统自动给出着色的方案
6.最后询问用户是否需要对其他图进行着色操作
七、体会与自我评价
编写地图着色以后的体会
本次题目是我选择的图操作的一个问题，设计到图的邻接顶点的访问和图的遍历。图的存储结构我选择的是邻接表的形式，，在遍历图时是从第一个顶点开始，一次在定点数组中完成所有顶点的遍历，保证了全部的顶点都是可以访问到的。因为要对地图着色，所以着色是一个动态的过程，可以在遍历的过程中完成对地图的着色，每次访问一个结点，先赋值第一种颜色，如果和它的的邻接点的颜色不重复，则对下个顶点开始着色，否则本顶点的颜色转换到下一种，直到能够完成赋值。程序编写本身并不难，思路很清晰，就是赋值和比较之间的来回循环。
写程序的时候查阅了着色问题，直到了这个问题是用计算机进行证明的，地图到目前为止还没有出现这个证明的反例；而且也明白了计算机在现代数学中的重要作用，因为如果没办法归纳证明，那就可以使用计算机进行穷举，只要穷举出来没有反例出现，则可以说明他没有问题。
在题目要求中说是中国地图，但是我觉得为了程序的灵活性，应该能够对任意图进行着色，所以我增加了建图的功能，使他可以对不同的图进行操作。
本次实验中巩固了我对图这种数据结构的认识，掌握了图的建立，图的数据的存取，使我在这块知识上的认识更加巩固了。
浙公网安备 33021202002483