机械CAD中常用的数据结构.ppt

第1篇 CAD基础,4 机械CAD中常用的数据结构,本章目标 掌握机械CAD中常用的数据结构,本章学习要点 线性表的存储结构以及对线性表的建立、访问、修改、删除和插入的运算 栈的存储结构以及对栈的建立、进栈和出栈的运算 树的存储结构 二叉树的存储结构以及对二叉树的遍历运算,4 机械CAD中常用的数据结构,数据 是对客观事物的符号表示，是指所有能输入计算机内并被计算机处理的符号的总称。,4.1 基本概念,数值、字符是数据，图形、图像也是数据。,数据元素 是数据的基本单位，是数据这个集合中相对独立的个体。,零件可以作为产品或部件的数据元素，圆柱体、长方体可以作为零件形体的数据元素，直线、圆弧可以作为图形的数据元素。,4.1 基本概念,数据的逻辑结构 是只考虑数据之间的逻辑关系，独立于数据的存储介质。 通常所说的数据结构就是指数据的逻辑结构。,4.1 基本概念,数据的逻辑结构 是只考虑数据之间的逻辑关系，独立于数据的存储介质。 通常所说的数据结构就是指数据的逻辑结构。,4.1 基本概念,数据的物理结构 也称为数据的存储结构，是数据元素和它们之间的关系在计算机中的表示。,4.1 基本概念,结点,用一个位串表示一个数据元素，称这样 的位串为一个,结 点,结点是数据元素在计算机中的映像,4.1 基本概念,机械CAD中常用的数据结构,线性表,栈,树,二叉树,线性表是一种最常用且最简单的数据结构，是n个数据元素的有限序列（a1、a2、an）。,数据元素ai可以是一个数、一个符号，也可以是一个线性表，甚至是更复杂的数据结构。,4.2 线性表,例如：六角头螺栓(GB/T 5780-2000)的螺纹规格 d 可以构成一个简单的线性表 （3，4，5，6，8，10，12，16，20，24，30，36，42）,4.2 线性表,例如：减速箱明细表，表中的数据元素是由序号、名称、数量和材料4个简单数据组成的一个记录。,减速箱明细表,4.2 线性表,从上面两个实例中可以看出，尽管线性表中的数据元素可能是各种各样的，但同一表中数据元素的类型必须是相同的。,4.2 线性表,除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。,4.2 线性表,4.2.1 线性表的顺序存储结构,用一组连续的存储单元按线性表数据元素的逻辑结构依次存放表中所有数据元素。,4.2 线性表,特点：,（1） 有序性：各数据元素之间的存储顺序与逻辑顺序一致,（2） 均匀性：每个数据元素所占存储空间的长度相等,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,建表,访问,修改,删除,插入,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,static char listc =A, B, C, D, E;,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,6,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,char c; c=listc2;,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,Listc2=T;,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,4.2.1 线性表的顺序存储结构,4.2 线性表,从线性表中删除一个数据元素后还必须保持这个线性表的均匀性和有序性，因此被删除元素之后的所有元素均应向前移动，移动距离为一个数据元素所占存储空间的长度。,操作：,#define LEN 6 main() static char listcLEN= (A, B, C, D, E; int i,j; printf(“删除第几个数据元素？“）; scanf(“%d”,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,4.2.1 线性表的顺序存储结构,4.2 线性表,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,将一个新的数据元素插入到线性表的第i个位置，即插入第i-1元素和第i个元素之间。为了保证线性表的均匀性，新的数据必须和表内已有元素的类型一致；为了保证线性表的有序性，原线性表第i至最后一个元素要向后移动一个数据元素所占存储空间的长度,4.2.1 线性表的顺序存储结构,4.2 线性表,操作：,#define LEN 6 main() static char listcLEN= (A, B, C, D, E; int i,j; char cl; printf(“输入新的数据元素“）; c1=getche(); printf(“输入新的数据元素的位置“）; scanf(“%d”,线性表listc有 5个数据（A, B,C,D,E）, 用C语言编 写程序实现 此类操作,建表,访问,修改,删除,插入,优缺点: 1）线性表在顺序结构中对数据元素的访问（读取）、修改快而方便，但在删除和插入运算时，需要对数据元素作大量的移动。 2）由于线性表是一个静态表，只有运行前进行定义，定义完成后，大小不能改变。,4.2.1 线性表的顺序存储结构,4.2 线性表,应用: 多用于查找频繁、很少增删的场合，例如工程手册中的数据表。,4.2.1 线性表的顺序存储结构,4.2 线性表,链式存储结构的特点,4.2.2 线性表的链式存储结构,4.2 线性表, 单向链表:,单向链表结点的指针域只有一个,通常存放直接后继的地址。,4.2.2 线性表的链式存储结构,4.2 线性表, 单向链表:,假定线性表(A,B,C,D,E)，将其按单向链表存储,数据操作：访问、修改、删除、插入,4.2.2 线性表的链式存储结构,4.2 线性表,删 除,建 立,访 问,查 找,修 改,首先定义结点的数据类型，它有两个成员：data和next。 data用来存放数据元素本身，本例是字符型的； next存放该结点直接后继的地址，所以它必须是指针型的，而且是指向字符型变量的指针。 链表不必指出它的长度，而是根据需要动态的申请存储空间。,删 除,建 立,访 问,查 找,修 改,/*定义结点的数据结构*/ struct link char data; /*数据域*/ structure link *next; /*指向直接后继的指针*/ *head; /*链头结点指针，是全局变量*/,删 除,建 立,访 问,查 找,修 改,/*建立一个单向链表*/ void create(void) int i, LEN=5; /*链表初始长度为5*/ 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; ,删 除,访 问,查 找,修 改,链表的逻辑顺序与存储顺序无关，如果访问第i个元素，首先通过链头结点head找到第1个结点的地址，再根据这个结点的指针域找到下一个结点的地址，直至找到第i个结点的地址，再访问这个结点的数据域。,删 除,访 问,查 找,修 改,删 除,访 问,查 找,修 改,/*访问第 i 个数据元素*/ char visit ( int i ) int j=1; struct link *temp; temp=head; while(temp) if(j+=i) return(temp-data); temp=temp-next; printf(“序号超出链表的范围！”); return(0); ,删 除,修 改,查 找,在链表中查找是否有指定的数据元素，若有就输出第一次出现这个数据元素的逻辑位置，否则输出没有这个数据元素的信息。,删 除,修 改,查 找,/*查找特定数据元素的结点*/ int search (char c) int i=1; struct link *temp; temp=head; while(temp) if(temp-data=c) return(i); i+; temp=temp-next; printf(“没有找到这个数据！”); return(0); ,修 改,查 找,修改第i个数据元素的值时,首先找到这个数据元素的结点。若修改指定数据元素的值，同样先找到这个数据元素的结点，再修改这个结点的数据域即可。,删 除,查 找,若要删除第i个数据元素，需找到第 i-1和第 i 个数据元素的结点，然后将第i-1个结点的指针指向第i+1个结点，再释放第i个结点的存储空间即可。,删 除,查 找,/*删除第 i 个结点*/ void delete(int i) int j=1; struct link *node,*temp; node=temp=head; if(i=1) head=temp-next; free(temp); return; ,删 除,查 找,while(node) if(+j=i) temp=node-next; if(temp=NULL) pritnf(“序号超出链表的范围”); return; node-next=temp-next; free(temp); return; node=node-next; printf(“序号超出链表的范围”); ,查 找,访 问,查 找,删除,在第 i 个数据元素之后插入一个新的数据元素时,首先为该数据元素申请存储空间,得到一个新结点。在新节点的数据域存放数据元素的值，然后找到第i个结点。令结点指针域的指针等于第i个结点指针域的指针，第i个结点的指针域存放新结点的地址即可。,查 找,访 问,查 找,修 改,插入,/*在第 i 个数据元素后插入一个新的数据元素*/ void insert(char c,int i) int j=1; struct link *node,*temp; temp=(struct link *)malloc(sizeof(struct link); temp-data=c; if(inext=head; head=temp; elsenode=head;,查 找,访 问,查 找,修 改,插入,while(node-next) if(j+=i) break; node=node-next; if(node!=NULL) temp-next=node-next; node-next=temp; else node=temp; temp-next-NULL; , 双向链表:,4.2.2 线性表的链式存储结构,4.2 线性表,数据操作：访问、修改、删除、插入, 双向链表:,4.2.2 线性表的链式存储结构,4.2 线性表, 循环链表:,4.2.2 线性表的链式存储结构,4.2 线性表,链表与线性表相比，其特点： （1）删除或插入运算，数据元素不需要移动； （2）不需要事先分配存储空间； （3）表的容量根据需要动态申请和动态释放。,4.2.2 线性表的链式存储结构,4.2 线性表,链式存储结构的应用 链表较适合用于表容量大小不定、且增删操作频繁的场合。,4.2.2 线性表的链式存储结构,4.2 线性表,1什么是栈,后进先出,4.3 栈,三、栈,2. 栈的运算,深度优先搜索问题,4.3 栈,三、栈,3.栈的应用,某齿轮传动箱的传动关系图，其中0号轴为输入轴，6、7、8、9号轴为输出轴，其余各轴为中间传动轴。编写程序，输入指定的轴号，打印从0号轴到指定轴的传动路线。,4.3 栈,#include #include #define MAX 10 static int aMAXMAX=0,1,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1; main() int i=0,j=0,top=0,n,dir,sMAX; printf(“输入轴号(1-%d):“,MAX-1); scanf(“%d“,stop=0; while(top=0|j10) if(aij=1) top+; stop=j; if(j=n) printf(“n%d号轴的传动路线是:“,n); for(i=0;i=top;i+) printf(“-%d-“,si); switch(top%2) case 0:printf(“n输出轴转动方向与输入轴相同n“);break; case 1:printf(“n输出轴转动方向与输入轴相反n“);break; exit(1); else i=j;j=0; ,else if(j=9) j=stop; top-; i=stop; j+; printf(“没有找到%d号轴的传动路线n“,n); ,四、树,1树的概念 树（tree）是一种重要的非线性的数据结构，主要用来存放非线性的具有分支结构的结点。结点之间有着明显的层次关系。这种结构形式很常见。如书的目录。,4.4 树,四、树,2树的特点 1）根 2）叶子节点（终端结点）：度为零的结点称为叶子 结点或终端结点 3）节点的度：一个结点具有的子树数目称为该结点 的度 4）树的度：树内各结点的度的最大值称为树的度,4.4 树,四、树,2树的特点 5）结点的双亲：结点的直接前驱称为该结点的双亲 6）结点的孩子：结点的直接后继称为该结点的孩子 7）兄弟：同一双亲的孩子间称为兄弟 8）树的深度或高度：树中结点的最大层次称为树的深度或高度 9) 森林：0个或多个不相交的树的集合称为森林,4.4 树,四、树,2树的特点,如下图所示树：结点A、B、C的度分别为2、3、1；结点D、F、G、H、I均为叶子结点；树的度为3；结点A是结点B、C的双亲；结点B、C是结点A的孩子；B、C是兄弟；根结点为第一层，共有4层，树的高度为4。若去掉结点A就成为森林。,4.4 树,四、树,3树的存储结构 树结构为非线性结构，需采用多重链表存储，即每个结点除了数据域外，还需设有多个链域，分别指向该结点各孩子结点。,4.4 树,五、二叉树,1二叉树的概念： 二叉树是一种很重要的树结构。它的特点是每个结点下只有左右两棵子树，且左右子树不能颠倒，否则为另一棵二叉树。,4.5 二叉树,五、二叉树,2二叉树的分类 二叉树有五种基本形态，如图所示，其中（a）空二叉树，（b）只有一个根结点的二叉树，（c）右子树为空的二叉树，（d）左子树为空的二叉树，（e）左右子树均为非空的二叉树。,4.5 二叉树,五、二叉树,3二叉树与一般树的区别在于： 1）一般树至少有一结点，而二叉树可以为空。 2）一般树的子树不区分左右，而二叉树有左右之分，且不能颠倒。 3）一般树的每一个结点可以有任意个子树，而二叉树每一个结点的子树不能超过2个。,4.5 二叉树,五、二叉树,4二叉树的存储结构 如图所示为二叉树的逻辑结构和存储结构。二叉树的每个结点除了数据域info并设立两个链域Lchild、Rchild分别指向该结点的左子树和右子树的根结点。由于二叉树中的每个结点的构造均相同所以给存储和运算带来方便。,4.5 二叉树,五、二叉树,4二叉树的存储结构 如图所示为二叉树的逻辑结构和存储结构。二叉树的每个结点除了数据域info并设立两个链域Lchild、Rchild分别指向该结点的左子树和右子树的根结点。由于二叉树中的每个结点的构造均相同所以给存储和运算带来方便。,（b）逻辑结构,4.5 二叉树,五、二叉树,4二叉树的存储结构 如图所示为二叉树的逻辑结构和存储结构。二叉树的每个结点除了数据域info并设立两个链域Lchild、Rchild分别指向该结点的左子树和右子树的根结点。由于二叉树中的每个结点的构造均相同所以给存储和运算带来方便。,4.5 二叉树,五、二叉树,5二叉树的遍历,4.5 二叉树,遍历定义指按某条搜索路线遍访每个结点且不重复 （又称周游）。 遍历用途它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 遍历方法牢记一种约定，对每个结点的查看都是 “先左后右” 。,五、二叉树,5二叉树的遍历,4.5 二叉树,遍 历 规 则,二叉树由根、左子树、右子树构成， 定义为D、 L、R D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先序遍历 中序遍历 后序遍历,五、二叉树,5二叉树的遍历,4.5 二叉树,先序遍历: 根左右 结果为： 中序遍历： 左根右 结果为： 后序遍历： 左右根 结果为：,A B D E C D B E A C D E B C A,五、二叉树,5二叉树的遍历,4.5 二叉树,A,T,X,B,C,P,Z,Y,先序遍历:,中序遍历：,后序遍历：,ATBZXCYP,TZBACYXP,ZBTYCPXA,五、二叉树,5二叉树的遍历,4.5 二叉树,遍历的算法实现：用递归形式格外简单！,则三种遍历算法可写为:,先序遍历