云南大学软件学院数据结构实验六实验报告校园自动导游系统.docx
《云南大学软件学院数据结构实验六实验报告校园自动导游系统.docx》由会员分享，可在线阅读，更多相关《云南大学软件学院数据结构实验六实验报告校园自动导游系统.docx（20页珍藏版）》请在冰点文库上搜索。
云南大学软件学院数据结构实验六实验报告校园自动导游系统
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）
实验难度：
A□B□C□
序号
学号
姓名
成绩
1
2
3
指导教师
（签名）
学 期：
任课教师:
实验题目:
实验六图及图的应用
小组长:
联系电话:
电子邮件:
完成提交时间：
年月日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
姓名：
本人承担角色：
课题分析，算法设计，程序编写，后期调试，完成实验报告
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
（注：
此表在难度为C时使用，每个成员一份。
）
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
姓名：
本人承担角色：
课题分析，算法设计，后期调试，
完成实验报告
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
（注：
此表在难度为C时使用，每个成员一份。
）
（下面的内容由学生填写，格式统一为，字体:
楷体,行距:
固定行距18，字号:
小四，个人报告按下面每一项的百分比打分。
难度A满分70分，难度B满分90分）
一、【实验构思（Conceive）】（10%）
（本部分应包括：
描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）
1.数据结构算法的知识：
●图的定义。
●图的节点和边的表示。
●图的存储结构。
●图的分类：
有向图-无向图-带权图-无权图。
●图的遍历：
深度优先搜索-广度优先搜索。
2.面向对象的程序设计相关知识：
●C#基本语法知识。
●类的定义，实例化。
●对象的生成调用。
●变量的传递。
3.图形处理相关技术
●AdobePhotoshopCS4相关基本操作
●蒙板使用的技巧
二、【实验设计（Design）】（20%）
（本部分应包括：
抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
本实验创建了四个类Form类//用于窗口的初始化，控制各控件的属性和动作
Data类//用于本程序所需的数据的生成以及调用
Graph类//用于构造图以及定义图的各种操作
Vertex类//用于构造带权图的节点
抽象数据类型的功能规格说明：
窗口初始化：
privatevoidForm1_Load（objectsender,EventArgse）
开始按钮：
privatevoidbutton3_Click（objectsender,EventArgse）
复位按钮：
privatevoidbutton2_Click（objectsender,EventArgse）
查看产品信息：
privatevoidbutton4_Click（objectsender,EventArgse）
退出按钮：
privatevoidbutton3_Click（objectsender,EventArgse）
定义结构体数组：
publicstructmember
{
publicintfromsw;//起点的数字代号
publicinttosw;//目的地的数字代号
publicintdistance;//保存长度
}
Data的构造函数（创建带权图）publicData（）
HVertex类中创建节点的构造函数：
publicHVertex（intx,inty，intz）
Graph类中定义的节点类型：
publicHVertexroot,p,r;
Graph类中的构造函数，创建一个带权图：
publicGraph（）
Graph类中的成员函数，对于指定的字符实行深度优先搜索，遍历完之后形成一个深度优先搜索树：
publicintSearch（）
Graph类中的成员变量：
publicintDijikstra（）
主程序模块伪代码说明：
创建新的无向图：
Graph=newData（）;
退出程序：
this.Close（）
子程序伪代码说明（Graph）：
构建无向图：
publicVertex;
核心程序段（生成无向图）：
publicvoidPath（）
{
intstartTree=0;
vertexList[startTree].isInTree=true;
nTree=1;
for（intj=0;j<=nVerts;j++）
{
inttempDist=adjMat[startTree,j];
apath[j]=newGraph（startTree,tempDist）;
}
while（nTree{
intindexMin=GetMin（）;
intminDist=sPathp[indexMin].distance;
currentVert=indexMin;
startToCurrent=sPath[indexMin].distance;
vertexList[currentVert].isInTree=true;
nTree++;
AdjustShortPath（）;
}
返回栈中元素个数：
publicintcount{get{returnlist.Count;}}
主程序模块与各子程序模块间的调用关系：
ClassForm1调用ClassData初始化程序所要的各项数据。
ClassForm1调用ClassGraph生成无向图并且初始化Dijikstra算法。
ClassGraph调用ClassVertex来初始化各个节点。
ClassGraph调用ClassStack保存产生的节点编号用于回退。
三、【实现描述（Implement）】（30%）
（本部分应包括：
抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。
）
抽象数据类型具体实现的函数原型说明：
1、节点类型；
classVertex
{
publicstringlabel;
publicboolisInTree;
publicVertex（stringlab）
{
label=lab;
isInTree=false;
}
}2、深度优先搜索树算法
classGraph
{
publicintdistance;
publicintparentVert;
publicGraph（intpv,intd）
{
distance=d;
parentVert=pv;
}
publicvoidPath（）
{
intstartTree=0;
vertexList[startTree].isInTree=true;
nTree=1;
for（intj=0;j<=nVerts;j++）
{
inttempDist=adjMat[startTree,j];
apath[j]=newGraph（startTree,tempDist）;
}
while（nTree{
intindexMin=GetMin（）;
intminDist=sPathp[indexMin].distance;
currentVert=indexMin;
startToCurrent=sPath[indexMin].distance;
vertexList[currentVert].isInTree=true;
nTree++;
AdjustShortPath（）;
}
DisplayPath（）;
nTree=0;
for（intj=0;j<=nVerts-1;j++）
vertexList[j].isInTree=false;
}
publicintGetMin（）
{
intminDist=infinity;
intindexMin=0;
for（intj=1;j<=nVerts-1;j++）
if（!
（vertxList[j].isInTree）&&（sPath[j].distance{
minDist=sPath[j].distance;
indexMin=j;
}
rerutnindexMin;
}
publicvoidAdjustShortPath（）
{
intcolumn=1;
while（columnif（vertexListp[column].isInTree）
coiumn++;
else
{
intcurrentToFringe=adjMat[currentVert,column];
intstartToFringe=startToCurrent+currentToFringe;
intsPathDist=sPath[column].distance;
if（startToFringe{
sPathDist[column].parentVert=currentVert;
sPathDist[column].distance=startToFringe;
}
column++;
}
}
}
关键操作实现的伪码算法:
深度优先搜索伪代码：
先访问起点，然后按照一定规则选择一条为访问过的相邻节点，并将前一个访问过的节点入栈，一直递归访问，直至当前节点已无未被访问的相邻节点时，退栈，继续以上一节点为基准点访问周围节点，当栈中无元素且当前节点无未被访问过的相邻节点时，算法结束，返回0；
③关键的程序流程图：
④实验实践思路：
本实验作品由两部分组成，第一部分为一个命令行程序，实现手动输入学校的各个关键建筑以及之间的距离（距离是使用Photoshop功能中的标尺功能，对于云南大学呈贡校区总平面图上的比例尺精确比对后利用比例关系算出，误差不超过100m），然后使用Dijikstra算法，算出任意两个建筑之间的最短距离，根据程序的计算结果使用Photoshop作图，画出明显的路径线路。
第二个程序是一个Windows窗体程序，实现根据用户的选择，自动提取某一个已经编辑好了的地图调用，并显示在Picturebox里，并显示建筑物提示信息以及文字说明的推荐路线，大致的总长等等。
四、【测试结果（Testing）】（10%）
（本部分应包括：
对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）
测试过程：
测试过程：
我选择从楸院生活区出发到梓院生活区为测试数据，具体实施过程如下
1.双击程序图标打开程序主界面：
2.在“你的位置”的下拉菜单中选择“楸院生活区”或者直接输入：
在“你的目的地”下拉菜单中选择“梓院生活区”或直接输入：
3.点击“
”按钮，即可显示推荐路径及其最短距离，截图如下：
地图预览的截图：
我们在输入“你的位置”为“楸院生活区”和“你的目的地”为“梓院生活区”后点击“开始导航”按钮，程序就显示了最佳路径为：
楸院生活区->广田北路->庆来南路->图书馆->庆来西路->中山邦翰楼->余味堂->梓院生活区，并且显示最短距离为1816m。
程序上还显示了导航的预览图。
用户可根据以上信息顺利达到目的地。
测试成功！
由以上测试过程可知，我们的实现了一个能为新生指路的校园导游程序。
对校园不太熟悉的人可以使用此程序，只要知道自己是在哪一个有标记性的位置，并且知道目的地的标志性名称或建筑物，就可以利用此程序查出最短路径和所要走的路径方向，然后就可以随着导航走到目的地。
五、【实验总结】（10%）
（本部分应包括：
自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）
杨扬（20091120048）部分：
工作：
算法构思、设计、实现；编写代码。
总结：
这次实验使我对栈、图的遍历搜索算法，Dijikstra最短路径算法有了熟练的掌握。
在设计程序时，摆在我面前有以下几个难题：
首先，如何用C#生成符合一定规则的Graph？
这个问题花了我不少时间，最后通过定义一个图的Class来避免指针的缺失，解决了此问题。
其次，在生成Graph之后，如何实现Graph遍历算法呢？
这个问题到没话我太多时间，因为它的原理很简单，就是直接对变量进行赋值操作即可。
最后，通过什么方式控制无向图以正确的寻路呢，于是我想到了Dijikstra算法。
利用栈在每一次寻址之后得到一个结果进行进栈操作，很方便的实现了任意节点对于其他节点的寻址。
本次试验，小组配合得很好，一起讨论并解决了不少问题，使得程序更佳完善。
一个人不可能面面俱到，这时团队的帮助与合作尤为重要，一定要虚心求教，认真倾听别人的意见，不要认为自己做的东西才是最好的，只有这样才能进步。
许德胜（20091120210）部分：
此次实验的核心算法是迪杰斯特拉算法，这个恰好和计算机网络原理选路算实验中核心算法是一个的，都是利用迪杰斯特拉算法纠结最短路径，所以我现在对这个算法也有一个比较好的理解了，理解如下：
按路径长度递增次序产生最短路径算法：
把V分成两组：
（1）S：
已求出最短路径的顶点的集合
（2）V-S=T：
尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：
（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值S中顶点：
从V0到此顶点的最短路径长度T中顶点：
从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：
可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）求最短路径步骤…初使时令S={V0},T={其余顶点}，T中顶点对应的距离值ƒ若存在，为弧上的权值ƒ若不存在，为∝…从T中选取一个其距离值为最小的顶点W，加入S…对T中顶点的距离值进行修改：
若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值…重复上述步骤，直到S中包含所有顶点，即S=V为止
当然在这次实验中，对图的建立和遍历也有了比较好的认识。
基本上能熟练的进行图的入门级应用，不过还只是在入门边缘徘徊而已。
在这里还有谢谢我的组长，是他带着我做了这么多以前我想都不敢想的C级难度的实验，在这过程中我也在他身上学到了很多东西，自己的能力也得到了一定的提高。
六、【项目运作描述（Operate）】（10%）
（本部分应包括：
项目的成本效益分析，应用效果等的分析。
）
1.用户使用手册：
程序操作说明：
.先双击打开程序主界面：
2.在“
”框中填写你的位置，如楸院生活区。
在“
”填写你的目的地，如中山邦翰楼。
3.点击“
”按钮即可显示导航结果。
提示消息截图;
按
按钮重新进行数据的输入。
按
退出程序。
2.运作分析：
在成本方面有：
培训相关设计营销人员成本。
人力资源的消耗（成员基本工资）。
软件售后服务支持：
通信，交通费用。
在效益方面有：
应用后大大地减少新生入学之时对于校区的陌生，能够帮助他们迅速融入校园。
给我们提供难得的实践机会。
软件使用相关费用。
应用效果：
可改写成服务器版本，方便学生直接访问学校网站进行线路查询。
。
为后续的编程实现奠定了算法基础。
3.用户反馈：
田钦文（软件学院09级学生）：
程序所占用的内存比我想象的少很多，运行环境要求不高，运行时几乎没有延迟，界面友好。
范银（软件学院09级学生）：
程序总体上看来没有大的问题，能比较流畅的完成我们需要的工作，性能较为稳定。
巫德宝（软件学院09级学生）：
总体不错，不过也有一些需要注意的问题：
路线显示地太狭隘，最好能从地图上面选取起点和终点，直观又明了，望今后能做的更好。
升级会员 