数据结构课程设计交通咨询系统设计说明.doc

. . . 设计题目<二>：7.3.4交通咨询系统设计P160一、设计要求1问题描述根据不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的时间尽可能的短,出门旅行的旅客希望旅费尽可能的少,而老年人则要求中转次数少。模拟一个全国城市之间的咨询交通程序,为旅客提供两种或三种最优的交通路线。2需求分析二、概要设计1主界面设计图2.1"交通咨询系统"主菜单2存储结构设计本系统采用图结构类型存储抽象交通咨询系统的信息。typedef struct TrafficNodechar nameMAX_STRING_NUM; /班次 /MAX_STRING_NUM最为10int StartTime, StopTime; /起止时间 int EndCity; /该有向边指向的顶点在数组中的位置,即该城市编号 int Cost; /票价 TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum, FlightNum; /标记下面Train数组和Flight数组里元素个数 TrafficNodeDat TrainMAX_TRAFFIC_NUM; /数组成员为结构体,记录了到达城市、起止时间、票价和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM;/ int Cost; /遍历时到达该城市的耗费时间或者费用 VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat;3系统功能设计1添加城市。添加一个城市的名称2删除城市。输入一个城市名称,删除该城市。3添加交通路线。输入起始城市、终点城市、航班或火车、车次、起始时间、终点时间和票价4 删除交通路线。输入火车或飞机的班次删除该交通路线。5查询最小费用路线。输入起始城市、终点城市、航班或火车、车次、起始时间、终点时间查询最小费用路线。三、模块设计1模块设计无向网操作模块工作区模块主程序模块图2.2 模块调用示意图2系统子程序及功能设计1int ShowMenu<>/主菜单2void CopyRight<>3int SeekCity<char *name> /寻找城市4int InsertCity<char *Name> /添加城市5int SaveSysInfo<> /向程序输入数据6int DelCity<char *Name> /删除城市7int InsertTrain<char *train, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost>/添加火车路线8int InsertFlight<char *flight, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost>/添加飞机航线9int DelPath<char *name>/删除路线10void Dijkstra<int matxDij_MAXNDij_MAXN, int p_start, int p_end, int TravelType>11int InitSysData<>/存储数据12int SearchMinTime<CityType City, CityType EndCity, int CurTime, int curPathNo, int TravelType>/查询最短时间13int CalcMinTime<int StartCity, int EndCity, int TravelType> /显示最短时间14int CalcMinCost<int StartCity, int EndCity, int TravelType>/最少花费15int main<>/主函数3函数主要调用关系图15main89112754136361223716图2.3函数主要调用关系图四、详细设计1数据类型定义1全局变量的定义typedef short int CityType;/CityType 定义短整形的变量 typedef struct TrafficNodechar nameMAX_STRING_NUM; /班次 /MAX_STRING_NUM最为10int StartTime, StopTime; /起止时间 int EndCity; /该有向边指向的顶点在数组中的位置,即该城市编号 int Cost; /票价 TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum, FlightNum; /标记下面Train数组和Flight数组里元素个数 TrafficNodeDat TrainMAX_TRAFFIC_NUM; /数组成员为结构体,记录了到达城市、起止时间、票价和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM;/ int Cost; /遍历时到达该城市的耗费时间或者费用 VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat;2系统主要子程序详细设计1用户工作区模块的设计int ShowMenu<> printf<"n|*欢迎使用交通咨询系统*|n">printf<"n|-1: 添加城市-|">printf<"n|-2: 删除城市-|">printf<"n|-3: 添加交通路线-|">printf<"n|-4: 删除交通路线-|"> printf<"n|-5: 查询最小费用路线-|">printf<"n|-6: 查询最快路线-|">printf<"n|-7: 清除屏幕-|">printf<"n|-0: 退出-|n">printf<"n|*o<_>o o<_>o *|n">printf<"n请输入你的选择:">return 1;2用Dijkstra算法求两段路程的最短距离void Dijkstra_Output<int matxDij_MAXNDij_MAXN, int PreCityDij_MAXN, int p_end, int TravelType>int trackDij_MAXN;int i = 0, j, k, min, tmp, end, cost = 0;j = p_end; tracki+ = j;while <PreCityj >= 0>cost += matxPreCityjj;tracki+ = j = PreCityj;printf<"nTrack Way:">if <!TravelType>for <i-; i>0; i->printf<"n%s:", CityNametracki>end = tracki - 1; min = 32767;for <k = 0; k<AdjListtracki.TrainNum; k+>if <AdjListtracki.Traink.EndCity = end&&min>AdjListtracki.Traink.Cost>min = AdjListtracki.Traink.Cost;tmp = k;printf<"%s", AdjListtracki.Traintmp.name>printf<"%2d:%2d-%2d:%2d", AdjListtracki.Traintmp.StartTime / 60, AdjListtracki.Traintmp.StartTime % 60, AdjListtracki.Traintmp.StopTime / 60, AdjListtracki.Traintmp.StopTime % 60>elsefor <i-; i>0; i->printf<"n%s:", CityNametracki>end = tracki - 1; min = 32767;for <k = 0; k<AdjListtracki.FlightNum; k+>if <AdjListtracki.Traink.EndCity = end&&min>AdjListtracki.Flightk.Cost>min = AdjListtracki.Flightk.Cost;tmp = k;printf<"%s", AdjListtracki.Flighttmp.name>printf<"%2d:%2d-%2d:%2d", AdjListtracki.Flighttmp.StartTime / 60, AdjListtracki.Flighttmp.StartTime % 60, AdjListtracki.Flighttmp.StopTime / 60, AdjListtracki.Flighttmp.StopTime % 60>printf<"n%s: DESTINATION!", CityNametrack0>printf<"nMin Cost : %dn", cost>void Dijkstra<int matxDij_MAXNDij_MAXN, int p_start, int p_end, int TravelType>int PreCityDij_MAXN; /PreCityi=-1,never used; /PreCity>0,the precity of City i int i, j, min, pre, pos;for <i = 0; i<CityNum; i+>PreCityi = -1;PreCityp_start = -2;while <PreCityp_end = -1>min = -1;for <i = 0; i<CityNum; i+>if <PreCityi != -1>for <j = 0; j<CityNum; j+>if <PreCityj = -1 && matxij>0 && <min<0 | matxij<min>>pre = i; pos = j; min = matxij;PreCitypos = pre;Dijkstra_Output<matx, PreCity, p_end, TravelType>五、测试分析1. 添加城市在主菜单下,用户输入1,添加城市名称。图2.4添加城市2删除城市在主菜单下,用户输入2,删除已添加城市名称。图2.5删除城市3添加交通路线在主菜单下,用户输入3,已添加城市名称。添加起始城市、终点城市名称、乘车类型、乘车班次、起始时刻、终点时刻、和票价。图2.6添加交通路线4删除交通路线输入班次号,删除交通路线图2.7删除交通路线5查询最小费用交通路线图2.8 查询最小费用交通路线6查询最快交通路线图2.9查询最快交通路线7清除屏幕8退出六、用户手册使用本系统时,用户需先向程序添加城市后,在已有城市基础上添加已有城市的路线和使用各项功能。七、调试报告程序运行无错误,但当系统输入其他无储存容时程序会意外中断,代码需要优化。八、程序清单#include "stdafx.h"#include <stdio.h> #include <string.h> #include <stdlib.h>#define ERR 0 #define OK 1 #define Dij_MAXN 100 #define MAX_VERTEX_NUM 100#define MAX_STRING_NUM 100 #define MAX_TRAFFIC_NUM 100 const char CityFile = "city.txt"const char TrainFile = "train.txt"const char FlightFile = "flight.txt"typedef short int CityType;/CityType 定义短整形的变量 typedef struct TrafficNodechar nameMAX_STRING_NUM; /班次 /MAX_STRING_NUM最为10int StartTime, StopTime; /起止时间 int EndCity; /该有向边指向的顶点在数组中的位置,即该城市编号 int Cost; /票价 TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum, FlightNum; /标记下面Train数组和Flight数组里元素个数 TrafficNodeDat TrainMAX_TRAFFIC_NUM; /数组成员为结构体,记录了到达城市、起止时间、票价和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM;/ int Cost; /遍历时到达该城市的耗费时间或者费用 VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat;VNodeDat AdjListMAX_VERTEX_NUM; char CityNameMAX_VERTEX_NUMMAX_STRING_NUM; /城市名,采用第一下标为该城市在本程序中的编号 int CityNum; /城市数目 PNodeDat PathMAX_VERTEX_NUM; /存储临时最小时间路径 PNodeDat MinPathMAX_VERTEX_NUM; /存储搜索到当前的最小时间路径 int MinTime, StartTime;int curPath;int ShowMenu<> printf<"n|*欢迎使用交通咨询系统*|n">printf<"n|-1: 添加城市-|">printf<"n|-2: 删除城市-|">printf<"n|-3: 添加交通路线-|">printf<"n|-4: 删除交通路线-|"> printf<"n|-5: 查询最小费用路线-|">printf<"n|-6: 查询最快路线-|">printf<"n|-7: 清除屏幕-|">printf<"n|-0: 退出-|n">printf<"n|*o<_>o o<_>o *|n">printf<"n请输入你的选择:">return 1;void CopyRight<>printf<"n">int SeekCity<char *name> /寻找城市int i;for <i = 0; i<CityNum; i+>if <strcmp<name, CityNamei> = 0> /比较函数,若相等,则返回i值return i;return -1;/=Edit Info= int SaveSysInfo<> /向程序输入数据FILE *fp; int i, j, total;fp = fopen<CityFile, "w"> /打开CityFile文档fprintf<fp, "%dn", CityNum> /往文档中写城市的数量for <i = 0; i<CityNum; i+>fprintf<fp, "%sn", CityNamei> /往文档中写城市的名字fclose<fp>/将CityFile文档关闭total = 0;fp = fopen<TrainFile, "w">/打开TrainFile文档 for <i = 0; i<CityNum; i+> /计算列车班次的数量total += AdjListi.TrainNum;fprintf<fp, "%dn", total> /往文档中写列车班次的数量for <i = 0; i<CityNum; i+> /for <j = 0; j<AdjListi.TrainNum; j+> /往文档中写列车的车次、始发城市、终点城市fprintf<fp, "%s %s %s ", AdjListi.Trainj.name,CityNamei,CityNameAdjListi.Trainj.EndCity>fprintf<fp, "%2d:%2d %2d:%2d %dn", AdjListi.Trainj.StartTime / 60, /往文档中写AdjListi.Trainj.StartTime % 60,AdjListi.Trainj.StopTime / 60,AdjListi.Trainj.StopTime % 60,AdjListi.Trainj.Cost>fclose<fp> total = 0;fp = fopen<FlightFile, "w">for <i = 0; i<CityNum; i+>total += AdjListi.FlightNum;fprintf<fp, "%dn", total>for <i = 0; i<CityNum; i+>for <j = 0; j<AdjListi.FlightNum; j+>fprintf<fp, "%s %s %s ", AdjListi.Flightj.name,CityNamei,CityNameAdjListi.Flightj.EndCity>fprintf<fp, "%2d:%2d %2d:%2d %dn", AdjListi.Flightj.StartTime / 60,AdjListi.Flightj.StartTime % 60,AdjListi.Flightj.StopTime / 60,AdjListi.Flightj.StopTime % 60,AdjListi.Flightj.Cost>fclose<fp> return 1;int InsertCity<char *Name> /添加城市strcpy<CityNameCityNum, Name>AdjListCityNum.city = CityNum;AdjListCityNum.FlightNum = 0;AdjListCityNum.TrainNum = 0;CityNum+;return 1;int DelCity<char *Name> /删除城市int city, i, j,o=1,k=1;city = SeekCity<Name>printf<"%s",Name>while <true>while <CityNamek != Name>k+;if <k > CityNum>o-;printf<"未找到此城市,请重新输入！">return 0;for <i = city; i < CityNum - 1; i+> /？可能city是从0开始的strcpy<CityNamei, CityNamei + 1>AdjListi.FlightNum = AdjListi + 1.FlightNum;AdjListi.TrainNum = AdjListi + 1.TrainNum;for <j = 0; j < AdjListi.FlightNum; j+> /为什么没有火车的？AdjListi.Flightj.Cost = AdjListi + 1.Flightj.Cost;AdjListi.Flightj.EndCity = AdjListi + 1.Flightj.EndCity;strcpy<AdjListi.Flightj.name, AdjListi + 1.Flightj.name>AdjListi.Flightj.StartTime = AdjListi + 1.Flightj.StartTime;AdjListi.Flightj.StopTime = AdjListi + 1.Flightj.StopTime;CityNum-;return 1;int InsertTrain<char *train, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost>int i, j; /InsertTrain<name,s_city,e_city,s_hour*60+s_minute,e_hour*60+e_minute,cost>i = SeekCity<StartCity>j = SeekCity<EndCity>AdjListi.TrainAdjListi.TrainNum.Cost = cost;AdjListi.TrainAdjListi.TrainNum.EndCity = j;AdjListi.TrainAdjListi.TrainNum.StartTime = StartTime;AdjListi.TrainAdjListi.TrainNum.StopTime = EndTime;strcpy<AdjListi.TrainAdjListi.TrainNum.name, train>AdjListi.TrainNum+; /火车的数加1return 1;int InsertFlight<char *flight, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost>int i, j; i = SeekCity<StartCity>j = SeekCity<EndCity>AdjListi.FlightAdjListi.FlightNum.Cost = cost;AdjListi.FlightAdjListi.FlightNum.EndCity = j;AdjListi.FlightAdjListi.FlightNum.StartTime = StartTime;AdjListi.FlightAdjListi.FlightNum.StopTime = EndTime;strcpy<AdjListi.TrainAdjListi.FlightNum.name, flight>AdjListi.FlightNum+;return 1;int DelPath<char *name>int i, j, flag = 0;for <i = 0; i<CityNum; i+>for <j = 0; j<AdjListi.FlightNum; j+> /注意j是从0开始的if <strcmp<AdjListi.Flightj.name, name> = 0>flag = 1; break;if <flag>for < j<AdjListi.FlightNum - 1; j+> /把删除的航班后的每个航班向前移一位AdjListi.Flightj.Cost = AdjListi.Flightj + 1.Cost;AdjListi.Flightj.EndCity = AdjListi.Flightj + 1.EndCity;strcpy<AdjListi.Flightj.name, AdjListi.Flightj + 1.name>AdjListi.Flightj.StartTime = AdjListi.Flightj + 1.StartTime;AdjListi.Flightj.StopTime = AdjListi.Flightj + 1.StopTime;AdjListi.FlightNum-; break;for <j = 0; j<AdjListi.TrainNum; j+>if <strcmp<AdjListi.Trainj.name, name> = 0>flag = 1; break;if <flag>for < j<AdjListi.TrainNum - 1; j+> /把删除的列车后的每个列车车次都前移一位AdjListi.Trainj.Cost = AdjListi.Trainj + 1.Cost;AdjListi.Trainj.EndCity = AdjListi.Trainj + 1.EndCity;strcpy<AdjListi.Trainj.name, AdjListi.Trainj + 1.name>AdjListi.Trainj.StartTime = AdjListi.Trainj + 1.StartTime;AdjListi.Trainj.StopTime = AdjListi.Trainj + 1.StopTime;AdjListi.TrainNum-; break;return 1;/=Check Info= void Dijkstra_Output<int matxDij_MAXNDij_MAXN, int PreCityDij_MAXN, int p_end, int TravelType>int trackDij_MAXN;int i = 0, j, k, min, tmp, end, cost = 0;j = p_end; tracki+ = j;while <PreCityj >= 0>cost += matxPreCityjj;tracki+ = j = PreCityj;printf<"nTrack Way:">if <!TravelType>for <i-; i>0; i->printf<"n%s:", CityNametracki>end = tracki - 1; min = 32767;for <k = 0; k<AdjListtracki.TrainNum; k+>if <AdjListtracki.Traink.EndCity = end&&min>AdjListtracki.Traink.Cost>min = AdjListtracki.Traink.Cost;tmp = k;printf<"%s", AdjListtracki.Traintmp.name>printf<"%2d:%2d-%2d:%2d", AdjListtracki.Traintmp.StartTime / 60, AdjListtracki.Traintmp.StartTime % 60, AdjListtracki.Traintmp.StopTime / 60, AdjListtracki.Traintmp.StopTime % 60>elsefor <i-; i>0; i->printf<"n%s:", CityNametracki>end = tracki - 1; min = 32767;for <k = 0; k<AdjListtracki.FlightNum; k+>if <AdjListtracki.Traink.EndCity = end&&min>AdjListtracki.Flightk.Cost>min = AdjListtracki.Flightk.Cost;tmp = k;printf<"%s", AdjListtracki.Flighttmp.name>printf<"%2d:%2d-%2d:%2d", AdjListtracki.Flighttmp.StartTime / 60, AdjListtracki.Flighttmp.StartTime % 60, AdjListtracki.Flighttmp.StopTime / 60, AdjListtracki.Flighttmp.StopTime % 60>printf<"n%s: