使用弗洛伊德算法实现简单的校园导游咨询系统

博主是弱校大一软件工程专业的一名学生，上学期学校开设了程序设计基础——C语言，在这学期伊始，学校开设了一门两个学分的程序设计实践课程，要求用C语言来写一个简单的程序，给了25个命题，博主在一个朋友的邀请下，选择了这个比较有意思的校园导游咨询系统。 需求如下

1、功能描述：设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点， 存放景点名称，代号，简介等信息； 以边表示路径，存放路径长度等相关信息。 2、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 3、为来访客人提供图中任意景点相关信息的查询。 ……（可以补充其他功能） 测试数据：由读者根据实际情况指定。 实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，顶点和边均含有相关信息。

因为程序=数据结构+算法 很明显这个程序最应该选用的数据结构是图，用邻接矩阵来表示图结构。在刚开始做的时候，感觉这个需求的难点就是求出任意两个景点的最短路径，因为博主在大一上学期还自学了数据结构，知道求最短路径有两种算法，一种是迪杰斯特拉算法，另一种是弗洛伊德算法，便选择用弗洛伊德算法来求解。 还有感觉功能太过于单一，便又实现了打印学校平面图、评论以及查看评论的功能。 下面是系统功能模块图 每个功能文字说明 1.PrintGraph 打印出学校的平面图 2.SearchPath 运用弗洛伊德算法，计算出两个景点间的最短路径 3.SearchInfo 遍历图的存储景点名称的一维数组，查找到记录下下标，打印出景点的编号、名称、和基本信息 4.Comment 向用户提供键盘输入，将用户输入的内容写入到文件当中 5.ReadComment 读取保存用户评论的文件，并将内容依次输出到控制台 6.Exit 调用exit(0)退出程序，在退出前，调用Sleep，来实现倒计时 下面是程序的启动界面 这是功能一：打印学校的平面图 因为我没有学过C语言的图形库，这两幅图都是我的那个朋友画的，学校的平面图也是她用Visio画的，我主要负责其余的功能，我认为她做的非常的棒。 下面是程序的菜单列表 我一个理科男不太擅长做漂亮的界面，只是力求简洁（其实是自己懒）。 最后附上程序的源码

#include <stdio.h> #include <stdlib.h> #include <string.h> //引入字符串处理函数的头文件 #include <Windows.h> //引入包含Sleep函数的头文件 #include <conio.h> #include <graphics.h> #define MAXVEX 20 //图最大的结点数目 #define INFINITY 65535 //无穷大表示不存在弧 typedef int EdgeType; typedef struct { //定义图的每个结点信息 char name[20]; //景点的名称 int id; //景点的编号 char introduction[1000]; //景点的介绍 }VextexType; typedef struct Graph{ //定义图数据结构 VextexType vertex[MAXVEX]; //一维数组存储图的结点信息 EdgeType arc[MAXVEX][MAXVEX]; //二维数组存储图的弧的信息 int numVertexes, numEdges; //图的结点数和弧数 }MGraph; void Menu(); //显示菜单的函数 void Create(MGraph *G); //初始化图的函数 void PrintBackgrand(); //打印背景的函数 void PrintGraph(); //打印平面图的函数 void SearchPath(MGraph G, char *loc1, char *loc2); //查找最短路径的函数 void ShortestPath_Floyd(MGraph G, char *loc1, char *loc2); //弗洛伊德算法的函数 int SearchidByName(MGraph G, char *loc); //通过景点名称查找编号的函数 void SearchInfo(MGraph *G); //查找景点信息的函数 void Comment(); //评论的函数 void ReadComment(); //查看评论的函数 void Exit(); //退出程序的函数 IMAGE img1,img2,g1,g2,g3,g4,g5,g6,g7,g8,g9,g10; char *p="WELCOME TO SOUTHWEST PETROLEUM UNIVERSITY!"; char *p1="press any key to continue"; int main() { MGraph G; //定义一个图结构 Create(&G); //初始化图 PrintBackgrand(); while (1) { int choice; //需要进行的操作 Menu(); scanf("%d", &choice); system("cls"); switch (choice) { //根据输入的值选择对应的操作 case 1: //学校平面图 PrintGraph(); break; case 2: //查找两个景点的最短路径 system("cls"); char loc1[20], loc2[20]; printf("请输入您想查找最短路径的两个景点的名称:\n"); scanf("%s%s", &loc1, &loc2); if (SearchidByName(G, loc1) == -1 || SearchidByName(G, loc2) == -1){ printf("景点名称输入错误!\n"); } else{ SearchPath(G, loc1, loc2); } break; case 3: //查找景点的信息 system("cls"); SearchInfo(&G); break; case 4: //留下对西南石油大学的评论 Comment(); break; case 5: //查看评论 ReadComment(); break; case 6: //退出程序 Exit(); break; default: printf("输入错误,请重新输入!"); } system("pause"); system("cls"); } system("pause"); return 0; } //定义菜单的函数 void Menu() { printf("\n\n\n\n\n\n\n\t\t\t-------------------------------------------------------\n\n\n"); printf("\t\t\t\t欢迎使用西南石油大学校园导游咨询系统\n\n"); printf("\t\t\t\t\t请选择您需要的功能\n\n"); printf("\t\t\t\t\t1.学校平面图\n\n"); printf("\t\t\t\t\t2.查询两个景点之间的最短路径\n\n"); printf("\t\t\t\t\t3.查询景点的相关信息\n\n"); printf("\t\t\t\t\t4.留下您对西南石油大学的评论\n\n"); printf("\t\t\t\t\t5.查看评论\n\n"); printf("\t\t\t\t\t6.退出程序\n"); printf("\n\n\t\t\t-------------------------------------------------------\n\n"); } //定义初始化的函数 void Create(MGraph *G) { int i, j, k, w; FILE *fp; fp = fopen("view.txt", "r"); if (!fp) { printf("error!"); return; } if (fp) { fscanf(fp, "%d,%d", &G->numVertexes, &G->numEdges); for (i = 0; i < G->numVertexes; i++) { fscanf(fp, "%d,%s", &G->vertex[i].id, &G->vertex[i].name); fgets(G->vertex[i].introduction, 1000, fp); } for (i = 0; i < G->numVertexes; i++) { for (j = 0; j < G->numVertexes; j++) { G->arc[i][j] = INFINITY; } } for (k = 0; k < G->numEdges; k++) { fscanf(fp, "%d,%d,%d", &i, &j, &w); G->arc[i-1][j-1] = w; G->arc[j-1][i-1] = G->arc[i-1][j-1]; } fclose(fp); } else G->numEdges = 0; } //定义打印背景的函数 void PrintBackgrand() { initgraph(1000,700); loadimage(&img1,"Backgrond.jpg"); putimage(160,100,&img1); outtextxy(300,500,p); outtextxy(800,650,p1); getch(); closegraph(); } //定义打印平面图的函数 void PrintGraph() { initgraph(1100,800); loadimage(&img2,"Graph.jpg"); putimage(30,20,&img2); outtextxy(680,400,p); outtextxy(900,750,p1); getch(); closegraph(); } //定义计算最短路径的函数 void SearchPath(MGraph G, char *loc1, char *loc2) { ShortestPath_Floyd(G, loc1, loc2); } //定义弗洛伊德算法的函数 void ShortestPath_Floyd(MGraph G, char *loc1, char *loc2) { int l1, l2; l1 = SearchidByName(G, loc1); l2 = SearchidByName(G, loc2); int minDistance[MAXVEX][MAXVEX]; int path[MAXVEX][MAXVEX]; int i, j; for (i = 0; i < G.numVertexes; i++) { for (j = 0; j < G.numVertexes; j++) { minDistance[i][j] = G.arc[i][j]; path[i][j] = -1; } } for (int k = 0; k < G.numVertexes; k++){ for (int i = 0; i < G.numVertexes; i++) { for (int j = 0; j < G.numVertexes; j++) { if (minDistance[i][j] > minDistance[i][k] + minDistance[k][j]) { minDistance[i][j] = minDistance[i][k] + minDistance[k][j]; path[i][j] = k; } } } } printf("Matrix minDistance\n"); for (i = 0; i < G.numVertexes; i++) { for (j = 0; j < G.numVertexes; j++) { printf("%d\t", minDistance[i][j]); } printf("\n"); } printf("Matrix path\n"); for (i = 0; i < G.numVertexes; i++) { for (j = 0; j < G.numVertexes; j++){ printf("%d\t", path[i][j]); } printf("\n"); } printf("%s到%s最短的路径距离为:%d米\n", loc1, loc2, minDistance[l1][l2]); } //定义通过景点名称查找景点的编号的函数 int SearchidByName(MGraph G, char *loc) { int i; int flag = -1; for (i = 0; i < G.numVertexes; i++) { if (strcmp(G.vertex[i].name, loc) == 0) { flag = i; break; } } return flag; } //定义查找景点信息的函数 void SearchInfo(MGraph *G) { int i; int flag = -1; char name[20]; printf("请输入您想查询的景点的名称:\n"); scanf("%s", &name); for (i = 0; i < G->numVertexes; i++) { if (strcmp(G->vertex[i].name, name) == 0) { flag = i; break; } } if(flag != -1){ printf("该景点的编号为:%d\n", G->vertex[i].id + 1); printf("该景点的名称为:%s\n", G->vertex[i].name); printf("该景点的介绍为:%s\n", G->vertex[i].introduction); } else{ printf("景点名称输入错误!\n"); } } //定义评论的函数 void Comment() { int flag = 0; FILE *fp; fp = fopen("comment.txt", "at"); char comment[100]; printf("请输入您宝贵的意见:\n"); flag = scanf("%s", &comment); fprintf(fp, "%s\n", comment); if (flag) { printf("评论成功,感谢您的参与!\n"); } else { printf("I am sorry to tell you that you fail to comment!\n"); } fclose(fp); } //定义查看评论的函数 void ReadComment(){ FILE *fp; fp = fopen("comment.txt", "rt"); char comment[100]; while(fscanf(fp, "%s", &comment) != -1){ printf("%s\n", comment); } fclose(fp); } //定义退出程序的函数 void Exit() { for (int i = 5; i >= 1; i--) { printf("程序正在退出，倒计时：%d秒", i); Sleep(1000); system("cls"); } exit(0); }

最后也是希望能够宣传一下我们的学校，也希望各路朋友能够指正一些错误，以及提供更好的建议，我会陆续完善一些其它的功能，希望大家多多支持，非常感谢！！！