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

1、机械CAD技术基础第4章 CAD数据结构机械CAD技术基础第4章 CAD数据结构24.1 基本概念基本概念4.2 线性表线性表4.3 栈栈4.4 树树4.5 二叉树二叉树机械CAD技术基础第4章 CAD数据结构3 一个孤立的具体数据往往没有任何意义。一个孤立的具体数据往往没有任何意义。 各相关数据的集合各相关数据的集合描述任何复杂事物。描述任何复杂事物。 数据之间的关系为数据赋予了丰富的含义。数据之间的关系为数据赋予了丰富的含义。数据结构数据结构-是数据之间的关系是数据之间的关系4.1 数据结构的概念车床的数据结构图车床的数据结构图机械CAD技术基础第4章 CAD数据结构4个体特征总体事物及其

2、联系现实世界实体属性实体集实体及其联系信息世界记录数据项文件数据组织（数据文件、数据库）计算机世界4.1.1数据结构的基本概念机械CAD技术基础第4章 CAD数据结构54.1.1 数据结构的基本概念数据结构的基本概念 客观存在的并可互相区分的事物；客观存在的并可互相区分的事物； 实体的特征；实体的特征； 每个属性所能测量或纪录的值每个属性所能测量或纪录的值 属性值的变化范围；属性值的变化范围；机械CAD技术基础第4章 CAD数据结构6 描述实体的数值、字符及其它的各种物理符号描述实体的数值、字符及其它的各种物理符号 是组成数据的最小单位；是组成数据的最小单位； 可用数字、字母、专用符号表示可用

3、数字、字母、专用符号表示 是数据中最基本的、不可分的并有命名的数据单位是数据中最基本的、不可分的并有命名的数据单位4.1.1数据结构的基本概念机械CAD技术基础第4章 CAD数据结构7 由若干个数据项组成；由若干个数据项组成； 相同性质的记录的集合就是文件相同性质的记录的集合就是文件 相关组合项和数据项的集合构成一个记录，是描述某个相关组合项和数据项的集合构成一个记录，是描述某个实体属性的集合实体属性的集合 非单纯性、有结构文件的集合非单纯性、有结构文件的集合4.1.1数据结构的基本概念机械CAD技术基础第4章 CAD数据结构8数据结构理论数据结构理论 研究数据元素之间的抽象化关系，并不涉及数

4、据元素的具体内容。以车床为研究数据元素之间的抽象化关系，并不涉及数据元素的具体内容。以车床为例：例：4.1.2数据结构机械CAD技术基础第4章 CAD数据结构9数据结构数据结构 逻辑结构逻辑结构物理结构物理结构1.1.数据的逻辑结构数据的逻辑结构 数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度组织和表达数据。组织和表达数据。逻辑结构归纳逻辑结构归纳为两大类型：为两大类型：线性结构线性结构非线性结构非线性结构树状结构树状结构网状结构网状结构树状网状的结合树状网状的结合4.1.2数据结构机械CAD技术基础第4章 CAD数据结构10l

5、 线性结构线性结构 每一个数据元素仅与它前面的一个和后面的一个数据元素相联系，每一个数据元素仅与它前面的一个和后面的一个数据元素相联系，因而只能表达数据间的简单顺序关系。因而只能表达数据间的简单顺序关系。 特点：特点：l 这种结构的数据可以用数表的形式表示。这种结构的数据可以用数表的形式表示。又称这类数据结构为又称这类数据结构为“线性表结构线性表结构”4.1.2数据结构机械CAD技术基础第4章 CAD数据结构11例如：线性表的逻辑结构例如：线性表的逻辑结构4.1.2数据结构机械CAD技术基础第4章 CAD数据结构12 这种结构的数据间逻辑关系比较复杂。这种结构的数据间逻辑关系比较复杂。4.1.

6、2数据结构机械CAD技术基础第4章 CAD数据结构13（1 1） 树状结构树状结构 数据之间的关系是一种层次式的逻辑关系，每个数据元素仅与数据之间的关系是一种层次式的逻辑关系，每个数据元素仅与它前面的一个数据元素相关，可与后面多个数据元素相关。它前面的一个数据元素相关，可与后面多个数据元素相关。4.1.2数据结构机械CAD技术基础第4章 CAD数据结构144.1.2数据结构机械CAD技术基础第4章 CAD数据结构15（2) 2) 网状结构网状结构 数据元素之间的关系是一种多元关系，即多对多、多数据元素之间的关系是一种多元关系，即多对多、多对一。对一。9412641078410584548912

7、445678 910工艺路线方案图工艺路线方案图4.1.2数据结构机械CAD技术基础第4章 CAD数据结构16（4 4）树状网状的结合）树状网状的结合(E4)V1(V4)V2V4(E6)(E5)E2E4E1F1（F2）(F4)(F4)四面体四面体四面体的逻辑结构图四面体的逻辑结构图GF1F2E2E4E4E6E5F4F4V4V4V1V2E14.1.2数据结构机械CAD技术基础第4章 CAD数据结构172.2. 数据的物理结构数据的物理结构 ( (1) 1) 顺序存储结构顺序存储结构 4.1.2数据结构机械CAD技术基础第4章 CAD数据结构184.1.2数据结构机械CAD技术基础第4章 CAD数

8、据结构19 一个数据元素项由两个字段组成一个数据元素项由两个字段组成 信息字段（信息字段（INFO）和指）和指针字段针字段(POINT)信息字段信息字段 存放数据元素本身的域存放数据元素本身的域指针字段指针字段 存放直接后继或直接前驱的域称为指针域存放直接后继或直接前驱的域称为指针域(point )。指针域中存储的信息称作指针。指针域中存储的信息称作指针。（2 2）链接存储结构）链接存储结构4.1.2数据结构机械CAD技术基础第4章 CAD数据结构20根据指针的数目，链接存根据指针的数目，链接存储结构有三种类型：储结构有三种类型： 4.1.2数据结构机械CAD技术基础第4章 CAD数据结构21

9、正向链：正向链：连接方向与逻辑顺序相同连接方向与逻辑顺序相同反向链：反向链：R1R2R4R4R5反向链 。 R1R2R4R4R54.1.2数据结构机械CAD技术基础第4章 CAD数据结构22单向环链：单向环链：最后一个数据元素与第一个数据元素通过指针链最后一个数据元素与第一个数据元素通过指针链接接单向环链R1R2R4R4R54.1.2数据结构机械CAD技术基础第4章 CAD数据结构23R1R2R4R4R5双向链R1R2R4R4R5双向链环链4.1.2数据结构机械CAD技术基础第4章 CAD数据结构24 R24 R12 R42 R21R224) 4) 多向链结构多向链结构4.1.2数据结构机械C

10、AD技术基础第4章 CAD数据结构25 R1R2R4R4R5R6链接存储结构的记录增删链接存储结构的记录增删R1R2R4R4R54.1.2数据结构机械CAD技术基础第4章 CAD数据结构26线线性性结结构构非非线线性性结结构构图与网图与网4.1.4 常见的数据结构机械CAD技术基础第4章 CAD数据结构27 4.2 线性表机械CAD技术基础第4章 CAD数据结构28。4.2 线性表机械CAD技术基础第4章 CAD数据结构4.3 栈 机械CAD技术基础第4章 CAD数据结构30 4.3 栈机械CAD技术基础第4章 CAD数据结构4.4 队列 允许删除的一端叫队头允许删除的一端叫队头。 。机械CA

11、D技术基础第4章 CAD数据结构32 4.5 数 组机械CAD技术基础第4章 CAD数据结构33（1 1）树）树4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构34 4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构35 A B K F C J E G D H M I L机械CAD技术基础第4章 CAD数据结构36B C DE F G H I J A K L M 机械CAD技术基础第4章 CAD数据结构37传动系统图传动系统图逻辑结构图逻辑结构图物理结构图物理结构图4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构38机械CAD技术基础第4章 CAD数据结构39（2

12、2）二叉树）二叉树AABBA只有左子树的只有左子树的两叉树两叉树ACB全两叉树全两叉树4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构40HGEDFCBAI 两叉树的逻辑结构两叉树的逻辑结构ABGEFDIHC两叉树的物理结构两叉树的物理结构4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构41HGEDFCBAI前序遍历前序遍历3）二叉树的遍历）二叉树的遍历4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构42HGEDFCBAI中序遍历中序遍历 4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构43HGEDFCBAI后序遍历后序遍历4.6 树与二叉树机械CAD技术基础第4章 CAD数据结构44 154424.7 图与网机械CAD技术基础第4章 CAD数据结构4515442 1 1）以数组的方式顺序存储，）以数组的方式顺序存储，2 2）多向链