2022年《数据结构》课程设计报告N个城市最小生成树 .pdf

《2022年《数据结构》课程设计报告N个城市最小生成树 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构》课程设计报告N个城市最小生成树 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计报告学号101842110 姓名*8 班级软件 1042 指导教师* 安徽工业大学计算机学院2012年 6 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 目录构造 n 个城市连接的最小生成树（1）问题描述 （2）需求分析及设计思路 （3）数据结构定义 （4）系统功能模块介绍 （5）源程序 （6） 运行结果及调试分析 （7）课程设计总结 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

2、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 二构造n 个城市连接的最小生成树（1）问题描述一个地区的 n 个城市间的距离网，用Prim 算法或 Kruskal算法建立最小生成树， 并计算得到的最小生成树的代价。基本要求：1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2) 表示城市间距离网的邻接矩阵( 要求至

3、少 6 个城市，10 条边) （1）需求分析及设计思路首先解决如下5 个问题：(1)、如何选择存储结构去建立一个带权网络。(2)、如何在所选存储结构下输出这个带权网络。(3)、如何实现 PRIM 算法的功能。(4)、如何从每个顶点开始找到所有的最小生成树的顶点。(5)、如何输出最小生成树的边及其权值。此问题的关键在于如何实现PRIM 算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

4、第 3 页，共 11 页 - - - - - - - - - 首先我们对问题进行大致的概要分析：这个问题主要牵涉到通过PRIM 的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=（V，E ）是连通网， TE是 N 上最小生成树中边的集合。算法从U=u0( u0V),TE= 开始，重复执行下述操作：在所有uU,vV-U 的边（ u,v）E 中找一条代价最小的边（u0,v0） 并入集合 TE， 同时 v0并入 U， 直至 U=V 为止。此时 TE 中必有 n-1 条边，则 T=（V，E ）为 N 的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据

5、型， 然后输入每一条边的信息， 即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始省城的最小生成树。题目要求以及达到目标： 题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树，并且输出各边的权值。（3）数据结构定义#include #include #define INFINITY 30000 /* 定义一个权值的最大值 */ #define MaxVertexNum 30 /* 图的最大顶点数为30 */ typedefstruct /intvert

6、exsMaxVertexNum; /*顶点表 */ int arcsMaxVertexNumMaxVertexNum; /* 邻接矩阵，即边表 */ intvertexNum,edgeNum; /* 图的当前顶点数和边数 */ MGraph; /*Graph是以以邻接矩阵存储的图类型*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - typedefstruct intadjvertex; /* 某顶点 与已 构造 好的部 分

7、生 成树的 顶点 之间权 值最 小的顶点 */ intlowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值*/ ClosEdgeMaxVertexNum; /* 用普里 姆 算法 求最 小 生成 树时的 辅助数 组*/ （4）系统功能模块介绍输出矩阵存储的形式： （城市间无路径用？代替，如图）voidDisMatix(MGraph *G) 创建图：voidCreatGraph(MGraph *G) PRiM求最小生成树：voidMiniSpanTree_PRIM(MGraph *G,int u ) 主函数：int main() （5）源程序#include #include

8、 #include #define INFINITY 30000 /* 定义一个权值的最大值 */ #define MaxVertexNum 30 /* 图的最大顶点数为30 */ typedefstruct int arcsMaxVertexNumMaxVertexNum; /* 邻接矩阵，即边表 */ intvertexNum,edgeNum; /* 图的当前顶点数和边数 */ MGraph; /*Graph是以以邻接矩阵存储的图类型*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

9、- 第 5 页，共 11 页 - - - - - - - - - typedefstruct intadjvertex; /* 某顶点 与已 构造 好的部 分生 成树的 顶点 之间权 值最 小的顶点 */ intlowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值*/ ClosEdgeMaxVertexNum; /* 用普里 姆 算法 求最 小 生成 树时的 辅助数 组*/ voidDisMatix(MGraph *G) inti,j; printf(n图的邻接矩阵：n); for(i=1;ivertexNum;i+) for(j=1;jvertexNum;j+) if(G

10、-arcsij=INFINITY) printf( ?); elseprintf(%4d,G-arcsij); printf(n); printf(n); voidCreatGraph(MGraph *G) /* 构造邻接矩阵结构的图G */ inti,j; intstart,end,weight; printf(请输入图的顶点数和边数:); scanf(%d,%d,&G-vertexNum,&G-edgeNum); /* 输 入图 的顶 点数 和边 数*/ for(i=1;ivertexNum;i+) for(j=1;jvertexNum;j+) G-arcsij=INFINITY; /*

11、初始化邻接矩阵 */ printf(输入相邻两结点和其权值:n); for(i=1;iedgeNum;i+) scanf(%d,%d,%d,&start,&end,&weight); /* 输入边的起点和终点及权值 */ G-arcsstartend=weight; G-arcsendstart=weight; DisMatix(G); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - voidMiniSpanTree_PRIM

12、(MGraph *G,int u ) /* 从第 u 个顶点出发构造图G的最小生成树 , 最小生成树的顶点信息存放在数组 closedge中*/ ClosEdgeclosedge; inti,j,w,k; for(i=1;ivertexNum;i+) /* 辅助数组初始化 */ if(i!=u) closedgei.adjvertex=u; closedgei.lowcost=G-arcsui; closedgeu.lowcost=0; /* 初始， U=u */ for(i=1;ivertexNum-1;i+) /* 选择其余的G-vexnum-1 个顶点 */ w=INFINITY; fo

13、r(j=0;ivertexNum;j+) /* 在辅助数组closedge 中选择权值最小的顶点 */ if(closedgej.lowcost!=0&closedgej.lowcostw) w=closedgej.lowcost; k=j; /* 求出生成树的下一个顶点k*/ closedgek.lowcost=0; /* 第 k 个顶点并入U集*/ for(j=1;jvertexNum;j+) /* 新顶点并入U后，修改辅助数组*/ if(G-arcskjarcskj; printf(打印最小代价生成树的各条边：n); for(i=1;ivertexNum;i+) /*打印最小生成树的各条

14、边 */ if(i!=u) printf(%d-%d,%dn,i, closedgei.adjvertex, G-arcsiclosedgei.adjvertex); int main() printf(* 构 造n个 城 市 连 接 的 最 小 生 成 树 问 题*nn); printf(* 1.输 入城 市 的 个数 和 城市 间 的 路 径 数*n); printf(* 2. 输 入 相 邻 城 市 名 字 及 他 们 之 间 的 路 径 长 度*n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

15、 - - - - - 第 7 页，共 11 页 - - - - - - - - - printf(* 3. 以 邻 接 矩 阵 存 储 各 个 城 市 间 的 信 息 并 输 出*n); printf(* 4. 用PRIM 算 法 得 出n 个 城 市 连 接 的 最 小 生 成 树*n); printf(* 5. 打 印 出n个 城 市 连 接 的 最 小 生 成 树 路 径*nn); MGraph G; /* 采用邻接矩阵结构的图 */ int v; CreatGraph(&G); /* 生成邻接矩阵结构的图 */ printf(从哪一个顶点开始:); scanf(%d,&v); /* 输

16、入普里姆算法中的起始顶点 */ MiniSpanTree_PRIM(&G,v); /* 普里姆算法求最小生成树 */ return 0; （6）运行结果及调试分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 对于任意给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树并输出这些边的权值，所以如何实现输出显示所有的最小生成树关键问题所在，经过分析调试，用一个for语句就可以解决这个问题，从每个顶点出发，开始每一次遍历

17、并输出显示出来。算法的时间和空间性能分析根据程序中算法的循环语句可以判断出普利姆算法的时间复杂度名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 为 O （n2）算法和图中的边数无关。因此普利姆算法适合求稠密网的最小生成树，因为在算法中用邻接矩阵的存储结构，在无向图中，邻接矩阵是对称的。 所以仅需要存储上三角或下三角的元素，因此需要 n(n+1) 的存储空间。（7）课程设计总结最小生成树主要由PRIM算法完成，由于老师平时课上对

18、普利姆算法的知识的透彻讲解，通过整体构思，于是，先确立了基本步骤： 1. 建立一个具有n 个定点的无向图 2. 接着创建一个邻接矩阵来存储该图，然后初始化该矩阵，3. 最后根据普利姆算法，得到了最小生成树以及各边的权值。皇天不负有心人， 按照步骤， 忙碌了两周， 在不断地努力下，总算将此程序设计出来。尽管不完全是自己独立完成，但仍然很欣慰，因为在设计的过程中，让我了解到要设计一个大型程序，查找资料是至关重要的，在他人的基础上，再根据自己所学进行修改与调试，最后设计出自己想要的程序，这过程艰辛，但只要你持之以恒，定可将问题解决。通过本次实验巩固了课本的基本知识，熟练运用课程知识。 提高我的组织数

19、据及编写程序的能力，使我能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的问题在计算机内部表示出来并用软件解决问题，本次实验大大提高了对编程的爱好，发现，只要认认真真的去思名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 考，没有办不到的事情。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -