2．机电系统CAD算法基础 2．1．数值积分算法 2．1．1 基本数值积分方法 连续系统的动态特性一般可由一个微分方程或一组一阶微分方程加以描述。因此对系统进行计算机仿真，就需要研究如何利用计算机对微分方程进行求解，目前采用的方法是应用数值积分法对微分方程求数值解，其中欧拉法、梯形法、龙格一库塔法等数值积分法是几种基本的方法。 1．欧拉（Euler）法 欧拉法是一种最简单的数值积分方法，但其精度差，实际应用很少。然而由于其算法简单且具有明显的几何意义，有利于初学者学习应用数值积分法求解微分方程，因此在讨论数值积分法时通常先介绍欧拉法。 假设一阶微分方程为  （2-1） 初始条件为  欧拉法的基本思想就是将（2-1）式中的积分曲线解用直线段所组成的折线加以近似。根据导数的定义可知，存在  故 = （2-2） 成立，当足够小时，上式可近似表示为  （2-3） 若令，则得到  （2-4） 其中h称为计算步长。 因为，，所以有 由此可得到所欲求解在处的近似值为  （2-5） 这样就可由已知点去确定它在t-y平面上的另一点。若设点是初始给定点，且微分方程的精确解经过点，对应的的精确解为，即点，而由（2-5）式求得的值所对应的点为点，其坐标为，它是从点作斜率为的线段与直线的交点。 若从点出发，可求解在 上的近似值为  （2-6） 即从几点作斜率等于的线段与直线相交而得到点。根据类似的思想由式（2-6）不难推出  （2-7）  图2-1 欧拉数值积分方法 利用上式不断对微分方程求近似解，直至点。将诸点连成一条折线，即得到所求微分方程精确解的近似曲线解，如图2-1所示。（2-7）式称为欧拉 法递推公式。 该方法简单，计算量小，由前一点即可推出后一点值，属于单步法。因其从初值即可开始进行递推运算，无需其他条件要求，因此能够自启动。该算法精度低，适当减小计算步长h有助于提高计算精度。 2．梯形法 1）．欧拉法误差原因的分析 根据欧拉法的分析可知，该方法简单但较粗 糙，精度差。考虑对于微分方程   存在精确解  当时  （2-8） 由前述推导可知  （2-9） 对照（2-8）式与（2-9）式得到，在欧拉法中存在  用代替变量，由矩形近似曲边梯形，因此造成欧拉法误差较大。 2）．改进的欧拉法——梯形法 由前述分析可以看出，进一步改进欧拉法的方法就是利用梯形面积代替矩形面积，以逼近曲边梯形面积，即  推而广之，得到梯形法公式为  （2-10） 由上式可以看出，在计算时，在等式右边存在有，因此无法求出。在这种情况下，一般采用欧拉法进行一次选代，求出的预估值，再将其代人梯形公式计算出真值，从而构成预估校正梯形公式为  （2-11）  （2-12） （2-11）式称为预报式，（2-12）式称为校正式。 3．龙格一库塔（Runge- kutta）法 考虑如下一阶微分方程   设，这里h为计算步长，在时刻的解为，可在附近展成泰勒级数，取展开式的前三项得到  （2-13） 假设上式的解可表示为  (2-14)  (2-15)  (2-16) 将在附近展开成泰勒级数，并取前三项得到  (2-17) 将(2-15)式( 2-17)式代入(2-14)式中，经整理得  (2-18) 将（2-18）式与（2-13）式相比较得到 若取，则得到。将其代入（2-14）式、（2-15）式、（2-16）式，得  （2-19） 将（2-19）式写成递推形式  （2-20） 由于（2-20）式只取了级数展开式的前三项，略去了以上的高阶无穷小，其截断误差正比于，故这种方法称为二阶龙格库塔法。二阶龙格一库塔法的计算精度是不高的，为此在实际应用中往往采用精度更高的四阶龙格一库塔法，它的截断误差正比于，由于其推导过程与二阶龙格一库塔法类似，在此就不再推导，而直接给出四阶龙格一库塔法的递推表达式，即  （2-21） 考察（2-20）式可以清楚地看出,它与前面导出的梯形算法是相同的，因而可以知道梯形法的精度也是二阶的。当对级数展开式只取前两项时可以得到，这就是前面得到的欧拉法递推式。通过对龙格一库塔法的分析与推导，可以将欧拉法、梯形法与龙格、库塔法这三种数值积分方法统一起来，它们都可归于龙格一库塔法，只不过是阶次不同而且。从理论上讲，可以构造任意阶的计算方法，但截断误差的阶数与所计算函数数值f的次数并非是等值关系。对于四阶以上龙格一库塔法，所需计算的f次数将高于误差阶数，这将大大增加了计算工作量，因而选择这种高阶龙格-库塔法是不适当的。实际上，对于工程应用四阶龙格-库塔法已完全能够满足仿真精度要求，所以四阶龙格-库塔法在实际应用中具有重要地位。 4．四阶龙格一库塔法的向量表示 前面推导过程中假设系统为一阶系统，然而实际上系统往往是高阶的，因而描述这类系统应是一组一阶微分方程或是状态方程，所以介绍求解状态方程的四阶龙格一库塔向量式是完全必要的。 考虑一n 阶系统，其状态方程的一般描述为   四阶龙格-库塔法的向量表示为  其中是微分方程组中第i个方程的第j个RK系数。有时考虑到计算方便，又可将（2-22）式展为下述形式，即      其中i=1，2，…，n；n为系统阶数；下标为递推下标。 5．亚当斯（Adams）法 前面介绍数值积分算法的特点是，在计算时刻的值 时，只用到第时刻和的值。但实际上在逐步递推过程中，计算；之前已经获得了一系列的近似值，，…，以及，，…，，如果能够充分利用历史上的一些数据来求解，则有望既可加快仿真速度又能获得较高的仿真精度，这就是构造多步法的基本思路。Adams法就是利用已经得到的这些信息来实现对的计算，由于它充分利用了前面得到的信息，所以在加快仿真速度的同时提高了仿真精度。在各种多步法中，Adams法最具有代表性，应用也最普遍。 本书不再进行公式的推导，直接给出Adams显式表达式  （2-23） （2-23）式即为Adams显式表达式，其截断误差为 ，  因此（2-23）式为四阶Adams显式公式。 （2-24）式给出了Adams隐式表达式，即  （2-24） 其截断误差为 ，  隐式Adams法的优点主要在于精度较高，然而它无法实现自身递推，需要另外的显式提供一个估计值，（2-25）式给出了由Adams显式提供的估计值，隐式加以校正的四阶Adams预估校正法公式为  （2-25） 显然上式除了由Adams显式所提供的估计值外，还需要其他方法如四阶龙格-库塔法计算出、、等初值。 2．1．2 数值积分方法的计算稳定性 1．数值积分方法计算稳定性概念 数值积分方法的稳定性与机电系统的稳定性是两个不同的概念。一个稳定的系统，当用某种数值积分方法进行仿真计算时，若该方法或应用该方法所选参数不适当，则会产生意想不到的结果——仿真结论出错，这就是由于数值积分方法的稳定性引起的。不同的数值积分方法对应于不同的差分方程，一个数值解是否稳定决定于该差分方程的特征根是否满足稳定的要求。对于不同的数值积分方法，其稳定性和约束条件都是仿真过程中的重要参数。 考察已知系统，其微分方程为    其精确解为  现在取步长h=0.1，用欧拉法和四阶龙格-库塔法计算t=1.5时的y（t）值。 欧拉法  四阶龙格-库塔法  精确解  显然此时数值计算结果是错误的。这是因为数值积分法是一种近似积分方法，它在反复递推计算中将引入误差，若误差积累越来越大，将使计算出现不稳定。所以原系统稳定与用数值积分法的计算稳定性是不同的概念。对干系统稳定性的讨论，使用微分方程或传递函数；而后者的稳定性问题需要使用相应的差分方程来讨论。由于对高阶微分方程的数值计算稳定性进行全面的分析十分困难，通常用一简单的一阶微分方程来考察其相应的差分方程的计算稳定性问题。将下述微分方程 ，  （2-26） 称为测试方程。根据稳定性理论，其特征方程的根在S平面的左半部，即根的实部 Reλ＜0时，原方程稳定。现在以这种条件来讨论数值计算方法的自身稳定性问题。 2．欧拉法的计算稳定性分析 对测试方程根据欧拉法得到  （2-27） 对上式进行Z变换得  显然其特征方程为  根据控制理论可知，（2-27）式的稳定域在Z平面上是单位圆。（2-27）式稳定的条件是它的特征方程的根处于单位圆内，即  设原微分方程的特征根，并代入上式得到  经整理得  由上式易见，在坐标系下，即平面上的一个圆与平面上的稳定域是—一对应的，或者说平面上的稳定域映射到原微分方程的参数平面上也是一个圆，圆心在 处，半径为， 如图2-2所示。 图2-2 平面与Z平面的映射关系 由此可以看出，若原微分方程是稳定的，而其特征根在平面中映射到单位圆内，则对应的差分方程也是稳定的；若原微分方程也是稳定的，若原微分方程．是稳定的，但其特征根处于平面映射圆外，则差分方程是不稳定的。显然，平面中稳定域的大小与步长h有关，h越大稳定域越小，若考虑为负实根，即，，则。因此当采用欧拉法仿真时，h应按上式选择．否则将会出现不稳定。 3．梯形法稳定性分析 将测试方程（2-26）代人梯形法速推公式．可以得到  对上式进行Z变换可得  其特征根为  将代入上式可得  考察上式可知，当原系统稳定，其特征根存在负实部，即，此时必存在。因此只要原系统稳定，则应用梯形法计算也必稳定，故梯形法属于恒稳定数值积分法。 4．龙格-库塔法的计算稳定性分析 与前两种数值积分算法的稳定性分析相类似，将测试方程（2-26）代入四阶龙格库塔递推表达式后，经过整理变形得  其中。 再对其进行Z变换，得到特征根为  根据稳定的条件 |z|< 1，得到u平面上稳定域的边界参数方程为  显然四阶龙格-库塔法的稳定域与计算步长h有关。如果h过大，值有可能落在稳定域外，因此四阶龙格-库塔法是条件稳定的。 2．1．3 数值积分方法的MATLAB实现 在机电系统仿真中，连续系统的数学模型一般都可用微分方程来描述，对于高阶系统往往可由状态方程加以表示。求解这些微分方程的最为有效和常用的方法就是数值积分法。然而为了研究系统的动态过程，就需要大量的递推求解，以得到系统在一定输入作用下的变化过程。显然对于这样大量的计算工作，必须借助计算机进行编程加以实现，这就是所谓的系统仿真。 近年来，在机电领域的分析研究中，最有影响也最为有效的编程语言就是美国Math－works公司开发的MATLAB。尽管最初MATLAB语言并非是为机电系统的设计者开发的，然而它的强大绘图功能、数值与矩阵运算能力以及灵活的编程方式，征服了众多的机电系统设计与研究人员，因此借助MATLAB语言进行数值积分方法编程，实现控制系统仿真是非常重要的。下面将通过实例介绍典型数值积分方法的MATLAB实现。 1．欧拉法的MATLAB实现 例2-1已知二阶系统   解：根据欧拉法递推公式 ，应用 MATLAB语言不难编写相应的仿真程序。在此计算步长取h=0.01，初值均为零。输入为阶跃信号，取u =20，研究系统 25秒的动态过程。下面给出了所编制的程序，图2-3给出了仿真结果。 程序：Euler. m h=0.01；Tf=28；x10=0；x20=0；u=25；t=0； m=Tf/h； 图2- 3系统阶跃响应（h= 0.01） for i=1：m x1(i)=x10＋h*(-0.5572*x10-0.7814*x20＋u)； x2（i）=x20＋0.7814*h*x10； y（i）=1.9691*xl（i）＋6.4493*x2（i）； x10=xl（i）； x20=x2（i）； t=[t，t(i)+h]； y=[y，y（i）]； end plot(t，y） grid 当取计算步长 h=0.65时，其仿真结果如图 2-4所示。比较图 2-3与图 2-4可以发现，当其他参数保持不变，仅改变计算步长，使h加大到0.65时，系统的阶跃响应开始趋于发散。如果继续加大计算步长h，将导致仿真结果发散。这一点在前面章节已进行了讨论，在此验证了这一点。 图2-4 系统阶跃响应（h=0.65） 2．梯形法（预估校正法）的MATLAB实现 仍以欧拉法中研究的二阶系统为例，根据下述梯形法的递推公式   应用 MATLAB语言编制梯形法仿真程序。在递推计算的每一步中，均应根据预估公式对x1、x2两个变量计算预估值，然后再将其代入校正公式求取真值，计算系统输出响应y，修改初值后再返回进行下一次计算，直至完成预定计算为止。下面为相应的MATLAB程序，图2-5给出了步长h= 0.65 时的系统仿真结果。 程序如下： h=0.65；Tf= 30；x10= 0；x20= 0；y（1）= 0；u= 25；t= 0； m=Tf/h； for i=1：m xl（i+1）=x10+h*(-0.5572* x10-0.7814*x20+u）； x2（i+1）= x20+0.7814*h*x10； x11=x1（i+1）； x22=x2（i+1）； xxl（i+1）=x10+0.5* h* ((-0.5572*x10-0.7814*x20+u)+（-0.5572* xll-0.7814*x22 +u))； xx2（i十1）=x20 + 0.5* h* ((0.7814*h* xl0）+（0.7814* h* xll))； y（i十1）=1.9691* xx1（i+1）+6.4493* xx2（i+1）； x10=xxl（i+1）； x20=xx2（i+1）； t=[t，t（i）+h]； y= [ y，y（i）]； end plot（y） grid 图2-5 预估校正法系统仿真（h=0.65）图2-6四阶龙格.库塔法（向量形式）系统仿真结果（h=0.65） 3．龙格-库塔法的MATLAB实现 这里仍然以欧拉法中给出的示例作为研究对象，根据前面介绍的龙格-库塔法的向量形式，可以充分应用MATLAB语言强大的矩阵和矢量运算能力使得程序更加简洁。图2－6为系统仿真结果。 程序如下： X=[0；0]；Y=0；t= 0；U= 25；Tf= 28；h= 0.01； n= Tf／h； A=[-0.5572 –0.7814; 0.7814 0]； B=[1；0]； C=[1.9691 6.4493]； D=[0]； for i=1：n K1=A*X+B*U； K2=A*(X+h*K1/2）+B*U； K3= A*（X+h*K2/2）+ B*U； K4=A*（X+h*K3）+B*U； X=X+h*（K1+2*K2+2*K3+K4）/6； Y=[Y,C*X] t=[t，t（i）+h]； end plot（t，Y） grid 2．2．数据结构 机械CAD从本质上说是一个信息处理过程。在此过程中要加工和记录大量的信息数据，如果仅采用本书前面所介绍的数据资料的处理方法，那是远远不够的。因此，有必要对CAD过程中涉及的数据进行仔细的分析，以便寻找更为合理的数据结构和管理方法。 机械CAD所涉及的数据可分为两大类： ①直接数据：即直接描述设计对象本身特性和属性的数据。这些数据在CAD过程中不断地被修改，在设计完成后被传送到技术部门进行生产准备。这类数据包括几何形状数据(结构、零部件尺寸、形状和相互位置关系等)、技术要求(材料、热处理、加工精度、粗糙度、表面处理、重量、其他特殊检验要求等)。直接数据的结构复杂，数据量大。有些复杂的对象，比如设计一架高级喷气式飞机，直接数据达数千万之多。 ②间接数据：这些数据是作为设计的参考或对设计过程进行指导管理用的，包括管理信息(成组技术编码、零部件生产厂家、价格、供应批次、配套关系及库存量等)、技术责任信息(设计员、校对员、审核员、更改革、有效批次等)、有关文献资料、设计规范、各种标准。这些数据反映了对设计提出的要求和设计经验。设计过程中随时都要检索设计规范和各种标准，复杂的设计所需要的规范资料有时多达几十种，而且这些规范标准中包含的数据量是很大的，据估算300页左右的资料，约需IM存贮量。 存贮和管理种类繁多、数量如此之大的直接和间接数据，没有完善的数据管理技术是不可能的。 CAD需要数据库技术，更主要的原因是必须保证数据的一致性。一项大型设计，参加的人员很多，各人研制各自的程序模块，各人对数据的理解和看法不完全相同，重点不同，表达方式不同。此外，数据要从一个模块传递到另一个模块，需要保证数据的一致性，而且传递的路径较长，必须保证数据的快速转换。这一切只有通过数据库技术才能解决。将CAD的各种软件模块建立在一个公共的数据库基础上，既可保证一致性，又便于各模块之间的数据通讯。 应用数据库的另一个理由是为了保证数据的安全和保密。如果设计的产品涉及国家或企业的机密，如何保证它们不受外来侵害呢？在很长的设计周期中，数据是否会被无关人员更改？一般文件系统缺乏这方面的功能。基于上述原因，数据库已成为CAD系统不可缺少的重要环节，本章将介绍数据结构和数据库方面的基本知识、机械产品数据管理技术等。以便读者在此基础上通过进一步的自学掌握工程数据管理的实用技术。 2．2．1 有关数据结构的基本概念和术语 1．数据 在计算机中表示信息的基本方式是数据。现实世界中客观存在并相互区别的事物称为实体，例如一个机械零件、一个部件或一台机器。每个实体都有一定的特性， 表2.3-1 CL型齿轮联轴器(Q/ZB104-73) 型号 轴孔直径（mm） 许用最大直径(kN?m) 最高 转速(r/min) 内齿圈联接螺栓孔n-d0 齿轮   dmin dmax dmin dmax    模数 齿数  CL1 18 40 30 38 0.71 3780 6-13 2.5   CL2 30 50 40 55 1.40 3000 6-13 2.5 38  CL3 40 60 40 55 3.15 2400 6-17 3 40  CL4 45 75 60 75 5.60 2000 8-17 3 48  CL5 50 90 80 95 8.00 1680 8-21 3 56  CL6 60 105   11.80 1500 8-21 4 48  CL7 65 120 100 120 19.00 1270 10-21 4 56  CL8 80 140 130 150 23.60 1140 10-21 4 62  CL9 90 160   30.00 1000 10-25 6 48  CL10 110 180   50.00 850 12-25 6 56  CL11 120 220   71.00 750 12-25 8 48   通常将这些特性称为实体的属性，例如机械零件中的齿轮联轴器是一个实体，表2.3-1所示的型号、轴孔直径、许用最大扭矩等是它的属性。这些属性的具体数值，如联轴器型号CL1，最大轴孔直径40mm等称为属性值。实体的属性值的全体统称为数据，而其中的每一个属性值就是一个数据元素。 在上述表中，直径18(mm)、许用最大扭矩0.71(KN·m)等是数字，型号CL1中有字母，而内齿图联接螺栓孔6—13(表示6个孔，每个孔的直径为13mm)中包含符号“—”。由此可见，数据是由数字、字母或其他符号来表示的信息。 2．数据的描述 为了使CAD系统能正确地、高效地进行数据处理，必须将各种数据按一定的形式组织起来，存放到计算机的存贮器中。数据及数据间的关系可以从逻辑和物理两方面进行描述和组织。 数据的逻辑描述是指用户或程序设计员根据元素之间的逻辑关系来组织和表达数据，也就是实际应用时数据间存在的联系。例如滚动轴承的数据可按各部分之间组成的逻辑关系表达成图10．1那样的结构，图上连线表示各部分之间的关系。  图2.3.1 滚动轴承数据的逻辑关系 用户根据数据的逻辑关系用编程语言将数据输入计算机，系统软件把这种逻辑关系按一定方式映象到计算机存贮器中，获得了数据的物理结构。所以数据的物理描述是指数据在计算机内存或外存上的布局方式、顺序及存贮单元的分布。 数据可按其组成内容分为若干层次来描述，层次的多少由系统的复杂性而定，一般可分为下列5种层次形式，它们彼此间存在从属包含的关系。 ① 字符：数据的最小单位是字符，它可以是数字、字母、专用符号(如$、*、—、+等)及汉字等。 ② 数据项：是由一组字符组成的有实际意义的数据单位，如零件名称(齿轮、带轮、轴承等)、材料(A3、45、HT15－33等)。 它们可以是简单的数据项(如表2.3-1中的许用最大扭矩、最高转速等)，也可以是几个简单数据项的组合项(如表10．1中轴孔直径就是由dmin、dmax、dmin和dmax4个简单数据项组成的组合项)。 ③ 记录：是相关的数据项组成的集合。 例如表2.3-1中每一种型号的齿轮联轴器的相关数据，即表中的每一行，就是一个记录。 ④ 文件；相同性质记录的全体称为文件。例如表2.3-1的每一行表示一种CL型齿轮联轴器的数据记录，而整张表共有性质相同的 11个记录，作为一个整体存在，它就表达 CL型联轴器各种型号属性的数据文件。 ⑤ 数据库：它是数据描述中的最高层次，是存贮器中合理存放的相关数据的集合。数据库是通过文件而组织起来的，但它不是若干文件的简单的堆积，而且还包含着对文件的重新组织和管理，以便最大限度地减少文件中数据的冗余，并能较好地满足各种不同的应用需要。 3．数据结构 所谓数据结构是指作为计算机程序加工处理的、有一定关系或约束的对象集合。简言之，就是指数据之间的相互关系或约束。由于数据结构直接影响着算法的选择和效率，所以必须解决如何把数据进行组织，形成某种类型的数据结构，其次还要解决数据的查找、插入和删除及保密等问题。 在CAD软件设计时要用到各种类型的数据结构，包括数组、堆栈、队列、链表、树等，从事CAD技术应用的人员必须熟悉这些数据结构。 2．2．2 线性表结构 线性表结构是一种最常用的数据结构形式，它包括向量、数组、堆栈和队列等。 1．向量 向量是n(＞0)个元素的有限序列，它的逻辑结构可表示成： V：(V1，V2，…，Vn) 其中，V1，V2，…，Vn表示向量V的各个元素，下角1，2，…，n表示向量元素的下标。 向量的物理结构是在存贮器中开辟一个连续的存贮空间，按照表中元素的逻辑结构顺序，依次存放到这块连续的空间中。这种顺序分配原则决定了向量中元素在存贮器中的存放地址与该元素下标之间存在着对应关系。 如有一个向量结构包括10个元素，假定每个元素占4个单元，第一个元素在内存中的始地址为100(见图2.3.2)，那么向量V中任一元素V(i)的地址可用下式求得： V(i)的始地址=100+(i一1)*4 … V1 V2 V3 … V10 …   100 104 108 136 图2.3.2 向量 2．数组 数组是向量概念的扩展。数组中所有的构成元素都是向量，而且这些子向量具有相同的上限和下限。 二维数组的表示形成为A(m，n)，其中m、派均为整数。数组的存贮也采用顺序分配原则，其存放的顺序有两种：一种是以“行”为主顺序依次存放，如图2.3.3(a)所示，用于BASIC、PASCAL和COBOL等语言编程；另一种是以“列”为主顺字依次存放，如图10．3(b)所示，用于FORTRAN语言编程。 a11 a12 a13 a21 a22 a23  A= (a) a11 a21 a12 a22 a13 a23   (b) 图2.3.3 二维数组 数组元素在存贮空间是连续存放，敌对其中的元素访问很简便。例如有一数组A(m，n)，已知其第一个元素A(1，1)存贮地址为心，每个数组元素占l个存贮单元，则以“行”为主次序存放时，可由下式求得访问地址： A(i,j)的始地址=b＋[(i—1)*n+(j-1)]*l 3．栈 在CAD中，栈是一种很重要的线性表数据结构，它限定只能在表的一端进行插入或删除。我们称可以插入或删除的一端为栈顶，另一端为栈底。 由于插入和删除只能在同一端进行，所以当前被取出的那个元素一定是最后插入的元素，即找的工作方式是“后进先出”。 栈的物理结构是在存贮器中开辟一个连续空间。要定义栈名和栈的最大容量（上界），并分配一个单元用来批示当前栈顶地址的指针( top)。 设栈S=(a1，a2，…，an)，图2.3.4为该栈的物理结构，a1为栈底元素，  图2.3.4 栈 a1为栈顶元素。进栈的顺序为a1，a-2，…，an-1，an；出栈的顺序为an，an-1，…，a2，a1.。 栈在CAD中应用很广，下面以子程序调用为例予以说明。 当调用子程序时，需存贮返回地址。设主程序MAIN运行时需调用子程序AI，在子程序AI处理完成后，要自动返回主程序的厂处。同样地在子程序AI执行过程中还要调用子程序A2，而A2又要调用于程序A3，故应分别存贮它们的相应返回地址s、t。 由于返回时是按调用它的相反次序退出，故这样的序列可用如图2.3. 5所示的栈来表示， 进入的序列是r、s、t，而退出的序列是t、s、r。  4．队列 队列的逻辑结构是一个两端打开的线性表，它限定只能在表的一端插入，在表的另一端删除。允许插入的一端称为队尾，允许删除的一端称为队头。这样，第一个进队的元素也将第一个出队，其工作方式是“先进先出”。它保证了处理次序与原来存贮的次序一致，这与栈正好相反。 队列的物理结构是在存贮器中开辟一个连续的存贮空间。须定义队列名、队列的最大容量，并设置队头指针(Front)和队尾指针(Rear)。如图2.3.6所示，前者是指队列当前队头元素位置，后者是指当前队尾元素位置。 a1 a2 … an-1 an   队头 队尾 图2.3.6 队列物理结构 图2.3.7表示向空队列中压人元素及出队全部元素的过程。队列与堆栈的一个很大区别是：堆栈是一端固定，另一端随元素的进栈和出栈而上下移动；而队列没有固定端，两端都可移动。 2．2．3 链表结构 堆钱和队列可以方便地插入和删除元素，但这种插入和删除仅限于在其端部进行。在CAD中，需经常在任意位置上做插入及删除元素的工作，此时需用键表结构。 链表结构中的元素不是简单的数据，而是由多个数据域组合而成的一个。结点＂。结点内的不同数据域中可以存放不同描述的数据记录。最简单的链表结构包含两个域；一个是数据域；另一个是链域，它用来存放指示它所链接的结点的地址指针，如图2.3.8所示。此时数据元素在逻辑结构上的相邻性不是靠连续的存贮地址来实现，而是靠每个结点的链指针来实现，这样就使元素的插入和删除非常灵活。 1．单向键表结构 在链表结构中，若只含有一个链域则称为单向链表结构。它是一种最简单的链表结构，图2.3.9表示其逻辑结构和物理结构，H是头指针，指出了链表中第一个结点存放的地址；“0”或“。”表示空指针，表明该结点后面没有后继结点。  在链表运算中，主要是访问、插入和删除操作。图2.3.10表示某M维图形，它由一个外线环与三个内线环组成。外线环由直线、圆弧段及列表点曲线组成，其中a、公为直线段(分别记录其起点及终点坐标)；b．d／及人为圆弧段(分别记录其起点、终点及国心坐标)；C及g为列表曲线(分别记录着若干个坐标点)。内线环分别由直线及圆弧段组成(也相应记录其坐标 点)。 图2.3.10所示的图形可用图2.3.11所示的数据结构表示。其中信息采用有层次的链表结构：第一层存放图形信息，第二层存放线环信息，第三层存放线段信息，第四层存放相应线段的几何信息。  图2.3.11 图2.3.10图形的数据结构 2．双向链表 单向链表的链域中只给出该结点的直接后继地址，无法求得某结点的前趋地址。为了克服这一缺陷，双向链表则在结点中再增加一个键域，用来存放该结点的前趋结点的地址。这样，一个结点就由三个域组成，一个数据域和两个键域，如图2.3.12所示，其中Llink及RLink域分别存放前趋结点及后继结点的地址指针。  图2.3.12 双向链表结构 双向链表可用来描述复杂的数据结构，例如机械的装配关系。图2.3.13为一种装配件的数据结构。  图2.3.13 装配件的数据结构 在这种数据结构中，引入了虚环概念。虚环包括待装配件的转换矩阵及装配特征等。 图2.3.14为容器装配例子。该容器由容器盖和容器座、螺栓装配而成。图上表示的是它们的装配关系。  图2.3.14 容器装配及其装配关系 在这个例子中，共有两种装配关系，即贴合装配及对准装配。贴合装配是指平面与平面之间的装配，如容器盖接触面风与容器座接触面风就是贴合装配；对准装配是指圆柱体与孔之间的装配，如容器盖中心线Cl与容器座中心线C；就是对准装配。 虚环包括如下内容；指向下一个虚环的指针；指向上层装配件或次装配件的指针；指向装配特征的首地址；指向次装配件或零件的指针；指示装配关系的编码等。这种数据结构使用户可以方便地通过交互方式插入或删除某些零件或次装配件，也可方便地修改各种属性。 2．2．4 树结构 树结构属于非线性结构，也称层次结构。CAD中描述一个形体拼合过程的CSG树就是树状结构(见图2.3.15)。  图2.3.15 实体拼合的CSG树 图2.3.16 树的逻辑结构 树是由一个结点或多个结点组合的有限集合｝。其中有一个称为根结点；其余结点被分为n＞0个互不相交的有限集合几，Ti，…，T。，而这些集合的每一个又都是一棵树，称为根的子树，图2.3. 16表示一棵树，A是根结点，它有三棵子树。 由于树的结点可能是多孩子的，故采用多重链表结构，即每一个结点除了数据域外还有多个键指针域，分别指向各个孩子的结点地址。每个结点中的链域数取决于该结点的度数明p子树数)，而且一般树结构中每个结点的度数不可能相同，这就使得同一棵树中各个结点的链域数不同，如图2.3.17所示。为统一存贮格式，常采用如图2.3.18所示的定长结点的链表结构。   图2.3.18 定长结点的链表结构 2．2．5 数据检索 研究数据结构的目的是当应用程序需要时能迅速检索到所需要的数据。对数据文件的主要操作有数据的检索、删除和修改等，其中数据的检索是最基本的操作。 如上所述，文件是由若干记录组成，而每个记录中又有若干数据项，这些数据项在记录中的地位是不同的，其中有的数据项可用来识别记录，通常称之为数据项的关键字。例如由表10．l所建立的数据文件，可以取型号数据项作为关键字来进行数据的检索，因为人们通常是根据它来确定联轴器的其他属性。由于结构上的原因，有时也可以用联轴器轴孔直径d作为关键字。 此外，还要选择合适的数据检索方法。目前常用的方法有线性检索法、折半检索法、概率检索法、索引检索法和散列法等，这些方法的目标是实现快速有效的检索。限于篇幅，下面仅以折半检索法为例。 折半检索法的基本思路是：如果表中所有的记录是按关键字递增(或递减对叵序排列，那么查找是从表的中间记录开始，而不是由表的某一端开始。根据所给定的要求将查找记录的关键字值工与中间记录关键宇值天比较，此时可能出现三种情况： ①若x<k，欲找记录必在表的上部； ②若x=k，则中间记录就是所要检索的记录； ③若x>k，欲找记录必在表的下部。 因此，经过一次比较，就可使表的长度缩短一半，反复进行，直至找到所要检索的数据。显然采用这种检索法要比从表的一端开始按顺序进行查找快得多。