北京信息科技大学软件课程设计

《北京信息科技大学软件课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京信息科技大学计算机软件基础课程设计题目：最小生成树——最优通信网学院：信息与通信工程学院专业：通信工程专业学生姓名：XXXX班级/学号通信14XX/2014XXXXX指导老师：李振松，曹林起止时间：9月24日至10月30日摘要95摘要题目6最小生成树——最优通信网（难度系数10，全部做出给100分）主要内容1、如果以无向图表示n个城市之间的通信网络的建设规划，顶点表示城市，边上权值表示该线路的造价，设计一个方案，使这个通信网的总造价最低。2、学会建立图的邻接表，理解图的基本概念。3、学会编写DLL函数。4、掌握建立最小生成树的Prim算法、Krus

2、kal算法。5、掌握C++编程环境的基本调试方法，熟练使用可视化C++编程工具。6、提示：在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，使总的耗费最少，构成最优通信网呢？这个问题本质上就是构造连通图的最小代价生成树。设计要求1、上交课程设计的书面材料，要求打印。包括课程设计任务书、主要内容，源程序，对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。2、上交电子版源程序，包括邻接表建立程序、Prim算法、Kruskal算法。3、自己编写

3、一个求素数函数，把它书写成一个动态链接库形式，并在主函数中调用它。尝试把自己编写的程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用函数生成的EXE执行文件。主要仪器设备计算机一台，安装WindowsXP操作系统、MicrosoftVisualC++6.0、MSDNLibrary。主要参考文献[1]侯俊杰.深入浅出MFC(第二版)[M].武汉：华中科技大学出版社,2001.[2]谭浩强.C程序设计（第二版）[M].北京：清华大学出版

4、社,1999..[3]孟彩霞.计算机软件基础[M].陕西：西安电子科技大学出版社,2003.[4]严蔚敏,吴伟民.数据结构[M].北京：清华大学出版社,2005.课程设计进度计划（起止时间、工作内容）选做图的遍历和最小生成树题目的同学，2人1组，1人做图的遍历，1人做最小生成树，整个课程设计共20学时，具体进度如下：4学时了解课题背景，选题，学习DLL，学习图的基本概念。4学时编写邻接表建立程序。4学时最小生成树Prim算法。4学时最小生成树Kruskal算法。4学时调试程序，答辩。课程设计开始日期见选题说明课程设计完成日期见选题说明课程设计实验室名称

5、计算中心机房地点健翔桥校区95摘要摘要最小生成树——最优通信网对于这个题目，首先，我想到的是如何来构建一个通信网，也就是如何构建一张无向图，当然图在计算机内的存储有很多种，我这里应用了邻接表来存储无向图，但是后来又将其转换成邻接矩阵和边集数组的形式来存储，一方面我想了解比对一下这几种存储方式，另一方面也使得接下来的prim算法和Kruskal算法的处理变得容易，再说一下这两个最小生成树的算法，prim算法相比较而言更适合较多节点的图，而Kruskal算法则更适合于较少节点的图，prim算法给我的感觉更像是顺藤摸瓜，它先有一个起始点，之后顺着这个点往下遍

6、历，当找到最优路径时，我的想法是就把他们合为一个整体，依次将整个图的最优路径遍历出来，而Kruskal算法我感觉稍稍有一点不足，就是需要对权值进行排序，这在很多节点时就显得很不足，但这个算法对于节点很少的图来说非常好，基本上结果就是那个排好序的边集数组的前几项，当然如果形成环，就再加几项，我想这种情况也不是特别特别常见，因此很多时候不需要完整遍历整个图，所以相对较好一些，最后说一下输出，我这里采用邻接表和链接矩阵两种方式来做输出。95参考文献目录任务书1摘要2目录3正文4参考文献11源代码1295参考文献intmain()函数用途：主函数是这个工程的入

7、口函数，函数调用菜单函数，开始整个程序的运行voidmenu();函数用途：菜单函数，询问用户接下来要做的事情，并调用响应的功能函数voidaddHeadNode();函数用途：添加头节点voidaddNode();函数用途：添加普通节点voidchange();函数用途：将邻接表转换成邻接矩阵voidcompleteNode();函数用途：完成输入，输出当前的邻接表和邻接矩阵voidMiniSpanTree_Prim();函数用途：prim算法计算输出最优路径intFind(int*parent,intf);函数用途：Kruskal算法判断是否构成环

8、路voidMiniSpanTree_Kruskal();函数用途：Kruskal算法计算输出最