数据结构课程设计报告-地图着色.doc

数据结构课程设计报告题目：地图着色一、需求分析1.问题描述现在有一张地图，为了便于区别各个地图上的版块，地图上相邻的颜色块应该是不同颜色。现在的任务是给定一张地图，要对其进行着色，相邻版块之间颜色不能相同，输出最后的着色方案。2.基本功能：功能一：为了程序的灵活性，可以让程序自由建立图。功能二：对建好的图进行着色。3.输入输出输入一张图的信息，正数输入边数和顶点数，输入边的关系，输入边的关系就是输入一条边的两个顶点。颜色只用四种，所以每个结点的颜色域值只能取1到4输出时根据每个顶点不同的标号输出着色的结果。二、 概要设计1.设计思路给定四种颜色，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，知道所有的顶点都处理完后结束着色。2.数据结构设计：因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。抽象数据类型图的定义如下：数据对象V:V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在的路径基本操作P:CreateGraph(&G)操作结果：创建一张需要操作的无向图GDestroy(Graph &G)初始条件：无向图G存在操作结果：销毁图GLocate(&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 30struct ArcNodeint data;ArcNode *arcnext;typedef structint vexdata;Colour clo;ArcNode *firstnext;VNode,AdjlistMAX_NUM;typedef struct Adjlist vexlist;int arcnum,vexnum;Graph;图的基本操作：void CreateGraph(Graph& MyGraph)/创建一个要求的无向图int is_different(VNode test,Graph G )/如果结点test中的颜色和图G中和他相邻的结点颜色不同，返回TRUE，否则返回FALSEvoid Traverse(int current,Graph &G,int store)/对图G进行遍历，并且将分配的颜色按他在邻接表中的位置赋值到store中相应的位置void Destroy(Graph &G)/销毁已经存在的无向图Gint Locate(Graph MyGraph,int signal)寻找无向图中顶点为i的结点，返回其位置以上重要函数的的伪码算法int is_different(VNode test,Graph G )i=text.clofor(j=0;jG.vexnum;j+)if(G.vexlistj.clo=i)return FALSE; return TRUE;void Traverse(int current=1,Graph &G,int store) 主要函数其流程图如下：主要思想是遍历和递归 Traverse(int current=1,Graph &G,int store)sum=G,vexnum是否currentsum是 i=1否i=4G.vexlistcurrent.clo=i; storecurrent=i;终止函数G.vexlistcurrent.clo与它的邻接顶点的颜色域相同是否Traverse (current+1, G, store)i+返回终止void Destroy(Graph &G)for(i=0;iarcnext;free(p);p=q;函数调用关系图：mainCreateGraphprintDestroyTraverseis_different四、调试分析1.本程序的主要功能是自己建立一个图，然后对图进行着色，支持的数据类型是整形，用不同的数字表示不同的颜色。2.程序中完成着色的函数利用递归，从第一个结点开始判断，顺序判断如果有n个顶点，应该能够进入n层递归。因为利用的是邻接表，所以比邻接矩阵消耗的数据空间小得多，如果有n个顶点，邻接数组占用O(n)的空间。3.在写着色函数的时候，刚开始不知道怎么控制递归的出口，即如何判断最后一个元素已经被着上色了。后来查阅资料后，如果有n个顶点，则第n+1层递归就应该停止，所以可以用当前递归层数与图的结点个数比较来控制出口。程序中由于设计动态分配，最后销毁空间的时候把销毁顺序弄错，导致程序总是崩溃，细细调试一阵后终于完成了任务。4.程序中的关系结构应为是手动输入，所以对于大的图输入起来比较麻烦，应该可以把文件读取部分加入到程序里，减少输入程序的工作量。5.地图着色中只是着色方案中的一种，我们可以试着将所有的着色方案都能够列出来，这样在真正的工程应用中可以提供更多的可选方案，程序也能更加灵活。五、测试结果测试数据1：对下图进行着色。467581239红 蓝 红蓝 红 蓝红 蓝 红着色结果测试数据二：对下图着色1234红 蓝蓝 红着色结果六、用户手册1.进入操作界面2.按照屏幕的指令进行建图输入边数和顶点数3.输入边数后系统会显示输入的边数和顶点数,输入边的关系4.输入完毕后系统会以邻接表的方式显示出整个表，供用户核对5.最后系统自动给出着色的方案6.最后询问用户是否需要对其他图进行着色操作七、体会与自我评价 编写地图着色以后的体会 本次题目是我选择的图操作的一个问题，设计到图的邻接顶点的访问和图的遍历。图的存储结构我选择的是邻接表的形式，在遍历图时是从第一个顶点开始，一次在定点数组中完成所有顶点的遍历，保证了全部的顶点都是可以访问到的。因为要对地图着色，所以着色是一个动态的过程，可以在遍历的过程中完成对地图的着色，每次访问一个结点，先赋值第一种颜色，如果和它的的邻接点的颜色不重复，则对下个顶点开始着色，否则本顶点的颜色转换到下一种，直到能够完成赋值。程序编写本身并不难，思路很清晰，就是赋值和比较之间的来回循环。 写程序的时候查阅了着色问题，直到了这个问题是用计算机进行证明的，地图到目前为止还没有出现这个证明的反例；而且也明白了计算机在现代数学中的重要作用，因为如果没办法归纳