构造可以使n个城市连接最小生成树.doc

西北农林科技大学信息工程学院 C语言与数据结构实习报告 题 目：构造可以使n个城市连接的最小生 成树 学 号 2009012841 姓 名 孙千翱 专业班级 信管091班 指导教师 王娟勤 唐晶磊 实践日期 2010年7月19日-7月30日 目 录 一、综合训练目的与要求 3 二、综合训练任务 3 三、总体设计 4 四、详细设计说明 4 五、调试与测试 6 六、实习日志 8 七、实习总结 9 八、附录：核心代码清单 9 一、综合训练目的与要求 按照数据结构、C程序设计教学计划的安排，7月19日到30日，开展为期两周的数据结构与C程序设计课程设计。该课程设计是数据结构、C语言程序设计课程的重要实践教学环节，是一次全面的系统分析与设计能力的培养，是实现该专业学生总体培养目标的重要教学环节。使学生通过了解学科领域的发展动向，培养数据结构与程序设计的基本思想，独立分析和解决实践问题的能力，提高和锻炼学生动手能力。 实习的基本要求 (1)结合实践，学生选题与教师指定题目相结合，老师对题目的合理性、学生分组进行确认； (2)对所选题目，运用面向过程的分析与设计方法，给出系统分析与设计的结果，要求必须要运用数据结构课程中相关的基本知识； (3)选择熟悉的开发工具，用C语言完成系统实现和测试，掌握系统实现和测试的方法，必须要有详尽的程序注释； (4)撰写开发文档，培养编写系统分析与设计文档的水平。 二、综合训练任务 主要任务： 给定一个地区的n城市间的距离网，用Prim算法或算法建立最小生成树，并计算得到的最小生成树的代价。1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边） 3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于中。. 从p中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器累加1。 c. 从E中删除此最小边，转b继续执行，直到k=n-1,d. 判断是否构成回路的方法： 设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中或者两个顶点都不在S中，则不够成回路。 克鲁斯卡尔算法生成最小生成树的过程 （3）防止不能构成最小生成树的图 为避免输入的图构成的不是连通图，设计了judge ( ) 函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆（PRIM）算法，经过改编，形成了新的函数。 五、调试与测试 以一个6个城市、10条边的网络图为例进行测试 16 20 11 5 19 6 22 14 9 18 网络图 GE = 邻接矩阵 1、开始画面 2、输入信息 设置两顶点之间无边时∞权值为10000 3、数据处理 (1)、判断能否构成最小生成树 （2）、遍历所有城市生成最小生成数 16 11 5 6 18 生成的最小生成树 （3）、退出 六、实习日志 7月19日 在查阅有关资料和老师的指导下，我对要做的题目有了初步的了解，并能掌握了在网上查阅资料的技能。今天的主要任务是写（C语言与数据结构）的实施计划书， 通过写实施计划书，我掌握了一些发送电子邮件的技巧。 7月20日 昨天已经对所搞的题目有一定的了解，今天主要是进行编程，调试程序。通过自己动手才知道，自己的编程能力还是有待提高的。 7月21日 今天在调试的过程抱着好玩的心态写了一句代码；system(“color 4A”)；使原本黑黑的界面变成了多种好看的颜色。嘿嘿……现在才知道写代码好好玩。 7月22日 对克鲁斯卡尔进一步的研究也探索，对具体的步骤进行分析了一下，总的来说对这克鲁斯算法设计还是有较高的兴趣。 7月23日 今天尝试用克鲁斯卡尔算法求最小生成树，刚开始的时候错误一大堆，看者这些错误，心情老郁闷了。但我还是不能放弃，像蜗牛一样，