1、 数据结构（数据结构（C 语言）课程设计语言）课程设计 题目：题目：可视化弗洛伊德最短路径可视化弗洛伊德最短路径 班级：计算机班级：计算机 12 级级 日期：日期：2014 年年 1 月月 16 日日 一实习目的 通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、 编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及 操作方法，为进一步的应用开发打好基础。 二问题描述 设计、 实现随机或手动建立一个有向图， 可以使用弗洛伊德算法输出有向图中节点之间 最短路径及权值，并把有向图和弗洛伊德算法得出的最短路径及最小权值可视化。 三需求分析 （1） 可随机建立有向
2、图，并在屏幕上使图可视化； （2） 可手动建立有向图，添加节点、删除节点、移动节点、添加边、删除边、设置 权值，并在屏幕上使图可视化； （3） 对已建立的有向图实现弗洛伊德算法找出最短路径， 并在屏幕上使最短路径及 最小权值矩阵可视化； 四概要设计 系统中子程序及功能要求： 数据对象 V：一个集合，该集合中的所有元素具有相同的特性 数据关系 R：R=VR VR=|P(x,y)(x,y 属于 V) （1） OnButtonCreategraph()/随机建图按钮； （2） OnButtonHuman()/手动建图按钮； （3） OnButtonAddvertex()/添加节点按钮； （4） On
3、ButtonDeletevertex()/删除节点按钮； （5） OnButtonMovevertex()/移动节点按钮； （6） OnButtonAddedge()/添加边按钮； （7） OnButtonDeleteedge()/删除边按钮； （8） OnButtonSetweight()/设置权值按钮； （9） OnButtonFloyd()/弗洛伊德算法按钮； （10） DrawDGRandom(TCenterPoint, pDC)/随机建图； （11） DrawDiGraph(CDC *pDC)/图可视化； （12） DrawVexs(CDC *pDC)/节点可视化； （13） Dra
4、wEdges(CDC *pDC)/边可视化； （14） InitHand()/存储节点； （15） CreateDGHand(CPoint centerpoint)/手动建图； （16） AddVertsHand()/添加节点； （17） DeleteVex(CPoint vPoint)/删除节点； （18） AddEdgesHand()/添加边； （19） DeleteEdge(CGraphVertex* pBeginVex, CGraphVertex* pEndVex)/ 删除边； （20） SetEdgeWeightHand ()/设置权值； （21） Floyd()/弗洛伊德算法； （
5、22） DrawFloyd(CDC *pDC)/弗洛伊德可视化； 各程序模块之间的调用关系（子程序编号见上） ： 主函数可调用子程序 1、2、3、4、5、6、7、8、9 子程序 1 可调用子程序 10 子程序 2、3 可调用子程序 14、15 子程序 3 可调用子程序 16 子程序 4 可调用子程序 17 子程序 6 可调用子程序 18 子程序 7 可调用子程序 19 子程序 8 可调用子程序 20 子程序 9 可调用子程序 21 子程序 10 可调用子程序 11 子程序 16 可调用子程序 12 子程序 17 可调用子程序 12、19 子程序 18、19、20 可调用子程序 13 子程序 2
6、1 可调用子程序 22 五测试分析 按照附录中的测试数据，得出如下测试、分析结果： 1. 建图功能： （1） 随机建图：随机去顶节点的个数与位置及节点之间边的连接、方向与权值大小， 并在屏幕上输出图结构； 测试结果：可随机输出一有向图。 （2） 手动建图： a、 添加节点：手动添加节点并放在任意位置； 结果：可在任意位置添加节点。 b、 删除节点：手动删除一节点； 结果：只能按顺序删除，无法任意删除，有待改进。 c、 移动节点：可将某一节点移动到其他位置； 结果：尚未实现。 d、 添加边：在任意两个不同节点之间添加任意方向的边； 结果：可以实现添加任意方向的边。 e、 删除边：删除任意一条已存在的边； 结果：可以删除任意一条存在的边。 d、 设置权值：给任意一条已存在的边赋予权值； 结果：可以赋予权值； （3） 弗洛伊德算法：对已确定的有向图通过 Floyd 算法找到任意两点间的最短路径 并在屏幕上输出最短路径及权值的矩阵； 结果：可正确输出路径及权值。 六使用说明 1运行程序，首先出现主界面。
