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