数据结构——地图填色问题.doc

此文档收集于网络，仅供学习与交流，如有侵权请联系网站删除数据结构实验报告院系 光电与信息工程学院 专业 电子信息工程姓名 学号 电话 2011级 2班 2013年5月22日一、 实验题目数据结构期末综合实验地图填色问题二、 问题描述1976年。美国科学家APPEL和HAKEN利用计算机证明了：对一张地图，可以用不超过4种颜色对其填色，使得相邻的区域填上不同的颜色。要求输入一张行政区地图，用4种颜色对其填色，要求相邻的行政区域内没有相同的颜色，给出所有的填色方案，并统计方案个数。三、 数据描述首先考虑如何存储行政区域图，由于邻接矩阵能更好地描述各行政区之间的关系，所以采用邻接矩阵G来存储地图。G I , J =1 表示I ， J 两个行政区域相邻，为0表示不相邻可采用二维数组来表示邻接矩阵G；另外设一数组COLORI记录各行政区域所填颜色，分别取值为1（红色），2（黄色），3（蓝色），4（绿色）；数据描述如下：INT GNN;INT COLORN+1;四、 概要设计（1） 全局变量定义#define MAX_VERTEX_NUM26/ 最大行政区域个数/- 邻接矩阵数据类型的定义-typedef structchar vexsMAX_VERTEX_NUM;/ 行政区域-顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum;/ 地图当前行政区域个数Graph ;int ColorMAX_VERTEX_NUM+1;/ 地图行政区域填充的颜色存储数组long int Count=0;/ 统计总共的填色方案个数（2） 本程序主要包含6个函数： 主函数main() 创建地图及行政区域的邻接矩阵 Create_Graph () 显示行政区域的邻接矩阵关系Printf_Graph () 对地图行政区域进行第一次着色Load_Color () 对地图行政区域进行各种方案着色的显Print_Color () 判断这个颜色对第n行政区域能不能满足要求Same_Color（）Create_Graph各函数间调用关系如下：Printf_GraphMain（）Load_ColorSame_ColorPrint_Color（3） 主函数的伪码main() 定义一个邻接矩阵 G； 创建地图及行政区域的邻接矩阵； 显示行政区域的邻接矩阵关系；对地图进行填充颜色；改变颜色，显示多种方案；五、 详细设计/- 邻接矩阵数据类型的定义-#define MAX_VERTEX_NUM26/ 最大行政区域个数typedef structchar vexsMAX_VERTEX_NUM;/ 行政区域-顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum;/ 地图当前行政区域个数Graph ;/*函数：Create_Graph*功能：建立地图的邻接矩阵 *说明：输入参数 Graph *G本函数很好的完成了地图的创建以及行政区域之间的存储。在输入错误的时候，会有相应的指示，使得程序更加健壮。*/void Create_Graph( Graph *G )/ 建立地图行政区域的邻接矩阵输入地图的行政区域的个数G-vexnum ；输入行政区域，构造行政区域-顶点向量 ；初始化邻接矩阵都为0；构造行政区域邻接矩阵；输入与V1 相邻的行政区域，存放于 S 数组中；相邻的行政区域G-acrsij=1；/*函数：Printf_Graph*功能：显示地图行政区域的邻接矩阵 *说明：输入参数 Graph G。本函数很好的完成了地图行政区域的邻接矩阵的显示*/void Printf_Graph( Graph G )构造图形；横向显示 行政区域；纵向显示 行政区域；显示邻接矩阵；/*函数：Same_Color*功能：判断这个颜色对第n行政区域能不能满足要求*说明：输入参数 Graph G，int n，输出 0 则表示满足，输出 1 则表示不满足*/int Same_Color(Graph G,int n)Colorn分别与前面已经着色的几块比较；相邻并且颜色一样，则不满足；颜色满足 返回0颜色不满足 返回 1/*函数：Load_Color*功能：对地图行政区域进行第一次着色 ，始之满足要求*说明：输入参数 Graph G，int n*/void Load_Color( Graph G , int n )取一种颜色If(颜色满足，没有与前面冲突)下一块行政区域着色Load_Color(G,n+1);Else尝试另一种颜色/*函数：Print_Color*功能：对地图行政区域进行各种方案的显示。*说明：输入参数 Graph G，int m注意：调用本函数的前提是Color数组中有一个正确的填充颜色的方案。*/void Print_Color( Graph G , int m)for(i=1;i=4;i+)更换颜色，新的颜色不与前面冲突，颜色满足下一个行政区域Print_Color( G , m+1 ) ;直到（到最后一个行政区域,递归出口）遍历数组Color，显示所有行政区域颜色，新的方案； /*主函数*/Void main() 定义一个邻接矩阵 G；创建地图及行政区域的邻接矩阵；显示行政区域的邻接矩阵关系；对地图进行填充颜色；改变颜色，显示多种方案；六、 测试结果七、 参考文献数据结构八、 附录#include #include #include #include /*数据结构期末综合实验*/题目：地图填色问题#define MAX_VERTEX_NUM26/ 最大行政区域个数/- 邻接矩阵数据类型的定义-typedef structchar vexsMAX_VERTEX_NUM;/ 行政区域-顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum;/ 地图当前行政区域个数Graph ;/*函数：Create_Graph*功能：建立地图的邻接矩阵 *说明：输入参数 Graph *G本函数很好的完成了地图的创建以及行政区域之间的存储。在输入错误的时候，会有相应的指示，使得程序更加健壮。*/void Create_Graph( Graph *G )/ 建立地图行政区域的邻接矩阵int i , j , k , t ;/ 变量的定义char sMAX_VERTEX_NUM;/ 暂时存放与某一行政区域相邻的行政区域char tempMAX_VERTEX_NUM;/ 临时数组char V1 , V2 ;/ 相邻的两个行政区域的顶点向量Start:G-vexnum =0;/ 初始化，总的行政区域个数为 0printf(输入地图的行政区域的个数(不超过26个):t); scanf(%d,&G-vexnum);gets(temp);if( G-vexnum vexnum 27)/ 输入的数值不在026之间重新开始goto Start;for(i=0;ivexnum;i+)/ 构造 行政区域-顶点向量New_Input:for(t=0;tvexsi);gets(temp);if(G-vexs iz|G-vexs i0)/ 输入的不为单字符，重新输入printf(输入的不为单字符，重新输入n);goto New_Input;for(t=0;tvexs i=G-vexs t)printf(输入的行政区域之前已经输入过，重新输入n);goto New_Input;for(i=0;ivexnum;i+)/ 初始化邻接矩阵for(j=0;jvexnum;j+)G-acrsij=0 ;/ 都为0for(k=0;kvexnum;k+)/ 构造行政区域邻接矩阵New_Inputs:printf(请输入与%c相邻的行政区域,已有相邻行政区域有： ,G-vexsk);for(t=0;tvexnum ;t+)/ 显示与 Mg-vexsk 已经相邻的行政区域if(G-acrskt=1)printf(%c ,G-vexst);printf(n);V1=G-vexsk;/ V1 行政区域i=k;/ 确定 v1 在 G-vexs 中的位置 为 ifor(t=0;tMAX_VERTEX_NUM;t+)/ 清空 S 数组st=NULL;t=0;while(tvexnum)/ 输入与V1 相邻的行政区域，存放于 S 数组中scanf(%c , &st);if(s0=n) break;/ 没有的话就直接跳出if(getchar()=n) break;t+;for(t=0;tvexnum ;t+)/ 确定行政区域V1与其相邻的行政区域的关系，遍历数组 Sif(st!=NULL&st!=n)V2=st;/ V2 行政区域for(j=0;G-vexsj!=V2;j+);/ 确定 v2 在 G 中的位置 为 jif(jG-vexnum)/ 输入的元素不正确则显示 错误,要求重新输入printf(输入有误，请重新输入n);goto New_Inputs;if(V1!=V2)/ 输入的相邻行政区域与本身不相同G-acrsij=G-acrsji=1;/ 置v1,v2的对称弧v2,v1/*函数：Printf_Graph*功能：显示地图行政区域的邻接矩阵 *说明：输入参数 Graph G。本函数很好的完成了地图行政区域的邻接矩阵的显示*/void Printf_Graph( Graph G )int i , j ;printf(地图的邻接矩阵表示，相邻的用1表示n );printf( );/ 构造图形for(i=0;iG.vexnum ;i+)/ 横向显示 行政区域printf(%c ,G.vexs i);printf(n );for(i=0;iG.vexnum*4+3 ;i+)/ 显示相应长度的-printf(- );printf(n );for(i=0;iG.vexnum ;i+)printf(%c ,G.vexs i);/ 纵向显示 行政区域for(j=0;jG.vexnum ;j+)printf(%d ,G.acrsij);/ 显示邻接矩阵printf(n );/_/_int ColorMAX_VERTEX_NUM+1;/ 地图行政区域填充的颜色存储数组long int Count=0;/ 统计总共的填色方案个数/*函数：Same_Color*功能：判断这个颜色对第n行政区域能不能满足要求*说明：输入参数 Graph G，int n，输出 0 则表示满足，输出 1 则表示不满足*/int Same_Color(Graph G,int n) int i ; for(i=0;i=G.vexnum )/ 递归出口printf(n );elsefor(i=1;i=4;i+)Colorn=i;/ 存储颜色if(Same_Color(G,n)=0)/ 颜色满足，没有与前面冲突Load_Color(G,n+1);/ 下一块行政区域break;/*函数：Print_Color*功能：对地图行政区域进行各种方案的显示。*说明：输入参数 Graph G，int m注意：调用本函数的前提是Color数组中有一个正确的填充颜色的方案。*/void Print_Color( Graph G , int m)int i=0, j=0;for(i=1;i=4;i+)/ 尝试更换颜色Colorm=i;if(Same_Color(G,m)=0)/ 新的颜色不与前面冲突，颜色满足if(m=G.vexnum -1)/ 到最后一个行政区域,递归出口for(j=0;jG.vexnum ;j+)/ 遍历数组Color，显示所有行政区域颜色，新的方案！switch(Colorj)case 1:printf(%c区域填红色, ,G.vexs j);break;case 2:printf(%c区域填黄色, ,G.vexs j);break;case 3:printf(%c区域填蓝色, ,G.vexs j);break;case 4:printf(%c区域填绿色, ,G.vexs j);break;printf(n);Count+;