数据结构――地图填色问题

《数据结构》实验报告院系光电与信息工程学院专业电子信息工程姓名学号电话2011级2班2013年5月22日一、实验题目数据结构——期末综合实验——地图填色问题二、问题描述1976年。美国科学家APPEL和HAKEN利用计算机证明了：对一张地图，可以用不超过4种颜色对其填色，使得相邻的区域填上不同的颜色。要求输入一张行政区地图，用4种颜色对其填色，要求相邻的行政区域内没有相同的颜色，给出所有的填色方案，并统计方案个数。三、数据描述首先考虑如何存储行政区域图，由于邻接矩阵能更好地描述各行政区之间的关系，所以采用邻接矩阵G来存储地图。G[I,J]=1表示I，J两个行政区域相邻，为0表示不相邻可采用二维数组来表示邻接矩阵G；另外设一数组COLOR[I]记录各行政区域所填颜色，分别取值为｛1（红色），2（黄色），3（蓝色），4（绿色）｝；数据描述如下：INTG[N][N];INTCOLOR[N+1];四、概要设计（1）全局变量定义#defineMAX_VERTEX_NUM26//最大行政区域个数//-------------------------------邻接矩阵数据类型的定义--------------------------------typedefstruct{charvexs[MAX_VERTEX_NUM];//行政区域-顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum;//地图当前行政区域个数}Graph;intColor[MAX_VERTEX_NUM+1];//地图行政区域填充的颜色存储数组longintCount=0;//统计总共的填色方案个数（2）本程序主要包含6个函数：主函数main()创建地图及行政区域的邻接矩阵Create_Graph()2显示行政区域的邻接矩阵关系Printf_Graph()对地图行政区域进行第一次着色Load_Color()对地图行政区域进行各种方案着色的显Print_Color()判断这个颜色对第n行政区域能不能满足要求Same_Color（）各函数间调用关系如下：（3）主函数的伪码main(){定义一个邻接矩阵G；创建地图及行政区域的邻接矩阵；显示行政区域的邻接矩阵关系；对地图进行填充颜色；改变颜色，显示多种方案；}五、详细设计//-------------------------------邻接矩阵数据类型的定义--------------------------------#defineMAX_VERTEX_NUM26//最大行政区域个数typedefstruct{charvexs[MAX_VERTEX_NUM];//行政区域-顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum;//地图当前行政区域个数}Graph;/*****************************************************************************************函数：Create_Graph*功能：建立地图的邻接矩阵*说明：输入参数Graph*G本函数很好的完成了地图的创建以及行政区域之间的存储。在输入错误的时候，会有相应的指示，使得程序更加健壮。****************************************************************************************/voidCreate_Graph(Graph*G)//建立地图行政区域的邻接矩阵{输入地图的行政区域的个数G-vexnum；输入行政区域，构造行政区域-顶点向量；初始化邻接矩阵都为0；构造行政区域邻接矩阵；Main（）Create_GraphPrintf_GraphLoad_ColorPrint_ColorSame_Color3｛输入与V1相邻的行政区域，存放于S数组中；相邻的行政区域G-acrs[i][j]=1；｝}/*****************************************************************************************函数：Printf_Graph*功能：显示地图行政区域的邻接矩阵*说明：输入参数GraphG。本函数很好的完成了地图行政区域的邻接矩阵的显示****************************************************************************************/voidPrintf_Graph(GraphG){构造图形；横向显示行政区域；纵向显示行政区域；显示邻接矩阵；}/*****************************************************************************************函数：Same_Color*功能：判断这个颜色对第n行政区域能不能满足要求*说明：输入参数GraphG，intn，输出0则表示满足，输出1则表示不满足****************************************************************************************/intSame_Color(GraphG,intn){Color[n]分别与前面已经着色的几块比较；相邻并且颜色一样，则不满足；颜色满足返回0颜色不满足返回1}/*****************************************************************************************函数：Load_Color*功能：对地图行政区域进行第一次着色，始之满足要求*说明：输入参数GraphG，intn****************************************************************************************/voidLoad_Color(GraphG,intn){取一种颜色If(颜色满足，没有与前面冲突)下一块行政区域着色Load_Color(G,n+1);Else尝试另一种颜色}/*****************************************************************************************函数：Print_Color4*功能：对地图行政区域进行各种方案的显示。*说明：输入参数GraphG，intm注意：调用本函数的前提是Color[]数组中有一个正确的填充颜色的方案。****************************************************************************************/voidPrint_Color(GraphG,intm){for(i=1;i=4;i++)更换颜色，新的颜色不与前面冲突，颜色满足{下一个行政区域Print_Color(G,m+1);直到（到最后一个行政区域,递归出口）{遍历数组Color[]，显示所有行政区域颜色，新的方案；}}}/***************************************主函数*******************************************/Voidmain(){定义一个邻接矩阵G；创建地图及行政区域的邻接矩阵；显示行政区域的邻接矩阵关系；对地图进行填充颜色；改变颜色，显示多种方案；}六、测试结果56七、参考文献《数据结构》八、附录#includestdio.h7#includemath.h#includestdlib.h#includestring.h/*数据结构期末综合实验*///~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//题目：地图填色问题~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#defineMAX_VERTEX_NUM26//最大行政区域个数//-------------------------------邻接矩阵数据类型的定义--------------------------------typedefstruct{charvexs[MAX_VERTEX_NUM];//行政区域-顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum;//地图当前行政区域个数}Graph;/*****************************************************************************************函数：Create_Graph*功能：建立地图的邻接矩阵*说明：输入参数Graph*G本函数很好的完成了地图的创建以及行政区域之间的存储。在输入错误的时候，会有相应的指示，使得程序更加健壮。****************************************************************************************/voidCreate_Graph(Graph*G)//建立地图行政区域的邻接矩阵{inti,j,k,t;//变量的定义chars[MAX_VERTEX_NUM];//暂时存放与某一行政区域相邻的行政区域chartemp[MAX_VERTEX_NUM];//临时数组charV1,V2;//相邻的两个行政区域的顶点向量Start:G-vexnum=0;//初始化，总的行政区域个数为0printf(输入地图的行政区域的个数(不超过26个):\t);scanf(%d,&G-vexnum);gets(temp);if(G-vexnum1||G-vexnum27)//输入的数值不在0~26之间重新开始gotoStart;for(i=0;iG-vexnum;i++)//构造行政区域-顶点向量{New_Input:for(t=0;tMAX_VERTEX_NUM;t++)//清空temp数组temp[t]=NULL;printf(请输入第%d个行政区域(用a~z单字符表示):,i+1);8scanf(%c,&G-vexs[i]);gets(temp);if(G-vexs[i]'z'||G-vexs[i]'a'){//输入的单字符不符合，重新输入printf(输入的单字符不符合，重新输入\n);gotoNew_Input;}if(strlen(temp)0)//输入的不为单字符，重新输入{printf(输入的不为单字符，重新输入\n);gotoNew_Input;}for(t=0;ti;t++)//检测当前输入的行政区域与之前有没有冲突，有冲突，重新输入{if(G-vexs[i]==G-vexs[t]){printf(输入的行政区域之前已经输入过，重新输入\n);gotoNew_Input;}}}for(i=0;iG-vexnum;i++)//初始化邻接矩阵for(j=0;jG-vexnum;j++)G-acrs[i][j]=0;//都为0for(k=0;kG-vexnum;k++)//构造行政区域邻接矩阵{New_Inputs:printf(请输入与%c相邻的行政区域,已有相邻行政区域有：,G-vexs[k]);for(t=0;tG-vexnum;t++)//显示与Mg-vexs[k]已