數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告交通燈問(wèn)題

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課題28：交通燈問(wèn)題多叉路口交通燈的管理問(wèn)題。通常，在十字交叉路口只需設(shè)紅、綠兩色的交通燈便可保持正常的交通秩 序，而在多叉路口需設(shè)幾種顏色的交通燈才能既使車(chē)輛相互之間不 碰撞，又能達(dá)到車(chē)輛的最大流通。假設(shè)有一個(gè)如圖(a)所示的五叉路口，其中c和e為單行道。在路口有13條可行的通路，其中有的 可以同時(shí)通行，如ab和ec，而有的不能同時(shí)通行，如eb和ad。那么，在路口應(yīng)如何設(shè)置交通燈進(jìn)行車(chē)輛的管理呢？求解步驟：1.模型表示：（1）由于題目要求是對(duì)多叉路口交通燈的管理。一般，在十字交叉路口我們只需設(shè)紅、綠兩色的交通燈便可保持正常的交通秩序，但是在多叉路口需設(shè)多種顏色的交通燈才能既使

2、車(chē)輛相互之間不碰撞，又能達(dá)到車(chē)輛的最大流通。題目給出如上圖(a)所示的五叉路口，其中c和e為單行道。在路口有13條可行的通路，其中有的可以同時(shí)通行，如ab 和ec，而有的不能同時(shí)通行，如eb 和ad。要求出在路口應(yīng)如何設(shè)置交通燈進(jìn)行車(chē)輛的管理。（2）在圖中，用箭頭表示一條通路，如下圖，b.a.e.d路口的紅綠點(diǎn)表示交通燈，按交通規(guī)則，紅燈停，綠燈行。某交通路口的綠燈亮了，則此路口的車(chē)可開(kāi)出，其他路口的車(chē)可開(kāi)進(jìn)，求解是假設(shè)c路口無(wú)交通燈，而且b處燈為綠燈，其它為紅燈，按此模型可以求解后可以讓各個(gè)路口的車(chē)輛正常通行。2.算法設(shè)計(jì)：設(shè)計(jì)本題算法的構(gòu)思如下：為求出符合條件的交通燈數(shù)，要在求解過(guò)程中進(jìn)行

3、試探，按照?qǐng)D形依據(jù)交通規(guī)則讓交通燈在十秒內(nèi)改變，所以程序編寫(xiě)時(shí)箭頭試探可行路徑，若試探成功，會(huì)在試探完畢后圖形將顯示此時(shí)的所有可行路徑，即此時(shí)的箭頭指向。設(shè)置如下：（1）jtd.cpp定義應(yīng)用程序的入口點(diǎn)。在jtd.cpp中定義全局變量:hinstance hin表示當(dāng)前實(shí)例；tchar sztitlemax_loadstring表示標(biāo)題欄文本；tchar szwindowclassmax_loadstring表示主窗口類(lèi)名。函數(shù): myregisterclass()目的是注冊(cè)窗口類(lèi)。函數(shù): initinstance(hinstance, int)目的是保存實(shí)例句柄并創(chuàng)建主窗口，在此函數(shù)中，我

4、們?cè)谌肿兞恐斜４鎸?shí)例句柄并創(chuàng)建和顯示主程序窗口。函數(shù): wndproc(hwnd, uint, wparam, lparam)目的是處理主窗口的消息wm_command 處理應(yīng)用程序菜單wm_paint- 繪制主窗口wm_destroy- 發(fā)送退出消息并返回int_ptr callback about(hwnd hdlg, uint message, wparam wparam, lparam lparam) “關(guān)于”框的消息處理函數(shù)。（2）op.cpp定義應(yīng)用程序。程序定義可以存儲(chǔ)五個(gè)路口一維數(shù)組g_lk5；函數(shù)initdata(hwnd hwnd)對(duì)數(shù)據(jù)進(jìn)行初始化；在應(yīng)用程序中作圖時(shí)調(diào)用

5、jtd.cpp中的函數(shù)實(shí)現(xiàn)消息的響應(yīng)，則會(huì)在窗口的客戶(hù)區(qū)畫(huà)出所求圖形，在畫(huà)圖時(shí)的探索過(guò)程中即已實(shí)現(xiàn)算法的描述，求解出題目所要實(shí)現(xiàn)的交通燈管理，需四種顏色的交通燈才能使車(chē)輛正常通行。3.程序?qū)崿F(xiàn)：為上機(jī)實(shí)現(xiàn)本題，還需要做一些工作：1.添加功能：由算法可知，需要添加一些功能，如輸入數(shù)據(jù)建圖、輸出路徑，顯示求解狀態(tài)等。2.結(jié)構(gòu)及類(lèi)型說(shuō)明：若采用數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)工具，則可借助于實(shí)驗(yàn)工具中的存儲(chǔ)結(jié)構(gòu)，因此可省掉諸如類(lèi)型說(shuō)明、建圖、顯示圖等許多麻煩。于是我采用win32應(yīng)用程序中的典型的“helloword”程序，它可以提供并自動(dòng)生成一些程序代碼，在其中實(shí)現(xiàn)圖形的顯示更容易。3.輸入圖結(jié)構(gòu)：為方便地調(diào)試算法，

6、需要能方便地建圖。若采用逐個(gè)輸入元素的方式來(lái)建圖，會(huì)比較麻煩，這對(duì)調(diào)試算法來(lái)說(shuō)也是不方便的。為此，在“jtd.cpp”中利用一些函數(shù)實(shí)現(xiàn)消息響應(yīng)，在程序?qū)崿F(xiàn)時(shí)，調(diào)用這些函數(shù)即可實(shí)現(xiàn)圖形中箭頭的表示。4.顯示結(jié)構(gòu)：合理地顯示結(jié)構(gòu)是調(diào)試算法所必需的。在此，采用工具系統(tǒng)中的圖結(jié)構(gòu)、數(shù)組等有關(guān)功能，以方便地顯示結(jié)構(gòu)。5.顯示輸出結(jié)果：輸出結(jié)果也必須要以可接受的形式顯示出來(lái)。此處為形象的表達(dá)出圖形以便觀察，當(dāng)一個(gè)交通燈亮?xí)r，用箭頭表示此時(shí)可以通行的路口的車(chē)。完整程序如下：#pragma once#include resource.hextern void drawlk(hdc hdc,hwnd hwnd

7、);extern void drawsec(hdc hdc);extern void initdata(hwnd hwnd);/ jtd.cpp : 定義應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include jtd.h#define max_loadstring 100/ 全局變量:hinstance hinst;/ 當(dāng)前實(shí)例tchar sztitlemax_loadstring;/ 標(biāo)題欄文本tchar szwindowclassmax_loadstring;/ 主窗口類(lèi)名/ 此代碼模塊中包含的函數(shù)的前向聲明:atommyregisterclass(hinstance hi

8、nstance);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_param

9、eter(lpcmdline); / todo: 在此放置代碼。msg msg;haccel hacceltable;/ 初始化全局字符串loadstring(hinstance, ids_app_title, sztitle, max_loadstring);loadstring(hinstance, idc_jtd, szwindowclass, max_loadstring);myregisterclass(hinstance);/ 執(zhí)行應(yīng)用程序初始化:if (!initinstance (hinstance, ncmdshow)return false;hacceltable = lo

10、adaccelerators(hinstance, makeintresource(idc_jtd);/ 主消息循環(huán):while (getmessage(&msg, null, 0, 0)if (!translateaccelerator(msg.hwnd, hacceltable, &msg)translatemessage(&msg);dispatchmessage(&msg);return (int) msg.wparam;/ 函數(shù): myregisterclass()/ 目的: 注冊(cè)窗口類(lèi)。/ 注釋:/ 僅當(dāng)希望/ 此代碼與添加到 windows 95 中的“registerclass

11、ex”/ 函數(shù)之前的 win32 系統(tǒng)兼容時(shí)，才需要此函數(shù)及其用法。調(diào)用此函數(shù)十分重要，/ 這樣應(yīng)用程序就可以獲得關(guān)聯(lián)的/ “格式正確的”小圖標(biāo)。/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

12、= 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

13、(&wcex);/ 函數(shù): initinstance(hinstance, int)/ 目的: 保存實(shí)例句柄并創(chuàng)建主窗口/ 注釋:/ 在此函數(shù)中，我們?cè)谌肿兞恐斜４鎸?shí)例句柄并/ 創(chuàng)建和顯示主程序窗口。/extern int nst;extern int nsec;bool initinstance(hinstance hinstance, int ncmdshow) hwnd hwnd; hinst = hinstance; / 將實(shí)例句柄存儲(chǔ)在全局變量中 hwnd = createwindow(szwindowclass, sztitle, ws_overlappedwindow, cw_

14、usedefault, 0, cw_usedefault, 0, null, null, hinstance, null); if (!hwnd) return false; showwindow(hwnd, ncmdshow); updatewindow(hwnd); return true;/ 函數(shù): wndproc(hwnd, uint, wparam, lparam)/ 目的: 處理主窗口的消息。/ wm_command- 處理應(yīng)用程序菜單/ wm_paint- 繪制主窗口/ wm_destroy- 發(fā)送退出消息并返回/lresult callback wndproc(hwnd hwn

15、d, 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(hw

16、nd);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

17、;invalidaterect(hwnd,null,true); break;case wm_destroy:postquitmessage(0);break;default:return defwindowproc(hwnd, message, wparam, lparam);return 0;/ “關(guān)于”框的消息處理程序。int_ptr callback about(hwnd hdlg, uint message, wparam wparam, lparam lparam)unreferenced_parameter(lparam);switch (message)case wm_init

18、dialog: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;#inclu

19、de 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=r

20、ect.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=

21、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=

22、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*co

23、s(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

24、.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

25、;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;i

26、5;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 b

27、r,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

28、.x-p2.x)+k1*(p1.y-p2.y);/在底部畫(huà)下個(gè)三角形，高度為方格的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

29、,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(h

30、dc,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(h

31、dc,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);/畫(huà)順時(shí)針連線hpen pen,oldpen;pen= createpen(ps_solid,5,rgb(0

32、,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);/畫(huà)交通線hpen pen,pen1,oldpen;pen= createpen(ps_solid,5,rgb(0,255,255);/pen1= createpen(ps_solid,10,rgb(0,255,255); ol

33、dpen=(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

34、.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