数据结构优秀课程设计交通咨询系统标准设计.doc

设计题目<二>：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．函数关键调用关系图

15main（）
8
9
1
12
7
5
4
13
6
3
6
1
2
2
3
7
1
6

（图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<AdjList[track[i]].TrainNum; 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<AdjList[track[i]].FlightNum; 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<CityNum; i++)
{
PreCity[i] = -1;
}
PreCity[p_start] = -2;
while (PreCity[p_end] == -1)
{
min = -1;
for (i = 0; i<CityNum; i++)
if (PreCity[i] != -1)
{
for (j = 0; j<CityNum; j++)
if (PreCity[j] == -1 && matx[i][j]>0 && (min<0 || matx[i][j]<min))
{
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 <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 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<CityNum; 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<CityNum; i++)
{
fprintf(fp, "%s\n", CityName[i]); //往文档中写城市名字
}
fclose(fp);//将CityFile文档关闭
total = 0;
fp = fopen(TrainFile, "w");//打开TrainFile文档
for (i = 0; i<CityNum; i++) //计算列车班次数量
{
total += AdjList[i].TrainNum;
}
fprintf(fp, "%d\n", total); //往文档中写列车班次数量
for (i = 0; i<CityNum; i++) //
{
for (j = 0; j<AdjList[i].TrainNum; 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<CityNum; i++)
{
total += AdjList[i].FlightNum;
}
fprintf(fp, "%d\n", total);
for (i = 0; i<CityNum; i++)
{
for (j = 0; j<AdjList[i].FlightNum; 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_minute,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<CityNum; i++)
{
for (j = 0; j<AdjList[i].FlightNum; j++) //注意j是从0开始
if (strcmp(AdjList[i].Flight[j].name, name) == 0)
{
flag = 1; break;
}
if (flag)
{
for (; j<AdjList[i].FlightNum - 1; 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<AdjList[i].TrainNum; j++)
if (strcmp(AdjList[i].Train[j].name, name) == 0)
{
flag = 1; break;
}
if (flag)
{
for (; j<AdjList[i].TrainNum - 1; 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);
AdjList[i].Train[j].StartTime = AdjList[i].Train[j + 1].StartTime;
AdjList[i].Train[j].StopTime = AdjList[i].Train[j + 1].StopTime;
}
AdjList[i].TrainNum--; break;
}
}
return 1;
}

//==============================================Check Info================================================

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<AdjList[track[i]].TrainNum; 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<AdjList[track[i]].FlightNum; 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!", Ci