c语言公交最优路径查询数据结构

《数据结构》

课程设计说明一、课程设计的基本要求根据上述公交线路的输入格式，定义并建立合适的图模型。针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路X：站名S，…，站名M1；换乘线路X：站名M1，…，站名M2；…；换乘线路X：站名MK，…，站名T。共花费x元。针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为:线路X：站名S，…，站名M1；换乘线路X：站名M1，…，站名M2；…；换乘线路X：站名MK，…，站名T。共花费X时间。针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为:线路X：站名S，…，站名M1；换乘线路X：站名M1，…，站名M2；…；换乘线路X：站名MK，…，站名T。共花费X时间。二、课程设计的主要内容（包含分工）主要内容：首先将多有要用到的结构体全部定义完全，在课程设计的进程安排2010年01月10日之前：完成所有要用到的结构体的定义。2010年01月11日——01月12日：完成建立合适的图模型以及信息的初始化。2010年01月15日前：将初始化的所有的信息与建立的图模型完全连接起来，写调整函数将每一条路线的车的信息存放到所有的节点里去。2010年1月16日——2010年1月18日：完成按时间和价格的最优的方法选择路线。2010年1月19日——2010年1月20日：完成所有的程序。2010年1月21日答辩具体分工：XX（组长）：①，定义所有将要用到的结构体，编写函数实现根据公交路线信息修改站点信息的功能，利用Floyd算法找出按时间的所有两站之间的最优路径，编写时间最优的路线选择（不考虑等待时间），编写时间最优的路线选择（考虑等待时间）XX:①，初始化所有信息，建立图模型，编写价格最优的路线选择，界面优化2010年01月11日《数据结构》课程设计报告（模板）_正文1、目的求公交线路上优化路径的查询。2、需求分析程序需要根据乘客的需要来查询的出符合要求的信息在程序运行的过程中根据提示进行输入；程序输出所有符合要求的最优的路线以供乘客选择；程序能查询任意两站之间按时间和按价格的最优路线查询；3、概要设计先建图，再用Floyd函数求出任意两个结点之间的最优路径，后调用shortest函数进行求时间最优的路径，结束后在main函数里面提供选择界面，可以进行时间和价格最优路线的查询分别为Select_Time函数和Select_Money函数4、详细设计1）、定义结构体typedefstruct{intselectbusnum;charstation1,station2;intselectbusprice,selectbusgap;}Selects;〃存储按条件选择的最优选择路线的信息typedefstruct{charStaName;charLocation[128];}StationInfo;〃站点的信息，每个站点中存放的信息有名字和位置]typedefstruct{VRTypeadj;/因为是有向图，adj用来存放权值，存放的是两个结点之间的时间值InfoType*info;//存放弧的信息}ArCell,adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃adj[v][w]数组即v和w之间的权值typedefstruct{intnum;〃车辆的路线号intprice;〃每路车的票价intgap;〃每两次发车之间的时间间隔intspeed;〃车速intstopnum;〃每辆车经过的车站的总数Stationinfopass[MAX_VERTEX_NUM];//每一路车经过的站点的信息}BusInfo;〃车辆信息typedefstruct{charStaName;charLocation[32];intstopbusnum;Businfostopbus[MAX_BUS_NUM];}VertexType;//每个结点存放的信息，包括了站名，位置，经过的车辆数以及经过的该站点的所有的车辆的信息2)调整函数AdjustvoidAdjust(MGraph&G,VertexType*S){inti;for(i=0;i<MAX_VERTEX_NUM;i++)G.vexs[i].StaName=S[i].StaName;}将所有初始化的值与图联系起来，把初始化的点的名字传给图中各个节点的StaName。voidAdjust_2(Businfo*bus,MGraph&G){inti,j,t[8]={0,0,0,0,0,0,0,0},p;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_BUS_NUM;j++)for(p=0;p<bus[j].stopnum;p++)if(G.vexs[i].StaName==bus[j].pass[p].StaName){G.vexs[i].stopbusnum++;G.vexs[i].stopbus[t[i]].num=bus[j].num;G.vexs[i].stopbus[t[i]].price=bus[j].price;G.vexs[i].stopbus[t[i]].gap=bus[j].gap;G.vexs[i].stopbus[t[i]].speed=bus[j].speed;t[i]++;}}将所有的初始化的点的信息以及bus的信息传递给图，每个结点中记录了经过该站的所有的车辆的信息，bus[j].pass[p]是用来存放该车经过的站的信

息。定义的整型数组t[8]是用来对每辆车经过的站的个数进行计数的。3)建立图模型intLocateVex(MGraphG,charu){inti;for(i=0;i<Gvexnum;i++){if(u==Gvexs[i].StaName)returni;}if(i=G.vexnum){printf("Erroru!\n");return1;}return0;}LocateVex函数在下面建图函数中调用的时候是用来找到v1，v2结点分别在G向量中的位置的。voidCreateMGraph(BusInfo*bus,VertexType*S,MGraph&G){voidAdjust(MGraph&G,VertexType*S);voidAdjust_1(BusInfo*bus,VertexType*S);voidAdjust_2(BusInfo*bus,MGraph&G);//申明要调用的函数Adjust(G,S);Adjust_2(bus,G);Adjust_1(bus,S);inti,j,t;G.vexnum=8;G.arcnum=11;charv1,v2,a[11][2]={{'A','B'},{'A','D'},{'A',F},{'B','C'},{'D','C'},{'D',E},{F,E},{'C','G'},{'F',G},{'E','H'},{'G',E}};intb[11]={8,5,6,3,2,10,7,4,5,15,20};//根据初始化的数据构建弧的权值(时for(i=0;i<G.vexnum;i++)间)for(j=0;j<Gvexnum;j++)G.arcs[i][j].adj=INFINITY;//INFINITY宏定义的最大值表示距离for(t=0;t<11;t++){v1=a[t][0];v2=a[t][1];i=LocateVex(Gv1);j=LocateVex(Gv2);G.arcs[i][j].adj=b[t];//将v1，v2赋值为弧的两端的结点//i表示v1v1=a[t][0];v2=a[t][1];i=LocateVex(Gv1);j=LocateVex(Gv2);G.arcs[i][j].adj=b[t];//j表示v2在G向量结点数组中的位置//将数组b中的时间值赋给i到j的弧上}return;}建立图模型将所有的初始化的数据放到图的每项中。4)test函数voidTest(BusInfo*bus,MGraphG){inti,j;for(i=0;i<MAX_BUS_NUM;i++){printf("路线％d票价％d间隔％d分钟车速%dkm/h",bus[i].num,bus[i].price,bus[i].gap,bus[i].speed);printf("经过的站为:")；for(j=0;j<bus[i].stopnum;j++)printf("%c%s”,bus[i].pass[j].StaName,bus[i].pass[j].Location);printf("\n");}for(i=0;i<MAX_VERTEX_NUM;i++){printf("站名％c坐标％s\n”,S[i].StaName,S[i].Location);for(j=0;j<S[i].stopbusnum;j++){printf("停靠汽车及相关信息：路线%d票价％d间隔%d分钟车速％d千米每分”，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,Gvexs[i].stopbus[j].speed);printf("\n");}}}Test函数是用来测试建立图之后，原来初始化的数据是否已经成功的存放进图。Show_FLOYD函数voidShow_FLOYD(){Test(bus,G);〃先将图线输出便于后面的查看CreateMGraph(bus,S,G);〃建图PrintMGraph(G);Test(bus,G);〃图是用邻接矩阵的方法来建的，所以用在inti,j,k,l,m,n;〃这里的PrintMGraph函数是用来输出矩阵的for(i=0;i<Gvexnum;i++)G.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求对角元素值为0printf("邻接矩阵:\n");for(i=0;i<G.vexnum;i++)//直接有路径的输出时间，没有的在输出INFINITY{for(j=0;j<Gvexnum;j++)printf("%6d”,G.arcs[i][j]);printf("\n");}ShortestPath_FLOYD(G&p,&d);〃调用函数来找出按时间所有的的最短路径printf("d矩阵:\n");for(i=0;i<Gvexnum;i++){for(j=0;j<G.vexnum;j++)〃用二维数组来输出对应的矩阵中的权值printf("%6d”,d[i][j]);printf("\n");for(i=0;i<Gvexnum;i++)for(j=0;j<Gvexnum;j++){if(d[i][j]!=100)一printf("%c至0%c的最短时间为%d分\n”,G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);}printf("p矩阵:\n");〃p矩阵用来存放路线信息从i到j的具体路线l=G.vexnum;for(i=0;i<Gvexnum;i++){for(j=0;j<Gvexnum;j++){if(i!=j){m=0;//占位空格for(k=0;k<G.vexnum;k++)if(p[i][j][k]=1)printf("%c”,G.vexs[k].StaName);elsem++;for(n=0;n<m;n++)〃输出占位空格printf(-");〃如果两个结点之间找不到可以直接通的路}//线则在相应的位置上输出空格}printf("\n");}printf("按回车键继续");a=getchar();system("cls");〃输出信息过多，清屏一次}用于输出所有的两个结点的时间信息以及从每个点到其他任意一个点的具体路线ShortestPath_FLOYD函数voidShortestPath_FLOYD(MGraphG,PathMatrix*P,DistancMatrix*D){//用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其//带权长度D[v][w]。若P[v][w][u]为TRUE,则u是从v到w当前求得最短intu,v,w,i;for(v=0;v<G.vexnum;v++)//各对结点之间初始已知路径及距离for(w=0;w<Gvexnum;w++){(*D)[v][w]=G.arcs[v][w].adj;//D矩阵用来存放每一条弧的权值即时间值for(u=0;u<G.vexnum;u++)(*P)[v][w][u]=FALSE;if((*D)[v][w]<INFINITY)//当权值小于最大值时说明从v到w有直接路径{(*P)[v][w][v]=TRUE;//v,w之间有直接路径就将(*P)[v][w][v]赋值为1(*P)[v][w][w]=TRUE;}}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<Gvexnum;w++)if((*D)[v][u]+(*D)[u][w]<(*D)[v][w])〃从v经u到w的一条路径更短{(*D)[v][w]=(*D)[v][u]+(*D)[u][w];for(i=0;i<G.vexnum;i++)(*P)[v][w][i]=(*P)[v][u][i]||(*P)[u][w][i];}}此函数是用来求出每个点到另外的任意一个点的按时间的最优的路径，对于有两个结点相邻但路径的时间是否是最短进行判断并挑选出时间的最优的路径，下面的选择函数则是在将这些路径比较和挑选。Select_Time函数voidSelect_Time(){charv1,v2;inti,j,k,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM]={1,1,1,1,1,1};/*num数组用来做标记用，已做过标记为0，没做够标记为1*/chara[MAX_VERTEX_NUM];/*a[]字符数组用来存放从v1到v2的最短路径所经过的都有的站点名字*/printf(-请输入起始站点和目的点\n");scanf("%c%c",&v1,&v2);for(i=0;i<Gvexnum;i++){if(v1=G.vexs[i].StaName)〃找到与名字v1对应的结点{loc1=i;〃用来存放出发点v1在图中的位置printf("站名％c坐标％s\n",G.vexs[i].StaName,G.vexs[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){〃找出所有v2点停靠的车辆的信息printf("停靠汽车及相关信息：路线％d票价％d间隔％d分钟车速％d千米每分”，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf("\n经过的站为:")；for(m=0;m<bus[j].stopnum;m++)printf("%c%s”,Gvexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);〃将所有v2点停靠的车辆的信息输出printf("\n");

}if(v2==G.vexs[i].StaName){loc2=i;〃用来存放出发点v2在图中的位置printf("站名%c坐标％s\n",S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){〃找出所有v2点停靠的车辆的信息printf("停靠汽车及相关信息：路线％d票价％d间隔％d分钟车速％d千米每分”，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,Gvexs[i].stopbus[j].speed);printf("\n经过的站为:")；for(m=0;m<bus[j].stopnum;m++)〃将所有v2点停靠的车辆的信息输出printf("\n");}printf("%c%s”,Gvexs[i].stopbus[j].pass[m].StaName,Gvexs[i].stopbus[j].pass[m].Location);}}printf("\n*****************结果****************\n\n");for(i=0;i<MAX_BUS_NUM;i++){for(j=0;j<bus[i].stopnum;j++)if(v1==bus[i].pass[j].StaName||v2==bus[i].pass[j].StaName){〃判断在该车都经过的站点中有没有是v1或v2的t++;//用来标记一条最短路径中的v1，v2出现情况if(t==2)//〃将所有v2点停靠的车辆的信息输出printf("\n");}{printf("直达路线%d票价%d间隔%d分钟车速%dkm/h停靠％d站”，bus[i].num,bus[i].price,bus[i].gap,bus[i].speed,bus[i].stopnum);printf("\n经过的站为:")；for(m=0;m<bus[i].stopnum;m++)printf("%c%s”,bus[i].pass[m].StaName,bus[i].pass[m].Location);printf("\n");t=0;flag=1;//此处的t=0是t=2的情况重置便于下个循环的实现}}t=0;//此处是将t=1是的情况重置用于下一个大循环的实现}i=LocateVex(Gv1);〃找出v1在图中的位置j=LocateVex(Gv2);〃找出v2在图中的位置if(d[i][j]!=INFINITY)//当i，j之间有最短路径时输出下面信息printf("%c至0%c的最短时间为%d分\n”,G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);if(flag!=1){〃标记flag当为1时i和j直接有弧，有直接从i到j的车printf("两站直接没有车直达，可以选择换乘!!\n");printf("经过的站点")；for(t=0;tvG.vexnum;t++)if(p[i][j][t]=1)printf("%c",G.vexs[t].StaName);printf("\n");t=0;for(m=0;mv=Gvexnum;m++)if(p[i][j][m]=1)〃当p[i][j][m]为1时说明i,j之间有直接的路径{a[t]=G.vexs[m].StaName;t++;}//将每个结点的名字存放到a[]里for(m=0;mvt-1;m++){loc1=LocateVex(Ga[m]);loc2=LocateVex(Ga[m+1]);//先定义连续的两辆车for(i=0;ivG.vexs[loc1].stopbusnum;i++)for(j=0;jvGvexs[loc2].stopbusnum;j++)if(G.vexs[loc1].stopbus[i].num=G.vexs[loc2].stopbus[j].num){//判断连续的两个站是否有直接相连的一路车flag=m+1;〃如果有则记下m+1for(k=0;kvbus[i].stopnum;k++)if(G.vexs[loc1].stopbus[i].pass[k].StaName==a[flag])flag++;//如果经过locl的车同时经过下一个站个flag++if(num[G.vexs[loc1].stopbus[i].num]!=0){printf("乘坐％d路车在％。站上车在％。站下车\n",G.vexs[loc1].stopbus[i].num,a[m],a[flag-1]);num[G.vexs[loc1].stopbus[i].num]=0;/*表示已经做过了这辆车，则标记为0*/}}}}}根据输入的站名来选择时间上最优的路线。Select_Money函数voidSelect_Money(){charv1,v2,ch;SelectsB[10];inti,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM],min=0;chara[MAX_VERTEX_NUM];/*a[]字符数组用来存放从v1到v2的最短路径所经过的都有的站点名字*/printf(-请输入起始站点和目的点\n");scanf("%c%c",&v1,&v2);

printf("***************站点信息*************\n");for(i=0;i<Gvexnum;i++){if(v1==G.vexs[i].StaName){loc1=i;〃找出v1站点的位置printf("站名%c坐标％s\n",S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("停靠汽车及相关信息：路线%d票价%d元间隔%d分钟车速%d千米每分"，//输出经过该站点的所有的车的信息G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf("\n经过的站为:")；for(m=0;m<bus[j].stopnum;m++)printf("%cm].Location);%s”,Gvexs[i].stopbus[j].pass[m].StaName,Gvexs[i].stopbus[j].pass[printf("\n");}}if(v2==G.vexs[i].StaName){loc2=i;〃找出v1站点的位置printf("站名%c坐标％s\n",S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("停靠汽车及相关信息：路线%d票价%d元间隔%d分钟车速%d千米每分"，//输出多有经过v2的车的信息G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,Gvexs[i].stopbus[j].speed);printf("\n经过的站为:")；printf("%cm].Location);printf("%c%s”,Gvexs[i].stopbus[j].pass[m].StaName,Gvexs[i].stopbus[j].pass[m].Location);printf("\n");}}}printf("\n");printf("***************结果****************\n");for(i=0;i<MAX_BUS_NUM;i++)〃寻找最优路径{for(j=0;j<bus[i].stopnum;j++)if(v1==bus[i].pass[j].StaNamellv2==bus[i].pass[j].StaName)t++;〃标记t,当t为1是说明条件只满足了一个if(t==2)//当t为2时说明上述两个条件都满足{printf("直达路线％d票价％d元间隔％d分钟车速%dkm/h停靠％d站"，//t为2说明两个站都在这路车里找到了bus[i].num,bus[i].price,bus[i].gap,bus[i].speed,bus[i].stopnum);printf("\n经过的站为:")；for(m=0;m<bus[i].stopnum;m++)printf("%c%s”,bus[i].pass[m].StaName,bus[i].pass[m].Location);printf("\n");t=0;flag=1;num[n]=i;n++;}}t=0;}if(flag==1)//flag标记说明v1，v2之间有直接通的一路车{min=100;//将min最小先赋值为100用于下面的循环for(m=0;m<n;m++)if(bus[num[m]].price<min)min=m;printf("最省车费%d\n",bus[num[min]].price);printf("选择路线％d票价％d元间隔％d分钟车速%dkm/h停靠％d站”，bus[min].num,bus[min].price,bus[min].gap,bus[min].speed,bus[min].stopnum);printf("\n经过的站为:")；for(m=0;m<bus[min].stopnum;m++)printf("%c%s”,bus[min].pass[m].StaName,bus[min].pass[m].Location);printf("\n");}if(flag!=1){min=0;//将min赋值为0，由于两站之间没有直通车用于下面多i=LocateVex(Gv1);〃辆车的比较j=LocateVex(Gv2);printf("两站直接没有车直达，可以选择换乘!!\n");printf("经过的站点")；for(t=0;tvG.vexnum;t++)if(p[i][j][t]==1)printf("%c",G.vexs[t].StaName);printf("\n");t=0;for(m=0;mv=Gvexnum;m++)if(p[i][j][m]==1){a[t]=G.vexs[m].StaName;t++;}for(m=0;mvt-1;m++){loc1=LocateVex(Ga[m]);loc2=LocateVex(Ga[m+1]);//先定义连续的两个站for(i=0;i<G.vexs[loc1].stopbusnum;i++)for(j=0;j<Gvexs[loc2].stopbusnum;j++)if(G.vexs[loc1].stopbus[i].num=G.vexs[loc2].stopbus[j].num){〃判断连续的两个站是否有是同一路车B[k].selectbusnum=G.vexs[loc1].stopbus[i].num;B[k].station1=a[m];B[k].station2=a[m+1];B[k].selectbusprice=Gvexs[loc1].stopbus[i].price;B[k].selectbusgap=Gvexs[loc1].stopbus[i].gap;k++;//将该路车的信息存放到Select结构体数组B[]中}}flag=k;for(i=0;i<flag;i++)for(j=i+1;j<flag;j++)if(B[i].selectbusnum==B[j].selectbusnum&&B[i].station2==B[j].station1){B[j].selectbusnum=0;ch=B[i].station2;B[i].station2=B[j].station2;for(t=j+1;t<flag;t++)if(B[t].station1==ch)B[t].selectbusnum=0;}〃由于将每两个结点有弧的车全都存放进了数组B[]中可能存/〃在着重复的项，此循环则是用于将重复的车辆信息合并for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)min=min+B[t].selectbusprice;/*先将搜有能连接来那个地的所有的车的价格全部相加*/for(t=0;t<flag;t++)if(B[t].selectbusnum!=0&&B[t].station1==B[t+1].station1){if(B[t].selectbusgap<B[t+1].selectbusgap){min=min-B[t+1].selectbusprice;/*两两比较，将费用最少的找出，将高于最少的费用的其他同一路的车的价格减掉则剩下了费用最优的的路线组合*/B[t+1].selectbusnum=0;}〃求出两个站点的最少费用else{min=min-B[t+1].selectbusprice;B[t].selectbusnum=0;}}for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)//输出符合要求的信息printf("乘坐%d路车在%c站上车在%c站下车票价%d元间隔％d分钟\n”,B[t].selectbusnum,B[t].station1,B[t].station2,B[t].selectbusprice,B[t].selectbusgap);printf("最省路费为%d元\n",min);}printf("结束查询!谢谢使用!!\n");}9)main函数voidmain(){inti;chara;Show_FLOYD();printf(-请选择检索内容\n1去两地时间最短路线查询\n2去两地路费最省路线查\n3结束查询\n");scanf("%d",&i);a=getchar();//吸收缓冲区里的回车符system("cls");〃由于界面显示太多项，清屏一次switch(i){case1:printf("选择1去两地时间最短\n");Select_Time();break;case2:printf("选择2去两地路费最省\n");Select_Money();break;case3:printf("结束查询!谢谢使用!!\n");break;default:printf("输入错误!!\n");〃界面}}5、调试分析程序调试时，如果没有根据提示正确输入，界面上会出现提示出错的提示，可以到程序中找出错误并进行改正。6、测试结果

BCBCDBCDECDCDEDEBCDEFC&EFDEFEFBCGCCBCDHCPHDHEH，..按回车键进入查询,■■进入查询界面根据需求查询:SE9!■）（1｛）（1｛）（1｛）（1｛）（釜竟釜竟~［者［先：|圣才令专?内谷：）（）（）（厦）（）（）（■）（，）（3）C）C）C）C1＞去两地爵间参盅豺查询SE9!L去两地跄费簧眷盛线查询3＞绪来查宜请输入极的选ffi：1提示是否需要把等待时间加在一起查询:两站直掾没有车着摆顶以选择换乘?!经过的塞京龄班选择呈否要考虑等车的时间J是^否成功查询:cDEHcDEH在在在.5汆车车车fOnthLLLLUVc，rrn冒站站臂Escc4w郭在在在嗯-any的Is辱琨查3脂坐坐坐束g按价格进行查询:线查询

线查询索詹r酱线查询

线查询索詹r酱1戒2选间费¥=一一两衲束伯

-$在.A攵输请查询成功:口n车中丰留昭1517、用户使用说明在用户首次进入查询时就会出现提示，用户可以根据具体的提示来进行下一步的操作。

《数据结构》课程设计考核评估标准通过程序设计及答辩方式，并结合学生的动手能力（编程及调试程序能力）、独立分析解决问题的能力、创新精神、总结报告、答辩水平、学习态度以及题目难易程度综合考评，成绩分优、良、中、及格和不及格五等。课程设计的量化评分成绩见表（1）《数据结构》课程设计量化评分标准（每人一页）学生姓名：赵杰学生学号08030334指标最高分评分要素评分设计技术水平20程序运行情况良好，结构设计合理，算法说明清晰，理论分析与计算正确，实验数据无误，通用性和可扩充性强实际动手能力20独立完成设计，能够迅速准确的进行调试和纠错研究成果与专业知识10对研究的问题能较深刻分析或者有独到见解，很好地掌握了有关基础理论与专业知识，总结报告认识深刻写作与总结提炼能力10报告结构严谨，逻辑严密，论述层次清晰，语言流畅，表达准确，重点突出，文献综述10有较完善的文献综述，能够正确查阅参考文献资料规范化程度10提交的电子文档及打印文档的书写、存放完全符合规范化要求答辩情况10能简明扼要地阐述设计的主要内容，能准确流利地回答各种问题学习态度10端正的学习态度及认真刻苦程度等总分注意:本评分标准适用于数据结构课程设计；总分满分为100分，成绩参考标准为：优秀（100>XN90）；良好（90>XN80）；中等（80>XN70）；及格（70>XN60）；不及格（X<60）；发现有拷贝舞弊现象者，一律直接退回不作检查，两次舞弊者按不及格处理。每组学生至少要回答三个以上的问题，有两个以上问题回答不清楚者，一律不及格。课程设计报告不交或不规范者一律不及格。《数据结构》课程设计考核评估标准通过程序设计及答辩方式，并结合学生的动手能力（编程及调试程序能力）、独立分析解决问题的能力、创新精神、总结报告、答辩水平、学习态度以及题目难易程度综合考评，成绩分优、良、中、及格和不及格五等。课程设计的量化评分成绩见表（1）《数据结构》课程设计量化评分标准（每人一页）学生姓名：朱陈立学生学号08030337指标最高分评分要素评分设计技术水平20程序运行情况良好，结构设计合理，算法说明清晰，理论分析与计算正确，实验数据无误，通用性和可扩充性强实际动手能力20独立完成设计，能够迅速准确的进行调试和纠错研究成果与专业知识10对研究的问题能较深刻分析或者有独到见解，很好地掌握了有关基础理论与专业知识，总结报告认识深刻写作与总结提炼能力10报告结构严谨，逻辑严密，论述层次清晰，语言流畅，表达准确，重点突出，文献综述10有较完善的文献综述，能够正确查阅参考文献资料规范化程度10提交的电子文档及打印文档的书写、存放完全符合规范化要求答辩情况10能简明扼要地阐述设计的主要内容，能准确流利地回答各种问题学习态度10端正的学习态度及认真刻苦程度等总分注意:本评分标准适用于数据结构课程设计；总分满分为100分，成绩参考标准为：优秀（100>XN90）；良好（90>XN80）；中等（80>XN70）；及格（70>XN60）；不及格（X<60）；发现有拷贝舞弊现象者，一律直接退回不作检查，两次舞弊者按不及格处理。每组学生至少要回答三个以上的问题，有两个以上问题回答不清楚者，一律不及格。课程设计报告不交或不规范者一律不及格。答辩问题：1，优化问题是很重要的问题，许多问题比如数据挖掘问题就可以看作一个优化问题，请你谈谈对优化问题的认识？回答：数据挖掘，在人工智能领域，习惯上又称为数据库中知识发现（KnowledgeDiscoveryinDatabase,KDD），也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。在数据库中根据大量的信息，寻找最优的模型，完成优化。通过优化可以应用到很多领域，从而增加效益。优化问题在现实生活中有许多应用但基本思想是贪婪算法，即每一步都是最优的，整体就是最优的。例如笛杰斯特拉，普里母算法等。通过优化，可以找到解决问题的最优方法。2,你用什么标准选择公交线路上的优化路径？回答：在本程序中采用了时间和价格作为选择标准来进行查询，由于时间是在每两个站点之间的，对应图中的就是每条弧的权值，利用Floyd算法可以求到每一组站点之间的最优路径。按价格算的话，乘一次车给一次钱，换乘时才需要另外加钱，所以不能用Floyd算法来求价格的最优路径，所以在每个结点里存放进经过的所有的车的信息包括价格，在挑选车的时候可以将价格来进行比较挑选出最优路径。3,通过课程设计，你有那些收获，你对认为数据结构课程设计该怎样去做？回答：通过这次的课程设计，让我们更多的了解了贪婪算法的思想，更多的了解了Floyd算法的运用，在时间和价格最优的路线的挑选中就是运用了贪婪算法的思想，即每一步都占一点小的便宜，走最优的路线，到最后就可以得到从出发点到目的地的最优的路线了。做课程设计，首先要把自己的思想理清，确定自己的程序将要实现的是什么功能，再去找到理论依据，找到了理论依据后，就可以着手去写代码了。先将实现功能的主要的程序写出来，再由主要的程序向更加优化的方面考虑，去添加一些辅助的程序，最后调试时加以修改更正就可以了。#includestdio.hincludestring.hinclude〃stdlib.h〃include〃conio.h〃#defineTRUE1#defineFALSE0#include<limits.h>/*INT_MAX等*/defineINFINITY100defineMAX_VERTEX_NUM8defineMAX_BUS_NUM6typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintDistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintInfoType;typedefintVRType;PathMatrixp;DistancMatrixd;typedefstruct{intselectbusnum;charstation1,station2;intselectbusprice,selectbusgap;}Selects;typedefstruct{charStaName;charLocation[128];}StationInfo;typedefstruct{VRTypeadj;InfoType*info;}ArCell,adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct(intnum;intprice;intgap;//间隔intspeed;intstopnum;StationInfopass[MAX_VERTEX_NUM];}BusInfo;typedefstruct(charStaName;charLocation[32];intstopbusnum;BusInfostopbus[MAX_BUS_NUM];}VertexType;VertexTypeS[MAX_VERTEX_NUM]={{'A',〃（11,11）〃},{'B',〃（22,33）〃},{'C',〃（12,23）〃},{'D',〃（24,45）〃},{'E',〃（41,57）〃},{'F',〃（78,34）〃},{'G',〃（32,56）〃},{'H',〃（86,64）〃}};typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];adjMatrixarcs;intvexnum,arcnum;}MGraph;MGraphG;BusInfobus[MAX_BUS_NUM]={{1,2,10,4,4,{{'A',〃（11,11）〃},{'B',〃（22,33）〃},{'C',〃（12,23）〃},{'G',〃（32,56）〃}}},{2,1,5,4,4,{{'A',〃（11,11）〃},{'C',〃（12,23）〃},{'D',〃（24,45）〃},{'H',〃（86,64）〃}}},{3,2,10,4,4,{{'A',〃(11,11)〃},{'D',〃(24,45)〃},{'E',〃(41,57)〃},{'H',〃(86,64)〃}}},{4,1,5,4,4,{{'A',〃(11,11)〃},{'E',〃(41,57)〃},{'F',〃(78,34)〃},{'G',〃(32,56)〃}}},{5,1,10,4,3,{{'A',〃(11,11)〃},{'C',〃(12,23)〃},{'E',〃(41,57)〃}}},{6,2,8,4,4,{{'A',〃(11,11)〃},{'E',〃(41,57)〃},{'F',〃(78,34)〃},{'H',〃(86,64)〃}}}}；voidTest(BusInfo*bus,MGraphG){inti,j;for(i=0;i<MAX_BUS_NUM;i++){printf(〃路线%d票价%d元间隔%d分钟车速%dkm/h〃，bus[i].num,bus[i].price,bus[i].gap,bus[i].speed);printf(〃经过的站为：〃)；for(j=0;j<bus[i].stopnum;j++)printf("%c%s〃，bus[i].pass[j].StaName,bus[i].pass[j].Location);printf(〃\n〃)；}for(i=0;i<MAX_VERTEX_NUM;i++){printf(〃站名％c坐标%s\n〃,S[i].StaName,S[i].Location);for(j=0;j<S[i].stopbusnum;j++){printf(-停靠汽车及相关信息：路线％d票价%d间隔%d分钟车速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n〃)；}}}intLocateVex(MGraphG,charu){inti;for(i=0;i<G.vexnum;i++){if(u==G.vexs[i].StaName)returni;}if(i==G.vexnum){printf("Erroru!\n");return1;}return0;}//////////////////////////////////////////////////voidCreateMGraph(BusInfo*bus,VertexType*S,MGraph&G){voidAdjust(MGraph&G,VertexType*S);voidAdjust_1(BusInfo*bus,VertexType*S);voidAdjust_2(BusInfo*bus,MGraph&G);Adjust(G,S);Adjust_2(bus,G);Adjust_1(bus,S);inti,j,t;G.vexnum=8;G.arcnum=14;charv1,v2,a[14][2]={{'A','B'},{'A','D'},{'A','C'},{'A','E'},{'B','C'},{'C','D'},{'D','E'},{'E','F'},{'C','G'},{'D','H'},{'E','H'},{'F','G'},{'C','E'}};for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j].adj=INFINITY;for(t=0;t<11;t++){v1=a[t][0];v2=a[t][1];i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=b[t];}return;}voidPrintMGraph(MGraphG){inti,j;printf("OutputVertices:");for(i=0;i<MAX_VERTEX_NUM;i++)printf("%c",G.vexs[i].StaName);printf("\n");printf("OutputAdjMatrix:\n");for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)printf(〃%4d〃,G.arcs[i][j]);printf(〃\n〃)；}return;}voidAdjust(MGraph&G,VertexType*S){inti;for(i=0;i<MAX_VERTEX_NUM;i++)G.vexs[i].StaName=S[i].StaName;}voidAdjust_2(BusInfo*bus,MGraph&G){inti,j,m,t[8]={0,0,0,0,0,0,0,0},p;for(i=0;i<MAX_VERTEX_NUM;i++)G.vexs[i].stopbusnum=0;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_BUS_NUM;j++)for(p=0;p<bus[j].stopnum;p++)if(G.vexs[i].StaName==bus[j].pass[p].StaName)G.vexs[i].stopbusnum++;G.vexs[i].stopbus[t[i]].num=bus[j].num;G.vexs[i].stopbus[t[i]].price=bus[j].price;G.vexs[i].stopbus[t[i]].gap=bus[j].gap;G.vexs[i].stopbus[t[i]].speed=bus[j].speed;for(m=0;m<bus[j].stopnum;m++){G.vexs[i].stopbus[t[i]].pass[m].StaName=bus[j].pass[m].StaName;strcpy(G.vexs[i].stopbus[t[i]].pass[m].Location,bus[j].pass[m].Location);}t[i]++;}}voidAdjust_1(BusInfo*bus,VertexType*S)inti,j,t[8]={0,0,0,0,0,0,0,0},p,m;for(i=0;i<MAX_VERTEX_NUM;i++)S[i].stopbusnum=0;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_BUS_NUM;j++)for(p=0;p<bus[j].stopnum;p++)if(S[i].StaName==bus[j].pass[p].StaName){S[i].stopbusnum++;S[i].stopbus[t[i]].num=bus[j].num;S[i].stopbus[t[i]].price=bus[j].price;S[i].stopbus[t[i]].gap=bus[j].gap;S[i].stopbus[t[i]].speed=bus[j].speed;for(m=0;m<bus[j].stopnum;m++){S[i].stopbus[t[i]].pass[m].StaName=bus[j].pass[m].StaName;strcpy(S[i].stopbus[t[i]].pass[m].Location,bus[j].pass[m[.Location);t[i]++;}}voidShortestPath_FLOYD(MGraphG,PathMatrix*P,DistancMatrix*D){/*用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其*//*带权长度D[v][w]。若P[v][w][u]为TRUE，则u是从v到w当前求得最短*/intu,v,w,i;for(v=0;v<G.vexnum;v++)/*各对结点之间初始已知路径及距离*/for(w=0;w<G.vexnum;w++){(*D)[v][w]=G.arcs[v][w].adj;for(u=0;u<G.vexnum;u++)(*P)[v][w][u]=FALSE;if((*D)[v][w]<INFINITY)/*从v到w有直接路径*/(*P)[v][w][v]=TRUE;(*P)[v][w][w]=TRUE;}}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if((*D)[v][u]+(*D)[u][w]<(*D)[v][w])/*从v经u到w的一条路径更短*/{(*D)[v][w]=(*D)[v][u]+(*D)[u][w];for(i=0;i<G.vexnum;i++)(*P)[v][w][i]=(*P)[v][u][i]||(*P)[u][w][i];}}voidShow_FLOYD(){//Test(bus,G);CreateMGraph(bus,S,G);PrintMGraph(G);Test(bus,G);inti,j,k,l,m,n;chara;for(i=0;i<G.vexnum;i++)G.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求对角元素值为0printf("邻接矩阵:\n〃)；for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)printf(〃%6d〃,G.arcs[i][j]);printf(〃\n〃)；}ShortestPath_FLOYD(G,&p,&d);printf(〃d矩阵:\n〃)；for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)printf(〃％6d〃，d[i][j]);printf(〃\n〃)；for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){if(d[i][j]!=100)printf("%c到%c的最短时间为％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);}printf(〃p矩阵:\n〃)；l=G.vexnum;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(i!=j){m=0;//占位空格for(k=0;k<G.vexnum;k++)if(p[i][j][k]==1)printf(〃％c〃,G.vexs[k].StaName);elsem++;for(n=0;n<m;n++)//输出占位空格printf("");}printf(〃\n〃)；}printf（〃按回车键进入查询\n\n〃）；a=getchar();system(〃cls〃)；}/////////////////////////////////////////////////////////////////voidSelect_Time(){charv1,v2,ch;SelectsB[10];inti,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM]={1,1,1,1,1,1};chara[MAX_VERTEX_NUM];printf(〃请输入起始站点和目的点\n〃)；scanf(〃％c%c〃，&v1,&v2);printf(〃***************站点信息*************\n〃)；for(i=0;i<G.vexnum;i++){if(v1==G.vexs[i].StaName){loc1=i;printf("站名％c坐标％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("停靠汽车及相关信息：路线％d票价%d元间隔%d分钟车速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n经过的站为：〃)；for(m=0;m<bus[j].stopnum;m++)printf(〃%c%s〃，G.vexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);}}if(v2==G.vexs[i].StaName){loc2=i;printf(〃站名％c坐标％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf(〃停靠汽车及相关信息：路线％d票价%d元间隔%d分钟车速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n经过的站为：〃)；for(m=0;m<bus[j].stopnum;m++)printf(〃%c%s〃，G.vexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);}ch=getchar();system(〃cls〃)；printf(〃***************结果****************\n〃)；for(i=0;i<MAX_BUS_NUM;i++){for(j=0;j<bus[i].stopnum;j++)if(v1==bus[i].pass[j].StaName||v2==bus[i].pass[j].StaName){t++;if(t==2){printf("直达路线％d票价％d元间隔％d分钟车速%dkm/h停靠%d站〃，bus[i].num,bus[i].price,bus[i].gap,bus[i].speed,bus[i].stopnum);printf("\n经过的站为：")；for(m=0;m<bus[i].stopnum;m++)printf("%c%s〃，bus[i].pass[m].StaName,bus[i].pass[m].Location);printf(〃\n〃)；t=0;flag=1;}}t=0;}i=LocateVex(G,v1);j=LocateVex(G,v2);//if(d[i][j]!=INFINITY)//printf("%c到%c的最短时间为％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);if(flag!=1){printf("两站直接没有车直达,可以选择换乘！！\n〃)；printf("经过的站点")；for(t=0;t<G.vexnum;t++)if(p[i][j][t]==1)printf(〃％c〃,G.vexs[t].StaName);printf(〃\n〃)；t=0;for(m=0;m<=G.vexnum;m++)if(p[i][j][m]==1){a[t]=G.vexs[m].StaName;t++;}for(m=0;m<t-1;m++){loci二LocateVex(G,a[m]);loc2二LocateVex(G,a[m+1]);for(i=0;i<G.vexs[loc1].stopbusnum;i++)for(j=0;j<G.vexs[loc2].stopbusnum;j++)if(G.vexs[loc1].stopbus[i].num==G.vexs[loc2].stopbus[j].num){B[k].selectbusnum二G.vexs[loc1].stopbus[i].num;B[k].station1=a[m];B[k].station2=a[m+1];B[k].selectbusprice二G.vexs[loc1].stopbus[i].price;B[k].selectbusgap二G.vexs[loc1].stopbus[i].gap;k++;}flag=k;for(i=0;i<flag;i++)for(j=i+1;j<flag;j++)if(B[i].selectbusnum==B[j].selectbusnum&&B[i].station2==B[j].stationl){B[j].selectbusnum=0;ch=B[i].station2;B[i].station2=B[j].station2;for(t=j+1;t<flag;t++)if(B[t].station1==ch)B[t].selectbusnum=0;}}printf("选择是否要考虑等车的时间\n1/是2/否\n〃);scanf(〃%d〃,&m);ch=getchar();system(〃cls〃)；if(m==1){i=LocateVex(G,v1);j=LocateVex(G,v2);for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)d[i][j]=d[i][j]+B[t].selectbusgap;for(t=0;t<flag;t++)if(B[t].selectbusnum!=0&&B[t].station1==B[t+1].station1)if(B[t].selectbusgap<B[t+1].selectbusgap){d[i][j]=d[i][j]-B[t+1].selectbusgap;B[t+1].selectbusnum=0;}else{d[i][j]=d[i][j]-B[t].selectbusgap;B[t].selectbusnum=0;}printf("%c到%c的最短时间为％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)printf("乘坐％d路车在％c站上车在％c站下车票价%d元间隔%d分钟\n”,B[t].selectbusnum,B[t].station1,B[t].station2,B[t].selectbusprice,B[t].selectbusgap);}if(m==2){i=LocateVex(G,v1);j=LocateVex(G,v2);if(d[i][j]!=INFINITY)printf("%c到%c的最短时间为％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)printf("乘坐％d路车在％c站上车在％c站下车票价%d元间隔%d分钟\n”,B[t].selectbusnum,B[t].station1,B[t].station2,B[t].selectbusprice,B[t].selectbusgap);}printf（"结束查询!谢谢使用!!\n"）;}////////////////////////////////////////////////////////////////////////////////voidSelect_Money(){charv1,v2,ch;SelectsB[10];inti,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM],min=0;chara[MAX_VERTEX_NUM];printf("请输入起始站点和目的点\n〃)；scanf(〃％c%c〃，&v1,&v2);printf(〃***************站点信息*************\n〃)；for(i=0;i<G.vexnum;i++){if(v1==G.vexs[i].StaName){loc1=i;printf("站名％c坐标％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++)printf("停靠汽车及相关信息：路线％d票价%d元间隔%d分钟车速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n经过的站为：〃)；for(m=0;m<bus[j].stopnum;m++)printf(〃%c%s〃，G.vexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);printf(〃\n〃)；}}if(v2==G.vexs[i].StaName){loc2=i;printf(〃站名％c坐标％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("停靠汽车及相关信息：路线％d票价%d元间隔%d分钟车速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i]