CAD常用数据结构ppt课件.ppt

第2章 CAD常用的数据结构,CAD内部以及CAD与CAPP、CAM之间的数据集成：要求用户提供给计算机的已不是简单的、孤立的数据，而是存在一定关系的批量数据。这些数据是计算机操作的原材料，需要事先进行组织构造，让它们按照某种具体的结构形式相互关联在一起，这种关联就是数据结构。合理的数据结构：不但可以减少程序所占空间，还可以减少程序运行所用的时间。 本章介绍CAD常用的数据结构: 包括数组、栈、队、链表、树 和二叉树。,2.1 基本概念,1.数据：是对客观事物的符号表示，在计算机中是指所有能输入到计算机中并被计算机程序处理的符号总称。数值、字符是数据，图形、图像也是数据。2.数据元素：是数据的基本单位，是数据这个集合中相对独立的个体。数据元素本身可能是简单的，也可能是复杂的。 在复杂的线性表中，一个数据元素可以由若干个数据项组成，此时常把数据元素称为记录，而含有大量记录的线性表称为文件。,3.数据的逻辑结构:通常所说的数据结构一般是指数据的逻辑结构。数据的逻辑结构仅考虑数据之间的逻辑关系，它独立于数据的存储介质。4.数据的物理结构:数据的物理结构也称为数据的存储结构，是数据元素和它们之间的关系在计算机中的表示。5.数据类型:数据类型是程序设计语言允许变量的种类。每一种程序设计语言都提供一组基本的数据类型。C语言提供字符型、整型、浮点型和双精度型4种基本的数据类型。,2.2 线性表,定义：n个数据元素的有限序列 一个数据元素可以由若干个数据项（Item）组成，此时，常把数据元素称为记录（ Record ），含有大量记录的线性表又称为文件（File）。（a1,a2,a3,an）表中元素的个数n定义为线性表的长度(n=0)，n=0的表称为空表。,2.2.1 线性表的逻辑结构,1) 线性表是数据元素的一个有限序列。 2) 线性表中数据元素的个数定义为线性表的长度n，当n =0时，为空表 。 3)数据元素在线性表的位置取决于它们自己的序号，数据元素之间的相对位置是线性的，如a1是第一个元素，an是最后一个元素。 4)除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。 所有数据元素ai在同一个线性表中必须是相同的数据类型。,线性表的特点：,2.2.2 线性表的存储结构,1.线性表的顺序存储结构 顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放。数据元素在存储器中的存放地址和该元素的下标一一对应。假定一个线性表A(n)，它的每个数据元素占l个存储单元，第一个数据元素在内存中的开始地址为L(a1)，那么，第i个数据元素的存储位置为L(ai)=L(a1)+(i-1)l,(1) 有序性：各数据元素之间的存储顺序与逻辑顺序一致。(2) 均匀性：每个数据元素所占存储空间的长度是相等的。根据以上特点不难看出程序设计语言中的数组是典型的顺序存储的线性表。因此用程序建立顺序存储的线性表及对该表的运算，可通过对数组的说明和运算来实现。,线性表顺序存储结构的特点,举例,2.线性表的链式存储结构 链式存储就是用一组任意的存储单元存放表中的数据元素。结点：数据域、指针域数据域：用于存放数据元素值；指针域：用于存放直接前驱或直接后继结点的地址（指针）。,2.2.3 数组,几乎所有的程序设计语言都把数组作为固有数据类型。数组可以看成是线性表的扩充，数组的存储也采用顺序分配的原则，即在存储器中开辟一块连续的存储空间，依次存放数组的各个元素。 我们可以用数组来顺序地表示线性表，线性表是一个一维表，与线性表不同的是，数组可以是多维的。 如A(i)，B(i, j)，C(j1, j2, j3, , jn)都可以表示一个数组， A(4)是一维数组，数组长度为4； B(3, 5)是二维数组，第一维长度为3，第二维长度为5。,2.2.4 栈,1.栈的逻辑结构 栈也是线性表，它与普通线性表的区别就在于对它的运算仅限定在表尾。 假定栈s=(a1, a2, a3, , ai-1, ai, ai+1, , an)，则a1称为栈底元素，an为栈顶元素。进栈的顺序是a1, a2, a3, , an)，出栈的顺序是an, an-1, , a3, a2, a1。它的显著特点是后进先出(LIFO, Last In First Out)。,2.栈的存储结构 理论上讲，顺序存储或链式存储都可以作为栈的存储结构。由于栈的容量一般是可以预见的，而且运算仅限于栈顶，所以通常采用顺序存储作为栈的存储结构。,3.栈的运算建栈 栈的存储结构用数组sn。设一栈顶指针为TOP，它不必指向数据元素的实际地址，只记录数据元素的逻辑序号即可。当元素尚未进栈时，令TOP等于-1。进栈 如果有元素进栈，首先检查栈顶指针TOP，如果TOP等于m，表示栈满。如果TOP-1，出栈元素为sTOP，然后令TOP=TOP-1。,4.栈的应用举例 栈是一种应用很广的数据结构。例如在交互式图形系统中，将显示区域存入栈中，需要时可以恢复前几次的显示状态。用栈存放每次操作的命令，可以恢复到前几个命令时的状态。在计算机语言编译系统中，栈是一个非常重要的数据结构。,队列是两端开口的线性表，队列只限定在表的一端进行插入操作，在表的另一端进行删除操作。允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”。如图2.5所示，a1是队头元素，an是队尾元素，队列中元素以a1, a2, a3, , an的次序入队，也以同样的次序出队，其工作方式是先进先出(FIFO, First In First Out)，与栈的工作方式刚好相反。,2.2.5 队列,在对队列进行运算时，由于队列的两端均可浮动，因此，需要设立两个指针，分别指向队头(Front)和队尾(Rear)。这里规定指针Front总是指向实际队头的前一位置，而指针Rear指向队尾元素。 显然，当Rear=0或Front=Rear时，队列为空；当Rear等于上界时，队列满。 队列的主要运算是入队和出队。入队时，队尾指针加1；出队时，队头指针加1。,举例 计算机程序设计中经常用到队列结构。最典型的例子是操作系统中的作业排队，当系统中有多道程序运行时，可能同时有几个作业的运行结果需要通过通道输出，这就要按申请的先后次序排队。申请输出的作业从队尾进行队列，当通道传输完一个作业，要接受一个新作业时，队头的作业先从队列中退出输出操作。,2.2.6 单向链表,单向链表结点的指针域只有一个，通常存放直接后继的地址。第一个元素的地址需要专门存放在指定的指针型变量中，或者设置一个与链表结点相同的一个结点, 它的数据域可以是空的, 也可以存放表长等附加信息, 指针域存放第一个元素的地址。单向链表的最后一个节点的指针域是空的。如下图所示：,数据域 指针域Data nextPtr,节点,1.建立单向链表 假定线性表为(A，B，C，D，E)，将其按单向链表存储。首先定义结点的数据类型，它有两个成员；data和nextPtr。data是用来存放数据元素本身，所以，本例它应该是字符的。一个或多个普通类型的变量组成了该结点的数据域。nextPtr存放该结点的直接后继的地址，所以它应该是指针型的，而且是指向该结点（struct slink）类型数据的指针。,数据域 指针域Data nextPtr,节点,2.访问链表中数据元素的存储顺序与逻辑顺序无关。如果访问第i个元素，首先通过链头结点h找到第一个结点的指针域找到第二个结点；直至找到第i个结点，即可访问该结点的数据域。3.修改修改第i个元素的值，将第i个数据元素的值改为M。首先找到该结点，然后修改这个结点的数据域。,4.删除若删除第i个元素M，则要找到第i-1和第i个结点，并将第i-1个结点的指针域中第i个结点的地址改为第i+1个结点的地址，最后释放第i个结点所占的存储空间。删除操作如图2.6所示。,i-1,i,5.插入在第i个数据元素之前插入一个数值为M的元素，首先要为该元素申请一个新结点作为存储空间，在新结点的数据域存放数值M，再找到第i-1个结点，令新结点指针域的指针等于第i-1个结点指针域的指针，修改第i-1个结点的指针，让其存放这个新结点的地址。即让第i-1个结点指向新结点，而新结点指向第i个结点即可。插入操作如图2.7所示。,i,i-1,单向链表只给出结点的直接后继地址，因此从某个节点出发只能向后寻找其他结点。如果在每个结点的指针域增加一个指针域，用来存放结点的直接前趋地址，就可以方便地从每个结点向前寻找其他结点。这样的链表称为双向链表。如下图所示：,2.2.7 双向链表,1.建立双向链表 假定线性表为(A，B，C，D，E)，将其按双向链表存储。首先要定义结点的数据类型，它有3个成员，data、nextPtr和prePtr。data用来存放数据元素的数值，nextPtr用来存放结点直接后继的地址，prePtr存放结点直接前趋的地址。head和rear分别为链头和链尾结点。,nextPtr Data prePtr,2.访问 双向链表可以像单向链表那样从链头结点head开始找到第i个结点，还可以从链尾结点开始找到后起的第j个结点。3.修改 若修改第i个结点的值，首先找到这个结点，然后修改该结点的数据域即可。,4.删除 删除第i个数据元素，涉及第i-1，i，i+1三个结点。将结点i-1的指针域nextPtr存放结点i指针域nextPtr的内容，将结点i+1的指针域prePtr存放结点i指针域prePtr的内容。然后释放结点i所占的存储空间。删除操作如图2.8所示。,i-1 i i+1,5.插入 若在第i个数据元素前插入一个新的数据元素，首先为该元素申请存储空间，得到一个新结点，如图2.9（a）所示。这个新结点的数据域存放该元素的值。再找到第i-1个和第i个结点；新结点的指针域nextPtr存放第i-1个结点的指针域nextPtr的内容，指针域prePtr存放第i个结点指针域prePtr的内容；结点i-1的nextPtr指针域和结点i的prePtr指针域存放新结点的地址。如图2.9所示。,i,i-1,单向链表只给出结点的直接后继，无法求得某结点的前趋。单向链表最后一个结点的指针域是空的，如果将其存放第一个结点的地址就形成了循环链表，如图2.10（a）所示。在循环链表中，从任一结点出发可以达到表中所有的结点，从而克服了单向链表不能访问其前趋结点的缺点。,2.2.8 循环链表,如果将双向链表的最后一个结点的指针域存放第一个结点的地址，同时将第一个结点的指针域存放最后一个结点的地址就形成了双向循环链表，如图2.10（b）所示。,循环链表构成一个环，因此从表中任一结点出发均可找到其它结点。,线性表的链式存储与顺序存储比较，有以下几个特点：（1）删除或插入运算速度快，运算过程中数据并不移动。（2）不需事先分配存储空间，以免有些空间不能充分利用。（3）表的容量易于扩充。（4）按逻辑顺序进行查找的速度慢。（5）比相等长度的顺序存储多占用作为指针域的存储空间。2.链式存储刚好弥补了顺序存储的不足，它多用于事先难以确定容量或增删运算频繁的线性表的存储结构。如下图所示,小结,0 x1y1,xiyi,xnyn0,Head,Rear,的折线，它是由有序的顶点确定的复杂实体。从逻辑结构上看它是典型的线性表。由于它的顶点数量事先不能确定，并且在编辑过程中可能要修改、删除任意的顶点或在任意的顶点之后插入新的顶点，因此用链式存储结构是非常合适的。,树结构也是一类非常重要的数据结构，它是非线性的，数据元素之间存在明显的层次和嵌套关系。很多事物都可以用树来描述，如家族祖谱、行政组织机构等。树可分为一般树和分支固定的树，除了二叉树之外，四叉树和八叉树也都有非常重要的应用。,2.3 树与二叉树,树是由一个或一个以上节点组成的有限集T，其中一个节点称为根，其余节点可分为若干个互不相交的有限集T1，T2，T3，Tn，每一个集合本身又是一棵树，称为根的子树。可见，树结构是一个递定义。图2.11为树的逻辑结构。,2.3.1 树的逻辑结构,基本术语：节点的度：节点的孩子（子树）的数量称为度。树的度：树中所有节点中最大的度数称为这个树的度数。 上图中的树的度数为4。根节点：没有直接前驱的节点，A称为根节点。分支节点：度不为0的节点，或者有直接后继的节点。如节点B、F、D、J。每个分支节点可以有不只一个直接后继。,叶节点：没有直接后继的节点，或者说度为0的节点。如节点E、K、G、H、C、I、L都是树叶，也称终端节点。双亲：节点的直接前驱称为该节点的双亲。如A是B的双亲。孩子：节点的直接后继称为该节点的孩子。如B是A的孩子。兄弟：同一双亲的孩子间称为兄弟。如E、F、G、H。堂兄弟：双亲在同一层的节点互为堂兄弟。如G与I、J互为堂兄弟。,深度：树的最大层次数量称为树的深度或高度。上图中树的深度为4。11) 祖先：从根到该节点所经的所有节点都是该节点的祖先。如节点L的祖先A、D、J节点。12) 子孙：以该节点为根的子树中的任一节点都是该节点的子孙。如I、J、L是D的子孙，节点A的子孙则是树中其余的11个节点。13）边：节点间的连线。,由于树的逻辑结构为非线性的，所以只能用链式作为它的存储结构。1.定长方式：以最大度数节点的结构作为该树的所有节点的结构。,2.3.2 树的存储结构,数据域 子树1地址 子树2地址 子树n地址,2.不定长方式：每个节点增加一个存放度数的域，节点长度随着度数不同而不同。,在计算机中数据的表示总是有序的，树结构在计算机内的表示也隐含着一种确定的相对次序，因此，树结构中的各子树之间的相对位置也是确定的，如果交换同一层次各子树的位置就构成了不同的树。如图2.14所示为两棵不同的树。,2.3.3 树的应用举例,树是典型的具有层次关系的数据结构，它的应用非常普遍，如下图所示是某多轴钻的传动箱示意图。其中A为电机轴，B、C为传动轴，D、E、F、G、H为钻孔主轴。,多轴钻传动箱示意图,用树可以表示各轴的传动关系，若轴带动轴，则从结点向结点画一带有箭头的连接线，如下图所示。,传动关系的逻辑结构图,结点可采用定长方式，这棵树的度数为3，可设3个子树域，如果传动关系变化，例如B轴再增加从动轴，子树域就不够，这时子树域的数量应大于3。数据域（值域）可存放多数数据，它们可以是轴的位置、功率、转速、材料、轴上齿轮的数据等。子树域（指针域）存放该轴带动的各轴的地址，如下表所示。,值域和指针域存放的数据,1.定义 二叉树是树结构的一种，但不同于一般树结构，即每个结点至多有两棵子树，并有左右之分，不能颠倒，二叉树可以是空的，一般树则至少有一个结点。二叉树的深度和度的定义与树一致。二叉树的五种基本形态如图2.15所示。,2.3.3 二叉树的逻辑结构,2.特殊二叉树深度为k的有2k-1个结点的二叉树称为满二叉树。深度为k，结点为n的二叉树，它从1到n的标号如果与深度 为k的满二叉树的标号一致，就称为顺序二叉树。(3) 结点的度数或者为零，或者为2的二叉树称为完全二叉树。,满二叉树,顺序二叉树,完全二叉树,满二叉树和顺序二叉树均可采用顺序存储。如果i=1，此结点是根结点。如果i=k，k/2是结点i的双亲结点，2k是i的左孩子，2k+1是i的右孩子。特点：节省空间，可以利用公式随机地访问每个结点和它的双亲及左右孩子，但不便删除或插入运算，,2.3.4 二叉树的存储结构,对于一般二叉树，通常采用多重链表结构，每个结点设三个域：数据域存放结点的值，左子树域存放左子树的地址，右子树域存放右子树的地址，如图2.18所示。这种存储结构会浪费一些存储空间，但便于删除或插入运算。,左子树域 数据域 右子树域,结点,遍历二叉树是指按一定规律走遍二叉树的每个结点，每个结点访问一次且只访问一次。即按一定规则将二叉树的所有结点排列成一个线性序列。由于二叉树是由根结点、左子树、右子树三个基本单元组成的，因此，依次遍历这三部分信息，就可以遍历整个二叉树了。,2.3.5 二叉树的遍历,根据根结点、左子树、右子树三者不同的先后次序，有6种遍历二叉树的方案。即 根结点、左子树、右子树 左子树、根结点、右子树 左子树、右子树、根结点 根结点、右子树、左子树 右子树、根结点、左子树 右子树、左子树、根结点前三种是按着先左后右的次序，属于常用的遍历方式。,1、先根遍历 先根遍历的次序是：先访问根结点，再访问左子树，最后访问右子树。遍历图2.19所示二叉树的过程如图2.20所示。遍历结果如下：A，B，D，H，E，C，F，G，I。,2、中根遍历 中根遍历的次序是：先访问左子树，再访问根结点，最后访问右子树。其遍历示意图如图2.21所示。遍历结果如下：D，H，B，E，A，F，C，I，G。,3、后根遍历 后根遍历的次序是：先访问左子树，再访问右子树，最后访问根结点。其遍历示意图如图2.22所示。遍历结果如下：H，D，E，B，F，I，G，C，A。,用二叉树表示一般树可以节省存储空间，一般树转换为二叉树的规则是：1）树的根节点为二叉树的根节点。2）保留根节点的孩子（从左到右），第一个孩子作为二 叉树的左子树。3）根节点的其余孩子作为该左子树的右子树（与左子树 原属于兄弟关系，现变为父子关系）,2.3.6 树的二叉树表示,将图2.11所示的一般树转换为二叉树的过程如图2.23所示。1）保留每个节点与最左孩子的边，去掉其余各边。2）连接同一双亲的所有兄弟。3）以树根节点为轴心，将整颗树顺时针旋转45度即可得 到转换后的二叉树。,1.利用二叉树排序 排序就是对一组无序的数据递增或递减的规律重新排列。用二叉树排序的过程分为两步： 构造这棵二叉树。 对这棵二叉树进行中根遍历。,2.3.7 二叉树应用举例,（1）构造二叉排序树 每一个数据将对应二叉树的一个结点。该结点在二叉树上的位置是这样确定的：第一个数据元素a1作为这棵二叉树的根结点；若a2 a1，a2作为a1的左子树，否则作为 a1的右子树；第i个数据元素ai首先同这棵二叉树的根结点比较，若ai a1，则ai应位于a1的左边，再同a1的左子树结点比较，否则同a1的右子树结点比较，以此类推，直到找到该数据元素的位置为止。,例如对一组数据(a1, a2, a3, , ai-1, ai, ai+1, , an)按非递减的规律排序。步骤如下：,（2）中根遍历二叉排序树 按照上面的方法建立二叉树以后，用中根遍历方式遍历该二叉树。,建立数组（9, 36, 45, 13，26，7，12，48）的二叉排序树，并写出中根遍历结果。,（2）图2.24所示的二叉树中根遍历结果是：7, 9, 12, 13, 26, 36, 45, 48。,（1）建立的二叉树如图2.24所示。,建立数组（9, 36, 45, 13，26，7，12，48）的二叉排序树，并写出中根遍历结果。,建立数组（12，36，48，8，11，23，5，62）的二叉排序树，并写出中根遍历结果。,建立数组（12，36，48，8，11，23，5，62）的二叉排序树，并写出中根遍历结果。,（2）中根遍历结果：5，8，11，12，23，36，48，62,（1）建立的二叉树如图所示。,建立数组（10，34，46，6，9，21，3，60）的二叉排序树，绘图并写出中根遍历结果。,建立数组（10，34，46，6，9，21，3，60）的二叉排序树，绘图并写出中根遍历结果。,（1）建立的二叉树如图所示。,（2）中根遍历结果：3，6，9，10，21，34，46，60,2.三维立体造型的CSG（Constructive Solid Geometry）树 一个复杂的形体可以看作由一些比较简单的形体经过交、并、差运算形成。二叉树可以描述复杂形体这一形成过程，因此，这样的树也可称为CSG树。,思考题,1、什么是数据结构？ 掌握数据、数据元素、数据的逻辑结构、数据的物理结构等基本概念。2、CAD常用的数据结构有哪些？3、线性表的概念？线性表的特点？线性表的存储结构？4、说明栈、队列两种数据结构的特点和区别？5、简述单向链表中对某个节点的访问、修改、删除、插入等操作步骤，并 绘出操作示意图。6、简述双向链表中对某个节点的访问、修改、删除、插入等操作步骤，并 绘出操作示意图。7、掌握树的存储结构。8、掌握二叉树的遍历应用。 利用排序二叉树将无序数列排列成升序。要求画出排序树和遍历过程， 写出有序数列。,