1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程設(shè)計任務(wù)書題 目公交咨詢程序?qū)W生姓名孫寶琳學(xué)號0124專業(yè)班級數(shù)學(xué)0701設(shè)計內(nèi)容與要求【問題描述】 利用圖實(shí)現(xiàn)公交咨詢系統(tǒng)，包括公交線路查詢、站點(diǎn)查詢以及最優(yōu)乘車方案的查詢?！拒浖δ堋? 從文件中接收圖和公交車信息；2 可實(shí)現(xiàn)確定公交線路查詢，即輸出該車的所有站點(diǎn)；3 可以對某一個站點(diǎn)進(jìn)行查詢輸出該站點(diǎn)的所有下一站；4 可以對乘車方案進(jìn)行查詢，即輸出確定起點(diǎn)，終點(diǎn)的最優(yōu)乘車方案，換車輸出換車次數(shù)及換車站點(diǎn)；【算法思想】設(shè)計公交車類（車號，路程長度，終點(diǎn)站）、圖類（站點(diǎn)名，公交車類，現(xiàn)有路線條數(shù)，現(xiàn)有站點(diǎn)數(shù)）、Dijkstra算法類（最短路徑上

2、的最后一個站點(diǎn)，最短路徑的站點(diǎn)數(shù)）；從文件中接收內(nèi)容并對圖和公交車進(jìn)行初始化，公交線路查詢在圖中找到起點(diǎn)站，按順序輸出所有公交車號相同的站點(diǎn)；乘車方案中利用Dijkstra算法算出最優(yōu)路線，并有最短路徑的最后一個站點(diǎn)將路徑上的所有站點(diǎn)入棧，出站時判斷是否換車并輸出方案；【提交成果】1.“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程設(shè)計任務(wù)書”一份，打印裝袋；2.“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程設(shè)計報告”一份，打印裝袋；3、上面兩項(xiàng)內(nèi)容的word文檔，通過電子郵件交到指導(dǎo)教師。起止時間2009 年 6 月 8 日 至 2009 年6月 19 日指導(dǎo)教師簽名年 月 日系（教研室）主任簽名年 月 日學(xué)生簽名孫寶琳 2009年 6

3、月18 日數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程設(shè)計專業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 班級 數(shù)學(xué)0701 學(xué)號 0124 姓名 孫寶琳 完成日期 6.18 指導(dǎo)教師（簽名）1、 程序設(shè)計說明書【設(shè)計題目】公交咨詢程序【問題描述】利用圖實(shí)現(xiàn)公交咨詢系統(tǒng)，包括公交線路查詢、站點(diǎn)查詢以及最優(yōu)乘車方案的查詢?！拒浖δ堋? 從文件中接收圖和公交車信息；2 可實(shí)現(xiàn)確定公交線路查詢，即輸出該車的所有站點(diǎn)；3 可以對某一個站點(diǎn)進(jìn)行查詢輸出該站點(diǎn)的所有下一站；4 可以對乘車方案進(jìn)行查詢，即輸出確定起點(diǎn)，終點(diǎn)的最優(yōu)乘車方案，換車輸出換車次數(shù)及換車站點(diǎn)；【算法思想】 設(shè)計公交車類（車號，路程長度，終點(diǎn)站），圖類（站點(diǎn)名，公交車類，現(xiàn)有路線條

4、數(shù)，現(xiàn)有站點(diǎn)數(shù)），Dijkstra算法類（最短路徑上的最后一個站點(diǎn)，最短路徑的站點(diǎn)數(shù)）；從文件中接收內(nèi)容并對圖和公交車進(jìn)行初始化，公交線路查詢在圖中找到起點(diǎn)站，按順序輸出所有公交車號相同的站點(diǎn)；乘車方案中利用Dijkstra算法算出最優(yōu)路線并有最短路徑的最后一個站點(diǎn)輸出乘車方案；【類的設(shè)計】 struct Bus /公交車類int number; /公交車號int length; /總站數(shù)char bus_stateMaxstate20; /站點(diǎn);class Graph /建立無向圖friend class Distance; /聲明友元類private:char statenameMaxst

5、ate20; /站點(diǎn)int busnumberMaxstateMaxstate; /鄰接矩陣，權(quán)值為這兩個站點(diǎn)的公交車號int currentstate; /當(dāng)前站點(diǎn)數(shù)int currentbus; /當(dāng)前公交車數(shù)Bus busesMaxbus; /公交車信息public:Graph() ； /無參構(gòu)造函數(shù)，對成員變量初始化 void Insertstate(char state)；/插入一個站點(diǎn)void Insertbusnumber(char V1,char V2,int busnum) ；/插入權(quán)值void Set_graph() ； /圖的建立bool IsGraphFull() ；

6、/判斷圖是否已滿void show_busmessage(int number)； /輸出公交信息int searchbusnumber(char v0,char v1) ； /查找指定站點(diǎn)的公交車號碼void direction(char v0,char v1) ； /輸出指定站點(diǎn)的公交車方向friend void busline(); /把外部函數(shù)定義為圖的友元函數(shù)，以便使用圖的私有成員變量friend void searchstate();friend void bestproject();friend void mainsurface();class StackNode /棧結(jié)點(diǎn)fri

7、end class Stack; /友元類private: char date20; /結(jié)點(diǎn)數(shù)據(jù)StackNode *link; /結(jié)點(diǎn)鏈指針public:/構(gòu)造函數(shù)：結(jié)點(diǎn)賦值StackNode (char d =0,StackNode *l =NULL)；;class Stack /定義棧private:StackNode *top; /棧頂指針public:Stack ( ) :top(NULL) /構(gòu)造函數(shù)Stack ( ); /析構(gòu)void Push(char item); /進(jìn)棧int Pop(char x);/退棧int GetTop(char x); /讀取棧頂元素void Ma

8、keEmpty (); /把棧置空int IsEmpty() ;class Distance:public Graph /定義最短距離類private:char path20; /最短距離的前一站int distanceMaxstate; /最短距離public:void bestchooce(char v0,char v1)； /最優(yōu)方案；【存儲結(jié)構(gòu)設(shè)計】 使用鄰接矩陣int busnumberMaxstateMaxstate;存儲圖的信息；公交車信息采用結(jié)構(gòu)體數(shù)組Bus busesMaxbus;存儲；棧使用鏈表來實(shí)現(xiàn)；【模塊劃分及調(diào)用關(guān)系】Main（） Mainsurface()退出Sea

9、rchstate()Bestproject()Busline()共有三個模塊：公交線路查詢Busline()、站點(diǎn)查詢Searchstate()、最優(yōu)方案Bestproject()【模塊流程圖】1. Busline():Mainsurface()Set_graph() 所有路線瀏覽特定車號的路線查詢循環(huán)輸出當(dāng)前車接收車號 存在 存 存在 輸出公交車信息show_busmessage()2 searchstate():Set_graph() 否 接收站點(diǎn)Mainsurface()在圖內(nèi)查找有站點(diǎn)名所到的車及方向3 bestproject(): 無路徑 有路徑 棧為 是 車相同 接收起始站Best

10、chooce()Set_graph()Dijkstra算法Mainsurface()對路徑上的站入棧出棧判斷是否是換車輸出換車信息輸出路徑Mainsurface()【界面設(shè)計】 采用簡單的人機(jī)會話，使操作簡單明了；【用戶手冊】 在程序所在文件夾下建立“公交查詢.txt”，并輸入以下內(nèi)容： 30世家星城-通訊學(xué)院-石油公寓-潘家莊-明德門-楊家村-城南客運(yùn)站-西八里村-醫(yī)學(xué)院-緯二街-雁南路-大雁塔-賽格電腦城-李家村-和平門-大差市-五路口-火車站;603電視塔-國展中心-吳家墳-八里村-緯二街-小寨-長安立交-省體育場-草場坡-南稍門-南門-鐘樓-北門-火車站;37城北客運(yùn)站-公交六公司-方

11、新村-龍首村-北關(guān)-鐘樓-東門-興慶路-建工路-幸福路南口;（每一個車的線路占一行）； 編譯運(yùn)行程序，根據(jù)提示執(zhí)行程序；要想有更為準(zhǔn)確的方案，可以在“公交查詢.txt”中加入公交車線路；2、 程序上機(jī)調(diào)試報告【語法錯誤及其排除】1 函數(shù)賦值時，將變量賦給了指針； 使用指針傳值；2 在出棧時沒有判斷棧是否為空，導(dǎo)致top指空 在出棧前判斷IsEmpty（）；【算法錯誤及其排除】1 在建立圖中沒有對a數(shù)組進(jìn)行置空，導(dǎo)致數(shù)據(jù)混亂；在使用a之前對a數(shù)組賦空；2 在輸出最優(yōu)結(jié)果時 沒有保留前一站使程序無法判斷是否換車加入b數(shù)組保留前一站；3、 程序測試結(jié)果【測試數(shù)據(jù)】30世家星城-通訊學(xué)院-石油公寓-潘

12、家莊-明德門-楊家村-城南客運(yùn)站-西八里村-醫(yī)學(xué)院-緯二街-雁南路-大雁塔-賽格電腦城-李家村-和平門-大差市-五路口-火車站;603電視塔-國展中心-吳家墳-八里村-緯二街-小寨-長安立交-省體育場-草場坡-南稍門-南門-鐘樓-北門-火車站;37城北客運(yùn)站-公交六公司-方新村-龍首村-北關(guān)-鐘樓-東門-興慶路-建工路-幸福路南口;（每一個車的線路占一行）；【輸出結(jié)果】1公交線路查詢： 2 站點(diǎn)查詢：3 最優(yōu)方案：【程序性能評價】 使用簡單；結(jié)果正確、明了；【性能改進(jìn)方向】1. 將鄰接矩陣改為三維，即在相同兩站間由多個公交可以到達(dá)；2. 在站點(diǎn)里加入方位，即在尋找最優(yōu)結(jié)果的時候可以不必將所有站

13、點(diǎn)進(jìn)行操作，加快運(yùn)行速度；3. 在公交車類中加入收費(fèi)，在最優(yōu)結(jié)果輸出時計算收費(fèi)(有刷卡、投幣、按站收費(fèi))；【收獲及體會】 通過這個程序的編寫使我對c+中文件的操作、圖的操作、棧的操作、查找等內(nèi)容有了更深的理解，在編譯的過程中也是我知道了自己的數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容還很淺，還需要在努力；4、 源程序代碼#include<fstream.h>/文件庫#include<stdlib.h>#include<string.h>/字符串函數(shù)庫const int Maxbus=100;/最大公交車數(shù)const int Maxstate=200;/最大站點(diǎn)數(shù)const int M

14、axValue=999;/最大值struct Bus /公交車類int number; /公交車號int length; /總站數(shù)char bus_stateMaxstate20; /站點(diǎn);class Graph /建立無向圖friend class Distance; /聲明友元類private:char statenameMaxstate20; /站點(diǎn)int busnumberMaxstateMaxstate; /鄰接矩陣，權(quán)值為這兩個站點(diǎn)的公交車號int currentstate; /當(dāng)前站點(diǎn)數(shù)int currentbus; /當(dāng)前公交車數(shù)Bus busesMaxbus; /公交車信息p

15、ublic:Graph() /無參構(gòu)造函數(shù)，對成員變量初始化for(int i=0;i<Maxstate;i+)for(int j=0;j<Maxstate;j+)if(i=j)busnumberij=-1; /自己到自己沒有車elsebusnumberij=MaxValue; currentstate=0;currentbus=0;for(i=0;i<Maxbus;i+)busesi.number=-1;busesi.length=0;void Insertstate(char state) /插入一個站點(diǎn)if(!IsGraphFull() /如果圖沒滿for(int i=

16、0;i<currentstate;i+) /查看該站是否已經(jīng)存在if(strcmp(state,statenamei)=0)break;if(i=currentstate) /如果不存在，在站點(diǎn)數(shù)組后加入strcpy(statenamecurrentstate,state);for(i=0;i<currentstate;i+)busnumbercurrentstatei=MaxValue;busnumbericurrentstate=MaxValue;busnumbercurrentstatecurrentstate=-1;currentstate+; /當(dāng)前數(shù)組加一void In

17、sertbusnumber(char V1,char V2,int busnum) /插入權(quán)值for(int i=0;i<currentstate;i+) /查找站點(diǎn)if(strcmp(V1,statenamei)=0)break;for(int j=0;j<currentstate;j+)if(strcmp(V2,statenamej)=0)break;if(i!=currentstate&&j!=currentstate) /站點(diǎn)存在插入權(quán)值busnumberij=busnum;busnumberji=busnum;void Set_graph() /圖的建立c

18、har ch700,a20;int j=0,k=0,i;for(i=0;i<20;i+) /對a數(shù)組初始化ai='0'ifstream infile("公交查詢.txt"); /以讀的方式打開文件if(!infile) /文件打開失敗，則結(jié)束程序cout<<"Cant't open '公交查詢.txt'"<<endl;exit(0);while(!infile.eof()&&currentbus<Maxbus) /文件沒有讀完infile>>buses

19、currentbus.number; /接收車號碼infile.getline(ch,700); / 在文件中讀取一行for(int i=0;chi!=''i+)if(chi!='-') /把站點(diǎn)暫存在a中aj+=chi;elsestrcpy(busescurrentbus.bus_statek+,a); /對公交車站點(diǎn)賦值Insertstate(a); /插入站點(diǎn)for(j=0;j<20;j+)aj='0' /對a數(shù)組初始化j=0;strcpy(busescurrentbus.bus_statek+,a);Insertstate(a);b

20、usescurrentbus.length=k; /當(dāng)前公交車長度賦值currentbus+; /當(dāng)前公交車數(shù)加一k=0;j=0;for(i=0;i<currentbus;i+)for(k=0;k<busesi.length-1;k+) /插入權(quán)值Insertbusnumber(busesi.bus_statek,busesi.bus_statek+1,busesi.number);bool IsGraphFull() /判斷圖是否已滿return currentstate=Maxstate;void show_busmessage(int number) /輸出公交信息for(i

21、nt i=0;i<currentbus;i+) /查找權(quán)值if(busesi.number=number)break;if(i=currentbus)cout<<"查無此車!"<<endl;else /找到，輸出該公交車信息cout<<" "<<number<<"路（"<<busesi.bus_state0<<"<>"<<busesi.bus_statebusesi.length-1<<&q

22、uot;）"<<endl;for(int j=0;j<busesi.length-1;j+)cout<<busesi.bus_statej<<"<>"cout<<busesi.bus_statej<<endl;int searchbusnumber(char v0,char v1) /查找指定站點(diǎn)的公交車號碼int i,j,numb;for(int k=0;k<currentstate;k+) /查找站點(diǎn)if(strcmp(v0,statenamek)=0)i=k;if(strcm

23、p(v1,statenamek)=0)j=k;numb=busnumberij; /在鄰接矩陣中查找權(quán)值return numb;void direction(char v0,char v1) /輸出指定站點(diǎn)的公交車方向int i,j,numb,l;for(int k=0;k<currentstate;k+) /查找指定站點(diǎn)if(strcmp(v0,statenamek)=0)i=k;if(strcmp(v1,statenamek)=0)j=k;numb=busnumberij; for(l=0;l<currentbus;l+) /查找該公交車位置if(numb=busesl.num

24、ber)break;for(k=0;k<busesl.length;k+)if(strcmp(busesl.bus_statek,v0)=0)i=k;if(strcmp(busesl.bus_statek,v1)=0)j=k;if(i<j) /輸出公交車方向cout<<"（"<<busesl.bus_state0<<"->"<<busesl.bus_statebusesl.length-1<<"）"<<endl;elsecout<<&

25、quot;（"<<busesl.bus_state0<<"<-"<<busesl.bus_statebusesl.length-1<<"）"<<endl;friend void busline(); /把外部函數(shù)定義為圖的友元函數(shù)，以便使用圖的私有成員變量friend void searchstate();friend void bestproject();friend void mainsurface();class StackNode /棧結(jié)點(diǎn)friend class Sta

26、ck; /友元類private: char date20; /結(jié)點(diǎn)數(shù)據(jù)StackNode *link; /結(jié)點(diǎn)鏈指針public:/構(gòu)造函數(shù)：結(jié)點(diǎn)賦值StackNode (char d =0,StackNode *l =NULL):link(l)strcpy(date,d); class Stack /定義棧private:StackNode *top; /棧頂指針public:Stack ( ) :top(NULL) /構(gòu)造函數(shù)Stack ( ); /析構(gòu)void Push(char item); /進(jìn)棧int Pop(char x);/退棧int GetTop(char x); /讀取棧頂

27、元素void MakeEmpty (); /把棧置空int IsEmpty() return top = NULL; Stack :Stack()StackNode *p;while(top != NULL) /逐結(jié)點(diǎn)回收p=top; top=top->link; delete p; /釋放棧頂結(jié)點(diǎn)void Stack :MakeEmpty ()/把棧置空 StackNode *p;while (top != NULL) /逐結(jié)點(diǎn)回收p=top; top=top->link; delete p; /釋放棧頂結(jié)點(diǎn)void Stack:Push(char item )/進(jìn)棧 Stack

28、Node *p =new StackNode ( item, top );/新結(jié)點(diǎn)p->link=top; /鏈入*top之前top = p; /成為新棧頂int Stack :Pop (char x ) /退棧 if ( IsEmpty ( ) ) return 0; StackNode *p = top; top = top->link; /修改棧頂指針strcpy(x,p->date); /送回退棧元素 delete p; return 1; /釋放int Stack:GetTop (char x )/讀取棧頂元素 if (IsEmpty() return 0;strc

29、py(x,top->date); /送回棧頂元素return 1; /釋放 class Distance:public Graph /定義最短距離類private:char path20; /最短距離的前一站int distanceMaxstate; /最短距離public:void bestchooce(char v0,char v1) /最優(yōu)方案int sMaxstate,v,i,j,w,start=-1,end=-1,number1,number2;char a20,b20;Stack stack1; /定義棧Set_graph(); /建立圖for(i=0;i<curren

30、tstate;i+) / 查找起始站、終點(diǎn)站if(strcmp(statenamei,v0)=0) start=i;if(strcmp(statenamei,v1)=0)end=i;if(start=-1|end=-1)cout<<"站點(diǎn)不存在!"<<endl;bestproject();for( i=0;i<currentstate;i+) /初始化距離、前一站si=0; /s集合賦空if(busnumberstarti<MaxValue)distancei=1;pathi=start;elsedistancei=busnumberst

31、arti; /權(quán)值賦給最短距離pathi=-1;sstart=1; /起始站放入s集合distancestart=0;int min;for(i=0;i<currentstate;i+)min=MaxValue;for(w=0;w<currentstate;w+) /在鄰近的頂點(diǎn)中查找最短距離if(!sw&&distancew<min)v=w;min=distancew; sv=1; for(j=0;j<currentstate;j+)if(!sj&&(min+1)<distancej&&busnumbervj<

32、;MaxValue) /計算起點(diǎn)到每個站點(diǎn)的距離distancej=min+1;pathj=v;i=1;j=0;if(distanceend<MaxValue&&distanceend>0) /兩個站點(diǎn)有公交車cout<<" 到達(dá)"<<v1<<"共有"<<distanceend<<"站，最優(yōu)方案為:"<<endl;do /對路徑上的站點(diǎn)入棧stack1.Push(statenameend);end=pathend;while(end!=

33、start);stack1.Pop(a); /出棧number1=searchbusnumber(v0,a); /查找兩個站點(diǎn)的公交車號碼cout<<" 乘坐"<<number1;direction(v0,a); /查找兩站的公交方向cout<<v0<<"->"<<a;while(!stack1.IsEmpty() /判斷棧是否為空stack1.Pop(b); number2=searchbusnumber(a,b); /查找下兩個站間的公交車號碼if(number1=number2) /

34、判斷兩個車是否是同一輛cout<<"->"<<b;i+;else /不是同一輛，則換車if(i=1)cout<<" 僅有一站，建議步行"<<b<<endl;elsecout<<" 共"<<i<<"站"<<endl;cout<<" 換乘" <<number2; /輸出換車信息direction(a,b);number1=number2;cout<<a

35、<<"->"<<b;i=1;j+;strcpy(a,b); /保留前一站if(i=1)cout<<" 僅有一站，建議步行至"<<b<<endl;elsecout<<" 共"<<i<<"站"<<endl;if(j>0)cout<<" 共換車"<<j<<"次，"<<"請注意換車的站點(diǎn)!"<

36、<endl;elseif(distanceend=0)cout<<"您所在站點(diǎn)即為"<<v0<<endl;elsecout<<"從"<<v0<<"至"<<v1<<"無公交可到!"<<endl;void bestproject() /最優(yōu)方案Distance bestway;char start20,end20;cout<<"請輸入起點(diǎn)站:" /接收起點(diǎn)站和終點(diǎn)站cin&g

37、t;>start;cout<<"請輸入終點(diǎn)站:"cin>>end;cout<<endl;bestway.bestchooce(start,end);mainsurface();void mainsurface() /主界面int flag;cout<<" 歡迎使用公交咨詢系統(tǒng)"<<endl; /用戶會話界面cout<<" 1.公交線路查詢"<<endl;cout<<" 2.站點(diǎn)查詢"<<endl;cout<<" 3.最優(yōu)乘車方案查詢"<<endl;cout<<" 4.退出系統(tǒng)"<<endl;cout<<"請輸入您要選擇的服務(wù):"cin>>flag;cout<<endl;switch(flag)case 1:busline();break; /公交線路case 2:searchstate();break; /站點(diǎn)查詢case 3:bestproject();break; /最優(yōu)方案case 4:default: cout<<"謝