[数据结构与算法]【数据结构课程设计】c++实现校园导游程序及通信线路设计

【数据结构课程设计】c++实现校园导游程序及通信线路设计

校园导游程序及通信线路设计

问题描述：

设计校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
(1) 显示校园平面图（用cout显示即可）。
(2) 景点信息查询：为来访客人提供图中任意景点相关信息的查询。
(3) 任意2个景点的路径查询：为来访客人提供图中任意2个景点的问路查询,即查询任意两个景点之间的一条最短的简单路径及距离。
(4) 通信线路设计：以尽可能低的造价建造景点间的通信网络把这些景点联系在一起，每条通信线路的造价与景点间的距离成正比。给出铺设方案。
如何将编码转换成文字，或者不转换

基本要求：

1）关于显示校园平面图，示例如下：

2）图的存储采用邻接表；
3）程序做成菜单形式：
（路径查询->输入出发地与目的地->出最短路径）
4）给出部分景点的名称及简介（从中选取几个自己设计图，距离自定）

代码实现

主程序

#include<iostream>
#include<fstream>
using namespace std;
#define MaxEdgNum 100
#define MaxVerNum 100
#define Distance 50
#define Price 300
typedef string VertexTtpe;
typedef int EdgeType;
typedef struct node
{
	int adjvex;
	struct node* next;
	int info;
}EdgeNode;         //边结点
typedef struct vnode
{
	VertexTtpe vertex;
	EdgeNode* firstedge;
}VertexNode;       //顶点结点
typedef struct {
	VertexNode AdjList[MaxVerNum];
	int vnum, lnum;
}ALGraph;
typedef struct
{
	int v1;
	int v2;
	int cost;
}TreeEdgeType;           //最小生成树边结点
TreeEdgeType edges[MaxEdgNum], T[MaxVerNum];
//打印地图
void menu()
{
	cout << "1.景点信息查询" << endl;
	cout << "2.景点路径查询" << endl;
	cout << "3.通信线路铺设方案" << endl;
	cout << "0.退出系统" << endl;
}
void view()
{
	cout << "本地图的比例尺为1：5000                                              " << endl;
	cout << "                                      北校门                        " << endl;
	cout << "                                    /        \\                      " << endl;
	cout << "                                   /          \\                     " << endl;
	cout << "                          北图书馆               北运动场            " << endl;
	cout << "                        /         \\            /         \\         " << endl;
	cout << "                       /           \\          /           \\        " << endl;
	cout << "      大学生文化活动中心             奋  进  楼             大礼堂 " << endl;
	cout << "                       \\          /          \\                /    " << endl;
	cout << "                        \\        /            \\              |     " << endl;
	cout << "                          至诚楼             行政楼          |     " << endl;
	cout << "                                \\              |   \\         |     " << endl;
	cout << "                                 \\             |    \\       /      " << endl;
	cout << "                                 南运动场      |        南 图 书 馆 " << endl;
	cout << "                                         \\     |      /             " << endl;
	cout << "                                            南  校  门               " << endl;
}
//建邻接表
void CreateALGraph(ALGraph* G)
{
	int i, j, k, inf;
	EdgeNode* s;
	ifstream infile;       //从文件中导出哈夫曼树
	infile.open("data.dat");
	infile >> G->vnum >> G->lnum;
	for (i = 0; i < G->vnum; i++)
	{
		infile >> G->AdjList[i].vertex;
		G->AdjList[i].firstedge = NULL;
	}
	for (k = 0; k < G->lnum; k++)
	{
		infile >> i >> j >> inf;
		EdgeNode* s = new EdgeNode;
		s->adjvex = j;
		s->next = G->AdjList[i].firstedge;
		s->info = inf;
		G->AdjList[i].firstedge = s;
		EdgeNode* t = new EdgeNode;
		t->adjvex = i;
		t->next = G->AdjList[j].firstedge;
		t->info = inf;
		G->AdjList[j].firstedge = t;
	}
}
//景点查询
void Info()
{
	cout << "--------------" << endl;
	cout << "0;北校门" << endl;
	cout << "1:北图书馆" << endl;
	cout << "3:奋进楼" << endl;
	cout << "4:北运动场" << endl;
	cout << "5:行政楼" << endl;
	cout << "8:南校门" << endl;
	cout << "9:至城楼" << endl;
	cout << "10:大礼堂" << endl;
	cout << "11:南图书馆" << endl;
	cout << "12:大学生文化活动中心" << endl;
	cout << "14:南运动场" << endl;
	cout << "--------------" << endl;
}
void CheckInfo()
{
	Info();
	cout << "您好！ 按7可以退出查询" << endl;
	int m = 88;
	while (m != 99)
	{
		cout << "请输入查询的地点" << endl;
		cin >> m;
		switch (m)
		{
		case 0:
			cout << "北校门----学校的北入口" << endl;break;
		case 1:
			cout << "北图书馆---学校的北侧图书馆" << endl;break;
		case 3:
			cout << "奋进楼---公共机房" << endl;break;
		case 4:
			cout << "北运动场---具有足球场，篮球场，健身房等" << endl;break;
		case 5:
			cout << "行政楼---计算机学院楼及其他行政办公" << endl;break;
		case 8:
			cout << "南校门---学校南入口" << endl;break;
		case 9:
			cout << "至诚楼---办理学生事务处" << endl;break;
		case 10:
			cout << "大礼堂---学校大型文艺演出，讲座场所" << endl;break;
		case 11:
			cout << "南图书馆---学校南边的图书馆" << endl;break;
		case 12:
			cout << "大学生文化活动中心---团委，学生会，社联所在处" << endl;break;
		case 14:
			cout << "南运动场---具有足球场，篮球场，羽毛球场等" << endl;break;
		case 7:
			cout << "已退出景点信息查询，返回系统主菜单" << endl << endl; return;
		}
	}
}
//编号转换
void Change(int m)
{
	switch (m)
		{
		case 0:
			cout << "大学生文化活动中心";break;
		case 1:
			cout << "北图书馆";break;
		case 2:
			cout << "至诚楼";break;
		case 3:
			cout << "北校门";break;
		case 4:
			cout << "奋进楼";break;
		case 5:
			cout << "南运动场";break;
		case 6:
			cout << "北运动场";break;
		case 7:
			cout << "行政楼";break;
		case 8:
			cout << "南校门";break;
		case 9:
			cout << "南图书馆";break;
		case 10:
			cout << "大礼堂";break;
		}
}
int ReChange(int m)
{
	switch (m)
	{
	case 0:
		return 3;
	case 1:
		return 1;
	case 3:
		return 4;
	case 4:
		return 6;
	case 5:
		return 7;
	case 8:
		return 8;
	case 9:
		return 2;
	case 10:
		return 10;
	case 11:
		return 9;
	case 12:
		return 0;
	case 14:
		return 5;
	}
}
//最短路径
void ShortestPath(ALGraph* G)
{
	int vs, ve;
	Info();
	cout << "请根据编号输入您的出发地和目的地：" << endl;
	cin >> vs >> ve;
	vs = ReChange(vs);
	ve = ReChange(ve);
}
void floyd(ALGraph *G)
{
	int vs, ve;
	Info();
	cout << "请根据编号输入您的出发地和目的地：" << endl;
	cin >> vs >> ve;
	vs = ReChange(vs);
	ve = ReChange(ve); 
    int i, j, k, dist[MaxVerNum][MaxVerNum], path[MaxVerNum][MaxVerNum];
	for (i = 0; i < G->vnum; i++)
	{
		for (j = 0; j < G->vnum; j++)
		{
			dist[i][j] = 1000;
		}
		dist[i][i] = 0;
	}
	for (i = 0; i < G->vnum; i++)
	{
		EdgeNode* s = G->AdjList[i].firstedge;
		while (s)
		{
			dist[i][s->adjvex] = s->info;
			s = s->next;
		}
	}
	for (k = 0; k < G->vnum; k++)
	{
		for (i = 0; i < G->vnum; i++)
		{
			for (j = 0; j < G->vnum; j++)
			{
				if (dist[i][k] + dist[k][j] < dist[i][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = k;
				}
			}
		}
	}
	cout << "路径为：";
	Change(ve);
	if (path[vs][ve] == ve)
	{
		cout << "<-";
		Change(vs);
	}
	else 
	{
		k = ve;
		while (path[vs][k] != k)
		{
			k = path[vs][k];
			if (k < 0) break;
			cout << "<-";
			Change(k);
		}
		cout << "<-";
		Change(vs);
		cout << "(当前位置)";
	}
	cout << endl << "最短路径长度为" << dist[vs][ve] * Distance << "m" << endl;
}
//最小生成树
int Find(int father[], int v)
{
	int  t = v;
	while (father[t] >= 0)
		t = father[t];
	return t;
}
void Kruskal(ALGraph* G, TreeEdgeType edges[], TreeEdgeType T[])
{
	int father[MaxVerNum];
	int i, j, m, n, vf1, vf2, sum = 0;
	TreeEdgeType temp;
	ifstream infile;
	infile.open("data.dat");
	infile >> G->vnum >> G->lnum;
	for ( i = 0; i < G->vnum; i++)
	{
		infile >> G->AdjList[i].vertex;
	}
	for ( int k = 0; k < G->lnum; k++)
	{
		infile >> edges[k].v1 >> edges[k].v2 >> edges[k].cost;
	}
	for (m = 0; m < G->lnum; m++)
	{
		int swap = 0;
		for (n = 0; n < G->lnum - m; n++)
		if (edges[n].cost > edges[n+1].cost)
		{
			temp = edges[n + 1];
			edges[n + 1] = edges[n];
			edges[n] = temp;
			swap = 1;
		}
		if (swap == 0) break;
	}
	for (i = 0; i < G->vnum; i++)
		father[i] = -1;
	i = 0; j = 0;
	while (i < G->lnum && j < G->vnum - 1)
	{
		vf1 = Find(father, edges[i].v1);
		vf2 = Find(father, edges[i].v2);
		if (vf1 != vf2)
		{
			father[vf2] = vf1;
			T[j] = edges[i];
			j++;
		}
		i++;
	}
	cout << "经计算可以得知造价最低的方案需要铺设如下路段：" << endl;
	for (int a = 0; a < G->lnum; a++)
	{
		if (T[a].cost != 0)
		{
			Change(T[a].v1);
			cout << "--";
			Change(T[a].v2);
			sum = sum + T[a].cost;
			cout << endl;
		}
	}
	cout << endl << "长度为" << sum * Distance << "m" << endl;
	cout << "最低造价为" << sum * Price << "元" << endl;
}                                
//主函数
int main()
{
	ALGraph* G = new ALGraph;
	CreateALGraph(G);
	view();
	menu();
	char i = '*';
	while (i != '+')
	{
		cout << "请输入选择的选项" << endl;
		cin >> i;
		switch (i)
		{
		case'1':
			CheckInfo();
			menu();
			break;
		case'2':
			floyd(G);break;
		case'3':
			Kruskal(G, edges, T);break;
		case'0':return 0;
		}
	}
}

data.dat

11
15
0 1 2 3 4 5 6 7 8 9 10
0 1 3
0 2 4
1 3 2
1 4 1
2 4 3
2 5 5
3 6 6
4 6 8
4 7 4
5 8 2
6 10 7
7 8 10
7 9 4
8 9 1
9 10 6