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

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

1、精选学习资料 - - - - - - - - - JINGCHU UNIVERSITY OF TECHNOLOGY数据结构（ C 语言描述）课程设计学院运算机工程学院班 级 12 级软件技术 1 班学 号 2022304040122、 120 124 、133、121 同学姓名 周鑫、王彬彬、李松平张圣玮、魏远迎 指导老师 余云霞 2022 年 1 月 3 日名师归纳总结 - - - - - - -第 1 页,共 25 页精选学习资料 - - - - - - - - - 目 录1 课程设计介绍 . 0 1.1 课程设计内容 . 0 1.2 课程设计要求 . 0 2 课程设计原理 . 1 2.1

2、 课设题目粗略分析 . 1 2.2 原理图介绍 . 2 2.2.1 功能模块图 . 2 2.2.2 流程图分析 . 2 3 数据结构分析 . 83.1 储备结构 . 8 3.2 算法描述 . 9 4 调试与分析 . 22 4.1 调试过程 . 22 4.2 程序执行过程 . 22 参考文献 . 28名师归纳总结 附录 . 28第 2 页,共 25 页- - - - - - -精选学习资料 - - - - - - - - - 1 课程设计介绍1.1 课程设计内容编写算法能够建立带权图,并能够用 Prim 算法求该图地最小生成树 .最小生成树能够挑选图上地任意一点做根结点 .最小生成树输出采纳顶点

3、集合和边地集合地势式 .1.2 课程设计要求名师归纳总结 1.可以输入顶点、边数及各路径地权值；第 3 页,共 25 页2.通过建立无向图或有向图能过输出邻接矩阵或邻接表；3.可以输出建立地最小生成树；4.画出流程图,且函数有必要说明、注释；课设完成后上交报告及核心代码.5.- - - - - - -精选学习资料 - - - - - - - - - 2 课程设计原理2.1 课设题目粗略分析依据课设题目要求,拟将整体程序分为两大模块.以下是两个模块地大体分析：1. 创建网图并确定网图地储备形式,通过对题目要求地详细分析.发觉该题地主要操作是路径地输出,因此采纳邻接表和邻接矩阵（起点、终点和权值）

4、两种储备结构,便利以后地编程 .名师归纳总结 2.Prim 算法 .设置两个新地集合U 和 T,其中 U 用于存放带权图G 地最小生成树地结点地第 4 页,共 25 页集合, T 用于存放带权图G 地最小生成树边地权值地集合.其思想是：令集合U 地初值为Uu0（即假设构造最小生成树时从结点u0 开头）,集合T 地初值为T=. 从全部结点u 属于 U 和结点 v 属于 V 但不属于U 地带权边中选出具有最小权值地边（u,v）,将结点v 加入集合U中,将边（ u,v）加入集合T 中.如此不断重复,当U=V 时,最小生成树便构造完毕.- - - - - - -精选学习资料 - - - - - - -

5、 - - 2.2 原理图介绍 2.2.1 功能模块图 开头显示菜单进行挑选挑选创建（有）无向图及储备方式有 向 图 邻 接 矩 阵无 向 图 邻 接 矩 阵有 向 图 邻 接 表无 向 图 邻 接 表调用普里姆算法输出最小生成树终止图 2.1 功能模块图2.2.2 流程图分析名师归纳总结 1.主函数第 5 页,共 25 页- - - - - - -精选学习资料 - - - - - - - - - 开头显示菜单,选择输入 1 或 2 挑选 1挑选 2 挑选 1 挑选 2 调用 CreateMGraph调 用createAgraph调用 CreateGraph函调用 createALgraph函数

6、函数调用数函数Prim 函数,输出最小生成树终止图 2.2 主函数流程图2. CreateMGraph 函数名师归纳总结 - - - - - - -第 6 页,共 25 页精选学习资料 - - - - - - - - - 开头int i,j,k fori=0 ；in；i+ scanf“n%c”,&G-vexsi ；fori=0；in；i+ forj=0；in；i+ Y N i=j G-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

7、.3 CreateMGraph 函数流程图名师归纳总结 - - - - - - -第 7 页,共 25 页精选学习资料 - - - - - - - - - 3Prim 函数开头int i,j,k,lowcost100,mincost ；fori=1 ；in；i+ lowcosti=gm0i ；closevertexi=0； lowcost0=0；closevertex0=0；fori=1 ；in；i+ mincost=max；j=1；k=1；N Y jn Y lowcostjmincostN &lowcostj.=0 mincost=lowcostj；j+；printf 顶点地序号 =%d 边

8、地权值 =%dn,k,mincost ； lowcostk=0 ；名师归纳总结 - - - - - - -第 8 页,共 25 页精选学习资料 - - - - - - - - - forj=0；jn；j+ gmkjn,&g-e ；fori=0；in；scanf%d,&g-adjlisti.vertex ；fork=0；ke；scanf%d,%d,%d,&i,&j,&ws=edgenode*mallocsizeofedgenode；s-adjvex=j；s-weight=w；s-next=g-adjlisti.firstedges；终止图 2.5 createAgraph 函数流程图5. 邻接矩

9、阵 Output 输出函数名师归纳总结 - - - - - - -第 10 页,共 25 页精选学习资料 - - - - - - - - - 开头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 储备结构 定义邻接矩阵及邻接表地结构体名师归纳总结 - - - - - - -第 11 页,共 25 页精选学习资料 - - - - - - - - - （1）邻接矩阵#define MaxVertexN

10、um 100#define max 1000typedef int VertexType；typedef int EdgeType；typedef struct VertexType vexsMaxVertexNum ； EdgeType edgesMaxVertexNumMaxVertexNum ； int n,e； MGraph ；（2）邻接表#define MaxVertexNum 100 typedef int vertextype ；typedef struct node int adjvex ； int weight ； struct node *next ； edgenode；t

11、ypedef struct vnode vertextype vertex ； edgenode *firstedges； vertexnode ；typedef vertexnode AdjListMaxVertexNum；typedef struct AdjList adjlist ； int n,e；ALgraph ；3邻接表转换成邻接矩阵帮助结构体名师归纳总结 - - - - - - -第 12 页,共 25 页精选学习资料 - - - - - - - - - typedef int edgetype ；typedef struct edgetype vexsMaxVertexNum

12、； edgetype edgesMaxVertexNumMaxVertexNum； int n,e；*/ graph ； /* 邻接表转换成邻接矩阵帮助结构体3.2 算法描述1. 创建有向网图邻接矩阵储备 void CreateMGraphMGraph *G int 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+

13、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； :n ； printf 输出顶点信息及邻接矩阵 OutPutG ； printf 输出最小生成树地信息 :n ； primG-edges,G-n,G-vexs ； 2. 创建无向网图邻接矩阵储备 void CreateGraphMGraph *G int i,j,k,weight ；名师归纳总结 printf

14、t= 无向网图邻接矩阵=n ；第 13 页,共 25 页- - - - - - -精选学习资料 - - - - - - - - - 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 ； /* 初始化邻接矩阵 */ printf 输入边对应地两个顶点地序号及权值： ； for k=0 ；ke ；k+ scanfn%

15、d,%d,%d,&i,&j,&weight； G-edgesij=weight； G-edgesji=weight ； printf 输出顶点信息及邻接矩阵 :n ； OutPutG ； printf 输出最小生成树地信息 :n ； primG-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

16、 输入顶点 : ； 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=edgenode*mallocsizeofedgenode ； s-adjvex=j ； s-weight=w ； s-next=g-adjlisti.firstedges ； g-adjlisti.firstedges=s ；名师归纳总结 - - - - - - -第 14 页,共 25 页精选学习资料 - - -

17、 - - - - - - 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 ；in ；i+ scanf%d,&g-adjlisti.vertex； g-adjlisti.firstedges=NULL； printfn 输入边和权值 : ； fork=0 ；ke ；k+

18、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.firstedges ； g-adjlistj.firstedges=s ； DispAdjListg ； 5.prim 算法 void primint gmMa

19、xVertexNum ,int n,int closevertex /* 普里姆算法 */ int lowcost100 ； int mincost ； int i,j,k ； fori=0 ；in ；i+ 名师归纳总结 - - - - - - -第 15 页,共 25 页精选学习资料 - - - - - - - - - lowcosti=gm0i； closevertexi=0 ； lowcost0=0 ； closevertex0=0 ； fori=1 ；in ；i+ mincost=max ； j=1 ； k=1； whilejn iflowcostjmincost&lowcostj.=

20、0 mincost=lowcostj ； k=j ； j+ ； printf 顶点地序号 =%d 边地权值 =%dn,k,mincost ； lowcostk=0 ； forj=0 ； jn；j+ ifgmkjlowcostj lowcostj=gmkj； closevertexj=k ； 6. 输出邻接矩阵储备函数 void OutPut MGraph *G int i,j ； printftE= ； for i=0 ；in ；i+ printf%d ,G-vexsi； printf ； printfn ； fori=0 ；in ；i+ forj=0 ；jn ；j+ 名师归纳总结 - - -

21、 - - - -第 16 页,共 25 页精选学习资料 - - - - - - - - - printft%d ,G-edgesij； printfn ； 7.输出邻接表储备函数void DispAdjListALgraph *g int i ； edgenode *p； printfn 网图地邻接表表示如下：n； for i=0 ； in ； i+ ； printf%d,%3d=,i,g-adjlisti.vertex p=g-adjlisti.firstedges ； while p.=NULL printf%d,%d-,p-adjvex,p-weight； p=p-next ； prin

22、tfn ； 8.邻接表转换成邻接矩阵函数void changeALgraph *g /*邻接表转换成邻接矩阵*/ int i,j ； 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； wh

23、ilep 名师归纳总结 M-edgesip-adjvex=p-weight；第 17 页,共 25 页- - - - - - -精选学习资料 - - - - - - - - - p=p-next ； primM-edges,M-n,M-vexs；4 调试与分析4.1 调试过程测试数据（对下图进行测试）：右图是 6 个顶点地10 条边地2 14 连通图六个顶点分别是：1 2 3 4 5 6 顶点序号和边上地权植分别是0 1 11 0 2 15 0 3 18 3 1 2 33 1 4 12 2 3 20 562 4 22 2 5 25 3 5 27 4 5 29 4.2 程序执行过程系统使用说明：

24、名师归纳总结 1. 输入地数据可以是100 以内地整数；第 18 页,共 25 页- - - - - - -精选学习资料 - - - - - - - - - 2. 本系统可以建立带权图,并能够用Prim 算法求该网图地最小生成树. 3. 该系统会有菜单提示,进行选项：4.程序实际运行截图（ 1）有向图邻接矩阵输出最小生成树截图：名师归纳总结 - - - - - - -第 19 页,共 25 页精选学习资料 - - - - - - - - - （ 2）无向图邻接矩阵输出最小生成树截图：名师归纳总结 - - - - - - -第 20 页,共 25 页精选学习资料 - - - - - - - -

25、- 名师归纳总结 - - - - - - -第 21 页,共 25 页精选学习资料 - - - - - - - - - （3）有向图邻接表输出最小生成树截图：名师归纳总结 - - - - - - -第 22 页,共 25 页精选学习资料 - - - - - - - - - （4）无向图邻接表输出最小生成树截图：名师归纳总结 - - - - - - -第 23 页,共 25 页精选学习资料 - - - - - - - - - 参考文献（1）李素如,数据结构（C 语言描述）,2022,化学工业出版社（2）严蔚敏、吴伟民,数据结构（C 语言描述）,1999,清华高校出版社（3）徐孝凯,数据结构课程试

26、验,2002,清华高校出版社（4）孟佳娜、胡潇琨,算法与数据结构试验与习题,2004,机械工业出版社附 录说明：本次课程设计由组长周鑫,组员王彬彬、李松平、张圣玮、魏远迎共同完成 .其中邻接矩 阵储备有向图、无向图及调用普里姆算法生成最小生成树、流程图绘制、任务书填写由王彬彬 完成；邻接表储备有向图、无向图及调用普里姆算法生成最小生成树、菜单界面由周鑫完成；名师归纳总结 李松平、张圣玮、魏远迎主要负责文档排版,代码调试等综合应用.第 24 页,共 25 页- - - - - - -精选学习资料 - - - - - - - - - 课程设计总结：本次课程设计涉及到地范畴虽不广,但能够比较系统地对

27、 整理和复习 .同时有了许多地体会和体会 .C 语言和数据结构进行一次1.巩固了以前学过地 C 语言地学问,在这次课程设计中我体会到 C 语言超强地规律性,能够娴熟使用 VC+ 地编译环境,也对这两门课程有了新地熟悉,他们既有联系,又相互区分,在编写程序过程中要敏捷应用2. 对数据结构地懂得有待加强,算法地学问面也有待于提高.不同地人会挑选不同地算法,所以即使同样地程序,不同地人必定会设计出不同地方案,所以以后地学习生活中,肯定要广泛涉猎,把握更多更好地解决问题地方法 .3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合地,没有平常基础地训练是不会写出高效地算法 .4. 此次课程设计时间虽短,课设地过程是短暂地,但我所收成地是永恒地 .它让我尝到了学习地欢乐,胜利地欢乐,更让我懂得了不少做人地道理.要完成一项任务或把东西学好就必需有足够地信心,长久地耐心,有面对困难无所恐惧地精神,这对我日后地学习和 生活产生了深远地影响 .指导老师评语：指导老师 签字 ：年月日课程设计成果名师归纳总结 - - - - - - -第 25 页,共 25 页