數(shù)據(jù)結(jié)構(gòu)公交線路換乘

1、數(shù)據(jù)結(jié)構(gòu)公交線路換乘#include<fstream.h>/ 文件庫#include<stdlib.h>#include<string.h>/ 字符串函數(shù)庫const int Maxbus=100;/ 最大公交車數(shù)const int Maxstate=200;/ 最大站點(diǎn)數(shù)const int MaxValue=999;/ 最大值struct Bus / 公交車類int number; / 公交車號(hào)int length; / 總站數(shù)char bus_stateMaxstate20; / 站點(diǎn);class Grap

2、h / 建立無向圖friend class Distance; / 聲明友元類private:char statenameMaxstate20; / 站點(diǎn)int busnumberMaxstateMaxstate; / 鄰接矩陣，權(quán)值為這兩個(gè)站點(diǎn)的公交車號(hào)int currentstate;/ 當(dāng)前站點(diǎn)數(shù)int currentbus;/ 當(dāng)前公交車數(shù)Bus busesMaxbus; / 公交車信息public:Graph() / 無參構(gòu)造函數(shù)，對成員變量初始化for(int i=0;i<Maxstate;i+)for(int j=0;j<Maxstate;j+)if(

3、i=j)busnumberij=-1; / 自己到自己沒有車elsebusnumberij=MaxValue;currentstate=0;/ 站點(diǎn)數(shù)初始化為0currentbus=0;/ 公交車數(shù)初始化為0for(i=0;i<Maxbus;i+)busesi.number=-1;busesi.length=0;void Insertstate(char state) / 插入一個(gè)站點(diǎn)if(!IsGraphFull() /如果圖沒滿for(int i=0;i<currentstate;i+) / 查看該站是否已經(jīng)存在if(strcmp(state,statename

4、i)=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 Insertbusnumber(char V1,char V2,int busnum) / 插入權(quán)值for(int

5、 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() / 圖的建立char ch700,a20='0'

6、/int j=0,k=0,i;ifstream infile(" 公交查詢.txt"); / 以讀的方式打開文件if(!infile) /文件打開失敗，則結(jié)束程序cout<<"Cant't open ' 公 交 查詢 .txt'"<<endl;exit(0);while(!infile.eof()&&currentbus<Maxbus) / 文件沒有讀完infile&

7、gt;>busescurrentbus.number; / 接收車號(hào)碼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; str

8、cpy(busescurrentbus.bus_statek+,a);Insertstate(a);busescurrentbus.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.numb er);bool IsGraphFull() / 判斷圖是否已滿return cu

9、rrentstate=Maxstate;void show_busmessage(int number) / 輸出公交信息for(int i=0;i<currentbus;i+) / 查找權(quán)值if(busesi.number=number) break;if(i=currentbus)cout<<" 查無此車!"<<endl;else/ 找到，輸出該公交車信息cout<<""<<number&

10、;lt;<" 路( "<<busesi.bus_state0<<"<->"<<busesi.bus_statebusesi.length-1<<" ) "<<endl;for(int j=0;j<busesi.length-1;j+)cout<<busesi.bus_

11、statej<<"<->"cout<<busesi.bus_statej<<endl;int searchbusnumber(char v0,char v1)/ 查找指定站點(diǎn)的公交車號(hào)碼int i,j,numb;for(int k=0;k<currentstate;k+) / 查找站點(diǎn)if(strcmp(v0,statenamek)=0)i=k;if(strcmp(v1,statenamek)=0)j=k;numb=busnumber

12、ij; / 在鄰接矩陣中查找權(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.number)break;for(k=0;k<

13、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<&lt

14、;" ) "<<endl;elsecout<<"( "<<busesl.bus_state0<<"<-"<<busesl.bus_statebusesl.length-1<<" ) "<<endl;friend void busline();/把

15、外部函數(shù)定義為圖的友元函數(shù)，以便使用圖的私有成員變量friend void searchstate();friend void bestproject();friend void mainsurface();class StackNode / 棧結(jié)點(diǎn)friend 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):link(l)strcpy(date,d);class Stack / 定義棧pri

16、vate: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 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

17、 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)棧StackNode *p =new StackNode ( item, top );/ 新結(jié)點(diǎn) p->link=top; / 鏈入 *top 之前 top = p; / 成為新棧頂 int Stack :Pop (char x ) /退棧if ( IsEmpty ( ) ) return 0;Stac

18、kNode *p = top;top = top->link; / 修改棧頂指針 strcpy(x,p->date); / 送回退棧元素delete p;return 1; / 釋放int Stack:GetTop (char x )/讀取棧頂元素if (IsEmpty() return 0;strcpy(x,top->date); /送回棧頂元素return 1; / 釋放class Distance:public Graph / 定義最短距離類private:char path20;/ 最短距離的前一站int distanceMaxstate; /

19、 最短距離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<currentstate;i+) / 查找起始站、終點(diǎn)站if(strcmp(statenamei,v0)=0)start=i;if(strcmp(statenamei,v1)=0)end=i;if(start=-1|end=-1)cout<&a

20、mp;lt;" 站點(diǎn)不存在!"<<endl;return ;for( i=0;i<currentstate;i+) / 初始化距離、前一站si=0;/s 集合賦空if(busnumberstarti<MaxValue)distancei=1;pathi=start;elsedistancei=busnumberstarti; / 權(quán)值賦給最短距離pathi=-1;sstart=1; / 起始站放入s 集合distancestart=0;int min;for(i=0;i<currentst

21、ate;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<MaxValue) /計(jì)算起點(diǎn)到每個(gè)站點(diǎn)的距離distancej=min+1;pathj=

22、v;i=1;/ 兩個(gè)站j=0;if(distanceend<MaxValue&&distanceend>0)點(diǎn)有公交車cout<<"到 達(dá) "<<v1<<" 共 有"<<distanceend<<" 站 ， 最 優(yōu) 方 案 為 :"<<endl;do / 對路徑上

23、的站點(diǎn)入棧stack1.Push(statenameend);end=pathend;while(end!=start);stack1.Pop(a); / 出棧number1=searchbusnumber(v0,a); / 查找兩個(gè)站點(diǎn)的公交車號(hào)碼cout<<" 乘坐 "<<number1;direction(v0,a);/ 查找兩站的公交方向cout<<v0<<"->"<&

24、lt;a;while(!stack1.IsEmpty() / 判斷棧是否為空stack1.Pop(b);number2=searchbusnumber(a,b); / 查找下兩個(gè)站間的公交車號(hào)碼if(number1=number2)/ 判斷兩個(gè)車是否是同cout<<"->"<<b;i+;else / 不是同一輛，則換車if(i=1)cout<<" 僅有一站，建議步行"<<b<&

25、lt;endl;elsecout<<" 共 "<<i<<" 站 "<<endl;cout<<" 換乘 " <<number2; / 輸出換車信息direction(a,b);number1=number2;cout<<a<<"->&am

26、p;quot;<<b;i=1;j+;strcpy(a,b); /保留前一站if(i=1)cout<<" 僅有一站，建議步行至"<<b<<endl;elsecout<<" 共 "<<i<<" 站 "<<endl;if(j>0)cout<&am

27、p;lt;" 共 換 車 "<<j<<" 次 ，"<<" 請注意換車的站點(diǎn)!"<<endl;elseif(distanceend=0)cout<<" 您所在站點(diǎn)即為"<<v0<<endl;elsecout<<"從&

28、amp;quot;<<v0<<"至"<<v1<<" 無公交可到!"<<endl;void bestproject() / 最優(yōu)方案Distance bestway;char start20,end20;cout<<" 請輸入起點(diǎn)站:"cin>>start;cout<<

29、" 請輸入終點(diǎn)站:"cin>>end;cout<<endl;bestway.bestchooce(start,end);void mainsurface() / 主界面int flag;cout<<""<<endl; / 用戶會(huì)話界面cout<<""<<endl;cout<<"

30、cout<<""<<endl;cout<<"cout<<" 請輸入您要選擇的服務(wù)cin>>flag;/ 接收起點(diǎn)站和終點(diǎn)站歡迎使用公交咨詢系統(tǒng)1.公 交 線 路 查 詢2.站點(diǎn)查詢"<<endl;3. 最 優(yōu) 乘 車 方 案 查 詢4.退出系統(tǒng)"<<endl;:"cout&am

31、p;lt;<endl;switch(flag)case 1:busline();mainsurface();break; / 公交線路case 2:searchstate();mainsurface();break; / 站點(diǎn)查詢case 3:bestproject();mainsurface();break; / 最優(yōu)方案case 4:default:cout<<" 謝謝使用!"<<endl;void busline() / 公交線路int flag, a=0,i;Graph map; / 建立圖map.Set_graph();cout<<"公交線路查詢"<<endl;cout<<"1.確定車號(hào)的公交查詢"<<endl;cout<<"2.已有所有公交線路瀏覽"<<endl;cout<<"3.返回首頁"