公交线路管理系统剖析.doc

课 程 设 计 报 告课程设计名称： 数据结构课程设计 学 院： 信息工程学院 学 生 姓 名 ： * 班 级： 14计本1 学 号： 成 绩： 指 导 教 师： * 开 课 时 间：2015-2016学年一学期设计题目：公交线路管理系统一、 实习目的 通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。二、 问题描述实现功能：文件初始化交通图、公共汽车路线、城市站点信息；管理员和乘客登录；系统介绍使用说明；判断输入量路径间是否存在直接到达路径，此函数为录入交通线和添加删除路线中的辅助判断函数邻接表和邻接矩阵的互化，删除和添加路线，增设交通运行路线，查找公交车运营路线，查找任意两个城市之间是否有路径，若有则将最短路径输出，操作结束后检测文件是否被修改，若被更改则自动保存；功能分配：三、 需求分析该程序所做的工作是对公交车运行线路及城市交通网络的管理，首先城市交通信息应用文件形式进行保存，在运行开始前用文件对城市中城市交通图初始化；结束时用文件对程序各项数据信息进行保存。本程序面向乘客和管理员，故在开始时设计登录界面，只有输入密码获得管理员权限才可以使用本程序中设计的，增加路线，删除路线，和保存功能；普通乘客只能使用两类信息查询功能，公交路线查询和路径查询。本程序遵循由路必有车走、有车走必有路的原则设计城市路线和交通网络。四、 概要设计#define MaxC 20/最多容纳20站点#define Limit 10000/以10000千米代表两城市之间无站点#define Administrator 1/管理员标志#define Passenger 0/乘客身份标志using namespace std;typedef unsigned int NO_TYPE;/*定义城市类型包含城市编号和城市名称*/typedef struct NO_TYPE no_city;/城市编号string city_name;/城市名称CityType;/*定义邻接边类型*/typedef struct Road /城市节点类型NO_TYPE adjcity;/该边终点城市编号struct Road *NextCity;/顶点城市下一条邻边float Road_length;/路径长度RoadNode;/*定义邻接表表头节点*/typedef struct CityType data;/城市节点信息RoadNode *firstcity;/此城市可通向的第一个城市CitiesNode;/*定义车辆类型*/typedef struct string No_Bus;/车辆编号NO_TYPE num_Cities;/所经过城市的数目 NO_TYPE WayMaxC;/所经过路线以城市编号表示BusType;/*定义文件修改标志*/enum Change Yes,No;/*定义城市交通图类*/class TGraph vector <CitiesNode> CList;/交通图邻接表类型NO_TYPE num_of_city;/城市数量（City）vector <BusType> Bus_info;/车辆信息short User_id ;/用户身份标志Change m ;/交通图修改标志public: TGraph ();/*文件初始化在运行开始时形成一张邻接表*/bool Init_Graph ( );/初始化交通图/*为简便程序设计和保存方便故设计转化函数让程序中对交通图处理更加灵活*/bool MattoList (float mapMaxC);/转化邻接矩阵void ListtoMat (float mapMaxC);/邻接表转化为邻接矩阵void Find_info ();/查询/*采用狄克斯特拉算法求一节点到另一节点最短路径*/void Find_way (string , string);/查询直接路径/*设计用于跟新线路信息*/void Updata (NO_TYPE , NO_TYPE);/更新/*在两个站点之间插入新路线*/void Insert_rode (NO_TYPE , NO_TYPE);/judge_rode/*判断两城市是否是已有城市*/bool Judge_city (string , string);/*增加路线*/void Add_road ();/添加路线/*判断两城市之间有无直接路径*/bool Judge_road (NO_TYPE , NO_TYPE);bool Delete ();/删除操作/*删除添加操作都应调用此函数进行线路同步修改*/void Bus_mend (BusType*);/修改公交路线void Save ();/存入文件中/*最后将申请的空间都释放*/void Clean ();/释放申请的空间void Display ();/输出当前交通网络bool Land ();/管理员/用户登录;void Mainmenu (TGraph &G , int &k);/主菜单函数void Introduced ();/系统使用说明与登录函数一起使用 五、 详细设计#include "decl.h"float mapMaxCMaxC;/使最短路径查询简化/*/TGraph:TGraph ()if (!Init_Graph () cout<<"初始化失败！"<<endl;/*初始化函数*/bool TGraph:Init_Graph ()int i,j,n;ifstream input;input.open("City.txt");/打开城市文件if (!input)/文件打开出错cerr<<"文件"City.txt"打开错误！"<<endl;return false;input >>num_of_city;/文件初始化城市基本信息for (i = 0 ; i < num_of_city ; i+)/先将城市基本信息初始化CitiesNode c;/临时变量input >> c.data.no_city >>c.data.city_name ;c.firstcity = NULL;CList.push_back(c);/将初始化好的加入向量中input.close();/解绑文件input.clear();/清理输入流已备后用input.open ("Bus.txt");if (!input)cerr<<"文件"Bus.txt"打开错误！"<<endl;return false;while (input.good()/文件初始化公交车及其安排BusType b;/临时公交类型参数input >>b.No_Bus >>b.num_Cities ;n = b.num_Cities ;/经过城市数量for (i = 0 ; i < n ; i+)input>>b.Wayi;Bus_info.push_back (b); input.close ();input.clear();/float mapMaxCMaxC;/接收从文件中读取到的信息input.open ("Map.txt");if (!input)cerr<<"文件"Map.txt"打开错误"<<endl;return false;for (i=0 ; i<num_of_city; i+)/文件初始化邻接表for (j =0 ; j<num_of_city; j+)input >>mapij;/读取文件内容MattoList (map);/将从文件中读取的内容转化为邻接表input.close();/解绑文件return true;/*将文件中读取到的数据转化为临接表*/bool TGraph:MattoList (float mapMaxC)int i, j;RoadNode *r1 = 0;vector <CitiesNode>:iterator it_c = CList.begin();for (i = 0; i < num_of_city&&it_c != CList.end (); it_c+,i+)for (j = 0; j < num_of_city ; j+)if (mapij != Limit && mapij != 0)r1 = new RoadNode;r1->Road_length = mapij;r1->adjcity = j + 1;r1->NextCity = (*it_c).firstcity ;(*it_c).firstcity = r1;return true;/*查询两个城市之间有无路径*/void TGraph:Find info ( )string c1 , c2;cout <<"请输入起始点名称:"cin >> c1;cout <<"请输入终点名称:"cin >> c2;Find_way (c1, c2);/*查找路径*/void TGraph:Find_way (string Begin, string End)float distMaxC;NO_TYPE pathMaxC;NO_TYPE visitedMaxC;float mindis;int i,j,u,k,d;NO_TYPE n_b, n_e;NO_TYPE apathMaxC;vector<CitiesNode>:iterator it_c = CList.begin ();while (it_c != CList.end()/获取城市对应编号if (*it_c).data.city_name = Begin)n_b = (*it_c).data.no_city ;if (*it_c).data.city_name = End)n_e = (*it_c).data.no_city ;it_c+;n_e-; n_b-;for (i = 0; i < num_of_city; i+)disti = map n_bi;visitedi = 0;if (mapn_bi < Limit)path i = n_b;elsepath i = -1;visitedn_b = 1; path n_b = 0;for (i = 0; i < num_of_city; i+)mindis = Limit;for (j= 0; j < num_of_city; j+)if (visitedj = 0 && distj < mindis)u = j;mindis = distj;visitedu = 1;for (j = 0; j < num_of_city; j+)if (visitedj = 0)if (mapuj < Limit && distu + mapuj < distj)distj = distu + mapuj;path j = u;if (visited n_e = 1 && n_e != n_b)cout<<"从"<<CListn_b.data.city_name<<"到"<<CListn_e.data.city_name<<"的最短路径为："<<endl<<endl;d =0; apathd = n_e;k = pathn_e;if (k = -1) cout<<"两城市之间无路径可到达！"<<endl;return;else while (k != n_b)d+; apathd = k;k = path k;d+; apathd = n_b;cout << CListapath d.data.city_name<<">"for (j = d -1 ; j >= 0; j-)cout <<CListapathj.data.city_name;if(j - 1 >= 0) cout<<">"cout<<"t总长度为："<<distn_e<<" km"<<endl;/*更新*/void TGraph:Updata (NO_TYPE n_b , NO_TYPE n_e)float r_l;/存放修改值cout <<"请输入修改后的路径长度："<<endl;cin >> r_l;RoadNode *r;/作为处理信息的指针r = CListn_e - 1.firstcity ;while (r)/顺着定位好的r找到在其下的终点城市改边两者之间的路径长度if (r->adjcity = n_e )r->Road_length = r_l;m = Yes;break;else r = r->NextCity ;/*插入新线路*/void TGraph:Insert_rode (NO_TYPE n_b, NO_TYPE n_e)RoadNode *r1 = 0 ,*r2 = 0;vector<CitiesNode>:iterator it_c = CList.begin();while (it_c != CList.end ()/获取起始节点位置if (*it_c).data.no_city = n_b)r1 = (*it_c).firstcity ;break;else +it_c;if (r1)while (r1->NextCity) r1 = r1->NextCity ;/将r移至末端r2 = new RoadNode;/新开一存储空间保存新的邻接边r2->adjcity = n_e;/临接边的编号设为终点编号r2->NextCity = NULL;/将其下一邻接边打空cout << "请输入此路线长度"<<endl;cin >> r2->Road_length;r1->NextCity = r2;BusType b;cout<<"你需要设计一条公交线路来将此新线路变得有意义："<<endl;Bus_mend (&b);Bus_info.push_back(b);/*添加路线*/void TGraph:Add_road ()string if_con("1");/继续操作标志string s_begin , s_end;if (User_id = Administrator)/只有管理员身份才可操作CitiesNode c;while (if_con0 = '1')/system ("cls");cout <<"请输入你想添加路线的两个城市前者代表起点后者带表终点"<<endl<<endl;cin >>s_begin>>s_end;if (Judge_city (s_begin, s_end)/判断输入两城市是否正确NO_TYPE n_b = 0 , n_e = 0;vector<CitiesNode>:iterator it_c = CList.begin ();while (it_c != CList.end()/获取城市对应编号if (*it_c).data.city_name = s_begin)n_b = (*it_c).data.no_city ;/记录起点位置if (*it_c).data.city_name = s_end)n_e = (*it_c).data.no_city ;/记录终点位置it_c+;/迭代器下移if (Judge_road (n_b ,n_e)/如果插入两节点之间存在路线cout<<"你所要插入新线路的两个城市间已有线路!"<<endl<<endl;cout <<"1更新线路信息ttt2放弃插入"<<endl;string insert_select;cin >>insert_select;switch (insert_select 0)case '1':Updata (n_b ,n_e);break;/表示要更新case '2':return;default:cout<<"输入错误！"/switch/judge_roadelse Insert_rode (n_b ,n_e);/若两者之间并无路径则插入if_con = "0"/将继续标志打为否/judge_cityelse cout<<"输入城市有误！"<<endl<<endl;cout<<endl<<"是否继续！0否 1是"cin >> if_con;/是否继续标志else cout <<endl<<"乘客身份无法操作！"/*判断城市是否在已有数据中*/bool TGraph:Judge_city (string c1 , string c2)int i = 0;vector <CitiesNode>:iterator it_c = CList.begin();while (it_c != CList.end ()/如果c1，c2皆在已有数据中则i将被加之2if (*it_c).data.city_name = c1)i+;if (*it_c).data .city_name = c2)i+;it_c+;if (2 = i) return true;else return false;/*判断两城市之间有无路径*/bool TGraph:Judge_road (NO_TYPE c1 , NO_TYPE c2)RoadNode *r;vector<CitiesNode>:iterator it_c = CList.begin();while (it_c != CList.end()获取起始节点邻接边if (*it_c).data.no_city = c1)r = (*it_c).firstcity ;break;else it_c+;while (r)/当邻接边不空if (r->adjcity = c2)/并且其中有终点节点return true;/找到就返回正确值else r = r->NextCity ;return false;/*删除操作*/bool TGraph:Delete ()if (User_id = Administrator)/管理员方可操作system ("cls");RoadNode *f,*r;string s_begin , s_end;cout << "请输入你想删除路线的起始城市和终点城市:"<<endl<<endl;cin >>s_begin>>s_end;NO_TYPE n_b = 0 , n_e = 0;vector<CitiesNode>:iterator it_c = CList.begin ();while (it_c != CList.end()/获取城市对应编号if (*it_c).data.city_name = s_begin)n_b = (*it_c).data.no_city ;if (*it_c).data.city_name = s_end)n_e = (*it_c).data.no_city ;it_c+;if (!Judge_road (n_b , n_e)/判断这两城市之间是否有路径cout <<"tttt这两者之间无直接路径！无需删除！"<<endl;return false ;else f = CListn_b - 1.firstcity;if (!(f->NextCity)&&f->adjcity != n_e)/如果路径不是第一条r = f->NextCity ;while (r)/先确定位置后删除if (r->adjcity = n_e)f->NextCity = r->NextCity ;delete r;m = Yes;else f = r; r = r->NextCity;else /如果是第一条则直接删除CList n_b - 1.firstcity = f->NextCity ;delete f;m = Yes;vector <BusType>:iterator it_b = Bus_info.begin();/修改公交路线for (; it_b != Bus_info.end (); it_b+)/逮到走这条路线的公交车for (int i = 0; i < (*it_b).num_Cities; i+)if (*it_b).Way i - 1 = n_b && (*it_b).Way i = n_e )cout<<"ttt"<<"""<<(*it_b).No_Bus <<"""<<"号公交线路将不可用!必须修改："<<endl;Bus_mend (it_b);return true;cout<<"游客无法操作！"<<endl;return false; /*修改公交路线*/void TGraph:Bus_mend (BusType*b)cout<<"请输入公交车编号："<<endl<<endl;cin >>b->No_Bus ;cout <<"请输入公交车行驶过的城市数："<<endl<<endl;cin>>b->num_Cities ;bool input_err = true;/初始化为错误状态while (input_err)int i = 0, j;input_err = false;/默认管理员会输对cout <<"请输入行车路线(以城市编号顺序表示):："<<endl;for (j = 0 ; j < num_of_city ; j+)/输出个城市供管理员参考cout << CListj.data.no_city<<"."<<CListj.data.city_name<<" "cout <<endl;cin >>b->Way i;/避免数组越界访问for (i = 1 ; i < b->num_Cities ; +i)/录入公交路线cin >>b->Way i;if (!Judge_road (b->Way i - 1,b->Way i)/判断管理员输入的城市之间是否有路线可走cout <<"你添加的城市"<<"""<<CListb->Way /输出是哪里出错了i-1-1.data.city_name<<"""<<"""<<CListb->Way i-1.data.city_name<<"""<<"之间没有路线可走,请确认后重新输入！"<<endl;input_err = true;/置为出错break;m = Yes;/表示文件已被修改/*存入文件中*/void TGraph:Save ()if (m = Yes)/若文件修改过则执行下面的写入int ib;float map_outMaxCMaxC;vector <BusType>:iterator it_b = Bus_info.begin();ofstream output ("Bus.txt");/将公交路线保存到文件while (it_b!= Bus_info.end() && output)ib = 0;output <<setw(8)<<(*it_b).No_Bus<<setw(8)<<(*it_b).num_Cities;for (; ib <(*it_b).num_Cities ; ib+)output<<setw(6)<<(*it_b).Way ib;/依次向文件输入公交路线if (it_b + 1 != Bus_info.end()/最后一个不可以换行output <<endl;+it_b;output.close ();output.clear ();/使之又可用ListtoMat (map_out);/将邻接表转化为邻接矩阵output.open ("Map.txt");for (int i = 0 ; i < num_of_city ; i+)/将矩阵形式的交通图输入for (int j= 0 ; j < num_of_city ; j+)output <<setw(6)<<map_outij;output<<endl;output.close ();/解绑文件/*邻接表转化为邻接矩阵*/void TGraph:ListtoMat (float mapMaxC)RoadNode *r;for (int i = 0 ; i < num_of_city ; i+)for (int j = 0 ; j< num_of_city ; j+)if(i = j) mapij =0;else map ij = Limit;vector <CitiesNode> :iterator it_c = CList.begin ();for (i = 0 ; it_c != CList.end() ; it_c+,i+)/以每个城市循环r = (*it_c).firstcity;while (r)/以各邻接边循环mapir->adjcity-1 = r->Road_length ;r = r->NextCity ;/*