全國交通咨詢模擬系統(tǒng).doc

全國交通咨詢模擬系統(tǒng)目錄一、 需求分析4二、 個人工作4三、概要設計51主程序流程圖：52創(chuàng)建圖算法流程圖：6四、源程序14五、程序結果255.3設計和調試分析29六、程序設計體會30全國交通咨詢模擬系統(tǒng)一、 需求分析旅客對由于出行目的的不同對交通工具的要求也有不同。例如，因公事出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則希望旅費盡可能省，而老年旅客則要求中轉次數最少。為了能滿足廣大旅客的需求，方便旅客出行，就此編制一個全國城市間的交通咨詢程序，為旅客提供兩種或者三種最優(yōu)決策的交通咨詢，達到如下的基本要求:：（1） 提供對城市信息進行編輯（如：添加和刪除）的功能.（2） 城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班表進行編輯（增加或刪除）的功能。（3） 提供兩種最優(yōu)決策：最快到達和最省錢到達。全程只考慮一種交通工具。（4） 旅途中耗費的總時間應該包括中轉站的等候時間。（5） 咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘哪趟列車或哪一次班機到何地。（6） 通過對比以及用戶操作基本達到旅客出行的便利。二、 個人工作 此次課程設計是對全國城市交通圖列車時刻表及飛機航班表的編輯。此次課設是利用VC工具在dos環(huán)境下實現全國交通的咨詢與管理。通過此次程序可以對全國城市之間火車與飛機進行兩方面的咨詢，即最少的時間與最少的費用的咨詢，從而方便旅客的出行。通過此次課程設計，我要學會怎樣用在VC dos環(huán)境下編程，而且要通過此次課程設計加深對數據結構的理解，在設計中用鄰接表作交通圖的存儲結構，表示邊的結點中除含有鄰接點的信息外，還包括交通工具、路程中消耗的時間和花費以及出發(fā)和到達的時間等屬性。圖中頂點城市的信息，包括城市名稱、城市編號和依附該頂點的邊的指針。在程序中，利用迪杰斯特拉算法求花錢最少和花時間最少的交通方式。三、概要設計1主程序流程圖：開始CreateGraph(GT)CreateGraph(GP)OpenGraph_T(GT)OpenGraph_P(GP)Main_Menu(GT,GP)DestoryGraph(GT) DestoryGraph(GP)結束SaveGraph_T(GT)SaveGraph_P(GP)2創(chuàng)建圖算法流程圖：N開始iMAXVTXNUMG.FLAGI=0i+Y結束3打開圖算法流程圖：開始NY讀出城市的號數cityNum，標志Flag，城市名稱cityNamejvexNum讀出圖中頂點數vexNum,邊數edgeNum打開文件j+iedgeNumN讀出邊上的各信息Y 結束i+4主菜單操作算法流程圖：開始Switch(n)Case 2:Case 0:Case 1:Inquire_Menu(GT,GP)breakManage_Menu(GT,GP)5咨詢菜單流程圖Inquire_Menu(GT,GP)Switch(choice)Case 1:Case 2:Case 0:Inquire_Money(GT,GP)Inquire_Time(GT,GP)break6咨詢錢最少模塊圖Inquire_Money(GT,GP)NWhile(True)Y輸入 nYn=1NYinput_Money(GP,st, nd)n=2LeastMoneyPath (GP,st,nd,p)Ninput_Money(GT,st, nd)print_Money(GP,p)LeastMoneyPath(GT,st,nd,p)Yn=2結束Nprint_Money(GT,p)結束結束結束7input_Money(Graph G, int &st,int &sn)算法流程圖While(True)輸入起始城市名稱YinputVex(G,st)=truebreakNWhile(True)輸入終止城市名稱inputVex(G,sn)=truebreakN8inputVex(G,st)算法流程圖開始輸入城市名字 nameYLocateVex(G,name,i)=trueReturn trueN輸出城市不存在結束9LocateVex(G,name,i)算法流程圖開始imaxvexnumYG.Flagi=1&strcmp(G.Adjlisti.cityName,name)=0i+YReturn falseReturn true結束10print_Money(GT,p)算法流程圖開始i=0ip.len打印邊p的信息Sum+=p.money i+Y結束輸錢sumN11LeastMoneyPath(GT,st,nd,p)算法流程圖結束初始化i=0inextEdgep-elem.Moneyelem.jvex重置每個頂點的最少錢的路徑dijkstp-elem.jvex=p-elem.Money t=p-elemSetPath(pathp-elem.jvex,st,p-elem.jvex,t)Yp=qYNFound = false求從st 到nd 的最短路徑算法并復制此路徑copyPath(pathw,pathv)開始11ShortestTimePath(GT,st,nd,p)算法流程圖開始每個點初始一個最大值初始每條路徑置時間0置起點的時間為n置p為起點的第一條邊檢測依附每個頂點的邊依據迪杰斯特求每個起點到終點的時間最少的路徑結束12Manage_Menu(GT,GP)算法流程圖開始Switch(choice)Case 1:Case 0:Case 3:Case 2:Plane_Edit(GT,GP)breakTrain_Edit(GT,GP)City_Edit(GT,GP)13City_Edit(GT,GP)算法流程圖開始輸入n進行選擇Nn=1NYn =2添加城市及相關信息Y刪除城市及相關信息結束輸出錯誤輸入n進行選擇結束Nn =0Y結束14. Train_Edit(GT,GP)算法流程圖開始NWhile(true)YBreak 輸入n進行選擇結束Yn=1NYn=2輸入列車的信息breakN刪除列車的信息重新輸入n進行選擇Nn=0breakYbreak注釋：部分算法的設計思想相同，只是參數不同，故省略部分程序流程圖。四、源程序#define MAXVTXNUM 30 /圖中頂點數的最大值/*頂點、邊和圖類型*/typedef struct /定義各車次及航班的信息弧的信息int ivex; /起始點號int jvex; /終點號char Number10; / 車次號int Money; /費用int StartTime; /起始時間（秒）int EndTime; /終止時間（秒）int Time; /中途時間（秒）EdgeInfo; /邊的信息typedef struct EdgeNode /邊的信息 弧結點 EdgeInfo elem; EdgeNode *nextEdge;EdgeNode, *EdgePtr;/邊的結點類型，指向邊的指針typedef struct /城市信息 頭結點char cityName10;int cityNumber;EdgePtr firstEdge; /指向的一條依附該頂點的邊的指針Vnode; /頂點類型typedef struct /圖的結構Vnode AdjlistMAXVTXNUM;/鄰接表int vexNum, edgeNum; /圖中的頂點數和邊數int FlagMAXVTXNUM; /標志是否是圖中的頂點,0表示不是,1表示是 Graph; /圖類型/*圖的基本操作*/* 路徑類型 */typedef structint vx,vy; /vx為路徑的起點,vy為路徑的終點EdgeInfo p; /路徑中邊的信息Edge;typedef struct Edge edgesMAXVTXNUM; /路徑中邊的序列 : edgesi表示從起點到i的最短路徑int len; /路徑中邊的數目Path;/*/void copyPath (Path &p1,Path &p2)/復制路徑p1=p2int i;for(i=0;ip2.len;i+)p1.edgesi.vx=p2.edgesi.vx;p1.edgesi.vy=p2.edgesi.vy;p1.edgesi.p =p2.edgesi.p;p1.len=p2.len;void SetPath(Path &pa, int v, int w, EdgeInfo t)/設置pa從v到w的第一條邊,邊的信息為tpa.edges0.vx=v;pa.edges0.vy=w;pa.edges0.p=t;pa.len=1;#include int TimeChange(int hour,int minute) /把輸入的小時和分鐘樹轉換成分鐘的形式，忽略天數if(minute60)hour=hour+minute/60;minute=minute%60;if(hour24)hour=hour%24;#include #include #include #include Graph.h#include Time.h#include Path.h#define NULL 0bool OpenGraph_T(Graph &G);bool OpenGraph_P(Graph &G);int Main_Menu(Graph >,Graph &GP);bool SaveGraph_T(Graph G); bool SaveGraph_P(Graph G);void main()Graph GT; /火車交通圖Graph GP; /飛機交通圖 CreateGraph(GT); /建立空的火車交通圖CreateGraph(GP); /建立空的飛機交通圖OpenGraph_T(GT); /打開已經存在火車的數據OpenGraph_P(GP); /打開已經存在飛機的數據Main_Menu(GT,GP); SaveGraph_T(GT); /保存火車數據SaveGraph_P(GP); /保存飛機數據DestoryGraph(GT);DestoryGraph(GP);/*/void LeastMoneyPath(Graph G, int st, int nd, Path &pathA) /st：起點號，nd：終點號，結果存儲在pathA中 /path包括路徑的長度，起點，終點和路徑信息/利用迪杰斯特拉算法的基本思想求圖G中從頂點st到nd的一條/最短路徑PathInfo,路徑長度pathLength/設int dijkstMAXVTXNUM;Path pathMAXVTXNUM;int i;int dijkstMAXVTXNUM;bool finalMAXVTXNUM=false; Path pathMAXVTXNUM; /每個頂點都有路徑 EdgeNode *p,*q; /邊的信息 弧結點 EdgeInfo t; /邊的信息bool found;int min=9999,min_i,v,w;for(i=0;inextEdge;if(p-elem.Moneyelem.jvex)dijkstp-elem.jvex=p-elem.Money;t=p-elem;SetPath(pathp-elem.jvex,st,p-elem.jvex,t);p=q;found= false;while(!found)/在所有未求得最短路徑的頂點求使得dijksti取最小的ifor(i=0;iMAXVTXNUM;i+)if(finali=false & dijkstinextEdge;w=p-elem.jvex;if(finalw=false &(dijkstv+p-elem.Money)elem.Money;copyPath(pathw,pathv);InsertPath(pathw,v,w,p-elem);p=q; /while(p) /else/ while(!found)copyPath(pathA,pathnd);void ShortestTimePath(Graph G, int st, int nd, int n ,Path &pathA)/st：起點號，nd：終點號，n：當前時間（秒），結果存儲在pathA中/利用迪杰斯特拉算法的基本思想求圖G中從頂點st到nd的一條/最短路徑PathInfo,路徑長度pathLength/設int dijkstMAXVTXNUM;Path pathMAXVTXNUM;int i;int dijkstMAXVTXNUM;bool finalMAXVTXNUM=false; int nowMAXVTXNUM;Path pathMAXVTXNUM;EdgeNode *p,*q;EdgeInfo t;bool found;int min=99999,min_i,v,w,time;for(i=0;inextEdge;if(p-elem.StartTimeelem.EndTime=nowst)time= 1440-TimeSub(p-elem.EndTime,nowst);elsetime= TimeSub(p-elem.EndTime,nowst);if(timeelem.jvex)dijkstp-elem.jvex=time;t=p-elem;SetPath(pathp-elem.jvex,st,p-elem.jvex,t);nowp-elem.jvex=p-elem.EndTime;p=q;found= false;while(!found)/在所有未求得最短路徑的頂點求使得dijksti取最小的ifor(i=0;iMAXVTXNUM;i+)if(finali=false & dijkstinextEdge;w=p-elem.jvex;if(finalw=false &(dijkstv+TimeSub(p-elem.EndTime,nowv)elem.EndTime,nowv);copyPath(pathw,pathv);InsertPath(pathw,v,w,p-elem);p=q; /while(p) /else/ while(!found)copyPath(pathA,pathnd);void Inquire_Money(Graph GT,Graph GP)Path p;int n=5;int st,nd;while(1)cout tt 1.查詢飛機;cout t 2.查詢火車;cout t 0.退出n;cout n;fflush(stdin);cout n;if(n=1)input_Money(GP,st, nd);LeastMoneyPath (GP,st,nd,p); /最少錢數print_Money(GP,p);break;else if(n=2)input_Money(GT,st, nd);LeastMoneyPath (GT,st,nd,p); /最少錢數print_Money(GT,p);break;else if (n=0)break;elsecout 輸入有誤，請重新輸入！nn;/咨詢系統(tǒng)菜單void Inquire_Menu(Graph GT,Graph GP)while(1)int choice=5;coutt*n;coutt*咨詢系統(tǒng)菜單 *n;cout t* 1.最省錢咨詢 *n;cout t* 2.最快到達咨詢 *n;cout t* 0.退出系統(tǒng) *n;cout t*n;cout choice;fflush(stdin);if(choice=0) break;switch(choice)case 1: Inquire_Money(GT,GP);break;case 2: Inquire_Time(GT,GP);break;default:cout 輸入錯誤選項,請重試。nn;/城市編輯void City_Edit(Graph >,Graph &GP)int n,i;char name10;while(1)cout n;cout t 1.添加城市 ;cout t 2.刪除城市 ;cout t 0.退出 ;cout n;fflush(stdin);if(n=1)cout name;fflush(stdin);InsertVex(GT,name);InsertVex(GP,name);cout n添加成功！n;break;else if(n=2)cout n請輸入刪除城市的名稱：;if(input_Vex(GT,i)=true)DeleteVex(GT,i);DeleteVex(GP,i);cout 刪除成功！n;break;else if(n=0)cout n;break;elsecout 輸入有誤，請重新輸入！;/列車時刻表編輯 void Train_Edit(Graph >,Graph GP)int n,st,sn;int hour,minute;char number10;EdgeInfo q;while(1)cout n;cout t 1.添加列車 ;cout t 2.刪除列車 ;cout t 0.退出 ;cout n;fflush(stdin);if(n=1)while(1)cout n請輸入起始城市的名稱：;if(input_Vex(GT,st)=true)break;while(1)cout n請輸入終點城市的名稱：;if(input_Vex(GT,sn)=true)break;cout number ;fflush(stdin);q.ivex=st;q.jvex=sn;strcpy(q.Number,number);cout q.Money;fflush(stdin);cout n請輸入起始時間：;cout hour;fflush(stdin);cout minute;fflush(stdin);q.StartTime=TimeChange(hour,minute);cout n請輸入到站時間：;cout hour;fflush(stdin);cout minute;fflush(stdin);q.EndTime=TimeChange(hour,minute);q.Time=TimeSub(q.EndTime,q.StartTime);cout n行車時間: q.Time/60 小時 q.Time%60 分鐘;InsertEdge(GT,q);cout n添加成功！ n;break;else if(n=2)while(1)cout n請輸入起始城市的名稱：;if(input_Vex(GT,st)=true)break;while(1)cout n請輸入終點城市的名稱：;if(input_Vex(GT,sn)=true)break;cout n請輸入車次：;if(input_Number(GT,st,sn,number)q.ivex=st;q.jvex=sn;strcpy(q.Number,number);DeleteEdge(GT,q);cout 刪除成功！n;break;else if(n=0)cout (n);break;elsecout 輸入有誤，請重新輸入！;void Manage_Menu(Graph >,Graph &GP)while(1)int choice=5;cout t* n;cout t* 管理系統(tǒng)菜單 *n;cout t* 1.城市編輯 *n;cout t* 2.列車時刻表編輯 *n;cout t* 3.航班時刻表編輯 *n;cout t* 0.退出系統(tǒng) *n;cout t* n;cout choice;fflush(stdin);if(choice=0) break;switch(choice)case 1: City_Edit(GT,GP);break;case 2: Train_Edit(GT,GP);break;case 3: Plane_Edit(GT,GP);break;default:cout 輸入錯誤選項