首页 > 分享 > 数据结构课程设计

数据结构课程设计

花匠小妙招
2026-04-08 00:03

一、问题描述。
本次课程设计选择题目为公交线路图的构建和查询
1.使用图模拟城市公交系统，即站点和路线分别为对应有向图的数据结构顶点和边，采用邻接表的存储方式来构建和存放图。
2.公交路线图中满足一个站点上有存在多辆公交车经过
3.每条公交车都会经过多个站点，即一条公交之间需要多条边相连。
4.对于站点和公交路线等信息需要存放在文件中
对于正确创建的公交路线能够查询公交路线，站点信息，两站之前有无存在路径，同时可以适当对公交路线进行修改，来满足相应需求。

二、设计。
数据格式
buses.txt文件中存放的是公交车信息，每一行分别对应着公交车车名，公交车编号，公交车起始站点，公交车终止站点

stations.txt文件存放的是站点信息，每一行分别对应着站点编号，站点名字

routes.txt文件存放的是行驶该路线对应的公交车编号，路线起点站索引号，路线终点站索引号，两站点之前距离(单位m)。

数据结构
公交路线图采用的是邻接表（有向图）的存储方式，具体结构如下：

公交车的数据结构 1

typedef struct BUS {int bus_no;//公交编号 char* name;//公交名int Start;//起点int End;//终点 }BUS;

cpp

1234567

公交车站的数据结构 1

typedef struct Station { int station_no;//站点编号 char* station;//站点名 struct Route *route;//从该站点出发所有下行路线的链域 }Station;

cpp

123456

公交路线的数据结构

typedef struct Route { int route_no;//路线编号//公交索引号 int station_no1;//站点编号1 int station_no2;//站点编号2 int distance;//两站之间的距离 struct Route *next;//起始站点相同的，下一条路线 }Route;

cpp

12345678

公交路线图的数据结构

typedef struct BusMap { BUS *buses;//公交路线数组 Station *station;//站点数组 Route *route;//路线数组//为了让他存储跟方便 int station_num;//站点数 int bus_num;//公交路线数量 int route_num;//两站之前边数，即路数 }BusMap;

cpp

123456789

查询路径的数据结构

typedef struct Path //只有一个path结点 { Route route[MAX]; int transfer; //换乘次数 int alldist; //路线总路程 int top; }Path;

cpp

1234567

程序设计
分为main.cpp//主函数
ManageMenu.cpp//菜单管理类.cpp文件
ManageMenu.h//菜单管理类.h文件
Map.cpp//有关图的所有函数
Map.h//图.h文件
MapModel.h// 结构体变量存放位置

程序公交路线图相关函数

class Map { public: Map(); void CreateMap(); void LoadMap(); void ReLoadMap();//用于删除重新构图 void readtxt_bus();//读取文件中bus创建 bool initializebus();//判断文件中是否存在buses文件 int getbusnum();//获得buses中bus数量 void bussave();//保存至文件中 void stationsave();//保存至文件中 bool initializeStation(); int getstationnum(); void readtxt_station(); void routesave();//保存至文件中 bool initializeRoute(); int getroutenum(); void readtxt_route(); int FindBus(char* bus);//查找公交是否存在，有则返回索引号 int FindStation(char* station);//查找站点是否存在，有则返回索引号 int GetStation(char *station);//若无此站点则创建后返回索引号 int Finddistance( char* pStart,char* pEnd );//返回一条路线的距离 void AddRoute( char* pBus, char* pStart,char* pEnd,int distance);//添加路线 void QueryBus(char *pBus);//查询公交 int QueryStation(char *station);//查询站点 void ClearVisited();//遍历所有站点中所有的边，将边中的visited值设为false void Initialize(Path *&p,char *s,char *e); //先初始化 void Push(Path *&p,Route *s); //将路段压入栈,记录相关信息 void Pop(Path *&p,Route *&s); //将路段从栈弹出 void PrintPath(Path *p); //输出可行线路 void QueryPath(char *pStart,char *pEnd); void QueryPath();//路径查询 void AddStart(char *bus);//公交车添加起点 void AddEnd(char *bus);//公交添加终点 void deleteroute();//删除起始和终点路线 void deletestation();//删除任意一站点 void changestation();//修改站点名字 void changedistance();//修改路线距离 ~Map(); private: bool m_busfileIsEmpty;//判断buses.txt文件是否为空的变量 bool m_stationfileIsEmpty;//判断stations.txt文件是否为空的变量 bool m_routefileIsEmpty;//判断routes.txt文件是否为空的变量 };

cpp

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

------------------------------ManageMenu.h--------------------------------------------- #ifndef MANAGEMENU_H #define MANAGEMENU_H #include <iostream> #include <stdlib.h> #include "Map.h" using namespace std; class ManageMenu { public: ManageMenu(); void ShowMenu();//展示主菜单 void Exitsystem();//退出程序 ~ManageMenu(); Map map1; }; #endif // MANAGEMENU_H

cpp

1234567891011121314151617181920

------------------------------------MapModel.h--------------------------------------- #ifndef MAPMODEL_H #define MAPMODEL_H #define MAX 100 using namespace std; typedef struct BUS { int bus_no;//公交编号 char* name;//公交名 int Start;//起点 int End;//终点 }BUS; typedef struct Station { int station_no;//站点编号 char* station;//站点名 struct Route *route;//从该站点出发所有下行路线的链域 }Station; typedef struct Route { int route_no;//路线编号//公交索引号 int station_no1;//站点编号1 int station_no2;//站点编号2 int distance;//两站之间的距离 //bool visited;//遍历时候的标志符 struct Route *next;//起始站点相同的，下一条路线 }Route; typedef struct BusMap { BUS *buses;//公交路线数组 Station *station;//站点数组 Route *route;//路线数组//为了让他存储跟方便 int station_num;//站点数 int bus_num;//公交路线数量 int route_num;//两站之前边数，即路数 }BusMap; typedef struct Path //只有一个path结点 { Route route[MAX]; int transfer; //换乘次数 int alldist; //路线总路程 int top; }Path; #endif // MAP_H

cpp

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

------------------------------------Map.h--------------------------------------------------- #ifndef MAP_H #define MAP_H #include "MapModel.h" #include <iostream> #include <fstream> #include <malloc.h> #include <string.h> using namespace std; class Map { public: Map(); void CreateMap(); void LoadMap(); void ReLoadMap();//用于删除重新构图 void readtxt_bus();//读取文件中bus创建 bool initializebus();//判断文件中是否存在buses文件 int getbusnum();//获得buses中bus数量 void bussave();//保存至文件中void stationsave(); bool initializeStation(); int getstationnum(); void readtxt_station();void routesave(); bool initializeRoute(); int getroutenum(); void readtxt_route();int FindBus(char* bus);//查找公交是否存在，有则返回索引号 int FindStation(char* station);//查找站点是否存在，有则返回索引号 int GetStation(char *station);//若无此站点则创建后返回索引号 int Finddistance( char* pStart,char* pEnd );//返回一条路线的距离 void AddRoute( char* pBus, char* pStart,char* pEnd,int distance); void QueryBus(char *pBus);//查询公交 int QueryStation(char *station);//查询站点 void ClearVisited();//遍历所有站点中所有的边，将边中的visited值设为false void Initialize(Path *&p,char *s,char *e); //先初始化 void Push(Path *&p,Route *s); //将路段压入栈,记录相关信息 void Pop(Path *&p,Route *&s); //将路段从栈弹出 void PrintPath(Path *p); //输出可行线路 void QueryPath(char *pStart,char *pEnd); void QueryPath();//路径查询 void AddStart(char *bus);//公交车添加起点 void AddEnd(char *bus);//公交添加终点 void deleteroute();//删除起始和终点路线 void deletestation();//删除任意一站点 void changestation();//修改站点名字 void changedistance();//修改路线距离 ~Map(); private: bool m_busfileIsEmpty;//判断buses.txt文件是否为空的变量 bool m_stationfileIsEmpty;//判断stations.txt文件是否为空的变量 bool m_routefileIsEmpty;//判断routes.txt文件是否为空的变量 }; #endif // MAP_H

cpp

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657

------------------------------------main.cpp--------------------------------------------------- #include <iostream> #include <stdlib.h> #include "ManageMenu.h" using namespace std; int main(){ ManageMenu Menu;//创建一个管理类对象 int choice=0;//用户选择 while(true){ Menu.ShowMenu(); cout << "请输入你的选择："; cin>>choice; system("cls"); switch(choice) { case 1: { cout<<">---- 在公交路线图中添加站点 ----<"<<endl; cout<<">----仅能输入起点或终点，添加起始站点输入0，添加终止站点输入1 ----<"<<endl; int flag; cout<<">-----请输入起点或终点0/1-----<"<<endl; cin>>flag; char bus[20]; cout<<"请输入添加的公交路线公交车车名："<<endl; cin>>bus; if(flag==0){ Menu.map1.AddStart(bus); } else if(flag==1) { Menu.map1.AddEnd(bus); } else{ cout<<">-----输入有误-----<"<<endl; break; } system("pause"); system("cls"); break; } case 2: Menu.map1.deletestation(); system("pause"); system("cls"); break; case 3: Menu.map1.changestation(); system("pause"); system("cls"); break; case 4: Menu.map1.deleteroute(); system("pause"); system("cls"); break; case 5: Menu.map1.changedistance(); system("pause"); system("cls"); break; case 6: cout<<">---- 在公交路线图中查询公交车名字 ----<"<<endl; char bus[20]; cout<<"请输入查询公交车名字"<<endl;//查询公交车 cin>>bus; Menu.map1.QueryBus(bus); system("pause"); system("cls"); break; case 7: cout<<">---- 在公交路线图中查询站点名字 ----<"<<endl; char station[20]; cout<<"请输入查询站点名字："<<endl;//查询站点 cin>>station; Menu.map1.QueryStation(station); system("pause"); system("cls"); break; case 8: cout<<">---- 在公交路线图中查询路径 ----<"<<endl; Menu.map1.QueryPath();//查询路径 system("pause"); system("cls"); break; case 0: Menu.Exitsystem(); break; default:cout<<">-----请输入正确的指令-----<"<<endl; system("pause"); system("cls"); break; } } return 0; }

cpp

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687

------------------------------------ManageMenu.cpp-------------------------------------------- #include "ManageMenu.h" ManageMenu::ManageMenu() { } void ManageMenu::ShowMenu() { cout <<"*****************************************************" << endl; cout <<"*---------------------------------------------------*" << endl; cout <<"*| 公交管理系统 |*" << endl; cout <<"*---------------------------------------------------*" << endl; cout <<"*---------------------------------------------------*" << endl; cout <<"*---- (1)添加站点 -----*" << endl; cout <<"*---- (2)删除站点 -----*" << endl; cout <<"*---- (3)修改站点 -----*" << endl; cout <<"*---- (4)删除线路信息 -----*" << endl; cout <<"*---- (5)修改线路信息 -----*" << endl; cout <<"*---- (6)查询公交 -----*" << endl; cout <<"*---- (7)查询站点 -----*" << endl; cout <<"*---- (8)查询路径 -----*" << endl; cout <<"*---- (0)退出系统 -----*" << endl; cout <<"*---------------------------------------------------*" << endl; cout <<"*****************************************************" << endl; } void ManageMenu::Exitsystem() { cout <<"欢迎下次使用"<<endl; system("pause"); exit(0); } ManageMenu::~ManageMenu() { }

cpp

12345678910111213141516171819202122232425262728293031323334353637383940

------------------------------------Map.cpp--------------------------------------------------- #include "Map.h" BusMap g_BusMap;//全局变量，保存公交地图信息 char STATIONNAME[MAX][MAX];//存储站点名称 int STATION[MAX];//存储站点编号 int ROUTES[MAX][4];//存储路段信息 char BUS_NAME[MAX][MAX];//存储公交线路名称 int BUSES[MAX][3];//存储公交线路信息 bool visited[MAX]; //记录站点是否被访问过 int sum=0; //记录符合要求的路线数,初始为0 Path *path; Map::Map(){ LoadMap(); } void Map::bussave(){ ofstream M_bus; M_bus.open("buses.txt",ios::out); for( int i=0 ; i<g_BusMap.bus_num ; i++) { M_bus << g_BusMap.buses[i].name <<" " << g_BusMap.buses[i].bus_no <<" " << g_BusMap.buses[i].Start <<" " << g_BusMap.buses[i].End <<endl; } M_bus.close(); } bool Map::initializebus(){ //这里要加一个m_busfileIsEmpty ifstream M_bus("buses.txt"); //文件不存在 if(!M_bus.is_open()) { //初始化文件为空的标志 m_busfileIsEmpty=true; M_bus.close(); return m_busfileIsEmpty; } //文件存在,但是数据为空 char ch; M_bus>>ch; if(M_bus.eof()) { //初始化文件为空的标志 m_busfileIsEmpty=true; M_bus.close(); return m_busfileIsEmpty; } m_busfileIsEmpty=false; M_bus.close(); return m_busfileIsEmpty; } int Map::getbusnum(){ ifstream M_bus; M_bus.open("buses.txt",ios::in); int busno;//公交编号 string busname;//计数读入公交名 int busStart;//计数读入起点 int busEnd;//计数读入终点 int busnum=0; while( M_bus>>busno && M_bus>>busname && M_bus>>busStart && M_bus>>busEnd ){ busnum++; } M_bus.close(); return busnum; } void Map::readtxt_bus(){ m_busfileIsEmpty=initializebus();//首先判断文件是否为空 if(m_busfileIsEmpty==true){//实现M_bus文件的初始化 //cout<<"文件不存在或者文件内无内容，请重新添加数据"<<endl; g_BusMap.bus_num=0; return; } else{ g_BusMap.bus_num=getbusnum(); ifstream M_bus; M_bus.open("buses.txt",ios::out); int busno;//公交编号 string busname;//计数读入公交名 int busStart;//计数读入起点 int busEnd;//计数读入终点 int index=0;//计数赋值 char a[MAX]; while( M_bus>>busname && M_bus>>busno && M_bus>>busStart && M_bus>>busEnd ){ strcpy(a,busname.c_str());//将string转为char strcpy(BUS_NAME[index],a); BUSES[index][0]=busno; BUSES[index][1]=busStart; BUSES[index][2]=busEnd; index++; } M_bus.close(); } } void Map::stationsave(){ ofstream M_station; M_station.open("stations.txt",ios::out); for( int i=0 ; i<g_BusMap.station_num ; i++) { M_station << g_BusMap.station[i].station_no <<" " << g_BusMap.station[i].station <<endl; } M_station.close(); } bool Map::initializeStation(){ ifstream M_station("stations.txt"); //文件不存在 if(!M_station.is_open()) { //初始化文件为空的标志 m_stationfileIsEmpty=true; M_station.close(); return m_stationfileIsEmpty; } //文件存在,但是数据为空 char ch; M_station>>ch; if(M_station.eof()) { //初始化文件为空的标志 m_stationfileIsEmpty=true; M_station.close(); return m_stationfileIsEmpty; } m_stationfileIsEmpty=false; M_station.close(); return m_stationfileIsEmpty; } int Map::getstationnum(){ ifstream M_station; M_station.open("stations.txt",ios::in); int Station_no; string Station; int stationnum=0;//计数器 while( M_station>>Station_no && M_station>>Station ){ stationnum++; } M_station.close(); return stationnum; } void Map::readtxt_station(){ m_stationfileIsEmpty=initializeStation();//首先判断文件是否为空 if(m_stationfileIsEmpty==true){//实现M_bus文件的初始化 //cout<<"文件不存在或者文件内无内容，请重新添加数据"<<endl; g_BusMap.station_num=0; return; } else{ g_BusMap.station_num=getstationnum(); ifstream M_station; M_station.open("stations.txt",ios::out); int Station_no; string Station; int index=0;//计数赋值 char a[MAX]; while( M_station>>Station_no && M_station>>Station){ strcpy(a,Station.c_str());//将string转为char strcpy(STATIONNAME[index],a); STATION[index]=Station_no; index++; } M_station.close(); } } void Map::routesave(){ ofstream M_route; M_route.open("routes.txt",ios::out); for( int i=0 ; i<g_BusMap.route_num; i++) { M_route << g_BusMap.route[i].route_no<<" " << g_BusMap.route[i].station_no1 <<" " << g_BusMap.route[i].station_no2 <<" " << g_BusMap.route[i].distance <<endl; } M_route.close(); } bool Map::initializeRoute(){ ifstream M_route("routes.txt"); //文件不存在 if(!M_route.is_open()) { //初始化文件为空的标志 m_routefileIsEmpty=true; M_route.close(); return m_routefileIsEmpty; } //文件存在,但是数据为空 char ch; M_route>>ch; if(M_route.eof()) { //初始化文件为空的标志 m_routefileIsEmpty=true; M_route.close(); return m_routefileIsEmpty; } m_routefileIsEmpty=false; M_route.close(); return m_routefileIsEmpty; } int Map::getroutenum(){ ifstream M_route; M_route.open("routes.txt",ios::in); int Route_no;//路线编号 int Station_no1;//站点编号1 int Station_no2;//站点编号2 int Distance;//两站之间的距离 int routenum=0;//计数器 while( M_route>>Route_no && M_route>>Station_no1 && M_route>>Station_no2 && M_route>>Distance ){ routenum++; } M_route.close(); return routenum; } void Map::readtxt_route(){ m_routefileIsEmpty=initializeRoute();//首先判断文件是否为空 if(m_routefileIsEmpty==true){//实现M_bus文件的初始化 //cout<<"文件不存在或者文件内无内容，请重新添加数据"<<endl; g_BusMap.route_num=0; return; } else{ g_BusMap.route_num=getroutenum(); ifstream M_route; M_route.open("routes.txt",ios::out); int Route_no;//路线编号 int Station_no1;//站点编号1 int Station_no2;//站点编号2 int Distance;//两站之间的距离 int index=0;//计数赋值 while( M_route>>Route_no && M_route>>Station_no1 && M_route>>Station_no2 && M_route>>Distance ){ ROUTES[index][0]=Route_no; ROUTES[index][1]=Station_no1; ROUTES[index][2]=Station_no2; ROUTES[index][3]=Distance; index++; } } } void Map::CreateMap(){ g_BusMap.bus_num=getbusnum(); g_BusMap.buses=(BUS*)malloc(sizeof(BUS)*g_BusMap.bus_num); for(int i=0;i<g_BusMap.bus_num;i++) { g_BusMap.buses[i].bus_no=BUSES[i][0]; g_BusMap.buses[i].name=BUS_NAME[i]; g_BusMap.buses[i].Start=BUSES[i][1]; g_BusMap.buses[i].End=BUSES[i][2]; } g_BusMap.station_num=getstationnum(); g_BusMap.station=(Station*)malloc(sizeof(Station)*g_BusMap.station_num); for(int i=0;i<g_BusMap.station_num;i++) { g_BusMap.station[i].station=STATIONNAME[i]; g_BusMap.station[i].station_no=STATION[i]; g_BusMap.station[i].route=NULL; } g_BusMap.route_num=getroutenum(); g_BusMap.route=(Route*)malloc(sizeof(Route)*g_BusMap.route_num); for(int i=0;i<g_BusMap.route_num;i++) { g_BusMap.route[i].route_no=ROUTES[i][0]; g_BusMap.route[i].station_no1=ROUTES[i][1]; g_BusMap.route[i].station_no2=ROUTES[i][2]; g_BusMap.route[i].distance=ROUTES[i][3]; g_BusMap.route[i].next=NULL; } } void Map::LoadMap(){ readtxt_bus(); readtxt_station(); readtxt_route(); CreateMap(); for( int i=0 ; i<g_BusMap.route_num ; i++ ){ int j=g_BusMap.route[i].station_no1; if(g_BusMap.station[j].route==NULL){ g_BusMap.station[j].route=g_BusMap.route+i; } else{ g_BusMap.route[i].next=g_BusMap.station[j].route; g_BusMap.station[j].route=g_BusMap.route+i; } } } void Map::ReLoadMap(){ g_BusMap.buses=(BUS*)malloc(sizeof(BUS)*g_BusMap.bus_num); for(int i=0;i<g_BusMap.bus_num;i++) { g_BusMap.buses[i].bus_no=BUSES[i][0]; g_BusMap.buses[i].name=BUS_NAME[i]; g_BusMap.buses[i].Start=BUSES[i][1]; g_BusMap.buses[i].End=BUSES[i][2]; } g_BusMap.station=(Station*)malloc(sizeof(Station)*g_BusMap.station_num); for(int i=0;i<g_BusMap.station_num;i++) { g_BusMap.station[i].station=STATIONNAME[i]; g_BusMap.station[i].station_no=STATION[i]; g_BusMap.station[i].route=NULL; } g_BusMap.route=(Route*)malloc(sizeof(Route)*g_BusMap.route_num); for(int i=0;i<g_BusMap.route_num;i++) { g_BusMap.route[i].route_no=ROUTES[i][0]; g_BusMap.route[i].station_no1=ROUTES[i][1]; g_BusMap.route[i].station_no2=ROUTES[i][2]; g_BusMap.route[i].distance=ROUTES[i][3]; g_BusMap.route[i].next=NULL; } for( int i=0 ; i<g_BusMap.route_num ; i++ ){ int j=g_BusMap.route[i].station_no1; if(g_BusMap.station[j].route==NULL){ g_BusMap.station[j].route=g_BusMap.route+i; } else{ g_BusMap.route[i].next=g_BusMap.station[j].route; g_BusMap.station[j].route=g_BusMap.route+i; } } } int Map::FindBus(char *bus){ for(int i=0;i<g_BusMap.bus_num;i++) { if(strcmp(g_BusMap.buses[i].name,bus)==0) { return i; } } return -1; } int Map::FindStation(char* station){ for (int i = 0; i <g_BusMap.station_num; i++) { if (strcmp(g_BusMap.station[i].station, station)==0) return g_BusMap.station[i].station_no; } return -1; } int Map::GetStation(char *station){ //readtxt_route();//保证g_BusMap.station_num int nStation=FindStation(station); if(nStation==-1) { g_BusMap.station=(Station*)realloc(g_BusMap.station,sizeof(Station)*(g_BusMap.station_num+1)); Station *pStation=g_BusMap.station+g_BusMap.station_num; pStation->station=station; pStation->station_no=g_BusMap.station_num; pStation->route=NULL; nStation=g_BusMap.station_num; cout<<"已成功添加一个站点"<<endl; g_BusMap.station_num++; stationsave(); } return nStation; } int Map::Finddistance( char* pStart,char* pEnd ){ int nStart = FindStation(pStart); if(nStart==-1){ return 0; } int nEnd = FindStation(pEnd); if(nEnd==-1){ return 0; } for( int i=0 ; i<g_BusMap.route_num ; i++ ){ if(g_BusMap.route[i].station_no1==nStart&&g_BusMap.route[i].station_no2==nEnd){ return g_BusMap.route[i].distance; } } return 0; } void Map::AddRoute(char* pBus, char* pStart,char* pEnd,int distance){ int nBus = FindBus(pBus); if(nBus==-1){ cout<<"无法查找到该公交，请先添加公交后添加改路线"<<endl; return; } int nStart = GetStation(pStart); int nEnd = GetStation(pEnd); Station* pStStation =&g_BusMap.station[nStart]; Route* pStRoute =pStStation->route; // while (pStRoute != NULL && pStRoute->next != NULL) // { // //判断该边是否已经存在，如果已经存在，则不插入 // if (pStRoute->route_no == nBus && pStRoute->station_no2 == nEnd) // cout<<"该边已存在"<<endl; // return; // pStRoute = pStRoute->next; // } g_BusMap.route=(Route*)realloc(g_BusMap.route,sizeof(Route)*(g_BusMap.route_num+1)); Route* pNewRoute = g_BusMap.route+g_BusMap.route_num; pNewRoute->route_no = nBus; pNewRoute->station_no1 = nStart; pNewRoute->station_no2 = nEnd; pNewRoute->distance = distance; pNewRoute->next = NULL; g_BusMap.route_num++; routesave(); cout<<"添加成功"<<endl; //若是其实顶点的第一条边 if (pStStation->route == NULL) { pStStation->route = pNewRoute; } else { pNewRoute->next=pStRoute->next; pStRoute->next = pNewRoute; } } void Map::QueryBus(char *pBus){ int nBus= FindBus(pBus); if(nBus==-1){ cout<<"无该编号的公交车"<<endl; return; } int nStart= g_BusMap.buses[nBus].Start; int nEnd= g_BusMap.buses[nBus].End; int route[MAX]; route[0]= nStart; Station *pStation= &g_BusMap.station[nStart]; Route *pRoute= pStation->route;//选择其下行路线和站点是否有问题？需检查 int nStation= nStart; int num=1; while(nStation!=nEnd) { while(pRoute->route_no!=nBus)//不是该公交线路，则继续寻找 { pRoute=pRoute->next; } nStation=pRoute->station_no2; route[num]=nStation; num++; pStation=&g_BusMap.station[nStation]; pRoute=pStation->route; } //输出各站点 cout<<"公交车"<<pBus<<"路从"<<g_BusMap.station[nStart].station<<"到"<<g_BusMap.station[nEnd].station <<"经过"<<num<<"个站点"<<endl; cout<<g_BusMap.station[route[0]].station; for(int i=1;i<num;i++) { cout<<"-->"<<g_BusMap.station[route[i]].station; } cout<<endl; } int Map::QueryStation(char *station){ int nStation=FindStation(station); if(nStation==-1){ cout<<"无该站点"<<endl; return 0; } int nBus; int bus[g_BusMap.bus_num]; Station *pstation=&g_BusMap.station[nStation]; Route *pRoute=pstation->route; int num=0; //遍历该站点邻接表找到所有从该站点驶出的车 //如果用g_BusMap.route_num可能会跟好，但是使用图数据结构 while(pRoute!=NULL) { nBus=pRoute->route_no; //找到公交索引号 pRoute=pRoute->next; bus[num]=nBus; num++; } //遍历所有邻接点找到所有驶入该站点的车 for(int i=0;i<g_BusMap.station_num;i++) { Station *qstation=&g_BusMap.station[i]; Route *qroute=qstation->route; while(qroute!=NULL) { if(qroute->station_no2==nStation) { nBus=qroute->route_no; //找到公交索引号 int j=0; for(int k=0; k<num; k++) if(bus[k]== nBus) j++; if(!j) bus[num++]=nBus; } qroute=qroute->next; } } cout<<station<<"共有"<<num<<"辆车经过"<<endl; for(int i=0 ; i<num ; i++) { cout<<g_BusMap.buses[bus[i]].name<<endl; } return num; } void Map::ClearVisited(){ for(int i=0;i<g_BusMap.station_num;i++) visited[i]=false; } void Map::Initialize(Path *&p,char *s,char *e){ p=(Path*)malloc(sizeof(Path)); p->route[0].route_no=-1; p->route[0].distance=0; p->route[0].next=NULL; p->route[0].station_no2=FindStation(e); p->route[0].station_no1=FindStation(s); p->transfer=-1; visited[FindStation(s)]=true; p->top=0; p->alldist=0; } void Map::Push(Path *&p,Route *s){ if(p->route[p->top].route_no!=s->route_no) p->transfer++; p->top++; p->route[p->top].route_no=s->route_no; p->route[p->top].distance=s->distance; p->route[p->top].next=s->next; p->route[p->top].station_no1=s->station_no1; p->route[p->top].station_no2=s->station_no2; p->alldist+=s->distance; } void Map::Pop(Path *&p,Route *&s){ s=(Route*)malloc(sizeof(Route)); s->route_no=p->route[p->top].route_no; s->distance=p->route[p->top].distance; s->next=p->route[p->top].next; s->station_no2=p->route[p->top].station_no2; s->station_no1=p->route[p->top].station_no1; p->alldist-= s->distance; //减掉此段路线的路程 p->top--; if(p->route[p->top].route_no!=s->route_no) p->transfer--; } void Map::PrintPath(Path *p){ if(p->transfer<=1) { cout<<g_BusMap.station[p->route[0].station_no1].station; for(int i=1;i<=p->top;i++) { cout<<"--["<<g_BusMap.buses[p->route[i].route_no].name<<"]-"<<p->route[i].distance<<"->"<<g_BusMap.station[p->route[i].station_no2].station; } sum++; cout<<endl; cout<<"该路线总路程:"<<p->alldist<<" 换乘次数:"<<p->transfer<<endl; } } void Map::QueryPath(char *pStart,char *pEnd){ int nStart=FindStation(pStart); int nEnd=FindStation(pEnd); if( nStart ==-1 || nEnd==-1 ){ return ; } int n=nStart; Station *pStation=&g_BusMap.station[nStart]; Route *pRoute=pStation->route; if(n==nEnd) PrintPath(path); else { while(pRoute)//关键代码 { if(!visited[pRoute->station_no2]) { visited[pRoute->station_no2]=true; Push(path,pRoute); QueryPath(g_BusMap.station[pRoute->station_no2].station,pEnd);//递归函数，向前继续搜索 } pRoute=pRoute->next;//其他公交线路 } } Pop(path,pRoute); visited[pRoute->station_no2]=false; } void Map::QueryPath(){ char Start[30]; char End[30]; cout<<"=====查询两个站点公交线路（最多换乘1次）====="<<endl; cout<<"请输入要查询的起点:"; cin>>Start; cout<<"请输入要查询的终点:"; cin>>End; cout<<"-----------------------------------------"<<endl; if(FindStation(Start)==-1||FindStation(End)==-1) { cout<<"输入的起始站点或终点站有错误!"<<endl; return; } ClearVisited(); Initialize(path,Start,End); cout<<"从"<<Start<<"开往"<<End<<"找到以下路线:"<<endl; QueryPath(Start,End); if(sum!=0) { cout<<"总共有"<<sum<<"条路线符合要求!"<<endl; sum=0; } else cout<<"未找到符合要求的路线!"<<endl; free(path); } void Map::AddStart(char *bus){ int distance; char start[30]; int pBus=FindBus(bus);//公交线路的索引号 char *pstart=g_BusMap.station[g_BusMap.buses[pBus].Start].station; //int pstart=g_BusMap.buses[pBus].Start;//原来公交线路的起点索引号 cout<<">-----请输入新起点:-----<"<<endl; cin>>start; cout<<">---------------------------------------<"<<endl; cout<<">-----请输入新起点到原来起点的距离:-----<"<<endl; cin>>distance; int newStart=GetStation(start); if(strcmp(start,pstart)==0){ cout<<"输入起点错误"<<endl; return ; } cout<<"起始站点编号为--"<<newStart<<endl; AddRoute(bus,start,pstart,distance); g_BusMap.buses[pBus].Start=newStart;//原公交线路起点更改 //g_BusMap.station[newStart].station=start; bussave(); LoadMap(); stationsave(); } void Map::AddEnd(char *bus){ int distance; char End[30]; int pBus=FindBus(bus);//公交线路的索引号 //int pStart=g_BusMap.buses[pBus].Start; char* pEnd=g_BusMap.station[g_BusMap.buses[pBus].End].station;//原来公交线路的终点索引号 cout<<">-----请输入新终点:-----<"; cin>>End; cout<<">---------------------------------------<"; cout<<">-----请输入新终点到原来终点的距离:-----<"; cin>>distance; int newEnd=GetStation(End); cout<<"终止站点编号为--"<<newEnd<<endl; AddRoute(bus,pEnd,End,distance); g_BusMap.buses[pBus].End=newEnd;// bussave(); LoadMap(); } void Map::deleteroute(){ cout<<">-----------------------------------------------------------------<"<<endl; cout<<">---- 在公交路线图中修改站点名字 ----<"<<endl; cout<<">---- 仅能删除起始站点或终点站点 ----<"<<endl; cout<<">-----------------------------------------------------------------<"<<endl; readtxt_route(); readtxt_bus(); char bus[20]; cout<<"请输入删除公交路线公交名"<<endl; cin>>bus; int pBus=FindBus(bus); if( pBus==-1){ cout<<"无经过两站点的公交路线"<<endl; return ; } int flag; cout<<"请输入flag(0/1):0为删除起点，1为删除终点"<<endl; cin>>flag; if(flag==0){ cout<<"请输入删除公交路线起始点"<<endl; } else if(flag==1){ cout<<"请输入删除公交路线起终点"<<endl; } else{ cout<<"输入错误"<<endl; return; } char pstation[20]; cin>>pstation; int nStation=FindStation(pstation); if( nStation == -1 ){ cout<<"该公交站点不存在"<<endl; return ; } int index; int index1=0; int index2=0;//记录站点编号 for( index=0 ; index<g_BusMap.route_num ; index++ ){ if(ROUTES[index][0]==pBus&&(ROUTES[index][1]==nStation||ROUTES[index][2]==nStation)){ index1=ROUTES[index][1]; index2=ROUTES[index][2]; break; } } for( int j=0 ; j<g_BusMap.route_num-1 ; j++){ if(j>=index){ ROUTES[j][0]=ROUTES[j+1][0]; ROUTES[j][1]=ROUTES[j+1][1]; ROUTES[j][2]=ROUTES[j+1][2]; ROUTES[j][3]=ROUTES[j+1][3]; } } for( int j=0 ; j<g_BusMap.route_num-1 ; j++){ if( ROUTES[j][0]==pBus&&flag==0&&ROUTES[j][1]==index2 ){//改起点 BUSES[pBus][1]=index2; } if( ROUTES[j][0]==pBus&&flag==1&&ROUTES[j][2]==index1){//改终点 BUSES[pBus][2]=index1; } } cout<<"路线删除成功！"<<endl; g_BusMap.route_num--; ReLoadMap(); routesave(); bussave(); } void Map::deletestation(){ cout<<">---- 在公交路线图中删除站点 ----<"<<endl; readtxt_bus(); readtxt_station();//将文件东西读到数组里面便于修改 readtxt_route(); cout<<"-----------------------"<<endl; char station[20];// cout<<"请输入要删除的站点名："; cin>>station; int nStation=FindStation(station); if(nStation==-1) { cout<<"该站点不存在或已被删除"<<endl; return; } //删除站点时候路线情况 for( int j=0 ; j<g_BusMap.station_num-1 ; j++ ) { if(j>=nStation) { strcpy(STATIONNAME[j],STATIONNAME[j+1]); //STATION[j]=STATION[j+1]; } STATION[j]=j; } g_BusMap.station_num--; int num=g_BusMap.route_num; int j=0; for( int i=0 ; i<num ; i++ ) { if( nStation!=ROUTES[i][1] && nStation!=ROUTES[i][2] ) //如果站点不是路线起点或者终点 { ROUTES[j][0]=ROUTES[i][0]; ROUTES[j][1]=ROUTES[i][1]; ROUTES[j][2]=ROUTES[i][2]; ROUTES[j][3]=ROUTES[i][3]; j++; } else if(nStation==ROUTES[i][1]) { int p;//标志域，记录站点在文件中是一个情况的话，就是bus的起点 for(p=0; p<num&&!(nStation==ROUTES[p][2]&&ROUTES[p][0]==BUSES[ROUTES[j][0]][0]); p++); //判断路线是否相同 if(p==num) { for(int k=0; k<num; k++) //将起点改为后一个点 { if(BUSES[k][0]==ROUTES[i][0]&&BUSES[k][1]==ROUTES[i][1]) BUSES[k][1]=ROUTES[i][2]; } } } else if(nStation==ROUTES[i][2]) { int p; for(p=0; p<num&&!(nStation==ROUTES[p][2]&&ROUTES[p][0]==BUSES[ROUTES[j][0]][0]); p++); if(p!=num) { ROUTES[j][0]=ROUTES[i][0]; ROUTES[j][1]=ROUTES[i][1]; ROUTES[j][2]=ROUTES[p][2]; ROUTES[j][3]=ROUTES[i][3]+ROUTES[p][3]; j++; } else //公交站终点时 { for(int k=0; k<num; k++) //将终点改为前一个点 { if(BUSES[k][0]==ROUTES[i][0]&&BUSES[k][2]==ROUTES[i][2]) BUSES[k][2]=ROUTES[i][1]; } } } } g_BusMap.route_num=j; for( int i=0 ; i<j ; i++ ){ if(ROUTES[i][1]>=nStation){ ROUTES[i][1]--; } if(ROUTES[i][2]>=nStation){ ROUTES[i][2]--; } } for( int i=0 ; i<j ; i++ ){ if(BUSES[i][1]>=nStation){ BUSES[i][1]--; } if(BUSES[i][2]>=nStation){ BUSES[i][2]--; } } cout<<"删除成功！"<<endl; ReLoadMap(); routesave(); bussave(); stationsave(); } void Map::changestation(){ cout<<">-----------------------------------------------------------------<"<<endl; cout<<">---- 在公交路线图中修改站点名字 ----<"<<endl; cout<<">-----------------------------------------------------------------<"<<endl; char old_Station[20]; cout<<"请输入站点的原名字："; cin>>old_Station; int nStation=FindStation(old_Station); if(nStation==-1){ cout<<"输入的站点名有错误!"<<endl; return; } char new_Station[20]; cout<<"请输入站点的新名字："; cin>>new_Station; while(FindStation(new_Station)!=-1) { cout<<"站点名字已被占用，请重新输入："; cin>>new_Station; } Station *p=g_BusMap.station+nStation; strcpy(p->station,new_Station); stationsave();//把新的站点信息写入文件 cout<<"修改成功！"<<endl; LoadMap(); } void Map::changedistance() { cout<<">-----------------------------------------------------------------<"<<endl; cout<<">---- 在公交路线图中修改站点名字 ----<"<<endl; cout<<">---- 仅能改变路线距离 ----<"<<endl; cout<<">-----------------------------------------------------------------<"<<endl; char pStart[20]; char pend[20]; int pdistance; cout<<"请输入起始站点的名字："; cin>>pStart; cout<<"请输入结束站点的名字："; cin>>pend; cout<<"--------------------"<<endl; cout<<"请输入站点间的距离："; cin>>pdistance; int nStart=FindStation(pStart); int nEnd=FindStation(pend); int flag=0; //标志变量 if(nStart==-1||nEnd==-1){ cout<<"输入的站点名有误!"<<endl; return; } for(int i=0; i<g_BusMap.route_num; i++) { if((ROUTES[i][1]==nStart&&ROUTES[i][2]==nEnd)) { ROUTES[i][3]=pdistance; flag=1; } } if(flag==0) { cout<<"该路线不存在！"<<endl; return; } else { ReLoadMap(); routesave(); cout<<"修改成功！"<<endl; } } Map::~Map(){ //dtor }

cpp

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926

//请大家谅解，暂时不太会使用csdn排版，这个是数据结构课程设计源代码，可以创建三个文件夹，具体可以细聊