数据结构课程设计---交通咨询模拟.doc

滁州学院 课程设计报告 课程名称： 数据结构课程设计 设计题目： 交通咨询模拟 系 别： 计算机信息与工程学院 专 业： 计算机科学与技术 组 别： 第七组 起止日期: 2012年 5 月 20 日 ~ 年 6月10日 指导教师: 戴支祥 计算机与信息工程学院二○一二年制 课程设计题目 交通咨询模拟 组长 张远春 学号 2011211244 班级 2班 系别 计算机与信息工程学院 专业 计算机与科学技术 组员 张远春 王书航 王露 王俊德 芮威振 指导教师 戴支祥 课程设计目的 总结所学知识，学以自用 课程设计所需环境 Windows 7 VC++ 6.0 课程设计任务要求 用图的一种存储方式;输出两点间所有路径 课程设计工作进度计划 序号 起止日期 工 作 内 容 分工情况 1 5月21日 5月25日 程序设计 张远春 2 5月26日 5月31日 调试运行 王书航 王露 3 6月1日 6月2日 程序优化 王露 芮威震 王俊德 王书航 4 6月3日 6月4日 手稿与打印 王俊德 王书航 5 6月5日 6月6日 实验心得 张远春 王书航 王露 王俊德 芮威振 指导教师签字： 年 月 日 系（教研室）审核意见： 系（教研室）主任签字： 年 月 日 课程设计任务书 目 录 引 言…………………………………………………………………………3 1 广度优先遍历……………………………………………………………………3 1.1 广度优先遍历的递归定义 1.2 广度优先遍历的过程 2 两点间所有路径算法设计 ……………………………………………………3 2.1~2.6 算法分析 3 详细设计…………………………………………………………………………6 3.1 部分代码 4 调试与操作说明…………………………………………………………………11 4.1 使用说明 5 课程设计总结 …………………………………………………………………11 5.1总 结 致谢…………………………………………………………………………………11 [参考文献] ……………………………………………………………………… 11 课程设计的主要内容 【引言】本文首先介绍图的广度优先遍历算法，接着根据图的广度优先遍历算法求出连通图中两点间所有路径，并给出代码. 【关键词】图；广度优先遍历算法 1 广度优先遍历（Breadth_First Search） 广度优先遍历的递归定义 设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的有哪些信誉好的足球投注网站过程结束。??? 　若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的有哪些信誉好的足球投注网站过程，直至G中所有顶点均已被访问为止。??? 　广度优先遍历类似于树的按层次遍历。采用的有哪些信誉好的足球投注网站方法的特点是尽可能先对横向进行有哪些信誉好的足球投注网站，故称其为广度优先有哪些信誉好的足球投注网站(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。 2求两点间所有路径的算法 假设简单连通图如图一所示，那么的他的存储结构如图2所示。假设我们要找出结点3到结点6的所有路径，那么我们就设节点3为起点，结点6为终点。我们需要的存储结构有：图的邻接表建立图，一个标记数组visited[]，一个保存路径的数组a[]，一个保存权值的数组b[]。 2.1. 首先建立含有8个结点的交通图，初始a[]，b[]全部为-1，然后输入3和6，传递到广度优先遍历的函数中； 2.2. 将3标记为已访问状态visited[3]=1，并用a[0]=3保存下路径，然后寻找结点3的第一个邻接点1，用b[0]保存下从