第2章支撑技术

CHAPTER2 （第三章）BasicDevelopmentofSoftwareforCAD/CAMCAD/CAM支撑技术

简述

本章从软件开发的演化过程入手，引出软件工程的思想和方法以及软件开发的一般步骤，介绍了软件开发的技术基础——数据结构,并就CAD/CAM集成的关键——数据库技术进行阐述。

3.1软件开发与软件工程3.1.1软件开发的演化过程个人编程时代（46年~50年代末）软件开发是科学家们根据各自的应用需要写出的能够解决预定问题的运行程序。程序生产的效率极低，可靠性难以保证，且仅限于处理比较简单的数值计算问题。

软件开发的演化过程

软件作坊时代(60年代初一60年代未)

软件作坊的开发方法是个体的或小组的思维行为，使得软件任务延误、质量不可靠、甚至无法维护，极大地制约了计算机以后)的功能发挥和实际应用。软件工程时代(70年代在世界范围内出现了许多组织严密、管理科学、手段先进、工具齐全的软件开发公司，为计算机软件市场提供了大量成功的软件产品。80年代，明确提出了“软件工程支撑环境”的思想，使程序设计可以直接从支撑环境中调用所需的各个“组件”。3.1.2软件工程

软件工程的概念要解决软件危机需要借鉴从事工程项目所积累的原理、概念、技术和方法来开发和维护软件，把正确的管理和科学的技术结合起来，这就是软件工程。软件的生存周期软件产品从形成概念开始，经过开发、使用和不断增补修正，直到最后被淘汰的整个过程。按照软件工程的思想，这个过程又可划分成若干个互相区别而又有联系的阶段。软件的生存周期的六个阶段

（1）可行性研究与计划阶段明确“要做什么”及“是否能做”（2）需求分析阶段弄清“必须做什么”（3）设计阶段“如何做”和“如何具体做”（4）实现阶段源程序的编码、编译及程序单元测试。（5）测试阶段总装测试和确认测试（6）运行与维护阶段

根据新提出需求，扩充和修改软件

软件开发各阶段

软件的四类维护活动（1）改正性维护诊断和改正运行中发现的软件错误（2）适应性维护修改软件以适应环境的变化（3）完善性维护根据用户的要求改进或扩充软件（4）预防性维护

修改软件为将来的维护活动做预备。3.1.3软件工程规范

1．软件工程规范国家标准

(1)《计算机软件开发现范》(2)《计算机软件产品开发文件编制指市》

(3)《计算机软件需求说明编制指南》

(4)《计算机软件测试文件编制规范》(5)《计算机软件质量保证计划规范》(6)《计算机软件配置管理计划规范》

(7)《软件工程术语》2．软件文档

文档是软件开发阶段之间、程序员之间通讯的工具。按照《计算机软件产品开发文件编制指南》(GB8567—88)规定，整个软件生存周期共应提交十四种标准文档。3.1.4软件开发方法软件作为—种产品应当满足以下基本要求(1)正确性满足用户提出的应用需求，实现规划的全部功能。(2)可靠性出错概率小于预定指标，运行正常，容错性好。(3)完整性提供完整的有效运行程序和文档资料以及必要的培训服务。(4)实用性具有良好的人机界面，操作简便，有适用范围，能解决实际问题。(5)可维护性

便于纠正软件错误，扩充系统功能，实现各类维护活动。软件开发方法的三种类型

软件开发方法主要有三种类型：瀑布型快速原型及螺旋型平行进程型1.瀑布型

一种按软件生存阶段而顺序工作的、单向、单链的开发方法。

2．快速原型及螺旋型

尽快向用户提供原型系统，让用户试用，得到反馈信息，再按实用性、经济性、可靠性要求进一步修改设计，解决原型系统暴露出来的问题，从而开发出产品。3．平行进程型

该方法认为软件开发是三个进程组相立平行、相辅相成、齐头并进的团队行为。3.2数据结构

数据实际上是对客观对象、现实世界的性质和关系的一种描述。一个机械产品的数据，包括性能参数、结构尺寸、工艺过程、图样信息等．它们代表着该产品的性质及它与环境之间的关系。在CAD/CAM中，一个孤立出来的具体数据往往没有实际意义，而各种相关数据的集合就能描绘任一复杂事物，数据之间的关系有丰富的涵义。因此，对于数据的研究与管理不单纯限于数据本身，更重要的在于数据之间的关系，也就是结构问题。3.2.1基本概念与术语

从事物的物理状态到表示信息的数据，实际上经历了三个不同的领域：

现实世界——是存在于人们头脑之外的客观世界。信息世界——现实世界在人们头脑中的反映，是人们头脑中的观念世界。数据世界——是观念世界中信息的数据化，它是计算机处理的对象。

在数据处理中，首先应将现实世界转换为信息世界，然后再将信息世界转换为数据世界。基本概念与术语

其中包含几个层次的概念：

(1)实体客观世界存在并可相互区别的事物。

(2)属性实体的特性。

(3)属性值每个属性所能测量或记录的值。若干属性的属性值组成的集合即可表征一个实体。

(4)域属件值的变化范围。

(5)数据

描述文体的数值、字符及其它等各种物理符号。数据按其组成内容又可分为若干个层次级

数据1)字符

是数据的最小单位。2)数据项

是数据中最基本的、不可分的并有命名的数据单位。3)组合项

由若干个数据项组成。4)记录

相关组合项或数据项的集合构成一个记录，是描述某个实体属性值的集合。5)文件

相同性质的记录的集合就是文件。6)数据库非单纯性、有结构文件的集合。3.2.2数据结构

数据结构指的是数据之间的结构关系。数据元素不是孤立的，而是彼此相互关联的。数据结构理论研究数据元素之间的抽象化的关系，并不涉及数据元素的具体内容。数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构

1．数据的逻辑结构数据的逻辑结构描述的是数据之间的逻辑关系，它从客观的角度组织和表达数据通常可将逻辑结构归纳为两大类型。（1）线形结构这种结构的数据可以用数表的形式表示。在这种结构中，每一个数据元素仅与它前面的一个和后面的一个数据元素相联系，因而仅能用于表达数据之间的简单顺序关系。（2）非线性结构

这种结构的数据间逻辑关系比较复杂。这种数据元素之间的关系是一种多元关系。数据的物理结构

2．数据的物理结构数据的物理结构指的是数据在计算机内部的存贮方式，它从物理存贮的角度来描述数据，以及数据间的关系。常用的物理结构有顺序存贮结构与链接存贮结构两种。顺序存贮结构的存贮方式占用存贮单元少，简单易行，结构紧凑。但数据结构缺乏柔性，若要增删数据，必须重新分配存贮单元，重新存入全部数据。链接存贮结构可独立于逻辑结构，它使存贮的物理顺序不必与逻辑顺序一致而仍能按逻辑要求来存取数据。顺序存贮结构（1）顺序存贮结构：用一组连续的存储单元依次存放各种数据元素

。链接存贮结构

(2)链接存贮结构把数据的地址分散存放在其它有关的数据中，并按照存取路径进行链接。这样，在求得初始数据的地址后，检索出该地址存放的数据和下一个数据的地址，可逐次找到各个所需的数据。数据中存入的下一个数据的地址称为指针。通过各种指针，可构成不同的存取路径，以适应逻辑结构的需要。一个数据元素项由信息字段(INFO)和指针宇段(P()INT)组成。

链接存贮结构的类型

链接存贮结构根据指针的数目有三种类型

1)

单向链结构

2)双向链结构

3）多向链结构

3.2.3常见的数据结构

1．线性表这是—种最简单、最常见的数据结构，其特点就是数据元素之间呈线性关系，线性表的物理结构既可以采用顺序存贮结构，也可以采用链接存贮结构。线性表逻辑上可以表示为：常见的数据结构——栈与队列

2．栈与队列（1）栈

栈是一种特殊的线性表，它的插入和删除操作只能在表的一端进行。在栈中允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。顺序存贮和链接存贮都可以作为栈的存贮结构。只是采用顺序存储时要外加一个栈顶指示器。

在程序设计中，栈是一种非常有用的数据结构。子程序的调用和返回处理大多是用栈来实现的：递推算法也可以用栈结构来实现。

栈与队列栈与队列

(2)队列

队列也是一种特殊的线性表，它限定只能在表的一端插入，在表的另一端删除。允许插入的一端叫队尾，允许删除的一端叫队头。队列的物理结构可采用顺序存贮和链接存贮结构。常见的数据结构——数组、串

3．数组数组是线性表的推广，是一组按一定顺序排列的具有相同类型的数据。一维数组的逻辑结构实际上就是一个简单的线性表。至于二维数组，可将一行(或一列)数据元素看成一个数组元素，这个数组元素本身也是一个一维数组，即也相当于一个线性表。n维数组可以类推。数组与线性表的存贮方式相同，用顺序存贮结构存放无论一维数组还是二维数组或更高维数组在存贮器中部是按一维排列存贮的，只是按照一定的存贮顺序。

4．串串是一种字符型的线性表，串可用一个字符型数组来顺序存贮，也可用链接存贮。

常见的数据结构——树

5.树与二叉树（1）树树的每一个结点可能有无数个后继，但只有一个前驱，并且最高层结点没有前驱，树结构表示了元素间的层次关系。树中只有一个没有前驱的结点称为树根，其它结点仅有一个直接前驱结点，树中结点的最大层次称为树的深度；结点的子树的个数称为度；度数是0的结点称为树叶。树的物理结构可有多种形式。各数据元素既可以连续存贮在一起，也可以分散存贮，通过指针来建立元素间的联系和存取路径。

树的表示

树的存贮方式树的单向链存储结构

1)单向链结构

存贮结构与逻辑结构不—致，每一个元素只用一个指针，存取路径和时间较长。树的多向链存储结构

2）多向链结构

存贮结构与逻辑结构—致，各层数据元素分别按顺序连续存贮在三块中，层次之间的逻辑关系用指针实现。树的环链存储结构

3）环链结构分别建立上下层之间、同层各元素之间的环链连接，可通过左右不同的指针来达到不同的存取要求或不同的数据组合。左指针构造上下层次间的环链，右指针构造每一个子树的同层各元素间的环链。二叉树

（2）二叉树

1)特点与形态二叉树是树结构中的一种重要类型。二叉树与树的区别：

a．二叉树可以是空的，树则必须至少有一个根结点。

b．二叉树的度数不能超过2，树则无此限制。

c．二叉树的子树有左、右之分．不能颠倒，树的子树则可以交换位置。

二叉树的基本形态

二叉树的基本形态二叉树的存储结构

2)物理结构

通常采用链接结构．每个结点设两个指针，左指针指向左子树的地址；右指针指向右子树的地址。这种结构与逻辑结构一致，描述清楚，也便于删除和运算，但占用存贮单元较多。

遍历二叉树

3)遍历二叉树即按一定规律，不重复地访问树中的每一个结点。这对于在二叉树中查找某一指定结点，或逐一对全部结点进行某种处理，或将非线性结构线性化具有重要意义。对于线性结构来说，遍历并非难事，但对二叉树来讲就需要找到一个完整而有规则的遍历方法。常用的遍历方式有三种：前序遍历中序遍历后序遍历常用的遍历方式

a．前序遍历操作过程为：若二叉树为空，则退出。否则，a)访问根结点；b)前序遍历左子树；c)前序遍历右子树。这是一个从上至下，先左后右的原则。如图3—22所示二叉树的前序遍历为：ABDE—HICFG(见图3—23a)。

b．中序遍历操作过程为：若二叉树为空，则退出。否则，a)中序遍历左子树；2b)访问根结点；c)中序遍历右子树。这是—个从左向上．先上后下的原则。如图3—22所示二叉树的中序遍历为：DBHEIAFCG(见图3—23b)。

c．后序遍历

操作过程为：若二叉树为空．则退出。否则，a)后序遍历左子树；b)后序遍历右子树；c)访问根结点。这是一个从左向右，先下后上的原则。常用的遍历方式常见的数据结构——图与网

6．图与网(1)图图是比树更为复杂的一种非线性结构。在图结构中，每个结点可能有多个直接前趋，也可能有多个直接后继，结点的联系是任意的，因此，它不象树结构那样有明显的层次关系。网

(2)网

当图的边具有与它相关的权时，这样的图称为网。权可以代表从一个顶点到另一个顶点的距离、时间、所耗代价等等。可用邻接矩阵表示网，只要把矩阵中原来为l的元素改为权值即可。3.2.4文件

文件是数据管理的一种形式，它能独立于应用程序单独存贮。在CAD／CAM系统中，文件常常作为管理数据、交换数据的方法而被广泛采用。具体地说，文件是记录的集合。能够唯一地标识记录的数据项的值称为关键字。

同一文件的逻辑结构可以有多种物理组织方法，也可对文件进行需要的操作。

1．常用的文件组织方法顺序文件、索引文件、直接存取文件、索引链接文件、倒排文件、B树和变长记录文件等。文件的操作2．文件的操作文件的操作主要表现在两个方面，—是查找，二是排序。（1）查找即寻找关键字为某值的记录．常用的查找方法有三种：1)顺序查找法；2)折半查找法；3)分块查找法。（2）排序对文件中记录的关键字(或数组元素值)按递增或递减的顺序重新排列。常用的排序方法：1)选择排序、2)

冒泡排序、3)插入排序3.3数据资料的程序化处理

在CAD／CAM过程中，常常要参照各种标准和规范，根据一系列相关数据资料、图表、实验曲线来选用所需的数据。这些资料是先期以数据库或文件形式加以管理，以便在设计时由计算机按要求自动检索和调用；或在程序编制过程中融于其中，将其程序化，随着程序的运行，自然选用，加工处理。这是CAD／CAM软件开发的基本工作之一。3.3.1数值程序化

数值程序化就是将要使用的各个参数及其函数关系，用一种合理编制的程序存入计算机，以便运行使用。其方法要具体问题具体分析。

1.

用数组形式存贮数据如果要使用的数据是一组单一、严格、又无规律可循的数列存贮数据，可以用诉诸形式存储数据，以便在程序运行时直接检索使

2.用数学公式计算数据

如果要使用的数值是一组单一、严格、但能找到某种规律的数列，则不必定义数组逐项赋值，将反映这种规律的数学公式编入程序，通过计算即可快速、准确地达到目的。3.3.2数表程序化

数表程序化就是用程序完整、准确地描述不同函数关系的数表，以便在运行过程中迅速、有效地检索和使用数表中的数据。归纳起来，一般有下述几种方法。

1．

屏幕直观输出法

2．

数组存贮法

3．

公式计算法

4．交互式分级描述法3.3.3线图程序化

线图程序化的前提就是找出能描述线图的数学公式。由于实际工程问题比较复杂，往往很难将实验数据用公式进行精确描述，而常常采用某个曲线公式近似地反映它们的关系，这就是所谓经验公式。建立这种经验公式的过程称为曲线拟合。常用的方法一般为：最小二乘法。

3.3.4数据资料文件化

对于需要频繁修改、或系统内各应用程序之间共享