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

西安郵電學院 目：校园导游系统 院系名称：计算机学院 专业名称：计算机科学与技术 班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间：2011年月日~20年月日一. 设计目的 1 对自己学过的知识进一步巩固，对数据结构的算法思想要有更深的理解。 2 通过课程设计，学会通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用 。 3 学会综合运用数据结构课程中图类型数据结构，组建一个较为完整的系统。 二. 设计内容 1 校园平面图 2 选取有代表性的景点，用邻接链表存储相关信息 3 查询图中任意景点的相关信息 4 查询任意两个景点之间的一条最短的简单路径 5 查询中转最少的路径 6 查询两个景点间的全部路径 三．概要设计 1．功能模块图 2．各个模块详细的功能描述 ShortestPath_Floyd() 任意两个地点之间最短路径算法 least() 两个地点之间中转最少算法 main() 主函数 xiaoyuantu() 校园概略图 shuchu() 校园的全部信息输出 CreatUDN() 创建图 DFS_ path() 两个景点之间的全部路径 四．详细设计 2．各功能函数的数据流程图 ShortestPath_Floyd() allpath() least() 3．重点设计及编码 两个景点之间的全部路径 void DFS_path(AdjM g, int m,int n,int k) { int s; if(pre[k]==n k11) //pre[k]存储路径顶点 若pre[k]是终点，则输出该路径 { //递归出口，找到一条路径 for(s=0;sk;s++) printf(%s,g.vertex[pre[s]].name); //输出该路径。s=0 时为起点m printf(%s,g.vertex[pre[s]].name); //输出最后一个景点名(即顶点n的名字，此时s==k) printf(\n\n); } else { s=0; while(sg.vexnum) //从第m个顶点，试探至m到其他顶点是否有路径 { if((g.arcs[pre[k]][s].adjINFINITY) (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);