下载文档原格式
数据结构—交通系统在我们的日常生活中，交通系统是一个极其复杂但又至关重要的组成部分。
它就像是一个庞大的、不断运转的机器，将人们从一个地方运输到另一个地方，保障着城市和社会的正常运转。
而在这个复杂的系统背后，数据结构起着不可或缺的作用。
想象一下，每天有成千上万的车辆在道路上行驶，有无数的行人穿梭于街头巷尾，还有各种公共交通工具在城市中穿梭。
如何有效地管理和协调这一切，以确保交通的流畅、安全和高效？这就需要依靠数据结构来实现。
首先，让我们来谈谈交通流量数据。
这是交通系统中最基本也是最重要的数据之一。
通过在道路上设置传感器、摄像头等设备，我们可以实时收集到车辆的数量、速度、行驶方向等信息。
这些数据被整理和存储起来，形成了一个庞大的数据库。
而这个数据库的组织方式，就是一种数据结构。
比如说，我们可以使用链表来存储交通流量数据。
链表的特点是可以方便地进行插入和删除操作，这对于实时更新交通流量信息非常有用。
每当有新的数据产生，我们可以迅速地将其添加到链表中；而当某些数据过时或者不再需要时，也可以轻松地将其从链表中删除。
另外，队列这种数据结构在交通系统中也有广泛的应用。
比如在十字路口的信号灯控制中，车辆可以被看作是在一个队列中等待通行。
信号灯按照一定的规则依次放行队列中的车辆，从而保证交通的有序进行。
队列的先进先出原则很好地模拟了这种场景，使得交通控制更加合理和高效。
除了交通流量数据，路线规划也是交通系统中的一个重要环节。
当我们使用导航软件规划出行路线时，背后其实是一系列复杂的数据结构和算法在起作用。
例如，图这种数据结构被广泛应用于路线规划中。
我们可以将城市的道路网络看作是一个图，其中节点代表道路的交叉点，边代表道路段。
通过对这个图进行搜索和分析，导航软件可以找到从起点到终点的最优路径。
在图的搜索算法中，迪杰斯特拉算法是一种常用的方法。
它能够计算出图中一个节点到其他所有节点的最短路径。
当我们输入起点和终点后，导航软件就会运用这种算法，在道路网络的图中找到最短或者最快的路线，为我们提供准确的导航指引。
数据结构公交换乘系统公交换乘系统是现代城市交通系统中的重要组成部分，它为乘客提供了方便快捷的出行方式。
在一个繁忙的城市中，合理规划公交线路以及实现高效的换乘是提高公交系统效率的关键。
为了实现这一目标，数据结构在公交换乘系统的设计与实现中起着重要的作用。
一、问题描述公交换乘系统的目标是为乘客提供最佳的换乘路线。
给定起点和终点，系统需要计算出最短的换乘路线以及相应的换乘次数和换乘站点。
为了实现这一目标，我们需要使用合适的数据结构来存储和处理公交线路数据。
二、数据结构选择在设计公交换乘系统时，我们可以使用多种数据结构来存储和处理公交线路数据。
以下是几种常用的数据结构：1. 图（Graph）：公交线路可以被看作是一个有向图，图的节点表示公交站点，图的边表示公交线路。
使用图数据结构可以方便地表示公交线路之间的关系，以及计算最短路径。
2. 队列（Queue）：在公交换乘系统中，乘客需要按照先后顺序排队等待上车。
队列数据结构可以很好地模拟这一过程，保证乘客按照先来先服务的原则进行换乘。
3. 栈（Stack）：在某些情况下，公交线路可能需要进行回溯或者撤销操作。
栈数据结构可以很好地支持这些操作，保证系统的灵活性和可靠性。
根据公交换乘系统的需求，我们可以选择合适的数据结构来存储和处理公交线路数据。
三、数据结构的实现1. 图的实现在公交换乘系统中，我们可以使用邻接矩阵或邻接表来表示公交线路的图结构。
邻接矩阵是一个二维数组，其中的元素表示两个公交站点之间是否有直接的公交线路。
如果两个站点之间有直接线路，则对应位置的元素为1，否则为0。
邻接矩阵的优点是查询两个站点之间是否有直接线路的时间复杂度为O(1)，但是它的缺点是占用较多的存储空间。
邻接表是一种链表的数组，其中的每个链表表示一个公交站点的邻居站点。
邻接表的优点是占用较少的存储空间，但是查询两个站点之间是否有直接线路的时间复杂度为O(k)，其中k是邻居站点的数量。
2. 队列的实现在公交换乘系统中，我们可以使用数组或链表来实现队列数据结构。
《数据结构》课程设计报告一、课程设计名称公交线路管理模拟系统二、实用工具软件Microsoft visual C++ 6.0三、课程设计容简介1、实践目的1）、掌握图的概念、图的两种存储结构(邻接矩阵和邻接表)的存储思想及其存储实现；2）、掌握上机实现图的基本方法；3）、掌握有关图的操作并用高级语言编程实现；4）、熟练掌握图的深度、广度优先遍历算法思想及其程序实现；5）、掌握图的常见应用算法的思想及其程序实现。
2、实践要求1）、掌握本章实践的算法；2）、上机运行本章的程序，保存和打印出程序的运行结果，并结合程序进行分析；3）、按照你对图的操作需要，重新改写程序并运行，打印出文件清单和运行结果；4）、注意理解各算法实现时所采用的存储结构；5）、注意正、逆邻接表。
3、系统简介及设计思路本项目是对公交车路线信息的简单模拟，以完成建立公交路线信息、修改公交路线信息和删除公交路线信息等功能。
本项目的实质是完成对公交路线信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。
公交站点之间的关系可以是任意的，任意两个站点之间都可能相关。
而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据之间都可能相关。
所以可以用图形结构来表示n个公交站点之间及站点之间可能设置的公交路线，其中网的顶点表示公交站点，边表示两个站点之间的路线，赋予边的权值表示相应的距离。
因为公交路线是有一定的连续关系的，如果想输出从某一个起始点开始到某一终点结束的公交路线，就需要找到从某一点开始的第一个邻接点和下一个邻接点。
因为在邻接表中容易找到任一顶点的第一个邻接点和下一个邻接点，所以本项目使用了图的邻接表存储结构。
4、程序设计流程为了创建公交路线，首先建立结构体载入公交车的相关信息：名称、司机、起始站、终点站、站数以及距离。
利用邻接表把站点与站点之间的信息储存起来。
面向移终端的公交换乘系统后台的设计和实现的开题报告一、问题背景公交换乘是人们日常出行中非常常见的情况。
在城市中，不同公交线路之间可能存在交汇或者终点站的重叠，因此需要通过换乘来到达目的地。
为了提升乘客的出行体验和效率，设计和实现一个面向移动终端的公交换乘系统需要保证后台的可靠和高效。
二、研究内容1.需求分析：通过对公交换乘系统的调研，了解用户对于系统的需求和痛点，进而确定系统需求。
2.系统架构设计：在满足需求的前提下，设计合理的系统架构，包括数据存储、业务逻辑处理、数据接口设计等。
3.数据库设计：针对系统的数据存储需求设计数据库模型。
4.数据接口设计：为移动终端提供数据接口，提高用户体验。
5.系统测试：对系统进行全面测试，保证系统功能、性能和稳定性。
三、研究意义通过设计和实现一个面向移动终端的公交换乘系统后台，可以为广大出行人群提供便利和高效的服务。
同时，这也是一个技术挑战和机遇，可以在系统架构、数据库设计和业务逻辑等方面进行技术探索、创新和提升。
四、研究方法1.文献资料法：通过查阅文献资料，了解公交换乘系统的相关研究和实践经验，进而结合实际情况确定系统需求和设计方案。
2.实验法：通过实验验证系统的可靠性、性能和稳定性。
3.软件工程方法：使用软件工程方法进行系统设计和开发，包括系统架构设计、数据库设计、接口开发等。
五、预期成果1.一个面向移动终端的公交换乘系统后台；2.论文一篇，详细介绍系统的设计和实现过程，同时对系统进行全面测试和性能评估；3.项目开发过程中所积累的技术和经验。
六、进度安排阶段时间任务1 第1周~第2周系统调研、需求分析和方案提出2 第3周~第4周系统架构设计、数据库设计和接口设计3 第5周~第7周系统开发和测试4 第8周~第9周论文撰写和完善七、参考文献1.刘晓东. 公交换乘导航系统的研究与实现[J]. 规划交通, 2019(6): 103-107.2.吕嘉扬. 基于数据挖掘的公交换乘建议系统研究[J]. 交通科技, 2018(6): 43-45.3.吴敬华, 刘彦晨. 基于深度学习的公交换乘推荐算法设计[J]. 公路交通科技, 2019(1): 96-100.。
《数据结构》课程设计报告一、课程设计名称公交线路管理模拟系统二、实用工具软件Microsoft visual C++ 6.0三、课程设计内容简介1、实践目的1）、掌握图的概念、图的两种存储结构(邻接矩阵和邻接表)的存储思想及其存储实现；2）、掌握上机实现图的基本方法；3）、掌握有关图的操作并用高级语言编程实现；4）、熟练掌握图的深度、广度优先遍历算法思想及其程序实现；5）、掌握图的常见应用算法的思想及其程序实现。
2、实践要求1）、掌握本章实践的算法；2）、上机运行本章的程序，保存和打印出程序的运行结果，并结合程序进行分析；3）、按照你对图的操作需要，重新改写程序并运行，打印出文件清单和运行结果；4）、注意理解各算法实现时所采用的存储结构；5）、注意正、逆邻接表。
3、系统简介及设计思路本项目是对公交车路线信息的简单模拟，以完成建立公交路线信息、修改公交路线信息和删除公交路线信息等功能。
本项目的实质是完成对公交路线信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。
公交站点之间的关系可以是任意的，任意两个站点之间都可能相关。
而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据之间都可能相关。
所以可以用图形结构来表示n个公交站点之间及站点之间可能设置的公交路线，其中网的顶点表示公交站点，边表示两个站点之间的路线，赋予边的权值表示相应的距离。
因为公交路线是有一定的连续关系的，如果想输出从某一个起始点开始到某一终点结束的公交路线，就需要找到从某一点开始的第一个邻接点和下一个邻接点。
因为在邻接表中容易找到任一顶点的第一个邻接点和下一个邻接点，所以本项目使用了图的邻接表存储结构。
4、程序设计流程为了创建公交路线，首先建立结构体载入公交车的相关信息：名称、司机、起始站、终点站、站数以及距离。
利用邻接表把站点与站点之间的信息储存起来。
公交换乘系统本科生课程设计课程名称公交换乘系统学号学生姓名所在专业所在班级指导教师成绩教师签字课程设计时间：2010年6月一、目的与要求通过一个学期的系统学习，学生们掌握了数据结构的基础理论知识，然而由于数据结构原理的抽象性，可能使得学生对数据结构各部分理论的理解不够深入。
设置本课程设计，通过了解公交换乘算法的设计与实现，使学生能够学以致用，培养和提高学生的算法设计、运用计算机进行编程、调试等技能，从而培养学生独立工作的能力和创造能力。
二、设计内容公交换乘系统公交换乘在一个城市的公共交通系统设计中占据着极其重要的地位，公交换乘的过程将直接影响居民出行时间的长短，公交换乘的过程如下：指定一起始公交站点与目的公交站点，依据参考因素，例如：换乘路线的路径最短、耗费时间最短、所需车资最少等，经过分析处理得到可达目的站点换乘次数最少的乘车方案，具体可分为：（1）零次换乘起始站点和目的站点之间存在可直达的公交线路，即出行居民无需转乘就可以直接到达目的站点，这也是较为理想的方案。
（2）一次换乘起始站点和目的站点之间没有公交车直接往返，即两站点之间不存在可直达的公交线路，则出行居民需要在途经的某个站点下车，然后转乘另一线路公交车才能达到目的站点。
（3）多次换乘在起始站点和目的站点之间没有可直达的公交线路，出行居民需要经过一次以上的转乘才能达到目的站点，则得到多次换乘方案。
多次换乘方案可通过一次换乘的递归计算得到，一般情况下，超过两次转乘的方案对于出行居民来说是难以接受的，本课程设计只要求计算零次和一次换乘方案，对于一次以上的公交换乘不作要求。
三：本系统功能介绍：在这里通过主函数显示程序的主页版，上面是湛江的公交线路图。
在这里输入出发站点的名字，回车确定！在这里输入最终站点的名字！输入错误会提醒重新输入！输入要查询的起点和终点0次换乘，输出查询结果：按y或Y，可以继续查询！输入出发点和终点，一次换乘的结果如下：四：设计要求认真参阅本课程设计的相关参考资料、数据，了解公交换乘的原理要求，设计一个实现公交换乘的算法：指定任一起始站点和目的站点，依据算法得到所有可达目的站点的的公交线路，包括中间站点的换乘方法以及该公交线路所经过的公交站点。
广东海洋大学信息学院课程设计报告设计题目公交换乘系统课程名称数据结构姓名（学号）联系电话专业名称计算机科学与技术所在班级1101班指导教师教师职称起止时间2011 年12月26日至2012年1月6日评定成绩一、课程设计的主要内容1、公交线路中，为用户查找最短路径，有【0】次换乘就能到达目的地和【1】次换乘就能到达目的地。
2、为用户计算出路程所需费用。
3、该课程设计的公交系统中有分权限；分管理员用户和普通用户，管理员的登陆需要帐号和密码（暗文），普通用户可以直接登陆。
4、管理员可以重新输入新公交路线、输出公交路线、读取已经存盘的公交路线资料、存入新公交路线资料（慎用！）、查找最短公交路线、新增管理员用户和删除管理员用户。
5、普通用户只能输出公交路线和查找最短公交路线两个功能。
二、功能和结构设计1、为用户分权限2、管理员有重新输入新公交路线、输出公交路线、读取已经存盘的公交路线资料、存入新公交路线资料（慎用！）、查找最短公交路线、新增管理员用户和删除管理员用户3、普通用户只能输出公交路线和查找最短公交路线两个功能。
注：系统默认的公交线路图（系统开发者为用户事先存好的，在f1.txt文档中）三、流程图和算法设计算法：（给出查找最短路径的方法）void Bus<T>::findline(){int x,y,i,j,k,l,longers;longers=0;//x、y是起始和终止车站的编码；i、j是每个站点后两位编码；k是每个站点后两位编码的差值；l是转乘站点的后两位编码while(1){cout<<"请输入起始站点编号：";cin>>x;cout<<" 终止站点编号：";cin>>y;if((x/100)>lineNum||(x/100)<=0||(x%100)>=busStationNum[x/100-1]||(y/100)>lineNum ||(y/100)<=0||(y%100)>=busStationNum[y/100-1])//前两个是判断车站编码的首位的，第三个是判断车站编码的后两位的cout<<"----找不到您所输入站点，请重新输入！----"<<endl;elsebreak;}i=x%100;j=y%100;if((x/100)==(y/100)){cout<<"您可【0】次换乘到达目的地，路线如下："<<endl;// k=j-i;if(j-i>0){for(k=0;k<j-i;k++){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k].longer;}cout<<line[x/100-1][x%100+k].busStationName<<endl;}else{for(k=0;k>j-i;k--){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k-1].longer;}cout<<line[x/100-1][x%100+k].busStationName<<endl;longers+=line[x/100-1][x%100+k].longer;}cout<<"----路程所需费用："<<longers*0.5<<"元，祝您路途愉快！----"<<endl;}else{string takeName[2][5];//存放两条路线上可转乘车站的名称；int takeNum[2][5];//存放两条路线上可转乘车站的编号；int a,b;//a、b是计数的for(a=0;a<2;a++)for(b=0;b<5;b++){takeName[a][b]=" ";takeNum[a][b]=0;}//遍历每条路线可换乘的站点for(a=0,b=0;a<busStationNum[x/100-1];a++)if(line[x/100-1][a].take){takeName[0][b]=line[x/100-1][a].busStationName;takeNum[0][b]=line[x/100-1][a].number;b++;}for(a=0,b=0;a<busStationNum[y/100-1];a++)if(line[y/100-1][a].take){takeName[1][b]=line[y/100-1][a].busStationName;takeNum[1][b]=line[y/100-1][a].number;b++;}//比较可换乘的站点是否有相同的，如果有，可以了一次换乘到达目的地；否则不可以bool nn=false;for(a=0;a<5;a++){for(b=0;b<5;b++){if(takeName[0][a]!=" "&&takeName[1][b]!=""&&takeName[0][a]==takeName[1][b]){cout<<"您可以【1】次换乘到达目的地（换乘点前面有“*”提示），为你选择的路线如下："<<endl;l=takeNum[0][a]%100;if(l-i>0){for(k=0;k<l-i;k++){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k].longer;}cout<<"*"<<line[x/100-1][x%100+k].busStationName<<"-->";// money+=line[x/100-1][x%100+k].longer;}else{for(k=0;k>l-i;k--){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k-1].longer;}cout<<"*"<<line[x/100-1][x%100+k].busStationName<<"-->";// money+=line[x/100-1][x%100+k].longer;}l=takeNum[1][b]%100;if(j-l>0){longers+=line[y/100-1][l].longer;for(k=1;k<j-l;k++){cout<<line[y/100-1][l+k].busStationName<<"-->";longers+=line[y/100-1][l+k].longer;}cout<<line[y/100-1][l+k].busStationName<<endl;}else{//money+=line[y/100-1][l-1].longer;for(k=-1;k>j-l;k--){cout<<line[y/100-1][l+k].busStationName<<"-->";longers+=line[y/100-1][l+k].longer;}cout<<line[y/100-1][l+k].busStationName<<endl;longers+=line[y/100-1][l+k].longer;}cout<<"----路程所需费用："<<longers*0.5<<"元，祝您路途愉快！----"<<endl;nn=true;break;}else if(a==4&&b==4)cout<<"很抱歉，没有【0】次换乘或【1】次换乘可以到达目的地的路线！";}if(nn)break;}}}四、源程序代码Bus.h：#include<iostream>#include<string>using namespace std;template <typename T>class Bus{public:struct BusStation{int number; //车站编号string busStationName;//车站名称bool take; //是否可乘换int longer; //到下一个车站的路程};Bus();~Bus();void input();void output();void findline();//查找线路void readfile();//读取公交路线数据void writefile();//存入公交路线数据typedef BusStation* Pointer;private:Pointer *line; //指向三条路线的指针int lineNum;//路线数int *busStationNum;//每条路线的车站数};template<typename A>class Administrator{public:Administrator();~Administrator();void readAdministrator();//读取管理员资料void writeAdministrator();//存入管理员资料void addAdministrator();//增加用户void deleteAdministrator();//删除用户bool land();private:string *name;string *mima;int num;};/////////////////////////////////////////////////////////////////////////// Bus.cpp#include"Bus.h"#include<fstream>template<typename T>Bus<T>::Bus(){lineNum=0;line=new Pointer[lineNum];//三条线路busStationNum=new int [lineNum];//每条线路的车站数}template<typename T>Bus<T>::~Bus(){for(int i=0;i<lineNum;i++)delete [] line[i];lineNum=0;delete [] busStationNum;delete [] line;}template<typename T>void Bus<T>::input(){cout<<"请输入公交线路数：";cin>>lineNum;line=new Pointer[lineNum];//三条线路busStationNum=new int [lineNum];//每条线路的车站数for(int a=0;a<lineNum;a++){cout<<"请输入第"<<a+1<<"条公交线路的车站数：";cin>>busStationNum[a];}for(int b=0;b<lineNum;b++)line[b]=new BusStation[busStationNum[b]];//依据每条线路的车站数创建每条线路int k,m,i,j;//k指前一线，m指后一线，i指要比较的前一线的车站，j指要比较的后一线的车站cout<<"请依次输入每个车站的名称、到下一站点的距离："<<endl;for(i=0;i<lineNum;i++){cout<<"第"<<i+1<<"条路线的资料"<<endl;for(j=0;j<busStationNum[i];j++){line[i][j].number=(i+1)*100+j;//设置每个车站的编号line[i][j].take=false;//初始化每个车站为不可换乘cin>>line[i][j].busStationName;if(j<busStationNum[i]-1)cin>>line[i][j].longer;//到下一站点有3公里elsecin>>line[i][j].longer;}}//以下是要找出线路中可换乘的车站for(k=0,m=k+1;k<lineNum-1;)//每条路线的站点与另一条路线的站点进行比较{for(i=0;i<busStationNum[k];i++)for(j=0;j<busStationNum[m];j++){if(line[k][i].busStationName==line[m][j].busStationName){line[k][i].take=true;line[m][j].take=true;}}if(m>=lineNum-1){k++;m=k;}m++;}}template<typename T>void Bus<T>::output(){cout<<"编码";cout<<"车站名称";cout<<"到下一站的距离";cout<<"是否可以乘换"<<endl;cout<<setiosflags(ios::left);for(int i=0;i<lineNum;i++){for(int j=0;j<busStationNum[i];j++){cout<<setw(6)<<line[i][j].number;cout<<setw(20)<<line[i][j].busStationName;cout<<setw(20)<<line[i][j].longer;if(line[i][j].take)cout<<"是"<<endl;elsecout<<"否"<<endl;}cout<<endl;}}template<typename T>void Bus<T>::findline(){int x,y,i,j,k,l,longers;longers=0;//x、y是起始和终止车站的编码；i、j是每个站点后两位编码；k是每个站点后两位编码的差值；l是转乘站点的后两位编码while(1){cout<<"请输入起始站点编号：";cin>>x;cout<<" 终止站点编号：";cin>>y;if((x/100)>lineNum||(x/100)<=0||(x%100)>=busStationNum[x/100-1]||(y/100)>lineNum ||(y/100)<=0||(y%100)>=busStationNum[y/100-1])//前两个是判断车站编码的首位的，第三个是判断车站编码的后两位的cout<<"----找不到您所输入站点，请重新输入！----"<<endl;elsebreak;}i=x%100;j=y%100;if((x/100)==(y/100)){cout<<"您可【0】次换乘到达目的地，路线如下："<<endl;// k=j-i;if(j-i>0){for(k=0;k<j-i;k++){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k].longer;}cout<<line[x/100-1][x%100+k].busStationName<<endl;}else{for(k=0;k>j-i;k--){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k-1].longer;}cout<<line[x/100-1][x%100+k].busStationName<<endl;longers+=line[x/100-1][x%100+k].longer;}cout<<"----路程所需费用："<<longers*0.5<<"元，祝您路途愉快！----"<<endl; }else{string takeName[2][5];//存放两条路线上可转乘车站的名称；int takeNum[2][5];//存放两条路线上可转乘车站的编号；int a,b;//a、b是计数的for(a=0;a<2;a++)for(b=0;b<5;b++){takeName[a][b]=" ";takeNum[a][b]=0;}//遍历每条路线可换乘的站点for(a=0,b=0;a<busStationNum[x/100-1];a++)if(line[x/100-1][a].take){takeName[0][b]=line[x/100-1][a].busStationName;takeNum[0][b]=line[x/100-1][a].number;b++;}for(a=0,b=0;a<busStationNum[y/100-1];a++)if(line[y/100-1][a].take){takeName[1][b]=line[y/100-1][a].busStationName;takeNum[1][b]=line[y/100-1][a].number;b++;}//比较可换乘的站点是否有相同的，如果有，可以了一次换乘到达目的地；否则不可以bool nn=false;for(a=0;a<5;a++){for(b=0;b<5;b++){if(takeName[0][a]!=" "&&takeName[1][b]!=""&&takeName[0][a]==takeName[1][b]){cout<<"您可以【1】次换乘到达目的地（换乘点前面有“*”提示），为你选择的路线如下："<<endl;l=takeNum[0][a]%100;if(l-i>0){for(k=0;k<l-i;k++){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k].longer;}cout<<"*"<<line[x/100-1][x%100+k].busStationName<<"-->";// money+=line[x/100-1][x%100+k].longer;}else{for(k=0;k>l-i;k--){cout<<line[x/100-1][x%100+k].busStationName<<"-->";longers+=line[x/100-1][x%100+k-1].longer;}cout<<"*"<<line[x/100-1][x%100+k].busStationName<<"-->";// money+=line[x/100-1][x%100+k].longer;}l=takeNum[1][b]%100;if(j-l>0){longers+=line[y/100-1][l].longer;for(k=1;k<j-l;k++){cout<<line[y/100-1][l+k].busStationName<<"-->";longers+=line[y/100-1][l+k].longer;}cout<<line[y/100-1][l+k].busStationName<<endl;}else{//money+=line[y/100-1][l-1].longer;for(k=-1;k>j-l;k--){cout<<line[y/100-1][l+k].busStationName<<"-->";longers+=line[y/100-1][l+k].longer;}cout<<line[y/100-1][l+k].busStationName<<endl;longers+=line[y/100-1][l+k].longer;}cout<<"----路程所需费用："<<longers*0.5<<"元，祝您路途愉快！----"<<endl;nn=true;break;}else if(a==4&&b==4)cout<<"很抱歉，没有【0】次换乘或【1】次换乘可以到达目的地的路线！";}if(nn)break;}}//cout<<"还未写代码";}template<typename T>void Bus<T>::readfile(){ifstream infile("f1.txt",ios::in);if(!infile){cerr<<"open error!"<<endl;exit(1);}infile>>lineNum;line=new Pointer[lineNum];//三条线路busStationNum=new int [lineNum];//每条线路的车站数for(int a=0;a<lineNum;a++){infile>>busStationNum[a];}for(int b=0;b<lineNum;b++)line[b]=new BusStation[busStationNum[b]];//依据每条线路的车站数创建每条线路for(int i=0;i<lineNum;i++)for(int j=0;j<busStationNum[i];j++){infile>>line[i][j].number;infile>>line[i][j].busStationName;infile>>line[i][j].longer;infile>>line[i][j].take;}cout<<"----读取成功----"<<endl;infile.close();}template <typename T>void Bus<T>::writefile(){ofstream outfile("f1.txt",ios::out);if(!outfile){cerr<<"open error!"<<endl;exit(1);}outfile<<lineNum<<" ";for(int a=0;a<lineNum;a++){outfile<<busStationNum[a]<<" ";}for(int i=0;i<lineNum;i++)for(int j=0;j<busStationNum[i];j++){outfile<<line[i][j].number<<" ";outfile<<line[i][j].busStationName<<" ";outfile<<line[i][j].longer<<" ";outfile<<line[i][j].take<<" ";}cout<<"----存入成功----"<<endl;outfile.close();}//////////////////////////////////////////////template <typename A>Administrator<A>::Administrator(){num=0;name=new string[num];mima=new string[num];}template<typename A>Administrator<A>::~Administrator(){num=0;delete [] name;delete [] mima;name=NULL;mima=NULL;}template<typename A>void Administrator<A>::readAdministrator() {ifstream infile("Administrator.txt",ios::in);if(!infile){cerr<<"open error!"<<endl;exit(1);}infile>>num;name=new string[num];mima=new string[num];for(int i=0;i<num;i++){infile>>name[i]>>mima[i];}}template<typename A>void Administrator<A>::writeAdministrator() {ofstream outfile("Administrator.txt",ios::out);if(!outfile){cerr<<"open error!"<<endl;exit(1);}outfile<<num<<" ";for(int i=0;i<num;i++){outfile<<name[i]<<" ";outfile<<mima[i]<<" ";}}template<typename A>bool Administrator<A>::land(){string myname;string mymima;cout<<"请输入管理员帐号：";cin>>myname;cout<<" 密码：";char ch;while ((ch=getch())!=13) //输入密码时显示星号功能。
课程设计报告题目：武昌地区公交查询与换乘推荐课程名称：数据结构课程设计专业班级：学号：姓名：指导教师：报告日期：计算机科学与技术学院任务书设计内容掌握图、查找、排序等数据结构的物理存储结构与基本算法，通过解决较复杂的基于图模型的实际问题，提高学生对数据结构知识综合运用的技能与实践能力。
设计要求（1）从互联网或相关资料获取可靠的武汉公交线路及其地理数据，通过线性结构与图模型对其进行表示，且以文件保存。
（2）图形方式显示上述图模型与求解结果。
（3）界面友好，实现的功能包括：录入与修改公交线路信息；查询所有线路信息（线路名号、起点、终点、首末车时间、票价规则），按线路名或起点站名排序；查询指定线路的详情（沿途站点、首末车时间、票价规则、站间距离等）；查询某一位置途经的所有公交线路、指定起点与终点，推荐乘车方案（如要求换乘次数最少、路线最短或无要求条件等）。
参考文献[1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,1997[2] 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,1999[3] 博客园，华山大师兄的博客，最短路径——Dijkstra算法和Floyd算法/biyeymyhjob/archive/2012/07/31/2615833.html#33 39167目录1 引言 (4)1.1 课题背景与意义 (4)1.1.1 公交出行 (4)1.2国内外研究现状 (4)1.3课程设计的主要研究工作 (4)2 系统需求分析与总体设计 (7)2.1系统需求分析 (7)2.2 系统总体设计 (7)3 系统详细设计 (8)3.1有关数据结构的定义 (8)3.2 主要算法设计 (9)4 系统实现与测试 (14)4.1 系统实现 (14)4.2 系统测试 (15)5 总结与展望 (21)5.1 全文总结 (21)5.1 工作展望 (22)6. 附录 (22)1 引言1.1课题背景与意义1.1.1 公交出行公交出行是现在城市生活中必不可少的一种出行方式。
公交线路换乘系统设计方案一、引言随着城市规模的不断扩大和人口增长的加速，公交交通作为一种重要的城市公共交通方式，承担着越来越多的出行需求。
然而，由于公交线路的复杂性和出行人数的增加，公交换乘所带来的不便已成为很多城市居民的痛点。
因此，设计一套高效便捷的公交线路换乘系统具有重要意义。
二、系统概述公交线路换乘系统是一种基于计算机技术的智能交通系统，旨在提供快速、准确和便捷的公交换乘方案。
该系统通过收集和处理公交线路数据、交通流量数据、用户出行数据等信息，利用算法和模型优化公交线路，以提高公交换乘的效率和用户体验。
三、系统功能1. 数据采集和处理：系统需要收集公交线路、站点、交通流量等数据，并对数据进行处理和整理，以便后续的换乘优化和查询功能。
2. 换乘优化：基于用户出行数据和交通流量数据，系统可以通过算法和模型计算出最优的换乘方案，包括最短时间、最少换乘次数、最少步行距离等多个指标。
3. 查询和推荐：系统可以提供用户查询和推荐功能，用户可以根据自身需求输入起点和终点，系统将根据算法和模型提供最佳的换乘方案，并提供乘车时间、换乘站点、步行距离等相关信息。
4. 实时更新：系统可以实时更新公交线路数据和交通流量数据，以保证换乘方案的准确性和时效性。
5. 用户反馈：系统可以提供用户反馈和评价功能，用户可以对换乘方案进行评价和意见反馈，以便系统进行优化和改进。
四、系统设计1. 数据采集和处理：系统需要与公交运营公司合作，获取实时的公交线路、站点和交通流量数据。
采集到的数据将会通过数据处理模块进行清洗和整理，以便后续的计算和查询。
2. 换乘优化：系统将根据用户出行数据和交通流量数据建立模型，并运用优化算法对公交线路进行优化。
优化的目标可以是最短时间、最少换乘次数、最少步行距离等，以提供用户最优的换乘方案。
3. 查询和推荐：系统提供用户输入起点和终点的查询功能，通过模型和算法计算出最佳的换乘方案，并将结果展示给用户。
公交路线查询系统（基于数据结构和C语言）#include#include#include#include#define max 30#define len 20#define MAX 100typedef struct Linedot{//站int stopno;//站号char stopname[max];//站名struct Linedot *next;}linedot,*dot;typedef struct lineway{//线路int lineNo;//线路号int stopnum;//该线路上站的个数dot stop;//站}way;typedef struct lineNode{int linenum;//线路条数way data[len];//线路}line;typedef struct co_Node{int zhanNo;int busNo;struct co_Node *next;}co_node,*co_zhan;typedef struct Node{int firstbus;//始发车号char stopname[max];//站名co_zhan zhan;}node,*list;typedef struct zhanNode{int vexnum;//顶点数int arcnum;//弧数node vexs[max];//顶点}spot;typedef struct sqNode//定义双向队列{int data;struct sqNode *prior;struct sqNode *next;}sqnode,*sqlist;typedef struct//双向链队列类型{sqlist front;sqlist rear;}LQ;void initqueue(LQ *Q)//初始化队列{Q->front=Q->rear=new sqnode;Q->front->data=Q->rear->data=-1;Q->front->next=Q->rear->next=NULL; Q->front->prior=Q->rear->prior=NULL; }void enqueue(LQ *Q,int e)//进队{sqlist p;p=new sqnode;p->data=e;p->next=NULL;p->prior=Q->front;Q->rear->next=p;Q->rear=p;}void dequeue(LQ *Q,int *e)//出队{Q->front=Q->front->next;if(Q->front!=NULL)*e=Q->front->data;else*e=-1;}typedef struct stackNode//定义栈{int figuer;struct stackNode *next;}stacknode,*stack;void initstack(stack *S)//初始化栈{*S=NULL;}void push(stack *S,int e)//进栈{stack p;p=new stacknode;p->figuer=e;p->next=*S;*S=p;}int pop(stack *S,int *e)//出栈{stack p=*S;if(p==NULL){printf("栈空!\n");return 0;}*e=p->figuer;*S=(*S)->next;delete p;return 1;}void gettop(stack S,int *e)//得到栈顶{if(S==NULL){printf("栈空!\n");return;}*e=S->figuer;}int locate(spot C,char e[]){int i;for(i=0;i<c.vexnum;i++){if(strcmp(C.vexs[i].stopname,e)==0)return i;}if(i>C.vexnum){printf("Not found!\n");return -1;}}void init(FILE *fp,line *W,spot *C)//公交线路初始化{dot p,q;co_zhan R;int i,j,m,n,num;char vex1[max],vex2[max];if((fp=fopen("f.txt","r"))==NULL)//打开文件{printf("The file error!\n");getchar();exit(0);}fscanf(fp,"%d",&W->linenum);for(i=0;ilinenum;i++)fscanf(fp,"%d%d",&W->data[i].lineNo,&W->data[i].stopnu m);//输入线路号和该线路上站的个数for(i=0;ilinenum;i++){W->data[i].stop=NULL;for(j=0;jdata[i].stopnum;j++){p=new linedot;p->next=NULL;fscanf(fp,"%d%s",&p->stopno,p->stopname);//输入站名q=W->data[i].stop;if(!q)W->data[i].stop=p;else{while(q->next)q=q->next;</c.vexnum;i++)q->next=p;}}}fscanf(fp,"%d%d",&C->vexnum,&C->arcnum);for(i=0;ivexnum;i++){fscanf(fp,"%s%d",C->vexs[i].stopname,&C->vexs[i].firstbus); C->vexs[i].zhan=NULL;}for(i=0;iarcnum;i++){fscanf(fp,"%s%s%d",vex1,vex2,&num);m=locate(*C,vex1);n=locate(*C,vex2);R=new co_node;R->zhanNo=n;R->busNo=num;R->next=C->vexs[m].zhan;C->vexs[m].zhan=R;}}void search1(line W)//查询指定车次的线路及途经站点{dot p;int i,n,k=0;printf("请输入车次:");scanf("%d",&n);for(i=0;i<w.linenum;i++){if(W.data[i].lineNo==n){p=W.data[i].stop;while(p){if(k==0)printf("%s",p->stopname);elseprintf("->%s",p->stopname);p=p->next;k++;}}}}void search2(line W,spot C){int k,i;char vex[max];dot p;printf("请输入站点名:");scanf("%s",vex);k=locate(C,vex);if(C.vexs[k].firstbus!=0)printf("该站点的始发车有:%d\n",C.vexs[k].firstbus); elseprintf("该站无始发车!\n");printf("该站点的过路车有:");for(i=0;i<w.linenum;i++)p=W.data[i].stop;if(!p)continue;while(p){if(strcmp(p->stopname,vex)==0&&p!=W.data[i].stop) printf("%d ",W.data[i].lineNo);p=p->next;}}}int stackempty(stack S){if(S==NULL)return 1;return 0;}void updown(stack S,stack *S1){stack p;while(!stackempty(S)){p=new stacknode;p->figuer=S->figuer;p->next=*S1;*S1=p;S=S->next;}void printstack(spot C,stack S)//打印栈里的元素{stack S1,p;co_zhan q;initstack(&S1);updown(S,&S1);p=S1;while(p){ q=C.vexs[p->figuer].zhan;while(q){if(p->next==NULL)break;if(q->zhanNo!=p->next->figuer)q=q->next;elsebreak;}printf("%s-%d->",C.vexs[p->figuer].stopname,q->busNo); p=p->next;}}void printqueue(sqlist Q,spot C){sqlist p;stack S,S1;initstack(&S);initstack(&S1);p=Q;while(p->data!=-1){push(&S,p->data);p=p->prior;}updown(S,&S1);printstack(C,S1);}void search3(spot C,int s,int e) {co_zhan p;int flag;LQ Q;sqlist q;int u,k,i=1;initqueue(&Q);enqueue(&Q,s);while(Q.front!=Q.rear){dequeue(&Q,&u);p=C.vexs[u].zhan;if(u==e){printf("-->>Line%d:",i++); printqueue(Q.front->prior,C); printf("%s\n",C.vexs[e].stopname);dequeue(&Q,&u);if(u==-1)break;p=C.vexs[u].zhan;}while(p){k=p->zhanNo;q=Q.front;while(q->prior!=NULL){if(q->data!=k){q=q->prior;flag=1;}else{flag=0;break;}}if(k!=s&&flag==1)enqueue(&Q,k);p=p->next;}}}void search4(spot C,int s,int e,LQ *Q,int visit[]){int u,k;co_z</w.linenum;i++)</w.linenum;i++)han p;if(!visit[s]){visit[s]=1;enqueue(Q,s);while(Q->front!=Q->rear){dequeue(Q,&u);p=C.vexs[u].zhan;if(u==e){printf("-->>Line:");printqueue(Q->front->prior,C); printf("%s\n",C.vexs[e].stopname); break;}while(p){k=p->zhanNo;if(!visit[k]){visit[k]=1;enqueue(Q,k);}}}}}int count(spot C,stack S,int e){int i,j,n=0,No=-1;stack p;co_zhan q;p=S;while(p){i=p->figuer;p=p->next;if(!p)break;j=p->figuer;q=C.vexs[i].zhan;while(q){if(q->zhanNo==j&&q->busNo!=No) {n++;No=q->busNo;break;}else}}return n-1;}void destroy(stack *S){stack p=*S;while(!stackempty(*S)){*S=(*S)->next;delete(p);p=*S;}}void savestack(stack S,stack *S2) {stack S1;initstack(&S1);updown(S,&S1);updown(S1,S2);}void change(sqlist Q,stack *S) {sqlist p;p=Q;while(p->data!=-1){push(S,p->data);p=p->prior;}}void search5(spot C,int s,int e,stack *S,stack *S2,int *m) {co_zhan p;int flag;LQ Q;sqlist q;int u,k,n1,n=MAX,i=1;initqueue(&Q);enqueue(&Q,s);while(Q.front!=Q.rear){dequeue(&Q,&u);p=C.vexs[u].zhan;if(u==e){change(Q.front,S);n1=count(C,*S,e);if(n1<n){savestack(*S,S2);n=n1;*m=n;}destroy(S);dequeue(&Q,&u);if(u==-1)break;p=C.vexs[u].zhan;}while(p){k=p->zhanNo;q=Q.front;while(q->prior!=NULL) {if(q->data!=k){q=q->prior;flag=1;}else{flag=0;break;}}if(k!=s&&flag==1) enqueue(&Q,k);p=p->next;}}}int menu(){int n;printf("*******************欢迎使用K城公交查询系统******************\n");printf("**************1.查询指定车次的线路及途经站点****************\n");printf("**************2.查询指定站点的始发车和过路车****************\n");printf("**************3.查询指定起点和终点所经的所有线路************\n");printf("**************4.查询指定起点和终点所经站点最少的线路********\n");printf("**************5.查询指定起点和终点换乘次数最少的乘车路线****\n");printf("**************0.退出****************************************\n");printf("******************************************************* *****\n");printf("-----起点站:电力大学/朱辛庄/北郊农场桥东/京昌路回龙观/北京师\n");printf(" 范大学/德胜门西/清华大学西门/圆明园/颐和园/香山\n");printf("-----终点站:电力大学/朱辛庄/北郊农场桥东/京昌路回龙观/北京师\n");printf(" 范大学/德胜</n)门西/清华大学西门/中关村/圆明园/颐和园\n");printf(" /西单\n");printf("-----公交线路:345/442/696/681/699/826\n");printf("******************************************************* *****\n");printf("请选择:");scanf("%d",&n);getchar();return n;}void main(){stack S,S2,S3;LQ Q;int n,m,i,s,e,k=1,visit[len],u; char ch='Y',start[max],end[max]; FILE *fp;line W;spot C;init(fp,&W,&C);do{n=menu();switch(n){case 1:search1(W);break;case 2:search2(W,C);break; case 3:for(i=0;i<len;i++)visit[i]=0;initstack(&S);printf("请输入起点和终点:"); scanf("%s%s",start,end);s=locate(C,start);e=locate(C,end);printf("%s到%s的所有路线如下:\n",C.vexs[s].stopname,C.vexs[e].stopname);search3(C,s,e);break;case 4:for(i=0;i<len;i++)visit[i]=0;initqueue(&Q);printf("请输入起点和终点:");scanf("%s%s",start,end);s=locate(C,start);e=locate(C,end);printf("%s到%s的最短路线如下:\n",C.vexs[s].stopname,C.vexs[e].stopname);search4(C,s,e,&Q,visit);break;case 5:initstack(&S);initstack(&S2);initstack(&S3);printf("请输入起点和终点:");scanf("%s%s",start,end);s=locate(C,start);e=locate(C,end);printf("%s到%s的最少换乘路线如下:\n",C.vexs[s].stopname,C.vexs[e].stopname);search5(C,s,e,&S,&S2,&m);updown(S2,&S3);pop(&S3,&u);printf("-->>Line:");printstack(C,S3);printf("%s\n",C.vexs[e].stopname); printf("共换乘%d次\n",m);break; case 0:exit(0);break;default:printf("error!\n");}getchar();printf("\n继续吗？Y/N:");scanf("%c",&ch);}while(ch=='Y'||ch=='y');}</len;i++)</len;i++)。
《数据结构与算法设计》课程设计任务书数据结构与算法设计课程设计专业数学与应用数学班级数学0701 学号 0124 姓名孙宝琳完成日期指导教师（签名）1、程序设计说明书【设计题目】公交咨询程序【问题描述】利用图实现公交咨询系统，包括公交线路查询、站点查询以及最优乘车方案的查询。
【软件功能】1 从文件中接收图和公交车信息；2 可实现确定公交线路查询，即输出该车的所有站点；3 可以对某一个站点进行查询输出该站点的所有下一站；4可以对乘车方案进行查询，即输出确定起点，终点的最优乘车方案，换车输出换车次数及换车站点；【算法思想】设计公交车类（车号，路程长度，终点站），图类（站点名，公交车类，现有路线条数，现有站点数），Dijkstra算法类（最短路径上的最后一个站点，最短路径的站点数）；从文件中接收内容并对图和公交车进行初始化，公交线路查询——在图中找到起点站，按顺序输出所有公交车号相同的站点；乘车方案中利用Dijkstra算法算出最优路线并有最短路径的最后一个站点输出乘车方案；【类的设计】struct Busxt”，并输入以下内容：30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;（每一个车的线路占一行）；编译运行程序，根据提示执行程序；要想有更为准确的方案，可以在“公交查询.txt”中加入公交车线路；2、程序上机调试报告【语法错误及其排除】1 函数赋值时，将变量赋给了指针；使用指针传值；2 在出栈时没有判断栈是否为空，导致top指空在出栈前判断IsEmpty（）；【算法错误及其排除】1在建立图中没有对a数组进行置空，导致数据混乱；在使用a之前对a数组赋空；2在输出最优结果时没有保留前一站使程序无法判断是否换车加入b数组保留前一站；3、程序测试结果【测试数据】30世家星城-通讯学院-石油公寓-潘家庄-明德门-杨家村-城南客运站-西八里村-医学院-纬二街-雁南路-大雁塔-赛格电脑城-李家村-和平门-大差市-五路口-火车站;603电视塔-国展中心-吴家坟-八里村-纬二街-小寨-长安立交-省体育场-草场坡-南稍门-南门-钟楼-北门-火车站;37城北客运站-公交六公司-方新村-龙首村-北关-钟楼-东门-兴庆路-建工路-幸福路南口;（每一个车的线路占一行）；【输出结果】1公交线路查询：2 站点查询：3 最优方案：【程序性能评价】使用简单；结果正确、明了；【性能改进方向】1.将邻接矩阵改为三维，即在相同两站间由多个公交可以到达；2.在站点里加入方位，即在寻找最优结果的时候可以不必将所有站点进行操作，加快运行速度；3.在公交车类中加入收费，在最优结果输出时计算收费(有刷卡、投币、按站收费)；【收获及体会】通过这个程序的编写使我对c++中文件的操作、图的操作、栈的操作、查找等内容有了更深的理解，在编译的过程中也是我知道了自己的数据结构课程内容还很浅，还需要在努力；4、源程序代码#include<>umber=-1;buses[i].length=0;}}void Insertstate(char state[]) xt"); xt'"<<endl;exit(0);}while(!()&¤tbus<Maxbus) umber; us_state[k++],a); us_state[k++],a);Insertstate(a);buses[currentbus].length=k; ength-1;k++) us_state[k],buses[i].bus_state[k+1],buses[i].number);}bool IsGraphFull() umber==number)break;if(i==currentbus)cout<<"查无此车!"<<endl;else{ us_state[0]<<"<—>"<<buses[i].bus_state[buses[i].length-1]<<"）"<<endl;for(int j=0;j<buses[i].length-1;j++)cout<<buses[i].bus_state[j]<<"<—>";cout<<buses[i].bus_state[j]<<endl;}}int searchbusnumber(char v0[],char v1[]) umber)break;for(k=0;k<buses[l].length;k++){if(strcmp(buses[l].bus_state[k],v0)==0)i=k;if(strcmp(buses[l].bus_state[k],v1)==0)j=k;}if(i<j) us_state[0]<<"->"<<buses[l].bus_state[buses[l].length-1]<<"）"<<endl;elsecout<<"（"<<buses[l].bus_state[0]<<"<-"<<buses[l].bus_state[buses[l].length-1]<<"）"<<endl;}friend void busline(); 交线路查询"<<endl;cout<<" 2.站点查询"<<endl;cout<<" 3.最优乘车方案查询"<<endl;cout<<" 4.退出系统"<<endl;cout<<"请输入您要选择的服务:";cin>>flag;cout<<endl;switch(flag){case 1:busline();break; 定车号的公交查询"<<endl;cout<<" 2.已有所有公交线路浏览"<<endl;cout<<" 3.返回首页"<<endl;cout<<"请输入您要选择的服务:";cin>>flag;cout<<endl;switch(flag){case 1:cout<<"请输入车号:"; umber);mainsurface();break;case 3:default:mainsurface();break;}}void searchstate() //站点查询{char name[20];Graph map; //建立图();cout<<" 站点查询"<<endl;cout<<"请输入要查询的站点:";cin>>name;for(int i=0;i<;i++) //查找站点if(strcmp[i],name)==0)break;if(i==cout<<"查无此站!"<<endl;else{ //找到，在图中找到它的下一站，及所到的公交车cout<<endl<<name<<"的下一站有："<<endl;for(int j=0;j<;j++)if[i][j]>0&&[i][j]<MaxValue){cout<<[j]<<" "<<[i][j];(name,[j]);}}mainsurface();}int main(){mainsurface(); //调用主界面return 0;}。
数据结构实验报告-交通指南数据结构实验报告交通指南一、引言随着城市的发展和人口的增长，交通问题日益复杂。
为了更好地理解和优化交通系统，我们进行了本次数据结构实验，旨在通过对交通数据的分析和处理，为人们提供更准确、实用的交通指南。
二、实验目的本次实验的主要目的是利用数据结构和算法，对交通数据进行存储、管理和分析，从而为用户提供最佳的出行路线规划和交通信息查询服务。
三、实验环境我们使用了以下工具和环境进行实验：1、编程语言：Python2、相关库：numpy、pandas、matplotlib、networkx3、开发工具：PyCharm四、数据来源与预处理1、数据来源我们获取了城市交通网络的相关数据，包括道路节点、路段长度、道路通行能力等信息。
此外，还收集了实时的交通流量数据和历史交通事故数据。
2、数据预处理为了使数据能够被有效地处理和分析，我们进行了以下预处理操作：数据清洗：去除重复、错误和缺失的数据。
数据转换：将数据转换为适合算法处理的格式。
数据归一化：对数据进行归一化处理，以便于比较和计算。
五、数据结构选择与算法设计1、数据结构选择我们选择了图数据结构来表示交通网络，其中节点表示道路的交叉点，边表示道路路段，边的权重表示路段的长度或通行时间。
使用邻接表来存储图，以便快速查找相邻节点和边的信息。
2、算法设计最短路径算法：采用迪杰斯特拉（Dijkstra）算法计算两点之间的最短路径。
最小生成树算法：使用普里姆（Prim）算法构建交通网络的最小生成树，以分析关键道路路段。
交通流量预测算法：基于历史交通流量数据，使用线性回归或时间序列分析方法进行预测。
六、实验结果与分析1、最短路径查询输入起始点和终点，能够快速准确地计算出最短路径，并给出路径的详细信息，包括经过的节点和路段。
通过对多个起点和终点的测试，验证了算法的正确性和效率。
2、交通拥堵分析根据实时交通流量数据，能够识别出拥堵路段，并分析拥堵的原因（如道路施工、事故等）。
数据结构公交换乘系统一、系统概述数据结构公交换乘系统是一种基于数据结构算法的智能化交通规划系统，旨在提供高效、准确的公交换乘服务。
该系统通过分析用户出发地和目的地，结合公交线路数据、交通拥堵情况等信息，计算出最佳的公交换乘方案，为用户提供准确的出行指导。
二、系统功能1. 用户注册与登录用户可以通过手机号码或邮箱注册账号，并通过账号登录系统。
登录后，用户可以享受系统提供的各项功能。
2. 输入出发地和目的地用户可以在系统界面中输入出发地和目的地的信息，包括地点名称、地理坐标等。
系统将根据用户输入的信息进行后续处理。
3. 公交线路查询系统根据用户输入的出发地和目的地，查询公交线路数据，并进行路径规划。
系统将根据用户的出行需求和实时交通情况，计算出最佳的公交换乘方案。
4. 换乘方案展示系统将计算出的最佳换乘方案展示给用户，包括具体的公交线路、乘车站点、换乘路线等信息。
用户可以根据系统提供的方案进行出行决策。
5. 实时交通信息更新系统会实时获取交通拥堵情况、公交车实时位置等信息，并对方案进行动态调整。
用户可以获取最新的交通信息，以便做出更合理的出行决策。
6. 路线导航用户选择最佳换乘方案后，系统将提供路线导航功能，指导用户如何步行至乘车站点、换乘公交线路及下车位置。
系统可以通过地图、文字等方式提供导航指引。
7. 历史记录与收藏系统会记录用户的出行历史，并提供历史记录查询功能。
用户还可以将常用的出行方案收藏起来，方便下次查询。
三、系统设计1. 数据存储系统需要存储大量的公交线路数据、地理信息数据等。
可以采用数据库来存储这些数据，以便系统能够高效地进行查询和处理。
2. 数据结构设计系统需要设计合适的数据结构来存储和处理公交线路数据、地理信息数据等。
可以使用图、树、队列等数据结构来表示和计算公交线路、路径规划等。
3. 算法设计系统需要设计高效的算法来进行公交线路查询和路径规划。
可以使用最短路径算法、深度优先搜索算法等来计算最佳换乘方案。
数据结构—交通系统数据结构—交通系统1：引言交通系统是一个城市或地区顺畅运行的重要组成部分。
为了有效管理和优化交通流量，需要设计和实现一个高效的交通系统。
本文档将介绍一个基于数据结构的交通系统设计。
2：整体架构交通系统可以分为以下几个模块：2.1 路网管理模块该模块负责管理整个路网的基础数据，包括道路、交叉口、车道、信号灯等信息。
2.2 路况监测模块该模块通过传感器和摄像头等设备对交通路况进行实时监测，并将数据反馈给系统。
2.3 路径规划模块该模块根据用户的起点和终点，利用路网数据和实时路况信息，计算出最优路径。
2.4 交通管理模块该模块根据实时路况和路径规划结果，控制信号灯、调整车道使用情况，以优化交通流量。
3：路网管理模块3.1 道路管理道路包括道路名称、起点和终点位置、道路长度等属性。
可以使用线性表或图来表示道路之间的连接关系。
3.2 交叉口管理交叉口是道路交汇的地方，包括交叉口名称、交叉口坐标、交通灯状态等属性。
可以使用树来表示交叉口的层级关系。
3.3 车道管理车道是道路上划分出的车辆行驶通道，包括车道编号、车道容量、车道速度限制等属性。
可以使用链表或数组来表示车道之间的关系。
4：路况监测模块4.1 传感器数据采集通过部署传感器设备，采集道路状况、车辆数量等数据。
可以使用数组或链表来存储和管理传感器数据。
4.2 图像识别技术利用摄像头采集交通图片，并通过图像识别技术分析车辆数量、车辆类型等信息。
可以使用图像处理算法来实现图像识别功能。
5：路径规划模块5.1 起点和终点选择用户选择起点和终点，并提供其他限制条件，例如出行时间、交通工具等。
5.2 最短路径算法利用最短路径算法，通过路网数据和实时路况信息，计算出起点到终点的最优路径。
可以使用Dijkstra算法、A算法等来实现最短路径计算。
6：交通管理模块6.1 信号灯控制根据交通流量和道路状况，动态调整信号灯的时间间隔，以控制交通流量。
6.2 车道使用管理根据车流量和道路容量，动态调整车道使用情况，例如开放或关闭车道，以优化交通流量。
数据结构公交线路换乘#include<fstream.h>//文件库#include<stdlib.h>#include<string.h>//字符串函数库const int Maxbus=100;//最大公交车数const int Maxstate=200;//最大站点数const int MaxValue=999;//最大值struct Bus //公交车类{int number; //公交车号int length; //总站数char bus_state[Maxstate][20]; //站点};class Graph //建立无向图{friend class Distance; //声明友元类private:char statename[Maxstate][20]; //站点int busnumber[Maxstate][Maxstate]; //邻接矩阵，权值为这两个站点的公交车号int currentstate; //当前站点数int currentbus; //当前公交车数Bus buses[Maxbus]; //公交车信息public:Graph() //无参构造函数，对成员变量初始化{for(int i=0;i<Maxstate;i++)for(int j=0;j<Maxstate;j++){if(i==j)busnumber[i][j]=-1; //自己到自己没有车elsebusnumber[i][j]=MaxValue;}currentstate=0;//站点数初始化为0 currentbus=0;//公交车数初始化为0for(i=0;i<Maxbus;i++){buses[i].number=-1;buses[i].length=0;}void Insertstate(char state[]) //插入一个站点{if(!IsGraphFull()) //如果图没满{for(int i=0;i<currentstate;i++) //查看该站是否已经存在if(strcmp(state,statename[i])==0)break;if(i==currentstate) //如果不存在，在站点数组后加入{strcpy(statename[currentstate],state);for(i=0;i<currentstate;i++){busnumber[currentstate][i]=MaxValue;busnumber[i][currentstate]=MaxValue;}busnumber[currentstate][currentstate]=-1;currentstate++; //当前数组加一}}}void Insertbusnumber(char V1[],char V2[],int busnum) //插入权值for(int i=0;i<currentstate;i++) //查找站点if(strcmp(V1,statename[i])==0)break;for(int j=0;j<currentstate;j++)if(strcmp(V2,statename[j])==0)break;if((i!=currentstate)&&(j!=currentstate)) //站点存在插入权值{busnumber[i][j]=busnum;busnumber[j][i]=busnum;}}void Set_graph() //图的建立{char ch[700],a[20]={'\0'};//int j=0,k=0,i;ifstream infile("公交查询.txt"); //以读的方式打开文件if(!infile) //文件打开失败，则结束程序{cout<<"Cant't open '公交查询.txt'"<<endl;exit(0);}while(!infile.eof()&&currentbus<Maxbus) //文件没有读完{infile>>buses[currentbus].number; //接收车号码infile.getline(ch,700); // 在文件中读取一行for(int i=0;ch[i]!=';';i++){if(ch[i]!='-') //把站点暂存在a中a[j++]=ch[i];else{strcpy(buses[currentbus].bus_state[k++],a); //对公交车站点赋值Insertstate(a); //插入站点for(j=0;j<20;j++)a[j]='\0'; //对a数组初始化j=0;}}strcpy(buses[currentbus].bus_state[k++],a);Insertstate(a);buses[currentbus].length=k; //当前公交车长度赋值currentbus++; //当前公交车数加一k=0;j=0;}for(i=0;i<currentbus;i++)for(k=0;k<buses[i].length-1;k++) //插入权值Insertbusnumber(buses[i].bus_state[k],buses[i].bus_state[k+1],buses[i].numb er);}bool IsGraphFull() //判断图是否已满{return currentstate==Maxstate;}void show_busmessage(int number) //输出公交信息{for(int i=0;i<currentbus;i++) //查找权值if(buses[i].number==number)break;if(i==currentbus)cout<<"查无此车!"<<endl;else{ //找到，输出该公交车信息cout<<" "<<number<<"路（"<<buses[i].bus_state[0]<<"<->"<<bu ses[i].bus_state[buses[i].length-1]<<"）"<<endl;for(int j=0;j<buses[i].length-1;j++)cout<<buses[i].bus_state[j]<<"<->";cout<<buses[i].bus_state[j]<<endl;}}int searchbusnumber(char v0[],char v1[]) //查找指定站点的公交车号码{int i,j,numb;for(int k=0;k<currentstate;k++) //查找站点{if(strcmp(v0,statename[k])==0)i=k;if(strcmp(v1,statename[k])==0)j=k;}numb=busnumber[i][j]; //在邻接矩阵中查找权值return numb;}void direction(char v0[],char v1[]) //输出指定站点的公交车方向{int i,j,numb,l;for(int k=0;k<currentstate;k++) //查找指定站点{if(strcmp(v0,statename[k])==0)i=k;if(strcmp(v1,statename[k])==0)j=k;}numb=busnumber[i][j];for(l=0;l<currentbus;l++) //查找该公交车位置if(numb==buses[l].number)break;for(k=0;k<buses[l].length;k++){if(strcmp(buses[l].bus_state[k],v0)==0)i=k;if(strcmp(buses[l].bus_state[k],v1)==0)j=k;}if(i<j) //输出公交车方向cout<<"（"<<buses[l].bus_state[0]<<"->"<<buses[ l].bus_state[buses[l].length-1]<<"）"<<endl;elsecout<<"（"<<buses[l].bus_state[0]<<"<-"<<buses[l ].bus_state[buses[l].length-1]<<"）"<<endl;}friend void busline(); //把外部函数定义为图的友元函数，以便使用图的私有成员变量friend void searchstate();friend void bestproject();friend void mainsurface();};class StackNode //栈结点{friend class Stack; //友元类private:char date[20];//结点数据StackNode *link; //结点链指针public://构造函数：结点赋值StackNode (char d[] =0,StackNode *l =NULL):link(l) {strcpy(date,d);}};class Stack //定义栈{private:StackNode *top; //栈顶指针public:Stack():top(NULL){ } //构造函数~Stack(); //析构void Push(char item[]); //进栈int Pop(char x[]);//退栈int GetTop(char x[]); //读取栈顶元素void MakeEmpty (); //把栈置空int IsEmpty(){return top == NULL;}};Stack ::~Stack(){StackNode *p;while(top != NULL){//逐结点回收p=top;top=top->link;delete p; //释放栈顶结点}}void Stack ::MakeEmpty ()//把栈置空{StackNode *p;while (top != NULL){ //逐结点回收p=top;top=top->link;delete p; //释放栈顶结点}}void Stack::Push(char item[] )//进栈{StackNode *p =new StackNode ( item, top );//新结点p->link=top; //链入*top之前top = p; //成为新栈顶}int Stack ::Pop (char x[] ) //退栈{if ( IsEmpty ( ) ) return 0;StackNode *p = top;top = top->link; //修改栈顶指针strcpy(x,p->date); //送回退栈元素delete p;return 1; //释放}int Stack::GetTop (char x[] )//读取栈顶元素{if (IsEmpty()) return 0;strcpy(x,top->date); //送回栈顶元素return 1; //释放}class Distance:public Graph //定义最短距离类{private:char path[20]; //最短距离的前一站int distance[Maxstate]; //最短距离public:void bestchooce(char v0[],char v1[]) //最优方案{int s[Maxstate],v,i,j,w,start=-1,end=-1,number1,number2; char a[20],b[20];Stack stack1; //定义栈Set_graph(); //建立图for(i=0;i<currentstate;i++) // 查找起始站、终点站{if(strcmp(statename[i],v0)==0)start=i;if(strcmp(statename[i],v1)==0)end=i;}if(start==-1||end==-1){cout<<"站点不存在!"<<endl; return ;}for( i=0;i<currentstate;i++) //初始化距离、前一站{s[i]=0; //s集合赋空if(busnumber[start][i]<MaxValue){distance[i]=1;path[i]=start;}else{distance[i]=busnumber[start][i]; //权值赋给最短距离path[i]=-1;}}s[start]=1; //起始站放入s集合distance[start]=0;int min;for(i=0;i<currentstate;i++){min=MaxValue;for(w=0;w<currentstate;w++) //在邻近的顶点中查找最短距离if(!s[w]&&distance[w]<min){v=w;min=distance[w];}s[v]=1;for(j=0;j<currentstate;j++)if(!s[j]&&(min+1)<distance[j]&&busnumber[v][j]<Ma xValue) //计算起点到每个站点的距离{distance[j]=min+1;path[j]=v;}}i=1;j=0;if(distance[end]<MaxValue&&distance[end]>0) //两个站点有公交车{cout<<" 到达"<<v1<<"共有"<<distance[end]<<"站，最优方案为:"<<endl;do //对路径上的站点入栈{stack1.Push(statename[end]);end=path[end];}while(end!=start);stack1.Pop(a); //出栈number1=searchbusnumber(v0,a); //查找两个站点的公交车号码cout<<" 乘坐"<<number1;direction(v0,a); //查找两站的公交方向cout<<v0<<"->"<<a;while(!stack1.IsEmpty()) //判断栈是否为空{stack1.Pop(b);number2=searchbusnumber(a,b); //查找下两个站间的公交车号码if(number1==number2) //判断两个车是否是同一辆{cout<<"->"<<b;i++;}else{ //不是同一辆，则换车if(i==1)cout<<" 仅有一站，建议步行"<<b<<endl;elsecout<<" 共"<<i<<"站"<<endl; cout<<" 换乘" <<number2; //输出换车信息direction(a,b);number1=number2;cout<<a<<"->"<<b;i=1;j++;}strcpy(a,b); //保留前一站}if(i==1)cout<<" 仅有一站，建议步行至"<<b<<endl; elsecout<<" 共"<<i<<"站"<<endl;if(j>0)cout<<" 共换车"<<j<<"次，"<<"请注意换车的站点"<<endl;}elseif(distance[end]==0)cout<<"您所在站点即为"<<v0<<endl;elsecout<<"从"<<v0<<"至"<<v1<<"无公交可到!"<<endl;}};void bestproject() //最优方案{Distance bestway;char start[20],end[20];cout<<"请输入起点站:"; //接收起点站和终点站cin>>start;cout<<"请输入终点站:";cin>>end;cout<<endl;bestway.bestchooce(start,end);}void mainsurface() //主界面{int flag;cout<<" 欢迎使用公交咨询系统"<<endl; //用户会话界面cout<<" 1.公交线路查询"<<endl;cout<<" 2.站点查询"<<endl; cout<<" 3.最优乘车方案查询"<<endl;cout<<" 4.退出系统"<<endl; cout<<"请输入您要选择的服务:";cin>>flag;cout<<endl;switch(flag){case 1:busline();mainsurface();break; //公交线路case 2:searchstate();mainsurface();break; //站点查询case 3:bestproject();mainsurface();break; //最优方案case 4:default:cout<<"谢谢使用!!"<<endl;}}void busline() //公交线路{int flag, a=0,i;Graph map; //建立图map.Set_graph();cout<<" 公交线路查询"<<endl; cout<<" 1.确定车号的公交查询"<<endl;cout<<" 2.已有所有公交线路浏览"<<endl; cout<<" 3.返回首页"<<endl;cout<<"请输入您要选择的服务:";cin>>flag;cout<<endl;switch(flag){case 1:cout<<"请输入车号:"; //特定车号查询cin>>a;map.show_busmessage(a);break;case 2:for(i=0;i<map.currentbus;i++) //所有路线查询map.show_busmessage(map.buses[i].number);break;case 3:default:break;}}void searchstate() //站点查询{char name[20];Graph map; //建立图map.Set_graph();cout<<" 站点查询"<<endl;cout<<"请输入要查询的站点:";cin>>name;for(int i=0;i<map.currentstate;i++) //查找站点if(strcmp(map.statename[i],name)==0)break;if(i==map.currentstate)cout<<"查无此站!"<<endl;else{ //找到，在图中找到它的下一站，及所到的公交车cout<<endl<<name<<"的下一站有："<<endl; for(int j=0;j<map.currentstate;j++)if(map.busnumber[i][j]>0&&map.busnumber[i][j]<MaxValue) {cout<<map.statename[j]<<""<<map.busnumber[i][j];map.direction(name,map.statename[j]);}}}int main(){mainsurface(); //调用主界面return 0;}。
广东海洋大学信息学院课程设计报告设计题目公交换乘系统课程名称数据结构姓名（学号）201411621146联系电话专业名称计算机科学与技术所在班级计科1141指导教师谢仕义教师职称教授起止时间2015 年11月20日至2015年12月26日评定成绩目录一、课程设计主要内容………………………………………P31.1 概况…………………………………………………………….P3 1.2 主要内容……………………………..………………….…P41.3 开发环境和工具………………………………..…………….P4二、功能和结构设计………………………………………….P4三、流程图和算法设计……………………………………………P4四、源程序代码………………………………………….…..P9五、课程设计总结………………………………………….…..P175.1 优点……………………………………………………P175.2 缺点……………………………………………………P175.3 自我总结……………………………………………P17六、参考资料……………………………………………….…..P18一、课程设计主要内容1.1 概况名称：公交换乘系统用途：交通运输公司、乘客功能：实现最优路线的显示1.2 主要内容公交换乘在一个城市的公共交通系统设计中占据着极其重要的地位，公交换乘的过程将直接影响居民出行时间的长短，公交换乘的过程如下：指定一起始公交站点与目的公交站点，依据参考因素，例如：换乘路线的路径最短、耗费时间最短、所需车资最少等，经过分析处理得到可达目的站点换乘次数最少的乘车方案，具体可分为：（1）零次换乘起始站点和目的站点之间存在可直达的公交线路，即出行居民无需转乘就可以直接到达目的站点，这也是较为理想的方案。
（2）一次换乘起始站点和目的站点之间没有公交车直接往返，即两站点之间不存在可直达的公交线路，则出行居民需要在途经的某个站点下车，然后转乘另一线路公交车才能达到目的站点。
数据结构程序设计课程设计题目公交换乘系统专业学号姓名指导老师完成日期2010年6月17日目录1.公车换乘流程图 (3)2.数据储存结构 (4)3. 程序 (4)4.分析..................................................................................... (16)5. 总结..................................................................................... . (18)一、公车换乘流程图二、数据存储结构Ⅰ线路信息：定义在结构体中①经过站点的所有公交路线，采用整型的1维的数组;数组长度为默认为50。
②字串符指向下一站和最后一站。
struct str //定义双重链表{char s[50];str *next;str *last;};Ⅱ站点信息：定义在结构体中①经过该站点的路线条数。
是一个整型变量。
②把该站作为所要求路线的第一站。
struct location//定义一个结构体来保存车站位置{int i;str *first;};三、程序location Find(str *pos,char *s)//查找车站位置{//初始化基本信息int i=0;location f;f.first=NULL;f.i=0;str *p=pos;//查找车站的位置while(p){if(::strcmp (s,p->s)==0){f.first =p;f.i=i;//车站的位置return f;}i++;p=p->next;}return f;}char car1[50],car2[50]; //保存相交车站的信息int public_car(str *i,str * p1)//查找两线线路是否有公共车站以及公共车站个数{int k=0;char *a;str *p=i;str *j=p1;//利用循环来判断两个公交车线路上是否有相同的车站while(p){a=p->s;j=p1;while(j){if(::strcmp (a,j->s)==0) //比较两个结点信息是否相同{if(k==0){::strcpy (car1,a);//用car1保存第一公共车站k++;break;}if(k==1){::strcpy (car2,a);//用car2保存第二公共车站k++;break;}}j=j->next ;}if(k==2) break;//因为最多只有两个相交车站,如果k=2了,跳出循环p=p->next ;}return k;}//初始化暂存信息的数据结点int s1,s2,k1,k2;location f, x1,x2,y1,y2;int count1,count2;//用于计算车站的个数char B[50],C[50];//用于保存用户输入的车站信息str *A,*p=NULL;str **Str=new str*[3];//定义三条链表保存公交车基本信息char station1[20][50],station2[20][50];//当有两个车站线路时用于保存每个车站线路的信息void setData()//初始化基本数据的涵数{count1=0;count2=0;s1=-1,s2=-1,k1=-1,k2=-1;x1.first=NULL;x2.first=NULL;y1.first=NULL;y2.first =NULL;}void printAllStationLine()//打印全部线路的函数{ //初始化保存车站的数组char a[][50]={"农垦医院站","潜水运动站","海滨宾馆站","海上城市站","市旅游总公司站","霞湖医院站","海运集团公司站"};char b[][50]={"东华站","湾桥站","农垦医院站","啤酒厂站","俱乐部站","广医附院站","国贸站", "广州湾站","建新东路站","霞湖医院站","霞山汽车运输总站"};char c[][50]={"海滨医院站","海滨宾馆站","儿童公园站","广州湾站","建设路站", "湛江汽车南站","人民大道中巴专线","世纪广场站"};//利用循环打印车站列表for(int i=0;i<3;i++){Str[i]=NULL;//初始化第i个链表if(i==0)//初始化第一条公交车线路链表{for(int k=0;k<7;k++){A=new str;A->next =NULL;A->last =NULL;strcpy(A->s,a[k]);//把数组的数据保存到链表的每一个结点if(!Str[i]){Str[i]=A;p=A;}else {p->next =A;A->last =p;p=A;}}}if(i==1)//初始化第二条公交车线路链表{for(int k=0;k<11;k++){A=new str;A->next =NULL;A->last =NULL;strcpy(A->s,b[k]);if(!Str[i]){S tr[i]=A;p=A;}else{p->next =A;A->last =p;p=A;}}}if(i==2)//初始化第三条公交车线路链表{for(int k=0;k<8;k++){A=new str;A->next =NULL;A->last =NULL;strcpy(A->s,c[k]);if(!Str[i]){Str[i]=A;p=A;}else{p->next =A;A->last =p;p=A;}}}}printf("\n ~~~~~~~~欢迎您的使用~~~~~~~~~ \n");printf("\n***************************湛江市公交车线路换乘系统*****************************\n");for(i=0;i<3;i++)//打印输出车站列表{printf("\n-----------------------------第%d条路线的车站列表-----------------------------\n",i+1);p=Str[i];while(p->next){printf("%s－>",p->s);p=p->next;}printf("%s\n",p->s);}printf("\n************************************************************ ********************\n");}void prinftTheBestWay(){//打印最优线路的信息printf("最优路线:\n");printf("\n-------------------从%s 到%s 路线列表-------------------\n",B,C);if(count1<count2)//比较线路1和线路2的车站个数{for(int j=0;j<count1;j++){printf("%s",station1[j]);if(j!=count1-1)printf("->");}}else{for(int j=0;j<count2;j++){printf("%s",station2[j]);if(j!=count2-1)printf("->");}}}void printfChooseStationLine()//打印客户选择的线路路线{while(1)//利用循环等待用户输入数据{setData();cout<<"\n请输入开始地和目的地(输入0 0 表示结束):";// scanf("%s%s",B,C);//用户输入两个车站数据cin>>B>>C;if(::strcmp (B,"0")==0&&::strcmp (C,"0")==0)break;//输入法0 0表示结束查询cout<<("\n****************************用户自选公交路线列表********************************\n");//printf("起点: %s\n终点: %s\n",B,C);cout<<"起点站:"<<B<<endl;cout<<"终点站:"<<C<<endl;for(int i=0;i<3;i++){p=Str[i];f=Find (p,B);//查找输入的第一个车站的位置if(f.first){if(s1==-1){x1=f;//保存第一个车站在线路的位置s1=i;//保存第一个车站在哪条线路上}else //因为有时车站可能是两条线路的公交点,因此可能会出现车站在两条线路上的情况{x2=f ;//保存车站在线路的位置s2=i;//保存车站在哪条线路上}}f=Find(p,C);//查找输入的第二个车站的位置,下面与上面功能类同if(f.first ){if(k1==-1){y1=f;k1=i;}else{k2=i;y2=f ;}}}if(s1==k1)//当s1=k1时候,表时两个车站在同一条公交线路上{cout<<"在"<<s1+1<<"条路线上,是零次换乘，经过的车站是:"<<endl;cout<<endl<<"------------------------从"<< B<<"到"<<C<<"路线列表---------------------"<<endl;if(x1.i<y1.i)//当输入的第一个车站的位置比第二个车站的位置小时,按顺序打印车站列表{p=x1.first;while(p!=y1.first){count1++;cout<<p->s<<"->";p=p->next ;}count1++;cout<<p->s<<endl;cout<<endl<<"经过的站点数目:"<<count1<<endl;cout<<endl<<"-------------------------------------"<<endl;}else //当输入的第一个车站的位置比第二个车站的位置大时,按逆序打印车站列表{p=y1.first ;while(p!=y1.first){count1++;cout<<p->s<<"->";p=p->last ;}cout<<p->s<<endl;cout<<endl<<"经过的站点数目:"<<count1<<endl;cout<<endl<<"-------------------------------------"<<endl;}}else//当s1!=k1时候,表时两个车站在两条公交线路上{i=::public_car (Str[s1],Str[k1]);//两个公交线路车站的个数if(i==0) //表示公交线路线没有公交点,不过本例不存在这种情况{cout<<B<<"->"<<C<<"不存在的通路"<<endl;continue;}else if(i==1)//如果两条公交线路的有一个公交车站{cout<<"在"<<s1+1<<","<<k1+1<<"条路线上，经一次换乘，经过的车站是:"<<endl;cout<<endl<<"--------------------从"<<B<<" 到"<<C<<" 路线列表----------------------"<<endl;f=Find(Str[s1],car1);//在第一条公交线路上找公交站点位置if(x1.i<f.i)//当输入的第一个车站的位置比公交车站的位置小时,按顺序打印车站列表{p=x1.first;while(::strcmp (car1,p->s))//当还没有打印到公交车站时,继续打印{count1++;cout<<p->s<<"->";p=p->next ;}cout<<p->s<<"->";}else//当输入的第一个车站的位置比公交车站的位置大时,按逆序打印车站列表{p=x1.first;while(::strcmp (car1,p->s)){count1++;cout<<p->s<<"->";p=p->last ;}cout<<p->s<<"->";}f=Find(Str[k1],car1);//在第二条公交线路上找公交站点位置,下面功能与上面类同if(y1.i>f.i){p=f.first;p=p->next;while(p!=y1.first)//当还没有打印到公交车站时,继续打印,与上面while语句一样功能的,只不过不同表述{count1++;cout<<p->s<<"->";p=p->next ;}cout<<p->s<<endl;}else{p=f.first;p=p->last ;while(p!=y1.first){count1++;cout<<p->s<<"->";p=p->last ;}cout<<p->s<<endl;}cout<<endl<<"经过的车站数目是:"<<count1<<endl;cout<<"\n-------------------------------------\n";}else if(i==2)//如果两条公交线路的有两个公交车站时,下面的功能与上面的类同{cout<<"有两种方案:\n";cout<<"第一种方方案:\n在"<<s1+1<<","<<k1+1<<"路线上，经一次换乘，经过的车站是:\n";cout<<"\n--------------------从"<<B<<"到"<<C<<"路线列表----------------------\n";f=Find(Str[s1],car1);if(x1.i<f.i){p=x1.first;while(::strcmp (car1,p->s)){strcpy(station1[count1],p->s);count1++;cout<<p->s<<"->";p=p->next ;}strcpy(station1[count1],p->s);count1++;cout<<p->s<<"->";}else{p=x1.first ;while(::strcmp (car1,p->s)){strcpy(station1[count1],p->s);count1++;cout<<p->s<<"->";p=p->last ;}strcpy(station1[count1],p->s);count1++;cout<<p->s<<"->";}f=Find(Str[k1],car1);if(y1.i>f.i){p=f.first;p=p->next;while(p!=y1.first){strcpy(station1[count1],p->s);count1++;cout<<p->s<<"->";p=p->next ;}strcpy(station1[count1],p->s);count1++;cout<<p->s<<endl;cout<<"\n经过车站的数目:"<<count1<<endl;cout<<"\n-------------------------------------\n"; }else{p=y1.first;p=p->next;while(p!=y1.first){strcpy(station1[count1],p->s);count1++;cout<<p->s<<"->";p=p->last;}strcpy(station1[count1],p->s);count1++;cout<<p->s<<endl;cout<<"\n经过车站的数目:"<<count1<<endl;cout<<"\n-------------------------------------\n"; }cout<<"\n第二种方方案:\n在"<<s1+1<<","<<k1+1<<"条路线上，是一次换乘，经过的车站是:\n";cout<<"\n-------------------从"<<B<<"到"<<C<<"路线列表-------------------\n";f=Find(Str[s1],car2);if(x1.i<f.i){p=x1.first;while(::strcmp (car2,p->s)){strcpy(station2[count2],p->s);count2++;cout<<p->s<<"->";p=p->next ;}strcpy(station2[count2],p->s);count2++;cout<<p->s<<"->";}else{p=x1.first ;while(::strcmp (car2,p->s)){strcpy(station2[count2],p->s);count2++;cout<<p->s<<"->";p=p->last ;}strcpy(station2[count2],p->s);count2++;cout<<p->s<<"->";}f=Find(Str[k1],car2);if(y1.i>f.i){p=f.first;p=p->next;while(p!=y1.first){strcpy(station2[count2],p->s);count2++;cout<<p->s<<"->";p=p->next ;}strcpy(station2[count2],p->s);count2++;cout<<p->s<<endl;}else{p=y1.first;p=p->next;while(p!=y1.first){strcpy(station2[count2],p->s);count2++;cout<<p->s<<"->";p=p->last ;}strcpy(station2[count2],p->s);count2++;cout<<p->s<<endl;}cout<<"\n经过的车站的数目:"<<count2<<endl;cout<<"\n-------------------------------------\n";}prinftTheBestWay();cout<<("\n******************************************************** ************************\n");}}};int main(int argc, char* argv[]){printAllStationLine();printfChooseStationLine();return 0;}四、分析（1）首先初始化公交车线路链表，以下为初始化第一条公交车线路链表，第二、第三也基本一致。
