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

多叉路口交通灯管理一、 需求分析1.设计背景通常，在十字路口只需设红、绿两色的交通灯便可以保证正常的交通秩序，而在多叉路口需设计几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流量。该程序就是在多叉路口情况下，判断各个路口交通灯颜色，以便人们进行管理。对于用户任意输入的多叉路口（实际输入所有的可以通行的方向及数量，从而构建出图），输出需要的交通灯的数量。2.任务概述假设有一个如图1所示的五叉路口，其中C和E为单行道。在路口有13条可行的道路，其中有的可以同时通行，如AB和EC，而有的不能同事通行，如EB，AD，那么，如何设置交通灯呢？每个圆圈表示五叉路口上的一条通路，两个圆圈之间的连线表示这两个圆圈表示的两条道路不能同事通行。设置交通灯的问题等价为对图的顶点进行染色问题。要求对图上的每个顶点染一种颜色，并且要求有限相连的两个顶点不能具有相同颜色，而且总的颜色种类尽可能少。所以，我准备把每个顶点用字母“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 color30=0;/来存储对应块的对应颜色typedef char vextype;typedef int adjtype;typedef struct /定义图 vextype vexsMAXedg; /存放边的矩阵 adjtype arcsMAXedgMAXedg; /图的邻接矩阵 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.vexsi); getchar(); printf(输入边的两个顶点和权值:n); for(k=0;kG.vnum) output(G); exit(1); else for(i=1;i=N;i+)/对每一种色彩逐个测试 colors=i; if(colorsame(s,G)=0) trycolor(s+1,G);/进行下一块的着色 3.3 定位函数 int LocateVex(Graph G,char u)在已经输入的图中，找到与要记录的顶点在图中的位置，返回值是在数组中的位置。部分代码如下：for(i=1;i=G.vnum;i+) if(u=G.vexsi) return i; if(i=G.vnum) printf(Error u!n); exit(1); return 0;3.4 主程序 int main() int i,j; Graph G; Create(G); printf(多叉路口的各顶点：n); for(i=1;i=G.vnum;i+) printf(%c ,G.vexsi); printf(n); printf(相应的亮灯方案:n); trycolor(1,G); return 0;三、调试分析1 经验体会通过这次课设，体会很深刻，将一直以来学到的东西都运用到实际上来，学以致用，对所学知识有了更深刻的理解，同时还发现了许多平时在书本上没有遇见过的问题，促进了自己对知识的渴望，遇见了问题，就希望能够通过查找课外书来解决它们。刚接触题目的时候，自己就有了一定的想法，觉得这个程序做起来是问题不大的，但到了自己真正开始编程的时候却发现远远没有想象中那么简单，很多细节的问题没有预想到，很多关系的处理想得过于简单，以至于实施起来遇到了很大的困难，花了大量的时间。2 算法改进关于这个程序的缺点方面，由于自己花的时间不是很多，再加上知识有限，并不会运用可视化编程工具来辅助自己编程，所以弄得这个程序的不足之处还是挺多的，首当其冲的是程序界面，一开始的时候是注重功能的实现，并没有怎么理会运用界面，而到了后期，当辛辛苦苦搞好了功能之后，界面就没有动力再去弄了，所以程序的界面很粗糙。四、 用户手册在VC+环境下，运行该程序。根据提示输入多叉路口的顶点数和边数，例如五叉路口的情况，顶点13个，20条边，就输入13 20然后回车，根据提示输入顶点a b c d e f g h i j k l m回车，根据提示输入两个顶点和权值a j 1 a e 1回车，程序结果就出现在屏幕上了“亮灯方案：1 1 1 1 2 2 3 3 1 2 4 4 1”五、 测试结果正确输入时结果如下图第一组：第二组：第三组：第四组：错误输入后，如果不按照要求输入， 测试结果：系统没能作出良好提示，突然退出 六、 附录#include #include #define MAXedg 30#define MAX 0#define N 4 /亮灯的颜色数int color30=0;/来存储对应块的对应颜色typedef char vextype;typedef int adjtype;typedef struct /定义图 vextype vexsMAXedg; /存放边的矩阵 adjtype arcsMAXedgMAXedg; /图的邻接矩阵 int vnum,arcnum; /图的顶点数和边数Graph;int LocateVex(Graph G,char u) int i; for(i=1;i=G.vnum;i+) if(u=G.vexsi) return i; if(i=G.vnum) printf(Error u!n); exit(1); return 0;void Create(Graph &G) /输入图 int i,j,k,w; vextype v1,v2; printf(输入多叉路口的顶点数和边数:n); scanf(%d%d,&G.vnum,&G.arcnum); getchar(); printf(输入多叉路口的各顶点：n); for(i=1;i=G.vnum;i+) scanf(%c,&G.vexsi); 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.arcsij=w; G.arcsji=w; int colorsame(int s,Graph G)/判断这个颜色能不能满足要求 int i,flag=0; for(i=1;i=s-1;i+)/分别于前面已经着色的几块比较 if(G.arcsis=1&colori=colors) flag=1;break; return flag;void output(Graph G) int i; for(i=1;iG.vnum) output(G); exit(1); else for(i=1;i=N;i+)/对每一种色彩逐个测试 colors=i; if(colorsame(s,G)=0) trycolor(s+1,G);/进行下一块的着色 int main() int i,j; Graph G; Create(G); printf(多叉路口的各顶点：n); for(i=1;iname); btree-right=NULL; s=new treenode; printf(配偶:);scanf(%s,s-name); s-right=s-left=NULL; btree-left=s; frist=0; elseprintf(父亲结点:);scanf(%s,xm); if(strcmp(xm,#)=0)contin=0; elsep=findfather(btree,xm); if(p!=NULL)p=p-left; if(p=NULL) printf(不能有孩子,因为没有配偶n); else while(p-right!=NULL)p=p-right; s=new treenode; s-right=NULL; p-right=s; printf(孩子:);scanf(%s,s-name); printf(配偶:);scanf(%s,xm); if(strcmp(xm,#)!=0) t=new treenode; strcpy(t-name,xm); t-left=t-right=NULL; s-left=t; else s-left=NULL; else printf(不存在这样的父亲结点!n); 3.2 插入函数 void insert(struct treenode*p)插入函数是插入配偶或插入孩子的函数，先从父亲结点进行查找，如果不存在则结束，倘若存在则遍历其左子树，为空则插入其配偶结点，不空则在其配偶结点右子树插入孩子结点。部分代码如下：if(!t-left)t-left=q;q-right=NULL;q-left=NULL;elset=t-left;while(t-right)t=t-right;t-right=q;q-right=NULL;q-left=NULL;3.3 查找父亲结点函数 struct treenode *findfather(struct treenode *p,char xm)对二叉树进行查找，先进行根结点查找，而后左子树再右子树查找。部分代码如下：if(p=NULL)return(NULL); elseif(strcmp(p-name,xm)=0)return(p); elsebt=findfather(p-left,xm); if(bt!=NULL)return(bt); else return(findfather(p-right,xm); 3.4 查找孩子结点函数 void findson(struct treenode *bt) 查找孩子结点，是先findfather（）找出这样的父亲结点p是否存在，若存在则p=p-left,再查找p是否为空，即是够有配偶，若配偶存在再查找配偶结点的右子树，返回孩子的信息。p=findfather(bt,xm); if(p=NULL)printf(不存在这样的父亲结点n); else p=p-left;/p=p-right;if(!p)|(!(p-right)printf(配偶:);printf(%sn,p-name);printf(没有孩子n);else printf(配偶:);printf(%sn,p-name);printf(有以下孩子:n); p=p-right;while(p!=NULL) printf(%sn,p-name);p=p-right; 3.5 主函数 void main()void main() struct treenode *bt,*p;int i,j,flag=1;char ch10;bt=creatree();while(flag)printf(1,查找2,加孩子3,结婚0,结束n); scanf(%d,&j);switch(j)case 1:printf(查找n); findson(bt); break; case 2:printf(n请输入要加孩子的人的姓名n);scanf(%s,ch); p=findfather(bt,ch); if(!(p-left) printf(该人未婚);else insert(&p); break; case 3:printf(n请输入要结婚的人的姓名n); scanf(%s,ch);p=findfather(bt,ch);if(p-left) printf(该人已婚);else insert(&p);break;case 0: flag=0;break;三、 调试分析1. 经验总结好的数据结构有时比好的算法更能给程序带来便捷2. 时空分析时间效率：O(n)；空间效率:O(n+e)。3. 算法改进分析家庭成员的以什么数据结构来存储对本题来说是非常重要。除了我给出来的这种程序结构外，还可以尝试建立二叉树，但是鉴于二叉树不能不易向上回溯查找父母结点。4经验和体会先思而后行可以减少无谓的时间，心细与不孜可以减少无谓的错误。四、 用户手册在VC+环境下，运行该程序。系统提供了良好的提示，根据提示输入父亲、配偶。用户可以先自己在草稿纸上建立家庭关系，然后依照提示严格输入。具体操作可以参考测试结果中用例，这里不再赘述。 五、 测试结果第一组：第二组：第三组：第四组，查找无父亲结点时，仍可继续输入：六、 附录#include#include #include struct treenode char name10;struct treenode *left,*right; ;struct treenode *findfather(struct treenode *p,char xm) struct treenode*bt; if(p=NULL)return(NULL); elseif(strcmp(p-name,xm)=0)return(p); elsebt=findfather(p-left,xm); if(bt!=NULL)return(bt); else return(findfather(p-right,xm); struct treenode *creatree() int contin=1;int frist=1; char xm10; struct treenode *btree,*s,*t,*p; printf(输入m是儿子,f是女儿:n);printf(建立一个家谱二叉树(以#结尾):n); while(contin) if(frist=1)btree=new treenode; printf(姓名:);scanf(%s,btree-name); btree-right=NULL; s=new treenode; printf(配偶:);scanf(%s,s-name); s-right=s-left=NULL; btree-left=s; frist=0; elseprintf(父亲结点:);scanf(%s,xm); if(strcmp(xm,#)=0)contin=0; elsep=findfather(btree,xm); if(p!=NULL)p=p-left; if(p=NULL) printf(不能有孩子,因为没有配偶n); else while(p-right!=NULL)p=p-right; s=new treenode; s-right=NULL; p-right=s; printf(孩子:);scanf(%s,s-name); printf(配偶:);scanf(%s,xm); if(strcmp(xm,#)!=0) t=new treenode; strcpy(t-name,xm); t-left=t-right=NULL; s-left=t; else s-left=NULL; else printf(不存在这样的父亲结点!n); return(btree); void findson(struct treenode *bt) char xm10; struct treenode *p; printf(查找指定父亲的所有孩子n); printf(父亲结点：);scanf(%s,xm); p=findfather(bt,xm); if(p=NULL)printf(不存在这样的父亲结点n); else p=p-left;/p=p-right;if(!p)|(!(p-right)printf(配偶:);printf(%sn,p-name