《数据结构prim算法vc++编程》由会员分享，可在线阅读，更多相关《数据结构prim算法vc++编程（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计目录摘要、关键字 .3 第一章、需求分析 .3 第二章、数据结构定义及其操作实现.4 第三章、程序设计及其实现.5 第四章、运行结果及其分析.9 第五章、问题及其解决方法.10 第六章、心得体会（设计总结）.11 第七章、其他.11 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -摘要最小生成树是数据结构中图的一种重要应用，在图中对于 n 个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以邻接矩阵作为图的存储结构,采用 Prim 算法求最小生成树。Prim 算法是求最小生成树的常用算法它们分别适用于
2、稠密图和稀疏图。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆,构建造价最低的通讯网络。关键词：最小生成树；邻接矩阵；Prim 算法第一章、需求分析一、目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。二、要求问题要求：给定一个地区的n 个城市的距离网，用prim 算法和 kruscal 算法建立最小生成树，并计算出最小生成树的代价。程序运行环
3、境：windows、visual c+或 java 等要求：1）城市间距离用邻接矩阵表示，邻接矩阵的存储结构用书本定义表示，若城市间不存在道路，则将相应边的权值用自己定义的无穷大表示，要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示出得到的最小生成树的代价。2）表示城市间距离的邻接矩阵（至少6 个城市 10条道路）；3）给出使用的数据结构的ADT 及其实现；4）最小生成树中包括边及其权值，并显示出得到的最小生成树的代价：名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -第二章、数据结构定义及其操作实现抽象数据类型图的定义如下：ADT Graph 数据对象
4、 V：V 是具有相同特性的数据元素的集合，称为顶点集。数据关系 R：R=VR VR=|v,w 属于 v 且 p(v,w),(v,w)表示从 v 到 w 的弧，谓词 p(v,w)定义了弧 的意义或信息 基本操作 P：CreatGraph(&G,V,VR)；初始条件：V 是图的顶点集，VR 是图中弧的集合。操作结果：按 V 和 VR 的定义构造图 G。DestoryGraph(&u)；初始条件：图 G 存在。操作结果：销毁图G。LocateVex(G,u)；初始条件：图 G 存在,u 和 G 中顶点有相同的特征。操作结果：若 G 中存在顶点 u，则返回该顶点在图中的位置；否则返回其他信息。GetV
5、ex(G,v)；初始条件：图 G 存在，v 是图中某个顶点。操作结果：返回 v 的值。PutVex（&G，v，value）；初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：对 v 赋值 value。NextAdjVex(G,v,w)；初始条件：图 G 存在，v 是图中某个顶点，w 是 v 的邻接顶点。操作结果：返回 v 的（相对于 w 的）下一个邻接顶点。若w 是 v 的最后一个邻接点，则返回“空”。BFSTraverse(G,Visit()；初始条件：图 G 存在，Visit 是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit 一次且仅一次。
6、一旦visit()失败，则操作失败。ADT Graph 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -第三章、程序设计及其实现一、主要功能逻辑过程和实现算法2、用prim算法求解功能选择开 始1、建立邻接矩阵结 束名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -二、主要函数模块设计1、图的邻接矩阵模块：int creatMGraph(MGraph&G)char v1,v2;int i,j,w;printf(建立邻接矩阵:n);printf(请输入图 G 顶点（城市）和弧（边）的个数:);scanf(%d,&G.vexnum);scanf(%
7、d,&G.arcnum);printf(输入所有顶点:);for(i=0;iG.vexsi;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij.adj=int_max;G.arcsij.info=NULL;printf(输入所有边及依附的顶点（城市）和权（距离）:n);for(int k=0;kv1v2w;/输入一条边衣服的两点及权值i=localvex(G,v1);/确定顶点 v1 和 v2 在图中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;ljjzprint(G);printf(图 G
8、 邻接矩阵创建成功！n);return G.vexnum;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -2、prim 求解模块：int prim(int gmax,int n)/最小生成树 PRIM 算法/prevex存储最短路径在 U 中的结点int lowcostmax,prevexmax;/lowcost 存储当前集合 U 分别到剩余结点的最短路径int i,j,k,min;int sum=0;for(i=2;i=n;i+)/n个顶点，n-1 条边lowcosti=g1i;/初始化prevexi=1;/顶点未加入到最小生成树中 lowcost1=0;/标志顶点
9、 1 加入 U 集合for(i=2;i=n;i+)/形成 n-1 条边的生成树min=inf;k=0;for(j=2;j=n;j+)/满足边的一个顶点在U，另一个顶点在 v 的最小边if(lowcostjmin)&(lowcostj!=0)min=lowcostj;k=j;printf(%d,%d)%dt,prevexk-1,k-1,min);sum+=min;lowcostk=0;for(j=2;j=n;j+)/修改由顶点 k 到其他顶点边的权值if(gkjs;switch(s)case 1:d=creatMGraph(G);vnode v;coutendl注意：若该图为非强连通图(含有多个
10、连通分量)时endl 最小生成树不存在,则显示为非法值 endlendl;break;case 2:coutkruskal 算法求解如下：endl;D=(MGraphA*)malloc(sizeof(MGraphA);CreatGraph(D);MiniSpanTree(D);break;printf(n);coutendly;if(y=n)break;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -第四章、运行结果及其分析将程序员录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的
11、提示。操作简单方便实用，下面即为一些操作的示意图。运行程序后出界面，运行结果如图1 所示。图 1 图中有 1-2 两个个选项，可选取其中的一个选项进行操作。选取选项 1 进行操作，运行结果如图2 所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -图 2 依据提示，分别输入无向图的顶点个数与弧的个数，然后依次输入各个顶点所对应的符号及与各个顶点相关联的弧与权值，存在邻接矩阵中。图 3 图中显示了求得的最小生成树所对应的边、权值第五章、问题及其解决方法由于对数据结构和c 语言不是很了解，尽管在参考其它资料的时候也忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。1、问题一：求出图中的最小值现象：求出的最小值是0 原因：图中没有连通的两个顶点之间的权值赋值为0 2、问题二：求最小生成树时，else 语句需再调用一个函数现象：对某些二叉树能求出最小生成树，但不能普遍适应原因：对于找最小生成树边的各种可能没有考虑全面，代码才没有广泛名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -的适应性第七章、其他参考文献：1 严蔚敏.数据结构（C语言版）M.北京：清华大学出版社,1997.2 谭浩强.C 程序设计（第三版）M.北京：清华大学出版社，2005.1.名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -
