1、沈阳航空工业学院课程设计报告- 1 -数据结构课程设计报告撰写要求（一）纸张与页面设置1采用国际标准 A4 型打印纸或复印纸，纵向打印。2页边距：上 3.5cm、下 2.5cm、左边距 3.0cm，右边距 2.5cm。3页眉 2.5cm、页脚 1.8cm、对称页边距。（二）页眉“沈阳航空工业学院课程设计报告” ，五号楷体，居中。（三）页脚标页码，五号宋体，居中。（四）题目、摘要、关键词题目：小二号黑体，居中。（五）标题一级标题，三号粗宋体，居中，用“1 ” 、 “2 ”、 “3 ”等表示序号。二级标题，小三号粗宋体，左对齐，用“1.1” 、 “1.2”、 “1.3”等表示序号。三级标题，四号粗
2、宋体，左对齐，用“1.1.1” 、 “1.1.2”、 “1.1.3”等表示序号。（六）正文小四号宋体，两端对齐，1.5 倍行距。（七）图、表 1表头包括：表标识及表名两部分，表头在表上，居中，用五号宋体字。2图头包括：图标识及图名两部分，图头在图下，居中，用五号宋体字。（八）参考文献格式：序号作者.译者.书名.版本.出版社，出版时间（九）报告封页及模版见下页沈阳航空工业学院课程设计报告- 2 -沈阳航空工业学院课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：PRIM 算法求最小生成树院（系）：计算机学院专 业：计算机科学与技术班 级： 7401102班学 号： 2007040
3、11030姓 名：指导教师： 郑志勇沈阳航空工业学院课程设计报告 I目 录沈阳航空工业学院 .- 2 -1 需求分析 .11.1 题目内容及要求 .11.2 题目分析 .12 系统设计 .32.1 数据结构设计 .32.2 函数设计 .42.2.1 系统流程 .5H u i t u ( )G r a p h i c V e r ( )p r i m （）m a i n ( ) 结束图 2.2.1 系统流程 .52.2.2 PRIM 函数流程 .52.2.3 Huitu 函数流程 .62.2.4 GraphicVer 函数输出邻接矩阵 .63 调试分析 .73.1 调试初期 .73.2 调试中期
4、 .73.3 调试后期 .94 测试及运行结果 .104.1 欢迎界面 .104.2 获取输入，绘制无向图 .104.3 输出邻接矩阵 .134.4. 演示 PRIM 算法生成最小生成树 .134.5 用户退出 .14参考文献 .15附 录（关键部分程序清单） .16沈阳航空工业学院课程设计报告 II沈阳航空工业学院课程设计报告11 需求分析1.1 题目内容及要求以合适方便的方式输入一个带权值的无向图，采用合适的存储结构存储该无向图。然后根据 PRIM 算法求该无向图的最小生成树并输出。要求：1.输入无向图的方法尽量简单方便2.要能够形象方便地观察无向图的图形结构3.要能够形象地演示 PRIM
5、 算法求最小生成树的过程1.2 题目分析刚拿到题目，乍看一下题目很简短，貌似很简单，但是细看之后就发现了很多隐藏在简短语句后的更深一层次的要求。首先是“以合适方便的方式输入” ，短短十个字就向你提出了两方面要求：首先是“输入” ，即代表你最好可以得到一种通用的算法让你对一定范围内的数据进行运算后从而得到正确的结果；“合适方便”即提示你要从输入方便且有利于运算的输入数据的方法；采用合适的存储结构必然是本次课设当之无愧的重点，亦是此题目的第三方面要求；最后就是用 PRIM 算法求无向图的最小生成树。PRIM 算法在理解与实现方面不是很困难，但要求能够形象的演示该算法就不是那么简单了。无论从算法角度
6、，还是从输入方便、存储安全角度，数组都是此次课设的不二选择，即采用邻接矩阵的存储方式来存储无向带权图。虽然邻接表的动态存储可以令该算法使用更大规模的数据并在一定范围内比数组更加节省空间并有更高的效率，但此次课设另一个重点就是演示算法而非真正的应用于实际问题，所以只需要较少的数据量来完成 PRIM 算法的演示即可。故数组的便于操作及更加稳定、方便的优势便凸显出来。在画图这个问题上，我曾一度找错了方向。刚拿到题目时，我只是望文生义的认为我需要演示的是最小生成树一步一步的演示过程，这让我一度选择 VC 6.0沈阳航空工业学院课程设计报告2中的 MFC 来演示过程。但后来，当我因为 MFC 当量调用
7、WINDOWS 的程序并有较多的头文件而焦头烂额的时候，重读课设要求的时候我才发现，过于注重细枝末节的我竟没有抓住此题目真正要求！“模拟 PRIM 算法最小生成树的过程”即是让你显示 PRIM 算法在更接近计算机可以理解的方式上显示其具体过程。Turbo C 的超强的图像处理让我明白，它就是我这次课设的系统环境了。沈阳航空工业学院课程设计报告 32 系统设计2.1 数据结构设计对于无向图的任何操作，无疑都必须依赖于数据的存储结构。这里的存储结构不仅仅指的是数据在计算机中的物理内存，更多的是抽象程度更高的抽象数据结构。图的存储结构主要有两种:邻接矩阵和邻接表。邻接表以一个一维数组作表头节点存储图
8、的顶点，然后利用表头引出所有以该点为箭尾的邻接边的信息；而邻接矩阵则是单独建立一个一维数组来存储顶点的信息，并以顶点的个数来建立一个相应的 N 阶对称矩阵，以二维数组存储单元来存储相应边的权值。由于 PRIM 算法需要多次修改 closeedge 中的 adjvex 和 lowcost 值，且此次数据规模较小，只需达到演示部分数据即可，所以统一采用数组的存储结构，即亦采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作。邻接矩阵的抽象数据结构定义：#define INFINITY INT_MAX /最大值#define MAX_ERTEX_NUM 20 /最大顶点数typedef enum
9、DG , DN , UDG , UDN GraphKind;/ 有向图，有向网，无向网，无向图typedef struct Arc CellVRType adj ; / VRType 是顶点关系的类型。对无权图，用 1 和0 表示相邻否；对/带权图则为权值类型InfoType * info; /该弧相关信息的指针ArcCell , AdjMatrix MAX_VERTEX_NUMMAX_VERTEX_NUM；Typedef struct VertexType vexs MAX_VERTEX_NUM ; /顶点向量AdjMatrix arcs ; / 邻接矩阵int vexnum , arcnu
10、m ; /图的当前顶点数和弧数沈阳航空工业学院课程设计报告 4GraphKind kind ; / 图的种类标志Mgraph ;2.2 函数设计本系统所使用的函数见表 2.2.1表 2.2.1 本系统所使用的函数函数名称 函数原型 功能描述main() int main(void) 系统调用主函数Huiru() Void Huitu () 绘制无向图GraphicVer()void GraphicVer(Graph *G)输出邻接矩阵prim() void prim(Graph *G) PRIM 算法演示本系统所调用函数调用的关系见图 2.2.2H u i t u ( )G r a p h i
11、 c V e r ( )p r i m （）m a i n ( ) 结束图 2.2.2 本系统的函数调用关系2.2 关键流程流程图能直观和系统地把主函数的各个执行步骤和调用的子函数以及调用先后表示出来，子函数中也有调用其他子函数的情况，画出子函数的流程图能清楚地看出子函数中各步语句的执行，下面是关于主函数流程和关键的子函数流程图的直观表示。沈阳航空工业学院课程设计报告 52.2.1 系统流程H u i t u ( )G r a p h i c V e r ( )p r i m （）m a i n ( ) 结束图 2.2.1 系统流程2.2.2 PRIM 函数流程声明l o w c o s t
12、, c l o s e st 数组初始化 l o w c o s t 并标记 l o w c o s t 1 在 l o w c o s t 中寻找最小值并记录其对应点标记上一顶点开始更新 l o w c o s t 结束输出两数组值输出两数组值表 2.2.2 PRIM 函数流程沈阳航空工业学院课程设计报告 62.2.3 Huitu 函数流程开 始图 形 初 始 化定 义 变 量获 取 用 户 输 入坐 标 、 顶 点 在 相 应 位 置 绘 制 圆并 涂 上 颜 色 ， 在 圆心 处 添 加 顶 点获 取 用 户 输 入坐 标 、 顶 点判 断 用 户 输入 是 否 为 0退 出表 2.2.3 Huitu 函数流程2.2.4 GraphicVer 函数输出邻接矩阵清屏开始输入顶点数 、 边数按顶点数初始化二维数组按边数重复获取边权值输入邻接矩阵内输出矩阵内的权值或无穷大结束图 2.2.4 GraphicVer 函数输出邻接矩阵
