多叉路口交通灯 数据结构

1多叉路口交通灯管理一、需求分析1.设计背景通常，在十字路口只需设红、绿两色的交通灯便可以保证正常的交通秩序，而在多叉路口需设计几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流量。该程序就是在多叉路口情况下，判断各个路口交通灯颜色，以便人们进行管理。对于用户任意输入的多叉路口（实际输入所有的可以通行的方向及数量，从而构建出图），输出需要的交通灯的数量。2.任务概述假设有一个如图1所示的五叉路口，其中C和E为单行道。在路口有13条可行的道路，其中有的可以同时通行，如A—B和E—C，而有的不能同事通行，如E—B，A—D，那么，如何设置交通灯呢？每个圆圈表示五叉路口上的一条通路，两个圆圈之间的连线表示这两个圆圈表示的两条道路不能同事通行。设置交通灯的问题等价为对图的顶点进行染色问题。要求对图上的每个顶点染一种颜色，并且要求有限相连的两个顶点不能具有相同颜色，而且总的颜色种类尽可能少。所以，我准备把每个顶点用字母“a、b、c、……”表示，而染色的颜色用数字表示。2可以同时通行的道路交通灯的颜色相同，不能同时通行的颜色不同。顶点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.数据结构首先，是考虑数据类型。在多叉路口中，每条通路是最基本的组成部分，对于交通灯管理已经不可能在细分了，所以选定通路作为数据的基本类型，并在程序中定义图的数据结构,其中包含存放图的顶点和图的边，以及顶点数和边数。用邻接矩阵表示图的结构。其形式描述如下：intcolor[30]={0};//来存储对应块的对应颜色typedefcharvextype;typedefintadjtype;typedefstruct//定义图{vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MAXedg][MAXedg];//图的邻接矩阵intvnum,arcnum;//图的顶点数和边数}Graph;在选择数据结构方面，直接用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用顺序表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简单容易实现，效率高，而且在内存中的数据可以直接读入到文件中，文件中的数据也可以直接读入内存，不需要进行转换。所以在衡量的各个方面之后，我决定用数组来处理数据间的联系。2.算法流程图2.1建立邻接矩阵的流程图32.2交通灯颜色模块的流程图43．函数之间的调用关系图构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，输入图函数、染色函数、输出函数等。3.1输入图函数voidCreate(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染色函数voidtrycolor(ints,GraphG)给各个顶点染色，然后输出染色结果，并调用判断颜色是否满足要求函数。从第一个顶点开始染色，而后判断和其相邻的顶点的颜色是够与第一个顶点相同。部分代码如下：if(sG.vnum)5{output(G);exit(1);}else{for(i=1;i=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}3.3定位函数intLocateVex(GraphG,charu)在已经输入的图中，找到与要记录的顶点在图中的位置，返回值是在数组中的位置。部分代码如下：for(i=1;i=G.vnum;i++){if(u==G.vexs[i])returni;}if(i==G.vnum){printf(Erroru!\n);exit(1);}return0;3.4主程序intmain(){inti,j;GraphG;Create(G);printf(多叉路口的各顶点：\n);for(i=1;i=G.vnum;i++)printf(%c,G.vexs[i]);printf(\n);printf(相应的亮灯方案:\n);trycolor(1,G);return0;}三、调试分析1经验体会通过这次课设，体会很深刻，将一直以来学到的东西都运用到实际上来，学以致用，对6所学知识有了更深刻的理解，同时还发现了许多平时在书本上没有遇见过的问题，促进了自己对知识的渴望，遇见了问题，就希望能够通过查找课外书来解决它们。刚接触题目的时候，自己就有了一定的想法，觉得这个程序做起来是问题不大的，但到了自己真正开始编程的时候却发现远远没有想象中那么简单，很多细节的问题没有预想到，很多关系的处理想得过于简单，以至于实施起来遇到了很大的困难，花了大量的时间。2算法改进关于这个程序的缺点方面，由于自己花的时间不是很多，再加上知识有限，并不会运用可视化编程工具来辅助自己编程，所以弄得这个程序的不足之处还是挺多的，首当其冲的是程序界面，一开始的时候是注重功能的实现，并没有怎么理会运用界面，而到了后期，当辛辛苦苦搞好了功能之后，界面就没有动力再去弄了，所以程序的界面很粗糙。四、用户手册在VC++环境下，运行该程序。根据提示输入多叉路口的顶点数和边数，例如五叉路口的情况，顶点13个，20条边，就输入1320然后回车，根据提示输入顶点abcdefghijklm回车，根据提示输入两个顶点和权值aj1ae1…回车，程序结果就出现在屏幕上了“亮灯方案：1111223312441”五、测试结果正确输入时结果如下图第一组：7第二组：第三组：第四组：错误输入后，如果不按照要求输入，测试结果：系统没能作出良好提示，突然退出8六、附录#includestdio.h#includestdlib.h#defineMAXedg30#defineMAX0#defineN4//亮灯的颜色数intcolor[30]={0};//来存储对应块的对应颜色typedefcharvextype;typedefintadjtype;typedefstruct//定义图{vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MAXedg][MAXedg];//图的邻接矩阵intvnum,arcnum;//图的顶点数和边数}Graph;intLocateVex(GraphG,charu){inti;for(i=1;i=G.vnum;i++){if(u==G.vexs[i])returni;}if(i==G.vnum){printf(Erroru!\n);exit(1);}return0;}voidCreate(Graph&G)//输入图{inti,j,k,w;vextypev1,v2;printf(输入多叉路口的顶点数和边数:\n);scanf(%d%d,&G.vnum,&G.arcnum);getchar();printf(输入多叉路口的各顶点：\n);for(i=1;i=G.vnum;i++){9scanf(%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;}}intcolorsame(ints,GraphG)//判断这个颜色能不能满足要求{inti,flag=0;for(i=1;i=s-1;i++)//分别于前面已经着色的几块比较if(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}returnflag;}voidoutput(GraphG){inti;for(i=1;i=G.vnum;i++)printf(%d,color[i]);printf(\n);}voidtrycolor(ints,GraphG)//s为开始图色的顶点，从1开始{inti;if(sG.vnum){output(G);exit(1);}else10{for(i=1;i=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}}intmain(){inti,j;GraphG;Create(G);printf(多叉路口的各顶点：\n);for(i=1;i=G.vnum;i++)printf(%c,G.vexs[i]);printf(\n);printf(相应的亮灯方案:\n);trycolor(1,G);return0;}11家庭成员的管理问题一、需求分析1.设计背景例如有这样的一对老夫妻（A、B），他们生有n男m女，其中，某个儿子（D）娶妻（C）生有x男y女，某个女儿（E）嫁夫（F）生有i男j女，其余的子女有可能婚嫁，也有可能单身，已婚的可能生有孩子若干，其孩子相继婚嫁……数据对象是以上所有的家庭成员，要求建立他们之间的夫妻、子女等关系并方便查询。2.任务概述家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理程序，实现对一个家族所有的资料进行收集整理。构建数据模型，按时间关系建立他们之间的夫妻，子女等关系。按姓名查询某个家庭成员及其配偶和孩子二、详细设计在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构，数据类型等等，只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。1.数据结构首先是考虑数据类型。在家谱中，家族成员是最基本的组成部分，对于家族管理中，已经不能再进行细分了，所以选定家族成员作为数据的基本类型。定义每个成员为一个结点，结点属性包括成员的姓名和左右子树的指针，为了查找方便，我设计父亲结点的左孩子根结点是该父亲结点的配偶，而父亲结点的右孩子根结点是其父亲结点的孩子。性别的辨别是通过用户输入“m”或“f”来辨别，并没有定义其属性。structtreenode{charname[10];structtreenode*left,*right;};2.算法流程图122.1.建树的流程图2.2查找父亲节点流程图132.3查找孩子结点流程图2.4插入妻子和孩子函数的流程图143．函数之间的调用关系图构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，输入图函数、染色函数、输出函数等。重要函数的大体思想看下面：3.1建树函数structtreenode*creatree()由屏幕输入结点姓名和其配偶，再添加孩子结点，逐步建立树。while(contin){if(frist==1){btree=newtreenode;printf(姓名:);scanf(%s,btr