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

《数据结构课程设计报告-地图着色》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告题目：地图着色一、需求分析1.问题描述现在有一张地图，为了便于区别各个地图上的版块，地图上相邻的颜色块应该是不同颜色。现在的任务是给定一张地图，要对其进行着色，相邻版块之间颜色不能相同，输出最后的着色方案。2.基本功能：功能一：为了程序的灵活性，可以让程序自由建立图。功能二：对建好的图进行着色。3.输入输出输入一张图的信息，正数输入边数和顶点数，输入边的关系，输入边的关系就是输入一条边的两个顶点。颜色只用四种，所以每个结点的颜色域值只能取1到4输出时根据每个顶点不同的标号输出着色的结果。二、概要设

2、计1.设计思路给定四种颜色，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，知道所有的顶点都处理完后结束着色。2.数据结构设计：因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。抽象数据类型图的定

3、义如下：数据对象V:V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={(v,w)

4、v,w∈V,(v,w)表示v和w之间存在的路径}基本操作P:CreateGraph(&G)操作结果：创建一张需要操作的无向图GDestroy(Graph&G)初始条件：无向图G存在操作结果：销毁图GLocate(&G,i)初始条件：无向图G存在操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息Traverse(current,&G,store[])初始条件：无向图G存在，在图中有第cu

5、rrent个顶点操作结果：对图开始遍历，并且用他们的序号在store数组的相应位置上存储所染上的颜色print(&G)初始条件：无向图G存在操纵结果：打印图G中每个顶点的颜色着色情况is_different(test,G)初始条件：无向图G存在，test为图中的一个顶点操作结果：如果图G中test的邻接顶点颜色都不与test相同，则返回真，否则返回假3.软件结构设计：本程序分为两个模块：1.主程序模块intmain(){建立一张图G建立存储最终着色结果的数组对地图进行着色打印地图着色的情况销毁图退出}无向操作图模块-

6、---------à无向图中结点的赋值，遍历主程序模块无向图操作模块三、详细设计#defineMAX_NUM30structArcNode{intdata;ArcNode*arcnext;};typedefstruct{intvexdata;Colourclo;ArcNode*firstnext;}VNode,Adjlist[MAX_NUM];typedefstruct{Adjlistvexlist;intarcnum,vexnum;}Graph;图的基本操作：voidCreateGraph(Graph&MyGrap

7、h)//创建一个要求的无向图intis_different(VNodetest,GraphG)//如果结点test中的颜色和图G中和他相邻的结点颜色不同，返回TRUE，否则返回FALSEvoidTraverse(intcurrent,Graph&G,intstore[])//对图G进行遍历，并且将分配的颜色按他在邻接表中的位置赋值到store中相应的位置voidDestroy(Graph&G)//销毁已经存在的无向图GintLocate(GraphMyGraph,intsignal)寻找无向图中顶点为i的结点，返回其

8、位置以上重要函数的的伪码算法intis_different(VNodetest,GraphG){i=text.clofor(j=0;j

9、是i=1否i<=4G.vexlist[current].clo=i;store[current]=i;终止函数G.vexlist[current].clo与它的邻接顶点的颜色域相同是否Traverse(current+1,G,store)i++返回终止voidDestroy(Graph&G){for(i=0;i