常用图形数据结构.ppt

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