《计算机辅助设计与制造(CADCAM).doc》由会员分享，可在线阅读，更多相关《计算机辅助设计与制造(CADCAM).doc（81页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、 CAD/CAM 概论本章主要是讲解 CAD/CAM 的根本概念、根本功能和工作原理等。CAD/CAM 技术是一门多学科综合性应用技术，是 20 世纪制造领域最精彩的技术之一。1.1 CAD/CAM 的根本概念CAD(Computer Aided Design):是指工程技术人员以计算机为工具完成产品设计过程中的各项任务，如草图绘制、零件设计、装配设计、工装设计、工程分析等；CAPP(Computer Aided Process Planning): 是指工艺人员利用计算机，依据产品制造工艺要求，交互或自动地确定产品加工方法和方案，如加工方法的选择、工艺路线和工序的设计等；CAM(Comp
2、uter Aided Manufacturing):制造人员借助于计算机完成从生产预备到产品制造出来的过程中各个环节与活动，如数控加工编程、制造过程把握、质量检测等。市场需求CADCAPPCAM将三者集成CAD/CAM1.1.1 从产品制造的过程理解CAD/CAM 传统制造概念与过程 如图 1。1产品设计阶段任务规程概念设计工艺设计阶段毛坯设计工艺路线设计产品生产阶段NC 编程加工仿真产品构造设计与分析工序设计NC 加工具体设计工装设计质量把握工程设计装配性能测试现代制造概念与过程市场需求分析产品概念设计产品设计生产预备治理与协调效劳销售1质量把握生产制造利用计算机完成各个环节的工作成为CAD
3、/CAM几点说明：1、计算机技术只能解决信息的查询与统计，信息的治理、重复而繁琐的工作等，而并不能代替人的工作，特别是制造性的工作。2、现代制造概念很大，本书CAD/CAM 的概念只涉及到产品的设计、工艺设计、加工、车间把握与质量把握等内容。3、上述制造环中有三个流：物流、资金流与信息流。4、企业制造资源有人、财、物、技术与信息。1.1.2 CAD/CAM 的根本功能在 CAD/CAM 系统中，人们利用计算机完成产品构造描述、工程信息表达、工程信息的传输与转化、信息治理等工作。因此，CAD/CAM 系统应具备以下根本功能：1、产品与过程的建模如何用计算机能够识别的数据信息来表达描述产品。如产品
4、外形构造的描述、产品加工特性的描述、如何将有限元分析所需要的网格及边界条件描述出来等等。2、图形与图象处理在 CAD/CAM 系统中，图形图象照旧是产品外形与构造的主要表达形式，因此，如何在计算机中表达图形、对图形进展各种变换、编辑、消隐、光照等处理是CAD/CAM 的根本功能。3、信息存储与治理设计与制造过程会产生大量、种类繁多的数据，如设计分析数据、工艺数据、制造数据、治理数据等。数据类型有图形图象、文字数字、声音、视频等；有构造化和非构造化的数据；有动态和静态数据等。怎样将 CAD/CAM 系统产生这些大量的电子信息存储与治理好，是CAD/CAM 的必备功能。承受工程数据库。4、工程分析
5、与优化计算体积、重心、转动惯量等，机构运动计算、动力学计算、数值计算，优化设计等。CAE5、工程信息传输与交换信息交换有 CAD/CAM 系统与其他系统的信息交换和同一CAD/CAM 系统中40不同功能模块的信息交换。6、模拟与仿真为了检察产品的性能，往往需要对产品进展各种试验与测试，需要特地的设备 与生产出样品，并具有破坏性，时间长，本钱大。通过建立产品或系统的数字化模式， 承受计算机模拟技术可以解决这一问题。如加工轨迹仿真，机构运动仿真，工件、刀具和机床碰撞与干预检验等。7、人机交互数据输入、路线与方案的选择等，都需要人与计算机进展对话。人机对话交互的方式有软件界面与设备键盘、鼠标等8、信
6、息的输入与输出信息的输入与输出有人机交互式输入输出与自动输入输出。CAD/CAM 的具体功能见图 1.3P4CAD几何造型工程绘图工程分析和优化模拟与仿真CAPP工艺学问检索工艺路线生成工艺设计工程数据库EDBMSCAM数控加工编程加工仿真车间治理打算调度质量把握1.1.3 CAD/CAM 系统的组成与工作过程如图 1.4P51.2 CAD/CAM 技术的进展回忆1.2.1CAD 技术的进展1. 形成期1950MITCRT(阴极射线管) 计算机能够处理图形 计算机图形学。2. 进展期50 年月 光笔交互式会图60 年月 屏幕菜单点击、 功能键盘、光笔定位、图形动态修改。 1962美国Ivan
7、Sutherland 第一个交互式图形系统SketchPad2D 系统3、成熟期1973实体造型技术 实体造型软件 3D 系统4.集成期信息分散、不能共享，不能发挥合力效益，开发专用接口，本钱大，自动化程度不高等等集成CAD/CAM.1.2.2 CAM 技术的进展1952 年数控机床1955 自动编程工具APT 1958 自动换刀系统加工中心MC 1962 工业机器人物料搬运自动化，利用一台计算机把握多台数控设备(直接数控系统)DNC FMS.70 年月，交互式图形编程系统，CAM 成熟智能化，集成化，自动化。1.2.3 CAPP 技术的进展1969 年，挪威，成组技术，零件分类归族，典型样件
8、与典型工艺 AutoPros1980 年，英国 AutoCAP.派生式 CAPP 系统。简洁，有用，本钱低， 周期短；但与企业的特性相关度高，一般不适合于其他企业。承受规章，推理，依据工艺的特性，自动生成工艺路线，成为创成式 CAPP， 自动化程度高，适合于多种企业。但由于工艺过程涉及的因素多，开发周期及 本钱高，目前照旧在争辩阶段。80 年月中期，CAPP 专家系统。1.2.4 CAD/CAM 的集成技术CAD、CAPP、CAM 技术长时间独立进展，使数据构造、软件构造、平台等方面有很大差异。系统之间不能进展自动的数据交换，需要大量的人工参 与以完成数据传输工作，严峻阻碍 CAD、CAPP、
9、CAM 技术的效益与进展。80 年月，人们致力于 CAD、CAPP、CAM 技术集成争辩。相继推出了 CADAM、CATIA、UG、Pro/E 等。1.3 CAD/CAM 技术的应用1.3.1 CAD/CAM 的应用现状机械是主要应用领域2D 应用最广我国在 2D CAD 系统和CAPP 系统中自主产品，市场占有率较高。3D 刚起步。1.3.2 CAD/CAM 的应用效益生产精度与产品质量提高产品开发周期缩短GM汽车 5 年3 年产品牢靠性提高 20%60%生产本钱下降 波音 777 未生产样机具体效益请见P111.4 CAD/CAM 技术的进展1.4.1 制造企业面临的市场形式产品形式多样化
10、、共性化，生产方式由大批量、少品种少批量、多品种； 市场响应速度快。大吃小快吃慢产品的范畴：产品产品P+质量Q+时间T+效劳S(T,Q,C,S)竞争范围：区域全球核心竞争力创技术与人才各种技术的消灭与应用，特别是计算机与信息技术，Internet 上述缘由，企业将来呈现的特点：1、 产品开发生产周期短，上市快；2、 制造柔性化；3、 整个产品生命周期内的质量保证4、 企业组织形式，消灭虚拟企业与企业联盟5、 生产过程更为精良6、 人才素养高7、 智能化与自动化程度高8、 绿色制造9、 分布、并行、集成并存企业将来力呈现的特点对CAD/CAM 系统的要求1、 集成化，2、智能话，3、网络化，4、
11、分布并行处理，5、综合技术的产品开发，6、虚拟现实技术，7、人机工程。1.4.2 CAD/CAM 方向1、 支持 TOP-Down，2、支持DFx，3、智能CAD/CAM，4、CE、5、虚拟制造，6、集成制造，7、异地设计制造。二、CAD/CAM 系统CAD/CAM 系统的根本组成、构造与分类，软件、硬件及网络的根本概念，软件、硬件的分类，网络设备的功能等。重点是应用软件的根本概念及其分类和网络与网络设备的根本功能。2.1 CAD/CAM 系统组成与分类2.1.1 CAD/CAM 系统组成CAD/CAM 系统由硬件和软件系统组成。硬件系统是指可触摸到的物理设备，如主机设备、终端设备、网络及通信
12、设备、输入输出设备，数控加工及把握设备等。软件系统通常是指程序及其相关文档的总和，软件系统一般分为系统软件、支撑软件和应用软件。具体见图 2.1P21.2.1.1 CAD/CAM 系统的分类从不同的角度，CAD/CAM 系统可分为不同的类型。从硬件角度，分为两大类。1、以大型机或小型计算机为主机的、多用户分时系统。其根本构造如 2.2a 图，P22.主机系统的特点：1) 外围设备和用户工作站与主机相连，用户工作站中至少有一台图型工作站和一套图形处理设备如图形终端，图形输入输出设备等，图形工作站根本构造如 2.2b 图，P22.2) 优点：主机功能强，可处理大量信息，如分析计算，模拟。使用性能取
13、决于软件水平。3缺点：系统专用性强，比较封闭，终端过多，系统速度变慢，价格较高。另外，系统的牢靠性取决于主机主机发生故障，整个系统都将瘫痪。2、工程工作站或微机系统的单用户系统。 此系统特点：1） 每一个工程工作站或微机系统都能独立完成CAD/CAM 系统所要求的各项任务。2） 价格较低，在中小型企业得到应用3） 牢靠性高已成为主流按功能划分，CAD/CAM 系统可分为CAD、CAM、CAD/CAM。1、 CAD 系统：特地为设计而建立的系统，可完成各项设计任务，如造型、会图、工程分析仿真与模拟，文档治理等。不具备数控编程、加工仿真、生产把握及治理等。2、 CAM 系统：具备数控编程、加工仿真
14、、生产把握及治理等功能，几乎不具备造型、会图、工程分析仿真与模拟等功能。3、 CAD/CAM 系统：具备 CAD 与 CAM 的全部功能，并可进展信息的自动交换。已成为主流。依据是否使用计算机网络，CAD/CAM 系统又可分为单机系统和网络系统。计算机网络：通过通信线路连接起来的自治的计算机集合。包括三个含义1、必需有两台或两台以上的具有独立功能的计算机系统相互连接在一起，到达资源共享的目的；2、连接在一起的计算机必需有一条信息交换的通道；3、在同一网络中的计算机系统之间进展信息交换，必需遵循共同的商定与规章，即协议1、 单机 CAD/CAM 系统：具备全部 CAD/CAM 的软件与硬件功能。
15、但不能与其他CAD/CAM 进展信息交换。信息不能共享。2、 网络CAD/CAM 系统：将具备 CAD/CAM 的软件与硬件功能的各个节点用网络设备和通信线路进展连接就形成了一个网络化的CAD/CAM 系统。可实现资源与信息共享。已成为主流。网络构造有星型、环型、总线型和网络等形式。由于总线型具有兼容性强，开放性和可扩展性良好等特性，因此，总线已成为主流。2.2 CAD/CAM 系统中的典型硬件2.2.1 计算机根本系统计算机根本系统由主机包括 CPU、主板和内存、外存磁盘、光盘、显示器、键盘和鼠标等组成。主机：包括CPU、主板和内存主机的性能主要取决于CPU 性能，CPU 由把握器、运算器及
16、各种存放器组成，其性能由主频和存放器的位数打算。内存：内存直接与 CPU 相连，并直接进展数据读取。内存分为只读存储器ROM 与随机存取存储器RAM。8 位二进制为一个字节。外存：磁盘、光盘2.2.2 输入设备键盘、鼠标、操纵杆；数字化仪如图2.7 P27，数字化一般用于将纸张图转化成计算机图。图形板、光笔、触摸屏、扫描仪、数字化手套、传感器等。2.2.3 输出设备显示器、打印机、绘图仪、生产设备。2.2.4 网络设备效劳器用于供给公共效劳的高性能计算机，运行网络操作系统、工作站。电缆：同轴电缆(500m)、光缆(1000m)、双绞线100m。网卡中继器：用于信号放大，使信息传输更远，不转变信
17、号。网桥：对网络进展分割，平衡网络负载。路由器：LAN 与 WAN 的连接设备，将多个独立网进展连接。实现互联网之间的最正确寻径与数据传输。网关：连接不同体系网络，如不同协议。Novell 与 Ethernet。2.3 CAD/CAM 软件系统软件是一种规律实体，是程序、数据及相关技术文档的总和。依据层次划分，CAD/CAM 软件系统分为系统软件、支撑软件和应用软件。其层次关系如图 2.13P35系统软件：面对计算机及网络系统的，实现对计算机及网络的治理，供给用户操作及管 理计算机与网络的界面。是其他软件系统的根底。系统软件主要包括操作系统、编程语言、网络通信及其治理三大局部。1、操作系统操作
18、系统的主要功能是：处理器治理、设备治理、存储治理、文件治理与用户接口界面。按功能及其工作方式分，操作系统可分为单用户、批处理、实时、分时、网络和分布式六类。DOS 是一个单用户、单任务系统，而 Unix 与 Windows 是多用户分时系统。可由人工干预，实现交互式操作。实时系统不需要人工干预，处理速度快，牢靠性高，能够对信息处理的过程进展监控。在 CAD/CAM 系统中，常用的操作系统有，工作站：Unix、VMS；微机：Windows、XENIX。2、计算机编程语言计算机语言有机器、汇编低级语言及高级语言。机器语言是计算机唯一能够识别的语言。用汇编和高级语言编写的程序必需经过转换成机器语言后
19、才能运行。低级语言依靠计算机硬件程度高，而高级语言几乎不依靠以计算机硬件。低级语言编写的程序比高级语言编写的程序要快。高级语言编写的程序必需经过编译和连接后才能执行。常用的高级语言有 VisualC+、Visual Basic、Java面对对象编程方法。Lisp,ProLog用于人工智能与专家系统。3、网络通信及其治理软件网络通信及其治理软件主要包括网络协议、网络资源治理、网络任务治理、网络安全治理与网络通信扫瞄工具等功能。在计算机网络中，不同的计算机系统之间进展信息交换时，必需遵循某种共同的商定与 规章，这种商定与规章即为协议。网络协议是按层次划分的。按 ”开放系统网络标准模式” OSI，网
20、络协议分为七层，即应用层、表示层、会话层、传输层、网络层、链路层和物理层。CAD/CAM 流行的主要网络协议有：1) MAP(Manufacturing Automation Protocol)用于工厂自动化2) TOP(Technicality and Office Protocol)用于技术与办公环境3) TCP/IP( Transmission Control Protocol / Internet Protocol) 按报文为传输单位。2.3.2 机械 CAD/CAM 支撑软件支撑软件不为某一具体应用而设计开发的，只为用户供给应用工具和开发环境。从功能 上划分，支撑软件可分为，根本图形
21、资源与自动绘图，几何造型、工程分析与计算、仿真与模拟、专用设备把握程序生成器、集成与治理等6 大局部。1、根本图形资源治理与自动绘图软件根本图形资源软件是依据图形标准或标准实现的软件包，为用户供给的是根本图形及图形操作的程序和函数库。是其他图形软件的根底。常用的有 CGI(计算机图形界面)，GKS图形软件包及PHIGS(程序员等级交互图形系统)等。自动绘图软件供给了各种根本图元与图形根本操作等功能，用户可承受交互式方式完成绘图工作，常用有AutoCAD，CADKey 等。2、几何建模软件。供给完整的三维几何外形的描述与显示。还具有各种图形渲染及物性计算等功能，常用有Pro/E、UGII。3、工
22、程分析与计算利用工程计算及分析软件可完成运动学、动力学、有限元分析等任务，常用的有 Ansys、nastran 等。4、仿真与模拟软件5、工艺过程设计6、治理与集成对各种CAD/CAM 软件所产生的数据进展治理，承受数据库。常用的数据库有Oracle、Sybase、MS SQL Server 、DB2、Informix。2.3.3 应用软件基于系统软件、支撑软件根底之上，专为某种特别应用开发而成应用软件。如机械标准件图库，公差标注工具，电子元器件。2.4 CAD/CAM 系统的设计原则2.4.1 系统设计的总原则在满足需求的前提下，既要实现目标，又要适应技术的进展，还要考虑具有的人才与资金的条
23、件。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 系统应用过程中，不仅要向系统输入大量的数据，同时系统也
24、会产生大量的数据，怎样存储、使用、治理好这些数据是使用好 CAD/CAM 系统的重要任务，也是开发CAD/CAM 软件的根底。3.1 工程数据的程序化在进展机械设计与制造中，会遇见很多格式数据，要实现 CAD/CAM 系统，首先要对这些数据进展计算机化或程序化。3.1.1 数值程序化1、数组形式对于一组单一、准确、而数据之间又无规律的数列，可定义数组进展存放处理。如齿轮标准模数，见P43 表 3.1可定义一个一维数组加以存放与处理。2、公式化对于一组单一、准确、而数据之间又规律的数列可承受公式表达。如 60、70、80、90、100、110、120 这一标准的直径序列，可承受以下公式表达式进展
25、处理D=int(Dc/10.02)*10+10其中Dc 是依据强度计算所得到的直径。3.1.2 数表程序化1、屏幕直观交互式输入法假设数表中的数据量不大，可在有限的屏幕中放置，且数据为有限个离散值，在使用时是依据综合考虑选用中间值，此时可这些数据用屏幕输出语句输到屏幕上供使用者直观交互式地选用。如齿轮传动强度计算中的系数 Kv，此系数是依据原动机工作特性和工作载荷特性等进展综合，在表 3.2 中进展选值可选中间值。表中数据量少，可在有限的屏幕中放置。2、数组化数据量较大，准确且无规律的数表可承受数组进展存储与处理。如平键和键槽与轴径的尺寸关系数表 3.3P45。注：只能选用数表中数据，不能取中
26、间值。3、公式化假设数表中只有两个参数，设 P 、f ，且这两个参数存在一一对应关系，即一个在ii数表中找得到的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,y 、x ,y 、x ,y 、xn,yn序列插值函122ii数。常用
27、的插值方法有线性插值和拉格朗日插值法。1） 线性插值(两点插值)两点，x,y 、x ,y ，并近似地认为其它数据在这两点区间成线性关系，则可承受线1122性插值。插值函数为y - yy- yy- y=1x - x121x- x21y=y1+21x- x21(x-x1)假设有多点，相邻两点用直线段连接，则每段线性插值的一般形式为：yy=yi+ xii- y- xi-1 (x-xi-1)例如：如表 3.4 P47 中蜗轮当量齿数与齿形系数的关系表，i-1当 zv=25.6(即 x=25.6) ( xi-1=24, yi-1=1.88)；( xi=26, yi=1.85)，求YF2） 拉格朗日插值当
28、线性插值误差较大，可承受高次插值二次和二次以上 通过整理线性插值表达式得：f(x)=y=y x - x2+ y x - x11x - x122x- x21二次插值(x - x)(x - x)(x - x)(x - x)(x - x)(x - x )f(x)=y=y 1(x2- x )(x3- x )+ y 2(x1- x )(x3+ y -3x )(x1- x )(x2- x )121321233132对于 n 个节点的n-1 次拉格朗日插值的一般式子有：f(x)=y= ny A其中A =(x - x1)(x - x2)L(x - xi-1)(x - xi+1)L(x - x )niii=1i
29、(xi- x )(x1 i- x )L(x2 i- xi-1)(xi- xi+1)L(xi- x )n4、交互式分级描述法将简洁的多元函数表按确定的原则分解成多个子表，用程序描述各子表之间的关系，通过人机交互式的方式逐步选值。如表 3-5 齿轮常用材料及力学性能 , P48。3.1.3 线图程序化在工程中有很多线图，这些线图有的是通过计算公式所计算数据而来，有的是通过试验 数据而来。对试验数据，由于实际状况的简洁性，很难用公式准确描述，一般承受某种近似曲线公式来加以描述，这种曲线公式就称为阅历公式，建立阅历公式的过程称为曲线拟合。拟合与插值的区分是，插值是必需过插值节点，而拟合是不愿定需要过节
30、点的。1、拟合原理曲线拟合的方法很多，常用的是最小二乘法。1） 线性方程拟合有 n 组试验数据x ，y ，设线性方程的形式：y=a+bxii最小二乘法：为了到达最好的拟合，应使各节点的偏差平方最小，即使。S(a，b)= n ( yii=1- a - bxi)2 最小。S(a，b)有两个参数 a 与 b。承受偏导求出最大值。2） 对数方程拟合有 n 组试验数据x ，y ，设对数方程的形式：y=a+blnxii设 X=lnx，则对数方程的形式为y=a+bX。留意：在利用 3.9 和 3.10 式求 a，b 时，应将 lnxi 代入。ii3） 指数方程拟合有 n 组试验数据x ，y ，设指数方程的形
31、式： y=axb对两边取对数。得lny=lna+blnx。设Y=lny，X=lnx，A=lna，则有 Y=A+bX与线性方程拟合一样求解。4） 对数指数方程拟合略5） 二次方程及屡次方程拟合略3.2 CAD/CAM 中的数据构造在 CAD/CAM 中存在大量的数据，如性能参数，工艺数据、治理数据等。这些数据不是孤立的，他们之间存在作关系。怎样将这些数据进展有效的治理与存储，表达和定义好他们的构造是根底。这就是数据构造问题。3.2.1 根本概念与术语数据：是现实世界客观存在的实体或事物的属性值，即人们感知到的景象。数据可以是数值、字符、文字，也可以是声音、图形图象等。存储数据处理信息信息：是含有
32、确定意义的数据称为信息信息与数据的关系是：1） 信息是有确定含义的数据2） 信息是经过加工处理后的数据3） 信息是对决策有价值的数据现实世界数据、信息与计算机之间的关系如图3.8P56实体：客观存在并可相互区分的事物。属性：实体特性属性值：每一个实体属性所能测量或记录的值。数据属性域：属性取值范围数据按组成的内容可分成假设干层次1） 字符 是组成数据的最小单位。包括数字、字母、特别符号等2） 数据项是数据中最根本的、不行分的、并有命名的数据单位，由字符组成，代表某一数据量。如轴承性能表 3.9P57 中的轴承代号、尺寸、载荷等。3） 组合项由一个或多个数据项组成。如尺寸由四个数据项组成。4）
33、记录：相关数据项或组合项构成的集合称为一条记录，他描述了一个实体。如代号为 6202 轴承对应一行中的各数据项共同描述的某一型号的轴承。记录又称为数据元素。5） 文件 一样性质的记录的集合就是文件。表 3.9中记录全体构成了一个文件6） 数据库 非单纯性即有确定的特点与要求、具有构造文件的集合。3.2.2 数据构造数据元素记录不是孤立的，而是相互有关联的。多个数据元素之间的关系构成一个数据构造，而数据构造又可能是另一个数据构造中的数据元素。即数据构造是可嵌套的。如图 3.9 中的车床构造图。数据构造有规律构造和物理构造之分。1、规律构造规律构造描述的是数据之间的规律关系，它是从客观的角度去组织
34、和表达数据。依据关系特点，规律构造分为线性构造和非线性构造。1） 线性构造数据之间的关系只有挨次排列的位置关系，这种挨次位置关系是线性的。因此这种数据构造称为线性构造，也称为线性表构造。数组就是一种线性构造。在线性构造中，每一数据元素节点或数据域只有一个前趋节点和一个后趋节点。2） 非线性构造当数据构造中的某数据元素有两个或两个以上的前趋或后趋节点，则这种数据构造中的数据元素之间的关系是非线性的，因此此种数据构造称为非线性数据构造。如图 3-9车床零部件关系树状构造和图 3-10 工艺路线方案网状构造 P58图 3-11 表示的是一个几何图形及其数据构造，在这个数据构造中，树状构造与网状构造共
35、存。树状构造：当数据构造中的数据元素有多个前趋，只有一个后趋。网状构造：当数据构造中的数据元素有多个前趋和多个后趋。2、物理构造数据的物理构造是指数据在计算机内部的存储方式，是从物理存储的角度描述数据之间的关系。常用的物理构造有挨次存储构造与链接存储构造两种。1） 挨次存储构造：用一组连续的存储单元依次存放各数据元素。特点：存储挨次与规律挨次全都，只需要存放第一个数据元素的地址，其他元素的地址 是第一个元素地址加上一个相对地址，因此占用存储单元少，简洁，构造紧凑。但缺乏柔性， 当要进展增删操作时，必需重安排存储单元。费时。如数组。2） 链接存储构造在数据元素中，除存放数据外，还存放其他数据的存
36、放地址。这样，在得到第一个元素得地址后，就可以依据第一个数据元素中地址检索出其下一个数据元素的存放地，以此类推。这种物理存储方式称为链接存储构造。在链接存储构造中，每一个数据元素有数据和地址或指针两种域组成。依据指针域的个数，链接存储构造可大致分为三类。（1） 单向链构造在每一个数据元素中，只有一个指向下或上一个数据元素指针域。如图 3-14a假设指针所指的方向与规律挨次一样，则称正向链；如图3-14a 假设指针所指的方向与规律挨次相反，则称为反向链；如图3-14b假设在最终一个数据元素中，有指向第一个数据元素的指针，则此链接构造构成了一个环链；如图 3-14c（2） 双向链构造 在每一个数据
37、元素中，有两个指针，一个指向下一个数据元素，而另一个指向上一个数据元素。双向链也可以构成环链。如图3-14d 和如图 3-14e环链的最大特点是任何一个数据元素都可以是数据存取的入口点，存取效率高。（3） 多向链构造 在数据构造中，某些数据元素有两个以上的指向其他数据元素的指针域。多向链构造一般用于矩 、树状等数据构造存储。如图 3-14f3.2.3 常用的数据构造1、线性表12n12n线性表是一个由 nn=0个数据元素a ，a ，a 组成的有限序列，表中的每一个数据元素，除第一个和最终一个外，仅有一个直接前驱和一个直接后继。当n=0 时， 称为空表。线性表的规律表示可为：a ，a ，a ，如
38、轴径序列值3，6，10，14， 18，24，30，40，50，65，.线性表的物理存储构造既可以承受挨次存储，也可以承受链接存储构造。2、栈与队列1） 栈 当对线性表的删除与插入操作只能在表的一端进展时，线性表就变成了栈。在栈中，允许插入与删除的端称为栈顶，而另一端称为栈底。栈的操作是按后进先出的 原则进展的，因此栈也称为后进先出表LIFO。实际生活中，栈的例子很多。如穿衣服，火车换道。栈的示意图如图 3-16。举例 2 5 3 4 按挨次入栈，出栈有几种挨次？栈的物理存储构造可以是挨次，也可以是链接。在挨次栈中，要有一个栈顶指示器和一个栈顶界限限制栈的空间。2） 队列 当对线性表的删除与插入
39、操作限制只在一端插入，在另一端删除时，线性表就变成了队。允许插入的一端称为队尾，而允许删除的一端称为队头。栈的操作是按先进先出的原则进展的，因此队也称为先进先出表LIFO。实际生活中，队的例子很多。如排队买东西，如图 3-18。队的物理存储构造可以是挨次，也可以是链接。在挨次队中，要分别设置队头指针和队尾指针以及一个队尾界限限制队的空间。队“溢出”与“假溢出”，参见 P 62.承受循环队解决“假溢出”问题。 3、数组数组是一种按挨次排列与存储、并且每个数据元素具有一样的数据类型的特别线性表。4、串是一种特别的数组，其数据元素中数据为字符类型。5、树与二叉树1树栈、队、数组与串都是线性构造，不能
40、解决实际中非线性问题，如行政单位构造，产品构造等问题。这就需要各种非线性构造。树是一种常用的非线性构造，其定义为当数据元素集合中的每一个数据元素都一个或多 个后继，而只有一个前驱，并且处于最高层的那个数据元素没有前驱。这样的数据构造称为 树。没有前驱的最高层的那个数据元素节点称为树根；树的最大层次称为树的深度；节点的后继子树个数称为度；度数或后继为零的节点称为树叶。用例子图 3-21 说明这些概念。P63树的物理构造可以是挨次、也可以是链接。2） 二叉树当树具有以下特点时，就称其为而叉树。（1） 可以没有任何数据节点，即为空。树必需具有至少一个根节点。（2） 每一个节点的度不能超过 2。树则无
41、限制；（3） 二叉树的子树有左右之分，不能颠倒。树的子树无左右之分，可以交换位置。 二叉树的物理存储构造常承受链接构造，其每个节点有一个左指针域和一个右指针域。这种构造与二叉树的规律构造全都。3） 二叉树的遍历按确定规律，不重复地访问树中的每一个节点，这种操作称为遍历。对于二叉树，有三中遍历方式，即前序、中序和后序。具体算法见P64。举例说明三种遍历方法的算法。参见图3-24P65 6、图与网在一个数据构造中，每一个节点数据元素可以有多个直接的前驱和后继时，这种数据构造称为图。图由顶点与边组成，见图 3-25P65设V 是顶点集合，E 是边的集合，则图G 可用下式表示：G=(V,E)假设顶点之
42、间是有序的，则边是有方向的，如图 3-25G3P65，这种图称为有向图。否则称为无向图。树与图的关系：树是一种特别的图。图3-25 中的图G2，即是图，也是树。P65通常用n 阶邻接方阵来表示n 个顶点的图的规律构造。邻接矩阵中每个元素定义如下：V(i,j)=1假设Vi 与Vj 相连0假设Vi 与Vj 不相连参见图 3-26 说明图及其邻接矩阵。当图的边有权重时，图的邻接变为V(i,j)=Wij假设 Vi 与Vj 相连0假设Vi 与Vj 不相连此时图称为网。参见图 3-27 说明网及其邻接矩阵。3.3 数据文件文件是数据治理的一种形式，它能独立于应用程序单独存储。文件用于数据的治理、交换等。文
43、件是记录的集合，文件记录中唯一能够记录的数据项的称为关键字。如表3-10 齿轮参数表P67中的零件编号就是齿轮参数文件的关键字。1、常用的文件组织方法1） 挨次文件物理存储挨次与其规律挨次全都。其存储是连续的，构造紧凑简洁，但 增删、查询算法较为简洁，时间度与空间度较大。有一些存储设备只能存储挨次文件，如磁带。2） 索引文件 带有一个包括关键字与记录存放地址索引表的文件称为索引文件。索引文件查询方法是：先按关键字到索引文件中查到该关键字所对应的记录存放地址， 在依据地址到数据文件中去查找记录。索引文件的索引表必需按关键字按挨次排序。而文件本身可以排序或不排序。假设文件本身排序称为索引挨次文件，
44、否则称为索引非挨次文件。3） 直接存取文件 又称为随机文件。承受一种算法将记录的关键字转换为一个随机数，依据这个随机数确定记录在存储器中存放的位置。2、文件的操作文件的操作主要是查询与排序。1） 查询 即查找关键字为某值的记录常用的查找方法有挨次、折半和分块等三种查找方法。（1） 挨次查找法从第一条记录开头，逐条查找，假设查找到欲查数值则查找完毕。此方法最为简洁，但效率低。（2） 折半查找法也叫二分查找法原理是：先将文件记录按关键字大小挨次排序，再将位置为中间的记录的关键字值Km 与欲查值 K 进展比较，比较结果有三种，KmK、KmK KmK。假设 KmK，则欲查记录在文件前半区；假设KmK，则欲查记录在文件后半区；假设Km=K，则查到欲查记录， 查找完毕。假设为前两种状况，则在前半区或后半区连续进展。（3） 分块查找原