没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
3(116 行).
题目:公交车。
数据结构:图,最小路径和最小换乘分别通过两种不同的方法构造图。
算法思想:最小路径就是构造最基本的路线图,每一条线路就是一条线,最小换乘则把每
条路线构建成一张网,这样样子最小换乘也可以转换成最短路径来实现了。然后使用迪杰
斯特拉算法便可求解和记录下路径。
测试用例:
本代码无需输入,因为数据存储在了文件中
源代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
#dene Status int
#dene VRType oat
#dene InfoType char
#dene VertexType char
#dene TRUE 1
#dene FALSE 0
#dene OK 1
#dene ERROR 0
#dene INFEASIBLE -1
#dene OVERFLOW -2
#dene INFINITY 3000
#dene MAX_VERTEX_NUM 600
#dene QElemType int
struct line
{
int len; //
这辆车有多少个站点
char name[40]; //
车的名称
int b[50]; //
代表站点在站点总数组里是第几个
};
struct node
{
char name[40]; //
站点名称
int b[300]; //
代表车名在车总数组里是第几个
int len; //
有多少辆车
};
line bus[300]; //
所有的车
node d[MAX_VERTEX_NUM]; //
所有的站点
char s[40]; //
暂存从文件里读取的东西
int dian_n,bus_n,way_n; //
所有的站点数和车数
int way[600]; //
用来存储最终路径上的点
int nd_dian(char*s) //
寻找车
{
for(int i=1;i<=dian_n;i++)
if(strcmp(s,d[i].name)==0)
return i;
return -1;
}
int nd_bus(char*s) //
寻找站点
{
for(int i=1;i<=bus_n;i++)
if(strcmp(s,bus[i].name)==0)
return i;
return -1;
}
void read() //
将 文 件
中的信息读取
{
fstream dataFile;
dataFile.open("7.txt",ios::in);
if(!dataFile)
{
cout<<"
文件打开失败
"<<endl;
exit(0);
}
bus_n=dian_n=0;
while(!dataFile.eof()) //
文件没读完时持续读取
{
dataFile>>s;//
读取一个字符串
if(dataFile.fail())
break;
if((s[0]>='0'&&s[0]<='9')||(s[1]>='0'&&s[1]<='9')) //
判断录进来的是车名
//
因为车号的范围很大 如果文件大 可能回到几百 不容易判断 既然是用字符串的形式读取的 可
以判断
s[0]
,如果是数字就是车号,如果不是数字就是站点
{
bus_n++;//
车数加一
strcpy(bus[bus_n].name,s);//
存入车号的结构体
bus[bus_n].len=0;
}
else //
录 进 来 的 站
点名
{
int k=nd_dian(s); //
判断是否为已存入的站点
if(k==-1) //
新增站点
{
k=++dian_n;
strcpy(d[k].name,s);
d[k].len=0;
}
bus[bus_n].b[++bus[bus_n].len]=k;//
记录站点
d[k].b[++d[k].len]=bus_n;//
记录站点对应的车次
}
}
dataFile.close();
}
typedef struct ArcCell
{
VRType adj;
int len;
InfoType info[50][100];//char
}ArcCell;
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM][80];
ArcCell **arcs;
int vexnum,arcnum;
}MGraph;
Status CreateUDN1(MGraph &G) //
最小路径图
{
int i,j,k,n;
char v1[80],v2[80];
oat w;
G.vexnum=dian_n;//
站点转化为图的点
G.arcnum=0;//
初始化
G.arcs=new ArcCell*[G.vexnum]; //
二维数组的空间申
请
for(i=0;i<G.vexnum;i++)
{
G.arcs[i]=new ArcCell[G.vexnum];
}
for(i=0;i<G.vexnum;i++)
剩余15页未读,继续阅读
资源评论
weixin_45092867
- 粉丝: 1
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功