數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(交通燈管理,含最終的報告)

1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計設(shè)計題目 交通燈管理系統(tǒng)學生姓名 吳軍學 號 11s2156124專業(yè)班級 11計科專升本指導(dǎo)教師 余云信息工程學 院 計算機科學與技術(shù) 系安徽新華學院課程設(shè)計成績評定表(本科)課題名稱交通燈管理系統(tǒng)院 系信息工程學院年級專業(yè)11計科專升本學 號姓 名成 績11s2156124吳軍課題設(shè)計目的與設(shè)計意義1、課題設(shè)計目的：城市的日益發(fā)展帶來了很多的交通道路問題，其中有關(guān)于交通燈的設(shè)計管理問題尤為重要。本次課程設(shè)計的目的在于解決多岔道的交通路口信號燈的解決方案，既要使車輛安全有序地通過路口，又要使得路口的流通量最大2、課題設(shè)計意義：熟練運用離散數(shù)學的知識，利用數(shù)學建模

2、簡化實際問題；將數(shù)學模型實現(xiàn)計算機語言的轉(zhuǎn)化；靈活運用數(shù)據(jù)結(jié)構(gòu)中的各種數(shù)據(jù)結(jié)構(gòu)，存儲結(jié)構(gòu)以及運算，為建立的數(shù)學模型選擇合理的數(shù)據(jù)結(jié)構(gòu)，存儲結(jié)構(gòu)以及運算；加深對數(shù)據(jù)結(jié)構(gòu)算法的理解，以及能夠分析算法的優(yōu)劣指導(dǎo)教師：年 月 日目錄一 需求分析41.1設(shè)計背景41.2任務(wù)概述4二、 詳細設(shè)計52.1數(shù)據(jù)結(jié)構(gòu)52.2算法流程圖62.2.1建立鄰接矩陣的流程圖62.2.2 交通燈顏色模塊的流程圖62.3函數(shù)之間的調(diào)用關(guān)系圖72.3.1 輸入圖函數(shù)72.3.2 染色函數(shù)82.3.3 定位函數(shù)82.3.4 主程序9三、調(diào)試分析93.1 經(jīng)驗體會93.2 算法改進10四、 用戶手冊10五、 測試結(jié)果10六、 附

3、錄12多叉路口交通燈管理一 需求分析1.1設(shè)計背景通常，在十字路口只需設(shè)紅、綠兩色的交通燈便可以保證正常的交通秩序，而在多叉路口需設(shè)計幾種顏色的交通燈才能既使車輛相互之間不碰撞，又能達到車輛的最大流量。該程序就是在多叉路口情況下，判斷各個路口交通燈顏色，以便人們進行管理。對于用戶任意輸入的多叉路口（實際輸入所有的可以通行的方向及數(shù)量，從而構(gòu)建出圖），輸出需要的交通燈的數(shù)量。1.2任務(wù)概述假設(shè)有一個如圖1所示的五叉路口，其中C和E為單行道。在路口有13條可行的道路，其中有的可以同時通行，如A>B和E>C，而有的不能同事通行，如E>B，A>D，那么，如何設(shè)置交通燈呢？每個圓

4、圈表示五叉路口上的一條通路，兩個圓圈之間的連線表示這兩個圓圈表示的兩條道路不能同事通行。設(shè)置交通燈的問題等價為對圖的頂點進行染色問題。要求對圖上的每個頂點染一種顏色，并且要求有限相連的兩個頂點不能具有相同顏色，而且總的顏色種類盡可能少。所以，我準備把每個頂點用字母“a、b、c、”表示，而染色的顏色用數(shù)字表示?？梢酝瑫r通行的道路交通燈的顏色相同，不能同時通行的顏色不同。頂點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”表示。二、 詳細設(shè)計2.1數(shù)據(jù)結(jié)構(gòu)首先，是考慮數(shù)據(jù)類型。在多叉路口中，每

5、條通路是最基本的組成部分，對于交通燈管理已經(jīng)不可能在細分了，所以選定通路作為數(shù)據(jù)的基本類型，并在程序中定義圖的數(shù)據(jù)結(jié)構(gòu),其中包含存放圖的頂點和圖的邊，以及頂點數(shù)和邊數(shù)。用鄰接矩陣表示圖的結(jié)構(gòu)。其形式描述如下：int color30=0;/來存儲對應(yīng)塊的對應(yīng)顏色typedef char vextype;typedef int adjtype;typedef struct /定義圖 vextype vexsMAXedg; /存放邊的矩陣 adjtype arcsMAXedgMAXedg; /圖的鄰接矩陣 int vnum,arcnum; /圖的頂點數(shù)和邊數(shù)Graph;在選擇數(shù)據(jù)結(jié)構(gòu)方面，直接用數(shù)組

6、來存儲數(shù)據(jù)，即使是在內(nèi)存中也用數(shù)組來處理數(shù)據(jù)間的聯(lián)系。運用順序表這個結(jié)構(gòu)雖然不是那么直觀，但在查找數(shù)據(jù)時的算法設(shè)計比較簡單容易實現(xiàn)，效率高，而且在內(nèi)存中的數(shù)據(jù)可以直接讀入到文件中，文件中的數(shù)據(jù)也可以直接讀入內(nèi)存，不需要進行轉(zhuǎn)換。所以在衡量的各個方面之后，我決定用數(shù)組來處理數(shù)據(jù)間的聯(lián)系。2.算法流程圖2.2.1建立鄰接矩陣的流程圖圖2-1鄰接矩陣流程圖2.2.2 交通燈顏色模塊的流程圖圖2-2交通燈顏色模塊流程圖3函數(shù)之間的調(diào)用關(guān)系圖構(gòu)想好總體規(guī)劃之后，便開始設(shè)計程序中需要用到的各個功能函數(shù)，輸入圖函數(shù)、染色函數(shù)、輸出函數(shù)等。圖3-1 函數(shù)關(guān)系圖2.3.1 輸入圖函數(shù) void Create(G

7、raph &G)考慮到輸入的問題，就是在輸入界面以何種形式輸入，輸入頂點和邊數(shù)以及邊的權(quán)值在計算機內(nèi)部建立數(shù)組存儲。部分代碼如下：printf("輸入多叉路口的頂點數(shù)和邊數(shù):n"); scanf("%d%d",&G.vnum,&G.arcnum); getchar(); printf("輸入多叉路口的各頂點：n"); for(i=1;i<=G.vnum;i+) scanf("%c",&G.vexsi); getchar(); printf("輸入邊的兩個頂點和權(quán)值:n

8、"); for(k=0;k<G.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;2.3.2 染色函數(shù) 給各個頂點染色，然后輸出染色結(jié)果，并調(diào)用判斷顏色是否滿足要求函數(shù)。從第一個頂點開始染色，而后判斷和其相鄰的頂點的顏色是夠與第一個頂點相

9、同。部分代碼如下：void trycolor(int s,Graph G)if(s>G.vnum) output(G); exit(1); else for(i=1;i<=N;i+)/對每一種色彩逐個測試 colors=i; if(colorsame(s,G)=0) trycolor(s+1,G);/進行下一塊的著色 2.3.3 定位函數(shù) 在已經(jīng)輸入的圖中，找到與要記錄的頂點在圖中的位置，返回值是在數(shù)組中的位置。部分代碼如下：int LocateVex(Graph G,char u)for(i=1;i<=G.vnum;i+) if(u=G.vexsi) return i; i

10、f(i=G.vnum) printf("Error u!n"); exit(1); return 0;2.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("相應(yīng)的亮燈方案:n"); trycolor(1,G); return 0;三、調(diào)試分析3.1 經(jīng)驗體會通過這次課設(shè)，

11、體會很深刻，將一直以來學到的東西都運用到實際上來，學以致用，對所學知識有了更深刻的理解，同時還發(fā)現(xiàn)了許多平時在書本上沒有遇見過的問題，促進了自己對知識的渴望，遇見了問題，就希望能夠通過查找課外書來解決它們。剛接觸題目的時候，自己就有了一定的想法，覺得這個程序做起來是問題不大的，但到了自己真正開始編程的時候卻發(fā)現(xiàn)遠遠沒有想象中那么簡單，很多細節(jié)的問題沒有預(yù)想到，很多關(guān)系的處理想得過于簡單，以至于實施起來遇到了很大的困難，花了大量的時間。3.2 算法改進關(guān)于這個程序的缺點方面，由于自己花的時間不是很多，再加上知識有限，并不會運用可視化編程工具來輔助自己編程，所以弄得這個程序的不足之處還是挺多的，首

12、當其沖的是程序界面，一開始的時候是注重功能的實現(xiàn)，并沒有怎么理會運用界面，而到了后期，當辛辛苦苦搞好了功能之后，界面就沒有動力再去弄了，所以程序的界面很粗糙。四、 用戶手冊在VC+環(huán)境下，運行該程序。根據(jù)提示輸入多叉路口的頂點數(shù)和邊數(shù)，例如五叉路口的情況，頂點13個，20條邊，就輸入13 20然后回車，根據(jù)提示輸入頂點a b c d e f g h i j k l m回車，根據(jù)提示輸入兩個頂點和權(quán)值a j 1 a e 1回車，程序結(jié)果就出現(xiàn)在屏幕上了“亮燈方案：1 1 1 1 2 2 3 3 1 2 4 4 1”五、 測試結(jié)果正確輸入時結(jié)果如下圖第一組：圖1：輸出界面圖一第二組：圖2：輸出界面

13、圖二第三組：圖3 輸出界面圖三第四組：錯誤輸入后，如果不按照要求輸入， 測試結(jié)果：系統(tǒng)沒能作出良好提示，突然退出 圖4 出錯界面六、 附錄#include <stdio.h>#include <stdlib.h>#define MAXedg 30#define MAX 0#define N 4 /亮燈的顏色數(shù)int color30=0;/來存儲對應(yīng)塊的對應(yīng)顏色typedef char vextype;typedef int adjtype;typedef struct /定義圖 vextype vexsMAXedg; /存放邊的矩陣 adjtype arcsMAXedg

14、MAXedg; /圖的鄰接矩陣 int vnum,arcnum; /圖的頂點數(shù)和邊數(shù)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("輸入多叉路口的頂點數(shù)和邊數(shù):n"); scanf(&q

15、uot;%d%d",&G.vnum,&G.arcnum); getchar(); printf("輸入多叉路口的各頂點：n"); for(i=1;i<=G.vnum;i+) scanf("%c",&G.vexsi); getchar(); printf("輸入邊的兩個頂點和權(quán)值:n"); for(k=0;k<G.arcnum;k+) scanf("%c", &v1);getchar(); scanf("%c", &v2);getcha

16、r(); 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+)/分別于前面已經(jīng)著色的幾塊比較 if(G.arcsis=1&&colori=colors) flag=1;break; return flag;void output(Graph G) int i; for(i=1;i<=G.vnum;i+) printf("%d ",colori); printf("n");void trycolor(int s,Graph G)/s為開始圖色的頂點，從1開始 int i; if(s>G.vnum) output(G); exit(1); else for(i=1;i<=N;i+)/對每一種色彩逐個測試 co