机械CAD技术基础

1、 机械CAD 技术基础 第一章 慨述 本章介绍本章介绍CAD CAD 技术的发展现状、产品开发设计流程、技术的发展现状、产品开发设计流程、CAD CAD 工作工作内容和内容和CADCAD技术发展趋势。技术发展趋势。1 . 1 CAD 1 . 1 CAD 发展现状发展现状 计算机辅助设计（Computer Aided Design , CAD ）指利用电子计算机处理设计过程中的数字、字符和图形等数据。由于计算机运算速度快、精度高，长于信息存储和记忆，可以进行枯燥味的重复性工作，这些优点和设计人员的综合分析、形象思维和创造能力结合起来，形成最佳组合。使得产品的设计周期缩短，设计质量提高，设计成本降

2、低，从而提高了产品的市场竞争能力。 CAD 技术诞生于50 年代初期，四十多年来经历了形成、发展、提高和集成四个主要发展时期。 CAD 技术的应用普及水平成了衡量一个国家的科学技术现代化和工业现）代化的重要标志之一。 随着计算机技术的发展，CAD 技术几经更新，已从原来的简单辅助绘图 ( Drafting ) ，即二维绘图、尺寸标注，发展到辅助设计（ Design ）、数据管理) 、智能化、集成化的CAD / CAM 系统，CAD 技术经历了五代。l 第一代CAD 系统用于二维绘图、标注符号和尺寸。l 第二代CAD 系统可进行绘图及几何数据管理。l 第三代CAD 系统可进行三维图形描述，备有工

3、程计算和软件接口。这些工程分析软件包括优化设计、有限元分析、l 第四代CAO 系统以数据库为核心，是包括曲面造型和实体造型技术的集成系统。l 第五代CAD 系统则是智能化的CAO / CAM 集成系统。 CAD CAD一般应具备三个条件：一般应具备三个条件：1.有较完备的数据库；2.有较完备的程序库 包括： 数学方法库 优化设计库 有限元方法库 常用机械设计方法库 3. 交互式图形系统（包括硬件和软件） 包括 主机和各种输入/输出设备 图形支撑系统1.2 机械CAD技术应用 机械产品开发设计可大致分成： 概念设计：根据市场需求确定新产品的功能，给出新产品的概念性分析模型或草图。 初步设计：对概

4、念设计输出的结果进行方案分析比较，修正概念模型。 详细设计：这是产品的真正结构设计阶段。由概念模型和分析产生的数据对详细设计起着重要的指导作用，同时详细设计的结果也要进行必要的分析，并适时根据需要修改概念模型。目前的CAD 系统大都提供详细设计手段，而很少把它和概念设计及分析联系起来。 文档设计：各设计阶段都根据不同的需求产生相应的文档，以便从产品市场需求分析到开发、制造及销售能够有机地组织起来。 计算机可以不同程度地参与这四个阶段的工作，如图下图所示。除概念设计阶段计算机参与较少以外，在其它三个阶段中，CAD 的应用几乎是无所不在。CAD 系统在设计中承担的主要工作有数据处理、工程分析、图形

5、处理与动画仿真等。1.3 CAD1.3 CAD发展趋势发展趋势 以上介绍的CAD系统的概念模型已经使计算机在辅助人们在机械产品的机械设计方面所起的作用大大增强了，同时也对新一代机械CAD 系统的性能在很多方面提出了更高的要求。 多能化 智能化 集成化 标准化 网络化 另外，人工智能、网络技术、软件工程中面向对向的方法及工程数据库技术的发展也为CAD 技术的不断提高提供了强大的动力。现在，市场的发展使得制造业的竞争日益激烈，也为CAD 技术提出了更高的要求。 1.4 1.4 常见的常见的CADCAD软件软件 由于CAD应用巨大市场的存在，不仅传统的CAD软件开发公司不断推出自己的商品软件，许多新

6、兴的软件公司也加入了竞争的行列，涌现出来许多CAD软件开发企业 1.4.1 1.4.1 国外软件国外软件 国外一些CAD软件开发公司长期从事CAD方面技术的研究，其技术实力雄厚，市场占有率高。主要的CAD软件有: 1 1、 AutoCADAutoCAD AutoCAD是世界第四大PC软件公司Autodesk的主导产品，是当今优秀的二维绘图软件之一。他除具有强大的绘图、编辑等二维功能外(同时也具有简单的三维造型能力)，还提供AutoLisp, ADS, ARX,VBA等二次开发的工具，在不少行业(如机械、建筑、电子等)得到开发应用。AutoCAD于80年代进入我国，得到了广泛的应用，在各行业的影

7、响较大。 2 2、 UnigraphicsUnigraphics (UG) (UG) UG是Unigraphics Solutions公司的产品，其特点是将优越的参数化和变量化技术与传统的实体、线框和曲面结合在一起。UG是从二维绘图、数控加工编程、曲面造型等功能发展起来的软件。1997年Unigraphics Solutions公司合并了Intergragh公司的机械CAD产品，将微机版的Sold Edge软件统一到Parasolid平台上。由此形成了一个从低端到高端，兼容Windows NT微机版的较完善的CAD/CAE/CAM/PDM集成系统。 3 3、 Solid EdgeSolid E

8、dge Sold Edge是基于参数和特征实体造型的机械设计CAD系统，他运用强大的设计指引工具在全三维参数化几何造型环境中方便地构建机械零件和装配，是最早的应用实体造型系统。 4 4 、 Pro/Engineer Pro/Engineer Pro/E系统是美国参数技术公司(Parametric Technology Corporation，简称PTC)的产品。PTC公司提出的单一数据库、参数化、基于特征、全相关的概念改变了机械CAD/CAM/CAE的传统观念，这种全新的概念以成为当今世界机械CAD/CAMICAE领域的新标准。利用该概念开发出来的第三代机械CAD/CAM/CAE产品Pro/E

9、ngineer软件能将从设计到生产全过程集成到一起，让所有的用户能同时进行同一产品的设计制造工作，即所谓的并行工程。 5 5、 I-DEASI-DEAS I-DEAS是美国SDRC公司的产品，是全世界制造业广泛应用的大型CAD/CAMICAE软件。SDRC提出了一种比参数化技术更先进的实体造型技术一变量化技术，这成为CAD软件今后发展的方向。他以极高的效率，在单一数字模型中从产品设计、仿真分析、测试直到数控加工的产品研发全过程。 6 6、 SolidWorksSolidWorks SolidWorks的建模核心是基于Windows的CAD/CAM/CAE/PDM桌面集成系统，他是在总结和继承了

10、大型机械CAD软件的基础上，在Windows环境下实现的第一个机械CAD软件。SolidWorks软件是面向产品级的机械设计工具，他全面采用非全约束的特征建模技术。 SolidWorks的全相关技术使得零部件之间和零部件与图纸之间的更新完全同步;SolidWorks能自动进行动态约束检查，具有强劲复杂曲面造型能力，能设计表面形状复杂的曲面零件;SolidWorks既可以先设计立体的钣金零件,也可以按零件的平面展开图进行设计。由于以上特点，SolidWorks成为目前微机平台上的主流三维设计软件。 7 7、 CATIACATIA CATIA是法国Dassault System公司的CAD/CAE

11、/CAM一体化软件，居世界CAD/CAE/CAM领域的领导地位，广泛应用于航空航天、汽车制造、造船、机械制造、电子、电器、消费品行业，它的集成解决方案覆盖所有的产品设计与制造领域，其特有的DMZJ电子样机模块功能及混合建模技术更是推动着企业竞争力和生产力的提高。CATIA提供方便的解决方案，迎合所有工业领域的大、中、小型企业需要。包括:从大型的波音747飞机、火箭发动机到化妆品的包装盒，几乎涵盖了所有的制造业产品。在世界上有超过13,000的用户选择了CATIA。 CATIA源于航空航天业，但其强大的功能以得到各行业的认可，在欧洲汽车业，己成为事实上的标准。CATIA的著名用户包括波音、克莱斯

12、勒、宝马、奔驰等一大批知名企业。其用户群体在世界制造业中具有举足轻重的地位。波音飞机公司使用CATIA完成了整个波音777的电子装配，创造了业界的一个奇迹，从而也确定了CATIA在CAD/CAE/CAM行业内的领先地位。 1.4.2 1.4.2 国内软件国内软件 为了摆脱国外CAD软件的长期垄断，在CAD软件市场占有一席之地，国内也涌现出了一批CAD软件开发企业，其软件产品主要有: 1 1、 高华高华CADCAD 高华CAD是由北京高华计算机有限公司推出的CAD产品。主要高华CAD是由北京高华计算机有限公司推出的CAD产品。主要包括计算机辅助绘图支撑系统GHDrafting、机械设计及绘图系统

13、GHIvmS、工艺设计系统GHCAPP、三维几何造型系统GHGEMS、产品设计管理系统GHPDMS及自动数控编程系统GHCAM 。 2 2、 CAXACAXA电子图板电子图板 CAXA电子图板是北京北航海尔软件有限公司的产品。他包括零件图、装配图、工艺图表、平面包装等方面的辅助设计系统。适合所有需要二维设计的场合。 3 3、 开目开目CADCAD 开目CAD是华中理工大学开发的CAD和图纸管理软件，他面向工程实际，模拟人的设计绘图思想，操作简便，机械绘图效率较AutoCAD有明显提高。开目CAD支持多种几何约束种类及多视图同时驱动，具有局部参数化的功能，能够处理设计中的过约束和欠约束的情况。

14、第2章 计算机辅助设计系统 CAD 系统包括硬件系统和软件系统两大部分。 硬件系统是计算机辅助设计技术的物质基础。 软件系统是计算机辅助设计技术的核心，它决定了系统所具有的功能。2.1 CAD 系统的构成与分类 2.1.1 CAD系统的分类 从硬件角度将CAD 系统划分为四类。 主机系统 小型机系统 微型机系统 工作站系统 2.1.2 CAD系统的类型 从软件上分CAD系统有许多形式，按系统的工作方式及功能大致可以分为三种： 检索型 自动型 交互型 智能型2.1.3 网络结构 CAD 系统的网络时常采用局域网，网上设备通过传输媒介相互传送信息。常见形式有三种： 1.星型网。网的中心是一台计算机

15、，也称服务器，一般采用大中型机或超级小型机，周围是若干无外存的工作站，也称无盘结点。星型网的优点是所有网上用户均能使用中心计算机上的数据库；缺点是一旦中心计算机出故障，则整个系统不能工作。 2 环型网：适用于工程工作站或微机连网。它的优点是网内用户能共享任一结点上的数据库或文件；此外当某结点发生故障时，其余结点可照常工作。 3.总线型：适用于将差别较大的设备连入网中。公共总线可长达2.5km，可接1024 个设备，不够时，用中继线再接一条，形成分叉的树形结构。以太网就是一种有名的总线网，在以太网上可以连接各种不同类型的工程工作站、微机、外设及终端等。 还可将不同类型的局域网组合成复杂的网络，例

16、如将环型网接到总线网上，如下图所示。 网络性能的好坏要看它的传输速度，它所支持的操作系统，以及用什么样的网络协议。所谓网络协议就是网上传输信息时所用的格式，必须采用标准的网络协议，最常用的就是TCP / IP 协议，它能支持各种操作系统，如UNIX、VMS 及Ms_Dos 。在TCP / IP 基础上制定的网络文件系统（NFS ）协议可使网络内用户具有透明的文件共享功能，可使不同结构、不同操作系统共同工作。 2.2 CAD 系统的硬件组成 CAD 系统的硬件一般由计算机主机、常用外围设备、图形输入设备和图形输出设备组成。图形输入和输出设备种类很多，可根据需要进行选配。现代CAD 系统均为交互系

17、统，交互是靠用户操作图形输入设备来实现的。下图表示了一个CAD 系统的基本组成。 2.2.2 图形输入设备l鼠标l数字化仪l扫描仪2.2.3 图形显示设备 l光栅扫描显示器l液晶显示器2.2.4 绘图输出设备 l打印机 l针式打印机l激光打印机l喷墨打印机l笔式绘图仪l平板式绘图机l滚筒式绘图机l喷墨绘图机 2.3 CAD系统的软件组成 CAD 系统应具备两类软件，即系统软件与应用软件。应用软件的范围很广，可分为CAD 支撑软件及用户开发的应用软件两种，前一种一般在市场上可以买到，后一种则需用户开发，右图表示了这些软件间的层次关系。 系统软件指操作系统及语言等，它们不是用户的具体应用程序，而是

18、着眼于计算机资源的有效管理，用户任务的有效完成，以及操作的方便，目的是要构成一个良好的软件工作环境，供应用程序的开发使用，包括以下软件。1 操作系统（0S : operaing，System ) 具有五方面的管理功能，即内存分配管理、文件管理、外部设备管理、作业管理及中断管理。目前最常见的是多用户、多任务操作系统UNIX ，已成为事实上的工业标准，从工作站到微机均有使用，它在微机上的变种 XENIX , ONIX 及VENIX 等。微机上使用最多的要数 MS一DOS 、WINDOWS 。再有一种虚拟存储操作系统VMS ，大都在DEC公司的VAX计算机上使用。 2 计算机语言 汇编语言是一种与计

19、算机硬件相关的符号指令。汇编语言属低级语言，执行速度快，能充分发挥硬件功能，常用来编制最底层绘图功能，如画点、画线等。此外当涉及到硬件设备时，如编制驱动程序时，也往往用它 另一类称高级语言，与自然语言比较接近，所编程序与具体计算机无关，经编译及与有关为连接后即可执行。目前有许多语言，而且还在发展，用得较广的有BAsic 、FORTRAN 、PASCAL 、C 等，特别是C 语言的使用正变得越来越普遍，并发展为面向对象的C + 。在人工智能方面用得较多的语言有LISP 、Prolog 等。 3.窗口系统 有以下特点:l采用位图形图标、窗口、菜单、按钮等界面组成部分。l用鼠标移动光标，直接指点图形

20、对象完成各种操作。l用户可根据个人喜爱对界面进行裁剪和定制。l出错保护与强有力的学习指示功能（Help 功能）。l提供强有力开发工具，使用户的应用纳入它的环境中。 窗口系统的结构层次如图所示。 4网络通信及管理软件 现在CAD 系统都是联网系统，用户能共享网内全部硬软件资源，可以使工作小组共同进行某个产品的辅助设计或开发同一软件系统。为了使网络中信息交换能正常有效地进行，一般都分层次规定了双方通信的约定，称为协议。目前，这种层次型网络协议已逐步达到了标准化，国际标准的网络协议方案为“开放系统网络标准模式”( OSI），它分为七层，即应用层、表达层、会话层、传送层、网络层、链路层和物理层。以太网

21、（Ethernet ）是国际著名的局域网络之一，它的结构功能分层完全和OSI 模式相对应，工作可靠，易于扩充，所以被广泛采用。 Cad支撑软件l工程数据库l图形软件 包括： 图形支撑系统（图形开发工具） 应用图形库l计算方法库 包括： 常用数学方法库 常用机械设计方法库 有限元分析方法库第3章CAD 常用的数据结构本章介绍CAD 常用的数据结构，包括数组、栈、队、链表、树和图。 3.1 基木概念1数据：数据是指用来描述客观事物的、能输入到计算机中并被计算机接受和处理的各种字符、数字的集合。2数据元素：数据元素是数据的基本单位，是数据这个集合的一个个体。常把数据元素称为记录，而含用大量记录的线性

22、表称为文件。3. 数据的逻辑结构：通常所说的数据结构一般是指数据的逻辑结构。数据的逻辑结构仅考虑数据之间的逻辑关系，它独立于数据的存储介质。4数据的物理结构：数据的物理结沟也称存储结构，是数据结构在计算机中的映象。计算机处理信息的最小单位叫作位（bit ) ，一个位表示一个二进制的数，若干位组合起来形成一个位串。用一个位串表示一个数据元素，称这个位串为一个结点，结点是数据元素在计算机中的映象。映象的方法不同，数据元素在计算机中的存储结构也不同，顺序映象得到顺序的存储结构，非顺序映象得到非顺序的存储结构，也称链式存储结构。5数据类型：数据类型是程序设计语言允许变量的种类。 3.2 线性表 线性表

23、结构是一种最常用的数据结构形式，包括向量、数组、栈、队列和链表。 3.2.1 线性表的逻辑结构 线性表是一种最常用且最简单的数据结构，是n个数据元素的有限序列( a1， a2， a3，ai-1， ai， ai+1，, an) 数据元素“ai” 可以是一个数，可以是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。线性表具有以下特点：l 线性表是数据元素的一个有限序列。l 线性表中数据元素的个数定义为线性表的长度n ，当n 二O 时，为空表。l 数据元素在线性表的位置取决于它们自己的序号，数据元素之间的相对位置是线性的，如a1是第一个元素， an 是最后一个元素。l 除了第一个和最后一个数据

24、元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。当1 i n 时， ai 的前一个元素ai-1 是它的直接前趋， ai的后一个元素ai+1是它的直接后继。 3.2.2 线性表的存储结构1 线性表的顺序存储结构 顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放。一般情况下，线性表是按照数据元素的逻辑顺序依次存放的，即按顺序分配的原则，用一组连续的存储单元依次存储各个元素。数据元素在存储器中的存放地址和该元素的下标一一对应。假定一个线性表A(n)，它的每个数据元素占1个存储单元，第一个数据元素在内存中的开始地址为L(al)，那么，第i个数据元素的存储位置为 L(ai

25、) =L(a1)+(i-l)l 线性表的顺序存储结构如图所示，图中b=L(al）。 线性表的顺序存储结构具有以下特点；l 有序性：各数据元素之间的存储顺序与逻辑顺序一致。l 均匀性：每个数据元素所占存储空间的长度是相等的。线性表在顺序存储结构中是均匀有序的，只要知道线性表的首地址和数据元素的序号，就能知道它的实际地址。因此对表中数据元素进行的访问、修改运算速度快。在删除或插入运算时，必须进行大量数据元素的移动，增加运算时间。因此，这种存储结构多用于查找频繁、很少增删的场合，如工程手册中的数表。向量、数组、栈、队列等属于顺序存储结构。 2 线性表的链式存储结沟 用一组任意的存储单元存放表中的数据

26、元素。由于存储单元可以是不连续的，因此为了表示表中元素的逻辑关系，除了存储元素本身的信息之外，还要存储这个元素直接后继或直接前趋的存储位置。这两种信息组成数据元素的存储映象，称为结点。结点包括两种域，存放数据元素本身的域称为数据域，存储直接后继或直接前趋地址指针的域称为指针域。如图所示。 在链式存储结构中，数据元素在逻辑结构上的相邻性不是靠连续的存储地址来保证，而是靠每个结点的链指针。在这种存储结构中，元素的插入和删除操作非常容易。 单向链表和双向链表属于链式存储结构。 3.2.3 数组 几乎所有的程序设计语言都把数组作为固有数据类型。数组可以看成是线性表的扩充，数组的存储也采用顺序分配的原则

27、。 我们可以用数组来顺序地表示线性表，线性表是一个一维表，数组与线性表不同的是，数组可以是多维的。如A(i),B(i,j),C(j1,j2,.，jn）都可以表示一个数组，括号内的i,j，j1,j2,.，jn称为数组下标,下标的个数表明数组的维数，下标数值表明该维的长度。A(4）是一维数组，数组长度为4；B(3,5）是二维数组，第一维长度为3，第二维长度为5 。前面的C(j1,j2,.，jn）则是n维数组。当n=1 时，n 维数组C(j1,j2,.，jn）退化为一维数组。 3.2.4 栈 1栈的逻辑结构 栈也是线性表，它与普通线性表的区别就在于对它的运算仅限定在表尾。 假定栈S（a1，a2， a

28、n)， a1称为栈底元素， an，为栈顶元素。进栈的顺序是a1，a2， ，an。出栈的顺序是an， an-1， ， a1。它的显著特点是后进先出，如图所示。2栈的存储结构 顺序存储或链式存储都可以作为栈的存储结构。但由于栈的容量一般是可以预见的，而且运算仅限于栈顶，所以通常采用顺序存储作为栈的存储结构。3栈的运算(1）建立一个栈 栈的存储结构用数组sn。设m为栈的上界，则在C 语言中，由于第1 个数组元素是s0，所以栈的上界m等于n-1。设一栈顶指针为TOP ，它不必指向数据元素的实际地址，只记录数据元素的逻辑序号即可。当元素尚未进栈时，令top等于-1。 ( 2 ）进栈 如果有元素进栈，首先

29、检查栈顶指针TOP ，如果TOP 等于In ，表示栈满，显示出错信息，否则将发生上溢。如果TOP m ，令ToP = ToP + 1 ，将该元素赋给s ToP 。( 3 ）出栈出栈即取走栈顶元素。首先检查栈顶指针TOP ，如果TOP 二一，表示栈空，显示出错信息，否则将发生下溢。如果TOP 一1 ，出栈元素为。 TOP , 然后令TOP 二TOP 一1 。出入栈操作如图所示。4 栈的应用举例栈是一种应用很广的数据结构。例如在交互式图形系统中，将显示区域存入栈中，需要时可以恢复前几次的显示状态。用栈存放每次操作的命令，可以恢复到前几个命令时的状态。在计算机语言编译系统中，栈是一个非常重要的数据结

30、构。3.2.5 队列 队列是两端开口的线性表，队列只限定在表的一端进行插入操作，在表的另一端进行删除操作。允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”。如图所示， a1 是队头元素，an 是队尾元素，队列中元素以a1, a3, a3, an的次序入队，也以同样的次序出队，其工作方式是先进先出，与栈的工作方式刚好相反。 在对队列进行运算时，由于队列的两端均可浮动，因此，需要设立两个指针，分别指向队头（Front）和队尾（Rear）。这里规定指针Front 总是指向实际队头的前一位置，而指针Rear 指向队尾元素。 显然，当Rear =O 或Front=Rear 时，队

31、列为空；当Rear 等于上界时，队列满。队列的主要运算是入队和出队。入队时，队尾指针加1 ；出队时，队头指针加1 。 计算机程序设计中经常用到队列结构。最典型的例子是操作系统中的作业排队，当系统中有多道程序运行时，可能同时有几个作业的运行结果需要通过通道输出，这就要按申请的先后次序排队。申请输出的作业从队尾进行队列，当通道传输完一个作业，要接受一个新作业时，队头的作业先从队列中退出输出操作。 3.2.6 单向链表 从性质上说，单向链表结构仍然属于线性表，但表中的元素已不再是简单的一个数据元素或是只包含多个相同类型数据的记录，而是由多个数据域（至少有一个）和一个指针域组成。在单向链表中，结点只有

32、一个指针域，通常存放直接后继的地址。在顺序存储的线性表中，数组名即为线性表的首地址，也是表的第一个数据元素的地址。在链式存储的线性表中，一般不建数组，所以第一个元素的地址需要专门存放在某指针型变量的存储单元中。通常设置一个与链表结点相同的一个结点，它的指针域存放第一个元素的地址，数据域可以是空的，也可以存放表长等其他信息，该结点通常称为链头结点。单链表的最后一个结点的指针域是空的。 1建立单向链表 假定线性表为（A , B , C , D , E )，将其按单向链表存储。 首先定义结点的数据类型，它有两个成员；data 和nextPt。data 是用来存放数据元素本身，所以它应该是字符型的。n

33、extPt存放该结点的直接后继的地址，所以它应该是指针型的，而且应该是指向字符型数据的指针。链表不必事先指定它的长度，可以根据需要动态地申请存储空间，整个链表的长度可存放在存储第一个数据元素地址的结点即链头结点h的数据域或某一变量中。单向链表的结点结构如下：struct slink char date； struct slink *nextPtr; 2访问 链表中数据元素的存储顺序与逻辑顺序无关。如果访问第i个元素，首先通过链头结点h 找到第一个结点的指针域找到第二个结点； 直至找到第i 个结点，即可访问该结点的数据域。3修改 修改第i 个元素的值，将第i 个数据元素的值改为M 。首先找到该结

34、点，然后修改这个结点的数据域。在程序中进行如下操作：node 一data=M 即可。 4删除 若删除第i个元素M，则要找到第i-1和第i个结点，并将第i-1个结点的指针域中第i个结点的地址改为第1+1个结点的地址，最后释放第i个结点所占的存储空间。删除操作示意图。5插入 在第i 个数据元素之前插入一个数值为M的元素，首先要在该元素前申请一个新结点作为存储空间，在新结点的数据域存放数值M,再找到第i-1个结点，令新结点指针域的指针等于第i-1 个结点指针域的指针，修改第i-1 个结点的指针，让其存放这个新结点的地址。即让第i-1 个结点指向新结点，而新结点指向第i 个结点即可。插入操作示意图。

35、3.2.7 双向链表 每个结点域增加一个指针域，用来存放结点的直接前趋地址。即第i个结点的指针域存放第i-1个结点的地址。由于第1个结点没有直接前趋，它的指向直接前趋的指针域是空的。同样最后一个结点没有直接后继，该结点指向其直接后继的指针域也是空的。一般再设置一个链尾结点，在它指向直接前趋的指针域存放最后一个结点的地址。 假定线性表为（A , B , C , D , E ) ，将其按双向链表存储，并进行访问、修改、删除和插入的运算。 (1）建立双向链表 首先要定义结点的数据类型，它有3 个成员，data 、nextPtr 和prePtr 。data 用来存放数据元素的数值，nextPtr 用来

36、存放结点直接后继的地址，PrePtr存放结点直接前趋的地址。head 和rear 分别为链头和链尾结点。双向链表的结点结构如下：struct dlink char date : struct dlink *prePtr Struct dlink *nextPtr (2）访问 双向链表可以像单向链表那样从链头结点h开始找到第i个结点，还可以从链尾结点开始找到后起的第j 个结点。 (3）修改 若修改第i个结点的值，首先找到这个结点，然后修改该结点的数据域即可。(4）删除 删除第i个数据元素，涉及第i-1,i,i+1三个结点。将结点i-1的指针域nextPtr存放结点i指针域nextPtr 的内容，

37、将结点i+1的指针域prePtr存放结点i指针域PrePtr的内容。然后释放结点i所占的存储空间。删除操作示意图。 (5)插入 若在第i个数据元素前插入一个新的数据元素，首先为该元素申请存储空间，得到一个新结点。这个新结点的数据域存放该元素的值。再找到第i-1个和第i个结点；新结点的指针域nextPtr，存放第i-1个结点的指针域nextPtr 的内容，指针域prePtr存放第i个结点指针域prePtr的内容；结点i-1 的指针域和结点i指针域存放新结点的地址。插入择作示章图。 3.2.8 循环链表 单向链表只给出结点的直接后继，无法求得某结点的前趋。单向链表最后一个结点的指针域是空的，如果将

38、其存放第一个结点的地址就形成了循环链表，如图所示。 在循环链表中，从任一结点出发可以达到表中所有的结点，从而克服了单向链表不能访问其前趋结点的缺点。如果将双向链表的最后一个结点的指针域存放第一个结点的地址，同时将第一个结点的指针域存放最后一个结点的地址就形成了双向循环链表，如图所示。 循环链表构成一个环，因此从表中任一结点出发均可找到其它结点。 3.3 树与二又树 树结构也是一类非常重要的数据结构，它是非线性的。但树结构的数据元素之间存在明显的层次和嵌套关系。很多事物都可以用树来描述，如家族祖谱、行政组织机构等。树可分为一般树和分支固定的树，除了二叉树之外，四叉树和八叉树也都有非常重要的应用。

39、3.3.1 树的逻辑结构 树是由一个或一个以上结点组成的有限集T，其中一个结点称为根，其余结点可分为若干个互不相交的有限集T1，T2，T3 ,Tn,每一个集合本身又是一棵树，称为根的子树。可见，树结构是一个递归定义。下图为树的逻辑结构。 现在，结合图所示的树结构，介绍下面一些基本术语。这是一个拥有12个结点的树结构，它们是A,B，L，其中A结点是树根，称为根结点；从图中可以明显地看出，除根结点外，每个结点有且仅有一个直接前趋。l结点的度：结点的孩子（子树）的数量称为度。l树的度：树中所有结点中最大的度数称为这个树的度数。上图所示的树，其度数为4.l根结点：没有直接前趋的结点，A为根结点。l分支

40、结点：度不为0的结点，或者有直接后继的结点。如结点B,F,O,J。每个分支结点可以有不只一个直接后继。l 叶结点：没有直接后继的结点，或者说度为O 的结点。如结点E,K,G，H，C,I,L都是树叶，称终端结点。l 双亲：结点的直接前趋称为该结点的双亲。如A是B 的双亲。l 孩子：结点的直接后继称为该结点的孩子。如B是A 的孩子。l 兄弟：同一双亲的孩子间称为兄弟。如E,F,G，H。l堂兄弟：双亲在同一层的结点互为堂兄弟。如G与I ,J互为堂兄弟。l深度：树的最大层次数量称为树的深度或高度，图示的树，其深度为4。l相先：从根到该结点所经的所有结点都是该结点的祖先。如结点L的祖先是A,D,J结点。

41、l子孙：以该结点为根的子树中的任一结点都是该结点的子孙。如I,J,L是O的子孙，结点A的子孙则是树中其余的11 个结点。l边：结点间的连线。3.3.2 树的存储结构 由于树的逻辑结构为非线性的，所以只能用链式作为它的存储结构。可采用定长或不定长两种方式描述树的结点。1定长方式 以最大度数结点的结构作为该树的所有结点的结构，如图所示，每个结点都有n个子树域。如图所示的树用定长结点作为它的存储结构，如图所示。定长存储结构 2不定长方式 每个结点增加一个存放度数的域，结点长度随着度数不同而不同，如图所示。采用不定长结点表示图所示的树，如图所示。 定长方式存储中，所有的结点是同构的，运算方便，但浪费一

42、定空间。而在不定长方式存储中，可节省一些空间，但运算不方便。在计算机中数据的表示总是有序的，树结构在计算机内的表示也隐含着一种确定的相对次序，因此，树结构中的各子树之间的相对位置也是确定的，如果交换同一层次各子树的位置就构成了不同的树。如图所示为两棵不同的树。 3.3.3 二叉树的逻辑结构1 定义 二叉树是树结构的一种，但不同于一般树结构，即每个结点至多有两棵子树，并有左右之分，不能颠倒，二叉树可以是空的，一般树则至少有一个结点。二叉树的深度和度的定义与树一致。二叉树的五种基本形态如图所示。 2特殊二叉树(1） 深度为k的有2K-l个结点的二叉树称为满二叉树，如图a所示。 (2）深度为k，结点

43、为n的二叉树，它从1到n 的标号如果与深度为k的满二叉树的标号一致，就称为顺序二叉树，如图b 所示。(3）结点的度数或者为零，或者为2 的二叉树称为完全二叉树，如图a ,图C。 3.3.4 二叉树的存储结构 对于满二叉树的存储结构，可采用顺序存储。如果i =1，此结点是根结点。如果i=k，K/2是结点i的双亲结点，2k是i的左孩子，2k+1是i的右孩子。这种存储结构的特点是节省空间，可以利用公式随机地访问每个结点和它的双亲及左右孩子，但不便删除或插入运算，如图所示。 对于一般二叉树，通常采用多重链表结构，每个结点设三个域：数据域存放结点的值，左子树域存放左子树的地址，右子树域存放右子树的地址，

44、如图所示。这种存储结构会浪费一些存储空间，但便于删除或插入运算。 3.3.5 二又树的遍历 遍历二叉树是指按一定规律走遍二叉树的每个结点，每个结点访问一次且只访问一次。即按一定规则将二叉树的所有结点排列成一个线性序列。由于二叉树是由根结点、左子树、右子树三个基本单元组成的，因此，依次遍厉这三部分信息，就可以遍历整个二叉树了。 根据根结点、左子树、右子树三者不同的先后次序，有6种遍历二叉树的方案。即l 根结点、左子树、右子树l 左子树、根结点、右子树、l 左子树、右子树、根结点l 根结点、右子树、左子树l 右子树、根结点、左子树l 右子树、左子树、根结点前三种是按先左后右的次序，属于常用的遍历方

45、式。 1 先根遍历 先根遍历的次序是：先访问根结点，再访问左子树，最后访问右子树。如图所示。 2中根遍历 中根遍历如图所示。先访问左子树，再访问根结点，最后访问右子树。 3后根遍历 后根遍历的次序是：先访问左子树，再访问右子树，最后访问根结点，如图所示。 3.3.6 树的二叉树表示 用二叉树表示一般树可以节省存储空间，一般树转换为二叉树的规则是：l树的根结点为二叉树的根结点；l保留根结点的孩子（从左到右）第一个孩子作为二叉树的左子树；l根结点的其余孩子作为该左子树的右子树（与左子树原属于兄弟关系，现变为父子关系）。 将图所示的一般树转换为二叉树的过程如图所示： 1保留每个结点与最左孩子的边，去

46、掉其余各边。 2连接同一双亲的所有兄弟。 3以树根结点为轴心，将整棵树顺时针旋转45。即可得到转换后的二叉树。3.3.7 二叉树应用举例 三维立体造型的CSG 树 一个复杂的形体可以看作由一些比较简单的形体经过交、并、差运算形成的。二叉树可以描述复杂形体这一形成过程，因此，这样的树也可称做CSG 树。图a给出一个复杂形体的形成过程，该过程也可以用图b 的CSG 树来描述，从图中可以看出，这是一棵二叉树，树叶结点是构成这个复杂形体的各个简单形体，其余结点描述了对它的左右子树的运算种类，经过三层五次运算，就得到了这个复杂形体。 第4章 设计资料处理 在机械设计过程中，往往需要从有关的工程手册或设计

47、规范中查找各种系数或数据 传统方法：设计人员手工查取，费时、繁琐 现代设计方法：计算机处理 中心问题在：如何将这种人工查找转变成在CAD进程中的高效、快速处理。 两种处理方法: 程序化 在应用程序内部对这些数表数表及线图线图进行查表、处理或计算。处理方法有两种：u第一种将数表中的数据或线图经离散化后存入一维、二维或三维数组，用查表、插值等方法检索所需数据；u第二种将数表或线图拟合成公式，编入程序计算出所需数据 数据库存储 u将数表及线图(经离散化)中的数据按数据库的规定进行文件结构化，存放在数据库中。如确定字段名、字段类型、字段宽度等u数据独立于应用程序，又能为所有应用程序提供服务，这是大规模

48、工程数据的主要处理方法。（需借助专业的数据库管理系统）4.1 设计数表的计算机处理例1：一维数组 只有一个自变量，即型号，定义一个整型变量 i 代表型号。定义4个一维数组。程序实现：例2：二维数组 决定工况系数KA值时有两个自变量，即原动机的载荷特性和工作机的载荷特性，各有三种情况。程序实现：floatfloat例3： 函数数表 查的的包角可能不会正好是表中所列的值应调用一元函数插值求解如=95，K2=?例4：函数数表2 表中D/d及r/d值在一定范围内是随机的，必须采用二元函数插值。实际编程时，设已知D, d, r，在定义二维数组AA610,调用二元插值函数，即可求得应力集中系数a 。 r/

49、d=0.2, D/d=1.10 a=AA47=1.34 r/d=0.22, D/d=1.15 a =? a4.2 设计线图的计算机处理 在工程设计中，时常遇到一些线图供查找系数或参数等使用，如齿轮传动的动裁荷系数 有些还以曲线族的形式给出，例如根据齿轮在轴上不同的布置方式，根据齿宽系数查找齿向载荷系数的一族曲线。 线图的计算机处理方法 最好找到线图原来的公式，将公式编入程序,这是最精确的程序化处理办法。并非所有的线图都存在着原来的公式，即使有也难找到。 解决办法：解决办法：将线图转换成相应的数表数表中没有的节点值采取插值法求得将线图公式化线图的处理1数表化处理过程处理过程1.线图转换为数表2.

50、编制程序处理数表齿向载荷分布系数的数表化线图的处理2公式化齿轮传动的动裁荷系数kv值的线图 1）直角坐标系线图在b图中标有“7”级精度的直线上取两点， 如x1=2, y1=1.09, x2=10, y2= 1.47 代入两点式直线方程 121211xxyyxxyy整理得 即1047. 0 xy1)100/047. 0(1vzKv2）对数坐标系线图普通v带选型图 对于图中的80100A直线段，取其上两点的坐标， x1 = 1, y1 =102.3139206 和 x2 = 6.3,y2 = 1600 代人下列两点式直线方程 121211lglglglglglglglgxxyyxxyy经整理后得

51、1137. 13139. 21137. 13139. 210)10lg(lgxyxy1137. 13139. 2110cPn 即 4.3 常用设计数据处理方法一、列表函数插值1. 一元列表函数的插值l 线性插值l 抛物线插值2. 二元列表函数的插值l 直线直线插值l 抛物线直线插值l 抛物线抛物线插值二、列表函数公式化插值定义 定义：定义： 设函数设函数y=f(x)在区间在区间【a,b】上有定义，且上有定义，且已知在点已知在点a= x0 x1xn=b上的值上的值y0, y1, , yn, 若存在一个简单的函数若存在一个简单的函数p(x), 使使 p(xi)=yi (i=0,1,2,n)成立，就

52、称成立，就称p(x) 为为f(x)的插值函数。的插值函数。采用多项式插值时次数采用多项式插值时次数 m = n 整体插值误差大！因此常采用整体插值误差大！因此常采用分段插值方法分段插值方法4.3.1一元列表函数插值设有一用数据表格给出的列表函数y=f(x)由于列表函数只能给出结点x1，x2，xn处的函数值y1，y2，yn，当自变量为结点的中间值时，就要用插值法求取其函数值。插值法的基本思想：在插值点附近选取几个合适结点，过这些点构造一简单函数g(x)，在此区间用g(x) 的值来代替原函数f(x)，因此插值的本质问题是如何构造一个简单且精度足够的函数g(x)。插值方法很多，在此主要介绍线性插值和

53、二次插值。线性插值步骤1.从一维列表中选取两个邻近的自变量x1和x2,并满足x1xx22.用过A、B两点的直线g(x)代替原有函数f(x)，则由解析几何可写出对称式直线方程的表达式为3.记 整理得 21211212121211)()(yxxxxyxxxxxgxxyyxxyxg2121)(xxxxxA1212)(xxxxxA2211)()()(yxAyxAxg一维线性插值/p.x已知，求p.ybool GetValue_Line1(const point p1, const point p2, point& p) if(p.x p2.x) /? return false; double

54、A1x = (p.x p2.x)/(p1.x p2.x); double A2x = (p.x p1.x)/(p2.x p1.x); p.y = A1x*p1.y + A2x*p2.y; return true;抛物线插值（1） 插值多项式)()()()()()()()()()()()()(231321332123123121321332211xxxxxxxxxAxxxxxxxxxAxxxxxxxxxAyxAyxAyxAxg 几何解释 用通过三点(x1,y1)、(x2,y2)、(x3,y3)所作得抛物线g(x)来近似替代(或逼近)原有函数f(x)抛物线插值（2） 选取三个合适的插值点 原则选取

55、得三个插值点与待求得插值点临近 步骤211111;,. 2:. 1iidiiddiididiiixxxxxxxxxxxxxxx否则，第三点取则第三点取的值，若和比较，并满足下列条件和从一维表中选取两点211iidiixxxxx一维抛物线插值/p.x已知，求p.y bool GetValue_Parabola1(const point p1, const point p2, const point p3, point& p) /或const point3, point &p if(p.x p3.x) /? return false; double A1x = (p.x p2.x)

56、*(p.x p3.x)/(p1.x p2.x)*(p1.x p3.x); double A2x = (p.x p1.x)*(p.x p3.x)/(p2.x p1.x)*(p2.x p3.x); double A3x = (p.x p2.x)*(p.x p1.x)/(p3.x p2.x)*(p3.x p1.x);p.y = A1x*p1.y + A2x*p2.y + A3x*p3.y; return true;4.3.2二元列表函数的插值在三维空间选定几个点，通过这些点构造一块曲面g(x,y)，用它近似的表示在这块区间内原有的曲面f(x,y)直线直线插值（即双线性插值）插值步骤如下 根据k点的(

57、xk,yk)找出周围四个点a,b,c,d，并且有以下关系式：xa = xc ; xb = xdya = yb ; yc = ydxa xk xb ; ya yk yc 找出对应于a,b,c,d的A,B,C,D，过A、B用线性插值求得点E，再过C、D用线性插值求得F点。 过E、F 再用线性插值求得K点，此即为所求。 抛物线直线插值插值步骤如下 根据k点的(xk,yk)找出周围四个点a,b,c,d，并根据抛物线插值中的取点方法增加2个点，如图增加e、f二个点，这样共得六个点， 找出对应上述六个点的A,B,C,D,E,F，过A、B、E用抛物线插值求得点U，再过C、D、F用抛物线插值求得V点。 过U、

58、V再用线性插值求得K点，此即为所求。 抛物线-线性插值bool GetValue_ParaLine(const point3D pABE3, const point3D pCDF3, point3D & p) /p.x, p.y已知，求已知，求p.z if(p.x pABE2.x) /检查检查x是否越界是否越界 return false; if(p.y pCDF0.y) /检查检查y是否越界是否越界 return false; point pA, pB, pE, pC, pD, pF; pA.x = pABE0.x; pA.y = pABE0.z; point pU, pV; pV.x

59、 = pU.x = p.x; if( GetValue_Polabola1(pA, pB, pE, pU) = false) return false; if( GetValue_Polabola1(pC, pD, pF, pV) = false) return false; if(GetValue_Line1(pU, pV, p) = false) return false; return true;也可以先进行也可以先进行y向向3个线性插值得个线性插值得到到3个点，再由此个点，再由此3点进行点进行抛物线插值抛物线插值先抛物线插值2次（X向），再y向线性插值1次抛物线抛物线插值（即双抛物线插

60、值）4.3.3 列表函数公式化 实际问题的复杂性，很难求得理论公式=对测量数据建立经验公式，用曲线拟合，不必通过指定点，但应反映数据的变化趋势，尽可能逼近。 拟合方式 线性拟合 幂函数或指数函数拟合 多项式拟合 确定拟合曲线方程 最小二乘法线性拟合 在直角坐标系中点大致呈线性分布， y（x） a0a1x xy幂函数或指数函数拟合 在对数坐标系中点大致呈线性分布xbaybayxlnlnlnYXXLnY多项式拟合 Y(x) = ajxj (j=0,1,2,3,m) YX最小二乘法的基本思想 w最小二乘法的多项式拟合（1）W 最小二乘法的多项式拟合（2）njyxaxaxaxaxnjxyxaxaxaanjayxaxaxaaimij