【C++课程设计】校园导游程序及通信线路设计
问题描述： 设计校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (1) 显示校园平面图（用cout显示即可）。 (2) 景点信息查询：为来访客人提供图中任意景点相关信息的查询。 (3) 任意2个景点的路径查询：为来访客人提供图中任意2个景点的问路查询,即查询任意两个景点之间的一条最短的简单路径及距离。 (4) 通信线路设计：以尽可能低的造价建造景点间的通信网络把这些景点联系在一起，每条通信线路的造价与景点间的距离成正比。给出铺设方案。
校园的平面图如下
这些地图是我自己选的，如果想换其他的地图请参考文章【数据结构课程设计】c++实现校园导游程序及通信线路设计_c+设计校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、-CSDN博客
话不多说，上代码。这些代码是我在学期期间写的代码，可能会比较不完善，还请大家多多包涵。这里提供出代码给大家参考。
代码
#include<iostream>
#include<string>
using namespace std;
#define MAXVERNUM 10
#define MAXCOST 10000;
string names[MAXVERNUM] = { "A操场","B偏门","C图书馆","D大门","E食堂","F诚智楼","G博学楼","H创新楼","I海天楼","J明德楼" };
class EdgeNode//边结点
{
public:
EdgeNode()
{
this->adjvex = -1;
this->next = NULL;
}
int adjvex;//记录结点的编号
EdgeNode * next;
};
class VertexNode//顶点结点
{
public:
VertexNode()
{
this->vertex = "";
this->firstedge = NULL;
}
string vertex;//记录结点的名字
EdgeNode * firstedge;
};
class ALGraph
{
public:
ALGraph()
{
this->Vnum = -1;
this->Enum = -1;
}
VertexNode AdjList[MAXVERNUM];
int edges[MAXVERNUM][MAXVERNUM];//记录边之间的距离
int Vnum,Enum;//顶点数和边数
};
void CreateALGraph(ALGraph * G,int Vnum,int Enum)//不需要用户输入
{
EdgeNode * s;
G->Vnum = Vnum;
G->Enum = Enum;
for (int i = 0;i < G->Vnum;i++)
{
for (int j = 0;j < G->Vnum;j++)
{
if (i == j) G->edges[i][j] = 0;
else G->edges[i][j] = INT_MAX-1;
}
}
G->edges[0][1]=57;G->edges[0][3]=48;G->edges[0][4]=97;
G->edges[1][0]=57;
G->edges[2][3]=66;
G->edges[3][0]=48;G->edges[3][2]=66;G->edges[3][8]=15;G->edges[3][9]=223;
G->edges[4][0]=97;G->edges[4][6]=255;
G->edges[5][6]=134;G->edges[5][9]=82;
G->edges[6][4]=255;G->edges[6][5]=134;G->edges[6][7]=99;
G->edges[7][6]=99;
G->edges[8][3]=15;G->edges[8][9]=10;
G->edges[9][3]=223;G->edges[9][5]=82;G->edges[9][8]=10;
for (int i = 0;i <G->Vnum;i++)
{
G->AdjList[i].vertex = names[i];
G->AdjList[i].firstedge = NULL;
}
for (int i = 0;i < G->Vnum;i++)
{
for (int j = 0;j < G->Vnum;j++)
{
if (G->edges[i][j] < 500)
{
s = new EdgeNode();
s->adjvex = j;
s->next = G->AdjList[i].firstedge;
G->AdjList[i].firstedge = s;
}
}
}
}
void PrintMap()
{
cout << " 《校园地图》 " << endl;
cout << "============================================================" << endl;
cout << "|| A操场-----B偏门 ||" << endl;
cout << "|| / \\ ||" << endl;
cout << "|| / \\ ||" << endl;
cout << "|| C图书馆------D大门 E食堂----------\\ ||" << endl;
cout << "|| / \\ \\ ||" << endl;
cout << "|| / \\ F诚智楼-----G博学楼-H创新楼 ||" << endl;
cout << "|| / \\ / ||" << endl;
cout << "|| I海天楼-----J明德楼 ||" << endl;
cout << "============================================================" << endl;
}
void PrintMenu()
{
cout << "1.景点信息查询" << endl;
cout << "2.景点路径查询" << endl;
cout << "3.通信线路铺设方案" << endl;
cout << "0.退出系统" << endl;
}
//构建最小生成树
void Prim(ALGraph *G, int tree[MAXVERNUM], int cost[MAXVERNUM])
{
int flag[MAXVERNUM] = { 0 };
int i, j, k, mincost;
for (i = 1;i < G->Vnum;i++)
{
cost[i] = G->edges[0][i];
tree[i] = 0;
}
flag[0] = 1;
tree[0] = -1;
k = 0;
for (i = 1;i < G->Vnum;i++)
{
mincost = MAXCOST;
for (j = 1;j < G->Vnum;j++)
{
if (flag[j] == 0 && cost[j] < mincost)
{
mincost = cost[j];
k = j;
}
}
flag[k] = 1;
for (j = 1;j < G->Vnum;j++)
{
if (flag[j] == 0 && G->edges[k][j] < cost[j])
{
cost[j] = G->edges[k][j];
tree[j] = k;
}
}
}
}
//求最短路径
void ShorttestPath(ALGraph * G, int *P, float *D,int vs,int bs)
{
//vs为起始点，bs为终点
int fina[MAXVERNUM];//标志数组
int i,k,min,pre,j=0;
int tmp;
for (i = 0;i < G->Vnum;i++)
{
D[i] = G->edges[vs][i];
P[i] = vs;
fina[i] = 0;
}
//辅助数组D记录最短路径长度，P记录路径
D[vs] = 0;fina[vs] = 1;P[vs] = -1;
for (i = 1;i < G->Vnum;i++)
{
min = INT_MAX;
for (k = 0;k < G->Vnum;k++)
{
if (fina[k] == 0 && D[k] < min)
{
j = k;
min = D[k];
}
}
fina[j] = 1;
for ( k = 0;k < G->Vnum;k++)
{
if (fina[k] == 0 && (D[j] + G->edges[j][k] < D[k]))
{
D[k] = D[j] + G->edges[j][k];
P[k] = j;
}
}
}
cout << "从您选择的起始地点到目的地的最短距离为：" << D[bs] << endl << " 距离最短的路线为 : " << G->AdjList[bs].vertex;
pre = P[bs];
while (pre >= 0)
{
cout << "→" << G->AdjList[pre].vertex;
pre = P[pre];
}
cout << endl;
}
void Menu_One()
{
char a;
cout << "请选择要查询的景点（输入编号）";
cin >> a;
//对编号的判断
while (!(int(a) >= 65 && int(a) <= 74))
{
cout << "您输入的该景点编号不存在，请重新输入：";
cin >> a;
}
cout << "您所查询的地点为：" << names[a - 65] << " 该地点简介：";
if (a == 'A') cout << "具有足球场、篮球场、健身房等" << endl;
else if (a == 'B') cout << "学校的偏入口" << endl;
else if (a == 'C') cout << "学校北侧图书馆" << endl;
else if (a == 'D') cout << "学校正入口" << endl;
else if (a == 'E') cout << "学校师生食堂" << endl;
else if (a == 'F') cout << "公共机房" << endl;
else if (a == 'G') cout << "办理学生事务处" << endl;
else if (a == 'H') cout << "经管学院楼" << endl;
else if (a == 'I') cout << "计算机学院楼及其他行政办公" << endl;
else cout << "又称H楼，具有桌球、乒乓球、会议室、舞厅等" << endl;
}
void Menu_Two(ALGraph * G)
{
int P[MAXVERNUM];
float D[MAXVERNUM];
char a, b;
cout << "请输入您要查询的两个地点：";
cin >> a >> b;
while (!(int(a) >= 65 && int(a) <= 74)|| !(int(b) >= 65 && int(b) <= 74))
{
cout << "您输入的该景点编号不存在，请重新输入：";
cin >> a >> b;
}
if (a < b) swap(a, b);
ShorttestPath(G, P, D, a-65,b-65);
}
void Menu_Three(ALGraph *G)
{
int tree[MAXVERNUM];
int cost[MAXVERNUM];
int total=0;
for (int i = 0;i < MAXVERNUM;i++)
{
tree[i] = 0;
cost[i] = 0;
}
Prim(G, tree, cost);
for (int i = 1;i < MAXVERNUM;i++)
{
total += G->edges[i][tree[i]];
}
cout << "通信线路的铺设为：" << endl;
for (int i = 1;i < MAXVERNUM;i++)
{
cout << G->AdjList[i].vertex << "--- " << G->AdjList[tree[i]].vertex << endl;
}
cout << "总的路程为：" << total;
}
int main()
{
//图的初始化，根据需求可更改
ALGraph *myALGraph = new ALGraph();
CreateALGraph(myALGraph,MAXVERNUM,22);
while (true)
{
int choice;
PrintMap();
PrintMenu();
cin >> choice;
//检测菜单输入
while (choice != 1 && choice != 2 && choice != 3 && choice != 0)
{
cout << "您输入的选项有误，请重新输入:";
cin >> choice;
}
switch (choice)
{
case 1:
Menu_One();
system("pause");
system("cls");
break;
case 2:
Menu_Two(myALGraph);
system("pause");
system("cls");
break;
case 3:
Menu_Three(myALGraph);
system("pause");
system("cls");
break;
case 0:
cout << "欢迎下次使用！" << endl;
system("pause");
exit(0);
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-03-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读