数据结构实验报告三

《数据结构实验报告三》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划数据结构实验报告三　　电子科技大学　　实验报告　　课程名称：　　学生姓名：　　学号：　　点名序号：　　指导教师：　　实验地点：实验时间：　　XX-XX-2学期　　信息与软件工程学院　　实验报告(三)　　学生姓名：陈*浩学号：************指导教师：钱**　　实验地点：科研教学楼A508实验时间：　　一、实验室名称：软件实验室　　二、实验项目名称：数据结构与算法—图　　三、实验学时：4　　四、实验原理：目的-通过该培训员工可对保安行业

2、有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　Kruskal算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝，令G的最小生成树为T，其初态为T＝，即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通

3、分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。　　如教材153页的图(a)所示，按照Kruskal方法构造最小生成树的过程如图所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个结点的生成树，有n－1条边，故反复上述过程，直到选取了n－1条边为止，就构成了一棵最小生成树。　　五、实验目的：　　本实验通过实现最小生成树的

4、算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal算法。通过练习，加强对算法的理解，提高编程能力。　　六、实验内容：　　假定每对顶点表示图的一条边，每条边对应一个权值；　　输入每条边的顶点和权值；　　输入每条边后，计算出最小生成树；目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　打印最小生成树边的顶点及权值。　　七、实验器材：　　八、数据结构

5、及程序　　#include　　#include　　#include　　#definemaxnode17　　#definemaxedgs120　　charFileAddress[100]="F:\";//全局通用文件地址　　typedefstruct{　　intvex;//顶点信息　　intgno;//顶点所在的连通分量编号　　}TVex,*TpVex;　　typedefstruct{　　intvhead,vtail;//边依附的两顶点　　intwght;//边的权值　　intflag;//0：未加入MST;1：已入选;-1：已删除　　}TEdge,*

6、TpEdge;　　typedefstruct{　　TpVexVexList;//顶点数组　　TpEdgeEdgeList;//边数组　　intnvex,nedge;//顶点数量，边数量目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　}TGraph,*TpGraph;　　intRead_File(charFileAdress[],TpGraphGraph);//读

7、取文件并建立图　　intKruskal_Tree(TpGraphGraph);//构建最小生成树并输出边信息　　voidAss_Con_Comp(TpGraphGraph,intVex1,intVex2);//使一个连通分量内的所有顶点的分量值相同　　voidOutput_Graph(TpGraphGraph);//输出图的结构　　PC机一台，装有C/C++语言集成开发环境。　　intmain(void)　　{　　TGraphG;　　intk;　　charchoose='y';　　printf("--------图与Kruskal算法---------

8、-");　　while(choose=='y')　　{　　printf("请输入信息文件地