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

《数据结构课程设计---交通咨询模拟》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、滁州学院课程设计报告课程名称：数据结构课程设计设计题目：交通咨询模拟系别：计算机信息与工程学院专业：计算机科学与技术组别：第七组起止日期:2012年5月20日~年6月10日指导教师:戴支祥计算机与信息工程学院二○一二年制课程设计题目交通咨询模拟组长张远春学号2011211244班级2班系别计算机与信息工程学院专业计算机与科学技术组员张远春王书航王露王俊德芮威振指导教师戴支祥课程设计目的总结所学知识，学以自用课程设计所需环境Windows7VC++6.0课程设计任务要求用图的一种存储方式;输出两点间所有路径课程设计工作进度计划序号起止日期工作内容分工情况15月21日5月25日程序设计张远春

2、25月26日5月31日调试运行王书航王露36月1日6月2日程序优化王露芮威震王俊德王书航46月3日6月4日手稿与打印王俊德王书航56月5日6月6日实验心得张远春王书航王露王俊德芮威振指导教师签字：年月日系（教研室）审核意见：系（教研室）主任签字：年月日课程设计任务书目录引言…………………………………………………………………………31广度优先遍历……………………………………………………………………31.1广度优先遍历的递归定义1.2广度优先遍历的过程2两点间所有路径算法设计……………………………………………………32.1~2.6算法分析3详细设计…………………………………………………………

3、………………63.1部分代码4调试与操作说明…………………………………………………………………114.1使用说明5课程设计总结…………………………………………………………………115.1总结致谢…………………………………………………………………………………11[参考文献]………………………………………………………………………11课程设计的主要内容【引言】本文首先介绍图的广度优先遍历算法，接着根据图的广度优先遍历算法求出连通图中两点间所有路径，并给出代码.【关键词】图；广度优先遍历算法1广度优先遍历（Breadth_FirstSearch）1.1广度优先遍历的递归定义设图G的初态是所有顶点

4、均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。   　若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。   　广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广

5、度优先遍历。1.2广度优先遍历的过程在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，…，xs和y1，y2，…，yt。为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，…，xs和y1，y2，…，yt，对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。2求两点间所有路径的算法假设简单连通图如图一所示，那么的他的存储结构如图2所示。假设我们要找出结点3到

6、结点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]保存下从3到1的权值w；2.3.1未访问且不为6，递归，将1标记为以访问，然后寻找与1相邻的第一个邻接点0，用a[1]=1保存下路径，并用b[1]保存下从1到0的权值w；2.4

7、.0未访问且不为6，递归，将0标记为以访问，然后寻找与1相邻的第一个邻接点2，用a[2]=0保存下路径，并用b[2]保存下从0到2的权值w；2.3.2未访问且不为6，递归，将2标记为以访问，然后寻找与2相邻的第一个邻接点6，用a[3]=2保存下路径，并用b[3]保存下从0到2的权值w；2.46为终点，用b[4]记录下从2到6的权值，然后用a[4]=6保存下路径。从i=0到i<=G.verticesMAX_VERTEX_NUM20[]