下载文档原格式
重庆科技学院课程设计报告院（系）:_电气与信息工程学院专业班级:计科普0902学生姓名:周杨学号: 2009441622设计地点（单位）____计算机基础自主学习中心I306___设计题目:_________校园导游咨询____________________ 完成日期： 2011 年 1 月 14 日指导教师评语: _______________________________________ ___________________________________________________________________________ ___________________________________________________________________________ ___________________________________________________ __________ _成绩（五级记分制）:______ __________指导教师（签字）:________ ________重庆科技学院课程设计任务书设计题目：校园导游咨询教研室主任：指导教师：向毅、陈刘奎、熊茜2010年 12 月 20日摘要现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。
本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。
数据结构试验报告校园导游《数据结构》课程设计报告课程名称：《数据结构课程设计》；课程设计题⽬：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：⼤⼆；学号：10054220；指导教师：王⽴波；2011年12⽉17⽇1 课程设计的⽬的 (x)2 需求分析 (x)3 课程设计报告内容 (x)1、概要设计 (x)2、详细设计 (x)3、调试分析 (x)4、⽤户⼿册 (x)5、测试结果 (x)6、程序清单 (x)4 ⼩结 (x)5 参考⽂献 (x)1.课程设计的⽬的：（1）熟练运⽤C++编写程序；（2）会⽤Floyd算法查找最短路径；2.需求分析：1.题⽬：【校园导游咨询】[问题描述]（1）设计你的学校的校园平⾯图，所含景点不少于10个。
以图中顶点表⽰学校各景点，存放景点名称、代号、简介等信息；以边表⽰路径，存放路径长度等相关信息。
（2）为来访客⼈提供图中任意景点的问路查询，即查询任意两个景点之间的⼀条最短的简单路径。
（3）为来访客⼈提供图中任意景点相关信息的查询。
[测试数据]由读者根据实际情况指定。
2.任务：通过此程序可实现以下功能：（1）⽤⼀维数组存放景点信息，⼆维数组存放景点间的距离，最短距离，最短路径；（2）Floyd算法计算最短距离和路径；（3）根据景点序号查询景点的⼀系列信息，及两景点间的最短路径和最短距离。
3.测试数据:查询类型：I（表⽰查询景点信息）；景点编号：3；查询类型：D（表⽰查询景点间的最短路径和最短距离）；景点编号：1 9；3. 课程设计报告内容：1. 概要设计：（1）⾸先我画了学校主要⼏个景点的分布图以及⾃⼰定的⼀些距离，图如下：（2）接着我定义了⼀个顶点结构体，定义如下：struct Date{int num; //景点编号char name[50]; //景点名称char introduce[100]; //景点介绍};（3）然后我定义了⼀个类，定义如下：class Travel{private:Date date[15];int distance[15][15];int Path[15][15];int ShortestDistance[15][15];void Floyd();public:Travel();~Travel(){}void Introduce(int);void Scanf();void ShortDistance(int,int);};（4）基本操作：void Floyd(); //Floyd算法，计算最短路径和最短距离Travel(); //构造函数~Travel(){} //析构函数void Introduce(int); //介绍景点函数void Scanf(); //外部输⼊函数void ShortDistance(int,int); //最短距离计算函数本程序分为2个模块：Int main(){初始化；Void Scanf();}函数调⽤关系基本结构图如下所⽰：2. 详细设计：（1）主函数初始化变量；（2）调⽤外部接⼝函数Scanf()；（3）输⼊查询类型，如果为“I”，调⽤景点介绍函数，如果为“D”，调⽤最短距离和路径函数。
《数据结构与算法》实验报告一、需求分析【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】(1)设计你所在学校的校园平面图，所含景点不少于10个。
以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。
【测试数据】由读者根据实际情况指定。
【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。
顶点和边均含有相关信息。
【选作内容】(6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。
二、概要设计1）抽象数据类型定义描述#include<iostream>using namespace std;const int MaxSize=18;const int INFINITY=65535;//最大值无穷class direction;template <class T> class MGraph;template <class T>class VertexNode//定义景点结点，存储景点信息{friend class MGraph<T>;public:int vex;//景点名称T vexname;//景点名称T vexinf;//景点信息direction dir;//存放景点方位信息的direction类的dir。
};class direction{public:int ln;//存放在方向图中的横坐标，表示东西int col;//存放在方向图中的纵坐标，表示南北};template <class T>class MGraph//定义无向图的邻接矩阵{public:MGraph();//构造函数，初始化具有n个顶点的图void printvexname();//显示所有景点及景点代号void printvexinf(int i);//显示代号为i景点的名称及信息void printroad(int i,int j);//显示景点i~j的最短路径方案信息void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南200m”VertexNode<T> adjlist[MaxSize]; //存放景点全部信息的景点类数组int vertexNum,arcNum; //图的顶点数和边数void Root(int p,int q);//递归寻找pq间的最短路径int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度int Line[MaxSize];//Line存放路径int kkk;//在floyed算法中，做Line[]数组的标记private:T vertex[MaxSize]; //存放图中顶点的数组int arc[MaxSize][MaxSize];//存放图中边的数组};2）功能模块设计（如主程序模块设计）int funcchoice()//系统功能选择页面{int choice;cout<<"=============================================================="<<endl;cout<<" 欢迎进入校园导游咨询平台"<<endl;cout<<" 1--显示校园所有景点信息"<<endl;cout<<" 2--查询校园景点信息"<<endl;cout<<" 3--问路查询系统"<<endl;cout<<" 4--退出导游资讯平台"<<endl;cout<<"=============================================================="<<endl;cout<<"请输入要选择的功能号：";cin>>choice;return choice;}3）模块层次调用关系图三、详细设计//程序的头文件#include<iostream>#include<iomanip>#include"guide.h"using namespace std;template <class T>MGraph<T>::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，d[]为景点方位信息的横坐标，e[]为景点方位信息的纵坐标，s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][]{i nt s[]={0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};i nt a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};c har* b[]={"南门","实验楼","南图","大活","睿思楼","大礼堂","南4教","知行楼","国交楼","南3教","南2教","南1教","北图","北3教","北4教","北2教","北1教","北门"};c har* c[]={"南校区正门","物理实验楼","南校区图书馆","大学生活动中心","教师办公楼、医务室及留学生公寓","大礼堂，用于举办各种文艺演出","南校区第4教学楼","实习基地，计算机房等","国际交流中心，教职工餐厅","南校区第3教学楼","南校区第2教学楼","南校区第1教学楼","北校区图书馆","北校区第3教学楼","北校区第4教学楼","北校区第2教学楼","北校区第1教学楼","北校区正门"};i nt d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};i nt e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};i nt i,j;v ertexNum=18;a rcNum=30;f or(i=0;i<vertexNum;i++){adjlist[i].vex=a[i];adjlist[i].vexname=b[i];adjlist[i].vexinf=c[i];adjlist[i].dir.ln=d[i];adjlist[i].dir.col=e[i];}f or (i=0; i<vertexNum; i++)//初始化邻接矩阵for (j=0; j<vertexNum; j++)arc[i][j]=arc[j][i]=s[(i*(i+1))/2+j]; //根据s[]的对称性，将一维数组中的数据赋给二维数组arc[][]}template<class T>void MGraph<T>::printvexname(){i nt i;f or(i=0;i<vertexNum;i++)cout<<adjlist[i].vex<<" "<<adjlist[i].vexname<<endl;;}template<class T>void MGraph<T>::printvexinf(int i){c out<<i<<" "<<adjlist[i].vexname<<":"<<adjlist[i].vexinf<<endl;}template<class T>void MGraph<T>::printdir(int i,int j){i nt dx,nb;//临时存放i与j之间的南北东西关系 j在i的哪边？？d x=adjlist[j].dir.col-adjlist[i].dir.col;n b=adjlist[j].dir.ln-adjlist[i].dir.ln;i f(dx>0)//即j在i的东边cout<<"向东"<<dx*100<<"m，";e lsecout<<"向西"<<dx*(0-100)<<"m，";i f(nb>0)//即j在i的南边cout<<"向南"<<nb*100<<"m";e lsecout<<"向北"<<nb*(0-100)<<"m";}template<class T>void MGraph<T>::Root(int p,int q){i f (Path[p][q]>0){Root(p,Path[p][q]);Root(Path[p][q],q);}e lse{Line[kkk]=q;kkk++;}}template<class T>void MGraph<T>::printroad(int i,int j){i nt p,q,m,k,item1,item2;f or(p=0;p<vertexNum;p++)for(q=0;q<vertexNum;q++)Dist[p][q]=arc[p][q];//邻接矩阵赋值f or(k=0;k<vertexNum;k++)for(p=0;p<vertexNum;p++)if (Dist[p][k]>0)for(q=0;q<vertexNum;q++)if (Dist[k][q]>0)if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}c out<<"\n=====================================================\n";c out<<"从"<<adjlist[i].vexname<<"到"<<adjlist[j].vexname<<"的最短路径为："<<endl;c out<<adjlist[i].vexname;k kk=2;R oot(i,j);i tem2=Line[2];c out<<"-->";p rintdir(i,item2);c out<<"-->"<<adjlist[item2].vexname;f or(m=3;m<=kkk-1;m++){item1=Line[m];cout<<"-->";printdir(item1-1,item1);cout<<"-->"<<adjlist[item1].vexname;}c out<<endl;c out<<"\n=====================================================\n";}========================以下为main.cpp文件中主函数的实现========================== #include<iostream>#include"guide.cpp"using namespace std;int funcchoice()//系统功能选择页面{i nt choice;c out<<"=============================================================="<<endl;c out<<" 欢迎进入校园导游咨询平台"<<endl;c out<<" 1--显示校园所有景点信息"<<endl;c out<<" 2--查询校园景点信息"<<endl;c out<<" 3--问路查询系统"<<endl;c out<<" 4--退出导游资讯平台"<<endl;c out<<"=============================================================="<<endl;c out<<"请输入要选择的功能号：";c in>>choice;r eturn choice;}void main(){M Graph<char*> mg;i nt funcchoice();i nt fc;w hile(1){fc=funcchoice();if(fc==1){int i;for(i=0;i<mg.vertexNum;i++)mg.printvexinf(i);}else if(fc==2){int i;mg.printvexname();cout<<endl<<"请输入所要查询景点代号：";cin>>i;mg.printvexinf(i);}else if(fc==3){int i,j;mg.printvexname();cout<<"请输入两景点代号（我们将把最短路线反馈予您）：";cin>>i>>j;mg.printroad(i,j);}else if(fc==4)break;elsecout<<"输入有误，请重新输入！"<<endl;}}if调试分析遇到的问题及解决的办法：在调试过程中，最常见到的问题有以下几种：1、忘记调用函数类模块template<class T>，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错误。
姓名：班级：学号：指导教师：2012年12月目录1、需求分析 (1)1.1 系统简介 (1)1.2 系统功能模块介绍 (1)2、概要设计 (1)2.1 系统功能结构图 (1)2.2 系统流程图 (2)2.3 主要函数概要设计 (3)2.3.1 主函数概要设计 (3)2.3.2 初始化图函数InitGraph() (3)2.3.4 查询景点信息函数设计SearchGraph() (4)2.3.5 显示图中信息函数设计ShowGraph() (4)2.3.6 弗洛伊德算法函数设计Floyd() (4)3、详细设计 (4)3.1 主函数详细设计 (4)3.2初始化图函数详细设计InitGraph() (5)3.3查询景点信息函数详细设计SearchGraph() (6)3.4 弗洛伊德算法函数详细设计Floyd() (7)4、调试分析 (8)4.1 显示主界面函数测试 (8)4.2 查找两景点间最短路径测试 (9)4.3 查看景点信息测试 (10)5.课程设计总结 (11)6、附录 (12)1、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。
考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。
开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。
本系统界面友好，提示信息充分，在实际使用过程中运行良好。
1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。
一、设计目的与内容1．设计目的设计一个校园导游程序，为来访的客人提供各种信息查询服务。
2．设计内容1> 设计学校的校园平面图，所含13个景点，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
2> 为来访客人提供图中任意景点相关信息的查询。
3> 为来访客人提供景点的问路查询，即已知一个某紫薇.ylbqhm.景点，查询到某景点之间的一条最短路径及长度。
4> 退出导游程序。
二、算法的基本思想1．使用菜单页，选择不同的功能（景点信息查询、求最短路径、最短路径距离、退出程序等），进行相应的操作；2．采用数组作为数据的存储结构，存储检索出的路径、最短距离等；3．利用short函数运算，求两地间的距离，并输出其路径；4．主程序有掌控函数调用，选择功能模块执行，在程序运行工程中可以反复操作。
算法的思路是三、需求分析1．本系统是把校园平面图抽象成一个无向网，取校园中 13 个代表性景点作为图的顶点，存放顶点名称、代号、简介等有关信息、并以边表示路径，两景点间的距离作为边的权值。
以二维数组的数据结构存储构建无向图，cost[i][j];当i=j及i点与j点无直接连通时，其值为无穷大，定义一个很大的整数Init_Length代替无穷大。
当i与j点连接时，其值为两点间的权值即两点间距离。
2．本程序的目的是为用户提供路径咨询和景点查询。
根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。
1> 查询景点信息将相应景点信息存入函数print中，依据需要调用读取该函数，并显示在屏幕上。
2> 两点间最短路径利用shortestdistance函数逐级循环，查训两景点间所有路径距离，将最短路径距离存入D[v]中；并将所查得的景点存储在二维数组path[i][j]中；执行输出命令输出最短路径及距离。
3> 执行exit（0）；函数跳入退出界面执行退出操作。
西安邮电大学（计算机学院）数据结构课程设计报告题目：校园导游系统专业名称：班级：学生姓名：学号（8位）：指导教师：设计起止时间:一. 设计目的1.数据结构课程设计是让学生综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发2.通过课程设计，使学生通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。
3.学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。
二. 设计内容1.完成校园导游咨询系统。
2.校园平面图（景点、路径等信息）3.利用深度优先和广度优先搜索搜索所有景点4.查询图中任意景点的相关信息5.问路信息（查询任意两个景点之间的一条最短的简单路径，任意两景点之间的所有路径）校园图的关节点、多个景点的最佳访问路线6.校园导游图的界面仿真。
7.添加删除道路信息。
三．概要设计1．功能模块图；选择显示标识信息2．各个模块详细的功能描述。
1.登录模块进入后可添加删除道路信息。
2.路线选择模块选择路线，在右侧窗口显示最短路径3.其他查询景点信息，查看深度优先遍历查看广度优先遍历四．详细设计*重点设计及编码//结点function Node(vexdata){this.vexdata=vexdata;this.node=[];this.weight=[];}//类定义function AdjList(vexnum,arr){this.vexnum=vexnum;this.arcnum=0;this.vertex=[];=[];//名称r=[];//信息this.flag=[];//标记this.arr=[];//存储路径this.ar=[];//存储路径2for(var i=0;i<this.vexnum;i++){this.vertex[i]=new Node(arr[i]);this.flag.push(0);}//增加结点this.addarc=addarc;//增加边this.addvex=addvex;//深度优先搜索this.dfs=dfs;this.edfs=edfs;//广度优先搜索this.guangdu=guangdu;this.guang=guang;//输出存储结构this.printf=printf;//求最短路径this.getpath=getpath;//输出景点信息函数this.printinfor=printinfor;}function addarc(a1,a2,weight){this.vertex[a1].node.push(a2);this.vertex[a1].weight.push(weight);this.vertex[a2].node.push(a1);this.vertex[a2].weight.push(weight);this.arcnum++;}function addvex(v){var temp=new Node(v);this.vertex.push(temp);this.vexnum++;}function edfs(flag,v,g,arr){arr.push(v);flag[v]=1;for(var i=0;i<g.vertex[v].node.length;i++){if(1!=flag[g.vertex[v].node[i]]){edfs(flag,g.vertex[v].node[i],g,arr);}}}function dfs(){var temp=parseInt(document.getElementById('last').value);this.arr=[];for(var i=0;i<this.vexnum;i++)this.flag[i]=0;edfs(this.flag,temp,this,this.arr);for(var i=0;i<this.vexnum;i++){if(this.flag[i]!=1) edfs(this.flag,i,this,this.arr);}var showpath="<b>深度遍历路线：</b>";for(var i=0;i<this.arr.length;i++){showpath+="->";showpath+=[this.arr[i]];}document.getElementById('footer').innerHTML=showpath; }function guangdu(temp,g){var v,k,w=temp;var que=[];que.push(w);g.flag[w]=1;while(que.length!=0){w=que[0];g.ar.push(que[0]);que.splice(0,1);k=0;v=parseInt(g.vertex[w].node[k++])while(k<g.vertex[w].node.length){if(g.flag[v]!=1){g.flag[v]=1;que.push(v);}v=parseInt(g.vertex[w].node[k++]);}}}function guang(){var temp=parseInt(document.getElementById('last').value);this.ar=[];for(var i=0;i<this.vexnum;i++)this.flag[i]=0;guangdu(temp,this);for(var i=0;i<this.vexnum;i++)if(this.flag[i]!=1)guangdu(i,this);var showpath="<b>广度遍历路线：</b>";for(var i=0;i<this.ar.length;i++){showpath+="->";showpath+=[this.ar[i]];}document.getElementById('footer').innerHTML=showpath; }function printf(){for(var i=0;i<this.vexnum;i++){document.write('<br>'+this.vertex[i].vexdata+" :");for(var j=0;j<this.vertex[i].node.length;j++)document.write('->'+this.vertex[i].node[j]+":"+this.vertex[i].weight[j]);}}function getpath(/*start,end*/){var start=parseInt(document.getElementById('first').value);var end=parseInt(document.getElementById('last').value);var mindist;var k;var a=[];var path=new Array(this.vexnum);//初始化for(var i=0;i<this.vexnum;i++){document.getElementById('b'+i).style.color='#000';}for(var i=0;i<this.vexnum;i++){path[i]=[];}for(var i=0;i<this.vexnum;i++){a[i]=10000;path[i][0]=0;}path[start][0]=1;for(var i=0;i<this.vertex[start].node.length;i++){a[this.vertex[start].node[i]]=this.vertex[start].weight[i];path[this.vertex[start].node[i]].push(start);}//找各条最短路径for(var i=1;i<this.vexnum;i++){mindist=10000;//找最小权值路径for(var j=0;j<this.vexnum;j++){if(!path[j][0]&&a[j]<mindist){k=j;mindist=a[j];}}if(10000==mindist) return;path[k][0]=1;//改变记录for(var j=0;j<this.vertex[k].node.length;j++){if(!path[this.vertex[k].node[j]][0]&&a[this.vertex[k].node[j]]>a[k]+this.vertex[k].weight[j]){a[this.vertex[k].node[j]]=a[k]+this.vertex[k].weight[j];path[this.vertex[k].node[j]]=[0];for(var t=1;t<path[k].length;t++){path[this.vertex[k].node[j]].push(path[k][t]);}path[this.vertex[k].node[j]].push(k);}}}//返回最短路径var showpath="路线：";for(var i=1;i<path[end].length;i++){document.getElementById('b'+path[end][i]).style.color='#fff';showpath+=[path[end][i]];showpath+="->";}document.getElementById('b'+end).style.color='#fff';showpath+="<b>"+[end]+"</b>";document.getElementById('path').innerHTML=showpath;}function printinfor(){var last=document.getElementById('last').value;document.getElementById('footer').innerHTML=r[parseInt(last)]; }五．测试数据及运行结果六．调试情况，设计技巧及体会每当写完一个函数的时候，都会出现很多错误，就这样坚持着改错误，慢慢的发现其实很多是由于自己粗心造成的，别的错误改多了就习惯了。
琼州学院电子信息工程学院课程设计报告课程名称：《数据结构》课程设计设计题目：校园导游咨询专业：软件工程班级：2010软件工程学生姓名：学号：起止日期：指导教师：注意事项一、设计目的《数据结构》是一门实践性较强的软件基础课，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。
本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
二、设计要求1．通过这次课程设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
2．学生必须仔细研读《数据结构》课程设计要求，以学生自学为主、指导教师指导为辅，独立完成课程设计的任务，有问题及时主动与指导教师沟通。
3．本次课程设计按照教学要求需要在本学期15周前完成，学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向指导教师汇报。
4．编程语言：C 语言。
三、课程设计说明书的格式要求设计文档的撰写必须提前进行，以保证使文档与程序同步提交。
1．设计题目2．运行环境（软、硬件环境）3．算法的需求分析4．算法概要设计5．算法详细设计6．算法的测试7．运行结果分析8．收获及体会四、问题分析、设计和测试过程要规范化1．需求分析：将题目中要求的功能进行叙述分析。
2．概要设计：算法的设计说明，描述解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。
3．详细设计：即各个算法的具体实现步骤，每个题目要有相应的源程序，其中每个功能模块采用不同的函数实现。
源程序要规范编写：结构要清晰，注释要清楚。
姓名：班级：学号：指导教师：2012年12月目录1、需求分析 (1)1.1 系统简介 (1)1.2 系统功能模块介绍 (1)2、概要设计 (2)2.1 系统功能结构图 (2)2.2 系统流程图 (2)2.3 主要函数概要设计 (3)2.3.1 主函数概要设计 (3)2.3.2 初始化图函数InitGraph() (4)2.3.4 查询景点信息函数设计SearchGraph() (4)2.3.5 显示图中信息函数设计ShowGraph() (4)2.3.6 弗洛伊德算法函数设计Floyd() (5)3、详细设计 (5)3.1 主函数详细设计 (5)3.2初始化图函数详细设计InitGraph() (6)3.3查询景点信息函数详细设计SearchGraph() (7)3.4 弗洛伊德算法函数详细设计Floyd() (8)4、调试分析 (9)4.1 显示主界面函数测试 (9)4.2 查找两景点间最短路径测试 (10)4.3 查看景点信息测试 (11)5.课程设计总结 (12)6、附录 (13)1、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。
考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。
开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。
本系统界面友好，提示信息充分，在实际使用过程中运行良好。
1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。
9、校园导游咨询问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。
基本要求：⑴设计华东交通大学的校园平面图，所含景点不少于10个。
以图中顶点表示校内各景点，⑵存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
⑶为来访客人提供图中任意景点相关信息的查询。
⑷为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
#include <stdio.h>#define MAXV 100 //最大顶点个数#define INF 32767 //用32767表示∞#include <stdlib.h> //调用函数system改变字体颜色的头文件typedef int InfoType;#define MAXV 100 //最大顶点个数//以下定义邻接矩阵类型typedef struct{ int no; //顶点编号InfoType info; //顶点其他信息} VertexType; //顶点类型typedef struct //图的定义{ int edges[MAXV][MAXV]; //邻接矩阵int vexnum,arcnum; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息} MGraph;void ecjtumap()//建立华东交通大学地图{ printf("\t|-------------------------------------------------------------|\n");printf("\t| |\n");printf("\t| |\n");printf("\t| ---------- |\n");printf("\t| ==============================| 国防生宿舍| |\n");printf("\t| 。
姓名：班级：学号：指导教师：2012年12月目录1、需求分析 (1)1.1 系统简介 (1)1.2 系统功能模块介绍 (1)2、概要设计 (1)2.1 系统功能结构图 (1)2.2 系统流程图 (2)2.3 主要函数概要设计 (3)2.3.1 主函数概要设计 (3)2.3.2 初始化图函数InitGraph() (3)2.3.4 查询景点信息函数设计SearchGraph() (4)2.3.5 显示图中信息函数设计ShowGraph() (4)2.3.6 弗洛伊德算法函数设计Floyd() (4)3、详细设计 (4)3.1 主函数详细设计 (4)3.2初始化图函数详细设计InitGraph() (5)3.3查询景点信息函数详细设计SearchGraph() (6)3.4 弗洛伊德算法函数详细设计Floyd() (7)4、调试分析 (8)4.1 显示主界面函数测试 (8)4.2 查找两景点间最短路径测试 (9)4.3 查看景点信息测试 (10)5.课程设计总结 (11)6、附录 (12)1、需求分析1.1 系统简介随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。
考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。
开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。
本系统界面友好，提示信息充分，在实际使用过程中运行良好。
1.2 系统功能模块介绍本系统主要分为以下三大功能模块：1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。
若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方；2、查询景点信息：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入想要查询的景点的编号，回车后系统将在已存储的景点中进行匹配，若该景点信息尚未存储则将提示错误；若找到对应信息则系统将输出景点信息，显示于幕上方；3、退出系统：用户在使用完本系统后，选择此功能模块，系统提示“欢迎再次使用”后，按任意键系统将自动退出。
2、概要设计2.1 系统功能结构图2.2 系统流程图2.3 主要函数概要设计2.3.1 主函数概要设计主函数首先是调用初始化图函数InitGraph()函数创建一个图，而后调用显示主界面函数显示一个可视化主界面，内容包含本系统LOGO以及景点信息及操作编号的提示信息。
之后，当用户成功输入操作编号后，使用一个switch()函数，判断用户所需操作，匹配成功后，调用相关函数实现用户所需功能。
2.3.2 初始化图函数InitGraph()InitGraph()函数首先使用MyGraph结构体声明一个用于存储图中信息的结构体，而后定义结构体中的景点数量以及路径数量，然后使用循环为景点信息和路径长度赋值，其中赋值景点信息时使用strcpy()函数将字符串复制给G.siteArray[i].siteName以及G.siteArray[i].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算法首先将两景点间路径长度数据存储于数组 D[v][w]中，而后使用一个三维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。
以上部分完成后，当用于标记输入数据是否合法的flag=1时，输出错误信息，提示用户重新输入，当输入数据合法时，输出以上程序得到结果。
3、详细设计3.1 主函数详细设计#define InfiniteNum 10000 //定义一个无穷大数#define MaxInfoNum 100 //定义景点数据最大容量#include<stdio.h>#include<stdlib.h>#include<string.h>#include"MyGraph.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("欢迎下次继续使用 !\n\n");}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.siteArray[i].siteIdentifier = i; //对景点进行对应编号strcpy(G.siteArray[1].siteName,"一教");strcpy(G.siteArray[1].siteInfo,"最有历史的教学楼");strcpy(G.siteArray[2].siteName,"软件学院");strcpy(G.siteArray[2].siteInfo,"规模庞大，师资雄厚，全校第二大院"); strcpy(G.siteArray[3].siteName,"老图书馆");strcpy(G.siteArray[3].siteInfo,"说实话，太破了！");strcpy(G.siteArray[4].siteName,"校门");strcpy(G.siteArray[4].siteInfo,"有点小家子气，规模太小");strcpy(G.siteArray[5].siteName,"新图书馆");strcpy(G.siteArray[5].siteInfo,"邵逸夫先生捐赠的,设施较为完备,最常去的地方");strcpy(G.siteArray[6].siteName,"南区食堂");strcpy(G.siteArray[6].siteInfo,"价格尚算公道，但卫生状况较为堪忧，已经吃出好几次头发了");for(i = 1;i<=G.siteNumber;i++) //使用循环对路径进行赋值，对于没有直接路径的，赋值为无穷大for(j = 1;j<=G.siteNumber;j++)G.pathArray[i][j].path = InfiniteNum;G.pathArray[1][2].path = 200;G.pathArray[1][3].path = 100;G.pathArray[1][4].path = 400;G.pathArray[2][4].path = 300;G.pathArray[4][5].path = 100;G.pathArray[4][6].path = 500;G.pathArray[5][6].path = 500;for(i = 1;i<=G.siteNumber;i++) //所构造的图为无向图，故相反方向路径相同for(j = 1;j<=G.siteNumber;j++)G.pathArray[j][i].path = G.pathArray[i][j].path;return G;}3.3查询景点信息函数详细设计SearchGraph()void SearchGraph(MGraph *G) //用于查询景点信息，以列表方式输出{int k,flag=1;while(flag){printf(" 请输入要查询的景点编号:");scanf("%d",&k);if(k<=0||k>G->siteNumber) //输入景点编号不合法时提示错误{printf(" 景点编号不存在!请重新输入景点编号:");scanf("%d",&k);}if(k>0&&k<=G->siteNumber) // 输入合法时将 falg 置为 0flag=0;}printf(" \n");printf(" 编号景点名称简介 \n");printf(" %-4d %-16s %-62s\n",G->siteArray[k].siteIdentifier,G->siteArray[k].siteName,G->siteAr ray[k].siteInfo); //输出景点信息}3.4 弗洛伊德算法函数详细设计Floyd()void Floyd(MGraph *G) //使用弗洛伊德算法2求出最短路径{int v,u,i,w,k,j;int flag = 1; //用于标记输入数据是否正确，若输入数据符合要求，则将 flag 置为0int p[7][7][7],D[7][7];for(v = 1;v <= G->siteNumber;v++)for(w = 1;w<=G->siteNumber;w++){D[v][w] = G->pathArray[v][w].path; //将路径数据存放至数组 D[v][w] 中for(u = 1;u<=G->siteNumber;u++)p[v][w][u]=0; //该三维数组用于存放两景点之间是否有直接路径，若有则记为1，无则记为0if(D[v][w] < InfiniteNum){p[v][w][v] = 1;p[v][w][w] = 1;}}for(u = 1;u<=G->siteNumber;u++)for(v = 1;v<=G->siteNumber;v++)for(w = 1;w<=G->siteNumber;w++)if(D[v][u] + D[u][w]<D[v][w]) // 如果两点之间直接路径大于简介路径，则将该两点之间路径置为间接路径{D[v][w] = D[v][u]+D[u][w];for(i = 1;i<=G->siteNumber;i++)p[v][w][i] = p[v][u][i]||p[u][w][i]; //获取两点之间路径所经过的景点编号}while(flag){printf(" 请输入出发点和目的地的编号:");scanf("%d%d",&k,&j);if(k<=0||k>G->siteNumber||j<=0||j>G->siteNumber){printf(" 景点编号不存在!请重新输入:");scanf("%d\n%d",&k,&j);}if(k==j){printf(" 出发点和目的地一样!请重新输入:");scanf("%d\n%d",&k,&j);}if(k>0&&k<=G->siteNumber&&j>0&&j<=G->siteNumber)flag=0; //输入的数据合法，故将 flag = 0}printf("\n最短游览路线：%s",G->siteArray[k].siteName);if(k>j){for(u = G->siteNumber;u>0;u--)if(p[k][j][u] && k!=u && j!=u)printf("-->%s",G->siteArray[u].siteName);}if(k<j){for(u=1;u<=G->siteNumber;u++)if(p[k][j][u] && k!=u && j!=u)printf("-->%s",G->siteArray[u].siteName);}printf("-->%s",G->siteArray[j].siteName);printf(" 总路线长%dm\n",D[k][j]);}4、调试分析4.1 显示主界面函数测试显示主界面函数必须实现提示景点名称及其对应编号，主界面下方以列表方式提示用户系统可进行的操作及其对应编号，最后提示用户进行输入。
