景区旅游信息管理系统
【问题描述】
在旅游景区，经常会遇到游客打听从⼀个景点到另⼀个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，⽽是挑选⾃⼰感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采⽤迪杰斯特拉算法或弗洛伊德算法均可。建⽴⼀个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。 课程
任务中景点分布是⼀个⽆向带权连通图，图中边的权值是景点之间的距离。
（1）景区旅游信息管理系统中制订旅游景点导游线路策略，⾸先通过遍历景点，给出⼀个⼊⼝景点，建⽴⼀个导游线路图，导游线路图⽤有向图表⽰。遍历采⽤深度优先策略，这也⽐较符合游客⼼理。 （2）为了使导游线路图能够优化，可通过拓朴排序判断图中有⽆回路，若有回路，则打印输出回路中的景点，供⼈⼯优化。
（3）在导游线路图中，还为⼀些不愿按线路⾛的游客提供信息服务，⽐如从⼀个景点到另⼀个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。
（4）在景区建设中，道路建设是其中⼀个重要内容。道路建设⾸先要保证能连通所有景点，但⼜要花最⼩的代价，可以通过求最⼩⽣成树来解决这个问题。本任务中假设修建道路的代价只与它的⾥程相关。
【基本要求】
本任务应有如下功能模块：
创建景区景点分布图；
输出景区景点分布图（邻接矩阵）
输出导游线路图；
判断导游线路图有⽆回路；
求两个景点间的最短路径和最短距离；
输出道路修建规划图。
主程序⽤菜单选项供⽤户选择功能模块。
因为时间很仓促，做的不是很好，判断导游线路图我没⽤拓扑排序(写了没⽤) .
然后我的边和景点信息存在⼯程下⽬录edge 和 map 两个⽂件中.
代码 :
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#define path ""
#include <windows.h>
#include <vector>
#include <iostream>
using namespace std ;
const int MAX = 105 ;
const int inf = 0x3f3f3f;
// 景区旅游信息管理系统
typedef struct node{
char PlaceName[MAX] ; // 景点的名字 int number ; // 景点编号
char PlaceNum[MAX] ; // 编号 ;
}Node;
typedef struct Tornode{
int u ;
int v ;
int weight ;
}TorNode; // 起点终点和距离 ;
typedef struct matGraph{
int map[MAX][MAX] ;
int n , e ;
}MatGraph;// 完整的图邻接矩阵类型
typedef struct NODE{
int key ;// 关键字项
Node infor ; // 信息
struct NODE *lchild ;
struct NODE *rchild ;
}BSTNode;
typedef struct ANode{
int adjvex ; // 编号
struct ANode *nextarc ;
int weight ;
}ArcNode ; // 边节点的类型
typedef struct Vnode{
ArcNode *fitstarc ;
int count ;
}VNode; // 邻接表的头结点类型
typedef struct {
VNode adjlist[MAX] ;
int n , e ; // 边数和顶点数
}AdjGraph;
int vis[MAX] ;
int dis[MAX] ;
int count1 ;
BSTNode *MapVex[MAX] ; // 顶点
void CreatMatGragh(MatGraph > ,int n ,int e , int pot, TorNode Gr[MAX][MAX]) {
// 创建导游有向图 ;
for(int i = 1 ; i<=n ; i++)
{
for(int j = 1 ; j <=n ;j++)
{
if(i == j )
{
GT.map[i][j] = 0 ;
}
GT.map[i][j] = inf ;
}
}
for(int i = 1 ; i<=e ; i++)
{
GT.map[Gr[pot][i].u][Gr[pot][i].v] = Gr[pot][i].weight ;
}
return ;
}
int cmp(const Node &a , const Node &b)
{
return a.number <b.number ;
}
int digit(int x )
{
// 计算位数
int t = x ;
int k = 0 ;
while(t)
{
k++;
k++;
t/=10 ;
}
return k ;
}
char *transtr(int n)
{
//转换成字符串
//char t[MAX] ;
char t[MAX] ;
int i = 0 ,x = n ;
while(x)
{
t[digit(n) - i-1] = (x%10) + '0' ;
x/=10 ;
i++;
}
return t ;
}
void Read(Node Place[] ,int n ,int e)
{
// 读取数据
FILE *fp ;
fp = fopen(path,"r");
if(fp == NULL)
{
perror("fopen\n") ;
exit(-1) ;
}
for(int i = 1 ; i<=n ; i++)
{
fscanf(fp,"%s %d",Place[i].PlaceName,&Place[i].number); int d = digit(Place[i].number) ;
char Tmp[MAX] = "000";
if(d==1)
{
strcpy(Place[i].PlaceNum,transtr(Place[i].number)) ;
strcat(Tmp,Place[i].PlaceNum) ;
strcpy(Place[i].PlaceNum,Tmp) ;
}
else if(d==2)
{
char Tmp[MAX] = "00";
strcpy(Place[i].PlaceNum,transtr(Place[i].number)) ;
strcat(Tmp,Place[i].PlaceNum) ;
strcpy(Place[i].PlaceNum,Tmp) ;
}
else if(d==3)
{
char Tmp[MAX] = "0";
strcpy(Place[i].PlaceNum,transtr(Place[i].number)) ;
strcat(Tmp,Place[i].PlaceNum) ;
}
}
return ;
}
void MAtToList(MatGraph g , AdjGraph *&G)
{
//将邻接矩阵转换成邻接表
//将邻接矩阵转换成邻接表
ArcNode *p ; // 边节点
G = (AdjGraph *)malloc(sizeof(AdjGraph)) ; for(int i = 1 ; i<=g.n ; i++)
{
G->adjlist[i].fitstarc = NULL ;
}
for(int i = 1 ; i<= g.n ; i++)
{
for(int j = g.n ; j >=1 ; j--)
{
if(g.map[i][j]!= 0 && g.map[i][j] !=inf )
{
p = (ArcNode *)malloc(sizeof(ArcNode)) ; p->adjvex = j ;
p->weight = g.map[i][j] ;
p->nextarc = G->adjlist[i].fitstarc ;
G->adjlist[i].fitstarc = p ;
}
}
}
G->n = g.n ;
G->e = g.e ;
return ;
}
int DispAdj(AdjGraph *G )
{
// 输出邻接表
ArcNode *p ;
int count = 0 ;
for(int i = 1 ; i <=G->n ; i++ )
{
p = G->adjlist[i].fitstarc ;
printf("%3d: " ,i ) ;
while(p!=NULL )
{
printf("%3d[%d]-> ", p->adjvex , p->weight ) ; p = p->nextarc ;
count++ ;
}
printf(" ^ \n") ;
}
return count;
}
BSTNode *SearchBST(BSTNode *bt , int k ) {
// 在⼆叉搜素树中查编号为k 的节点
// return 节点的地址
if(bt == NULL || bt->infor.number == k )
{
return bt ;
}
if(k < bt->infor.number)
{
return SearchBST(bt->lchild , k) ;
}
else
{
return SearchBST(bt->rchild , k ) ;
}
}
void TopSort(AdjGraph *G)
{
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议