数据结构课程设计全国交通模拟汇总.docx
《数据结构课程设计全国交通模拟汇总.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计全国交通模拟汇总.docx(43页珍藏版)》请在冰点文库上搜索。
![数据结构课程设计全国交通模拟汇总.docx](https://file1.bingdoc.com/fileroot1/2023-6/11/10e15ca1-e978-4b7c-a5a4-4af2539aa81b/10e15ca1-e978-4b7c-a5a4-4af2539aa81b1.gif)
数据结构课程设计全国交通模拟汇总
数据结构
课程设计报告
班级:
191113
学号:
20111000611
姓名:
黄建钊
指导老师:
朱晓莲
日期:
2013年3月
7.全国交通咨询模拟
出于不同目的的旅客对交通工具有不同的要求。
例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少。
编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。
要求:
(1)提供对城市信息进行编辑(如添加或删除)的功能。
(2)城市之间有两种交通工具:
火车和飞机。
提供对列车时刻表和飞机航班进行编辑(增设或删除)的功能。
(3)提供两种最优决策:
最快到达或最省钱到达。
全程只考虑一种交通工具。
(4)旅途中耗费的总时间应该包括中转站的等候时间。
(5)咨询以用户和计算机的对话方式进行。
1.需求分析
1、设计最短路径的算法及其需要信息的存储:
本设计中最短路径的算法利用迪杰斯特拉算法,存储方法利用邻接矩阵存储。
2、该程序所做的工作的是模拟全国交通咨询,为旅客提供种最优决策的交通咨询。
此程序规定:
在程序中输入城市名称时,需输入10个字母以内的字母串;输入列车或飞机编号时需输入一个字符串类型;输入列车或飞机的费用时需输入一个实型数据;输入列车或飞机开始时间和到达时间时均需输入一个整型数据,在选择功能时,应输入与所选功能对应的一个整型数据。
程序的输出信息主要是:
最快需要多少时间才能到达,或最少需要多少旅费才能到达,说明在途中经过的城市名称;
程序的功能包括:
提供对城市信息的编辑,提供列车时刻表和飞机航班表的编辑,提供两种最优决策:
最快到达、最省钱到达。
2.设计
2.1设计思想
本系统整体上分为存储系统和求最短路径两部分,存储系统运用到数组和结构体。
该系统分别存储火车列次,航班,出发点与目的地以及所需要走的路程和所用费用。
最短路径使用迪杰斯特拉算法编程求算得出最近或最便宜路径。
该算法主要分为三步:
1、起始点(V0)与其相邻点的权值(即当前最短路径)。
2、求出当前最短路径中的最小值即是该起始点(V0)与另一点(Vi)的最短路径。
3、V0到Vi的距离加上Vi到Vj的距离小于V0到Vj则将V0到Vi的距离加上Vi到Vj的距离记为V0到Vj当前最短路径,循环第二、三步。
如此得到V0到各点的最短路径,进而可以得到想要的一条。
(1)数据结构设计:
structTra//火车或飞机的存储结构
{
charcc[20];//用"车次"的前两个字母表示火车或飞机航班的代码
charstart[20];//出发点
chardestination[20];//目的地
floattime;//路途时间
floatprice;//价钱
};
(2)算法设计
A,本设计采用的数据结构有图中的最短路径。
(1)、开始-----
(2)、得到存储最少花费或最短时间信息的邻接矩阵------
(3)、得到起始点与相邻的点的权值(即当前最短路径)并记录点-----
(4)、求出当前最短路径中的最小值即是该起始点(V0)与另一点(Vi)的最短路径-----
(5)、V0到Vi的距离加上Vi到Vj的距离小于V0到Vj则将V0到Vi的距离加上Vi到Vj的距离记为V0到Vj当前最短路径并且记录前一个点。
(6)、重复(4),(5)步得到所有点最短路径。
(7)、以终点开始逐步向前赋值得到所需路径并输出该路径的权值。
代码:
voidshort_path(structTra*timetable,char*start,char*dest,charcity[][20],inttn,intcn,intchoice)
{
inti,j,k,st,et;
floatmin,t;
charpcity[10][20];
floatedge[15][15],dist[15];
intpath[15],s[15];
for(i=0;ifor(j=0;j{
edge[i][j]=max;
}
for(i=0;ij=search(city,timetable[i].start,cn);
k=search(city,timetable[i].destination,cn);
if(choice==0)
{t=timetable[i].time;
if(t}
else
{t=timetable[i].price;
if(t}
}
st=search(city,start,cn);
et=search(city,dest,cn);
for(i=0;idist[i]=edge[st][i];
s[i]=0;
if(i!
=st&&dist[i]elsepath[i]=-1;
}
s[st]=1;dist[st]=0;
for(i=0;imin=max;
k=st;
for(j=0;jif(!
s[j]&&dist[j]{k=j;min=dist[j];}
s[k]=1;
for(j=0;jif(!
s[j]&&edge[k][j]dist[j]=dist[k]+edge[k][j];path[j]=k;
}
}
k=et;
i=0;
if(path[k]==-1){
printf("\t\t对不起,不存在从%s到%s的路线\n\n",start,dest);
return;
}
while(path[k]!
=-1)
{
strcpy(pcity[i++],city[k]);
k=path[k];
}
strcpy(pcity[i++],city[st]);
printf("\t\t最佳路线为:
\n\t\t");
for(j=i-1;j>=0;j--)
printf("%s",pcity[j]);
printf("\n");
if(choice==0)printf("\t\t所需总时间为:
%5.1f小时\n",dist[et]);
elseprintf("\t\t所需的总费用为:
%7.2f元\n",dist[et]);
printf("\n");
}
B,界面以及主函数功能板块
本设计采用的是在界面上通过输入相应的字符表示的要求来实现对于不同目的不同函数的调用,主要用到的数据结构有图中的交通网的各种信息的邻接矩阵的存储。
通过顾客输入不同的字符来实现不同的功能,主界面上注释着这个程序的系统名称,组员以及指导老师等基本学生信息,用星号来加以修饰;然后就是用一个swich语句来实现多功能的选取以及程序的退出;主要有一:
1:
修改地图2:
编辑火车时刻表\t3:
编辑飞机航班表\t4:
选择出游路线t5:
退出;继而通过选中其中的数字来实现自己的目的;然后再引用程序再用一个switchcase语句来实现123选项中的添加删除以及退出功能,然后在4中再用if语句来实现自己的需求考虑。
可以随时退出程序。
最后再经调用函数再来输出结果;
代码:
#include
#include
#include
constfloatmax=FLT_MAX;
};voidmain()
{
inti,j,k,m,n,cn=5,tn=6,fn=6;
printf("\t\t******************************************\n");
printf("\t\t******************************************\n");
loop1:
printf("\t请选择所需功能:
\n\t\t1:
修改地图\n\t\t2:
编辑火车时刻表\n\t\t3:
编辑飞机航班表\n\t\t4:
选择出游路线\n\t\t5:
退出");
switch(i)//switch语句
{
case1:
{//第一种情况,修改地图*****
while(j!
=1&&j!
=2&&j!
=3)
{
case2:
{//修改火车时间表
case3:
{//修改飞机航班表,和列车相似
case4:
{
printf("\t\t请选择交通工具(1.火车2.飞机):
");
scanf("%d",&j);
printf("\n");
if(j==1&&k==1)short_path(train,city[m-1],city[n-1],city,6,5,0);
if(j==1&&k==2)short_path(train,city[m-1],city[n-1],city,6,5,1);
if(j==2&&k==1)short_path(flight,city[m-1],city[n-1],city,6,5,0);
if(j==2&&k==2)short_path(flight,city[m-1],city[n-1],city,6,5,1);
gotoloop1;//回到主菜单
case5:
return;//退出系统}
2.2设计表示
函数调用关系图
Main()
short_path()
Search()
各模块调用关系
主菜单
修改地图编辑火车时刻表编辑飞机航班表选择出游路线退出
修改地图
增加城市删除城市返回
编辑火车时刻表
添加删除返回
编辑飞机航班表
添加删除返回
选择出游路线
飞机火车
最短时间最少花费最短时间最少花费
2.3详细设计
voidmain()
{
inti,j,k,m,n,cn=5,tn=6,fn=6;
printf("\t\t************************************************\n");
printf("\t\t********欢迎使用全国交通咨询模拟********\n");
printf("\t\t********黄建钊********\n");
printf("\t\t********191113********\n");
printf("\t\t********20111000611********\n");
printf("\t\t********计算机学院********\n");
printf("\t\t********指导老师:
朱晓莲********\n");
printf("\t\t************************************************\n");
charcity[15][20]={"深圳","成都","南昌","杭州","北京"};//现有城市,最多15个城市
structTratrain[20]={
{"T1","杭州","深圳",10,190},
{"T2","北京","深圳",18,270},
{"T3","北京","南昌",13,150},
{"T4","北京","成都",25,300},
{"T5","北京","杭州",14,160},
{"T6","南昌","杭州",11,200}
};
structTraflight[20]={
{"F1","杭州","北京",3,1500},
{"F2","深圳","北京",2.5,1300},
{"F3","北京","成都",1,600},
{"F4","南昌","北京",3,1400},
{"F5","深圳","南昌",1,700},
{"F6","成都","杭州",3,1650}
};
printf("\t\t现有城市");//输出现有地图上的城市,便于后面的输入和修改
for(j=0;jprintf("%d.%s\t",j+1,city[j]);
printf("\n\n");
loop1:
printf("\t请选择所需功能:
\n\t\t1:
修改地图\n\t\t2:
编辑火车时刻表\n\t\t3:
编辑飞机航班表\n\t\t4:
选择出游路线\n\t\t5:
退出");
printf("\n\t请选择:
");
scanf("%d",&i);
while(i!
=1&&i!
=2&&i!
=3&&i!
=4&&i!
=5)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&i);
}//避免按错而导致程序错误
switch(i)//switch语句
{
case1:
{//第一种情况,修改地图
loop2:
printf("\t现有城市:
\n\t\t");
for(j=0;jprintf("%d.%s\t",j+1,city[j]);
printf("\n\n");
printf("\t\t功能:
\n\t\t1:
添加2:
删除3:
返回\n");
printf("\t\t请选择:
");
scanf("%d",&j);
while(j!
=1&&j!
=2&&j!
=3)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&j);
}//避免按错而导致程序错误
printf("\n");
if(j==1)
{
printf("\t请输入城市名:
");
scanf("%s",city[cn]);
cn++;
gotoloop2;
}//if语句
if(j==2)
{printf("\t请选择要删除的城市的编号:
");
scanf("%d",&k);
while(k>cn||k<1)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&k);
}//避免按错而导致程序错误
if(k==cn)cn--;
else{
for(m=k-1;mstrcpy(city[m],city[m+1]);//k后面的城市依次往前移一位
cn--;//城市总数减少一个
}
gotoloop2;//查看修改后的地图,便于判断或是再次修改
}
elsegotoloop1;//回到主菜单
}
case2:
{//修改火车时间表
loop3:
printf("\n\t\t现有火车时刻表:
\n");
printf("\t\t车次起点站终点站路途时间(h)票价(元)\n");//输出各火车时刻表
for(j=0;jprintf("\t\t%d:
%s\t%s\t%s\t%5.1f\t\t%5.2f\t\n",j+1,train[j].cc,train[j].start,train[j].destination,train[j].time,train[j].price);
printf("\n\n");
printf("\t功能:
1.添加\t2.删除\t3.返回\n");
printf("\t请选择:
");
scanf("%d",&j);
while(j!
=1&&j!
=2&&j!
=3)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&j);
}//避免按错而导致程序错误
printf("\n");
if(j==1)
{
printf("现有城市:
\n");
for(k=0;kprintf("%d.%s\t",k+1,city[k]);
printf("\n");
printf("请输入数据:
\n");
printf("火车时刻表:
\n");
printf("车次起点站终点站路途时间(h)票价(元)\n");
scanf("%s%s%s%f%f",train[tn].cc,train[tn].start,train[tn].destination,&train[tn].time,&train[tn].price);
tn++;//火车车次加一
gotoloop3;//回到loop3,查看修改后的列车信息
}
elseif(j==2)
{
printf("\t请选择所需删除车次编号:
");
scanf("%d",&k);
while(k>tn||k<1)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&k);
}//避免按错而导致程序错误
if(k==tn)tn--;//火车车次减一
else{
for(m=k-1;mtrain[m]=train[m+1];
tn--;
}
gotoloop3;//回到loop3,查看修改后的列车信息
}
elsegotoloop1;//回到主菜单
}
case3:
{//修改飞机航班表,和列车相似
loop4:
printf("\t\t现有飞机航班表:
\n");
printf("\t\t班次起点终点路途时间(h)票价(元)\n");
for(j=0;jprintf("\t\t%d:
%s\t%s\t%s\t%5.1f\t\t%5.2f\t\n",j+1,flight[j].cc,flight[j].start,flight[j].destination,
flight[j].time,flight[j].price);
printf("\n\n");
printf("\t\t功能:
1.添加\t2.删除\t3.返回\n");
printf("\t\t请选择:
");
scanf("%d",&j);
while(j!
=1&&j!
=2&&j!
=3)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&j);
}//避免按错而导致程序错误
printf("\n");
if(j==1){
printf("现有城市:
\n");
for(k=0;kprintf("%d.%s\t",k+1,city[k]);
printf("\n");
printf("请输入数据:
\n");
printf("车次\t起点站\t终点站\t路途时间(h)\t票价(元)\n");
scanf("%s%s%s%f%f",flight[fn].cc,flight[fn].start,flight[fn].destination,&flight[fn].time,&flight[fn].price);
fn++;
gotoloop4;
}
elseif(j==2)
{
printf("\t\t请选择所要删除的编号:
");
scanf("%d",&k);
while(k>fn||k<1)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&k);
}//避免按错而导致程序错误
if(k==fn)fn--;
else{
for(m=k-1;mflight[m]=flight[m+1];
fn--;
}
gotoloop4;
}
elsegotoloop1;//回到主菜单
}
case4:
{
printf("\t\t请选择交通工具(1.火车2.飞机):
");
scanf("%d",&j);
while(j!
=1&&j!
=2)
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&j);
}//避免按错而导致程序错误
printf("\t\t请选择决策方案(1.最短时间2.最少花费):
");
scanf("%d",&k);
while(k!
=1&&k!
=2)
{printf("\t\t输入有误,请重新输入:
");
scanf("%d",&k);
}//避免按错而导致程序错误
printf("\t现有城市:
\n");
for(i=0;iprintf("\t\t%d.%s\n",i+1,city[i]);
printf("\n");
printf("\t\t出发地编号:
");
scanf("%d",&m);
while(m>cn||m<1)//cn为现有城市数目
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&m);
}//避免按错而导致程序错误
printf("\t\t目的地编号:
");
scanf("%d",&n);
while(n>cn||n<1)//cn为现有城市数目
{
printf("\t\t输入有误,请重新输入:
");
scanf("%d",&n);
}//避免按错而导致程序错误
printf("\n");
if(j==1&&k==1)short_path(train,city[m-1],city[n-1],city,6,5,0);
if(j==1&&k==2)short_path(train,city[m-1],city[n-1],city,6,5,1);
if(j==2&&k==1)short_path(flight,city[m-1],city[n-1],city,6,5,0);
if(j==2&&k==2)short_path(flight,city[m-1],city[n-1],city,6,5,1);
gotoloop1;//回到主菜单
}
case5:
return;//退出系统
}
}
voidsh