数据结构课程设计说明书--公交乘车

1、精选优质文档-倾情为你奉上数据结构与算法设计课程设计任务书题 目公交咨询程序学生姓名孙宝琳学号0124专业班级数学0701设计内容与要求【问题描述】 利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1 从文件中接收图和公交车信息；2 可实现确定公交线路查询，即输出该车的所有站点；3 可以对某一个站点进行查询输出该站点的所有下一站；4 可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】设计公交车类（车号，路程长度，终点站）、图类（站点名，公交车类，现有路线条数，现有站点数）、Dijkstra算法类（最短路径上

2、的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线，并有最短路径的最后一个站点将路径上的所有站点入栈，出站时判断是否换车并输出方案；【提交成果】1.“数据结构与算法设计课程设计任务书”一份，打印装袋；2.“数据结构与算法设计课程设计报告”一份，打印装袋；3、上面两项内容的word文档，通过电子邮件交到指导教师。起止时间2009 年 6 月 8 日 至 2009 年6月 19 日指导教师签名年 月 日系（教研室）主任签名年 月 日学生签名孙宝琳 2009年 6

3、月18 日数据结构与算法设计课程设计专业 数学与应用数学 班级 数学0701 学号 0124 姓名 孙宝琳 完成日期 6.18 指导教师（签名）1、 程序设计说明书【设计题目】公交咨询程序【问题描述】利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。【软件功能】1 从文件中接收图和公交车信息；2 可实现确定公交线路查询，即输出该车的所有站点；3 可以对某一个站点进行查询输出该站点的所有下一站；4 可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】 设计公交车类（车号，路程长度，终点站），图类（站点名，公交车类，现有路线条

4、数，现有站点数），Dijkstra算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线并有最短路径的最后一个站点输出乘车方案；【类的设计】 struct Bus /公交车类int number; /公交车号int length; /总站数char bus_stateMaxstate20; /站点;class Graph /建立无向图friend class Distance; /声明友元类private:char statenameMaxst

5、ate20; /站点int busnumberMaxstateMaxstate; /邻接矩阵，权值为这两个站点的公交车号int currentstate; /当前站点数int currentbus; /当前公交车数Bus busesMaxbus; /公交车信息public:Graph() ； /无参构造函数，对成员变量初始化 void Insertstate(char state)；/插入一个站点void Insertbusnumber(char V1,char V2,int busnum) ；/插入权值void Set_graph() ； /图的建立bool IsGraphFull() ；

6、/判断图是否已满void show_busmessage(int number)； /输出公交信息int searchbusnumber(char v0,char v1) ； /查找指定站点的公交车号码void direction(char v0,char v1) ； /输出指定站点的公交车方向friend void busline(); /把外部函数定义为图的友元函数，以便使用图的私有成员变量friend void searchstate();friend void bestproject();friend void mainsurface();class StackNode /栈结点fri

7、end class Stack; /友元类private: char date20; /结点数据StackNode *link; /结点链指针public:/构造函数：结点赋值StackNode (char d =0,StackNode *l =NULL)；;class Stack /定义栈private:StackNode *top; /栈顶指针public:Stack ( ) :top(NULL) /构造函数Stack ( ); /析构void Push(char item); /进栈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)； /最优方案；【存储结构设计】 使用邻接矩阵int busnumberMaxstateMaxstate;存储图的信息；公交车信息采用结构体数组Bus busesMaxbus;存储；栈使用链表来实现；【模块划分及调用关系】Main（） Mainsurface()退出Sea

9、rchstate()Bestproject()Busline()共有三个模块：公交线路查询Busline()、站点查询Searchstate()、最优方案Bestproject()【模块流程图】1. Busline():Mainsurface()Set_graph() 所有路线浏览特定车号的路线查询循环输出当前车接收车号 存在 存 存在 输出公交车信息show_busmessage()2 searchstate():Set_graph() 否 接收站点Mainsurface()在图内查找有站点名所到的车及方向3 bestproject(): 无路径 有路径 栈为 是 车相同 接收起始站Best

10、chooce()Set_graph()Dijkstra算法Mainsurface()对路径上的站入栈出栈判断是否是换车输出换车信息输出路径Mainsurface()【界面设计】 采用简单的人机会话，使操作简单明了；【用户手册】 在程序所在文件夹下建立“公交查询.txt”，并输入以下内容： 30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方

11、新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;（每一个车的线路占一行）； 编译运行程序，根据提示执行程序；要想有更为准确的方案，可以在“公交查询.txt”中加入公交车线路；2、 程序上机调试报告【语法错误及其排除】1 函数赋值时，将变量赋给了指针； 使用指针传值；2 在出栈时没有判断栈是否为空，导致top指空 在出栈前判断IsEmpty（）；【算法错误及其排除】1 在建立图中没有对a数组进行置空，导致数据混乱；在使用a之前对a数组赋空；2 在输出最优结果时 没有保留前一站使程序无法判断是否换车加入b数组保留前一站；3、 程序测试结果【测试数据】30世家星城-通讯学院-石油公寓-潘

12、家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;（每一个车的线路占一行）；【输出结果】1公交线路查询： 2 站点查询：3 最优方案：【程序性能评价】 使用简单；结果正确、明了；【性能改进方向】1. 将邻接矩阵改为三维，即在相同两站间由多个公交可以到达；2. 在站点里加入方位，即在寻找最优结果的时候可以不必将所有站

13、点进行操作，加快运行速度；3. 在公交车类中加入收费，在最优结果输出时计算收费(有刷卡、投币、按站收费)；【收获及体会】 通过这个程序的编写使我对c+中文件的操作、图的操作、栈的操作、查找等内容有了更深的理解，在编译的过程中也是我知道了自己的数据结构课程内容还很浅，还需要在努力；4、 源程序代码#include<fstream.h>/文件库#include<stdlib.h>#include<string.h>/字符串函数库const int Maxbus=100;/最大公交车数const int Maxstate=200;/最大站点数const int M

14、axValue=999;/最大值struct Bus /公交车类int number; /公交车号int length; /总站数char bus_stateMaxstate20; /站点;class Graph /建立无向图friend class Distance; /声明友元类private:char statenameMaxstate20; /站点int busnumberMaxstateMaxstate; /邻接矩阵，权值为这两个站点的公交车号int currentstate; /当前站点数int currentbus; /当前公交车数Bus busesMaxbus; /公交车信息p

15、ublic:Graph() /无参构造函数，对成员变量初始化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) /插入一个站点if(!IsGraphFull() /如果图没满for(int i=

16、0;i<currentstate;i+) /查看该站是否已经存在if(strcmp(state,statenamei)=0)break;if(i=currentstate) /如果不存在，在站点数组后加入strcpy(statenamecurrentstate,state);for(i=0;i<currentstate;i+)busnumbercurrentstatei=MaxValue;busnumbericurrentstate=MaxValue;busnumbercurrentstatecurrentstate=-1;currentstate+; /当前数组加一void In

17、sertbusnumber(char V1,char V2,int busnum) /插入权值for(int i=0;i<currentstate;i+) /查找站点if(strcmp(V1,statenamei)=0)break;for(int j=0;j<currentstate;j+)if(strcmp(V2,statenamej)=0)break;if(i!=currentstate&&j!=currentstate) /站点存在插入权值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数组初始化ai='0'ifstream infile("公交查询.txt"); /以读的方式打开文件if(!infile) /文件打开失败，则结束程序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!='-') /把站点暂存在a中aj+=chi;elsestrcpy(busescurrentbus.bus_statek+,a); /对公交车站点赋值Insertstate(a); /插入站点for(j=0;j<20;j+)aj='0' /对a数组初始化j=0;strcpy(busescurrentbus.bus_statek+,a);Insertstate(a);b

20、usescurrentbus.length=k; /当前公交车长度赋值currentbus+; /当前公交车数加一k=0;j=0;for(i=0;i<currentbus;i+)for(k=0;k<busesi.length-1;k+) /插入权值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+) /查找权值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) /查找指定站点的公交车号码int i,j,numb;for(int k=0;k<currentstate;k+) /查找站点if(strcmp(v0,statenamek)=0)i=k;if(strcm

23、p(v1,statenamek)=0)j=k;numb=busnumberij; /在邻接矩阵中查找权值return numb;void direction(char v0,char v1) /输出指定站点的公交车方向int i,j,numb,l;for(int k=0;k<currentstate;k+) /查找指定站点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(); /把外部函数定义为图的友元函数，以便使用图的私有成员变量friend void searchstate();friend void bestproject();friend void mainsurface();class StackNode /栈结点friend class Sta

26、ck; /友元类private: char date20; /结点数据StackNode *link; /结点链指针public:/构造函数：结点赋值StackNode (char d =0,StackNode *l =NULL):link(l)strcpy(date,d); class Stack /定义栈private:StackNode *top; /栈顶指针public:Stack ( ) :top(NULL) /构造函数Stack ( ); /析构void Push(char item); /进栈int Pop(char x);/退栈int GetTop(char x); /读取栈顶

27、元素void MakeEmpty (); /把栈置空int IsEmpty() return top = NULL; Stack :Stack()StackNode *p;while(top != NULL) /逐结点回收p=top; top=top->link; delete p; /释放栈顶结点void Stack :MakeEmpty ()/把栈置空 StackNode *p;while (top != NULL) /逐结点回收p=top; top=top->link; delete p; /释放栈顶结点void Stack:Push(char item )/进栈 Stack

28、Node *p =new StackNode ( item, top );/新结点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) /最优方案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+) / 查找起始站、终点站if(strcmp(statenamei,v0)=0) start=i;if(strcmp(statenamei,v1)=0)end=i;if(start=-1|end=-1)cout<<"站点不存在!"<<endl;bestproject();for( i=0;i<currentstate;i+) /初始化距离、前一站si=0; /s集合赋空if(busnumberstarti<MaxValue)distancei=1;pathi=start;elsedistancei=busnumberst

31、arti; /权值赋给最短距离pathi=-1;sstart=1; /起始站放入s集合distancestart=0;int min;for(i=0;i<currentstate;i+)min=MaxValue;for(w=0;w<currentstate;w+) /在邻近的顶点中查找最短距离if(!sw&&distancew<min)v=w;min=distancew; sv=1; for(j=0;j<currentstate;j+)if(!sj&&(min+1)<distancej&&busnumbervj<

32、;MaxValue) /计算起点到每个站点的距离distancej=min+1;pathj=v;i=1;j=0;if(distanceend<MaxValue&&distanceend>0) /两个站点有公交车cout<<" 到达"<<v1<<"共有"<<distanceend<<"站，最优方案为:"<<endl;do /对路径上的站点入栈stack1.Push(statenameend);end=pathend;while(end!=

33、start);stack1.Pop(a); /出栈number1=searchbusnumber(v0,a); /查找两个站点的公交车号码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<<"次，"<<"请注意换车的站点!"<

36、<endl;elseif(distanceend=0)cout<<"您所在站点即为"<<v0<<endl;elsecout<<"从"<<v0<<"至"<<v1<<"无公交可到!"<<endl;void bestproject() /最优方案Distance bestway;char start20,end20;cout<<"请输入起点站:" /接收起点站和终点站cin&g

37、t;>start;cout<<"请输入终点站:"cin>>end;cout<<endl;bestway.bestchooce(start,end);mainsurface();void mainsurface() /主界面int flag;cout<<" 欢迎使用公交咨询系统"<<endl; /用户会话界面cout<<" 1.公交线路查询"<<endl;cout<<" 2.站点查询"<<endl;cout<<" 3.最优乘车方案查询"<<endl;cout<<" 4.退出系统"<<endl;cout<<"请输入您要选择的服务:"cin>>flag;cout<<endl;switch(flag)case 1:busline();break; /公交线路case 2:searchstate();break; /站点查询case 3:bestproject();break; /最优方案case 4:default: cout<<"谢