CAD常用数据结构

第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的表称为空表。姓名学号性别年龄班级健康状况王晓林02001男18机械02健康程红02002女20机械02一般刘建平02006男21机械02神经衰弱2.2.1线性表的逻辑结构1)线性表是数据元素的一个有限序列。2)线性表中数据元素的个数定义为线性表的长度n，当n=0时，为空表。3)数据元素在线性表的位置取决于它们自己的序号，数据元素之间的相对位置是线性的，如a1是第一个元素，an是最后一个元素。4)除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。所有数据元素ai在同一个线性表中必须是相同的数据类型。a1a2a3a4an……线性表的特点：2.2.2线性表的存储结构1.线性表的顺序存储结构顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放。数据元素在存储器中的存放地址和该元素的下标一一对应。假定一个线性表A(n)，它的每个数据元素占l个存储单元，第一个数据元素在内存中的开始地址为L(a1)，那么，第i个数据元素的存储位置为L(ai)=L(a1)+(i-1)l元素下标123…i…n内存状态…a1a2a3…ai…an…存储地址bb+1lb+2lb+3lb+(i-1)lb+(n-1)l图2.1线性表的存储结构(1)有序性：各数据元素之间的存储顺序与逻辑顺序一致。(2)均匀性：每个数据元素所占存储空间的长度是相等的。根据以上特点不难看出程序设计语言中的数组是典型的顺序存储的线性表。因此用程序建立顺序存储的线性表及对该表的运算，可通过对数组的说明和运算来实现。线性表顺序存储结构的特点举例2.线性表的链式存储结构链式存储就是用一组任意的存储单元存放表中的数据元素。结点：数据域、指针域数据域：用于存放数据元素值；指针域：用于存放直接前驱或直接后继结点的地址（指针）。a)结点b)链表图2.2链表结构数据域指针域DataLinkData2Link2DatanData1Link1…Head2.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,LastInFirstOut)。进栈出栈栈顶an…a3a2栈底a1图2.3栈结构2.栈的存储结构理论上讲，顺序存储或链式存储都可以作为栈的存储结构。由于栈的容量一般是可以预见的，而且运算仅限于栈顶，所以通常采用顺序存储作为栈的存储结构。3.栈的运算建栈栈的存储结构用数组s[n]。设一栈顶指针为TOP，它不必指向数据元素的实际地址，只记录数据元素的逻辑序号即可。当元素尚未进栈时，令TOP等于-1。进栈如果有元素进栈，首先检查栈顶指针TOP，如果TOP等于m，表示栈满。如果TOPm，令TOP=TOP+1，将该元素赋给s[TOP]。出栈出栈即取走栈顶元素。首先检查栈顶指针TOP，如果TOP=-1，表示栈空。如果TOP-1，出栈元素为s[TOP]，然后令TOP=TOP-1。图2.4出入栈操作TOP=-1AEDCBACBATOP=0TOP=4TOP=24.栈的应用举例栈是一种应用很广的数据结构。例如在交互式图形系统中，将显示区域存入栈中，需要时可以恢复前几次的显示状态。用栈存放每次操作的命令，可以恢复到前几个命令时的状态。在计算机语言编译系统中，栈是一个非常重要的数据结构。队列是两端开口的线性表，队列只限定在表的一端进行插入操作，在表的另一端进行删除操作。允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”。如图2.5所示，a1是队头元素，an是队尾元素，队列中元素以a1,a2,a3,,…,an的次序入队，也以同样的次序出队，其工作方式是先进先出(FIFO,FirstInFirstOut)，与栈的工作方式刚好相反。出队a1a2a3…an入队队头元素队尾元素图2.5队列结构2.2.5队列在对队列进行运算时，由于队列的两端均可浮动，因此，需要设立两个指针，分别指向队头(Front)和队尾(Rear)。这里规定指针Front总是指向实际队头的前一位置，而指针Rear指向队尾元素。显然，当Rear=0或Front=Rear时，队列为空；当Rear等于上界时，队列满。队列的主要运算是入队和出队。入队时，队尾指针加1；出队时，队头指针加1。出队a1a2a3…an入队队头元素队尾元素图2.5队列结构举例计算机程序设计中经常用到队列结构。最典型的例子是操作系统中的作业排队，当系统中有多道程序运行时，可能同时有几个作业的运行结果需要通过通道输出，这就要按申请的先后次序排队。申请输出的作业从队尾进行队列，当通道传输完一个作业，要接受一个新作业时，队头的作业先从队列中退出输出操作。2.2.6单向链表单向链表结点的指针域只有一个，通常存放直接后继的地址。第一个元素的地址需要专门存放在指定的指针型变量中，或者设置一个与链表结点相同的一个结点,它的数据域可以是空的,也可以存放表长等附加信息,指针域存放第一个元素的地址。单向链表的最后一个节点的指针域是空的。如下图所示：数据域指针域DatanextPtr节点1.建立单向链表假定线性表为(A，B，C，D，E)，将其按单向链表存储。首先定义结点的数据类型，它有两个成员；data和nextPtr。data是用来存放数据元素本身，所以，本例它应该是字符的。一个或多个普通类型的变量组成了该结点的数据域。nextPtr存放该结点的直接后继的地址，所以它应该是指针型的，而且是指向该结点（structslink）类型数据的指针。BDAHeadCE数据域指针域DatanextPtr节点2.访问链表中数据元素的存储顺序与逻辑顺序无关。如果访问第i个元素，首先通过链头结点h找到第一个结点的指针域找到第二个结点；……直至找到第i个结点，即可访问该结点的数据域。3.修改修改第i个元素的值，将第i个数据元素的值改为M。首先找到该结点，然后修改这个结点的数据域。BDAHeadCE4.删除若删除第i个元素M，则要找到第i-1和第i个结点，并将第i-1个结点的指针域中第i个结点的地址改为第i+1个结点的地址，最后释放第i个结点所占的存储空间。删除操作如图2.6所示。ABMCDE0ABMCDE0图2.6删除一个结点HeadHeadi-1i5.插入在第i个数据元素之前插入一个数值为‘M’的元素，首先要为该元素申请一个新结点作为存储空间，在新结点的数据域存放数值‘M’，再找到第i-1个结点，令新结点指针域的指针等于第i-1个结点指针域的指针，修改第i-1个结点的指针，让其存放这个新结点的地址。即让第i-1个结点指向新结点，而新结点指向第i个结点即可。插入操作如图2.7所示。ABMCDE0ABMCDE0图2.7插入一个结点HeadHeadii-1单向链表只给出结点的直接后继地址，因此从某个节点出发只能向后寻找其他结点。如果在每个结点的指针域增加一个指针域，用来存放结点的直接前趋地址，就可以方便地从每个结点向前寻找其他结点。这样的链表称为双向链表。如下图所示：2.2.7双向链表HeadRearA0CB0ED1.建立双向链表假定线性表为(A，B，C，D，E)，将其按双向链表存储。首先要定义结点的数据类型，它有3个成员，data、nextPtr和prePtr。data用来存放数据元素的数值，nextPtr用来存放结点直接后继的地址，prePtr存放结点直接前趋的地址。head和rear分别为链头和链尾结点。HeadRearA0CB0EDnextPtrDataprePtr2.访问双向链表可以像单向链表那样从链头结点head开始找到第i个结点，还可以从链尾结点开始找到后起的第j个结点。3.修改若修改第i个结点的值，首先找到这个结点，然后修改该结点的数据域即可。HeadRearA0CB0ED4.删除删除第i个数据元素，涉及第i-1，i，i+1三个结点。将结点i-1的指针域nextPtr存放结点i指针域nextPtr的内容，将结点i+1的指针域prePtr存放结点i指针域prePtr的内容。然后释放结点i所占的存储空间。删除操作如图2.8所示。图2.8双向链表的删除操作HeadRearA0CB0ED（a）删除前HeadRearA0CB0E（b）删除后Di-1ii+15.插入若在第i个数据元素前插入一个新的数据元素，首先为该元素申请存储空间，得到一个新结点，如图2.9（a）所示。这个新结点的数据域存放该元素的值。再找到第i-1个和第i个结点；新结点的指针域nextPtr存放第i-1个结点的指针域nextPtr的内容，指针域prePtr存放第i个结点指针域prePtr的内容；结点i-1的nextPtr指针域和结点i的prePtr指针域存放新结点的地址。如图2.9所示。图2.9双向链表的插入操作HeadRearA0CB0ED（c）插入后HeadRearA0CB0E（b）将B、D结点地址分别赋给C结点DC（a）申请一个新结点ii-1单向链表只给出结点的直接后继，无法求得某结点的前趋。单向链表最后一个结点的指针域是空的，如果将其存放第一个结点的地址就形成了循环链表，如图2.10（a）所示。在循环链表中，从任一结点出发可以达到表中所有的结点，从而克服了单向链表不能访问其前趋结点的缺点。ABCDN（a）单向循环链表Head…2.2.8循环链表如果将双向链表的最后一个结点的指针域存放第一个结点的地址，同时将第一个结点的指针域存放最后一个结点的地址就形成了双向循环链表，如图2.10（b）所示。图2.10循环链表HeadRearACBN（b）双向循环链表……循环链表构