数据结构课程设计-公交线路图

#include "model.h" #include "iostream" #include "cstring" #include "map.h" using namespace std; int Length = 0; int* gPath = (int*)malloc(sizeof(int) * 100); void IntialMap(BusMap& g_sMap) { g_sMap.Bus_Num = 0; g_sMap.Station_Num = 0; g_sMap.Route_Num = 0; g_sMap.Buses = NULL; g_sMap.Stations = NULL; } void ClearVisited(bool* Visited, int num) { for (int i = 0; i < num; i++) Visited[i] = false; } int GetStationIndex(BusMap& g_sMap, char* name) { //搜索车站下标，未找到则返回-1 for (int i = 0; i < g_sMap.Station_Num; i++) if (strcmp(g_sMap.Stations[i].StationName, name) == 0) return i; return -1; } int GetBusIndex(BusMap& g_sMap, char* name) { //搜索公交名下标，未找到则返回-1 for (int i = 0; i < g_sMap.Bus_Num; i++) if (strcmp(g_sMap.Buses[i].Name, name) == 0) return i; return -1; } int AddStation(BusMap& g_sMap, char* name) { for (int i = 0; i < g_sMap.Station_Num; i++) if (strcmp(g_sMap.Stations[i].StationName, name) == 0) return i; g_sMap.Stations = (Station*)realloc(g_sMap.Stations, sizeof(Station) * (g_sMap.Station_Num + 1)); Station* pStation = &g_sMap.Stations[g_sMap.Station_Num]; strcpy(pStation->StationName, name); pStation->Routes = NULL; //尚不知晓第一个从此站点出发的路线 g_sMap.Station_Num++; return g_sMap.Station_Num - 1; } int AddBus(BusMap& g_sMap, char* name, int Station1, int Station2) { for(int i=0;i<g_sMap.Bus_Num;i++) if (strcmp(g_sMap.Buses[i].Name, name) == 0) return i; g_sMap.Buses = (Bus*)realloc(g_sMap.Buses, sizeof(Bus) * (g_sMap.Bus_Num + 1)); Bus* pBus = g_sMap.Buses + g_sMap.Bus_Num; strcpy(pBus->Name, name); pBus->Start = Station1; pBus->End = Station2; //尚不清楚插入公交的起点站和终点站 g_sMap.Bus_Num++; return g_sMap.Bus_Num - 1; } int AddRoute(BusMap& g_sMap, char* Station1, char* Station2, int dis, char* BusName) { int IndexOfStation1 = GetStationIndex(g_sMap, Station1); int IndexOfStation2 = GetStationIndex(g_sMap, Station2); if (IndexOfStation1 == -1) { cout << "输入失败，请检查出发站站名" << endl; return -1; } if (IndexOfStation2 == -1) { cout << "输入失败，请检查到达站站名" << endl; return -1; } int IndexOfBus = AddBus(g_sMap, BusName,IndexOfStation1, IndexOfStation2); if (IndexOfBus < 0) { cout << "找不到该公交信息" << endl; return -1; } //后期可以通过查找有无回路判断是否添加线路 Route* pRoute = g_sMap.Stations[IndexOfStation1].Routes; Route* pxRoute= pRoute; while (pRoute != NULL) { if (pRoute->IndexOfStation == IndexOfStation2) { //遍历搜索出发站，到达站相同的路径 if (pRoute->IndexOfBus == IndexOfBus) { bool flag = false; cout << "已有同样的路线信息:" << endl; cout << "且其长度为" << pRoute->Distance << endl; cout << "是否覆盖(1/0):"; cin >> flag; if (flag) { pRoute->Distance = dis; return 0; } } } pxRoute = pRoute; pRoute = pRoute->Next; } //在已有的数据里没有该路径，添加该路径 if (g_sMap.Stations[IndexOfStation1].Routes == NULL) { g_sMap.Stations[IndexOfStation1].Routes = (Route*)malloc(sizeof(Route)); g_sMap.Stations[IndexOfStation1].Routes->Next = NULL; g_sMap.Stations[IndexOfStation1].Routes->IndexOfStation = IndexOfStation2; g_sMap.Stations[IndexOfStation1].Routes->IndexOfBus = IndexOfBus; g_sMap.Stations[IndexOfStation1].Routes->Distance = dis; } else { pxRoute->Next = (Route*)malloc(sizeof(Route)); pxRoute->Next->Next = NULL; pxRoute->Next->IndexOfStation = IndexOfStation2; pxRoute->Next->IndexOfBus = IndexOfBus; pxRoute->Next->Distance = dis; } if (g_sMap.Buses[IndexOfBus].Start == IndexOfStation2) { g_sMap.Buses[IndexOfBus].Start = IndexOfStation1; } if (g_sMap.Buses[IndexOfBus].End == IndexOfStation1) { g_sMap.Buses[IndexOfBus].End = IndexOfStation2; } cout << "本次添加后，线路" << g_sMap.Buses[IndexOfBus].Name << "的起点站和终点站分别为" << endl; cout << g_sMap.Stations[g_sMap.Buses[IndexOfBus].Start].StationName << "--->"; cout << g_sMap.Stations[g_sMap.Buses[IndexOfBus].End].StationName << endl; g_sMap.Route_Num++; return 0; } void CoutStation(BusMap& g_sMap) { for (int i = 0; i < g_sMap.Station_Num; i++) { cout << g_sMap.Stations[i].StationName << endl; } } void CoutRoute(BusMap& g_sMap) { Route* pRoute = NULL; for (int i = 0; i < g_sMap.Station_Num; i++) { pRoute = g_sMap.Stations[i].Routes; while (pRoute != NULL) { cout << g_sMap.Stations[i].StationName << "-->"<<g_sMap.Stations[pRoute->IndexOfStation].StationName; cout << " Distance: " << pRoute->Distance << " Bus: " << g_sMap.Buses[pRoute->IndexOfBus].Name << endl; pRoute = pRoute->Next; } } } void CoutBus(BusMap& g_sMap) { for (int i = 0; i < g_sMap.Bus_Num; i++) { cout << g_sMap.Buses[i].Name << endl; } } void FreeBus(BusMap& g_sMap) { if (g_sMap.Bus_Num > 0) free(g_sMap.Buses); } void FreeStation(BusMap& g_sMap) { if (g_sMap.Station_Num > 0) { Route* pRoute = NULL, * pxRoute = NULL; for (int r = 0; r < g_sMap.Station_Num; r++) { pRoute = g_sMap.Stations[r].Routes; while (pRoute != NULL) { pxRoute = pRoute->Next; free(pRoute); pRoute = pxRoute; } } } } int FindRoute(BusMap& g_sMap, bool* Visited, int IndexOfStation1, int IndexOfStation2, int* Path, int& n, int& length) { Visited[IndexOfStation1] = true; Route* pRoute = g_sMap.Stations[IndexOfStation1].Routes; while (pRoute != NULL) { if (Visited[pRoute->IndexOfStation] == false) { Path[n++] = pRoute->IndexOfStation; length += pRoute->Distance; if (pRoute->IndexOfStation == IndexOfStation2) { if (length < Length) { Length = length; gPath[0] = n; for (int i = 1; i <= n; i++) { gPath[i] = Path[i - 1]; } } } else FindRoute(g_sMap, Visited, pRoute->IndexOfStation, IndexOfStation2, Path, n, length); length -= pRoute->Distance; n--; } pRoute = pRoute->Next; } Visited[IndexOfStation1] = false; return 0; } int SearchOfRoute(BusMap& g_sMap, char* Station1, char* Station2) { int IndexOfStation1 = GetStationIndex(g_sMap, Station1); int IndexOfStation2 = GetStationIndex(g_sMap, Station2); if (IndexOfStation1 < 0) { cout << "输入失败，请检查出发站站名" << endl; return -1; } if (IndexOfStation2 < 0) { cout << "输入失败，请检查到达站站名" << endl; return -1; } if (IndexOfStation1 == IndexOfStation2) { cout << "两站点重合" << endl; } bool* Visited = (bool*)malloc(sizeof(bool) * g_sMap.Station_Num); ClearVisited(Visited, g_sMap.Station_Num); int* Path = (int*)malloc(sizeof(int) * g_sMap.Station_Num); int cnt = 0, length = 0; Length = 50000; FindRoute(g_sMap, Visited, IndexOfStation1, IndexOfStation2, Path, cnt, length); if (Length < 50000) { cout << "两路线可达, 且其中最短路径经过站点数为" << gPath[0] + 1 << endl; cout << "最短经过的路径为" << g_sMap.Stations[IndexOfStation1].StationName; for (int j = 1; j < gPath[0] + 1; j++) { cout << "--->" << g_sMap.Stations[gPath[j]].StationName; } cout << endl; cout << "最短路径长度为" << Length << endl; } else { cout << "不可达" << endl; } free(Visited); free(Path); return 0; } void SearchOfBus(BusMap& g_sMap, char* Busname) { int IndexOfBus = GetBusIndex(g_sMap, Busname); if (IndexOfBus < 0) { cout << "无此公交信息，请检查并重输." << endl; return; } cout << "公交：" << g_sMap.Stations[g_sMap.Buses[IndexOfBus].Start].StationName; cout << "--->" << g_sMap.Stations[g_sMap.Buses[IndexOfBus].End].StationName << endl; int cnt = 1; int length = 0; int IndexOfStation1 = g_sMap.Buses[IndexOfBus].Start; cout << g_sMap.Stations[IndexOfStation1].StationName; Route* pRoute = g_sMap.Stations[IndexOfStation1].Routes; while (pRoute != NULL) { if (pRoute->IndexOfBus == IndexOfBus) { cout << "--->" << g_sMap.Stations[pRoute->IndexOfStation].StationN