校园导游系统课程设计.doc

(完整word版)校园导游系统课程设计

西 安 邮 电 大 学
（计算机学院）

数据结构课程设计报告

题 目： 校园导游系统

专业名称：
班 级：
学生姓名：
学号（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=[];
this.name=[];//名称
this.infor=[];//信息
this.flag=[];//标记
this.arr=[];//存储路径
this.ar=[];//存储路径2
for(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.name[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.name[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+=this.name[path[end][i]];
showpath+="->";
}
document.getElementById('b'+end).style.color='#fff';
showpath+="<b>"+this.name[end]+"</b>";
document.getElementById('path').innerHTML=showpath;
}
function printinfor()
{
var last=document.getElementById('last').value;
document.getElementById('footer').innerHTML=this.infor[parseInt(last)];
}
五．测试数据及运行结果

六．调试情况，设计技巧及体会
每当写完一个函数的时候，都会出现很多错误，就这样坚持着改错误，慢慢的发现其实很多是由于自己粗心造成的，别的错误改多了就习惯了。
1．改进方案
程序代码还不够简练，还有很大的改进余地。自己需要付出更多的努力。
2．体会

经过几周的课程设计，我学到了很多东西：巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。
课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。
在这次课程设计中我遇到许多问题和麻烦，得到了老师的帮助和指导，才能够使得这次课程设计顺利的进行下去，另外，在程序编写和调试过程中，也得到很多同学的帮助，给我及时指出错误，提出许多宝贵意见。此对老师和同学们表示感谢！

七．参考文献
《数据结构与算法》
《javascript编程全解》
。