计算机辅助设计与制造CADCAM

1、一、 CAD/CAM概论CAD/CAM技术是一门多学科综合性应用技术，是20世纪制造领域最杰出的技术之一。11 CAD/CAM的基本概念CAD(Computer Aided Design):是指工程技术人员以计算机为工具完成产品设计过程中的各项任务，如草图绘制、零件设计、装配设计、工装设计、工程分析等；CAPP(Computer Aided Process Planning):是指工艺人员利用计算机，根据产品制造工艺要求，交互或自动地确定产品加工方法和方案，如加工方法的选择、工艺路线和工序的设计等；CAM(Computer Aided Manufacturing):制造人员借助于计算机完成从生

2、产准备到产品制造出来的过程中各个环节与活动，如数控加工编程、制造过程控制、质量检测等。1.1.1 从产品制造的过程理解CAD/CAM传统制造概念与过程 如图1。1产品设计阶段工艺设计阶段产品生产阶段任务规程概念设计结构设计与分析详细设计工程设计毛坯设计工艺路线设计工序设计工装设计NC编程加工仿真NC加工质量控制装配性能测试市场需求产品CADCAPPCAM将三者集成CAD/CAM现代制造概念与过程市场需求分析产品概念设计产品设计生产准备生产制造质量控制销售服务管理与协调利用计算机完成各个环节的工作成为CAD/CAM几点说明：1、计算机技术只能解决信息的查询与统计，信息的管理、重复而繁琐的工作等，

3、而并不能代替人的工作，特别是创造性的工作。2、现代制造概念很大，本书CAD/CAM的概念只涉及到产品的设计、工艺设计、加工、车间控制与质量控制等内容。3、上述制造环中有三个流：物流、资金流与信息流。4、企业制造资源有人、财、物、技术与信息。1.1.2 CAD/CAM的基本功能在CAD/CAM系统中，人们利用计算机完成产品结构描述、工程信息表达、工程信息的传输与转化、信息管理等工作。因此，CAD/CAM系统应具备以下基本功能：1、产品与过程的建模如何用计算机能够识别的数据（信息）来表达描述产品。如产品形状结构的描述、产品加工特性的描述、如何将有限元分析所需要的网格及边界条件描述出来等等。2、图形

4、与图象处理在CAD/CAM系统中，图形图象仍然是产品形状与结构的主要表达形式，因此，如何在计算机中表达图形、对图形进行各种变换、编辑、消隐、光照等处理是CAD/CAM的基本功能。3、信息存储与管理设计与制造过程会产生大量、种类繁多的数据，如设计分析数据、工艺数据、制造数据、管理数据等。数据类型有图形图象、文字数字、声音、视频等；有结构化和非结构化的数据；有动态和静态数据等。怎样将CAD/CAM系统产生这些大量的电子信息存储与管理好，是CAD/CAM的必备功能。采用工程数据库。4、工程分析与优化计算体积、重心、转动惯量等，机构运动计算、动力学计算、数值计算，优化设计等。CAE5、工程信息传输与交

5、换信息交换有CAD/CAM系统与其他系统的信息交换和同一CAD/CAM系统中不同功能模块的信息交换。6、模拟与仿真为了检察产品的性能，往往需要对产品进行各种试验与测试，需要专门的设备与生产出样品，并具有破坏性，时间长，成本大。通过建立产品或系统的数字化模式，采用计算机模拟技术可以解决这一问题。如加工轨迹仿真，机构运动仿真，工件、刀具和机床碰撞与干涉检验等。7、人机交互数据输入、路线与方案的选择等，都需要人与计算机进行对话。人机对话交互的方式有软件界面与设备（键盘、鼠标等）8、信息的输入与输出信息的输入与输出有人机交互式输入输出与自动输入输出。CAD/CAM的具体功能见图1.3 P4CAD几何造

6、型工程绘图工程分析和优化模拟与仿真CAPP工艺知识检索工艺路线生成工艺设计CAM数控加工编程加工仿真车间管理计划调度质量控制工程数据库EDBMS1.1.3 CAD/CAM系统的组成与工作过程如图1.4 P51.2 CAD/CAM技术的发展回顾1.2.1CAD技术的发展1形成期 1950 MIT CRT(阴极射线管) 计算机能够处理图形 计算机图形学。2. 发展期 50年代 光笔交互式会图 60年代 屏幕菜单点击、 功能键盘、光笔定位、图形动态修改。1962 美国 Ivan Sutherland 第一个交互式图形系统（SketchPad） 2D系统3、成熟期1973 实体造型技术 实体造型软件

7、3D系统4.集成期信息分散、不能共享，不能发挥合力效益，开发专用接口，成本大，自动化程度不高 等等 集成CAD/CAM.1.2.2 CAM技术的发展1952年数控机床1955自动编程工具（APT） 1958自动换刀系统加工中心（MC） 1962工业机器人物料搬运自动化，利用一台计算机控制多台数控设备(直接数控系统)DNC FMS.70年代，交互式图形编程系统，CAM成熟 智能化，集成化，自动化。1.2.3 CAPP技术的发展1969年，挪威，成组技术，零件分类归族，典型样件与典型工艺 AutoPros1980年，英国AutoCAP. 派生式CAPP系统。简单，实用，成本低，周期短；但与企业的特

8、性相关度高，一般不适合于其他企业。采用规则，推理，根据工艺的特性，自动生成工艺路线，成为创成式CAPP，自动化程度高，适合于多种企业。但由于工艺过程涉及的因素多，开发周期及成本高，目前仍然在研究阶段。80年代中期，CAPP专家系统。1.2.4 CAD/CAM的集成技术CAD、CAPP、CAM技术长时间独立发展，使数据结构、软件结构、平台等方面有很大差异。系统之间不能进行自动的数据交换，需要大量的人工参与以完成数据传输工作，严重阻碍CAD、CAPP、CAM技术的效益与发展。80年代，人们致力于CAD、CAPP、CAM技术集成研究。相继推出了CADAM、CATIA、UG、Pro/E等。1.3CAD

9、/CAM技术的应用1.3.1CAD/CAM的应用现状机械是主要应用领域2D应用最广我国在2D CAD系统和CAPP系统中自主产品，市场占有率较高。3D刚起步。1.3.2 CAD/CAM的应用效益生产精度与产品质量提高产品开发周期缩短 GM 汽车 5年3年新产品可靠性提高 20%60%生产成本下降 波音777未生产样机详细效益请见P111.4 CAD/CAM技术的新发展1.4.1 制造企业面临的市场形式产品形式多样化、个性化，生产方式由大批量、少品种少批量、多品种；市场响应速度快。大吃小快吃慢产品的范畴：产品产品P+质量Q+时间T+服务S (T,Q,C,S)竞争范围：区域全球核心竞争力创新技术与

10、人才各种新技术的出现与应用，特别是计算机与信息技术，Internet上述原因，企业未来呈现的特点：1、 产品开发生产周期短，上市快；2、 制造柔性化；3、 整个产品生命周期内的质量保证4、 企业组织形式，出现虚拟企业与企业联盟5、 生产过程更为精良6、 人才素质高7、 智能化与自动化程度高8、 绿色制造9、 分布、并行、集成并存企业未来力呈现的特点对CAD/CAM系统的要求1、 集成化，2、智能话，3、网络化，4、分布并行处理，5、综合技术的产品开发，6、虚拟现实技术，7、人机工程。1.4.2CAD/CAM新方向1、 支持TOP-Down，2、支持DFx，3、智能CAD/CAM，4、CE、5、

11、虚拟制造，6、集成制造，7、异地设计制造。二、CAD/CAM系统2.1 CAD/CAM系统组成与分类2.1.1 CAD/CAM系统组成CAD/CAM系统由硬件和软件系统组成。硬件系统是指可触摸到的物理设备，如主机设备、终端设备、网络及通信设备、输入输出设备，数控加工及控制设备等。软件系统通常是指程序及其相关文档的总和，软件系统一般分为系统软件、支撑软件和应用软件。具体见图2.1 P21.2.1.1 CAD/CAM系统的分类从不同的角度，CAD/CAM系统可分为不同的类型。从硬件角度，分为两大类。1、以大型机或小型计算机为主机的、多用户分时系统。其基本结构如2.2a图，P22.主机系统的特点：1

12、) 外围设备和用户工作站与主机相连，用户工作站中至少有一台图型工作站和一套图形处理设备（如图形终端，图形输入输出设备等），图形工作站基本结构如2.2b图，P22.2)优点：主机功能强，可处理大量信息，如分析计算，模拟。使用性能取决于软件水平。3）缺点：系统专用性强，比较封闭，终端过多，系统速度变慢，价格较高。另外，系统的可靠性取决于主机（主机发生故障，整个系统都将瘫痪）。2、工程工作站或微机系统的单用户系统。（）此系统特点：1）每一个工程工作站或微机系统都能独立完成CAD/CAM系统所要求的各项任务。2）价格较低，在中小型企业得到应用3）可靠性高已成为主流按功能划分，CAD/CAM系统可分为C

13、AD、CAM、CAD/CAM。1、 CAD系统：专门为设计而建立的系统，可完成各项设计任务，如造型、会图、工程分析仿真与模拟，文档管理等。不具备数控编程、加工仿真、生产控制及管理等。2、 CAM系统：具备数控编程、加工仿真、生产控制及管理等功能，几乎不具备造型、会图、工程分析仿真与模拟等功能。3、 CAD/CAM系统：具备CAD与CAM的所有功能，并可进行信息的自动交换。已成为主流。根据是否使用计算机网络，CAD/CAM系统又可分为单机系统和网络系统。计算机网络：通过通信线路连接起来的自治的计算机集合。包括三个含义（1、必须有两台或两台以上的具有独立功能的计算机系统相互连接在一起，达到资源共享

14、的目的；2、连接在一起的计算机必须有一条信息交换的通道；3、在同一网络中的计算机系统之间进行信息交换，必须遵循共同的约定与规则，即协议）1、 单机CAD/CAM系统：具备所有CAD/CAM的软件与硬件功能。但不能与其他CAD/CAM进行信息交换。信息不能共享。2、 网络CAD/CAM系统：将具备CAD/CAM的软件与硬件功能的各个节点用网络设备和通信线路进行连接就形成了一个网络化的CAD/CAM系统。可实现资源与信息共享。已成为主流。网络结构有星型、环型、总线型和网络等形式。由于总线型具有兼容性强，开放性和可扩展性良好等特性，因此，总线已成为主流。2.2CAD/CAM系统中的典型硬件2.2.1

15、计算机基本系统计算机基本系统由主机（包括CPU、主板和内存）、外存（磁盘、光盘）、显示器、键盘和鼠标等组成。主机：包括CPU、主板和内存主机的性能主要取决于CPU性能，CPU由控制器、运算器及各种寄存器组成，其性能由主频和寄存器的位数决定。内存：内存直接与CPU相连，并直接进行数据读取。内存分为只读存储器ROM与随机存取存储器RAM。8位二进制为一个字节。外存：磁盘、光盘2.2.2输入设备键盘、鼠标、操纵杆；数字化仪（如图2.7 P27），数字化一般用于将纸张图转化成计算机图。图形板、光笔、触摸屏、扫描仪、数字化手套、传感器等。2.2.3输出设备显示器、打印机、绘图仪、生产设备。2.2.4网络

16、设备服务器（用于提供公共服务的高性能计算机，运行网络操作系统）、工作站。电缆：同轴电缆(500m)、光缆(1000m)、双绞线（100m）。网卡中继器：用于信号放大，使信息传输更远，不改变信号。网桥：对网络进行分割，平衡网络负载。路由器：LAN与WAN的连接设备，将多个独立网进行连接。实现互联网之间的最佳寻径与数据传输。网关：连接不同体系网络，如不同协议。Novell与Ethernet。2.3 CAD/CAM软件系统软件是一种逻辑实体，是程序、数据及相关技术文档的总和。根据层次划分，CAD/CAM软件系统分为系统软件、支撑软件和应用软件。其层次关系如图2.13 P35系统软件：面向计算机及网络

17、系统的，实现对计算机及网络的管理，提供用户操作及管理计算机与网络的界面。是其他软件系统的基础。系统软件主要包括操作系统、编程语言、网络通信及其管理三大部分。1、操作系统操作系统的主要功能是：处理器管理、设备管理、存储管理、文件管理与用户接口（界面）。按功能及其工作方式分，操作系统可分为单用户、批处理、实时、分时、网络和分布式六类。DOS是一个单用户、单任务系统，而Unix与Windows是多用户分时系统。可由人工干预，实现交互式操作。实时系统不需要人工干预，处理速度快，可靠性高，能够对信息处理的过程进行监控。在CAD/CAM系统中，常用的操作系统有，工作站：Unix、VMS；微机：Window

18、s、XENIX。2、计算机编程语言计算机语言有机器、汇编（低级语言）及高级语言。机器语言是计算机唯一能够识别的语言。用汇编和高级语言编写的程序必须经过转换成机器语言后才能运行。低级语言依赖计算机硬件程度高，而高级语言几乎不依赖以计算机硬件。低级语言编写的程序比高级语言编写的程序要快。高级语言编写的程序必须经过编译和连接后才能执行。常用的高级语言有VisualC+、Visual Basic、Java（面向对象编程方法）。Lisp,ProLog用于人工智能与专家系统。3、网络通信及其管理软件网络通信及其管理软件主要包括网络协议、网络资源管理、网络任务管理、网络安全管理与网络通信浏览工具等功能。在计

19、算机网络中，不同的计算机系统之间进行信息交换时，必须遵循某种共同的约定与规则，这种约定与规则即为协议。网络协议是按层次划分的。按”开放系统网络标准模式” OSI，网络协议分为七层，即应用层、表示层、会话层、传输层、网络层、链路层和物理层。CAD/CAM流行的主要网络协议有：1) MAP(Manufacturing Automation Protocol) 用于工厂自动化2) TOP(Technicality and Office Protocol) 用于技术与办公环境3) TCP/IP( Transmission Control Protocol / Internet Protocol) 按报

20、文为传输单位。2.3.2机械CAD/CAM支撑软件支撑软件不为某一具体应用而设计开发的，只为用户提供应用工具和开发环境。从功能上划分，支撑软件可分为，基本图形资源与自动绘图，几何造型、工程分析与计算、仿真与模拟、专用设备控制程序生成器、集成与管理等6大部分。1、基本图形资源管理与自动绘图软件基本图形资源软件是根据图形标准或规范实现的软件包，为用户提供的是基本图形及图形操作的程序和函数库。是其他图形软件的基础。常用的有CGI(计算机图形界面)，GKS（图形软件包）及PHIGS(程序员等级交互图形系统)等。自动绘图软件提供了各种基本图元与图形基本操作等功能，用户可采用交互式方式完成绘图工作，常用有

21、AutoCAD，CADKey等。2、几何建模软件。提供完整的三维几何形状的描述与显示。还具有各种图形渲染及物性计算等功能，常用有Pro/E、UGII。3、工程分析与计算利用工程计算及分析软件可完成运动学、动力学、有限元分析等任务，常用的有Ansys、nastran等。4、仿真与模拟软件5、工艺过程设计6、管理与集成对各种CAD/CAM软件所产生的数据进行管理，采用数据库。常用的数据库有Oracle、Sybase、MS SQL Server 、DB2、Informix。2.3.3应用软件基于系统软件、支撑软件基础之上，专为某种特殊应用开发而成应用软件。如机械标准件图库，公差标注工具，电子元器件。

22、2.4 CAD/CAM系统的设计原则2.4.1系统设计的总原则在满足需求的前提下，既要实现目标，又要适应技术的发展，还要考虑具有的人才与资金的条件。1、 实用性；2、适度的先进性；3、系统性（完整性、功能与性能的配套，集成）；4、整体设计与分步实施。2.4.2系统硬件选用原则1、系统功能速度、精度、存储能力及兼容性2、 开发性与可移植性3、 升级与扩展性4、 性价比5、可靠性及维护性与服务2.4.3 软件选用原则1、功能；2、性价比；3、与硬件配套；4、二次开发能力、二次工具与开发环境；5、开放性；6、可靠性与服务。三、CAD/CAM软件开发基础在CAD/CAM系统应用过程中，不仅要向系统输入

23、大量的数据，同时系统也会产生大量的数据，怎样存储、使用、管理好这些数据是使用好CAD/CAM系统的重要任务，也是开发CAD/CAM软件的基础。3.1工程数据的程序化在进行机械设计与制造中，会遇见很多格式数据，要实现CAD/CAM系统，首先要对这些数据进行计算机化或程序化。3.1.1 数值程序化1、数组形式对于一组单一、精确、而数据之间又无规律的数列，可定义数组进行存放处理。如齿轮标准模数，见P43 表3.1可定义一个一维数组加以存放与处理。2、公式化对于一组单一、精确、而数据之间又规律的数列可采用公式表达。如60、70、80、90、100、110、120这一标准的直径序列，可采用下列公式（表达

24、式进行处理）D=int(Dc/10.02)*10+10 其中Dc是根据强度计算所得到的直径。3.1.2数表程序化1、屏幕直观交互式输入法如果数表中的数据量不大，可在有限的屏幕中放置，且数据为有限个离散值，在使用时是根据综合考虑选用中间值，此时可这些数据用屏幕输出语句输到屏幕上供使用者直观交互式地选用。如齿轮传动强度计算中的系数Kv，此系数是根据原动机工作特性和工作载荷特性等进行综合，在表3.2中进行选值（可选中间值）。表中数据量少，可在有限的屏幕中放置。2、数组化数据量较大，精确且无规律的数表可采用数组进行存储与处理。如平键和键槽与轴径的尺寸关系数表3.3 P45。注：只能选用数表中数据，不能

25、取中间值。3、公式化如果数表中只有两个参数，设Pi、fi，且这两个参数存在一一对应关系，即已知一个在数表中找得到的Pi值、数表中有一个fi值与其对应，且若已知一个在数表中找不到的Pi值，有一个近似非数表中的fi值与之对应，Pi与fi存在函数关系，则此数表可进行公式化。如表3.4 （ P47 ）中蜗轮当量齿数与齿形系数的关系表。工程上常采用插值法和拟合法对这种数表可进行公式化。插值法原理：设有离散点序列（x1,y1）、（x2,y2）、（xi,yi）、（xn,yn），若有一函数y=f(x)，且yi=f(xi)，则称y=f(x)为（x1,y1）、（x2,y2）、（xi,yi）、（xn,yn）序列插值

26、函数。常用的插值方法有线性插值和拉格朗日插值法。1）线性插值(两点插值)已知两点，（x1,y1）、（x2,y2），并近似地认为其它数据在这两点区间成线性关系，则可采用线性插值。插值函数为=y=y1+(x-x1)如果有多点，相邻两点用直线段连接，则每段线性插值的一般形式为：y=yi+(x-xi-1) 例如：如表3.4 （ P47 ）中蜗轮当量齿数与齿形系数的关系表，当zv=25.6(即x=25.6) ( xi-1=24, yi-1=1.88)；( xi=26, yi=1.85)，求YF2）拉格朗日插值当线性插值误差较大，可采用高次插值（二次和二次以上）通过整理线性插值表达式得：f(x)=y=y1

27、·+ y2·二次插值f(x)=y=y1·+ y2·+ y3·对于n个节点的n-1次拉格朗日插值的一般式子有：f(x)=y=yi·Ai 其中Ai=4、交互式分级描述法将复杂的多元函数表按一定的原则分解成多个子表，用程序描述各子表之间的关系，通过人机交互式的方式逐步选值。如表3-5齿轮常用材料及力学性能 , P48。3.1.3线图程序化在工程中有许多线图，这些线图有的是通过计算公式所计算数据而来，有的是通过实验数据而来。对实验数据，由于实际情况的复杂性，很难用公式精确描述，一般采用某种近似曲线公式来加以描述，这种曲线公式就称为经验公式，建

28、立经验公式的过程称为曲线拟合。拟合与插值的区别是，插值是必须过插值节点，而拟合是不一定需要过节点的。1、拟合原理曲线拟合的方法很多，常用的是最小二乘法。1）线性方程拟合 有n组实验数据（xi，yi），设线性方程的形式：y=a+bx最小二乘法：为了达到最好的拟合，应使各节点的偏差平方最小，即使。S(a，b)=最小。S(a，b)有两个参数 a与b。采用偏导求出最大值。2）对数方程拟合 有n组实验数据（xi，yi），设对数方程的形式：y=a+blnx设X=lnx，则对数方程的形式为y=a+bX。注意：在利用3.9和3.10式求a，b时，应将lnxi代入。3）指数方程拟合有n组实验数据（xi，yi），

29、设指数方程的形式：y=axb对两边取对数。得lny=lna+blnx。设Y=lny，X=lnx，A=lna，则有 Y=A+bX与线性方程拟合一样求解。4）对数指数方程拟合（略）5）二次方程及多次方程拟合（略）3.2CAD/CAM中的数据结构在CAD/CAM中存在大量的数据，如性能参数，工艺数据、管理数据等。这些数据不是孤立的，他们之间存在作关系。怎样将这些数据进行有效的管理与存储，表达和定义好他们的结构是基础。这就是数据结构问题。3.2.1基本概念与术语数据：是现实世界客观存在的实体或事物的属性值，即人们感知到的景象。数据可以是数值、字符、文字，也可以是声音、图形图象等。信息：是含有一定意义的

30、数据称为信息数据处理信息存储信息与数据的关系是：1） 信息是有一定含义的数据2） 信息是经过加工处理后的数据3） 信息是对决策有价值的数据现实世界（数据）、信息与计算机之间的关系如图3.8 P56实体：客观存在并可相互区别的事物。属性：实体特性属性值：每一个实体属性所能测量或记录的值。数据（属性）域：属性取值范围数据按组成的内容可分成若干层次1）字符 是组成数据的最小单位。包括数字、字母、特殊符号等2）数据项 是数据中最基本的、不可分的、并有命名的数据单位，由字符组成，代表某一数据量。如轴承性能表 3.9 P57 中的轴承代号、尺寸、载荷等。3）组合项 由一个或多个数据项组成。如尺寸由四个数据

31、项组成。4）记录：相关数据项或组合项构成的集合称为一条记录，他描述了一个实体。如代号为6202轴承对应一行中的各数据项共同描述的某一型号的轴承。记录又称为数据元素。5）文件 相同性质的记录的集合就是文件。表 3.9 中记录全体构成了一个文件6）数据库 非单纯性（即有一定的特点与要求）、具有结构文件的集合。3.2.2 数据结构数据元素（记录）不是孤立的，而是相互有关联的。多个数据元素之间的关系构成一个数据结构，而数据结构又可能是另一个数据结构中的数据元素。即数据结构是可嵌套的。如图3.9中的车床结构图。数据结构有逻辑结构和物理结构之分。1、逻辑结构逻辑结构描述的是数据之间的逻辑关系，它是从客观的

32、角度去组织和表达数据。根据关系特点，逻辑结构分为线性结构和非线性结构。1）线性结构数据之间的关系只有顺序排列的位置关系，这种顺序位置关系是线性的。因此这种数据结构称为线性结构，也称为线性表结构。数组就是一种线性结构。在线性结构中，每一数据元素（节点或数据域）只有一个前趋节点和一个后趋节点。2）非线性结构当数据结构中的某数据元素有两个或两个以上的前趋或后趋节点，则这种数据结构中的数据元素之间的关系是非线性的，因此此种数据结构称为非线性数据结构。如图3-9 车床零部件关系（树状结构）和图3-10 工艺路线方案（网状结构） P58图3-11表示的是一个几何图形及其数据结构，在这个数据结构中，树状结构

33、与网状结构共存。树状结构：当数据结构中的数据元素有多个前趋，只有一个后趋。网状结构：当数据结构中的数据元素有多个前趋和多个后趋。2、物理结构数据的物理结构是指数据在计算机内部的存储方式，是从物理存储的角度描述数据之间的关系。常用的物理结构有顺序存储结构与链接存储结构两种。1）顺序存储结构：用一组连续的存储单元依次存放各数据元素。特点：存储顺序与逻辑顺序一致，只需要存放第一个数据元素的地址，其他元素的地址是第一个元素地址加上一个相对地址，因此占用存储单元少，简单，结构紧凑。但缺乏柔性，当要进行增删操作时，必须重新分配存储单元。费时。如数组。2）链接存储结构在数据元素中，除存放数据外，还存放其他数

34、据的存放地址。这样，在得到第一个元素得地址后，就可以根据第一个数据元素中地址检索出其下一个数据元素的存放地，以此类推。这种物理存储方式称为链接存储结构。在链接存储结构中，每一个数据元素有数据和地址（或指针）两种域组成。根据指针域的个数，链接存储结构可大致分为三类。（1）单向链结构 在每一个数据元素中，只有一个指向下（或上）一个数据元素指针域。如图3-14a如果指针所指的方向与逻辑顺序相同，则称正向链；如图3-14a如果指针所指的方向与逻辑顺序相反，则称为反向链；如图3-14b如果在最后一个数据元素中，有指向第一个数据元素的指针，则此链接结构构成了一个环链；如图3-14c（2）双向链结构 在每一

35、个数据元素中，有两个指针，一个指向下一个数据元素，而另一个指向上一个数据元素。双向链也可以构成环链。如图3-14d和如图3-14e环链的最大特点是任何一个数据元素都可以是数据存取的入口点，存取效率高。（3）多向链结构 在数据结构中，某些数据元素有两个以上的指向其他数据元素的指针域。多向链结构一般用于矩 、树状等数据结构存储。如图3-14f3.2.3 常用的数据结构1、线性表线性表是一个由n（n>=0）个数据元素（a1，a2，an）组成的有限序列，表中的每一个数据元素，除第一个和最后一个外，仅有一个直接前驱和一个直接后继。当n=0时，称为空表。线性表的逻辑表示可为：（a1，a2，an），如

36、轴径序列值（3，6，10，14，18，24，30，40，50，65，.）线性表的物理存储结构既可以采用顺序存储，也可以采用链接存储结构。2、栈与队列1）栈 当对线性表的删除与插入操作只能在表的一端进行时，线性表就变成了栈。在栈中，允许插入与删除的端称为栈顶，而另一端称为栈底。栈的操作是按后进先出的原则进行的，因此栈也称为后进先出表（LIFO）。实际生活中，栈的例子很多。如穿衣服，火车换道。栈的示意图如图3-16。举例 2 5 3 4 按顺序入栈，出栈有几种顺序？栈的物理存储结构可以是顺序，也可以是链接。在顺序栈中，要有一个栈顶指示器和一个栈顶界限（限制栈的空间）。2）队列 当对线性表的删除与插

37、入操作限制只在一端插入，在另一端删除时，线性表就变成了队。允许插入的一端称为队尾，而允许删除的一端称为队头。栈的操作是按先进先出的原则进行的，因此队也称为先进先出表（LIFO）。实际生活中，队的例子很多。如排队买东西，如图3-18。队的物理存储结构可以是顺序，也可以是链接。在顺序队中，要分别设置队头指针和队尾指针以及一个队尾界限（限制队的空间）。队“溢出”与“假溢出”，参见P 62.采用循环队解决“假溢出”问题。3、数组数组是一种按顺序排列与存储、并且每个数据元素具有相同的数据类型的特殊线性表。4、串是一种特殊的数组，其数据元素中数据为字符类型。5、树与二叉树1）树栈、队、数组与串都是线性结构

38、，不能解决实际中非线性问题，如行政单位结构，产品结构等问题。这就需要各种非线性结构。树是一种常用的非线性结构，其定义为当数据元素集合中的每一个数据元素都一个或多个后继，而只有一个前驱，并且处于最高层的那个数据元素没有前驱。这样的数据结构称为树。没有前驱的最高层的那个数据元素（节点）称为树根；树的最大层次称为树的深度；节点的后继（子树）个数称为度；度数（或后继）为零的节点称为树叶。用例子图3-21说明这些概念。P63树的物理结构可以是顺序、也可以是链接。2）二叉树当树具有以下特点时，就称其为而叉树。（1） 可以没有任何数据节点，即为空。树必须具有至少一个根节点。（2） 每一个节点的度不能超过2。

39、树则无限制；（3） 二叉树的子树有左右之分，不能颠倒。树的子树无左右之分，可以交换位置。二叉树的物理存储结构常采用链接结构，其每个节点有一个左指针域和一个右指针域。这种结构与二叉树的逻辑结构一致。3）二叉树的遍历按一定规律，不重复地访问树中的每一个节点，这种操作称为遍历。对于二叉树，有三中遍历方式，即前序、中序和后序。具体算法见P64。举例说明三种遍历方法的算法。参见图3-24 P656、图与网在一个数据结构中，每一个节点（数据元素）可以有多个直接的前驱和后继时，这种数据结构称为图。图由顶点与边组成，见图3-25 P65设V是顶点集合，E是边的集合，则图G可用下式表示：G=(V,E)若顶点之间

40、是有序的，则边是有方向的，如图3-25 G3 P65，这种图称为有向图。否则称为无向图。树与图的关系：树是一种特殊的图。图3-25中的图G2，即是图，也是树。 P65通常用n阶邻接方阵来表示n个顶点的图的逻辑结构。邻接矩阵中每个元素定义如下：1 若Vi与Vj相连0 若Vi与Vj不相连V(i,j)=参见图3-26说明图及其邻接矩阵。当图的边有权重时，图的邻接变为Wij 若Vi与Vj相连0 若Vi与Vj不相连V(i,j)=此时图称为网。参见图3-27说明网及其邻接矩阵。3.3数据文件文件是数据管理的一种形式，它能独立于应用程序单独存储。文件用于数据的管理、交换等。文件是记录的集合，文件记录中唯一能

41、够记录的数据项的称为关键字。如表3-10 齿轮参数表（P67）中的零件编号就是齿轮参数文件的关键字。1、常用的文件组织方法1）顺序文件 物理存储顺序与其逻辑顺序一致。其存储是连续的，结构紧凑简单，但增删、查询算法较为复杂，时间度与空间度较大。有一些存储设备只能存储顺序文件，如磁带。2）索引文件 带有一个包括关键字与记录存放地址索引表的文件称为索引文件。索引文件查询方法是：先按关键字到索引文件中查到该关键字所对应的记录存放地址，在根据地址到数据文件中去查找记录。索引文件的索引表必须按关键字按顺序排序。而文件本身可以排序或不排序。若文件本身排序称为索引顺序文件，否则称为索引非顺序文件。3）直接存取

42、文件 又称为随机文件。采用一种算法将记录的关键字转换为一个随机数，根据这个随机数确定记录在存储器中存放的位置。2、文件的操作文件的操作主要是查询与排序。1）查询 即查找关键字为某值的记录常用的查找方法有顺序、折半和分块等三种查找方法。（1）顺序查找法 从第一条记录开始，逐条查找，若查找到欲查数值则查找结束。此方法最为简单，但效率低。（2）折半查找法 也叫二分查找法原理是：先将文件记录按关键字大小顺序排序，再将位置为中间的记录的关键字值Km与欲查值K进行比较，比较结果有三种，KmK、KmK KmK。若KmK，则欲查记录在文件前半区；若KmK，则欲查记录在文件后半区；若Km=K，则查到欲查记录，查

43、找结束。如果为前两种情况，则在前半区或后半区继续进行。（3）分块查找 原理与折半法类似，不同是将按关键字排好序的文件分成大于2的若干块；再将欲查关键字依次与各块的最大关键字值进行比较，确定查找范围；然后在确定的那一块进行顺序查找。举例 设有一零件记录，其关键字分别为4、7、16、31、39、41、47、55、61、77、80、83，以升序排序，要查找关键字为80的记录。查找步骤：1、将记录分成三块（4、7、16、31）、（39、41、47、55）、）61、77、80、83）2、将欲查值80与各块的最大值（31、55、83）进行比较，确定欲查记录在第三块3、在第三块中进行顺序查找2）、排序对文件

44、中记录的关键字按递增或递减的顺序进行重新排列称为排序。排序的方法有很多，常用的有（1）选择排序在记录文件中找出关键字最小的记录，将其与第一条记录进行位置交换，然后从第二条记录开始到最后一条记录重复上述操作。举例 P69(2) 冒泡法顺序比较相邻记录的关键字，若后者比前者小，则交换位置，否则位置不变。经过不断的比较与位置交换，小值往前移，大值往后移，如水中的气泡。举例 P 69 （3）插入法首先假定第一条记录的位置是合适的，然后取出第二条记录与第一条记录进行关键字比较，若小于，则将第二条记录插入到第一条记录的前面，再取第三条记录与前面各条记录进行关键字比较；依次操作。 举例 P703.3.2 数

45、据库系统要解决CAD/CAM系统中的数据信息交换问题，首先是解决数据信息集成与共享问题。数据库技术是进行数据集成与共享的最佳技术。1、数据库特点数据管理技术经历了三个阶段，即人工管理、文件管理与数据库管理。人工管理：程序中所用到的数据及其相关操作（如存储、查询等）都必须由程序员自己编程完成。数据与程序依赖度高，程序中存在大量的重复数据（冗余），数据不能共享。数据与程序一一对应。如图 3-30 P70文件管理：数据按统一格式，以文件形式长期保存在计算机外存储器中，数据与程序之间相对独立。但数据文件之间彼此孤立，文件内部又无结构信息，因此数据的冗余度较大，共享范围有限，且文件管理系统缺乏对数据进行

46、集中管理与控制，数据的操作仍然离不开程序员，数据与程序不能完全独立。 数据文件与程序之间的关系见图3-31 P71数据管理：其特点如下：1）数据模型复杂 在描述数据的同时，也描述数据之间的关系，即数据结构化强。2）数据的共享性好、冗余度低 3）数据具有独立性 数据可独立于程序存在，应用程序不必随着数据结构的变化而修改。数据库系统本身具有很强数据操作功能，不需要程序进行数据操作。数据文件与程序之间的关系见图3-32 P714)数据具有安全性、完整性。数据库系统提供了对数据控制的功能，数据能够得到保护；数据的正确性、有效性、相容性，即完整性能得到保证。任何一个数据库管理系统DBMS（Data Ba

47、se Management System）,都会提供上述特点和功能。DBMS是数据库系统的核心。尽管数据库管理有许多优点，但必须根据具体情况选用数据的管理方法。2、数据库管理系统1）数据库系统的构成数据库系统由相应的硬件、软件和专职管理人员及数据构成。（1） 硬件（2） 软件 数据库软件系统层次见图3-33 P72（3） 数据库管理人员 （Data Base Administrator）DBA。决定数据库的信息内容与存储结构，定义和存储数据库数据；监督与控制对数据库的使用与运行，保证数据的完整性；定义用户权限；维护和改进数据库。（4） 数据库 由DBMS建立、运行、管理及维护的通用化的、综合性

48、的数据集合。2）数据库管理系统的功能（1）数据库定义功能 实现对数据的全局逻辑结构、局部逻辑结构、物理存储结构及权限等定义。（2）数据库管理功能 提供对数据各种应用操作，如增删、排序、查找、统计、输入输出、修改等。（3）数据库的建立与维护功能 建立、更新、再组织、恢复等功能。（4）通信功能 与操作系统通信、与应用程序的通信（5） 其他功能 文件管理、应用开发、存储管理、设备管理等3）数据库管理系统的组成（1）、数据描述语言（Data Description language ,DDL）及其翻译程序，用于描述数据及其之间的关系，实现对数据库的定义。（2）数据库操纵语言（Data Manipula

49、tion language ,DML）及其编译程序，用于存储、检索、编辑数据库数据。（3）数据库管理例行程序（Data Base Management Routiness ,DBMR），一般包括系统运行控制程序、语言翻译程序和DBMS的公用程序4）数据库管理系统的抽象层次用户所看到的数据与计算机中存储的数据之间有一种映射关系，这种映射关系通过数据库的三个模型层实现的。（1）外模型 用户使用的数据视图，是局部的逻辑视图。表示用户理解的实体、实体属性、实体之间的关系。外模型有多个，处理系统的外层。（2）概念模型 数据库的全局逻辑视图。表示整个系统的实体、实体属性、实体之间的关系。概念模型只有一个，

50、属于系统的概念层。（3）内模型 数据库的物理存储模型。只有一个，最底层。在DBMS中用DDL精确描述上述三种模型，就得到相应的模式。即外模式（子模式）、概念模式（模式）、内模式（物理模式）。以内模式（物理模式）为框架的数据库为物理数据库。以概念模式（模式）为框架的数据库为概念数据库。概念数据库是由数据库设计者在物理数据库之上构造出来的。以外模式（子模式）为框架的数据库为用户数据库。从内模式到外模式需要经过物理模式模式子模式的两级转换。参见图3-34和3-35 P743、数据库的数据模型表示实体与实体之间的关系的模型称为实体模型。常见的数据模型有层次模型、网状模型和关系模型。1）层次模型 用树结

51、构表示实体及实体之间的关系的模型。层次模型必须满足两个条件，即只有一个根节点，根节点以外的其他节点有且仅有一个前驱。 如图 3-36 P752) 网状模型 取消层次模型的两个要求，就可得到网状模型 如图 3-37 P753）关系模型 用二维表结构表示实体及实体之间的关系的模型。一张二维表就是一个关系。参见表3-11 P76关系二维表必须满足下列条件：（1） 表中的每一列必须是基本数据项，不能是组合项（2） 每一列必须具有相同的数据类型（3） 每一列必须有一个唯一的属性名（4） 不能有两条相同数据的行（5） 列与行的顺序不受限制基于关系模型建立的数据系统称为关系型数据库系统。4、工程数据库目前，

52、商用数据库（即关系型数据库）发展已较为成熟，但仍然不能满足对工程数据的管理。这是因为，工程数据具有如下特点：1）数据形态多样性 静态数据、动态过程数据、定期改变的结果数据。2）数据类型的多3）数据关系复杂 有网状数据、多层、多嵌套，还有不定结构的数据4）数据修改频繁 数据需要进行不断的交流、反馈、反复修改等。工程数据库应具备的功能特点：1） 能够描述复杂的数据模型2） 支持模式动态定义与修改3） 支持工程长事务的处理4） 具备版本管理、图形标准转换等工程数据库开发方法1） 以商用数据库为基础，扩充其功能2） 分析、拆解商用数据库系统的代码，按工程数据库管理系统的要求，重新组织其结构、模式等3） 根据EDBMS的要求，重新开发新一代数据库技术1） 分布式数据库 物理分布、逻辑整体、分布独立和场地自治性。2） 主动数据库