第2章CAD中常用的数据结构1.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,济南大学机械工程学院,第,2,章,CAD,中常用的数据结构,用计算机语言编写数值计算程序时，首先需要对变量进行数据类型说明，才能把数据提供给变量，由计算机对其进行存取和计算等操作。如,C,语言中的整型、浮点型等，数据类型实际上是语言系统提供的数据结构。,计算机不仅要处理数值计算问题，还要大量地处理包括图形、图像,、,文字、表格、声音等各种各样复杂的问题，这时提供给计算机的已不只是简单的、孤立的数据，而是存在某些关系的数据。,1,3,3,5,5,2,2,4,4,1,1,2,2,3,3,4,4,5,5,1,X1,Y1,X2,Y2,X3,Y3,X4,Y4,X5,Y5,(a),五个顶点,(b),五边形,(c),五角形,(a),五边形与屋角形,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,基本概念,数据 数据是描述客观事物的数字、字符及所有能输入到计算机中并可被计算机接受和处理的各种符号的集合。,数据元素 数据元素是数据的基本单位，是数据这个集合中的一个个体。,数据的逻辑结构和物理结构,数据的逻辑结构仅考虑数据之间的逻辑关系，数据结构一般指数据的逻辑结构。它独立于数据的存储介质。,数据的物理结构也称存储结构，是数据的逻辑结构在计算机中的映象。,计算机处理数据的最小单位叫做位,(Bit),，,一个位表示一个二进制的数，若干位组合起来形成一个位串。,用一个位串表示一个数据元素，称这个位串为一个节点。节点是数据元素在计算机中的映象。,映象的方法不同，数据元素在计算机中的存储结构也不同。顺序映象得到顺序的存储结构，非顺序映象得到非顺序的存储结构。,4,数据类型,数据类型是程序设计语言确定变量所具有的种类。每种程序设计语言都提供一组基本的数据类型。如整型、实型、双精度型、复型、逻辑型、字符型数据类型等；,程序设计语言还可以将不同类型的数据组合成一个有机的整体，构造出新的数据类型用来实现各种复杂的数据结构的运算。,2,2,1,线性表的逻辑结构,线性表是一种最常用、最简单的数据结构，是,n(n,o),个数据元素的有限序列。可表达成下述逻辑结构：,(a,1,a,2,a,3,a,i-1,a,i,a,i+1,a,n-1,a,n,),其中,a,i,可以是一个数、是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。,当,n,o,时，线性表中的每一个元素，除第一个及最后一个外，每个元素有且只有一个直接前趋，有且只有一个直接后继。,线性表中数据元素的数量定义为线性表的长度。,2,2,线性表,2,2,2,线性表的顺序存储结构,线性表在计算机存储器中的存储形式，可以按照数据元素的逻辑顺序依次存放，即用一组连续的存储单元依次存放各个数据元素，这种存储形式称为顺序存储结构。,假定每个数据元素占用,l,个存储单元，第一个数据元素占用的第一个存储单元的地址为,Loc(a,1,),，,则第,t,个数据元素的存储位置为,:,Loc(a,t,)=Loc(a,1,)+(t-1)*l,线性表顺序存储结构的持点,(1),均匀性,每个数据元素所占存储空间的长度相同。,(2),有序性,各数据元素之间的存储顺序与逻辑顺序一致。,顺序存储情况下线性表的删除和插入,1,从线性表中删除一个数据元素,2,将一个新的数据元素插入到线性表,A,B,C,D,E,A,B,D,E,删除前,删除后,A,B,C,D,E,A,B,I,C,D,E,插入前,插入后,2,2,3,线性表的链式存储结构,1,链式存储结构的待点,用一组任意的存储单元存放线性表的数据元素。由于这些存储单元可以是不连续的，为了表示这些元素的线性逻辑关系，除了存储元素本身的数据信息外，还要存储这个元素直接后继或直接前趋的存储位置。,这两种信息的存储映象，称为结点。结点包含两种域，存放数据元素本身的域称为数据域，存放直接后继或直接前趋的域称为指针域。,数据域,(data),指针域,(next),2.,单向链表,（,1,）建立单向链表,（,2,）删除单向链表的一个元素,A,B,C,D,E,head,A,B,C,D,E,head,A,B,C,D,E,head,删除前,删除后,/,用,C,语言建立单向链表的程序清单,#include,#include,#define MAX 5,struct link ,char data;/,定义结点结构,struct link*next;,*head;,main(),int i;,struct link*node,*temp;,for(i=0;idata=A+i;,node-next=NULL;,if(i=0)head=temp=node;,else,temp-next=node;,temp=node;,/,用,C,语言建立删除单向链表中一个元素的程序清单,void delete_link(struct link*node),int i,j;,struct link*temp;,printf(,删除第几个元素,);,scanf(%d,if(iMAX)printf(,超出链表范围,);return(-1);,j=1;,node=head;,if(inext;,free(node);,return;,while(node),if(j+=i-1),temp=node-next;,node-next=temp-next;,free(temp);,return;,node=node-next;,（,3,）向单向链表插入一个数据元素,A,B,C,D,E,head,插入前,M,A,B,C,D,E,head,插入后,M,3.,双向链表,双向链表的特点：,不但能方便地找到其直接后继，也能方便地找到其直接前趋,指针域,(next),数据域,(data),指针域,(last),双向链表的建立、删除和插入运算,(1),双向链表的建立,(2),双向链表的删除,E,D,C,B,A,rear,head,E,D,C,B,A,rear,head,/,用,C,语言建立双单向链表的程序清单,#include,#include,#define MAX 5,struct link ,struct link*last;,char data;/,定义结点结构,struct link*next;,*head,*rear;,main(),int i;,struct link*node,*temp;,for(i=0;ilast=NULL;,node-data=A+i;,node-next=NULL;,if(i=0)head=temp=node;,else,temp-next=node;,node-last=temp;,temp=node;,rear=temp;,（,3,）双向链表的插入,rear,E,D,C,B,A,head,M,rear,E,D,C,B,A,head,M,4.,循环链表,A,B,C,D,E,E,D,C,B,A,head,head,单向循环链表,双向循环链表,链表与线性表相比较，有以下特点：,(1),删除或插入运算，数据元素不需要移动；,(2),不需要事先分配存储空间，因此不存在空间浪费；,(3),表的容量根据需要实行动态申请和动态释放，存储空间利用效率高；,(4),按逻辑位置进行查找的速度慢。,因此，链表比较适合用于事先难以确定表的容量大小，并且增删操作频繁的场合。,2.3,栈和队列,1,、栈,栈是一种特殊形式的表。表的一端是封闭的，另一端是开口的。,对表只能在开口的一端进行删除（出栈）和插入（进栈）运算，这一端称为栈顶，另一端称为栈底。设,TOP,为栈顶指针，则：,出栈操作,(1,）,y=S(TOP),(2)TOP=TOP-1,进栈操作,(1,）,TOP=TOP+1,(2)S(TOP)=s,当栈满时再有元素进栈，栈将溢出，称为“上溢,”；,当栈空时作出栈运算，栈也将溢出，称为“下溢”。,a,n,a,3,a,2,a,1,进栈,出栈,栈底,栈顶,2,队,(,或称队列,),队列是一个两端均开口的线性表，元素只能从表的一端插入，在表的另一端删除。,表中允许插入的一端称为“队尾”，允许删除的一端称为“队头”,。,入队,出对,对头指针,队尾指针,树是一类重要的非线性数据结构，元素之间存在明显的层次关系。,几何形体的分解,2,4,树和二叉树,树的定义：,树是由一个或多个结点组成的有限集,T,，,其中有一个特定的称为根的结点,s,其余结点可分为,n(n,o),个互不相交的有限集,T,1,T,2,T,3,T,n,其中，每一个集合本身又是一棵树，并且称为该树的子树。,树形结构描述了数据之间的分支关系，即层次关系，其结构形式上很像一棵倒过来的树，树形结构由此得名。,2,4,1,树,树的逻辑结构,2,4,2,二叉树,1,二叉树的定义 ,二叉树的每个结点至多有两棵子树，子树有左右之分，不能颠倒。二叉树可以是空的。,二叉树与一般树的区别在于：,(1),一般树至少要有一个结点，但二叉树可以是空的。,(2),一般树的每一个结点可以有任意多个子树，但在二叉树中，每个结点的子树数不能超过,2,。”,(3),一般树中结点的子树不必区分它们之间的次序，而二叉树中的子树有左右之分，其次序不能颠倒。,二叉树的五种基本形态：,(a),空二叉树；,(b),只有一个根结点的二叉树；,(c),只有左子树的二叉树；,(d),只有右于树的二叉树，,(e),左右子树均存在的完全二叉树。,二叉树的存储结构,二叉树,存储结构形式,结点的构造,遍历二叉树,六种遍历二叉树的方案，令,D,表示根结点，,L,表示左子树、,R,表示有子树。,(1),左子树、根结点、右子树,(LDR),；,(2),左子树、右于树、根结点,(LRD),；,(3),根结点、左子树、右子树,(DLR),；,(4),根结点、有子树、左子树,(DRL);,(5),右子树、根结点、左子树,(RDL),；,(6),右子树、左子树、根结点,(RLD),。,如果按先左后右的次序，则只有前三种遍历方式：,LDR-,中序遍历,LRD-,后序遍历,DLR-,先序遍历,二叉树,中序遍历示意图,三种遍历方法遍历该树的结果：,(1),中序遍历,(LDR),结果：,C,，,B,，,E,，,D,，,A,，,G,，,H,，,I,，,F,，,J,(2),后序遍历,(LRD),结果：,C,，,E,，,D,，,B,，,I,，,H,，,G,，,J,，,F,，,A,(3),先序遍历,(DLR),结果：,A,，,B,，,C,，,D,，,E,，,F,，,G,，,H,，,I,，,J,中序遍历的算法,中序遍历示意图,中序遍历的算法框图,TOP,栈顶指针,P,指向结点的指针,N,Y,3.,二叉排序树,排序就是对一组无序的数据按递增或递减的规律重新排列。,二叉排序树是树形结构的一种简单应用，它可以把原来是无序的线性表变成有序的线性表。,对数组,18,14,22,7,17,20,35,27,11,3,20,的排序结果,假设：如果一棵二叉排序树不空，那么,根结点上所有左子树上的结点都,小于根结点，所有右子树上的结,点都不小于根结点。这个定义也,是一个递归的定义。,建立二叉排序树的算法：,设有一个序列,T,t,1,t,2,t,3,t,n,(1),令,t,1,为二叉树的根结点,(2),以,t,i,与二叉树的根结点作比较：若,t,i,小,于根结点，则将,t,i,插入到左子树中；,否则插入到有子树中；,(3),对,t,i,(i,2,，,3,，,，,n),所有的递归重,复步骤,(2),即可。,中序遍历二叉树,变量定义,#include stdafx.h,#include stdio.h,#include malloc.h,typedef struct _tagLink,struct _tagLink*LC,*RC;,int data;,LINK;,LINK*Head;,int A=18,14,22,7,17,20,35,27,11,3,20;,int N=sizeof(A)/sizeof(int);,中序遍,历二叉树,-,建立二叉树,void built(),for(int i=0;idata=Ai;,Node-LC=Node-RC=NULL;,if(i=0)Head=Node;continue;,Temp=Head;,for(;),if(Aidata),if(Temp-LC=NULL)Temp-LC=Node;break;,else Temp=Temp-LC;,else,if(Temp-RC=NULL)Temp-RC=Node;break;,else Temp=Temp-RC;,中序,遍历二叉树,输出,void output(),LINK*stack50;,int TOP=0;,LINK*P=Head;,for(;),if(P!=NULL),stackTOP+=P;,P=P-LC;,else,if(TOP=0)break;,P=stack-TOP;,printf(%dn,P-data);,P=P-RC;,中序,遍历二叉树,主程序,int main(int argc,char*argv),built();,output();,return 0;,