a方向第4章_cad中常用的数据结构 (1)

机械 CAD技术基础第 4章 CAD数据结构机械 CAD技术基础第 4章 CAD数据结构2主要内容主要内容4.1 基本概念4.2 线性表4.3 栈4.4 树4.5 二叉树机械 CAD技术基础第 4章 CAD数据结构3一个孤立的具体数据往往没有任何意义。各相关数据的集合 描述任何复杂事物。数据之间的关系为数据赋予了丰富的含义。数据结构 -是数据之间的关系车床车床床身及导床身及导 轨轨 主轴箱主轴箱 尾座尾座 走刀箱走刀箱 溜板箱溜板箱 刀架刀架离合器离合器 主轴组件主轴组件 中间变速机中间变速机 构构主轴主轴 主轴齿轮主轴齿轮 主轴轴承主轴轴承4.1 数据结构的概念车床的数据结构图机械 CAD技术基础第 4章 CAD数据结构4在数据处理中，现实世界在数据处理中，现实世界 信息世界信息世界 数据世界。数据世界。个体特征总体事物及其联系现实世界实体属性实体集实体及其联系信息世界记录数据项文件数据组织（数据文件、数据库）计算机世界4.1.1数据结构的基本概念包含几个层次概念：包含几个层次概念：机械 CAD技术基础第 4章 CAD数据结构54.1.1 数据结构的基本概念(1) 实体实体 客观存在的并可互相区分的事物；(2) 属性属性 实体的特征；(3) 属性值属性值 每个属性所能测量或纪录的值(4) 域域 属性值的变化范围；机械 CAD技术基础第 4章 CAD数据结构6（ 1）数据）数据 描述实体的数值、字符及其它的各种物理符号（ 2）字符）字符 是组成数据的最小单位； 可用数字、字母、专用符号表示（ 3）数据项）数据项 是数据中最基本的、不可分的并有命名的数据单位4.1.1数据结构的基本概念机械 CAD技术基础第 4章 CAD数据结构7（ 1）组合项）组合项 由若干个数据项组成；（ 2）文件）文件 相同性质的记录的集合就是文件（ 3）记录）记录 相关组合项和数据项的集合构成一个记录，是描述某个 实体属性的集合（ 4）数据库）数据库 非单纯性、有结构文件的集合4.1.1数据结构的基本概念机械 CAD技术基础第 4章 CAD数据结构8数据结构理论 研究数据元素之间的抽象化关系，并不涉及数据元素的具体内容。以车床为例：车床车床床身及导床身及导轨轨 主轴箱主轴箱 尾座尾座 走刀箱走刀箱 溜板箱溜板箱 刀架刀架离合器离合器 主轴组件主轴组件 中间变速中间变速 机构机构主轴主轴 主轴齿轮主轴齿轮 主轴轴承主轴轴承4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构9数据结构 包括数据的包括数据的 逻辑结构 和数据的和数据的 物理结构 。1. 数据的逻辑结构 定义：定义： 数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度组织和表达数据。逻辑结构归纳为两大类型：线性结构非线性结构树状结构网状结构树状网状的结合4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构10l 线性结构 每一个数据元素仅与它前面的一个和后面的一个数据元素相联系，因而只能表达数据间的简单顺序关系。 特点： 数据间的关系很简单，只是顺序排列的位置关系，而且这种位置数据间的关系很简单，只是顺序排列的位置关系，而且这种位置关系是线性的。关系是线性的。l 这种结构的数据可以用数表的形式表示。又称这类数据结构为 “线性表结构 ”4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构11例如：线性表的逻辑结构4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构12l非线性结构非线性结构 这种结构的数据间逻辑关系比较复杂。类型：类型： 树状结构、网状结构及树状网状的结合树状结构、网状结构及树状网状的结合4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构13（ 1） 树状结构 数据之间的关系是一种层次式的逻辑关系，每个数据元素仅与它前面的一个数据元素相关，可与后面多个数据元素相关。车床车床床身及导床身及导 轨轨 主轴箱主轴箱 尾座尾座 走刀箱走刀箱 溜板箱溜板箱 刀架刀架离合器离合器 主轴组件主轴组件 中间变速机中间变速机 构构主轴主轴 主轴齿轮主轴齿轮 主轴轴承主轴轴承4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构144.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构15（ 2) 网状结构 数据元素之间的关系是一种多元关系，即多对多、多对一。9412 641078410 584548912445678 910工艺路线方案图4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构16（ 4）树状网状的结合(E4)V1(V4)V2 V4(E6)(E5)E2E4E1F1（ F2）(F4)(F4)四面体 四面体的逻辑结构图GF1 F2E2 E4 E4 E6E5F4 F4V4V4V1 V2E14.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构172. 数据的物理结构定义定义 : 是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及数据间的关系。数据间的关系。l 常用种类常用种类 : 顺序存储结构、链接存储结构顺序存储结构、链接存储结构 。(1) 顺序存储结构 定义定义 : 利用一组地址连续的存储单元依次存放各数据元素。利用一组地址连续的存储单元依次存放各数据元素。 4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构18特点：特点： 1）存储单元少，简单易行，结构紧凑。）存储单元少，简单易行，结构紧凑。2）数据结构缺乏柔性，若要增删数据，必须重新分配存储单元。）数据结构缺乏柔性，若要增删数据，必须重新分配存储单元。应用应用 ： 查询频繁，修改、补充、删除数据量小的场合查询频繁，修改、补充、删除数据量小的场合 。4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构19用一组任意的存储单元存储数据元素用一组任意的存储单元存储数据元素 (这组存储单元可以是连续的，也可这组存储单元可以是连续的，也可以是不连续的以是不连续的 )。信息字段信息字段结构形式结构形式 ： 一个数据元素项由两个字段组成 信息字段（ INFO）和指针字段 (POINT)指针字段指针字段信息字段 存放数据元素本身的域指针字段 存放直接后继或直接前驱的域称为指针域 (point )。指针域中存储的信息称作指针。（ 2）链接存储结构4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构20u存储结构可独立于逻辑结构。存储结构可独立于逻辑结构。存储的物理顺序不必与逻辑顺序一致而仍能按逻辑要求存取数据。存储的物理顺序不必与逻辑顺序一致而仍能按逻辑要求存取数据。特点：特点： 链接存储结构在不改变原来存储结构的条件下，增删记录十分链接存储结构在不改变原来存储结构的条件下，增删记录十分方便，只要控制指针即可。方便，只要控制指针即可。根据指针的数目，链接存储结构有三种类型：单向链结构单向链结构 双向链结构双向链结构多向链结构多向链结构4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构21正向链： 连接方向与逻辑顺序相同反向链： 连接方向与逻辑顺序相反连接方向与逻辑顺序相反R1 R2 R4 R4 R5反向链1) 单向链结构单向链结构 各个数据元素由各个数据元素由 一个指针域一个指针域 和和 一个数据域组成一个数据域组成 ，通过指针构成一个链状结，通过指针构成一个链状结构，且链接方向单一构，且链接方向单一 。 R1 R2 R4 R4 R54.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构22单向环链： 最后一个数据元素与第一个数据元素通过指针链接特点：特点： 可以从任意一个元素进入，按指针逐个存取各条记录；可以从任意一个元素进入，按指针逐个存取各条记录； 某个指针损坏不影响整个结构。某个指针损坏不影响整个结构。单向环链R1 R2 R4 R4 R54.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构232）双向链结构）双向链结构双向链结构中有双向链结构中有 两个指针域两个指针域 ，分别按正、反两个方向链接。，分别按正、反两个方向链接。R1 R2 R4 R4 R5双向链R1 R2 R4 R4 R5双向链环链4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构24结构中有多个指针域（多于结构中有多个指针域（多于 2个）个）应用：应用： 通常用于矩阵元素、树结构存储，只要查询到某一元素，即可通常用于矩阵元素、树结构存储，只要查询到某一元素，即可获得相邻的、相关元素的地址。获得相邻的、相关元素的地址。R24 R12R42 R21R224) 多向链结构4.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构25链接存储结构的记录增、删链接存储结构的记录增、删 在不改变原来存储结构的条件下，只要控制指针即可在不改变原来存储结构的条件下，只要控制指针即可R1 R2 R4 R4 R5R6链接存储结构的记录增删R1 R2 R4 R4 R54.1.2数据结构机械 CAD技术基础第 4章 CAD数据结构26线性结构 串串非线性结构树与二叉树树与二叉树图与网4.1.4 常见的数据结构数组数组线性表线性表栈栈队列队列机械 CAD技术基础第 4章 CAD数据结构27线性表是一个由线性表是一个由 n（ n0）个数据元素）个数据元素 a1， a2， a4 a n组成的有组成的有限序列，表中的每一个数据元素限序列，表中的每一个数据元素 (除了第一个和最后一个除了第一个和最后一个 )仅有仅有一个直接前驱和直接后继。一个直接前驱和直接后继。定义定义 :线性表逻辑结构线性表逻辑结构 a(1)， a(2)， a(4)， ,a(k-1) ， a(k)， a(k+1)， ， a(n) 例如：例如： 光轴轴径系列值表示成线性表形式光轴轴径系列值表示成线性表形式 : （ 4， 6， 10， 14， 18， 20，22， ,90） 4.2 线性表机械 CAD技术基础第 4章 CAD数据结构28特点：特点： 数据元素之间呈线性关系，是最简单、最常见的数据结构。数据元素之间呈线性关系，是最简单、最常见的数据结构。线性表的物理结构线性表的物理结构 既可以采用顺序存储，也可以采用链接存储结既可以采用顺序存储，也可以采用链接存储结构构 。4.2 线性表机械 CAD技术基础第 4章 CAD数据结构4.3 栈定义定义 : 栈是一种特殊的线性表，它的插入与删除操作只能在表的一栈是一种特殊的线性