第3章CADCAM软件开发基础(计算机辅助设计与制造)56979.pptVIP

二、数据结构 数据结构是指数据之间的结构关系。包括数据的逻辑结构和物理结构。 1、数据的逻辑结构 描述数据之间的逻辑关系，有线性结构和非线性结构两种。 （1）线性结构：指按顺序简单进行排列。 （2）非线性结构：无法按顺序简单进行排列,例如图3.9、3.11 2、数据的物理结构 数据的物理结构指数据在计算机内部的存储方式，常用的有顺序存储结构和链接存储结构。 （1）顺序存储结构：数据按一定的排列顺序进行存储，例如G[1]、G[2]、G[3]、….G[30]等 （2）链接存储结构(图3.14)： a.单向链：正向链(图3.14 a)、反向链(图3.14 b)和环链结构(图3.14 c) b双向链：双向链(图3.14 d)和双向环链(图3.14 e) c多向链：(图3.14 f) 三、常见的数据结构 1、线性表：(a1,a2,a3,…,an) 2、栈与队列： （1）栈：具有后进先出特性（LIFO） （2）队列：具有先进先出特性（LIFO） 3、数组：a(1,1),a(2,1),a(2,1),a(2,2) 4、串：字符型线性表,A=“a1,a2…an” 5、树与二叉树 （1）树 树的表示见图3.21 （2）二叉树 二叉树是树结构的一种重要形式，见图3.23 A、二叉树的特点与形态，见图3.22 B、二叉树的结构，见图3.23 C、二叉树的遍历，见图3.24 i、前序遍历（图3.24a ）：从上而下，先左后右 ii、中序遍历（图3.24b）：从左至上，先上后下 iii、后序遍历（图3.24c）：从左至右，先下后上 表3.10为齿轮参数表，每一行构成一个记录，可以将齿轮零件号作为数据文件的关键词 3.3CAD/CAM中的数据结构 一、数据文件 1、常用的文件组织方法 （1）顺序文件：按顺序记录数据 （2）索引文件：关键词和索引表的文件 见图3.28 （3）直接存取文件（随机文件）见图3.29 2、文件的操作 （1）查找： A、顺序查找方法：按顺序逐个查找，方法简单，效率低。 B、折半查找方法：文件按关键字大小排列，比较关键字中点值与查找关键字大小，若查找关键字大于关键字中点值，说明查找的记录在后半区域，反之，同理。折半查找方法的参考程序见P304程序4 C、分块查找方法：文件按关键字大小排列成几个块后，查找的关键字在某块中，在该块中查找记录。 （2）排序 A、选择排序：选出最小的关键字记录，与第一个记录交换，然后，依次类推。 例如：关键字序列（8,4,3,6,9,2,7）选择排序操作过程如下： a、（8,4,3,6,9,2,7）选出2 b、（2,4,3,6,9,8,7）交换2与8位置，选出3 c、（2,3,4,6,9,8,7）交换3与4位置，选出7 d、（2,3,4,6,7,8,9）交换7与9位置，排序结束 选择排序参考程序见P304程序5 B、冒泡排序：按顺序比较相邻的关键字，后面的比前面小，交换位置，依次类推，直到结束。 例如：关键字序列(9,7,18,3,4,10,8)，冒泡排序操作过程如下： a、(9,7,18,3,4,10,8)比较9与7，97，交换位置，比较9与18， 918，位置不变…… b、(7,9,3,4,10,8,18)比较9与3，93，交换位置，比较9与4， 94，交换位置…… c、(7,3,4,9,8,10,18)比较7与3，73，交换位置，比较7与9， 97，位置不变…… d、(3,4,7,8,9,10,18)排序结束 C、插入排序：依次比较关键字大小，如果后面的关键字小，将后面的记录插入到前面，依次类推。例如： a、(8,4,6,9,2,7) 关键字84，4记录插到8前 b、((4,8),6,9,2,7) ，6记录插到4与8中间 c、 ((4,6,8),9,2,7) ，9记录插到8后 d、 ((4,6,8,9),2,7) ，2记录插到4前 e、 ((2,4,6,8,9),7) ，7记录插到6与8中间f、 ((2,4,6,7,8,9)) ,排序结束 二、数据库系统 1、数据库特点： （1）、数据模型复杂 （2）、共享性能好、冗余度低 （3）、数据具有独立性 （4）、数据具有安全性、完整性 2、数据库管理系统 （1）、数据库系统构成 A、硬件 B、软件 C、数据库管理员 D、数据库 （2）、数据库管理系统的功能 A、数据库定义 B、数据库管理 C、数据库的建立与维护 D、通讯 E、其他 （3）、数据库系统的组成 A、数据描述语言(Data Description Language, DLL) B、数据操作语言(Data Manipulation Language, DML) C、数据库管理例行程序(Data Base Management