数据结构课程设计交通咨询系统设计模板.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", AdjLis