《构造可以使n个城市连接的最小生成树 (2)》由会员分享，可在线阅读，更多相关《构造可以使n个城市连接的最小生成树 (2)（14页珍藏版）》请在金锄头文库上搜索。
1、西北农林科技大学信息工程学院C 语言与数据结构实习报告题 目：构造可以使n个城市连接的最小生成树学 号 2009012841姓 名 孙千翱专业班级 信管 091 班指导教师 王娟勤 唐晶磊实践日期 2010 年 7 月 19 日-7 月 30 日2目 录一、综合训练目的与要求 .3二、综合训练任务 .3三、总体设计 .4四、详细设计说明 .4五、调试与测试 .6六、实习日志 .8七、实习总结 .9八、附录：核心代码清单 .93一、综合训练目的与要求按照数据结构、C 程序设计教学计划的安排，7 月 19 日到 30 日，开展为期两周的数据结构与 C 程序设计课程设计。该课程设计是数据结构、C 语
2、言程序设计课程的重要实践教学环节，是一次全面的系统分析与设计能力的培养，是实现该专业学生总体培养目标的重要教学环节。使学生通过了解学科领域的发展动向，培养数据结构与程序设计的基本思想，独立分析和解决实践问题的能力，提高和锻炼学生动手能力。实习的基本要求(1)结合实践，学生选题与教师指定题目相结合，老师对题目的合理性、学生分组进行确认；(2)对所选题目，运用面向过程的分析与设计方法，给出系统分析与设计的结果，要求必须要运用数据结构课程中相关的基本知识；(3)选择熟悉的开发工具，用 C 语言完成系统实现和测试，掌握系统实现和测试的方法，必须要有详尽的程序注释；(4)撰写开发文档，培养编写系统分析与
3、设计文档的水平。二、综合训练任务主要任务：给定一个地区的 n 个城市间的距离网，用 Prim 算法或 Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少 6 个城市，10 条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。三、总体设计1 该程序的主要功能：能实现根据输
4、入城市的信息可以判断该城市间的距离网4开始 输入城市信息是否为连通图？求最小生成树初始化是否构成回路？将最小生成树边集合打印出最小生成树的权值与最小生成树的代价退出是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。2 该城市间的距离网用邻接矩阵表示3 用克鲁斯卡尔（Kruskal）算法建立最小生成树 四、详细设计说明 1 该程序的主要功能：能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。该程序的模块结构功能图及主要函数如下：5a) int main ( ) /主程序b) int menu ( )
5、 /菜单函数c) void create ( ) /输入城市信息函数d) void judge ( ) /判断是否能够生成最小生成树函数e) void display( ) /打印输出f) void set ( ) /初始化 pre,rank函数g) void find ( ) /判断是否构成回路函数h) void Union ( ) /将能构成最小生成树的边添加到一个集合l） void Krushal( ) /克鲁斯算法求最小生成树2该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法） ，利用两个数组来存储一个图。用 a i j数组，利用邻接矩阵方式来储存城市与城市间信息 。3
6、 算法设计（1）克鲁斯卡尔算法思想基本描述：假设连通图 N=（V，E） ，则令最小生成树的初始状态为只有 n 顶点而无边的非连通图 T=(V, )，图中每个顶点自成一个连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代价最小的边。以此类推，直至 T 中所有顶点都在同一个连通分量上为止。（2）克鲁斯卡尔算法设计a. 设置计数器 E，初值为 0，记录已选中的边数。将所有边从小到大排序，存于 p 中。b. 从 p 中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生
7、成树中，计数器 E 累加 1。 c. 从 E 中删除此最小边，转 b 继续执行，直到 k=n-1, 算法结束 d. 判断是否构成回路的方法： 设置集合 S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在 S 中，若是，则表示构成回路，否则，若有一个顶点不在 S 中 或者两个顶点都不在 S 中，则不够成回路。6克鲁斯卡尔算法生成最小生成树的过程（3）防止不能构成最小生成树的图为避免输入的图构成的不是连通图，设计了 judge ( ) 函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆（PRIM）算法，经过改编，形
8、成了新的函数。五、调试与测试以一个 6 个城市、10 条边的网络图为例进行测试1620 11 519 6 22 14 918网络图GE = 95184621905619邻接矩阵1 2164 5371、开始画面2、输入信息设置两顶点之间无边时权值为 100003、数据处理(1)、判断能否构成最小生成树（2） 、遍历所有城市生成最小生成数816 11 5618生成的最小生成树（3） 、退出六、实习日志7 月 19 日 在查阅有关资料和老师的指导下，我对要做的题目有了初步的了解，并能掌握了在网上查阅资料的技能。今天的主要任务是写（C 语言与数据结构）的实施计划书， 通过写实施计划书，我掌握了一些发送
9、电子邮件的技巧。 7 月 20 日昨天已经对所搞的题目有一定的了解，今天主要是进行编程，调试程序。通过自己动手才知道，自己的编程能力还是有待提高的。7 月 21 日今天在调试的过程抱着好玩的心态写了一句代码；system(“color 4A”)；使原本黑黑的界面变成了多种好看的颜色。嘿嘿现在才知道写代码好好玩。7 月 22 日对克鲁斯卡尔进一步的研究也探索，对具体的步骤进行分析了一下，总的来说对这克鲁斯算法设计还是有较高的兴趣。7 月 23 日今天尝试用克鲁斯卡尔算法求最小生成树，刚开始的时候错误一大堆，看者这些错误，心情老郁闷了。但我还是不能放弃，像蜗牛一样，一个错误一个错误改。7 月 24
10、 日7 月 25 日 休息日。15326497 月 26 日经过两天的修改程序，用克鲁斯卡尔算法求最小生成树的程序修改得差不多了。看着自己辛苦开发出来程序，还挺高兴的，虽然程序还存在问题，但毕竟是自己开发出来的。嘿嘿。7 月 27 日今天主要是开发一个输入城市信息的函数，在网上查了很多相关的资料，最终还是确定用 Create( )函数。因为这个函数相对比较好用，容易掌握。7 月 28 日经过几天的努力，对构造可以 n 个城市连接的最小生成树的系统程序大体上完成了，还有几个小错误，但程序基本的结构与算法已经设计好了。虽然我对这个系统程序的功能不是很满意，但也没办法，技术水平就这样子。自己以后会越
11、加努力，设计出更好的系统程序。7 月 29 日今天上午的时间用来制作演讲 PPT,下午的时间用来答辩，由于表达能力不好，在演讲时，完蛋了。哎以后要多加练习了。7 月 30 号今天是实习的最好一天了，实习的日子里有很多感慨，在编写程序上有了一定的进步。废话也就不多说了。以后的日子里，一定要像一只蜗牛，慢慢的成长，步步高升。嘎嘎七、实习总结通过两周的数据结构与 C 语言课程实训，我不仅对图的概念有了一个新的认识，而且对算法和 C 语言有了更深的理解，在学习了数据结构这门课后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉它有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也是说明
12、了想要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点与顶点之间的联系，图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例。在这次求可使构成 n 个城市的最小生成树的程序设计中，我采用了 a i j数组利用邻接矩阵方式来储存城市与城市间信息，再利用经典的克鲁斯克尔算法求得了最小生成树。在这次课程设计中，我明白了编写一段代码，我们不仅要考虑它的可行性，更应该考虑它的算法复杂度，运行效率。做同一件事，一万个人有一万种做法，换而言之，一万个人写一段代码实现同一个功能可以得到一万段代码。由此，我们可以看出做一10件事要精益求精，多加斟酌。八、附录：核心代码清单#include #include #include #define max 20#define MAX_LNT 10typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/int str; /*起点*/int end; /*终点*/int dis;/*距离*/node;node pmax,temp; /*p 记录城市信息*/int pre100,rank100;/*用于判断是否构成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n 表示城市个数，a
