作业解答-图-数据结构-教学课件.ppt

上传人:可****阿 文档编号:83280391 上传时间:2023-03-29 格式:PPT 页数:14 大小:653.04KB
返回 下载 相关 举报
作业解答-图-数据结构-教学课件.ppt_第1页
第1页 / 共14页
作业解答-图-数据结构-教学课件.ppt_第2页
第2页 / 共14页
点击查看更多>>
资源描述

《作业解答-图-数据结构-教学课件.ppt》由会员分享,可在线阅读,更多相关《作业解答-图-数据结构-教学课件.ppt(14页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构作业数据结构作业2002 年第七章 图7.1 已知如右图所示的有向图,请给出(1)各顶点的入/出度;(2)邻接矩阵;(3)邻接表;(4)逆邻接表;(5)强连通分量。BDAEFC解答:(1)顶点 入度 出度 顶点 入度 出度A 3 0 B 2 2 C 1 2 D 1 3E 2 1 F 2 3(2)邻接矩阵;A B C D E FA 0 0 0 0 0 0B 1 0 0 1 0 0C 0 1 0 0 0 1D 0 0 1 0 1 1 E 1 0 0 0 0 0F 1 1 0 0 1 0M=邻接矩阵邻接矩阵 A B CDEF1 2 3 4 5 6顶点数组顶点数组V1.6(3)邻接表;A B

2、C D E F 1 2 3 4 5 61图邻接表邻接表序号 头结点头结点数组 表表结点结点单链表4136562152(5)强连通分量。BDAEFC7。15#define MAX_VERTEX_NUM 20 /*图中最多顶点数图中最多顶点数*/#define INFINITY 32767 /*定义无穷大定义无穷大*/*DG:有向图:有向图,DN:有向网:有向网,UDG:无向图:无向图,UDN:无向网:无向网*/typedef enum DG,DN,UDG,UDN GraphKind;typedef char VertexType;/*假定顶点数据类型为字符假定顶点数据类型为字符*/typedef

3、 struct /*定义存储图的数据类型定义存储图的数据类型*/VertexType vexsMAX_VERTEX_NUM+1;/*顶点数组顶点数组*/int arcsMAX_VERTEX_NUM+1MAX_VERTEX_NUM+1;/*邻接矩阵邻接矩阵*/int vexnum;/*顶点数顶点数*/GraphKind kind;/*图类型:图类型:DG,DN,UDG,UDN*/MGraph;int InsertVex(MGraph*G,VertexType v)int i,val;if (G-vexnum=MAX_VERTEX_NUM)printf(“OVERFLOW”);return 0;/

4、*失败返回失败返回*/G-vexnum+;/*图图G的顶点数加的顶点数加1*/G-vexsG-vexnum=v;/*顶点数据写入图顶点数据写入图G的顶点数组中的顶点数组中*/val=(G-kind=DG|G-kind=UDG)?0:INFINITY;for(i=1;ivexnum;i+)/*图图G的邻接矩阵第的邻接矩阵第G-vexnum*/G-arcsG-vexnumi=val;/*行、列设置为行、列设置为val*/G-arcsiG-vexnum=val;return 1;/*成功返回成功返回*/if(G-kind=DG|G-kind=UDG)/*区分图和网区分图和网*/val=1;else

5、printf(“输入权值:输入权值:”););scanf(“%d”,&val);G-arcsij=val;if (G-kind=UDG|G-kind=UDN)/*图图G为无向图、无向网为无向图、无向网*/G-arcsji=val;return 1;/*成功返回成功返回*/int DeleteArc(MGraph*G,VertexType V,VertexType w)int i=0,j=0,k,val;for(k=1;kvexnum;k+)/*查询顶点查询顶点v的序号的序号i*/if (G-vexsk=v)i=k;for(k=1;kvexnum;k+)/*查询顶点查询顶点w的序号的序号j*/i

6、f (G-vexsk=w)j=k;if (i=0|j=0|i=j)/*失败返回失败返回*/printf(“弧不存在弧不存在”);return 0;int DeleteVex(MGraph*G,VertexType V)int i=0,j,k;for(i=1;ivexnum;i+)/*查询顶点查询顶点v的序号的序号k*/if (G-vexsi=v)k=i;if (k=0)/*失败返回失败返回*/printf(“顶点不存在顶点不存在”);return 0;/*从顶点数组中删除第从顶点数组中删除第k个顶点,后续顶点据向前移动个顶点,后续顶点据向前移动*/for(i=k+1;ivexnum;i+)G-vexsi-1=G-vexsi;

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 生活常识

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁