2022年运筹学课程方案报告书最小生成树问题 .pdf

《2022年运筹学课程方案报告书最小生成树问题 .pdf》由会员分享，可在线阅读，更多相关《2022年运筹学课程方案报告书最小生成树问题 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、个人资料整理仅限学习使用运筹学课程设计报告书专业班级学号姓名 LMZZ 日期 2018.09.01 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页个人资料整理仅限学习使用设计题目：最小生成树问题设计方案：本设计是在 C语言环境下运行的，主要有: minitree_KRUSKAL(此函数包含几个算法有对树的邻接矩阵的构造，数据的输入，克鲁斯卡尔算法 定义并输出邻接矩阵。主程序：int main( minitree_KRUSKAL(。 。ljjzprint(n。函数调用） 方案实施：?1、定义结构体以及各个变量；? 2 、数据的输入

2、；? 3 、采用克鲁斯卡尔算法求出该图的最小生成树；? 4 、采用邻接矩阵做储存结构创建图；? 5 、在主函数中分别调用以上各个函数，最终实现设计目的。克鲁斯卡尔算法的表示：while (i min=INFINITE。for (j=0。j if (ej.weight min=ej.weight。 sum+=min。k=j 。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页个人资料整理仅限学习使用if (tek.vexh.jihe!=tek.vext.jihe ek.flag=1。for (j=1。j if (tj.jihe=te

3、k.vext.jihe tj.jihe=tek.vexh.jihe。tek.vext.jihe=tek.vexh.jihe。i+ 。 else ek.flag=2。 邻接矩阵的表示：void ljjzprint(int n/*定义并输出邻接矩阵 */ int i,j。for(i=1。i for(j=1。j printf(%dt,adjmatrixij。printf(n。 int main( minitree_KRUSKAL(。函数调用printf(输出邻接矩阵是： n 。ljjzprint(n。输出矩阵return 0。 调试过程：原设计在定义输出矩阵函数时，没有形参，在调用时必须输入树的定点

4、数这和前面的函数在输入树的数据时重复操作，为了避免重复如果这个函数添加一个参数为 n 的形参，再 main 函数调用 minitree_KRUSKAL(。后 n 为定值， n 为了在 ljjzprint(n中为已知量则需在程序的开头定义一个全局变量n 即可。在求最小生成树的代价时，因为其顶点的权值时变的故重新定义个变量sum ，以实现其权值的相加然后输出。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页个人资料整理仅限学习使用结果与结论：测试结果：顶点为： a，b，c, d , e 其标号分别为 1，2，3，4，5Vexh 和 v

5、ext 分别为边的两端顶点， weight为边的权值运行如下 : 结论：通过实际操作，运用简单的C 语言程序编程能比较清楚和简单的把运筹学当中的相对抽象的最小树问题表现出来。具体分工：我主要负责程序后期的修改以及调试，才能使整个程序正常的运行出来。还有对 ppt 的制作和课程设计书整体的把握！收获与致谢：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页个人资料整理仅限学习使用紧张而又忙碌的课设学习终于结束了，在本次课设中我们也取得了相对很大的成就，通过本次课程设计我们也学到了很多，它增加了我们编程软件的兴趣，在具体操作中对所学的C

6、语言的理论知识得到了巩固，达到实训的目的也发现了自己的不足之处，在以后的上机中应更加注意，同时体会到了C语言具有语句简洁，使用灵活，执行效率高等特点，并且通过此次运筹学课程设计，我们通过C语言将其中抽象的最小树问题比较直观的变现出来，掌握了求最小树问题的克鲁斯卡尔算法以及邻接矩阵的构造，特别是对C 语言中数组和循环有了深刻的了解。通过实际操作将C语言编程和运筹学有机的结合起来，学会了C语言编程的基本步骤和基本方法，开发了自己的逻辑思维能力，培养了分析问题和解决问题的能力。在此衷心感谢学院安排这次课设，让我们又多了一次学习交流的机会，更好的巩固了所学的知识，拓展了知识面。本次课设能取得成功，要感

7、谢老师的帮助和指导。在课设期间老师帮助我们分析思路，提供方法，才使得我们的程序做的更加的完善。其次是要感谢和我同组的同学感谢对方对本次课设的付出。参考文献：运筹学教程 第三版）胡运权主编C程序设计 第三版）谭浩强编著C程序设计题解与上机指导第三版）谭浩强编著附件：本设计的详细代码如下：#include #define M 30 #define INFINITE 9999 #define n0 100 int adjmatrixn0+1n0+1。int n。typedef struct 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9

8、页个人资料整理仅限学习使用 char data 。int jihe。VEX。typedef struct int vexh,vext。int weight。int flag。EDGE 。void minitree_KRUSKAL( int i,m,min,k,j。int sum=0 。VEX tM 。EDGE eM。printf(最小生成树问题 n 。printf(程序设计者：冯云广，吕金刚n 。printf(输入顶点数及边数 : 。fflush(stdin。scanf(%d%d,&n,&m。 /n个点 m 条边printf(输入各个顶点名称 :n 。for (i=1。i printf(t%d

9、.data=:,i。 /输入顶点字符getchar( 。fflush(stdin。 /清除缓存scanf(%c,&ti.data。 / 输入点对应的字符ti.jihe=i。 printf(输入两个不同顶点及其边权:n 。for(i=1。i for(j=1。j adjmatrixij=0。for (i=0。i printf(vexh,vext,weight:。fflush(stdin。scanf(%d%d%d,&ei.vexh,&ei.vext,&ei.weight。if(ei.weight0 adjmatrixei.vexhei.vext=1。adjmatrixei.vextei.vexh=1

10、。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页个人资料整理仅限学习使用 ei.flag=0。 i=1 。while (i min=INFINITE。for (j=0。j if (ej.weight min=ej.weight。k=j 。 if (tek.vexh.jihe!=tek.vext.jihe ek.flag=1。for (j=1。j if (tj.jihe=tek.vext.jihe tj.jihe=tek.vexh.jihe。tek.vext.jihe=tek.vexh.jihe。i+ 。 else ek.flag

11、=2。 printf(克鲁斯卡尔算法及代价如下：n 。for (i=0。i if (ei.flag=1 printf(%d,%d %dn,ei.vexh,ei.vext,ei.weight。 sum+=ei.weight。 printf(最小生成树的权是： 。printf(%dn,sum。 void ljjzprint(int n/*定义并输出邻接矩阵 */ int i,j。for(i=1。i 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页个人资料整理仅限学习使用 for(j=1。j printf(%dt,adjmatrixij。printf(n。 int main( minitree_KRUSKAL(。printf(输出邻接矩阵是： n 。ljjzprint(n。return 0。指导教师评语：课程设计报告成绩：，占总成绩比例：20% 答辩成绩：，占总成绩比例：30% 课程设计作品，占总成绩比例：50% 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页个人资料整理仅限学习使用总成绩：。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页