第3讲CAD中的数据结构.pptVIP

第三讲 CAD中的数据结构 通过CAD系统进行工程或产品设计的过程，实质上就是一个应用计算几进行信息处理的过程。 一、数据的组织形式 字段：也称数据项，是数据中最基本的、不可分的和有名字的数据元素。（齿轮零件号、材料牌号、模数、齿宽等） 二、数据的逻辑结构 数据的逻辑结构是指用户表达数据的形式，也称为数据的逻辑描述。分为：顺序结构、树状结构、网状结构。 在线性并列表中，栈和队列是用得最广泛的两种重要数据结构。 三、数据的物理结构 四、二叉树 五、图形数据结构 1、确定图形形状的完整信息 2、单个三维形体的存储结构 * 数据是计算机表达的主要形式，在设计过程中要产生、记录和加工大量的图形数据及各种其它设计资料数据。如何有效地存储和管理各种数据，是CAD技术的关键。 记录：相关的字段组成一个记录，它是字段的集合。这种记录也称为逻辑记录 文件：相同性质记录的集合就是文件。 数据库：是存储在计算机内部，可以按需要使用的、通用的、综合性的、减少重复存储程序的数据的集合。（数据库不只是文件的集合，还蕴涵对文件的重新组织，以便最大限度的减少文件中的重复数据，并增强数据文件之间和文件数据之间的相互联系） 数据库管理系统（DBMS）：应用程序从数据库中存取数据，是在数据库管理系统控制下，根据应用程序中的命令进行的。 1、顺序关系的数据结构（顺序结构） 是最简单的逻辑结构，数据节点是顺序排列的。因此每一节点只与它前一个和后一个节点相联系，节点间只存在着线性位置关系，故也称线性并列表。 线性并列表是x(1),x(2),…,x(n) (n0)的集合，其约束条件为：当n0时， x(1)是第一个节点，第k个节点x(k) (1kn)的前一节点是x(k-1)，后一节点是x(k+1)，最后节点为x(n)。数组就是该结构的例子。 栈：限定只能在表的一端进行插入和删除的线性表。该端称栈顶，另一端称栈底。遵循“后进先出”原则。机械装拆是其例子。 队列：限定只能在表的一端进行插入、另一端进行删除的线性表。插入端称队尾，删除端称队首。遵循“先进先出”原则。工件在流水线上的情况是其例子。 进栈 出栈 进队 出队 队首 队尾 栈顶 栈底 2、树状层次关系的数据结构（树状结构） 该结构的数据元素之间具有从属关系的层次结构。 机器 部件4 部件3 部件2 部件1 组件3 组件2 组件1 零件3 零件2 零件1 A B1 B2 B3 B4 C1 C2 C3 D1 D2 D3 树状结构只有一个根节点，称为树根。树状结构的特点是下一层中的节点只能有一条连线与它的上一层的一个节点相连。 树根 树叶 子树根 第一层 第二层 第三层 第四层 深度：层次数；度：节点孩子数；树的度：最大的节点度。 3、网状关系的数据结构（网状结构） 该结构能表达数据间更复杂的关系。 网状结构与树状结构的主要区别：树状结构的下层节点只能与一个上层节点连接，而网状结构的下层节点可与几个上层节点连接。 数据的物理结构即数据在计算机内的存储形式。 设计好数据的逻辑结构后，系统通过特定的软件把数据以及数据间的关系按一定的形式存入计算机存储器中，构成这些数据的存储结构，即物理结构。 把逻辑结构变换成物理结构的过程，称为映射。 逻辑结构设计一般多从用户的要求来考虑，而存储结构设计除考虑数据的逻辑结构外，还要考虑存储资源的充分利用、减少存取时间、便于数据修改、提高系统可靠性等存储结构本身的一些特点和要求。 逻辑结构与物理结构两者一般不一致，同一逻辑结构可以映射出多种物理结构。 数据的物理结构有两种最基本方式：顺序式与链式。 1、顺序存储结构 数据按一定顺序连续存放在计算机的存储单元中，不使用其它单元作为辅助信息。 是一种最简单的存储方式，数据元素间相隔固定距离，数据在逻辑上的顺序与它在计算机内的顺序是一致的。如一元数组，任一元素A(i)的地址ai,可用公式： ai = a1+(i-1)l (l为各数组元素占用的字节数） A(1) A(2) A(3) …… A(n-2) A(n-1) A(n) a1 a1+l a1+2l a1+(n-3)l a1+(n-2)l a1+(n-1)l 2、链式存储结构 存储单元不是按逻辑结构的顺序分配的，数据元素在存储器中可按任意顺序存放在任意位置上，数据元素的逻辑元素顺序与在存储器内部的存放顺序可以不同。 为了能正确地存放数据元素，随同每一个元素的存储还必须存储另一个元素的地址，称为链指针。 每个存储单元由数据域和指针域两部分构成。 数据域存放节点的值；指针域用来实现关系，即用来存放与该节点有某种关系的节点的存储单元地址。 这种通过指针来实现逻辑