机械CAD第3章

机械CAD第三章CAD/CAM软件开发基础学习目标：掌握软件开发所需数据结构的基本理论；学会利用计算机，针对工程设计中不同数据的形式，采用适当的方式进行处理；了解数据管理几种方法的特点；掌握排序、查找的基本方法和数据库的基础知识；会编写排序、查找程序。学习内容：数据结构掌握数据资料的程序化处理应用数据库的基本原理与应用应用学习重点：数据资料的程序化处理方法。学习难点：数据结构。学习建议:本知识点中抽象内容较多，理论性很强，对非计算机专业学生来说有一定难度，应首先理解和掌握基本概念，在此基础上，学习具体的应用和实现算法；复习和进一步掌握一种高级语言，注意上机练习和实践。3.1软件开发和软件工程CAD／CAM软件开发是一项高难度、高智力的工程项目。为了保证所开发软件的质量，必须研究和采用科学的开发方法和技术。3.1软件开发和软件工程3.1.1软件开发的演化过程1.个人编程时代（1946年~50年代末）2.软件作坊时代（60年代初~60年代末）3.软件工程时代（70年代以后）3.1软件开发和软件工程3.1.2软件工程1、强调使用生存周期方法学。2、软件生存周期：软件产品从形成概念开始，经过开发、使用和不断增补修正，直到最后被淘汰的整个过程。3、国家计算机软件开发规范(GB8566-1988)将软件生存周期划分成六个阶段：3.1软件开发和软件工程3.1.2软件工程3、软件开发的六个阶段：(1)可行性研究与计划阶段；(2)需求分析阶段；(3)设计阶段；(4)实现阶段；(5)测试阶段；(6)运行与维护阶段。3.1软件开发和软件工程3.1.3软件工程规范美国电气与电子工程协会(IEEE)在1976年制定了软件工程标准，并于80年代初陆续获得批准、颁布、实施。我国在20世纪80年代初，由航空部率先成立软件工程化工作小组。80年代末颁布、实施。3.1软件开发和软件工程3.1.3软件工程规范1．软件工程规范国家标准(1)《计算机软件开发规范》(GB8566-88)(2)《计算机软件产品开发文件编制指南)(GB8567-88)(3)《计算机软件需求说明编制指南》(GB9385-88)(4)《计算机软件测试文件编制规范》(GB9386-88)(5)《计算机软件质量保证计划规范》(GB/T12504-90)(6)《计算机软件配置管理计划规范》(GB/T12505-90)(7)《软件工程术语》(GB/T11457-90)3.1软件开发和软件工程3.1.3软件工程规范2．软件文档3.1软件开发和软件工程3.1.3软件工程规范2．软件文档3.1软件开发和软件工程3.1.3软件工程规范2．软件文档3.1软件开发和软件工程3.1.4软件开发方法1．瀑布型（顺序、单向、单链式）2．快速原型及螺旋型3．平行进程型3.2数据结构数据结构的基本概念和术语数据结构常见的数据结构文件什么是数据数据实际上是对客观对象、现实世界的性质和关系的一种描述。例如：一个机械产品的数据包括：性能参数、结构参数、工艺参数、图样信息等。这些数据从不同角度反映了产品的性质以及它与环境的关系。在CAD/CAM中一个孤立的数据是没有实际意义的，相关的数据结合能描述一个复杂的事物，也就是说数据之间的关系为数据赋予了丰富的涵义。对于数据的研究、管理与应用不单纯是局限于数据的本身，更重要的是要研究数据之间的关系，这就是数据结构的问题3.2.1数据结构的基本概念与术语：事物状态的表达，实际上经历了三个不同的领域：•现实世界现实世界中的事物•信息世界现实世界中的事物在人的头脑中的反映，人脑中的观念事物•数据世界观念世界的数据化表达在事物的表达用数据处理时，首先应将现实世界转化为信息世界，然后将信息世界转化为数据世界。现实中的一个齿轮头脑中的一个齿轮齿轮的材料、齿数、模数、齿形曲线、齿面硬度、齿轮精度等级以及其他结构参数等。一、数据结构的基本概念：这里的数据包含几个层次概念：实体客观存在的并可互相区分的事物属性实体的特征属性值每个属性所能测量或纪录的值域属性值的变化范围数据描述实体的数值、字符及其它的各种物理符号二、数据按组成内容可分为若干个层次级字符是数据的最小单位数据项是数据中最基本的、不可分的并有命名的数据单位组合项由若干个数据项组成记录相关组合项和数据项的集合构成一个记录，是描述某个实体属性的集合文件相同性质的记录的集合就是文件数据库非单纯性、有结构文件的集合3.2.2数据结构一、数据结构：是研究数据之间的结构关系的科学。一组数据中各数据元素不是孤立的，而是彼此相互关联的，数据结构理论是研究数据元素之间的抽象关系，而不是研究数据元素的具体内容。二、数据结构：包括数据的逻辑结构和物理结构。数据元素之间的抽象化关系，并不涉及数据元素的具体内容。以车床为例：三、数据的逻辑结构数据的逻辑结构描述的是数据之间的逻辑关系，它从客观的角度组织和表达数据。数据的逻辑结构可分为两大类：线性结构非线性结构1、线性结构在这种数据结构中，每一个数据元素仅与它前面的一个和后面的一个数据元素相联系，因而只能表达数据间的简单顺序关系。如：BASIC、FORTRAN、C等各种算法语言中的数组都是采用这种结构。下图就表示了一个线性结构：包括树状结构和网状结构等。如下面的工艺路线方案图即是一种网状结构：2、非线性结构四、数据的物理结构数据的物理结构是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及数据间的关系。顺序存储结构链接存储结构1、顺序存贮结构利用一组连续的存储单元依次存放各数据元素。如将G1(1),G1(2)...G1(12)一维数组存入计算机，则各数据在存贮器中的存储顺序与逻辑顺序一致，也为依次排列。顺序存贮结构的特点顺序存贮结构占用存储单元少，简单易行，结构紧凑。但数据结构缺乏柔性，若要增删数据，必须重新分配存储单元，因而不适合需要频繁修改、补充、删除数据的场合。2、链接存贮结构即把数据的地址分散存放在其他有关的数据中，并按照存取路径进行链接。即：把数据存储到相应的地址中（数据地址或数据指针）在链接存储结构中，一个数据元素项由信息字段（INFO）和指针字段(POINT)组成：链接存储有以下几种形式：链接存贮结构的特点：链接存储结构在不改变原来存贮结构的条件下，增删记录十分方便，只要控制指针即可。3.2.3常见的数据结构线性表栈和队列数组队列串树与二叉树图与网一、线性表线性表逻辑结构线性表是一个由n（n≥0）个数据元素a1,a2,a3…an组成的有限序列，表中的每一个数据元素，除了第一个和最后一个，仅有一个直接前驱和直接后继。当n=0，称为空表。线性表的逻辑表示[a(1),a(2),a(3),…,a(k-1),a(k),a(k+1),…,a(n)]例如：光轴轴径系列值表示成线性表形式：（3，6，10，14，18，...）线性表物理结构的特点：数据元素之间呈线性关系，既可以采用顺序存储，也可以采用链接存贮结构。二、栈栈是一种特殊的线性表，它的插入与删除操作只能在表的一端进行。栈顶允许插入和删除操作的一端称为栈顶。栈底不允许插入和删除操作的一端称为栈底。栈的操作是按照后进先出的原则进行的即：LIFO。如，水库的水，衣服的穿脱，零部件的装拆等。栈的顺序存贮结构三、队列队列也是一种特殊的线性表，它限定只能在表的一端插入，在表的另一端删除。队尾允许插入的一端叫队尾。队头允许删除的一端叫队头。操作第一个进队的数据元素也将会第一个出队。所以，队列也叫先进先出（FIFO）表。队列的物理结构顺序存贮结构在顺序存贮结构中，要分别设头指针和尾指针。为出队和进队的数据指明存贮地址。队列头尾相结就成了循环队列，以解决假溢出。链接存贮结构四、数组数组：一组按一定顺序排列的具有相同类型的数据。一维数组的逻辑结构实际上就是一个简单的线性表。二维数组可将一行或一列数据元素看成一个数组元素，这个数组元素本身也是个一维数组，也相当于一个线性表。N维数组可以类推。数组与线性表的存储方式相同，用顺序存储结构存放在存储器中，数组都是按一维排列存储的。五、串串：一种字符型的线性表。通常记为：A=a1a2...an其中，A是串名，a1a2a3...为A的值。ai(1≤i≤n)为字符型常量。串的存储：可以用一个字符型数组来顺序存储，也可以链接存储。六、树树表示了元素之间的层次关系，这种关系就仿佛一棵倒长的树，故得名。树中只有一个没有前驱的结点称为树根，其它结点仅有一个直接前驱结点；树中结点的最大层次称为树的深度；结点的子树的个数称为度；度数是0的结点称为树叶。1、树的物理结构树中的各数据可以连续存储，也可以分散存储，通过指针来建立元素间的联系和存取路径。单向链结构存储结构与逻辑结构不一致，每个元素只用一个指针，存取路径和时间较长。多向链结构存储方式与逻辑方式一致，各层次的数据元素分别按顺序连续存储在三块中，层次间的逻辑联系用指针实现。当下层数据个数较多时，指针就多，所占存储单元就多。（见书）环链结构分别建立上下层次之间、同层各元素间的环链连接，可通过左右不同的指针来达到存取要求或不同的数据组合。（见书p44）2、二叉树二叉树的特点与形态•二叉树可以是空的，树则必须至少有一个根结点。•二叉树的度数不能超过2，树则无此限制。•二叉树的子树有左、右之分，不能颠倒，树的子树则可以交换位置。3、二叉树的物理结构通常采用链接结构，每个结点设两个指针，左指针指向左子树的地址；右指针指向右子树的地址。4、二叉树的遍历即按一定规律，不重复地访问树中的每一个结点。遍历方法有三种(以访问根结点为基准)前序遍历：按从上到下，先左后右的原则。中序遍历：按从左向上，先上后下的原则。后序遍历：按从左到右，先下后上的原则。二叉树的遍历(以访问根结点为基准)：前序遍历：按从上到下，先左后右的原则。中序遍历：按从左向上，先上后下的原则。后序遍历：按从左到右，先下后上的原则。七、图与网1、图是比树更为复杂的一种非线性结构。在图结构中，每个结点可能有多个直接前趋，也可能有多个直接后继，结点的联系是任意的，因此它不象树结构那样有明显的层次关系。1、图图由顶点和边组成，设图G=（V,E）其中V是顶点的集合；E是边的集合。边由确定该边的两顶点表示。若两顶点是有序的，则从Vi到Vj用一带箭头的线段相连，并用尖括号表示〈Vi,Vj〉,这样的图称为有向图。若两顶点是无序的，则边不带箭头，用圆括号表示为(Vi,Vj)，这样的图称为无向图。通常用N阶方阵表示N个顶点的图的逻辑结构。每个元素满足：V（i,j）=1若（Vi,Vj）∈E(G)即Vi,Vj有边连接V（i,j）=0若Vi,Vj无边连接2、网当图的边具有和它相关的权时，这样的图称为网。权可以代表从一个顶点到另一个顶点的距离、时间、所耗代价等等。网同样可采用邻接矩阵的形式表示,只是矩阵元素的取值为相应的权值。V（i,j）=Wij若（Vi,Vj）∈E(G)即Vi,Vj有边连接V（i,j）=0若Vi,Vj无边连接3.3.4文件文件：是数据管理的一种形式，它能独立于应用程序单独存储。:常作为管理数据、交换数据的方法而被广泛采用；即，文件是记录的集合。一、文件关键字：能够唯一地标识记录的数据项的值。如齿轮零件号数据项的值可作为关键字二、文件的组织方法组织方法概念说明顺序文件物理顺序与逻辑顺序一致的文件。有效存储区域是连续的，结构紧凑、简单，但增删、检索不够方便。磁带就是典型的顺序存储器。索引文件带有关键字和存放地址索引表的文件。索引文件的索引项必须按关键字顺序排列，文件本身可以按顺序排列或不按顺序排列，前者称为索引顺序文件，后者称为非索引顺序文件。直接存取文件（随机文件）采用一种算法将记录的关键字转化为一个近乎随机的数，根据这个数确定记录在存储器上的位置，以便存取。直接存取文件通常是利用杂凑法组织的。二、文件的组织方法（续）三、文件的查找1、顺序查找法从第一条记录开始，逐个查询，若找到欲查数值，则查找成功；否则查找失败。该法简单