第四章机械 CAD中常见的数据结构本章介绍
CAD系统进行工程或者产品设计的过程,
实质上就是应用计算机进行信息处理的过程 。
在这个过程中会产生大量用于表达产品信息的数据,文字和图形 。 如何有效的使用和管理各类数据,是 CAD技术的重要指标 。
对于 CAD系统,各类支撑软件是其重要组成部分 。 所以,软件设计技术的理论基础,
,数据结构,就不仅仅是计算机学科的核心课程,也应该是所有应用计算机的其他学科,
譬如机械 CAD所应该掌握的课程课程内容
1、基本概念和术语
2、数据的物理结构
3、数据的逻辑结构
4.1、基本概念和术语数据（ Data）
数据 对客观事物的符号表示，是信息的载体。
它能够被计算机识别、存储和加工处理，的符号的总称，是计算机程序加工的,原料,。
随着计算机应用领域的扩大，数据的范畴包括：
整数、实数、字符串、图像和声音等。
数据元素（ Data Element）
数据元素 是数据的基本单位，是数据这个集合中相对独立的个体。数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个 数据项
（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据类型
数据类型是程序设计语言提供的变量类别。每一种程序设计语言都提供一组基本的数据类型
对于 C语言，它提供了字符型、整型、
浮点型和枚举型四种基本数据类型，和结构型数据类型。数据类型确定了数据元素的基本特点和允许的操作。
数据结构（ Data Structure）
数据结构 指的是数据之间的相互关系，
即数据的组织形式。
1．数据结构一般包括以下三方面内容：
① 数据元素之间的逻辑关系，也称 数据的逻辑结构 （ Logical Structure）；
数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
例如：见课本 p56页，汽车的数据结构。
② 数据元素及其关系在计算机存储器内的表示，称为 数据的存储结构 （ Storage
Structure）；
数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），是数据元素和它们之间的关系在计算机中的表示。它依赖于计算机语言。结点是一个数据元素对应的位串，是数据元素在计算机中的映象。
③ 数据的运算,即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，
每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓 抽象的操作,是指我们只知道这些操作是 "做什么 "，而无须考虑 "如何做 "。只有确定了存储结构之后，才考虑如何具体实现这些运算。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【 例 1,1】 学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念学号 姓名 语文 化学 数学 物理 英语
0801 丁一 78 67 79 89 91
0802 马二 86 68 64 78 46
0803 张三 78 67 57 89 56
（ 1）逻辑结构表中的每一行是一个数据元素（或记录、结点），
它由学号、姓名、各科成绩等数据项组成。
表中数据元素之间的逻辑关系是：对表中任一个结点，
与它相邻且在它前面的结点（亦称为直接前趋
（ Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继
（ Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。
例如，表中 "马二 "所在结点的直接前趋结点和直接后继结点分别是 "丁一 "和 "张三 "所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。
（ 2）存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？
（ 3）数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，
这就是数据的运算问题。
搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。
数据结构三方面的关系
数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。
存储结构是数据结构不可缺少的一个方面：
同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。
【 例 】 线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。
数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，
也可能导致完全不同的数据结构。
【 例 】 若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；
若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。
更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。
4.2 线性表
线性表是一种最常见的数据结构。
它是 N个数据元素的有限序列
（ a1,a2…,an）
数据元素 ai可以是一个数，一个符号，
也可一是更为复杂的数据结构。
举例：课本 P56
4.2.1 线性表的顺序存储结构
什么是顺序存储结构？
把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构
（ Sequential Storage Structure），通常借助程序语言的数组描述。
该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
线性表的顺序存储结构的特点
1,有序性
2,均匀性
顺序存储的线性表的运算数组是典型的顺序存储的线性表，数组名是线性表的地址，也是线性表的第一个元素的地址。通过对数组的说明和运算可以实现对线性表的顺序存储和运算。
线性表的运算（ P57）
1,建表
2,访问
3,修改
4,删除
5,插入
4.2.2 线性表的链式存储结构
1,链式存储结构的特点对于任意一组存储单元存放的数据元素，由于存储单元可以是不连续的，因此还要存储这个元素直接前趋或直接后继的位置。这两种信息组成数据元素的映像成为结点。
结点有两个域：
数据域,存放数据元素本身指针域,存放直接前趋或直接后继的域课本 P59图 4－ 5示意图
2,单向链表单向链表的有一个指针域，用来存放直接后继的地址需要设定一个头指针，用来存放第一个元素的地址。数据域可以为空。
对单向链表可以进行访问、修改、删除、插入运算。
课本 P60 例 4－ 3
3,双向链表单向链式存储结构的结点只有一个存放直接后继的指针域，因此只能从某个结点出发向后寻找其他结点。
如果结点增设一个指针域，存放它的直接前趋的地址，就可以向前寻找其他结点。这样的链表称为双向链表。同样双向链表也有访问、修改、删除或者插入的运算。
课本 P64 例题 4－ 8
链式存储与顺序存储相比，有一些特点
1,删除或者插入运算速度快，因为在运算过程中数据不需要移动。
2,不需要事先分配存储空间，以免有些空间不能充分利用。
3,表的容量易于扩充。
4,按逻辑顺序查找的速度慢。
5,与等长度的顺序存储多占用作为指针域的存储空间。
4.3 栈
4.3.1 栈的结构
1、栈的逻辑结构栈也是一种特殊的线性表。它的特别之处在于运算只限于表尾的一端。
课本 P68页 图 4－ 13
2、栈的存储结构顺序存储或者链式存储都可以作为栈的存储结构，但由于运算一般只限于栈顶，且长度可以预测，通常采用顺序存储作为栈的存储结构。
4.3.2 栈的运算
1,栈的建立：用数组来说明栈的存储结构
2,进栈
3,出栈栈的运算过程见课本 P68图 4－ 13和 4－ 14
4.3.3 栈的应用实例在常见的交互式图形系统中建立存放显示区域的栈，每当确定新的显示区域时当前的显示区进栈，这样可以方面的恢复到前面的显示区域。
例题 4－ 10
确定各轴之间传动关系的数据结构建立求解传动路线的栈编写程序流程图 编程
4.4 树
4.4.1 树的逻辑结构树根、根结点树叶、终端结点边结点的双亲结点的孩子兄弟树的深度或高度树的度数
4.4.2 树的存储结构由于树的逻辑结构是非线性的，所以只能采用链式存储结构。分为定长或不定长两种方式。
1、定长方式以具有最大度数的结点的结构作为该树所有结点的结构。这样，每个结点都有相同数量的子树域。
特点：所有结点同构，运算方便；浪费空间如图 P72页 图 4－ 18,4－ 19
2、不定长方式每个结点增加一个存放度数的域，结点的长度随着度数的增加而增加。
特点：节省了存储空间，但是运算不方便。
4.4.3 树结构的应用举例课本 P73 轴系问题就是一个典型的树型结构问题。
4.5 二叉树
4.5.1 二叉树的逻辑结构
1、定义二叉树是一种特殊的树，它的每个结点最多有两棵子树，子树有左右之分。二叉树可以为空。二叉树的深度和度的定义与树相同。
2、特殊的二叉树
（ 1）满二叉树
（ 2）顺序二叉树
（ 3）完全二叉树课本 P76 如图 4－ 24
4.5.2 二叉树的存储结构对于一般的二叉树，可以采用链表存储结构。
如图 4－ 26。这种存储结构会多占一些存储空间，但是便于运算。
对于满二叉树和顺序二叉树，也可以采用顺序存储结构。这种结构节省存储空间，方便的查找结点。但是不便于删除和插入运算。
4.5.3 二叉树的遍历按照一定的规律走遍二叉树的每个结点，使每个结点被访问一次且只访问一次，叫做二叉树的遍历。常见的三种遍历方式：
（ 1）先序遍历
（ 2）中序遍历
（ 3）后序遍历
4.5.4 树的二叉树表示如何将树转换成为二叉树：
1、树的根结点作为二叉树的根结点
2、根结点最左端的孩子作为二叉树的左子树。
3、根结点的左端第二个孩子作为左端第一个孩子的右子树。
见课本 p78 图 4－ 31
小结
学习了数据结构的基本概念和一些专业术语
了解几种常见的数据结构
掌握这几种数据结构的物理结构和逻辑结构
了解数据结构的运算方式
CAD系统进行工程或者产品设计的过程,
实质上就是应用计算机进行信息处理的过程 。
在这个过程中会产生大量用于表达产品信息的数据,文字和图形 。 如何有效的使用和管理各类数据,是 CAD技术的重要指标 。
对于 CAD系统,各类支撑软件是其重要组成部分 。 所以,软件设计技术的理论基础,
,数据结构,就不仅仅是计算机学科的核心课程,也应该是所有应用计算机的其他学科,
譬如机械 CAD所应该掌握的课程课程内容
1、基本概念和术语
2、数据的物理结构
3、数据的逻辑结构
4.1、基本概念和术语数据（ Data）
数据 对客观事物的符号表示，是信息的载体。
它能够被计算机识别、存储和加工处理，的符号的总称，是计算机程序加工的,原料,。
随着计算机应用领域的扩大，数据的范畴包括：
整数、实数、字符串、图像和声音等。
数据元素（ Data Element）
数据元素 是数据的基本单位，是数据这个集合中相对独立的个体。数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个 数据项
（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据类型
数据类型是程序设计语言提供的变量类别。每一种程序设计语言都提供一组基本的数据类型
对于 C语言，它提供了字符型、整型、
浮点型和枚举型四种基本数据类型，和结构型数据类型。数据类型确定了数据元素的基本特点和允许的操作。
数据结构（ Data Structure）
数据结构 指的是数据之间的相互关系，
即数据的组织形式。
1．数据结构一般包括以下三方面内容：
① 数据元素之间的逻辑关系，也称 数据的逻辑结构 （ Logical Structure）；
数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
例如：见课本 p56页，汽车的数据结构。
② 数据元素及其关系在计算机存储器内的表示，称为 数据的存储结构 （ Storage
Structure）；
数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），是数据元素和它们之间的关系在计算机中的表示。它依赖于计算机语言。结点是一个数据元素对应的位串，是数据元素在计算机中的映象。
③ 数据的运算,即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，
每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓 抽象的操作,是指我们只知道这些操作是 "做什么 "，而无须考虑 "如何做 "。只有确定了存储结构之后，才考虑如何具体实现这些运算。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【 例 1,1】 学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念学号 姓名 语文 化学 数学 物理 英语
0801 丁一 78 67 79 89 91
0802 马二 86 68 64 78 46
0803 张三 78 67 57 89 56
（ 1）逻辑结构表中的每一行是一个数据元素（或记录、结点），
它由学号、姓名、各科成绩等数据项组成。
表中数据元素之间的逻辑关系是：对表中任一个结点，
与它相邻且在它前面的结点（亦称为直接前趋
（ Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继
（ Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。
例如，表中 "马二 "所在结点的直接前趋结点和直接后继结点分别是 "丁一 "和 "张三 "所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。
（ 2）存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？
（ 3）数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，
这就是数据的运算问题。
搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。
数据结构三方面的关系
数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。
存储结构是数据结构不可缺少的一个方面：
同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。
【 例 】 线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。
数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，
也可能导致完全不同的数据结构。
【 例 】 若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；
若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。
更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。
4.2 线性表
线性表是一种最常见的数据结构。
它是 N个数据元素的有限序列
（ a1,a2…,an）
数据元素 ai可以是一个数，一个符号，
也可一是更为复杂的数据结构。
举例：课本 P56
4.2.1 线性表的顺序存储结构
什么是顺序存储结构？
把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构
（ Sequential Storage Structure），通常借助程序语言的数组描述。
该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
线性表的顺序存储结构的特点
1,有序性
2,均匀性
顺序存储的线性表的运算数组是典型的顺序存储的线性表，数组名是线性表的地址，也是线性表的第一个元素的地址。通过对数组的说明和运算可以实现对线性表的顺序存储和运算。
线性表的运算（ P57）
1,建表
2,访问
3,修改
4,删除
5,插入
4.2.2 线性表的链式存储结构
1,链式存储结构的特点对于任意一组存储单元存放的数据元素，由于存储单元可以是不连续的，因此还要存储这个元素直接前趋或直接后继的位置。这两种信息组成数据元素的映像成为结点。
结点有两个域：
数据域,存放数据元素本身指针域,存放直接前趋或直接后继的域课本 P59图 4－ 5示意图
2,单向链表单向链表的有一个指针域，用来存放直接后继的地址需要设定一个头指针，用来存放第一个元素的地址。数据域可以为空。
对单向链表可以进行访问、修改、删除、插入运算。
课本 P60 例 4－ 3
3,双向链表单向链式存储结构的结点只有一个存放直接后继的指针域，因此只能从某个结点出发向后寻找其他结点。
如果结点增设一个指针域，存放它的直接前趋的地址，就可以向前寻找其他结点。这样的链表称为双向链表。同样双向链表也有访问、修改、删除或者插入的运算。
课本 P64 例题 4－ 8
链式存储与顺序存储相比，有一些特点
1,删除或者插入运算速度快，因为在运算过程中数据不需要移动。
2,不需要事先分配存储空间，以免有些空间不能充分利用。
3,表的容量易于扩充。
4,按逻辑顺序查找的速度慢。
5,与等长度的顺序存储多占用作为指针域的存储空间。
4.3 栈
4.3.1 栈的结构
1、栈的逻辑结构栈也是一种特殊的线性表。它的特别之处在于运算只限于表尾的一端。
课本 P68页 图 4－ 13
2、栈的存储结构顺序存储或者链式存储都可以作为栈的存储结构，但由于运算一般只限于栈顶，且长度可以预测，通常采用顺序存储作为栈的存储结构。
4.3.2 栈的运算
1,栈的建立：用数组来说明栈的存储结构
2,进栈
3,出栈栈的运算过程见课本 P68图 4－ 13和 4－ 14
4.3.3 栈的应用实例在常见的交互式图形系统中建立存放显示区域的栈，每当确定新的显示区域时当前的显示区进栈，这样可以方面的恢复到前面的显示区域。
例题 4－ 10
确定各轴之间传动关系的数据结构建立求解传动路线的栈编写程序流程图 编程
4.4 树
4.4.1 树的逻辑结构树根、根结点树叶、终端结点边结点的双亲结点的孩子兄弟树的深度或高度树的度数
4.4.2 树的存储结构由于树的逻辑结构是非线性的，所以只能采用链式存储结构。分为定长或不定长两种方式。
1、定长方式以具有最大度数的结点的结构作为该树所有结点的结构。这样，每个结点都有相同数量的子树域。
特点：所有结点同构，运算方便；浪费空间如图 P72页 图 4－ 18,4－ 19
2、不定长方式每个结点增加一个存放度数的域，结点的长度随着度数的增加而增加。
特点：节省了存储空间，但是运算不方便。
4.4.3 树结构的应用举例课本 P73 轴系问题就是一个典型的树型结构问题。
4.5 二叉树
4.5.1 二叉树的逻辑结构
1、定义二叉树是一种特殊的树，它的每个结点最多有两棵子树，子树有左右之分。二叉树可以为空。二叉树的深度和度的定义与树相同。
2、特殊的二叉树
（ 1）满二叉树
（ 2）顺序二叉树
（ 3）完全二叉树课本 P76 如图 4－ 24
4.5.2 二叉树的存储结构对于一般的二叉树，可以采用链表存储结构。
如图 4－ 26。这种存储结构会多占一些存储空间，但是便于运算。
对于满二叉树和顺序二叉树，也可以采用顺序存储结构。这种结构节省存储空间，方便的查找结点。但是不便于删除和插入运算。
4.5.3 二叉树的遍历按照一定的规律走遍二叉树的每个结点，使每个结点被访问一次且只访问一次，叫做二叉树的遍历。常见的三种遍历方式：
（ 1）先序遍历
（ 2）中序遍历
（ 3）后序遍历
4.5.4 树的二叉树表示如何将树转换成为二叉树：
1、树的根结点作为二叉树的根结点
2、根结点最左端的孩子作为二叉树的左子树。
3、根结点的左端第二个孩子作为左端第一个孩子的右子树。
见课本 p78 图 4－ 31
小结
学习了数据结构的基本概念和一些专业术语
了解几种常见的数据结构
掌握这几种数据结构的物理结构和逻辑结构
了解数据结构的运算方式
