数据结构课程设计报告--交通灯问题.doc

数据结构课程设计课题28：交通灯问题多叉路口交通灯的管理问题。通常，在十字交叉路口只需设红、绿两色的交通灯便可保持正常的交通秩 序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不 碰撞，又能达到车辆的最大流通。假设有一个如图(a)所示的五叉路口，其中c和e为单行道。在路口有13条可行的通路，其中有的 可以同时通行，如ab和ec，而有的不能同时通行，如eb和ad。那么，在路口应如何设置交通灯进行车辆的管理呢？求解步骤：1.模型表示：（1）由于题目要求是对多叉路口交通灯的管理。一般，在十字交叉路口我们只需设红、绿两色的交通灯便可保持正常的交通秩序，但是在多叉路口需设多种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。题目给出如上图(a)所示的五叉路口，其中c和e为单行道。在路口有13条可行的通路，其中有的可以同时通行，如ab 和ec，而有的不能同时通行，如eb 和ad。要求出在路口应如何设置交通灯进行车辆的管理。（2）在图中，用箭头表示一条通路，如下图，b.a.e.d路口的红绿点表示交通灯，按交通规则，红灯停，绿灯行。某交通路口的绿灯亮了，则此路口的车可开出，其他路口的车可开进，求解是假设c路口无交通灯，而且b处灯为绿灯，其它为红灯，按此模型可以求解后可以让各个路口的车辆正常通行。2.算法设计：设计本题算法的构思如下：为求出符合条件的交通灯数，要在求解过程中进行试探，按照图形依据交通规则让交通灯在十秒内改变，所以程序编写时箭头试探可行路径，若试探成功，会在试探完毕后图形将显示此时的所有可行路径，即此时的箭头指向。设置如下：（1）jtd.cpp定义应用程序的入口点。在jtd.cpp中定义全局变量:hinstance hin表示当前实例；tchar sztitlemax_loadstring表示标题栏文本；tchar szwindowclassmax_loadstring表示主窗口类名。函数: myregisterclass()目的是注册窗口类。函数: initinstance(hinstance, int)目的是保存实例句柄并创建主窗口，在此函数中，我们在全局变量中保存实例句柄并创建和显示主程序窗口。函数: wndproc(hwnd, uint, wparam, lparam)目的是处理主窗口的消息wm_command 处理应用程序菜单wm_paint- 绘制主窗口wm_destroy- 发送退出消息并返回int_ptr callback about(hwnd hdlg, uint message, wparam wparam, lparam lparam) “关于”框的消息处理函数。（2）op.cpp定义应用程序。程序定义可以存储五个路口一维数组g_lk5；函数initdata(hwnd hwnd)对数据进行初始化；在应用程序中作图时调用jtd.cpp中的函数实现消息的响应，则会在窗口的客户区画出所求图形，在画图时的探索过程中即已实现算法的描述，求解出题目所要实现的交通灯管理，需四种颜色的交通灯才能使车辆正常通行。3.程序实现：为上机实现本题，还需要做一些工作：1.添加功能：由算法可知，需要添加一些功能，如输入数据建图、输出路径，显示求解状态等。2.结构及类型说明：若采用数据结构实验工具，则可借助于实验工具中的存储结构，因此可省掉诸如类型说明、建图、显示图等许多麻烦。于是我采用win32应用程序中的典型的“helloword”程序，它可以提供并自动生成一些程序代码，在其中实现图形的显示更容易。3.输入图结构：为方便地调试算法，需要能方便地建图。若采用逐个输入元素的方式来建图，会比较麻烦，这对调试算法来说也是不方便的。为此，在“jtd.cpp”中利用一些函数实现消息响应，在程序实现时，调用这些函数即可实现图形中箭头的表示。4.显示结构：合理地显示结构是调试算法所必需的。在此，采用工具系统中的图结构、数组等有关功能，以方便地显示结构。5.显示输出结果：输出结果也必须要以可接受的形式显示出来。此处为形象的表达出图形以便观察，当一个交通灯亮时，用箭头表示此时可以通行的路口的车。完整程序如下：#pragma once#include resource.hextern void drawlk(hdc hdc,hwnd hwnd);extern void drawsec(hdc hdc);extern void initdata(hwnd hwnd);/ jtd.cpp : 定义应用程序的入口点。/#include stdafx.h#include jtd.h#define max_loadstring 100/ 全局变量:hinstance hinst;/ 当前实例tchar sztitlemax_loadstring;/ 标题栏文本tchar szwindowclassmax_loadstring;/ 主窗口类名/ 此代码模块中包含的函数的前向声明:atommyregisterclass(hinstance hinstance);boolinitinstance(hinstance, int);lresult callbackwndproc(hwnd, uint, wparam, lparam);int_ptr callbackabout(hwnd, uint, wparam, lparam);int apientry _twinmain(hinstance hinstance, hinstance hprevinstance, lptstr lpcmdline, int ncmdshow)unreferenced_parameter(hprevinstance);unreferenced_parameter(lpcmdline); / todo: 在此放置代码。msg msg;haccel hacceltable;/ 初始化全局字符串loadstring(hinstance, ids_app_title, sztitle, max_loadstring);loadstring(hinstance, idc_jtd, szwindowclass, max_loadstring);myregisterclass(hinstance);/ 执行应用程序初始化:if (!initinstance (hinstance, ncmdshow)return false;hacceltable = loadaccelerators(hinstance, makeintresource(idc_jtd);/ 主消息循环:while (getmessage(&msg, null, 0, 0)if (!translateaccelerator(msg.hwnd, hacceltable, &msg)translatemessage(&msg);dispatchmessage(&msg);return (int) msg.wparam;/ 函数: myregisterclass()/ 目的: 注册窗口类。/ 注释:/ 仅当希望/ 此代码与添加到 windows 95 中的“registerclassex”/ 函数之前的 win32 系统兼容时，才需要此函数及其用法。调用此函数十分重要，/ 这样应用程序就可以获得关联的/ “格式正确的”小图标。/atom myregisterclass(hinstance hinstance)wndclassex wcex;wcex.cbsize = sizeof(wndclassex);wcex.style= cs_hredraw | cs_vredraw;wcex.lpfnwndproc= wndproc;wcex.cbclsextra= 0;wcex.cbwndextra= 0;wcex.hinstance= hinstance;wcex.hicon= loadicon(hinstance, makeintresource(idi_jtd);wcex.hcursor= loadcursor(null, idc_arrow);wcex.hbrbackground= (hbrush)(color_window+1);wcex.lpszmenuname= makeintresource(idc_jtd);wcex.lpszclassname= szwindowclass;wcex.hiconsm= loadicon(wcex.hinstance, makeintresource(idi_small);return registerclassex(&wcex);/ 函数: initinstance(hinstance, int)/ 目的: 保存实例句柄并创建主窗口/ 注释:/ 在此函数中，我们在全局变量中保存实例句柄并/ 创建和显示主程序窗口。/extern int nst;extern int nsec;bool initinstance(hinstance hinstance, int ncmdshow) hwnd hwnd; hinst = hinstance; / 将实例句柄存储在全局变量中 hwnd = createwindow(szwindowclass, sztitle, ws_overlappedwindow, cw_usedefault, 0, cw_usedefault, 0, null, null, hinstance, null); if (!hwnd) return false; showwindow(hwnd, ncmdshow); updatewindow(hwnd); return true;/ 函数: wndproc(hwnd, uint, wparam, lparam)/ 目的: 处理主窗口的消息。/ wm_command- 处理应用程序菜单/ wm_paint- 绘制主窗口/ wm_destroy- 发送退出消息并返回/lresult callback wndproc(hwnd hwnd, uint message, wparam wparam, lparam lparam)int wmid, wmevent;paintstruct ps;hdc hdc;switch (message)case wm_command:wmid = loword(wparam);wmevent = hiword(wparam);/ 分析菜单选择:switch (wmid)case idm_about:dialogbox(hinst, makeintresource(idd_aboutbox), hwnd, about);break;case idm_exit:destroywindow(hwnd);break;default:return defwindowproc(hwnd, message, wparam, lparam);break;case wm_create:initdata(hwnd);settimer(hwnd,0,1000,null);break;case wm_paint:hdc = beginpaint(hwnd, &ps);/ todo: 在此添加任意绘图代码.drawlk(hdc,hwnd);endpaint(hwnd, &ps);break;case wm_timer: nsec-; drawsec(getdc(hwnd); if(nsec4)nst=1;invalidaterect(hwnd,null,true); break;case wm_destroy:postquitmessage(0);break;default:return defwindowproc(hwnd, message, wparam, lparam);return 0;/ “关于”框的消息处理程序。int_ptr callback about(hwnd hdlg, uint message, wparam wparam, lparam lparam)unreferenced_parameter(lparam);switch (message)case wm_initdialog:return (int_ptr)true;case wm_command:if (loword(wparam) = idok | loword(wparam) = idcancel)enddialog(hdlg, loword(wparam);return (int_ptr)true;break;return (int_ptr)false;struct lkchar name10;/路口名point p;point p1;point p2;point p3;point p4; char b;/b=0双向，1单向char c;/c=0只出,c=1只入point pt4;#include stdafx.h#include stdio.h#include op.h#include #include lk g_lk5;point org;double r=0;double w;int nsec=10;int nst=1;void initdata(hwnd hwnd)rect rect;int kr;point tmp;double pi = 3.1415926535;getclientrect(hwnd,&rect);if(rect.right-rect.left)(rect.bottom-rect.top)kr=rect.bottom-rect.top;else kr=rect.right-rect.left;r=(kr-40)/2;org.x=(rect.right-rect.left)/2-r;org.y=(rect.bottom-rect.top)/2-r;strcpy(g_lk0.name,a);w=r/5;g_lk0.b=0;g_lk0.c=0;g_lk0.p.x=org.x+r;g_lk0.p.y=org.y;g_lk0.p1.x=g_lk0.p.x-w;g_lk0.p1.y=g_lk0.p.y;g_lk0.p2.x=g_lk0.p.x+w;g_lk0.p2.y=g_lk0.p.y;g_lk0.p3.x=g_lk0.p1.x;g_lk0.p3.y=g_lk0.p1.y+2*w;g_lk0.p4.x=g_lk0.p2.x;g_lk0.p4.y=g_lk0.p2.y+2*w;g_lk1.b=0;g_lk1.c=0;g_lk1.p.x=org.x+r*(1-sin(pi*2/5);g_lk1.p.y=org.y+r*(1-cos(pi*2/5);g_lk1.p1.x=g_lk1.p.x+w*cos(pi*2/5);g_lk1.p1.y=g_lk1.p.y-w*sin(pi*2/5);g_lk1.p2.x=g_lk1.p.x-w*cos(pi*2/5);g_lk1.p2.y=g_lk1.p.y+w*sin(pi*2/5);g_lk1.p3.x=g_lk1.p.x+2*w*sin(pi*2/5)+w*cos(pi*2/5);g_lk1.p3.y=g_lk1.p.y+2*w*cos(pi*2/5)-w*sin(pi*2/5);g_lk1.p4.x=g_lk1.p.x+2*w*sin(pi*2/5)-w*cos(pi*2/5);g_lk1.p4.y=g_lk1.p.y+2*w*cos(pi*2/5)+w*sin(pi*2/5);g_lk2.b=0;g_lk2.c=0;g_lk2.p.x=org.x+r*(1-sin(pi/5);g_lk2.p.y=org.y+r*(1+cos(pi/5);g_lk2.p1.x=g_lk2.p.x-w*cos(pi/5);g_lk2.p1.y=g_lk2.p.y-w*sin(pi/5);g_lk2.p2.x=g_lk2.p.x+w*cos(pi/5);g_lk2.p2.y=g_lk2.p.y+w*sin(pi/5);g_lk2.p3.x=g_lk2.p.x+2*w*sin(pi/5)-w*cos(pi/5);g_lk2.p3.y=g_lk2.p.y-2*w*cos(pi/5)-w*sin(pi/5);g_lk2.p4.x=g_lk2.p.x+2*w*sin(pi/5)+w*cos(pi/5);g_lk2.p4.y=g_lk2.p.y-2*w*cos(pi/5)+w*sin(pi/5);g_lk3.b=0;g_lk3.c=0;g_lk3.p.x=2*org.x+2*r-g_lk2.p.x;g_lk3.p.y=g_lk2.p.y;g_lk3.p1.x=2*org.x+2*r-g_lk2.p2.x;g_lk3.p1.y=g_lk2.p2.y;g_lk3.p2.x=2*org.x+2*r-g_lk2.p1.x;g_lk3.p2.y=g_lk2.p1.y;g_lk3.p3.x=2*org.x+2*r-g_lk2.p4.x;g_lk3.p3.y=g_lk2.p4.y;g_lk3.p4.x=2*org.x+2*r-g_lk2.p3.x;g_lk3.p4.y=g_lk2.p3.y;g_lk4.b=0;g_lk4.c=0;g_lk4.p.x=2*org.x+2*r-g_lk1.p.x;g_lk4.p.y=g_lk1.p.y;g_lk4.p1.x=2*org.x+2*r-g_lk1.p2.x;g_lk4.p1.y=g_lk1.p2.y;g_lk4.p2.x=2*org.x+2*r-g_lk1.p1.x;g_lk4.p2.y=g_lk1.p1.y;g_lk4.p3.x=2*org.x+2*r-g_lk1.p4.x;g_lk4.p3.y=g_lk1.p4.y;g_lk4.p4.x=2*org.x+2*r-g_lk1.p3.x;g_lk4.p4.y=g_lk1.p3.y;for(int i=0;i5;i+)point cr;int nx=(g_lki.p3.x-g_lki.p4.x)/5;int ny=(g_lki.p3.y-g_lki.p4.y)/5;for(int j=0;j4;j+)cr.x=g_lki.p3.x-nx-nx*j;cr.y=g_lki.p3.y-ny-ny*j;g_lki.ptj.x=cr.x;g_lki.ptj.y=cr.y;/ellipse(hdc,cr.x-r/40,cr.y-r/40,cr.x+r/40,cr.y+r/40);void drawarrowlen(hdc hdc,point p1,point p2)point pt5,tmp;hbrush br,br1,oldbr;int dx1,dx2,dy1,dy2;double k1,k2,l;double pi = 3.1415926535; double tp=(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);l=sqrt(tp);k1=20*sin(pi*10/180)/l;k2=20*cos(pi*10/180)/l;dy1=k1*(p1.x-p2.x)+k2*(p1.y-p2.y);dx1=k2*(p1.x-p2.x)-k1*(p1.y-p2.y);dy2=k2*(p1.y-p2.y)-k1*(p1.x-p2.x);dx2=k2*(p1.x-p2.x)+k1*(p1.y-p2.y);/在底部画下个三角形，高度为方格的1/4，作为旗的底座pt0.x=p2.x+dx1;pt0.y=p2.y+dy1;/(cellrect.bottom-cellrect.top)*3/4pt1.x=p2.x;pt1.y=p2.y;pt2.x=p2.x+dx2;pt2.y=p2.y+dy2; movetoex(hdc,p1.x,p1.y,&tmp);lineto(hdc,p2.x,p2.y);br=createsolidbrush(rgb(0,0,0);oldbr=(hbrush)selectobject(hdc,br);polygon(hdc,pt,3);selectobject(hdc,oldbr);void drawlk(hdc hdc,hwnd hwnd)point tmp;initdata(hwnd);for(int i=0;i5;i+)movetoex(hdc,g_lki.p1.x,g_lki.p1.y,&tmp);lineto(hdc,g_lki.p3.x,g_lki.p3.y);movetoex(hdc,g_lki.p2.x,g_lki.p2.y,&tmp);lineto(hdc,g_lki.p4.x,g_lki.p4.y);movetoex(hdc,g_lk0.p3.x,g_lk0.p3.y,&tmp);lineto(hdc,g_lk1.p3.x,g_lk1.p3.y);movetoex(hdc,g_lk1.p4.x,g_lk1.p4.y,&tmp);lineto(hdc,g_lk2.p3.x,g_lk2.p3.y);movetoex(hdc,g_lk2.p4.x,g_lk2.p4.y,&tmp);lineto(hdc,g_lk3.p3.x,g_lk3.p3.y);movetoex(hdc,g_lk3.p4.x,g_lk3.p4.y,&tmp);lineto(hdc,g_lk4.p3.x,g_lk4.p3.y);movetoex(hdc,g_lk4.p4.x,g_lk4.p4.y,&tmp);lineto(hdc,g_lk0.p4.x,g_lk0.p4.y);textoutw(hdc,g_lk0.p1.x+20,g_lk0.p1.y,lc,2);textout(hdc,g_lk1.p2.x,g_lk1.p2.y-20,b,1);textout(hdc,g_lk2.p1.x+20,g_lk2.p1.y,a,1);textoutw(hdc,g_lk3.p1.x+20,g_lk3.p1.y-20,le,2);textout(hdc,g_lk4.p1.x-20,g_lk4.p1.y-20,d,1);/画顺时针连线hpen pen,oldpen;pen= createpen(ps_solid,5,rgb(0,255,255); oldpen=(hpen)selectobject(hdc,pen); drawarrowlen(hdc,g_lk1.pt3,g_lk2.pt0);drawarrowlen(hdc,g_lk3.pt3,g_lk4.pt0);drawarrowlen(hdc,g_lk4.pt3,g_lk0.pt3);selectobject(hdc,oldpen);/画交通线hpen pen,pen1,oldpen;pen= createpen(ps_solid,5,rgb(0,255,255);/pen1= createpen(ps_solid,10,rgb(0,255,255); oldpen=(hpen)selectobject(hdc,pen);switch(nst)case 0:break;case 1:drawarrowlen(hdc,g_lk1.pt0,g_lk0.pt0); drawarrowlen(hdc,g_lk1.pt1,g_lk4.pt2);/drawarrowlen(hdc,g_lk1.pt2,g_lk3.pt1);/drawarrowlen(hdc,g_lk1.pt3,g_lk2.pt0);break;case 2:point pt1,pt2;pt1.x=g_lk2.pt0.x+10;pt1.y=g_lk2.pt0.y;pt2.x=g_lk1.pt3.x+10;pt2.y=g_lk1.pt3.y; drawarrowlen(hdc,pt1,pt2);drawarrowlen(hdc,g_lk2.pt1,g_lk0.pt1);drawarrowlen(hdc,g_lk2.pt2,g_lk4.pt1);break;case 3:drawarrowlen(hdc,g_lk3.pt0,g_lk2.pt3);drawarrowlen(hdc,g_lk3.pt1,g_lk1.pt2);drawarrowlen(hdc,g_lk3.pt2,g_lk0.pt2);drawarrowlen(hdc,g_lk3.pt3,g_lk4.pt0);break;case 4:drawarrowlen(hdc,g_lk4.pt1,g_lk2.pt2);drawarrowlen(hdc,g_lk4.pt2,g_lk1.pt1);drawarrowlen(hdc,g_lk4.pt3,g_lk0.pt3);break;selectobject(hdc,old