太工校园导游咨询系统---数据结构课程设计.doc

太原工业学院校园导游咨询系统1 需求分析本程序的主要目的是为了提供本学校的景点的路径咨询,为来访的客人提供各种信息查询服务。1、为来访的客人提供图中任意景点相关信息的查询。2、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。3、为客人显示所有景点。2 概要设计本程序包含的几个函数：void cmd(void);/在主函数中用来调用其他应用子函数的函数声明MGraph InitGraph(void);/用来构造学校地图的子函数 返回MGraph类型void Menu(void);/菜单函数；void Browser(MGraph *G);/调用MGraph类型的地址，进行void ShortestPath_DIJ(MGraph * G);/迪杰斯特拉算法求最短路径的子函数void Floyd(MGraph *G);/佛洛伊德算法void Search(MGraph *G);/寻找要查询的景点，并输出该景点的信息void browse_view_distribute();/查看景点分布图void tou(MGraph *G);/景点列表void panduan();int LocateVex(MGraph *G,char* v);/定点位置MGraph * CreatUDN(MGraph *G);/初始化图形，接受用户输入void print(MGraph *G);/打印输出子函数void main(void)3 详细设计从学院的平面地图中选取出几个个有代表性的景点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表景点，存放景点名称、代号、简介等信息，权值代表两地之间的距离。1、 图的存储结构如下：typedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction200;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;/景点AdjMatrix arcs;/路径数组int vexnum,arcnum;/景点数，路径长度记录MGraph;4 测试分析 (这是初始化界面)选择1 选择2 选择 3 5 使用说明 选择1时，可以查看校园的大致地图。选择2，输入起点和终点的位置，系统会给出最佳路线，选择3时，可查询任意景点的信息.6 测试结果 略7 附录（源代码）#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#include#include #include Exit.htypedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction200;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;/景点AdjMatrix arcs;/路径数组int vexnum,arcnum;/景点数，路径长度记录MGraph;MGraph b;/全局变量 void cmd(void);/在主函数中用来调用其他应用子函数的函数声明MGraph InitGraph(void);/用来构造学校地图的子函数 返回MGraph类型void Menu(void);/菜单函数；void Browser(MGraph *G);/调用MGraph类型的地址，进行void ShortestPath_DIJ(MGraph * G);/迪杰斯特拉算法求最短路径的子函数void Floyd(MGraph *G);/佛洛伊德算法void Search(MGraph *G);/寻找要查询的景点，并输出该景点的信息void browse_view_distribute();/查看景点分布图void tou(MGraph *G);/景点列表void panduan();int LocateVex(MGraph *G,char* v);/定点位置MGraph * CreatUDN(MGraph *G);/初始化图形，接受用户输入void print(MGraph *G);/打印输出子函数void main(void)SetConsoleTitle(校园导游系统 By纷羽纪念);system(mode con: cols=100 lines=100);/设置调试窗口的大小 coutnnnnnn; cout *n; cout * *n; cout * *n; cout * *n; cout * *n; cout * *n; cout * 欢迎使用太工校园导游系统 *n; cout * *n; cout * *n; cout * *n; cout * *n; cout * *n; cout *n; coutnnnnnn; Sleep(1500); /system(cls);cmd();/用该函数来调用其他需要用到的函数void cmd(void)/用来调用其他需要用到的函数的子函数int i;b=InitGraph();/构造校园地图Browser(&b);/Menu();/调用菜单函数scanf(%d,&i);while(i!=4)switch(i)case 1:system(cls);browse_view_distribute();Browser(&b);break;case 2:system(cls);tou(&b);Floyd(&b);Browser(&b);break;case 3:system(cls);tou(&b);Search(&b);Browser(&b);break;case 4:exit(0);break;default:break;scanf(%d,&i);printf(欢迎下次继续使用 !nn);/*MGraph InitGraph(void)/构造校园地图MGraph G;int i,j;G.vexnum=13;/景点数量G.arcnum=21;/路径数量for(i=1;i=G.vexnum;i+)G.vexsi.num=i;/对景点进行对应编号 /*对对应的景点编号进行命名，输入简介*/strcpy(G.,超市); strcpy(G.roduction,一个地下超市，商品齐全);strcpy(G.,扇形报告厅);strcpy(G.roduction,进行晚会、大型活动的地方);strcpy(G.,女生宿舍楼);strcpy(G.roduction,女生楼); strcpy(G.,校门);strcpy(G.roduction,学校的形象，不过没有东大门霸气);strcpy(G.,男生宿舍楼);strcpy(G.roduction,男生楼，女生止步);strcpy(G.,教学区);strcpy(G.roduction,包括主楼、辅楼还有D楼，旁边是扇形报告厅);strcpy(G.,篮球场);strcpy(G.roduction,打篮球的场地);strcpy(G.,书香园);strcpy(G.roduction,图书馆的背面，晨读的好地方哦);strcpy(G.,逸夫图书馆);strcpy(G.roduction,学习、自习的好地方);strcpy(G.,文体中心);strcpy(G.roduction,进行室内体育的地方);strcpy(G.,综合楼);strcpy(G.roduction,有办公室还有实验室);strcpy(G.,足球场);strcpy(G.roduction,跑步、踢球的地方，校运会也在这里举行);strcpy(G., 东大门);strcpy(G.roduction,学校最霸气的建筑物);/对有路的各景点之间的路径长度进行设置,没路的设置为无穷大 for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+)G.arcsij.adj=INFINITY;G.arcs13.adj=100;G.arcs12.adj=100;G.arcs15.adj=200;G.arcs24.adj=100;G.arcs23.adj=150;G.arcs35.adj=200;G.arcs38.adj=300;G.arcs45.adj=100;G.arcs47.adj=150;G.arcs56.adj=100;G.arcs67.adj=150;G.arcs68.adj=100;G.arcs79.adj=50;G.arcs89.adj=200;G.arcs813.adj=200;G.arcs910.adj=200;G.arcs911.adj=150;G.arcs912.adj=200;G.arcs1011.adj=100;G.arcs1112.adj=150;G.arcs1213.adj=150;/无向图的路径是相互的 for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsji.adj=G.arcsij.adj; return G;/InitGraph end/输出所有景点信息void Browser(MGraph *G)int v; printf(nnnnnnn);printf(编号景点名称 n);for(v=1;vvexnum;v+)printf(%-4d%-12s,G-vexsv.num,G-); switch(v+2)case 4:printf( 太原工业学院校园导游图n);break;case 5:printf( n);break;case 6:printf( 编号 实 现 的 功 能 n);break;case 7:printf( n);break; case 8:printf( 1 查 看 景 点 分 布 图 n);break;case 9:printf( n);break;case 10:printf( 2 查 找 两 景 点 间 最 短 距 离 n);break; case 11:printf( n);break;case 12:printf( 3 查 看 景 点 信 息 n);break;case 13:printf( n);break;case 14:printf( 4 退 出 系 统 n);break;case 15:printf( n);break;default:printf(n);break;printf(n);printf(输入你的选择：);void Floyd(MGraph *G)int v,u,i,w,k,j,flag=1,p141414,D1414;for(v=1;vvexnum;v+)for(w=1;wvexnum;w+)Dvw=G-arcsvw.adj;for(u=1;uvexnum;u+)pvwu=0;if(DvwINFINITY)pvwv=1;pvww=1;for(u=1;uvexnum;u+)for(v=1;vvexnum;v+)for(w=1;wvexnum;w+)if(Dvu+DuwDvw)Dvw=Dvu+Duw;for(i=1;ivexnum;i+)pvwi=pvui | puwi;while(flag)printf(请输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(kG-vexnum | jG-vexnum)printf(景点编号不存在!请重新输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(k=j)printf(出发点和目的地一样!请重新输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(k0 & kvexnum & j0 & jvexnum)flag=0;printf(n最短游览路线：%s,G-);if(kj)for(u=G-vexnum;u0;u-)if(pkju & k!=u & j!=u)printf(-%s,G-);if(kj)for(u=1;uvexnum;u+)if(pkju & k!=u & j!=u)printf(-%s,G-);printf(-%s,G-);printf( 总路线长%dmn,Dkj);/Floyd end/*/寻找要查询的景点，并输出该景点的信息void Search(MGraph *G)int k,flag=1;while(flag)printf(请输入要查询的景点编号:);scanf(%d,&k);if(kG-vexnum)printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&k);if(k0&kvexnum)flag=0;printf(nn);printf(编号景点名称 简介 n);printf(%-4d%-16s%-62sn,G-vexsk.num,G-,G-roduction);printf(n);/Search end/*int LocateVex(MGraph *G,char* v) int c=-1,i;for(i=1;ivexnum;i+)if(strcmp(v,G-)=0)c=i;break;return c;/*MGraph * CreatUDN(MGraph *G)/初始化图形，接受用户输入int i,j,k,w;char v120,v220;printf(请输入图的顶点数,弧数:);scanf(%d%d,&G-vexnum,&G-arcnum);printf(请输入景点的编号:、名称、简介:n);for(i=1;ivexnum;i+)printf(景点编号:);scanf(%d,&G-vexs-num);printf(景点名称:);scanf(%s,G-);printf(景点简介:);scanf(%s,G-vexs-introduction);for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)G-arcsij.adj=INFINITY;printf(请输入路径长度:n);for(k=1;karcnum;k+)printf(第%d条边:n,k+1);printf(景点对(x,y):);scanf(%s,v1);scanf(%s,v2);printf(路径长度:);scanf(%d,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i0 & j0)G-arcsij.adj=w;G-arcsji=G-arcsij; return G;/*void browse_view_distribute()/查看景点分布图，3printf(n);printf( n);printf( n); printf( n);printf( - - - - - - - - - - 高 速 公 路- - - - - - - - - - - - n); printf( n); printf( 13.东大门 n);printf( n);printf( n);printf( n);printf( 综合楼 综合楼 n);printf( 12.足球场 n);printf( n);printf( n);printf( n);printf( n);printf