这里写自定义目录标题
- 一、系统实现功能：
- 二、详细设计
-
- 1 查询景点信息功能
- 2 查询两景点间最短距离功能
- 3 查询多个景点间最短距离功能
- 4 查询两景点通行采用不同出行方式产生的最短时间
- 三、完整源码
hello大家好 俺是小冉~
这是去年c++课程的一个大作业，今天清理文件的时候翻出来了源码哈哈哈哈。
考虑到可能对大家有帮助就把源码分享了出来 。
在写这个系统的时候还没有学习数据结构，所以变量名、函数名等命名都不是非常的规范，如有错误也请大佬批评指正。
写的时候也有参考网上的一些代码，主要用到的知识点有求最短路径的迪杰斯特拉算法以及一些c++中的虚函数的概念。
话不多说马上开始吧~~
一、系统实现功能：
1、查询校园内各景点信息。
2、查询两景点间的最短距离。
3、查询多个景点间的最短距离。
4、查询两景点通行采用不同出行方式时产生的最短时间。
二、详细设计
1 查询景点信息功能
先设计顶点类，类中储存校园内景点的备注、名字、代号、学生评价等信息
class Point//顶点类
{
friend class Graph;
private:
char code;
string name;
string intro;
string comments;
};
然后在 Graph 类中，建立一个 Point *类型的数据成员 PointList，用 new 操作符给它赋予
动态的存储空间，用来存放景点的信息，然后在输出景点信息的函数 Show 中，输出顶点 i
的信息。
2 查询两景点间最短距离功能
该功能主要利用迪杰斯特拉算法，利用数组 path 储存路径的前一个结点，然后利用 dist
储存最短路径长度，使用函数 MinPath 来计算结点 v 到其它结点的最短路径和最短距离。
void Graph::MinPath(int v)
{
int n=NumberOfPoints();
dist=new int[n];
path=new int[n];
bool * S=new bool[n]; //顶点集合,如果 s[i]等于 true 说明 i 点已经被加入最短路径集合中
int i,j,k,w,min;
for(i=0;i<n;i++)
{
dist[i]=getLength(v,i); //数组初始化
S[i]=false;
if(i!=v&&dist[i]<maxValue)
path[i]=v;//说明 i 到 v 有边相连 ，设置 path[i]=v
else
path[i]=-1;//说明 i 到 v 无边相连
}
S[v]=true; //顶点 v 加入顶点集合
dist[v]=0;//自己到自己的最短路径为 0
for(i=0;i<n-1;i++)
{
min=maxValue;
int u=v; //选不在 S 中具有最短路径的顶点 u
for(j=0;j<n;j++)
if(S[j]==false&&dist[j]<min){
u=j;
min=dist[j];
S[u]=true; //顶点 u 加入集合 S
for(k=0;k<n;k++)
{
w=getLength(u,k);
if(S[k]==false&&w<maxValue&&dist[u]+w<dist[k]) //顶点 k 未加入 S，且绕过 u 可以缩短路
径
{
dist[k]=dist[u]+w;
path[k]=u; //k 到 u 有边相连 //修改到 k 的最短路径
}}
}
};
在输出最短路径时，用倒序的方式，输出 path 数组中的前一个结点，完成对最短路径的输
出。
3 查询多个景点间最短距离功能
查询多个景点间的最短距离，也就是先用数组 c 储存要参观结点信息，然后找出两两之间
到达的最短路径，相加之后得到的就是要求的最短路径，在实际操作时，要先调用函数
MinPath（int v)然后再调用函数 FindMinPath(int v,int x)。
for(j=0,sum=0;j<i-1;j++)
{
MinPath(a[j]);
x=FindMinPath(a[j],a[j+1]);
sum+=x;
}
cout<<endl<<"最短路径长度为："<<sum<<endl
4 查询两景点通行采用不同出行方式产生的最短时间
完成该功能，设计了一个 Time 类和它的三个子类 bike、car 和 walk，三个类中包含虚函数
showTime（int x），在选择不同的交通方式时，showTime 函数会输出使用该交通方式时产
生的时间。
class Time
{
public:
Time(){};//构造函数
~Time(){};//析构函数
virtual void showTime(int x){
cout<<"您出行的时间为"<<endl ;
};
void show();
//输出所需时间
} ;
class bike:public Time{
public:
void showTime(int x){
cout<<"预计骑车所需的时间为："<<x/speed2<<"秒"<<endl;
}
};
class car:public Time{
public:
void showTime(int x){
cout<<"预计开车所需的时间为："<<x/speed3<<"秒"<<endl;
}
};
class walk:public Time{
public:
virtual void showTime(int x){
cout<<"预计步行所需的时间为：";
cout<<x/speed1<<"秒"<<endl;
}
};
三、完整源码
#include <iostream>
#include <string>
#include <iomanip>//输入输出
#include<windows.h>
using namespace std;
const int maxValue=9999;//最大值
const int maxPoint = 100; // 最大顶点数
const int DefaultPoints = 20; // 默认顶点数
const int num=20;
int number=0;
int speed1=1;
int speed2=3;
int speed3=16;
int min;
class Graph;
class Time
{
public:
Time(){};//构造函数
~Time(){};//析构函数
virtual void showTime(int x){
cout<<"您出行的时间为"<<endl ;
};
void show();
//输出所需时间
} ;
class bike:public Time{
public:
void showTime(int x){
cout<<"预计骑车所需的时间为："<<x/speed2<<"秒"<<endl;
}
};
class car:public Time{
public:
void showTime(int x){
cout<<"预计开车所需的时间为："<<x/speed3<<"秒"<<endl;
}
};
class walk:public Time{
public:
virtual void showTime(int x){
cout<<"预计步行所需的时间为：";
cout<<x/speed1<<"秒"<<endl;
}
};
class Point//顶点类
{
friend class Graph;
private:
char code;
string name;
string intro;
string comments;
};
class Graph:private Point //定义顶点类的子类 图类
{
public:
Graph (); // 构造函数
~Graph(); // 析构函数
int NumberOfPoints(); // 返回当前顶点数
int NumberOfEdges(); // 返回当前边数
Point getValue (int i); // 取顶点 i 的值,以类名为函数返回值
int getLength (int v1, int v2); // 取边上长度
int getPointPos (char code); // 给出顶点代码code在图中位置
bool insertPoint (char code,string name,string intro);// 插入一个顶点Point
bool insertEdge (int v1, int v2, int length); // 插入边(v1, v2), 长为length
void Show(int i);// 输出顶点i的信息
void MinPath(int v); // Dijkstra求最短路径算法
void ShowMin(int v,int x); // 输出两顶点间的最短路径和距离
int FindMinPath(int v,int x); // 查找多个顶点间的最佳路径
void ShowMany(); // 输出多个顶点间的最佳路径
int Increase(); // 增加景点和道路
int **Edg(){return Edges;} // 返回邻接矩阵
virtual void search(); // 景点信息查询
virtual void minest(); // 查询两景点间最短距离
void allpath(); // 查询任意两景点间的所有路径
void Map(); // 生成景点列表
void insertcomments();//加入备注
void insertcomment(int i,string comment);
void showTime();
private:
int maxPoint;// 图中最大顶点数
int numEdges; // 当前边数
int numPoints; // 当前顶点数
Point * PointsList; // 顶点数组首地址
int **Edges;// 邻接矩阵保存边长
int *path; // 保存该结点的前一个结点
int *dist; // 保存路径长度
int pathNum; // 两点间所有路径的数目
};
// 构造函数
Graph::Graph()
{
maxPoint = DefaultPoints;// 初始化 最大顶点数
numPoints = 0; // 初始化 顶点个数
numEdges = 0; // 初始化 边数
PointsList = new Point[maxPoint];// new一个动态的Point类类型的数组
Edges = new int*[maxPoint]; //new一个指针数组
for (int i = 0; i<maxPoint; i++)
Edges[i] = new int[maxPoint];
for (int i = 0; i<maxPoint; i++)
for (int j = 0; j<maxPoint; j++)
Edges[i][j] = (i==j)?0:maxValue;//初始化边的长度
insertPoint('a',"新西门","该门为正门，进出需要刷门禁");
insertPoint('b',"教五","普普通通用来上课的教学楼");
insertPoint('c',"图书馆","藏书众多，供学生阅览。由梁思成先生设计，历史悠久");
insertPoint('d',"牡丹园","开花的时候非常的漂亮，院内牡丹娇艳绽放，景色宜人。");
insertPoint('e',"畅志园","平常人很少，可以来这里看书、学习");
insertPoint('f',"曲江流饮","有一个小池子和小亭子，傍晚可以过来这里看书");
insertPoint('g',"喷泉广场","有喷泉，旁边是学子食府和墨香斋，周六有时候会有各个社团的外场活动，很热闹");
insertPoint('h',"校医院","校医院，位置很偏，差评");
insertPoint('i',"田径场","顾名思义，晚上会有广场舞，偶尔有人会举办小型演唱会");
insertEdge(0,1,190);
insertEdge(0,4,169);
insertEdge(0,2,300);
insertEdge(1,2,194);
insertEdge(5,3,562);
insertEdge(4,2,162);
insertEdge(4,3,140);
insertEdge(3,2,197);
insertEdge(5,2,414);
insertEdge(5,6,175);
insertEdge(5,8,257);
insertEdge(2,8,183);
insertEdge(5,7,342);
insertEdge(6,8,167);//插入边
};
//析构函数
Graph::~Graph()
{
delete[] PointsList;
delete[] Edges;
delete[] path;
delete[] dist;
};
//返回当前顶点数
int Graph::NumberOfPoints()
{
return numPoints;
};
//返回当前边数
int Graph::NumberOfEdges()
{
return numEdges;
};
// 取顶点 i 的值
Point Graph::getValue(int i)
{
return PointsList[i];
};
// 取边上权值
int Graph::getLength(int v1, int v2)
{
return Edges[v1][v2];
};
// 给出顶点代码code在图中位置
int Graph::getPointPos (char code)
{
for(int i=0;i<numPoints;i++)
if(PointsList[i].code==code)
{return i;}
return -1;
};
// 插入一个顶点Point
bool Graph::insertPoint(char code,string name,string intro)
{
if(numPoints==maxPoint)
{
printf("景点数已经达到最大值！");
return false;
}
PointsList[numPoints].code=code;
PointsList[numPoints].name=name;
PointsList[numPoints].intro=intro;
numPoints++;
return true;
};
void Graph::insertcomment(int i,string comment){
PointsList[i].comments+=comment+"\n";
}
// 插入边(v1, v2), 权为length
bool Graph::insertEdge(int v1, int v2, int length)
{
if(v1>-1 && v1<numPoints && v2>-1 && v2<numPoints)
{
Edges[v1][v2]=Edges[v2][v1]=length;
numEdges++;
return true;
}
else
return false;
};
// 输出顶点i的信息
void Graph::Show(int i)
{
int t=number;
int j;
cout << " 景点代号：" << PointsList[i].code << endl;
cout << " 景点名称：" << PointsList[i].name << endl;
cout << " 景点简介：" << PointsList[i].intro << endl;
cout << " 学生评价：" <<PointsList[i].comments<<endl;
cout << "***************************************" << endl;
};
//查询两景点之间的最短路径和距离
void Graph::MinPath(int v)
{
int n=NumberOfPoints();
dist=new int[n];
path=new int[n];
bool * S=new bool[n]; //顶点集合,如果s[i]等于true 说明i点已经被加入最短路径集合中
int i,j,k,w,min;
for(i=0;i<n;i++)
{
dist[i]=getLength(v,i); //数组初始化
S[i]=false;
if(i!=v&&dist[i]<maxValue)
path[i]=v;//说明i到v有边相连 ，设置path[i]=v
else
path[i]=-1;//说明i到v无边相连
}
S[v]=true; //顶点v加入顶点集合
dist[v]=0;//自己到自己的最短路径为0
for(i=0;i<n-1;i++)
{
min=maxValue;
int u=v; //选不在S中具有最短路径的顶点u
for(j=0;j<n;j++)
if(S[j]==false&&dist[j]<min)
{
u=j;
min=dist[j];
}
S[u]=true; //顶点u加入集合S
for(k=0;k<n;k++)
{
w=getLength(u,k);
if(S[k]==false&&w<maxValue&&dist[u]+w<dist[k]) //顶点k未加入S，且绕过u可以缩短路径
{
dist[k]=dist[u]+w;
path[k]=u; //k到u有边相连 //修改到k的最短路径
}
}
}
};
//输出两景点之间的最短路径和距离
void Graph::ShowMin(int v,int x)
{
int j,k,n;
n=NumberOfPoints();
int *d=new int[n];
{
j=x;
k=0;
while(j!=v)
{
d[k++]=j;
j=path[j];//path是指与j相连的上一个结点
}
cout<<getValue(v).name<<"到"<<getValue(x).name<<"的最短路径为："<<endl<<getValue(v).name;
while(k>0)
{
cout<<"-->"<<getValue(d[--k]).name;
}
cout<<endl<<"最短路径长度为："<<dist[x]<<endl;
}
delete[] d;
};
//查找多个顶点间的最佳路径
int Graph::FindMinPath(int v,int x)
{
int j,k,n;
n=NumberOfPoints();
int *d=new int[n];
{
j=x;
k=0;
while(j!=v)
{
d[k++]=j;
j=path[j];
}
while(k>0)
{
cout<<"-->"<<getValue(d[--k]).name;
}
}
delete[] d;
return dist[x];//返回v到x的最短路径
};
//输出多个顶点间的最佳路径
void Graph::ShowMany()
{
system("cls");
Map();
int i,j,sum,x,a[num];
char c[num];
for(i=0;;i++)//输入依次要参观的景点
{
cout <<"请输入你要参观的第"<<i+1<<"个景点(输入#结束): ";
cin >>c[i];
if(c[i]=='#')
break;
while(1)
{
a[i]=getPointPos(c[i]);
if(a[i]==-1)
{
cout <<"输入错误，请重新输入"<<endl;
cout <<"请输入你要参观的第"<<i+1<<"个景点(输入#结束): ";
getchar();
cin >>c[i];
}
else
{
break;
}
}
}
cout <<getValue(a[0]).name;
for(j=0,sum=0;j<i-1;j++)
{
MinPath(a[j]);
x=FindMinPath(a[j],a[j+1]);
sum+=x;
}
cout<<endl<<"最短路径长度为："<<sum<<endl;
cout <<"按回车键继续";
getchar();
getchar();
};
//增加景点和道路
int Graph::Increase()
{
system("cls");
printf("请输入管理员密码：");
int key;
cin>>key;
if(key==123456){
int f;
system("cls");
Map();
char code;
string name;
string intro;
cout <<"请输入要增加的景点的代码：";
cin >>code;
while(1)
{
f=0;
for(int i=0;i<numPoints;i++)
{
if(code==getValue(i).code)
{
cout <<"已有该代码请重新输入"<<endl;
f=1;
break;
}
}
if(f==1)
{
cout <<"请输入要增加的景点的代码：";
cin >>code;
}
else
{
break;
}
}
cout <<"请输入要增加的景点的名称：";
cin.ignore();
getline(cin,name);
cout <<"请输入要增加的景点的简介：";
getline(cin,intro);
insertPoint(code,name,intro);
int v1,v2,length;
char code1,code2;
cout <<"起始景点：";
cin >>code1;
cout <<"终止景点：";
cin>>code2;
while(1)
{
v1=getPointPos(code1);
v2=getPointPos(code2);
if(v1==-1||v2==-1)
{
cout <<"输入错误，请重新输入"<<endl;
cout << "编号如上图，请输入您要查询的两个景点的编号："<<endl;
cout <<"起始景点：";
cin >>code1;
cout <<"终止景点：";
cin>>code2;
}
else
{
cout <<"请输入两景点间的距离：";
cin>>length;
insertEdge(v1,v2,length);
break;
}
}
cout <<"按回车键继续";
getchar();
getchar();}
else{printf("对不起，您输入的密码错误，不能执行该操作！\n输入回车键返回");
getchar();
getchar();
return 0;
}
};
//景点信息查询
void Graph::search()
{
int i;
char code;
while(1)
{
Map();
cout <<"请输入要查询的景点编号(输入#退出)：";
cin >> code;
if(code=='#')
break;
i=getPointPos(code);
if(i==-1)
{
cout <<"输入错误，请重新输入"<<endl;
}
else
{
Show(i);
cout <<"按回车键继续";
getchar();
getchar();
}
}
};
//查询两景点间最短距离
void Graph::minest()
{
system("cls");
Map();
int v1,v2;
char code1,code2;
cout << "编号如上图，请输入您要查询的两个景点的编号："<<endl;
cout <<"起始景点：";
cin >>code1;
cout <<"终止景点：";
cin>>code2;
while(1)
{
v1=getPointPos(code1);
v2=getPointPos(code2);
if(v1==-1||v2==-1)
{
cout <<"输入错误，请重新输入"<<endl;
cout <<"起始景点：";
cin >>code1;
cout <<"终止景点：";
cin>>code2;
}
else
{
MinPath(v1);
ShowMin(v1,v2);
break;
}
}
cout <<"按回车键继续";
getchar();
getchar();
};
//动态生成景点列表
void Graph::Map()
{ system("cls") ;
cout<<endl<<endl<<endl<<endl;
cout << "***************************************" << endl;
cout << "***景点编号如下： ***" << endl;
for(int i=1;i<=numPoints;i++)
{
cout <<PointsList[i-1].code<<std::left<<setw(15)<<PointsList[i-1].name;//std：：left 左对齐 setw（15） 占十五行内容
if(i%3==0)
cout <<endl;
}
cout <<endl<< "***************************************" << endl;
};
void Graph::insertcomments(){
char code;
string comment;
Map();
int i;
cout<<"请输入您要添加备注的景点编号： "<<endl;
while(1){
cin>>code;
i=getPointPos(code);
if(i==-1) printf("输入错误，请重新输入！");
else break;
}
cout<<"请输入您对于" <<Graph::PointsList[i].name<<"的看法~！(输入#号结束)"<<endl;
cin.ignore();
getline(cin,comment,'#');
insertcomment(i,comment);
cout<<"输入成功！";
getchar();
}
void Graph::showTime() {//输出最短时间
system("cls");
Graph::Map();
char code1,code2;
int v1,v2;
walk walk1;
bike bike1;
car car1;
cout << "请输入您要查询的两个景点的编号："<<endl;
cout <<"起始景点：";
cin >>code1;
cout <<"终止景点：";
cin>>code2;
while(1)
{char t1; system("cls"); Graph::Map();
v1=Graph::getPointPos(code1);
v2=Graph::getPointPos(code2);
if(v1==-1||v2==-1)
{
cout <<"输入错误，请重新输入"<<endl;
cout <<"起始景点：";
cin >>code1;
cout <<"终止景点：";
cin>>code2;
}
else {
MinPath(v1);
int x=Graph::FindMinPath(v1,v2);
cout<<"请选择您的出行方式：\n"<<"1.步行\n"<<"2.骑车\n"<<"3.开车\n"<<endl;
int t;
cin>>t;
while(1){
if(t<=0||t>3){
cout<<"输入错误，请重新输入" ;
break;
}
else{
switch(t) {
case 1:
walk1.showTime(x);
break;
case 2: bike1.showTime(x);break;
case 3: car1.showTime(x); break;
}
cout<<"输入任意键继续";getchar(); break;
}getchar();
getchar();
}
cin>>t1;
}
break;
} }
//起始页
void start()
{
int i;
for(i=0; i<5; i++)
cout<<endl;
cout<<" *********************************************"<<endl;
cout<<" ** **"<<endl;
cout<<" ** 欢迎使用陕西师范大学导游系统 **"<<endl;
cout<<" ** **"<<endl;
cout<<" *********************************************"<<endl;
for(i=0; i<5; i++)
cout<<endl;
cout<<"按回车键继续......";
getchar();
}
//菜单页
void meau()
{ cout << "*****************************************************************************************************************" << endl;
cout << "*** 当当当当！我可以实现以下功能~ ***"<<endl;
cout << "*****************************************************************************************************************" << endl;
cout << "*** ***" << endl;
cout << "*** 输入1执行景点信息查询 ***" << endl;
cout << "*** 输入2执行增加您对于景点的备注 ***" << endl;
cout << "*** 输入3执行查询两景点间最短距离 ***" << endl;
cout << "*** 输入4执行查询两景点间采用不同出行方式的最短时长 ***" << endl;
cout << "*** 输入5执行查询多个景点间的最佳路径 ***" << endl;
cout << "*** 输入6执行增加景点和道路(该功能为管理员功能) ***" << endl;
cout << "*** 输入0执行退出系统 ***" << endl;
cout << "*** ***" << endl;
cout << "*****************************************************************************************************************" << endl;
}
// ######################## 程序主入口 ########################
int main()
{ MessageBox(NULL,"马上要进入陕西师范大学校园导航系统啦，你准备好了吗？！","欢迎使用陕师大校园导航系统！",MB_OK);
system("color F9");
Graph g;
Time t;
int c;
start();
system("cls");
meau();
while (1)
{
system("cls");
meau();
cout << "请输入您要执行功能的编号：（请输入数字！）" ;
cin >> c;
if(c<0||c>5)
{
cout <<"输入错误，请重新输入！"<<endl;
getchar();
getchar();
}
switch (c)
{
case 1://景点信息查询
g.search();
break;
case 2:
g.insertcomments();
break;
case 3: //查询两景点间最短距离
g.minest();
break;
case 4:
g.showTime() ;
break;
case 5: //查询多个景点间的最佳路径
g.ShowMany();
break;
case 6://增加景点和道路
g.Increase();
break;
case 0: //结束程序
cout<<"谢谢您的使用！"<<endl;
return 0;
}
}
return 0; // 返回退出
}
版权声明：本文为博主作者：我想当程序y原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/jiumi45/article/details/128255101
