#include<iostream>
#include<stack>
#include<string>
#include<vector>
using namespace std;
//*******************************************************************************
//编写一个寻找从纽约到洛杉矶的航线的程序需要的一个包含了航班信息的数据库
//数据库中的每一个记录项都必须包含出发的城市和目标城市、两个城市之间的距离,
//以及帮助沿原路返回的标记
struct FlightInfo
{
string from;
string to;
int distance;
bool skip;
FlightInfo()
{
from=" ";
to=" ";
distance=0;
skip=false;
}
FlightInfo(string f,string t,int d)
{
from=f;
to=t;
distance=d;
skip=false;
}
};
//***********************************************************************************
class Search
{
vector<FlightInfo> flights;
stack<FlightInfo> btStack;
bool match(string from, string to,int &dist);
bool find(string from,FlightInfo &f);
public:
void addflight(string from,string to,int dist)
{
flights.push_back(FlightInfo(from,to,dist));
}
void route();
void findroute(string from, string to);
bool routefound()
{
return !btStack.empty();
}
};
//*******************************************************************************************
//**********************************************************
//显示航线
void Search::route()
{
stack<FlightInfo> rev;
int dist=0;
FlightInfo f;
while(!btStack.empty())
{
f=btStack.top();
rev.push(f);
btStack.pop();
}
while(!rev.empty())
{
f=rev.top();
rev.pop();
cout<<f.from<<" to ";
dist+=f.distance;
}
cout<<f.to<<endl;
cout<<"Distance is "<<dist<<endl;
}
//***********************************************************
//判断两个城市之间是否有直接的连接
bool Search::match(string from,string to,int &dist)
{
for(unsigned i=0;i<flights.size();i++)
{
if(flights[i].from==from&&flights[i].to==to&&!flights[i].skip)
{
flights[i].skip=true;
dist=flights[i].distance;
return true;
}
}
return false;
}
//***********************************************************
//尝试寻找指定城市到任何其他城市的连接
const int MAXDIST=100000;
bool Search::find(string from,FlightInfo &f)
{
int pos=-1;
int dist=MAXDIST;
for(unsigned i=0;i<flights.size();i++)
{
if(flights[i].from==from&&!flights[i].skip)
{
if(flights[i].distance<dist)
{
pos=i;
dist=flights[i].distance;
}
}
}
if(pos!=-1)
{
f=flights[pos];
flights[pos].skip=true;
return true;
}
return false;
}
//************************************************************
//尝试在出发城市和目标城市之间找到一条航线
void Search::findroute(string from,string to)
{
int dist;
FlightInfo f;
if(match(from,to,dist))
{
btStack.push(FlightInfo(from,to,dist));
return;
}
if(find(from,f))
{
btStack.push(FlightInfo(from,to,f.distance));
findroute(f.to,to);
}
else if(!btStack.empty())
{
f=btStack.top();
btStack.pop();
findroute(f.from,f.to);
}
}
//************************************************************
//********************************************************************************************
int main()
{
char to[40],from[40];
Search ob;
ob.addflight("New York","Chicago",900);
ob.addflight("Chicago","Denver",1000);
ob.addflight("New York","Toronto",500);
ob.addflight("New York","Denver",1800);
ob.addflight("Toronto","Calgary",1700);
ob.addflight("Toronto","Los Angeles",2500);
ob.addflight("Denver","Urbana",500);
ob.addflight("Toronto","Chicago",1000);
ob.addflight("Denver","Houston",1000);
ob.addflight("Houston","Los Angeles",1500);
ob.addflight("Denver","Los Angeles",1000);
cout<<"From: ";
cin.getline(from,40);
cout<<"To: ";
cin.getline(to,40);
ob.findroute(from,to);
if(ob.routefound())
ob.route();
return 0;
}
没有合适的资源?快使用搜索试试~ 我知道了~
C++经典算法-最低成本搜索
共20个文件
pdb:3个
manifest:2个
obj:1个
3星 · 超过75%的资源 需积分: 32 5 下载量 83 浏览量
2009-01-07
16:41:22
上传
评论
收藏 1.03MB RAR 举报
温馨提示
C++经典数据结构算法,支持VC6.0版本运行
资源推荐
资源详情
资源评论
收起资源包目录
.rar (20个子文件)
最低成本搜索
最低成本搜索.plg 1KB
最低成本搜索.vcproj 5KB
最低成本搜索.dsw 549B
Least_cost.cpp 4KB
最低成本搜索.suo 8KB
Debug
最低成本搜索.exe.intermediate.manifest 145B
vc60.pdb 132KB
vc80.pdb 172KB
最低成本搜索.exe.embed.manifest.res 212B
Least_cost.obj 543KB
最低成本搜索.exe 632KB
BuildLog.htm 8KB
最低成本搜索.pdb 2.6MB
mt.dep 67B
最低成本搜索.exe.embed.manifest 146B
最低成本搜索.ncb 1.07MB
最低成本搜索.dsp 4KB
最低成本搜索.sln 900B
最低成本搜索.vcproj.PC-200806281721.Administrator.user 1KB
最低成本搜索.opt 48KB
共 20 条
- 1
资源评论
- juhui_sd2012-12-13谢谢LZ分享,自动搜索是常用的算法
AliX9527
- 粉丝: 6
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- python pear python pearpython pear
- 一个简单的Swift脚本示例,该脚本会请求用户输入两个数字,并计算它们的和与乘积,然后将结果输出到控制台
- 一个简单的Python脚本示例 这个脚本会要求用户输入两个数字,然后计算并输出这两个数字的和与乘积
- 没有word只有图片,打印图片打印出来发黑怎么办?如何像打印doc一样清楚 教你一招搞定
- 一个稍微复杂的Java程序示例 这个程序会计算并输出用户输入的两个整数的和与乘积
- 造成连接已重置ERR-CONNECTION-RESET的原因是
- 一个简单的x86架构下的汇编语言脚本示例,在控制台上输出"Hello, World!"
- Yearly word of AI 合作阅读材料.docx
- jmeter接口测试-http接口请求
- 数据可视化脚本案例:使用Python和Matplotlib库创建柱状图
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功