旅游系统资讯系统的设计方案

系统资讯系统的设计方案"/>

旅游系统资讯系统的设计方案

搜索算法 DFS 最短路径算法
在这里插入代码片旅游系统资讯系统的设计方案/*项目八 旅游景点咨询系统的设计与实现 (16学时)
1．问题描述：创建一个至少有15个点的有向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串
（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），
弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行0和索道1没有方式表示为零，两种）。建立一个游客咨询系统。
2．基本要求
（1）创建图的存储结构。
（2）输入两个景点名，就可以得到从一个景点到达另一个景点的。所有。简单路径、相应路径的路程公里数、行走的方法（每一段是步行0，还是坐索道1）(深度优先搜索)
（3）输入两个景点名，就可以得到其。最短。路径，即：路程最短的行进方法；如果两者无路径可通，就得出。“两景点不可达的信息”。。(最短路径算法)
（4）按照题意要求独立进行设计，设计结束后按要求写出设计报告。

在这里插入代码片*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MVnum 20/*定义了做多有多少个顶点*/
#define MAXint 32767
typedef struct Date
{int way;//表示的是到达的方式 1步行 -1索道 0没有方式int length;//代表的是两个地方的距离
}Date;
typedef struct AMgraph
{char vexs[MVnum][MVnum];//定义的是顶点的元素Date arcs[MVnum][MVnum];//定义的是变得矩阵int vexsnum, arcsnum;//顶点的个数 边的个数
}AMgraph;
int flag[MVnum];//建立一个标志的数组0代表这个节点没有被访问过 1就代表到达了这个顶点。
int list[MVnum];//把被访问的元素记录下来。
char vexs_end[20];
int getnum(AMgraph *T, char *s)
{int i;for (i = 0; i < (*T).vexsnum; i++){if (strcmp(s, (*T).vexs[i]) == 0){return i;}}
}
void creat_AMgraph(AMgraph *T)
{int i, j,s;char date1[20], date2[20];int way, length;FILE *fp;fp = fopen("C:\\Users\\钱磊\\Desktop\\项目四\\AMgraph.txt", "r");fscanf(fp, "%d", &(*T).vexsnum);for (i = 0; i < (*T).vexsnum; i++){fscanf(fp, "%s", (*T).vexs[i]);}//初始化边的信息for (i = 0; i < (*T).vexsnum; i++){for (j = 0; j < (*T).vexsnum; j++){(*T).arcs[i][j].way = 0;(*T).arcs[i][j].length = MAXint;}}fscanf(fp,"%d", &(*T).arcsnum);for (s = 0; s < (*T).arcsnum; s++){fscanf(fp,"%s%s%d%d", date1, date2, &way, &length);i = getnum(T, date1);j = getnum(T, date2);(*T).arcs[i][j].way = way;(*T).arcs[i][j].length = length;}fclose(fp);//建立图节点完成for (i = 0; i < (*T).vexsnum; i++){printf("%d  %s   ",i, (*T).vexs[i]);for (j = 0; j < (*T).vexsnum; j++){printf("%d %5d   ", (*T).arcs[i][j].way, (*T).arcs[i][j].length);}printf("\n");}
}
void DFS(AMgraph *T,char *vexs_start,int step)//setp的个数比走的次数多了一个。
{int i, j;i = getnum(T, vexs_start);if (strcmp(vexs_end, vexs_start) == 0)//到达最后的定点的话就做最后的处理 {int sum=0;for (i = 0; i < step-1; i++){sum = sum + (*T).arcs[list[i]][list[i + 1]].length;//计算总的公里数；}printf("总路程是%d公里", sum);for (i = 0; i < step-1; i++){if ((*T).arcs[list[i]][list[i + 1]].way == -1){printf("从%s到%s走划船  划船长度为%d     ", (*T).vexs[list[i]], (*T).vexs[list[i + 1]], (*T).arcs[list[i]][list[i + 1]].length);}if ((*T).arcs[list[i]][list[i + 1]].way == 1){printf("从%s到%s走步行 步行长度为%d     ", (*T).vexs[list[i]], (*T).vexs[list[i + 1]], (*T).arcs[list[i]][list[i + 1]].length);}}printf("\n");printf("\n");}else//没有到达最后的定点就不断的向下寻找。{for (j = 0; j < (*T).vexsnum; j++){if (flag[j] == 0&&(*T).arcs[i][j].length!=MAXint)//判断可不可以选择。{flag[j] = 1;//选择这个顶点list[step] = j;//目前走到了那个顶点step++;DFS(T, (*T).vexs[j], step);//这里注意下下++stepflag[j] = 0;//递归到了这个顶点代表目前就在这个顶点 step--;//step这个小东西他必须回溯这样才没问题。}}/*回溯的思想很重要的。对这个算法还不是很熟悉。就是这么一个意思。*/}
}
void shortpath_DIJ(AMgraph *T, char *vexs_start)
{int s[MVnum];// 1代表已经被选择过了int d[MVnum];//到顶点的距离 int path[MVnum];//前端的节点 int i, j, min,v;//初始化数据v = getnum(T, vexs_start);//被选择出来的定点for (i = 0; i < (*T).vexsnum; i++){if (i != v){s[i] = 0;d[i] = (*T).arcs[v][i].length;//从这个前面的顶点到第i个顶点的距离path[i] = v;}}s[v] = 1;d[v] = 0;path[v] = -1;for (i = 1; i < (*T).vexsnum; i++){min = MAXint;for (j = 0; j < (*T).vexsnum; j++){if (s[j] == 0 && min>d[j])//选择出一个最小的元素最小的元素下标记为v{min = d[j];v = j;}}//选出当前最优的顶点s[v] = 1;//最小的元素被选出来了d[i]最短的距离已经确定了for (j = 0; j < (*T).vexsnum; j++){if (s[j] == 0 && d[j] > d[v] + (*T).arcs[v][j].length){d[j] = d[v] + (*T).arcs[v][j].length;path[j] = v;}}}for (i = 0; i < (*T).vexsnum; i++){printf("%d %2d   ",i, path[i]);//把的前驱结点都记录出来了}j = getnum(T, vexs_end);printf("\n");if (d[j] == MAXint){printf("没有路径可以到达\n");}else{i = MVnum - 1;while (j != -1)//当j=-1的时候退出循环就是这么简单。{s[i] = j;j = path[j];i--;}printf("\n");int sum = 0;for (j = i+1; j < MVnum-1; j++)/*这个地方错了好多次就是很头疼*/{if ((*T).arcs[s[j]][s[j + 1]].way == -1){printf("从%s到%s要划船 坐船要%d公里     ", (*T).vexs[s[j]], (*T).vexs[s[j + 1]], (*T).arcs[s[j]][s[j + 1]].length);}if ((*T).arcs[s[j]][s[j + 1]].way == 1){printf("从%s到%s要步行 要步行%d公里     ", (*T).vexs[s[j]], (*T).vexs[s[j + 1]], (*T).arcs[s[j]][s[j + 1]].length);}sum = sum + (*T).arcs[s[j]][s[j + 1]].length;}printf("一共要走%d公里\n",sum);}
}
int main()
{int i;char vexs_start[20];AMgraph T;creat_AMgraph(&T);//用的是内部的地址就是这么简单 创建图节点完成。printf("输入两个顶点查看他们之间的所有的路径   ");scanf("%s%s", vexs_start, vexs_end);getchar();i = getnum(&T,vexs_start);flag[i] = 1;//起点list[0] = i;//起点DFS(&T,vexs_start,1);//选择就堵上保存起来。printf("输入想要得到的最短的距离的两个点");scanf("%s%s", vexs_start, vexs_end);shortpath_DIJ(&T, vexs_start);return 0;
}

图片的信息

输入输出