校园导游咨询

课程设计论文

Course’s Thesis课程名称 数据结构

专 业 通信工程 班 级 0803班 学 生 蔡兵 学 号 01 设计题目 校园导游咨询

指导教师 孙玉霞老师 时间 2011年3月22日 年度 2011年 第二 学期

目录 一、课程目的 二、基本要求 三、实验内容及步骤 1、概要设计 2、详细设计 （1）建立模型（逻辑结构） （2）建立模块之间的关系（存储结构） （3）算法 四、源程序清单 五、测试结果 六、课程设计总结及心得体会 实验题目：校园导游咨询 一、课程目的 为用户提供路径咨询和景点查询，根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。 二、基本要求 （1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 附加要求：a、界面友好，函数功能要划分好 b、总体设计应画一流程图 c、程序要加必要的注释 d、要提供程序测试方案 三、实验内容及步骤 1、概要设计： 在设计这个校园导游系统前考虑到整个信息的结点和操作，可以通过邻接矩阵借助图的相关知识来完成。 按照要求分为三个模块，图的信息的初始化，图各个景点信息的查询和景点间的最短路径查询功能 void introduce() //用来查询各景点的相关信息 int shortestdistance() //用来查询任意两个景点之间的最短路径和经过的景点 void floyed() //用来计算任意两个景点之间的最短路径 void display(int i,int j) //用来显示任意景点之间的最短路径和经过的景点 /*包含头文件*/ #include /*定义符号常量*/ #define INT_MAX 10000 #define n 10 /*定义全局变量*/ int cost[n][n];/* 边的值*/ int shortest[n][n];/* 两点间的最短距离*/ int path[n][n];/* 经过的景点*/ 2、详细设计： （1）建立模型（逻辑结构：图） 1 7 7 2 8 1 13 5 1 1 2 1 2 1 3 2 4 1 5 2 9 2 1 6 （2）建立模块之间的关系（存储结构：邻接矩阵） （3）算法 这个程序的关键代码就利用Floyd算法求最短路径并将路径存放起来。 Floyd算法的算法思想：设矩阵cost用来存放带权无向图G的权值，即矩阵元素cost[i][j]中存放着序号为i的结点到序号为j的结点之间的权值，可以通过递推构造一个矩阵序列A0，A1，A2，…，AN来求每对结点之间的最短路径。其中，Ak[i][j]表示从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度。初始时有A0[i][j]=cost[i][j]。当已经求出Ak，要递推求解Ak+1时，可分为两种情况来考虑：一种清楚是该结点序号为k+1的结点，此时该路径长度与从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度相同；另一种情况是该路径经过结点序号k+1的结点，此时该路径可分为两段，一段是从结点Vi到结点Vk+1的最短路径，另一段是从结点Vk+1到结点Vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况的路径长度较小者，就是要求的从结点Vi到结点Vj的路径上所经过的结点序号不大于k+1的最短路径长度。 Floyd具体算法设计 void floyed() { int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { shortest[i][j]=cost[i][j]; path[i][j]=0; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; } } 四、源程序清单 #include #define INT_MAX 10000 #define n 10 int cost[n][n]; int shortest[n][n]; int path[n][n]; void introduce(); int shortestdistance(); void floyed(); void display(int i,int j); void main() { int i,j,q; char k; printf(\"\----------------欢迎来到湖北师范学院----------------\\n\\n\"); printf(\"\---按1进入校园导游指示系统，否则请再次输入---\\n\"); PR:printf(\"\ ---------------请输入你的选择----------------\\n\\"); scanf(\"%d\ if(q!=1) { printf(\"\-----------------输入错误，请再次输入---------\\n\"); goto PR; } else { for(i=0;i<=n;i++) for(j=0;j<=n;j++) cost[i][j]=INT_MAX; cost[1][2]=cost[2][1]=3; cost[2][3]=cost[3][2]=1; cost[3][4]=cost[4][3]=2; cost[4][5]=cost[5][4]=1; cost[5][6]=cost[6][5]=1; cost[3][6]=cost[6][3]=2; cost[1][4]=cost[4][1]=5; cost[1][7]=cost[7][1]=7; cost[4][7]=cost[7][4]=1; cost[7][5]=cost[5][7]=1; cost[7][8]=cost[8][7]=2; cost[8][9]=cost[9][8]=1; cost[5][9]=cost[9][5]=2; cost[8][5]=cost[5][8]=2; cost[8][10]=cost[10][8]=1; cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0; while(1) { printf(\"----------------欢迎使用校园导游系统!----------------\\n\"); printf(\" -----------------湖北师范学院--------------------\\n\"); printf(\"1.景点信息查询………请按 i (introduc)键\\n\"); printf(\"2.景点最短路径查询…请按 s (shortestdistance)键\\n\"); printf(\"3.退出系统……………请按 e (exit)键\\n\"); printf(\"学校景点列表:\\n\"); printf(\" 1:学校大门\\n\"); printf(\" 2:图书馆\\n\"); printf(\" 3:教育大楼\\n\"); printf(\" 4:科教大厦\\n\"); printf(\" 5:实验楼\\n\"); printf(\" 6:外语楼\\n\"); printf(\" 7:花坛\\n\"); printf(\" 8:篮球场\\n\"); printf(\" 9:足球场\\n\"); printf(\" 10:食堂\\n\"); printf(\"请选择服务:\"); scanf(\"\\n%c\ switch(k) { case 'i': printf(\"进入景点信息查询:\"); introduce(); break; case 's': printf(\"进入最短路径查询:\"); shortestdistance(); break; case 'e': exit(0); default: printf(\"输入信息错误！\\n请输入字母i或s或e.\\n\"); break; } } } } void introduce() { int a; printf(\"您想查询哪个景点的详细信息?请输入景点编号:\"); scanf(\"%d\ printf(\"\\n\"); switch(a) { case 1: printf(\"1:学校大门\\n\\n 学校的正门，气势宏伟。\\n\\n\");break; case 2: printf(\"2:图书馆\\n\\n 学校信息资源中心。\\n\\n\");break; case 3: printf(\"3:教育大楼\\n\\n 学生自学自修的天堂。\\n\\n\");break; case 4: printf(\"4:科教大厦\\n\\n 全校学生公共教学楼。\\n\\n\");break; case 5: printf(\"5:实验楼\\n\\n 计算机机房及各种实验设施。\\n\\n\");break; case 6: printf(\"6:外语楼\\n\\n 外国文化交流中心。\\n\\n\");break; case 7: printf(\"7:花坛\\n\\n 美丽校园的缩影。\\n\\n\");break; case 8: printf(\"8:篮球场\\n\\n 篮球健儿的摇篮。\\n\\n\");break; case 9: printf(\"9:足球场\\n\\n 校内最开阔的地方。\\n\\n\\n\");break; case 10: printf(\"10:食堂\\n\\n 学生就餐的地方 。\\n\\n\");break; default: printf(\"景点编号输入错误！请输入1->10的数字编号！\\n\\n\"); break; } } int shortestdistance() { int i,j; printf(\"请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):\"); scanf(\"%d,%d\ if(i>n||i<=0||j>n||j<0) { printf(\"输入信息错误！\\n\\n\"); printf(\" 请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):\\n\"); scanf(\"%d,%d\ } else { floyed(); display(i,j); } return 1; } void floyed() { int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { shortest[i][j]=cost[i][j]; path[i][j]=0; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; } } void display(int i,int j) { int a,b; a=i; b=j; printf(\"您要查询的两景点间最短路径是:\\n\\n\"); if(shortest[i][j]!=INT_MAX) { if(i%d)最短距离是:%d米\\n\\n\ } else { printf(\"%d\ while(path[i][j]!=0) { printf(\"->%d\ if(i%d\ printf(\"\\n\\n\"); printf(\"(%d->%d)最短距离是:%5d米\\n\\n\ } } else printf(\"输入错误！不存在此路！\\n\\n\"); printf(\"\\n\"); } 五、测试结果 校园导游的主页面 输入1时进入校园导游系统 查询景点5的相关信息 查询景点1和6之间的最短路径和经过的景点 六、课程设计总结及心得体会 这次的课程设计题目是校园导游，总的来说还是比较简单的，只运用了Floyd算法和操作。程序设计也比较简单，运行结果正确，能够实现为来访客人提供校园任意景点的相关信息。 通过这次课程设计试验，我更加体会到了程序设计的三要素（即逻辑结构、存储结构和算法）的重要性，也让我加深了对三要素的理解。校园导游咨询这个程序设计充分体现了程序设计的三要素。 不过也通过这次课程设计，让我明白现实生活跟程序之间联系，同时也让我明白了数据结构这门课程的重要性，我以后会继续努力学习这门课程。