多叉路口交通灯数据结构.docVIP

多叉路口交通灯管理 需求分析 1.设计背景 通常，在十字路口只需设红、绿两色的交通灯便可以保证正常的交通秩序，而在多叉路口需设计几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流量。该程序就是在多叉路口情况下，判断各个路口交通灯颜色，以便人们进行管理。对于用户任意输入的多叉路口（实际输入所有的可以通行的方向及数量，从而构建出图），输出需要的交通灯的数量。 2.任务概述 假设有一个如图1所示的五叉路口，其中C和E为单行道。在路口有13条可行的道路，其中有的可以同时通行，如A—B和E—C，而有的不能同事通行，如E—B，A—D，那么，如何设置交通灯呢？ 每个圆圈表示五叉路口上的一条通路，两个圆圈之间的连线表示这两个圆圈表示的两条道路不能同事通行。设置交通灯的问题等价为对图的顶点进行染色问题。要求对图上的每个顶点染一种颜色，并且要求有限相连的两个顶点不能具有相同颜色，而且总的颜色种类尽可能少。所以，我准备把每个顶点用字母“a、b、c、……”表示，而染色的颜色用数字表示。可以同时通行的道路交通灯的颜色相同，不能同时通行的颜色不同。顶点AB为a，AC为b，AD为c，BA为d，BC为e，BD为f，DA为g，DB为h，DC为i，EA为j，EB为k，EC为l，ED为m，顶点之间的边全都用“1”表示。 二、 详细设计 在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构，数据类型等等，只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。 1.数据结构 首先，是考虑数据类型。在多叉路口中，每条通路是最基本的组成部分，对于交通灯管理已经不可能在细分了，所以选定通路作为数据的基本类型，并在程序中定义图的数据结构,其中包含存放图的顶点和图的边，以及顶点数和边数。用邻接矩阵表示图的结构。其形式描述如下： int color[30]={0};//来存储对应块的对应颜色 typedef char vextype; typedef int adjtype; typedef struct //定义图 { vextype vexs[MAXedg]; //存放边的矩阵 adjtype arcs[MAXedg][MAXedg]; //图的邻接矩阵 int vnum,arcnum; //图的顶点数和边数 }Graph; 在选择数据结构方面，直接用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用顺序表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简单容易实现，效率高，而且在内存中的数据可以直接读入到文件中，文件中的数据也可以直接读入内存，不需要进行转换。所以在衡量的各个方面之后，我决定用数组来处理数据间的联系。 2.算法流程图 2.1建立邻接矩阵的流程图 2.2 交通灯颜色模块的流程图 3．函数之间的调用关系图 构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，输入图函数、染色函数、输出函数等。 3.1 输入图函数 void Create(Graph G) 考虑到输入的问题，就是在输入界面以何种形式输入，输入顶点和边数以及边的权值在计算机内部建立数组存储。部分代码如下： printf(输入多叉路口的顶点数和边数:\n); scanf(%d%d,G.vnum,G.arcnum); getchar(); printf(输入多叉路口的各顶点：\n); for(i=1;i=G.vnum;i++) { scanf(%c,G.vexs[i]); getchar(); } printf(输入边的两个顶点和权值:\n); for(k=0;kG.arcnum;k++) { scanf(%c, v1);getchar(); scanf(%c, v2);getchar(); scanf(%d, w); getchar(); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=w; G.arcs[j][i]=w; } 3.2 染色函数 void trycolor(int s,Graph G) 给各个顶点染色，然后输出染色结果，并调用判断颜色是否满足要求函数。从第一个顶点开始染色，而后判断和其相邻的顶点的颜色是够与第一个顶点相同。部分代码如下： if(sG.vnum) { output(G); exit(1); } else { for(i=1;i=N;i++)//对每一种色彩逐个测试 { color[s]=i;