资源描述
姓 名： 班 级： 学 号： 指导教师： 2019年12月第 11 页目录1、需求分析11.1 系统简介11.2 系统功能模块介绍12、概要设计22.1 系统功能结构图22.2 系统流程图22.3 主要函数概要设计32.3.1 主函数概要设计32.3.2 初始化图函数InitGraph()42.3.4 查询景点信息函数设计SearchGraph()42.3.5 显示图中信息函数设计ShowGraph()42.3.6 弗洛伊德算法函数设计Floyd()53、详细设计53.1 主函数详细设计53.2初始化图函数详细设计InitGraph()63.3查询景点信息函数详细设计SearchGraph()73.4 弗洛伊德算法函数详细设计Floyd()84、调试分析94.1 显示主界面函数测试94.2 查找两景点间最短路径测试104.3 查看景点信息测试115.课程设计总结126、附录131、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于数据结构中图的相关算法开发了“江西农业大学校园咨询系统”。开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。本系统界面友好，提示信息充分，在实际使用过程中运行良好。1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称和其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方；2、查询景点信息：用户在选择此功能模块后，按照屏幕上方提示的景点名称和其对应的编号，要求用户输入想要查询的景点的编号，回车后系统将在已存储的景点中进行匹配，若该景点信息尚未存储则将提示错误；若找到对应信息则系统将输出景点信息，显示于幕上方；3、退出系统：用户在使用完本系统后，选择此功能模块，系统提示“欢迎再次使用”后，按任意键系统将自动退出。2、概要设计2.1 系统功能结构图2.2 系统流程图开始创建无向图写入信息至无向图中Case 1Case 2Case 3查询路径查询景点息TTFFTendF退出系统2.3 主要函数概要设计2.3.1 主函数概要设计主函数首先是调用初始化图函数InitGraph()函数创建一个图，而后调用显示主界面函数显示一个可视化主界面，内容包含本系统LOGO以和景点信息和操作编号的提示信息。之后，当用户成功输入操作编号后，使用一个switch()函数，判断用户所需操作，匹配成功后，调用相关函数实现用户所需功能。2.3.2 初始化图函数InitGraph()InitGraph()函数首先使用MyGraph结构体声明一个用于存储图中信息的结构体，而后定义结构体中的景点数量以和路径数量，然后使用循环为景点信息和路径长度赋值，其中赋值景点信息时使用strcpy()函数将字符串复制给G.siteArrayi.siteName以和G.siteArrayi.siteInfo两个数组。2.3.3 显示主界面函数设计MainGraph()MainGraph()函数主要用于显示主界面，函数中设计了本系统LOGO,同时，界面还提示了景点名称和其对应编号。主界面下方以列表方式提示用户系统可进行的操作和其对应编号，最后提示用户进行输入。2.3.4 查询景点信息函数设计SearchGraph()该函数首先定义了一个变量k(用于接收用户输入的查询编号)和一个标记位flag(初始值设为1)，而后使用while()循环，判断条件为flag=1,当输入编号不合法时提示错误，当输入合法时标记位flag置为0，此时跳出循环，调用MyGraph结构体对应编号的景点信息，以列表方式输出。2.3.5 显示图中信息函数设计ShowGraph() ShowGraph()函数主要功能为用循环将存储于图中的景点信息以列表方式输出，方便用户对应着进行输入，同时提示用户进行输入。2.3.6 弗洛伊德算法函数设计Floyd()本算法在设计时参考了数据结构C语言版一书中有关Floyd算法的介绍，同时借鉴了如今网上流行的设计方式。之所以选择本算法来实现计算最短路径，原因在于本算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。但是，本算法缺点在于时间复杂度过高，不适合用于计算大量数据。Floyd算法首先将两景点间路径长度数据存储于数组 Dvw中，而后使用一个三维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。以上部分完成后，当用于标记输入数据是否合法的flag=1时，输出错误信息，提示用户重新输入，当输入数据合法时，输出以上程序得到结果。3、详细设计3.1 主函数详细设计#define InfiniteNum 10000 /定义一个无穷大数#define MaxInfoNum 100 /定义景点数据最大容量#include#include#include#includeMyGraph.h /调用头文件void main(void) MGraph g; /创 建 图int i;g = InitGraph(); /初始化校园地图MainGraph(&g); /调用显示主界面函数scanf(%d,&i);while(i!=3)switch(i)case 1:ShowGraph(&g);Floyd(&g);MainGraph(&g);break; case 2:ShowGraph(&g);SearchGraph(&g);MainGraph(&g);break;case 3:exit(0);break;default:break;scanf(%d,&i);printf(欢迎下次继续使用 !nn);3.2初始化图函数详细设计InitGraph()MGraph InitGraph(void) /初始化图中的信息MGraph G;int i,j;G.siteNumber = 6; /景点数量G.pathNumber = 8; /路 径 数量for(i=1;i=G.siteNumber;i+)G.siteArrayi.siteIdentifier = i; /对景点进行对应编号strcpy(G.siteArray1.siteName,一教);strcpy(G.siteArray1.siteInfo,最有历史的教学楼); strcpy(G.siteArray2.siteName,软件学院); strcpy(G.siteArray2.siteInfo,规模庞大，师资雄厚，全校第二大院); strcpy(G.siteArray3.siteName,老图书馆); strcpy(G.siteArray3.siteInfo,说实话，太破了！); strcpy(G.siteArray4.siteName,校门); strcpy(G.siteArray4.siteInfo,有点小家子气，规模太小); strcpy(G.siteArray5.siteName,新图书馆); strcpy(G.siteArray5.siteInfo,邵逸夫先生捐赠的,设施较为完备,最常去的地方); strcpy(G.siteArray6.siteName,南区食堂); strcpy(G.siteArray6.siteInfo,价格尚算公道，但卫生状况较为堪忧，已经吃出好几次头发了); for(i = 1;i=G.siteNumber;i+) /使用循环对路径进行赋值，对于没有 直 接 路 径 的 ，赋值为无穷大 for(j = 1;j=G.siteNumber;j+)G.pathArrayij.path = InfiniteNum;G.pathArray12.path = 200;G.pathArray13.path = 100;G.pathArray14.path = 400;G.pathArray24.path = 300;G.pathArray45.path = 100;G.pathArray46.path = 500;G.pathArray56.path = 500; for(i = 1;i=G.siteNumber;i+) /所构造的图为无向图，故相反方向路径相同for(j = 1;j=G.siteNumber;j+)G.pathArrayji.path = G.pathArrayij.path; return G;3.3查询景点信息函数详细设计SearchGraph()void SearchGraph(MGraph *G) /用于查询景点信息 ，以列表方式输出int k,flag=1;while(flag)printf( 请输入要查询的景点编号:);scanf(%d,&k);if(kG-siteNumber) /输入景点编号不合法时提示错误printf( 景点编号不存在!请重新输入景点编号:);scanf(%d,&k);if(k0&ksiteNumber) / 输入合法时将 falg 置为 0flag=0;printf( n);printf( 编号 景点名称 简介 n);printf( %-4d %-16s %-62s n,G-siteArrayk.siteIdentifier,G-siteArrayk.siteName,G-siteArrayk.siteInfo); /输出景点信息3.4 弗洛伊德算法函数详细设计Floyd()void Floyd(MGraph *G) /使用弗洛伊德算法2求出最短路径int v,u,i,w,k,j; int flag = 1; /用于标记输入数据是否正确 ， 若输入数据符合要求 ，则将 flag 置为0 int p777,D77;for(v = 1;v siteNumber;v+)for(w = 1;wsiteNumber;w+)Dvw = G-pathArrayvw.path; /将路径数据存放至数组 Dvw 中for(u = 1;usiteNumber;u+)pvwu=0; /该三维数组用于存放两景点之间是否有直接路径，若有则记为1，无则记为0if(Dvw InfiniteNum)pvwv = 1;pvww = 1;for(u = 1;usiteNumber;u+)for(v = 1;vsiteNumber;v+)for(w = 1;wsiteNumber;w+)if(Dvu + DuwDvw) / 如果两点之间直接路径大于简介路径 ， 则将该两点之间路径置为间接路径Dvw = Dvu+Duw;for(i = 1;isiteNumber;i+)pvwi = pvui|puwi; /获取两点之间路径所经过的景点编号while(flag)printf( 请输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(kG-siteNumber|jG-siteNumber)printf( 景点编号不存在!请重新输入:);scanf(%dn%d,&k,&j);if(k=j)printf( 出发点和目的地一样!请重新输入:);scanf(%dn%d,&k,&j);if(k0&ksiteNumber&j0&jsiteNumber)flag=0; /输入的数据合法，故将 flag = 0printf(n最短游览路线：%s,G-siteArrayk.siteName);if(kj)for(u = G-siteNumber;u0;u-)if(pkju & k!=u & j!=u)printf(-%s,G-siteArrayu.siteName);if(kj)for(u=1;usiteNumber;u+)if(pkju & k!=u & j!=u)printf(-%s,G-siteArrayu.siteName);printf(-%s,G-siteArrayj.siteName);printf( 总路线长%dmn,Dkj);4、调试分析4.1 显示主界面函数测试显示主界面函数必须实现提示景点名称和其对应编号，主界面下方以列表方式提示用户系统可进行的操作和其对应编号，最后提示用户进行输入。经测试结果如下：4.2 查找两景点间最短路径测试本功能模块要求在按照景点信息列表中提示的信息用户输入起点编号和终点标号后输出最短路径，经测试后该功能能够实现，没有何错误。测试结果如下图：输入起点和终点：输出最短路径：4.3 查看景点信息测试本功能模块要求在用户输入景点编号后，系统和已存储的景点信息进行配对，如果景点不存在，则提示错误，若景点存在则输出景点信息，经测试，达到了预期效果，且容错处理正常运行。测试结果如下：5.课程设计总结经过这次课程设计，我对程序中算法的概念理解的更加透彻。算法是程序中必不可少的部分，它是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。同时，在选择算法时必须考虑算法的时间复杂度和空间复杂度，这样才能让程序正常，高效的运行。在系统设计时也碰到了很多问题，比如在设计InitGraph()函数时，首先我想到的是使用数组来保存信息，但发现这种设计无法方便的让程序中各个独立算法访问存储的景点信息，编写代码时十分复杂，后来，在出查阅相关书籍和阅读了网上其它相关算法后，我选择了使用结构体数组来保存信息，这种方式顺利地将信息保存到了图中，同时其它函数模块也可以方便的访问这部分信息，达到了我想要实现的功能。数据结构在计算机科学中是一门综合性的专业基础课.数据结构的研究不仅涉和到计算机的硬件(特别是编码理论、存储装置和存取方法等)的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉和到数据元素在存储器中的分配问题.在研究信息检索时也必须考虑如何组织数据,以便查找和存取数据元素更为方面.因此,可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程.在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统和其它系统程序和大型应用程序的重要基础。6、附录源程序清单：/以下保存在头文件 “MyGraph.h” 中typedef struct /定义用于存放权值的结构体int path; /路径长度ArCell,AdjMatrixMaxInfoNumMaxInfoNum;typedef structchar siteName30; / 用于存放景点名称int siteIdentifier; /用于存放景点编号char siteInfo200; /用于存放景点信息infoType;typedef structinfoType siteArrayMaxInfoNum; / 景点数组 ,用于存放景点名和景点信息AdjMatrix pathArray; / 路径数组int siteNumber; / 景点数量 int pathNumber; / 路径总数量MGraph;MGraph InitGraph(void) /初始化图中的信息MGraph G;int i,j;G.siteNumber = 6; /景点数量G.pathNumber = 8; /路 径 数量for(i=1;i=G.siteNumber;i+)G.siteArrayi.siteIdentifier = i; /对景点进行对应编号strcpy(G.siteArray1.siteName,一教);strcpy(G.siteArray1.siteInfo,最有历史的教学楼); strcpy(G.siteArray2.siteName,软件学院); strcpy(G.siteArray2.siteInfo,规模庞大，师资雄厚，全校第二大院); strcpy(G.siteArray3.siteName,老图书馆); strcpy(G.siteArray3.siteInfo,说实话，太破了！); strcpy(G.siteArray4.siteName,校门); strcpy(G.siteArray4.siteInfo,有点小家子气，规模太小); strcpy(G.siteArray5.siteName,新图书馆); strcpy(G.siteArray5.siteInfo,邵逸夫先生捐赠的,设施较为完备,最常去的地方); strcpy(G.siteArray6.siteName,南区食堂); strcpy(G.siteArray6.siteInfo,价格尚算公道，但卫生状况较为堪忧，已经吃出好几次头发了); for(i = 1;i=G.siteNumber;i+) /使用循环对路径进行赋值，对于没有 直 接 路 径 的 ，赋值为无穷大 for(j = 1;j=G.siteNumber;j+)G.pathArrayIj.path = Infinite;G.pathArray12.path = 200;G.pathArray13.path = 100;G.pathArray14.path = 400;G.pathArray24.path = 300;G.pathArray45.path = 100;G.pathArray46.path = 500;G.pathArray56.path = 500; for(I = 1;i=G.siteNumber;i+) /所构造的图为无向图，故相反方向路径相同for(j = 1;j=G.siteNumber;j+)G.pathArrayji.path = G.pathArrayij.path; return G;void Floyd(MGraph *G) /使用弗洛伊德算法2求出最短路径int v,u,i,w,k,j; int flag = 1; /用于标记输入数据是否正确 ， 若输入数据符合要求 ，则将 flag 置为0 int p777,D77;for(v = 1;v siteNumber;v+)for(w = 1;wsiteNumber;w+)Dvw = G-pathArrayvw.path; /将路径数据存放至数组 Dvw 中for(u = 1;usiteNumber;u+)pvwu=0; /该三维数组用于存放两景点之间是否有直接路径，若有则记为1，无则记为0if(Dvw InfiniteNum)pvwv = 1;pvww = 1;for(u = 1;usiteNumber;u+)for(v = 1;vsiteNumber;v+)for(w = 1;wsiteNumber;w+)if(Dvu + DuwDvw) / 如果两点之间直接路径大于简介路径 ， 则将该两点之间路径置为间接路径Dvw = Dvu+Duw;for(i = 1;isiteNumber;i+)pvwi = pvui|puwi; /获取两点之间路径所经过的景点编号while(flag)printf( 请输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(kG-siteNumber|jG-siteNumber)printf( 景点编号不存在!请重新输入:);scanf(%dn%d,&k,&j);if(k=j)printf( 出发点和目的地一样!请重新输入:);scanf(%dn%d,&k,&j);if(k0&ksiteNumber&j0&jsiteNumber)flag=0; /输入的数据合法，故将 flag = 0printf(n最短游览路线：%s,G-siteArrayk.siteName);if(kj)for(u = G-siteNumber;u0;u-)if(pkju & k!=u & j!=u)printf(-%s,G-siteArrayu.siteName);if(kj)for(u=1;usiteNumber;u+)if(pkju & k!=u & j!=u)printf(-%s,G-siteArrayu.siteName);printf(-%s,G-siteArrayj.siteName);printf( 总路线长%dmn,Dkj);void MainGraph(MGraph *G) /调用此函数可实现输出主界面功能int i;printf(*江西农业大学校园导游系统 *n);printf(n);printf( -输入命令后最短路径或景点信息显示于屏幕上方- n);printf(n); printf( 编号 景点名称 n);for(i = 1;i siteNumber; i+ ) printf( %-4d % -12s n,G-siteArrayi.siteIdentifier,G-siteArrayi.siteName); printf(n);printf( n); printf( 编号 功 能 n);printf( n);printf( 1 查 找 两 景 点 间 最 短 路径 n); printf( n); printf( 2 查 看 景 点 信 息 n);printf( n); printf( 3 退 出 系 统 n);printf( n); printf( 请输入您的操作编号：);void SearchGraph(MGraph *G) /用于查询景点信息 ，以列表方式输出int k,flag=1;while(flag)printf( 请输入要查询的景点编号:);scanf(%d,&k);if(kG-siteNumber) /输入景点编号不合法时提示错误printf( 景点编号不存在!请重新输入景点编号:);scanf(%d,&k);if(k0&ksiteNumber) / 输入合法时将 falg 置为 0flag=0;printf( n);printf( 编号 景点名称 简介 n);printf( %-4d %-16s %-62s n,G-siteArrayk.siteIdentifier,G-siteArrayk.siteName,G-siteArrayk.siteInfo); /输出景点信息void ShowGraph(MGraph *G) / 将图中的信息打印出来int i;printf( 编号 景点名称 n);for(i = 1;isiteNumber;i+)printf( %-4d %-12s n,G-siteArrayi.siteIdentifier,G-siteArrayi.siteName);/以下为主函数：#define InfiniteNum 10000 /定义一个无穷大数#define MaxInfoNum 100 /定义景点数据最大容量#include#include#include#includeMyGraph.h /调用头文件void main(void) MGraph g; /创 建 图int i;g = InitGraph(); /初始化校园地图MainGraph(&g); /调用显示主界面函数scanf(%d,&i);while(i!=3)switch(i)case 1:ShowGraph(&g);Floyd(&g);MainGraph(&g);break;case 2:ShowGraph(&g);SearchGraph(&g);MainGraph(&g);break;case 3:exit(0);break;default:break;scanf(%d,&i);printf(欢迎下次继续使用 !nn);
展开阅读全文