数据结构试验报告--校园导游.docx

数据结构课程设计报告课程名称：数据结构课程设计；课程设计题目：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：大二；学号：10054220；指导教师：王立波；2011年12月17日1 课程设计的目的x2 需求分析x3 课程设计报告内容x1、概要设计x2、详细设计x3、调试分析x4、用户手册x5、测试结果x6、程序清单x4 小结 x5 参考文献 x1. 课程设计的目的：（1） 熟练运用C+编写程序；（2） 会用Floyd算法查找最短路径；2. 需求分析：1. 题目：【校园导游咨询】问题描述 （1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 （3）为来访客人提供图中任意景点相关信息的查询。测试数据由读者根据实际情况指定。2. 任务：通过此程序可实现以下功能：（1） 用一维数组存放景点信息，二维数组存放景点间的距离，最短距离，最短路径；（2） Floyd算法计算最短距离和路径；（3） 根据景点序号查询景点的一系列信息，及两景点间的最短路径和最短距离。3. 测试数据:查询类型：I（表示查询景点信息）；景点编号：3；查询类型：D（表示查询景点间的最短路径和最短距离）；景点编号：19；3. 课程设计报告内容：1. 概要设计：（1）首先我画了学校主要几个景点的分布图以及自己定的一些距离，图如下： （2）接着我定义了一个顶点结构体，定义如下： struct Dateint num; /景点编号char name50; /景点名称char introduce100; /景点介绍; （3）然后我定义了一个类，定义如下： class Travelprivate:Date date15;int distance1515;int Path1515;int ShortestDistance1515;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”，调用最短距离和路径函数。 3. 调试分析： 刚开始运行时，所有汉字部分输出都为火星文，重新复制粘贴后此问题消失；改后 运行时初始和终止点之间的顶点输出有问题，查到原因是数组下标有问题，改了之 后，一切正常。 4. 用户手册（无） 5. 测试结果： 6. 程序清单： #include #include #include School.h#define MAX 1000 using namespace std;class Travelprivate:Date date15; /顶点数组int distance1515; /两顶点间的数组int Path1515; /存放最短路径int ShortestDistance1515; /存放最短距离void Floyd(); /Floyd算法public:Travel(); /构造函数Travel() /析构函数void Introduce(int); /景点介绍函数void Scanf(); /外部接口函数void ShortDistance(int,int); /最短路径及距离函数;/构造函数 Travel:Travel()int i,j;for(i=1;i=14;i+)datei.num=i; /给顶点的编号赋值switch(i)case 1:strcpy(,杭电大门);strcpy(roduce,大门像桥，像船，据说是亚洲第一长门，是杭电的标志性建筑之一。);break;case 2:strcpy(,1教);strcpy(roduce,计算机学院所在地，里面没有教室，除了老师的办公室外全部都为实验室。);break;case 3:strcpy(,2教);strcpy(roduce,电子信息学院所在地，阳光乐跑签到处。);break;case 4:strcpy(,3教);strcpy(roduce,外国语学院所在地，机房所在地。);break;case 5:strcpy(,6教);strcpy(roduce,理学院所在地，教室全天开放可供学生自修的地方);break;case 6:strcpy(,7教);strcpy(roduce,多媒体教室所在地，英语小班教室 所在地。);break;case 7:strcpy(,8教);strcpy(roduce,金工实习的地方。);break;case 8:strcpy(,9教);strcpy(roduce,上选修课的地方。);break;case 9:strcpy(,10教);strcpy(roduce,上选修课的地方。);break;case 10:strcpy(,11教);strcpy(roduce,上必修课与选修课的地方，阳光乐跑签到处。); break;case 11:strcpy(,12教);strcpy(roduce,上必修课与选修课的地方。);break;case 12:strcpy(,图书馆);strcpy(roduce,外形像一本巨大的打开的书，是杭电标志性建筑之一。);break;case 13:strcpy(,体育馆);strcpy(roduce,外形像一个飞碟，杭电的标志性建筑之一。);break;case 14:strcpy(,学生活动中心);strcpy(roduce,学生进行课余活动所在地。);break;default:break; for(i=1;i=10;i+) ShortestDistanceii=0; /所有的两顶点最短距离初始化为0 for (i=1;i=14;i+)for(j=1;j=14;j+)distanceij=MAX; /所有两顶点间的距离初始化为最大值 /有连接的顶点间的距离赋值distance11=distance22=distance33=distance44=distance55=distance66=distance77=0;distance88=distance99=distance1010=distance1111=distance1212=distance1313=distance1414=0;distance12=distance21=50;distance13=distance31=60;distance23=distance32=30;distance24=distance42=30;distance35=distance53=80;distance46=distance64=60;distance56=distance65=30;distance512=distance125=20;distance612=distance126=20;distance67=distance76=30;distance712=distance127=10;distance611=distance116=50;distance49=distance94=80;distance89=distance98=10;distance810=distance108=10;distance1011=distance1110=10;distance119=distance911=10;distance513=distance135=20;distance713=distance137=30;distance614=distance146=10;distance1114=distance1411=70; /景点介绍函数 void Travel:Introduce(int i)cout景点代号：datei.numendl景点名称：endl景点介绍：roduceendl;/Floyd算法 void Travel:Floyd() int i,j,k; for(i=1;i=14;i+) for(j=1;j=14;j+) ShortestDistanceij=distanceij; /最短距离用两点距离初始化 Pathij=0; /两顶点间的路径点用编号0初始化 for(i=1;i=14;i+) /起点的循环 for(k=1;k=14;k+) /中间点（即路径点的循环） for(j=1;j(ShortestDistanceik+ShortestDistancekj) ShortestDistanceij=ShortestDistanceik+ShortestDistancekj; Pathij=k; Pathji=k; /输入函数void Travel:Scanf()int i,j;char n;cout请输入查询项目编号I或D（I代表景点介绍，D代表查询两地间的最短距离及最短路径）：n;coutendl;if (n=I)cout请输入所要查询的景点代号（请输入114之间的数字）：i;if(i=1&i=14)Introduce(i);elsecout无此景点信息！endl;else if(n=D)cout请输入所要查询的两个景点编号（请输入114之间的数字）：ij;if(i=1&i=1&j=14)ShortDistance(i,j);elsecout无此景点信息，没有路径可查！endl; elsecout无此查询项！endl; /求两地的最短距离及路径 void Travel:ShortDistance(int i,int j)Floyd();int temp14; /临时数组，用来对路径起颠倒顺序作用int count=0,k;int a,b;a=i;b=j;couti号景点j号景点最短路径是：endl;if (ShortestDistanceij!=MAX) /如果两顶点可以直接或间接连接;if(i=0;k-)coutdatetemp