校园导游系统 数据结构实习报告.doc

西安郵電學院
数据结构设计报告
题目:校园导游系统
院系名称:计算机学院
专业名称:计算机科学与技术
班级:
学生姓名:
学号(8位):
指导教师:
设计起止时间:2011年12月12日~2011年12月16日
一. 设计目的
1 对自己学过的知识进一步巩固,对数据结构的算法思想要有更深的理解。
2 通过课程设计,学会通过系统分析、系统设计、编程调试,写实验报告等环节,进一步掌握应用系统设计的方法和步骤,灵活运用并深刻理解典型数据结构在软件开发中的应用。
3 学会综合运用数据结构课程中图类型数据结构,组建一个较为完整的系统。
二. 设计内容
1 校园平面图
2 选取有代表性的景点,用邻接链表存储相关信息
3 查询图中任意景点的相关信息
4 查询任意两个景点之间的一条最短的简单路径
5 查询中转最少的路径
6 查询两个景点间的全部路径



Main()
全部路径
最短路径
创建图
中转最少路径
校园平面图
校园信息输出

ShortestPath_Floyd() 任意两个地点之间最短路径算法
least() 两个地点之间中转最少算法
main() 主函数
xiaoyuantu() 校园概略图
shuchu() 校园的全部信息输出
CreatUDN() 创建图
DFS_ path() 两个景点之间的全部路径

Main()
DFS_path()
ShortestPath_Floyd()
CreatUDN()
least()
xiaoyuantu()
xiaoyuantu(
xiaoyuantu()
xiaoyuantu()
Shuchu()
all_path()

ShortestPath_Floyd()
开始
输入始末点
弗洛伊德


输出最短路径
结束
allpath()
开始
输入始末点
all_path()

DFS_path()

输出所有路径
结束
least()
开始
输入始末点
least()

弗洛伊德
输出中转最少路径
结束

两个景点之间的全部路径
void DFS_path(AdjM g, int m,int n,int k)
{
int s;
if(pre[k]==n && k<11) //pre[k]存储路径顶点若pre[k]是终点,则输出该路径
{ //递归出口,找到一条路径
for(s=0;s<k;s++)
printf("%s>>>>>",[pre[s]].name); //输出该路径。s=0 时为起点m
printf("%s",[pre[s]].name); //输出最后一个景点名(即顶点n的名字,此时s==k)
printf("\n\n");
}
else
{
s=0;
while(s<) //从第m个顶点,试探至m到其他顶点是否有路径
{
if(([pre[k]][s].adj<INFINITY) && (visited[s]==0)) //顶点k到顶点s有边,且未被访问
{
visited[s]=1;
pre[k+1]=s; //存储顶点编号s至pre[k+1]中
DFS_path(g,m,n,k+1); //求从下标为k+1的pre[k+1]个顶点开始的路径(递归调用),同时打印出一条m至n的路径
visited[s]=0; //将找到的路径上顶点的访问标志重新设置为0,以用于试探新的路径
}
s++; //试探从下一个顶点 s 开始是否有到终点的路径
}

}
}
void all_path(AdjM g)
{
int i,m,n;
printf("\n\n请输入你要查询的两个景点编号:\n\n");
scanf("%d %d",&m,&n);
printf("\n\n");
pre[0]=m; //存储路径起点u
for(i=0;i<;i++) //全部顶点访问标志初值设为0
visited[i]=0;
visited[m]=1; //表示已经访问过
DFS_path(g,m,n,0); //对应起点pre[0]==u
}
任意两个地点之间最短路径算法
ShortestPath_Floyd(AdjM *g) //弗洛伊德算法
{
int i,k,j,l,flag=1,