数据结构课程设计交通咨询系统设计说明
设计题目<二>：7.3.4交通咨询系统设计P160
一、设计要求
1．问题描述
根据不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅行的旅客希望旅费尽可能的少，而老年人则要求中转次数少。模拟一个全国城市之间的咨询交通程序，为旅客提供两种或三种最优的交通路线。
2．需求分析
二、概要设计
1．主界面设计
（图2.1“交通咨询系统”主菜单）
2．存储结构设计
本系统采用图结构类型存储抽象交通咨询系统的信息。
typedef struct TrafficNode
{
char name[MAX_STRING_NUM]; //班次 //MAX_STRING_NUM最为10
int StartTime, StopTime; //起止时间
int EndCity; //该有向边指向的顶点在数组中的位置，即该城市编号
int Cost; //票价
} TrafficNodeDat;
typedef struct VNode
{
CityType city;
int TrainNum, FlightNum; //标记下面Train数组和Flight数组里元素个数
TrafficNodeDat Train[MAX_TRAFFIC_NUM]; //数组成员为结构体，记录了到达城市、起止时间、票价和班次
TrafficNodeDat Flight[MAX_TRAFFIC_NUM];
// int Cost; //遍历时到达该城市的耗费（时间或者费用）
} VNodeDat;
typedef struct PNode
{
int City;
int TraNo;
} PNodeDat;
3．系统功能设计
（1）添加城市。添加一个城市的名称
（2）删除城市。输入一个城市名称，删除该城市。
（3）添加交通路线。输入起始城市、终点城市、航班或火车、车次、起始时间、终点时间和票价
（4）删除交通路线。输入火车或飞机的班次删除该交通路线。
（5）查询最小费用路线。输入起始城市、终点城市、航班或火车、车次、起始时间、终点时间查询最小费用路线。
三、模块设计
1．模块设计
（图2.2 模块调用示意图）
2．系统子程序及功能设计
（1）int ShowMenu()//主菜单
（2）void CopyRight()
（3）int SeekCity(char *name) //寻找城市
（4）int InsertCity(char *Name) //添加城市
（5）int SaveSysInfo() //向程序输入数据
（6）int DelCity(char *Name) //删除城市
（7）int InsertTrain(char *train, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost)//添加火车路线
（8）int InsertFlight(char *flight, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost)//添加飞机航线
（9）int DelPath(char *name)//删除路线
（10）void Dijkstra(int matx[Dij_MAXN][Dij_MAXN], int p_start, int p_end, int TravelType)
（11）int InitSysData()//存储数据
（12）int SearchMinTime(CityType City, CityType EndCity, int CurTime, int curPathNo, int TravelType)//查询最短时间
（13）int CalcMinTime(int StartCity, int EndCity, int TravelType) //显示最短时间
（14）int CalcMinCost(int StartCity, int EndCity, int TravelType)//最少花费
（15）int main()//主函数
3．函数主要调用关系图
（图2.3函数主要调用关系图）
四、详细设计
1．数据类型定义
（1）全局变量的定义
typedef short int CityType;//CityType 定义短整形的变量
typedef struct TrafficNode
{
char name[MAX_STRING_NUM]; //班次 //MAX_STRING_NUM最为10
int StartTime, StopTime; //起止时间
int EndCity; //该有向边指向的顶点在数组中的位置，即该城市编号
int Cost; //票价
} TrafficNodeDat;
typedef struct VNode
{
CityType city;
int TrainNum, FlightNum; //标记下面Train数组和Flight数组里元素个数
TrafficNodeDat Train[MAX_TRAFFIC_NUM]; //数组成员为结构体，记录了到达城市、起止时间、票价和班次
TrafficNodeDat Flight[MAX_TRAFFIC_NUM];
// int Cost; //遍历时到达该城市的耗费（时间或者费用）
} VNodeDat;
typedef struct PNode
{
int 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 matx[Dij_MAXN][Dij_MAXN], int
PreCity[Dij_MAXN], int p_end, int TravelType)
{
int track[Dij_MAXN];
int i = 0, j, k, min, tmp, end, cost = 0;
j = p_end; track[i++] = j;
while (PreCity[j] >= 0)
{
cost += matx[PreCity[j]][j];
track[i++] = j = PreCity[j];
}
printf("\nTrack Way:");
if (!TravelType)
{
for (i--; i>0; i--)
{
printf("\n%s:", CityName[track[i]]);
end = track[i - 1]; min = 32767;
for (k = 0; k if (AdjList[track[i]].Train[k].EndCity == end&&min>AdjList[track[i]].Train[k].Cost) { min = AdjList[track[i]].Train[k].Cost; tmp = k; } printf("%s", AdjList[track[i]].Train[tmp].name); printf("%2d:%2d-%2d:%2d", AdjList[track[i]].Train[tmp].StartTime / 60, AdjList[track[i]].Train[tmp].StartTime % 60, AdjList[track[i]].Train[tmp].StopTime / 60, AdjList[track[i]].Train[tmp].StopTime % 60); } } else { for (i--; i>0; i--) { printf("\n%s:", CityName[track[i]]); end = track[i - 1]; min = 32767; for (k = 0; k if (AdjList[track[i]].Train[k].EndCity == end&&min>AdjList[track[i]].Flight[k].Cost) { min = AdjList[track[i]].Flight[k].Cost; tmp = k; } printf("%s", AdjList[track[i]].Flight[tmp].name); printf("%2d:%2d-%2d:%2d", AdjList[track[i]].Flight[tmp].StartTime / 60, AdjList[track[i]].Flight[tmp].StartTime % 60, AdjList[track[i]].Flight[tmp].StopTime / 60, AdjList[track[i]].Flight[tmp].StopTime % 60); } } printf("\n%s: DESTINATION!", CityName[track[0]]); printf("\nMin Cost : %d\n", cost); } void Dijkstra(int matx[Dij_MAXN][Dij_MAXN], int p_start, int p_end, int TravelType) { int PreCity[Dij_MAXN]; //PreCity[i]==-1,never used; //PreCity>0,the precity of City i int i, j, min, pre, pos; for (i = 0; i { PreCity[i] = -1; } PreCity[p_start] = -2; while (PreCity[p_end] == -1) { min = -1; for (i = 0; i if (PreCity[i] != -1) { for (j = 0; j if (PreCity[j] == -1 && matx[i][j]>0 && (min<0 || matx[i][j] { pre = i; pos = j; min = matx[i][j]; } } PreCity[pos] = 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 #include #include #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 TrafficNode { char name[MAX_STRING_NUM]; //班次 //MAX_STRING_NUM最为10 int StartTime, StopTime; //起止时间 int EndCity; //该有向边指向的顶点在数组中的位置，即该城市编号 int Cost; //票价 } TrafficNodeDat; typedef struct VNode { CityType city; int TrainNum, FlightNum; //标记下面Train数组和Flight数组里元素个数 TrafficNodeDat Train[MAX_TRAFFIC_NUM]; //数组成员为结构体，记录了到达城市、起止时间、票价和班次 TrafficNodeDat Flight[MAX_TRAFFIC_NUM]; // int Cost; //遍历时到达该城市的耗费（时间或者费用） } VNodeDat; typedef struct PNode { int City; int TraNo; } PNodeDat; VNodeDat AdjList[MAX_VERTEX_NUM]; char CityName[MAX_VERTEX_NUM][MAX_STRING_NUM]; //城市名，采用第一下标为该城市在本程序中的编号 int CityNum; //城市数目 PNodeDat Path[MAX_VERTEX_NUM]; //存储临时最小时间路径 PNodeDat MinPath[MAX_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 { if (strcmp(name, CityName[i]) == 0) //比较函数，若相等，则返回i值 { return i; } } return -1; } //=============================================Edit Info==================================================== int SaveSysInfo() //向程序输入数据 { FILE *fp; int i, j, total; fp = fopen(CityFile, "w"); //打开CityFile文档 fprintf(fp, "%d\n", CityNum); //往文档中写城市的数量 for (i = 0; i { fprintf(fp, "%s\n", CityName[i]); //往文档中写城市的名字} fclose(fp);//将CityFile文档关闭 total = 0; fp = fopen(TrainFile, "w");//打开TrainFile文档 for (i = 0; i { total += AdjList[i].TrainNum; } fprintf(fp, "%d\n", total); //往文档中写列车班次的数量 for (i = 0; i { for (j = 0; j { fprintf(fp, "%s %s %s ", AdjList[i].Train[j].name, CityName[i], CityName[AdjList[i].Train[j].EndCity]); fprintf(fp, "%2d:%2d %2d:%2d %d\n", AdjList[i].Train[j].StartTime / 60, //往文档中写 AdjList[i].Train[j].StartTime % 60, AdjList[i].Train[j].StopTime / 60, AdjList[i].Train[j].StopTime % 60, AdjList[i].Train[j].Cost); } } fclose(fp); total = 0; fp = fopen(FlightFile, "w"); for (i = 0; i { total += AdjList[i].FlightNum; } fprintf(fp, "%d\n", total); for (i = 0; i { for (j = 0; j { fprintf(fp, "%s %s %s ", AdjList[i].Flight[j].name, CityName[i], CityName[AdjList[i].Flight[j].EndCity]); fprintf(fp, "%2d:%2d %2d:%2d %d\n", AdjList[i].Flight[j].StartTime / 60, AdjList[i].Flight[j].StartTime % 60, AdjList[i].Flight[j].StopTime / 60, AdjList[i].Flight[j].StopTime % 60, AdjList[i].Flight[j].Cost); } } fclose(fp); return 1; } int InsertCity(char *Name) //添加城市 { strcpy(CityName[CityNum], Name); AdjList[CityNum].city = CityNum; AdjList[CityNum].FlightNum = 0; AdjList[CityNum].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 (CityName[k] != Name) { k++; } if (k > CityNum) { o--; printf("未找到此城市，请重新输入！"); return 0; } for (i = city; i < CityNum - 1; i++) //？？？可能city是从0开始的 { strcpy(CityName[i], CityName[i + 1]); AdjList[i].FlightNum = AdjList[i + 1].FlightNum; AdjList[i].TrainNum = AdjList[i + 1].TrainNum; for (j = 0; j < AdjList[i].FlightNum; j++) //为什么没有火车的？？ { AdjList[i].Flight[j].Cost = AdjList[i + 1].Flight[j].Cost; AdjList[i].Flight[j].EndCity = AdjList[i + 1].Flight[j].EndCity; strcpy(AdjList[i].Flight[j].name, AdjList[i + 1].Flight[j].name); AdjList[i].Flight[j].StartTime = AdjList[i + 1].Flight[j].StartTime; AdjList[i].Flight[j].StopTime = AdjList[i + 1].Flight[j].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_minut e,cost); i = SeekCity(StartCity); j = SeekCity(EndCity); AdjList[i].Train[AdjList[i].TrainNum].Cost = cost; AdjList[i].Train[AdjList[i].TrainNum].EndCity = j; AdjList[i].Train[AdjList[i].TrainNum].StartTime = StartTime; AdjList[i].Train[AdjList[i].TrainNum].StopTime = EndTime; strcpy(AdjList[i].Train[AdjList[i].TrainNum].name, train); AdjList[i].TrainNum++; //火车的数加1 return 1; } int InsertFlight(char *flight, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost) { int i, j; i = SeekCity(StartCity); j = SeekCity(EndCity); AdjList[i].Flight[AdjList[i].FlightNum].Cost = cost; AdjList[i].Flight[AdjList[i].FlightNum].EndCity = j; AdjList[i].Flight[AdjList[i].FlightNum].StartTime = StartTime; AdjList[i].Flight[AdjList[i].FlightNum].StopTime = EndTime; strcpy(AdjList[i].Train[AdjList[i].FlightNum].name, flight); AdjList[i].FlightNum++; return 1; } int DelPath(char *name) { int i, j, flag = 0; for (i = 0; i { for (j = 0; j if (strcmp(AdjList[i].Flight[j].name, name) == 0) { flag = 1; break; } if (flag) { for (; j { AdjList[i].Flight[j].Cost = AdjList[i].Flight[j + 1].Cost; AdjList[i].Flight[j].EndCity = AdjList[i].Flight[j + 1].EndCity; strcpy(AdjList[i].Flight[j].name, AdjList[i].Flight[j + 1].name); AdjList[i].Flight[j].StartTime = AdjList[i].Flight[j + 1].StartTime; AdjList[i].Flight[j].StopTime = AdjList[i].Flight[j + 1].StopTime; } AdjList[i].FlightNum--; break; } for (j = 0; j if (strcmp(AdjList[i].Train[j].name, name) == 0) { flag = 1; break; } if (flag) { for (; j { AdjList[i].Train[j].Cost = AdjList[i].Train[j + 1].Cost; AdjList[i].Train[j].EndCity = AdjList[i].Train[j + 1].EndCity; strcpy(AdjList[i].Train[j].name, AdjList[i].Train[j + 1].name);