大二专业课太多,都没有好好的在博客上面做笔记,以备后面用的时候可以查找看一下,下面是写的不是完全正确的与图相关的代码~~希望指正~~
/* Name: Copyright: Author:Hxm Date: 2016/05/16 22:57 Description: 实验四(必做,设计性实验,6学时) 实验题目:校园导游咨询实验 目的:掌握图的存储方法和最短路经算法。 实验内容:设计一个校园导游程序,为来访客人提供各种信息查询服务。 测试数据根据实际情况指定。提示:一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向图。顶点和边均含有相关信息。 实验要求: 1、设计所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息; 以边表示路径,存放路径长度等相关信息。 2、为来访客人提供图中任意景点相关信息的查询。 3、为来访客人提供图中任意景点的纹路查询,即查询任意两个景点之间的一条最短的简单路径。 实验内容和实验步骤:(由学生填写) 实验用测试数据和相关结果分析:(由学生填写) 实验总结:(由学生填写) */ #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> //------图的数组(邻接矩阵)存储表示------------ #define MAX 10000 //最大值 #define N 11 //最大顶点个数 //--------------------景点结构-------------------------------------------------- typedef struct MGraph { char *information; //景点名称 int weight; //景点距离; 玲姐矩阵中的权值 char vex[N]; // 顶点向量A-K int vexnum[N]; //景点数:0-10 }MGraph, AdjMatrix[N][N]; //-------------------OUC图的定义(邻接矩阵)------------------------------------- static struct MGraph a[N][N], *g; //-------------- 1. 首先向您展示OUC的地图O(∩_∩)O~~\n"); ---------------------- void DisPlayMGraph() { int i,j,k; //预先直接构造校园的图:邻接矩阵 //MGraph *g; //printf("test1......\n"); for(i=0; i<N; i++) { for(j=0; j<N; j++) { if(i==j) a[i][j].weight=0; else a[i][j].weight=MAX; } } //直接构造相互连接的路径 for(i=0; i<N; i++) { for(j=0; j<N; j++) { a[0][1].weight=1; a[0][10].weight=10; a[1][0].weight=1; a[1][2].weight=2; a[1][9].weight=8; a[1][10].weight=9; a[2][1].weight=2; a[2][3].weight=3; a[2][8].weight=5; a[3][2].weight=3; a[3][6].weight=6; a[3][10].weight=10; a[4][3].weight=4; a[4][10].weight=10; a[5][4].weight=5; a[6][5].weight=6; a[7][3].weight=5; a[7][4].weight=6; a[7][9].weight=7; a[8][10].weight=10; a[9][1].weight=8; a[9][8].weight=7; a[10][0].weight=10; a[10][1].weight=9; a[10][3].weight=10; a[10][4].weight=10; a[10][8].weight=10; } } //printf("test 2...\n"); //构造景点的顶点向量 for(i=0; i<11; i++) { for(j=0; j<11; j++) { a[0][i].vex[i]='A'+i; } } //printf("test 3......\n"); //景点的信息 for(i=0; i<N; i++) { a[0][0].information="北区宿舍"; a[0][1].information="康惠达超市"; a[0][2].information="3区教学区 "; a[0][3].information="九球广场 "; a[0][4].information="信息学院 "; a[0][5].information="图书馆 "; a[0][6].information="南区宿舍 "; a[0][7].information="西门 "; a[0][8].information="东区 "; a[0][9].information="体育馆 "; a[0][10].information=" 五子顶"; } //printf("test4.......\n"); for(i=0; i<N; i++) a[0][i].vexnum[i]=i; //printf("test5........\n"); printf(" "); for(i=0; i<N; i++) printf("%6c", a[0][i].vex[i]); printf("\n"); for(i=0; i<N; i++) { printf("%5c ", a[0][i].vex[i]); for(j=0; j<N; j++) { if(a[i][j].weight==MAX) printf(" ∞"); else printf(" %5d", a[i][j].weight); } printf("\n"); } printf("\n\n\n||--------------------------------------------------------------||\n\n\n"); printf("|| 以上矩阵对应的边的信息如下: ||\n\n\n"); for(i=0; i<N; i++) printf("%5c:%s ", a[0][i].vex[i], a[0][i].information); printf("\n\n\n\n\n"); } //-----------2. 任意景点相关信息的查询\n");---------------------------------- void QueryAnyViews() { printf("\n\n---------------------------------------------------------\n\n"); printf("*****请输入您要查询的景点序号:A~K (输入形式为大写字母 )******\n\n\n"); char choice; scanf("%c", &choice); printf("||------------------------------------------------------------------||\n"); switch(choice) { case 'A': printf("|| A 为中国海洋大学北区宿舍公寓,主要为理工科同学 ||\n"); break; case 'B': printf("|| B 为康惠达超市,里面为同学们提供各种日常所需用品 ||\n"); break; case 'C': printf("|| C 为公共教学区的第3 教学区, 主要是同学们上课自习的场所 ||\n"); break; case 'D': printf("|| D 为九球广场 周围是紫藤,开后非常 漂亮 ||\n"); break; case 'E': printf("|| E 为信息学院 主要是计算机、物理、海科等专业在里面做实验所用 ||\n"); break; case 'F': printf("|| F 为图书馆 里面藏书丰富 平常同学们都是满满的 期末考试时爆满 ||\n"); break; case 'G': printf("|| G 为南区宿舍 南区主要就是文管类的同学啦 ||\n"); break; case 'H': printf("|| H 为西门校门了 也是海大崂山校区的正门了 特别漂亮 ||\n"); break; case 'I': printf("|| I 为东区主要部分, 东区可是美食城啊 ||\n"); break; case 'J': printf("|| J 为体育馆 同时也是大学生活动多功能厅 ||\n"); break; case 'K': printf("|| K 为五子顶 它在夜景下可是一颗心形的,下面是美丽的樱花大道 ||\n"); break; default: break; } printf("||------------------------------------------------------------------||\n"); printf("\n\n\n"); } //---------------3. 任意景点的纹路查询,即查询任意两个景点之间的一条最短的简单路径-------------- //用 Dijkstra算法求原点到所有顶点的最短路径 void SimpleShortestPath() { printf("请输入您要查询的任意两个景点的顶点向量:0~10 \n\n\n "); int u, v; printf("\n请输入第一个要查询的起点\n"); scanf("%d", &u); printf("\n请输入第二个要查询的终点\n"); scanf("%d", &v); MGraph start[N]; //用start[N]数组来存放原点到所有顶点的而最短路径值 //先初始化start[N]数组, 就是 0 号顶点到其余各个顶点的初始路程 int i, j, k, min; for(i=0; i<N; i++) start[i].weight=a[0][i].weight; int book[N]; //book数组来记录最短路畅的顶点集合 book[i]为1表示此顶点在最短路径的集合中, 为0则没有 for(i=0; i<N; i++) book[i]=0; //book数组初始化 book[1]=1; //-----------Dijkstra算法核心语句---------------------------- for(i=0; i<N-1; i++) { min=MAX; //找距离 0 号最近的顶点 for(j=0; j<N; j++) { if(book[j]==0 && start[j].weight<min) { min=start[j].weight; u=j; } } book[u]=1; for(v=0; v<N; v++) { if(a[u][v].weight < MAX) { if(start[v].weight>start[u].weight + a[u][v].weight) start[v].weight=start[u].weight+a[u][v].weight; } } } //输出最终结果 for(i=0; i<N; i++) printf("%5d", start[i].weight); getchar(); getchar(); getchar(); } //-------------------------------------------------------------------------- //用 FloydWay算法求原点到所有顶点的最短路径 void FloydWay() { //printf("请输入您要查询的任意两个景点的顶点向量:0~10 \n "); int u, v, w; //printf("请输入第一个要查询的起点\n"); //scanf("%d", &v); //printf("请输入第二个要查询的终点\n"); // scanf("%d", &w); int i; MGraph g, distance[N][N]; int path[N][N][N]; for(v=0; v<N; v++) { for(w=0; w<N; w++) { distance[v][w].weight=a[v][w].weight; for(u=0; u<N; ++u) { path[v][w][w]=-1; if(distance[v][w].weight < MAX) { path[v][w][v]=TRUE; //从v 到 w 有直接路径 } } } } for(u=0; u<N; ++u) { for(v=0; v<N; ++v) { for(w=0; w<N; ++w) { if(distance[v][u].weight+distance[u][w].weight < distance[v][w].weight) { //从v到w的一条路径更短 distance[v][w].weight=distance[v][u].weight+distance[u][w].weight; for(i=0; i<N; i++) path[v][w][i]= path[v][u][i]||path[u][w][i]; } // printf("%3c ->%3c", distance[v][w].weight, distance[v][w].weight); } } } getchar(); getchar(); } void DisPlayWay() { printf("请输入您要查询的任意两个景点的顶点向量:0~10 \n "); int u, v, w; printf("请输入第一个要查询的起点\n"); scanf("%d", &v); printf("请输入第二个要查询的终点\n"); scanf("%d", &w); //printf("%c---->%c 的最短路径: \n", g.vex[v], g.vex[w]); printf("*********%5d------>%5d 的最短路径如下:*************\n\n\n", v, w); printf("*********%5s------->", a[0][v].information); printf("%5s***********\n\n\n", a[0][w].information); MGraph p[N][N]; int i, j, k; for(i=v; i<N; i++) { for(j=w; j<N; j++) { if(a[i][j].weight < MAX) { p[i][j].weight += a[v][w].weight; // printf("%d", p[i][j].weight); } //else // printf("%d ---> %d 没有最短路径。。。。。\n"); } //printf("%5s----->", p[i][j].information); //printf("%s", p[i][j].information); printf("%d----->", p[i][j].weight); } printf("\n\n\n"); } //---------------------------------主程序界面--------------------------------- int main() { printf("******************OUC校园导游*****************\n"); printf("******1.地图如下:******\n\n\n"); printf(" A: 北区宿舍 \n\n\n"); printf(" B:康惠达超市 \n\n"); printf(" J:体育馆 \n\n"); printf("\n\n\n"); printf(" K:五子顶 \n\n"); printf("H:西门 C:3区教学楼 \n\n"); printf(" I:东区 \n\n\n"); printf(" D:九球广场 \n\n"); printf(" E:信息学院 \n\n\n"); printf("\n\n F:图书馆 \n\n\n"); printf("\n\n\n G:南区 \n\n\n"); printf("*********请选择要进行的操作**************\n\n\n"); printf(" 1. 首先向您展示OUC的地图O(∩_∩)O~~\n\n\n"); printf(" 2. 任意景点相关信息的查询\n\n\n"); printf(" 3. 任意景点的纹路查询,应Dijkstra方法求即查询任意两个景点之间的一条最短的简单路径--------------\n\n\n"); printf (" 4. 用Floyd弗洛伊德方法求一对顶点之间的最短路径\n\n\n"); printf(" 0. 退出。。-------------------------------\n\n\n"); printf("****请输入1 、 2进行选择(直接输入 0 结束 **********\n\n\n"); int choice; scanf("%d", &choice); while(choice!=0) { switch(choice) { case 1: printf(" 1. 首先向您展示OUC的地图O(∩_∩)O~~\n\n"); DisPlayMGraph(); break; case 2: printf(" 2.现在您会看到ouc景点的简要介绍\n\n"); QueryAnyViews(); break; case 3: printf(" 3.从北区宿舍楼到其他各个顶点的最短路径距离\n\n"); SimpleShortestPath(); break; case 4: printf("任意两个顶点之间的最短路径\n\n\n"); FloydWay(); DisPlayWay(); break; default: break; } printf("********请输入1 、 2、 3、 4 进行选择(直接输入 0 结束 **********\n\n\n"); scanf("%d", &choice); } system("pause"); return 0; }
运行效果如下:
希望大神指正~~~