【数据结构】公交线路上的优化路径查询(C++)

您所在的位置：网站首页 › 城市公交时间查询 › 【数据结构】公交线路上的优化路径查询(C++)

【数据结构】公交线路上的优化路径查询(C++)

2024-07-15 17:38| 来源: 网络整理| 查看: 265

（本科的课程设计，终于从草稿箱翻出来了

题目要求：

当时的实验报告

代码

题目要求：根据公交线路的输入格式，定义并建立合适的图模型。针对输入的公交线路，能查询任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x元。针对输入的公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的不考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x时间。针对输入的公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等待下一辆线路的最省时间的路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x元。

当时的实验报告

1. 需求描述

1.1 问题描述

最短路径问题是图论中的一个经典问题，其中的Dijkstra算法一直被认为是图论中的好算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。

对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为：

线路编号：起始站点(该站坐标）；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；……；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一趟。车速。

例如：63：A(32,,45)；B(76,45)；C(76,90)；……；N(100,100)。1元。5分钟。1/每分钟。

假定该线路的乘坐价格与乘坐站数无关，假定不考虑公交线路上的交通堵塞。对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径等等。

1.2 基本要求

1）根据上述公交线路的输入格式，定义并建立合适的图模型

2）针对上述公交线路，能查询任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x元。

3）针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的不考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x时间。

4）针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等待下一辆线路的最省时间的路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x元。

5）实现提示：需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。

1.3 输入要求

输入形式：

输入数据例子：

111：A(1,1）；B(3,4)；C(5,2)；D(4,6)。4元。1分钟。4/分钟。

……

1.4 输出要求

输出形式：

线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x元。

线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；换乘线路x：站名MK，…，站名T。共花费x时间。

输出数据例子：

线路222：站点A,站点E。换乘线路333：站点E,站点D。共花费2元。

2. 设计

2.1 结构设计

公交车站点struct busNode：包含每个站点的名称sta_name、横坐标dx、纵坐标dy、指向下一个站点指针*next；公交车类class busNode：存储了公交车经过的站点链表结构；公交车线路类busRoute：存储公交车经过的站点、票价、速度、发车时间间隔；两站点之间的线路信息struct routeInfo：包括线路编号和数据（票价或者所用时间）；两站点之间的线路信息，可有多条线路struct ver：成员对象为routeInfo类型的数组；邻接矩阵类adjMatrix：存储整合后的公交线路信息，同时实现求最短路径的Dijkstra算法以及输出最短路径方法。

2.2 数据及数据类(型)定义

1. 公交车节点busNode

struct busNode { string sta_name;//站点名称 double dx;//站点横坐标 double dy;//站点纵坐标 busNode *next;//指向下一个站点的指针 };

2. 公交车经过的站点链表类busChain

class busChain { friend class busRoute;//友元 public: busChain() {//构造函数 firstNode = NULL; listSize = 0; } ~busChain();//析构函数 bool isEmpty() { return listSize == 0; }//判断是否为空 int size() { return listSize; }//站点数目 busNode *getFirst() { return firstNode; }//得到首节点 string getFirstStation() { return firstNode->sta_name; }//得到始发站名称 void insert(const string &s, const double &x, const double &y);//在链表最后插入一个节点 void get_distance();//计算每两个站点之间的距离，存入dx void output(ostream &out) const;//输出 private: busNode * firstNode;//指向首节点的指针 int listSize;//节点个数 };

3. 公交车线路类busRoute

class busRoute { public: busRoute();//构造函数 ~busRoute();//析构函数 void initi1(int nn, int ss);//设置线路编号、站点总数 void initi2(double sp, double pp, double tt);//设置票价、发车间隔、速度 double getPrice() { return price; }//得到线路票价 double getSpeed() { return speed; }//得到速度 int getNum() { return num; }//得到线路编号 int getSum() { return sum; }//得到站点总数 double getTime_() { return time_; }//得到发车时间间隔 busChain& getLink() { return link; }//得到经过站点链表 void output(ostream &out) const;//输出本线路停经站点及其坐标 private: int num;//线路编号 int sum;//站点总数 double speed;//速度 double price;//票价 double time_;//发车时间间隔 busChain link;//本公交线路链表 };

4. 两站点之间的线路信息struct routeInfo

struct routeInfo { int Info;//线路编号 double data;//数据 };

5. 两站点之间的线路信息，可有多条线路struct ver

struct ver { routeInfo ro[sn];//每条线路信息 };

6. 邻接矩阵类class adjMatrix

class adjMatrix { public: adjMatrix(int theCapacity);//构造函数 ~adjMatrix();//析构函数 void insert(int i, int j, int nth, routeInfo rt);//插入元素 void erase(int i, int j, int nth);//删除元素 double getElement(int i, int j, int nth);//查找 int getM() const {//得到总边数 return m; } void ini();//初始化为无边 int search(int i, int j, int su);//查找站点i到站点j的所有线路中的最优解 int search2(int i, int j, int su, busRoute *bus);//查找站点i到站点j的所有线路中的最优解（判断是否加入等待时间） void Dijkstra(double *dis, int *pre, int da, int su);//求da到其他点的最短路径 void outputPath(int pa, int pb, string *in, int *pre, int su);//输出pa到pb的最短线路 void Dijkstra2(double *dis, int *pre, int da, int su, busRoute *bus); //求da到其他点的最短路径，加入中间站点的等待时间 double find_(int Infomation, int su, busRoute *bus);//查找线路编号对应的等待时间 private: ver * *theMatrix;//邻接矩阵 int n;//点数 int m;//边数 };

7. 全局变量

#define sn 30//站点总数 #define noEdge 9999 int option; //进行功能选择 char flag = 'y';//通过输入判断是否退出 busRoute *bus = new busRoute[10];//公交车线路数组，预设为10，可修改 int BUS_SUM;//公交线路数 string in[sn] = {","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"," "," "," " }; //已有对应关系，将站点名和站点标号对应 double dis[sn];//到源点的距离 int vis[sn];//Dijkstra算法中判断点是否访问过 int pre[sn];//前驱，Dijkstra算法中用来记录前驱 adjMatrix matrix(30);//邻接矩阵

2.3 算法设计及分析-伪代码

2.3.1 公交车经过的站点链表类busChain

1. 构造函数：

busChain::busChain() {//构造函数 firstNode指向空; listSize置为0; }

2. 析构函数：

busChain::~busChain() { busNode *p = firstNode, *pp; while (p不为空) { pp = p->next; 删除p节点; p = pp; } }

3. 在链表的最后插入一个节点：

void insert(站点名称, 横坐标, 纵坐标) { if(firstNode为空) {//当前链表为空 firstNode = new busNode; firstNode->sta_name = 站点名称; firstNode->dx = 横坐标; firstNode->dy = 纵坐标; firstNode->next = 空; } else { busNode *p = firstNode; if(p->next不为空) p=p->next; busNode *pp = new busNode; pp->sta_name = 站点名称; pp->dx = 横坐标; pp->dy = 纵坐标; pp->next = 空; p-next = pp; } listSize+1; }

4. 计算相邻两个站点之间的距离并将其值存入dx：

void busChain::get_distance() { busNode *p = firstNode, *pp; for (pp = p->next; pp不为空; pp = pp->next) { p->dx = 距离; p = pp; } p->dx = noEdge;//最后一个节点指针指向空 }

5. 输出本线路信息：

void busChain::output(ostream &out) const { busNode *p; for (p = firstNode; p->next不为空; p = p->next) { 输出站点p的名称(横坐标,纵坐标); } 输出最后一个站点的名称(横坐标,纵坐标)。 }

6. 重载

【本文地址】

公司简介

联系我们