3-常用图形数据结构.pptVIP

第三章 Data Structure 常用图形数据结构 常用图形数据结构 概述 线性表结构 栈和队列 树和二叉树 工程数据的计算机处理 概述 数据结构与数据元素 概述 数据的逻辑结构与物理结构 概述 图形数据的基本要求 概述 数据项、记录和数据文件 线性表结构 概述 线性表结构 线性表的顺序存储结构 线性表结构 线性表结构 线性表的链式存储结构 线性表结构 线性表结构 线性表结构 栈和队列 栈 树和二叉树 树 树和二叉树 树的概念 树和二叉树 二叉树 树和二叉树 一般树向二叉树转化 工程数据的计算机处理 概述 工程数据的计算机处理 数据表格的程序化 工程数据的计算机处理 工程数据的计算机处理 线图的程序化 工程数据的计算机处理 * * 数据元素：事件（如指示灯亮灭）、数字或符号的总称或它是数据的基本单位或数据集合中的一个个体。如图中1、2、3、4、5点 数据结构：是研究描述一个客观事物新需要的数据元素和它们之间相互关系：如图中1、2、3、4、5点之间的连接关系 数据的逻辑结构：它仅考虑数据间的逻辑关系，它独立于数据的存储介质。 数据结的物理构：是数据的逻辑结构在计算机中的映象。它包括数据元素的映象和关系的映象。 如线性表的存储： 顺序存储 链表式存储 能够描述物体或图形的几何信息和拓扑信息 便于对物体和图形进行各种操作 需要有较小的存贮空间 便于检索 常用的数据结构：线性表、数组、栈、队、链表、树和图等 基本要求： 对象：数据结构所描述的客观实体称为对象，对象的描述是通过对象的属性来表示 数据项：描述属性的数据 记录：记录描述一个对象的全部数据项称为记录 . . . . . . . . . . . . 45Cr 6 35 24 2 G007 记录2 45 7 30 18 3 G005 记录1 材料 精度 齿宽 齿数 模数 零件号 数据项 属性 记录 线性表是一个有序的数据元素的有限集合 线性表中的数据结构和类型必须相同 线性表结构：向量、链表、栈和队列、数组等 存储结构：顺序存储和链式存储 特点： 均匀性 有序性 访问、修改某一元素非常方便 在删除插入操作时需要进行大量的数据移动 删除前： 删除后： 插入前： 插入后： 删除元素 插入元素 存储空间的分配：在进行删除、插入运算时，线性表的长度也要发生变化，而在给线性表分配存储空间时，必须按最大的长度分配存储空间，并且表的长度也不能随意扩充。 线性表适用场合：查找频繁、长度变化不大、很少进行增删的场合，如工程手册中的数表。 特点：链式存储结构的线性表是用一组任意的存储单元存储线性表的元素，不要求存储单元的连续性。 逻辑上有序，物理结构上无序 节点：存储元素本身的数据信息 及下一元素的存储位置信息 指针域（next） 数据域（Data） 单向链表的结点： 链表的结构形式 单向链表 头部 尾部 删除节点 插入节点 环形单向链表 双向链表 删除节点 增加节点 先进后出FILO 队列 进栈 出栈 先进先出FIFO 第一层 构造几何法（CSG） 树的逻辑结构 根结点 B节点度为3 第二层 第三层 第四层 树的高度度为4 树的度为3 叶结点（度为0） 树是由一个或多个结点组成的有限集T，其中有一个结点称为根结点，其余结点可分为不相交的有限集T1，T2……Tn，而这些集合的每一个集合本身又都是一棵树，我们称之为该树的子树。 树的度、高度。 树的表示 数据域 指针域 二叉树可以是空 每个结点的度不超过2 子树有左、右之分，其次序不能颠倒 满二叉树、完全二叉树 左子树 右子树 度不超过2 可以为空 把起始于每一结点的分支除最左一个分支外，都去掉 从一个结点画一条边连接同一双亲的所有兄弟 以树的根结点为轴心，将整棵树顺时针旋转45o 传统设计中，工程资料是以手册（数表或线图）的形式提供的。 CAD系统帮助设计人员通过计算机自动检索所需的数据或线图等资料来获取所需的数据 如何将设计手册转化成计算数据？ 程序化方法 数据文件法 数据库法 一维数表 三角胶带传动弯曲影响系数Kw（×10-3） 49.8 26.6 7.5 2.65 1.03 0.39 Kw（i） 5 4 3 2 1 0 i 变量 E D C B A O 型号 Kw[i] Kw[0] Kw[1] Kw[2] 二维数表 2.25 1.75 1.5 kk(3,j) i=3 中等冲击 2.0 1.5 1.25 kk(2,j) i=2 轻度冲击 1.75 1.25 1.0 kk(1,j) i=1 工作平稳 kk(i,3) kk(i,2) kk(i,1) 工况系数 kk(i,j)