单击此处编辑母版标题样式单击此处编辑母版文本样式第二层第三层第四层第五层数据结构图(1) 对于含有数据库的软件系统除了用DFD和数据字典进行数据描述 外还可以用数据结构图(DSDdata structure diagram)来说明文 件之间的联系 单个文件的组成与组织很容易用字典来定义但用条目的形式 来描述文件之间的相互联系就不及图形直观方便使用数据结构 图可以弥补字典在这方面
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级第七章图7.1 抽象数据类型图的定义7.2 图的存储表示7.3 图的遍历7.4 最小生成树7.7两点之间的最短路径问题7.5拓扑排序7.6 关键路径 图是由一个顶点集 V 和一个弧集 R构成的数据结构 Graph = (V R ) R={VR}其中VR{<vw> vw∈V 且 P(vw)}
第二章 线性 表第三章 栈和队列第四章 树第五章 图第六章 排序第七章 查找第一章 概 述第二部分 数据结构51图的基本概念53图的遍历52图的存储方法第五章图A51图的基本概念(b) 这条边关联于顶点vi 和vj。(vi, vj) 关于一条边或弧的表示方法:(a)顶点vi 与vj 是这条边的两个邻接点。无向图: 有向图: 网(络):与边有关的数据称为权,边上带权的图称为网络。对于(vi,vj)?
BEA(vw)=(wv)61完全图子图无向完全图——n个顶点的无向图最大边数是n(n-1)2有向完全图——n个顶点的有向图最大边数是n(n-1)子图——如果图G(VE)和图G(VE)满足:V?VE?E 则称G为G的子图B12路径{AECF}的路径长度为3例连通图强连通图连通分量强连通分量连通——从顶点V到顶点W有一条路径则说V和W是连通的连通图——图中任意两个顶点都是连通的 连通分量:(
弧(Arc) :表示两个顶点v和w之间存在一个关系用顶点偶对<vw>表示通常根据图的顶点偶对将图分为有向图和无向图 有向图(Digraph): 若图G的关系集合E(G)中顶点偶对<vw>的v和w之间是有序的称图G是有向图 在有向图中若 <vw>?E(G) 表示从顶点v到顶点w有一条弧 其中:v称为弧尾(tail)或始点(initial node)w称为弧头(head)或终点(t
抽象数据类型图的定义 抽象数据类型图的定义4例如: G2=(V2VR2)V2={A B C D E F}VR2={(A B) (A E) (B E) (C D) (D F) (B F) (C F) }连通图连通分量强连通图强连通分量C7 若边或弧的个数 e<nlogn则称作稀疏图否则称作稠密图E对有向图来说A若无向图G中任意两个顶点之间都有路径相
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级 ?版权所有或翻印必究 Page 单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级 ?版权所有
#
第三讲: 数据结构概述 林梦香北京航空航天大学2009年10月计算机软件技术基础程序设计需要确定: (问题)数据在计算机中如何表示?如何存储? (数据结构) 对数据实施哪些操作?如何控制?(算法)数据如何输入到计算机?(输入/输出)计算结果如何输出?数 据 结 构第一章 概述第二章 线性表第三章 栈和队列第四章 树第五章 图第六章 排序第七章 文件第一章 概 述数据数据结构数据结构研究内容算法及算
#
违法有害信息,请在下方选择原因提交举报