2022年普里姆算法生成最小生成树_课程设计.docx

《2022年普里姆算法生成最小生成树_课程设计.docx》由会员分享，可在线阅读，更多相关《2022年普里姆算法生成最小生成树_课程设计.docx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源JINGCHU UNIVERSITY OF TECHNOLOGY数据结构（ C 语言描述）课程设计学院运算机工程学院 班级 12 级软件技术 1 班学号 2021304040122、 120124 、133、121同学姓名周鑫、王彬彬、李松平张圣玮、魏远迎指导老师余云霞2021 年 1 月 3 日欢迎下载精品学习资源目录1 课程设计介绍01.1 课程设计内容01.2 课程设计要求02 课程设计原理12.1 课设题目粗略分析12.2 原理图介绍22.2.1 功能模块图22.2.2 流程图分析23 数据结构分析83.1 储备结构83.2 算法描述94 调试与分析224.1 调试过程22

2、4.2 程序执行过程22参考文献28附 录28欢迎下载精品学习资源1 课程设计介绍1.1 课程设计内容编写算法能够建立带权图，并能够用Prim 算法求该图地最小生成树.最小生成树能够挑选图上地任意一点做根结点.最小生成树输出采纳顶点集合和边地集合地势式.1.2 课程设计要求1. 可以输入顶点、边数及各路径地权值；2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表；3. 可以输出建立地最小生成树；4. 画出流程图，且函数有必要说明、注释；5. 课设完成后上交报告及核心代码.欢迎下载精品学习资源2 课程设计原理2.1 课设题目粗略分析依据课设题目要求，拟将整体程序分为两大模块.以下是两个模块地大

3、体分析：1. 创建网图并确定网图地储备形式，通过对题目要求地详细分析.发觉该题地主要操作是路径地输出，因此采纳邻接表和邻接矩阵（起点、终点和权值）两种储备结构，便利以后地编程 .2. Prim 算法 .设置两个新地集合 U 和 T，其中 U 用于存放带权图 G 地最小生成树地结点地 集合， T 用于存放带权图 G 地最小生成树边地权值地集合 .其思想是：令集合 U 地初值为 Uu0（即假设构造最小生成树时从结点 u0 开头），集合 T 地初值为 T=. 从全部结点 u 属于 U 和结点 v 属于 V 但不属于 U 地带权边中选出具有最小权值地边（ u，v），将结点 v 加入集合 U 中，将边（

4、 u， v）加入集合 T 中.如此不断重复，当 U=V 时，最小生成树便构造完毕 .欢迎下载精品学习资源2.2 原理图介绍2.2.1 功能模块图开头显示菜单进行挑选挑选创建（有）无向图及储备方式有向图邻接矩阵无向图邻接矩阵有向图邻接表无向图邻接表调用普里姆算法输出最小生成树终止图 2.1 功能模块图2.2.2 流程图分析1. 主函数欢迎下载精品学习资源调用CreateMGraph调 用createAgraph调用 CreateGraph函调用createALgraph函数函数数函数开头显示菜单，选择输入 1 或 2挑选 1挑选 2挑选 1挑选 2调用 Prim 函数，输出最小生成树终止图 2.

5、2 主函数流程图2. CreateMGraph 函数欢迎下载精品学习资源开头int i,j,kfori=0 ；in ；i+scanf“n%c”,&G-vexsi ；fori=0 ；in；i+forj=0 ；in；i+YNi=jG-edgesij=0 ；G-for k=0；ke ；k+scanfn%d,%d,%d,&i,&j,&weight ；G-edgesij=weight ；OutPutG；primG-edges,G-n,G-终止图 2.3 CreateMGraph 函数流程图欢迎下载精品学习资源3. Prim 函数开头int i,j,k,lowcost100,mincost ；fori=1

6、 ；in；i+lowcosti=gm0i；closevertexi=0； lowcost0=0 ；closevertex0=0；fori=1 ；in；i+mincost=max；j=1 ；k=1；NYjnYNlowcostjmincost&lowcostj.=0mincost=lowcostj；j+ ；printf 顶点地序号 =%d 边地权值 =%dn,k,mincost ；lowcostk=0 ；欢迎下载精品学习资源forj=0 ；jn；j+gmkjn,&g-e ；fori=0 ；in ；scanf%d,&g-adjlisti.vertex ；fork=0 ；ke；scanf%d,%d,%

7、d,&i,&j,&ws=edgenode*mallocsizeofedgenode；s-adjvex=j；s-weight=w；s-next=g-adjlisti.firstedges ；终止图 2.5 createAgraph 函数流程图5. 邻接矩阵 Output 输出函数欢迎下载精品学习资源开头int i,j ；for i=0 ；in ；i+printf%d ,G-vexsi ；fori=0 ；in ；i+forj=0 ；jn ；j+printft%d ,G-edgesij ；终止图 2.6 Output 函数流程图3 数据结构分析3.1 储备结构定义邻接矩阵及邻接表地结构体欢迎下载精品

8、学习资源（ 1）邻接矩阵#define MaxVertexNum 100#definemax1000typedef int VertexType ；typedef int EdgeType；typedef structVertexType vexsMaxVertexNum ；EdgeType edgesMaxVertexNumMaxVertexNum；int n,e；MGraph ；（ 2）邻接表#define MaxVertexNum 100 typedef int vertextype ；typedef struct nodeint adjvex ；int weight ；struct n

9、ode *next ；edgenode ；typedef struct vnodevertextype vertex ；edgenode *firstedges ；vertexnode ；typedef vertexnode AdjListMaxVertexNum；typedef struct AdjList adjlist ；int n,e ；ALgraph ；3邻接表转换成邻接矩阵帮助结构体欢迎下载精品学习资源typedef int edgetype ；typedef structedgetype vexsMaxVertexNum ；edgetype edgesMaxVertexNumMa

10、xVertexNum；int n,e；graph ；/* 邻接表转换成邻接矩阵帮助结构体*/3.2 算法描述1. 创建有向网图邻接矩阵储备void CreateMGraphMGraph *Gint i,j,k,weight ；printft= 有向网图邻接矩阵=n ；printf 请输入顶点数和边数：；scanf%d,%d,&G-n,&G-e；printf 请输入顶点信息 : ；for i=0 ；in ； i+ scanfn%d,&G-vexsi；for i=0 ；in ； i+for j=0 ；jn ；j+ ifi=j G-edgesij=0；else G-edgesij=max ；/* 初

11、始化邻接矩阵 */printf 输入边对应地两个顶点地序号及权值： ；for k=0 ；ke ；k+scanfn%d,%d,%d,&i,&j,&weight；G-edgesij=weight；printf 输出顶点信息及邻接矩阵:n ；OutPutG ；printf 输出最小生成树地信息:n ；primG-edges,G-n,G-vexs ；2. 创建无向网图邻接矩阵储备void CreateGraphMGraph *Gint i,j,k,weight ；printft= 无向网图邻接矩阵=n ；欢迎下载精品学习资源printf 请输入顶点数和边数： ；scanf%d,%d,&G-n,&G-e

12、；printf 请输入顶点信息 : ；for i=0 ；in ； i+ scanfn%d,&G-vexsi；for i=0 ；in ； i+for j=0 ；jn ；j+ ifi=j G-edgesij=0；else G-edgesij=max ； /* 初始化邻接矩阵 */printf 输入边对应地两个顶点地序号及权值： ；for k=0 ；ke ；k+scanfn%d,%d,%d,&i,&j,&weight；G-edgesij=weight；G-edgesji=weight；printf 输出顶点信息及邻接矩阵:n ；OutPutG ；printf 输出最小生成树地信息 :n ；primG

13、-edges,G-n,G-vexs ；3. 创建有向网图邻接表储备void createAgraph ALgraph *g /*创建有向网图 */int i,j,k,w ；edgenode *s；printft= 有向网图邻接表 =n ；printf 输入顶点数和边数 : ；scanf%d,%d%*c,&g-n,&g-e；printfn输入顶点 : ；fori=0 ；in ；i+scanf%d,&g-adjlisti.vertex；g-adjlisti.firstedges=NULL；printfn输入边和权值 : ；fork=0 ；ke ；k+scanf%d,%d,%d,&i,&j,&w；s

14、=edgenode*mallocsizeofedgenode ；s-adjvex=j ；s-weight=w ；s-next=g-adjlisti.firstedges；g-adjlisti.firstedges=s ；欢迎下载精品学习资源DispAdjListg ；4. 创建无向网图邻接表储备void createALgraphALgraph *g /*创建无向网图 */int i,j,k,w ；edgenode *s；printft= 无向网图邻接表 =n ；printf 输入顶点数和边数 : ；scanf%d,%d%*c,&g-n,&g-e；printfn输入顶点 : ；fori=0 ；

15、in ；i+scanf%d,&g-adjlisti.vertex；g-adjlisti.firstedges=NULL；printfn输入边和权值 : ；fork=0 ；ke ；k+scanf%d,%d,%d,&i,&j,&w；s=edgenode*mallocsizeofedgenode ；s-adjvex=j ；s-weight=w ；s-next=g-adjlisti.firstedges；g-adjlisti.firstedges=s ；s=edgenode*mallocsizeofedgenode ；s-adjvex=i ；s-weight=w ；s-next=g-adjlistj.

16、firstedges；g-adjlistj.firstedges=s ；DispAdjListg ；5. prim 算法void primint gmMaxVertexNum ,int n,int closevertex /* 普里姆算法 */int lowcost100 ；int mincost ；int i,j,k ；fori=0 ；in ；i+欢迎下载精品学习资源lowcosti=gm0i；closevertexi=0 ；lowcost0=0 ；closevertex0=0 ；fori=1 ；in ；i+mincost=max ；j=1 ；k=1 ；whilejniflowcostjmi

17、ncost&lowcostj.=0mincost=lowcostj ；k=j ；j+ ；printf 顶点地序号 =%d 边地权值 =%dn,k,mincost ；lowcostk=0 ；forj=0 ； jn ；j+ ifgmkjlowcostjlowcostj=gmkj；closevertexj=k ；6. 输出邻接矩阵储备函数void OutPut MGraph *Gint i,j ；printftE= ；for i=0 ；in ；i+ printf%d ,G-vexsi；printf；printfn ；fori=0 ；in ；i+forj=0 ；jn ；j+欢迎下载精品学习资源prin

18、tft%d ,G-edgesij；printfn ；7. 输出邻接表储备函数void DispAdjListALgraph *gint i ；edgenode *p；printfn 网图地邻接表表示如下：n；for i=0 ； in ； i+ printf%d,%3d=,i,g-adjlisti.vertex；p=g-adjlisti.firstedges；while p.=NULLprintf%d,%d-,p-adjvex,p-weight；p=p-next ；printfn ；8. 邻接表转换成邻接矩阵函数void changeALgraph *g/*邻接表转换成邻接矩阵*/int i,j

19、 ；edgenode *p；graph *M ；M=graph*mallocsizeofgraph；M-n=g-n ；M-e=g-e ；fori=0 ；ie ；i+ forj=0 ；je ；j+ifi=jM-edgesij=0；else M-edgesij=MaxVertexNum；fori=0 ；in ； i+M-vexsi=g-adjlisti.vertex；fori=0 ；in ； i+p=g-adjlisti.firstedges；whilepM-edgesip-adjvex=p-weight；欢迎下载精品学习资源p=p-next ；primM-edges,M-n,M-vexs；4 调

20、试与分析4.1 调试过程测试数据（对下图进行测试）：右图是 6 个顶点地 10 条边地连通图1六个顶点分别是：1 2 3 4 5 6顶点序号和边上地权植分别是2401110215031831233141223205242262525352745294.2 程序执行过程系统使用说明：1. 输入地数据可以是100 以内地整数；欢迎下载精品学习资源2. 本系统可以建立带权图，并能够用Prim 算法求该网图地最小生成树.3. 该系统会有菜单提示，进行选项：4.程序实际运行截图（ 1）有向图邻接矩阵输出最小生成树截图：欢迎下载精品学习资源（ 2）无向图邻接矩阵输出最小生成树截图：欢迎下载精品学习资源欢迎

21、下载精品学习资源（3） 有向图邻接表输出最小生成树截图：欢迎下载精品学习资源（4） 无向图邻接表输出最小生成树截图：欢迎下载精品学习资源参考文献（ 1）李素如，数据结构（C 语言描述）， 2021，化学工业出版社（ 2）严蔚敏、吴伟民，数据结构（C 语言描述）， 1999，清华高校出版社（ 3）徐孝凯，数据结构课程试验，2002，清华高校出版社（ 4）孟佳娜、胡潇琨，算法与数据结构试验与习题，2004，机械工业出版社附 录说明：本次课程设计由组长周鑫，组员王彬彬、李松平、张圣玮、魏远迎共同完成.其中邻接矩阵储备有向图、无向图及调用普里姆算法生成最小生成树、流程图绘制、任务书填写由王彬彬完成；邻

22、接表储备有向图、无向图及调用普里姆算法生成最小生成树、菜单界面由周鑫完成；李松平、张圣玮、魏远迎主要负责文档排版，代码调试等综合应用.欢迎下载精品学习资源课程设计总结：本次课程设计涉及到地范畴虽不广，但能够比较系统地对C 语言和数据结构进行一次整理和复习 .同时有了许多地体会和体会.1. 巩固了以前学过地C 语言地学问，在这次课程设计中我体会到C 语言超强地规律性，能够娴熟使用VC+ 地编译环境，也对这两门课程有了新地熟悉，他们既有联系，又相互区分，在编写程序过程中要敏捷应用2. 对数据结构地懂得有待加强，算法地学问面也有待于提高.不同地人会挑选不同地算法，所以即使同样地程序，不同地人必定会设计出不同地方案，所以以后地学习生活中，肯定要广泛涉猎，把握更多更好地解决问题地方法.3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合地，没有平常基础地训练是不会写出高效地算法.4. 此次课程设计时间虽短，课设地过程是短暂地，但我所收成地是永恒地.它让我尝到了学习地欢乐，胜利地欢乐，更让我懂得了不少做人地道理.要完成一项任务或把东西学好就必需有足够地信心，长久地耐心，有面对困难无所恐惧地精神，这对我日后地学习和生活产生了深远地影响.指导老师评语：指导老师 签字 ：年 月 日课程设计成果欢迎下载