机械CADCAM技术全册配套最完整精品课件2.ppt

1、机械机械CADCAM技术全册配套最技术全册配套最 完整精品课件完整精品课件2 机械CAD/CAM技术 3 第一章第一章 概述概述 第一节 CAD/CAM的基本概念 第二节 CAD/CAM的发展历史 第三节 CAD/CAM的发展趋势 第四节 我国CAD/CAM的发展状况 4 随着人们生活水平的提高，消费者的价值观 正在发生结构性的变化，呈现出多样化与个性化多样化与个性化, 用户对各类产品的质量、产品的更新换代的速度、 以及产品从设计、制造到投放到市场的周期都提 出了越来越高的要求。为了适应这种变化，工厂 的产品也向着多品种、中小批量方向发展。要适 应这种瞬息万变的市场要求瞬息万变的市场要求，则要

2、求生产更具有 柔性。计算机辅助设计(CAD)与计算机辅助制造 (CAM)就是满足这种新的要求而产生的一种新的 制造方法。 引言引言 5 第一节第一节 CAD/CAMCAD/CAM的基本概念的基本概念 产品生产过程与CAD/CAM 6 一一CAD/CAMCAD/CAM的基本概念的基本概念 1. .CAD (Computer Aided Design System) 是指以计算机为辅助手段来完成整个产品的设计过程， 广义的CAD 包括设计和 分析两个 方面。 7 2. CAM( Computer Aided Manufacturing System) 通过计算机与生产设备直接的或间接的联系,进 行

3、规划、设计、管理和控制产品的生产制造过程。 关于CAM的概念有两种理解： (1)狭义的CAM，数控编程与数控机床数控装置 的软件接口。 (2)广义的CAM，除自动编程以外，还包括工艺 过程的设计(CAPP)、制造过程仿真(MPS)、自动化 装配、车间生产计划、制造过程检测和故障诊断、 产品装配与检测等。 8 9 3.CAPP3.CAPP（Computer Aided Process PlanningComputer Aided Process Planning） 借助计算机来完成毛坯设计，工艺规程设 计，工装设计等任务，称为CAPP。 4.CAD/CAM4.CAD/CAM集成技术集成技术 CA

4、D产生的图纸直接被CAPP，CAM以及以 后的CIMS所利用，这就是CAD/CAM集成。 10 二二CAD/CAMCAD/CAM的组成的组成 CAD/CAM CAD/CAM 的组成的组成 11 硬件组成主要是指计算机及各种配件设备，如各 种档次的计算机、打印机、绘图机、数控机床等。 1 1）对硬件的主要要求是：）对硬件的主要要求是： 具备强大的人机交互功能 需要有相当大的外存储容量 良好的联网通信功能 1 1硬件组成硬件组成 12 2 2）CAD/CAMCAD/CAM硬件的类型硬件的类型 根据系统总体配置、组织方式及所用计算机的 不同，有不同的分类方法。 （1）按系统总体配置分类 主机系统 成

5、套系统 超级微型工作站 个人计算机系统 13 （2）按系统的组织方式分类 单机系统：单机系统： 联机系统：联机系统： 系统的网络拓扑结构：系统的网络拓扑结构：总线型拓扑结构，星型拓扑 结构，环型拓扑结构，网状型拓扑结构，混合型拓扑结 构。 14 2 2软件组成软件组成 CAD/CAM系统的软件运行环境，可分为3个层次： 系统软件 支撑软件 应用软件 (1)(1)系统软件系统软件 主要负责管理硬件资源和各种软件资源，它面 向所有用户，是计算机的公共性底层管理软件，即 系统开发平台。 系统软件主要包括三个部分：操作系统、网络 系统和窗口系统，如Windows98、Windows2000等。 15

6、16 (2)(2)支撑软件支撑软件 定义 是目前市场上供应的各种商品化CADCAM系统。是在系统软件 基础上开发出来的满足CAD用户一些需要的通用软件或工具软件， 是CAD/CAM系统的核心。 主要功能 CAD（二维绘图，三维线框、曲面、实体造型，真实感显示，特 征设计）； CAE（有限元前、后置处理，运动机构造型，几何特性计算，静 态、动态、热特性分析）； CAM（数控加工和测量编程，工艺过程设计）； 装配设计，钣金件展开和排样，加工尺寸精度控制，过程仿真和 干涉检查，工程数据管理和技术文件签发系统等。 引进软件 Unigraphics, ProEngineer， Computer Visi

7、on，Intergraph，CATIA， SDRC-IDEAS，Euclid，Applicon，DUCT，Medusa， CDC/ICEM，CADAM，Mastercam，Calma，Auto-trol，Gerber 国内软件 北航CAXA、华中开目CAD等 17 绘图软件 例如 Auto CAD绘图软件 几何建模软件 例如 Pro-E UG 软件 有限元分析软件 例如 SAP 软件 优化方法软件 例如 OPB软件 数据库系统软件 例如 SQL Server 数据库系 统软件等 系统运动学/动力学仿真软件 例如 ADAMS机械 动力学自动分析软件 网络系统软件 NOVELL公司的NET WAR

8、E (2)(2)支撑软件续支撑软件续 18 (3)(3)应用软件应用软件 定义 是用户解决实际问题而自行开发或委托开发的程序 系统。它是在系统软件的基础上，或用高级语言编 程，或基于某种支撑软件，针对特定的问题设计研 制，既可为一个用户使用，也可为多个用户使用的 软件。 分类 对CAD而言，按系统运动时设计人员介入的程度， 以及系统的工作方式，可分为检索型，自动型，交 互型，智能型。 开发应 用软件 应遵循 的原则 使用方便、记忆最少原则、可以容忍的响应时间、 灵活的提示信息、良好的工作方式、良好的出错处 理 3.CAD/CAM3.CAD/CAM软硬件系统层次关系软硬件系统层次关系 19 20

9、 1 1CAD/CAMCAD/CAM系统的基本功能系统的基本功能 图形显示功能 输入输出功能 存储功能 交互功能 (即人机接口) 三三CAD/CAMCAD/CAM功能与任务功能与任务 21 2 2 CAD/CAMCAD/CAM系统的主要任务系统的主要任务 （P7P7） 几何造型 计算分析 工程绘图 结构分析 优化设计 计算机辅助工艺规程设计 (CAPP) NC自动编程 模拟仿真 工程数据管理 特征造型 二次开发 22 1952年由空军部门委托帕森斯公司和麻省理工学 院伺服机构研究所试制成功世界上第一台数控机床。 1955年研制出APT编程系统，并用于加工复杂的零件曲 面。 1962年，麻省理工

10、学院的研究生I.E.Sutherland发 表了人机对话图形通讯系统的论文，推出了二维 SKETCHPAD系统，该系统容许设计者在图形显示器前 操作光笔和键盘，同时在屏幕上显示图形。他的论文首 次提出了计算机图形学，交互技术及图形符号的存储采 用分层的数据结构等思想，为CAD技术提供了理论基础。 第二节第二节 CAD/CAMCAD/CAM的发展历史的发展历史 23 1969年挪威正式发表了AUTOPROS系统。它是根据 成组技术的原理，利用零件的相似性准则去检索和修 改零件的标准工艺来制定相应的零件工艺规程的，这 是开发得最早的CAPP系统。 70年代中期小型计算机出现。由于其较低的价格， 高

11、超的数据处理和输入输出功能，使它迅速应用到数 控机床的控制系统中，出现了所谓的计算机数控系统 (CNC)。 70年代以后，随着CNC技术的不断发展， DNC发 展为分布式数字控制。 24 80年代初CAD开始全面打入市场。 80年代以后，随着计算机技术、通讯技术和CIMS 技术的发展，DNC的内涵和功能不断扩大。 90年代技术上最大进展莫过于信息技术，信息高 速公路和互联网的发现，使世界在20世纪的最后十年 里发生了巨大的变化。计算机硬件、软件、通讯技术 的进步把制造业带进了新的发展阶段，数控机床的控 制系统进入“以PC机为平台、开放式结构、无产权” 的新阶段。 25 1CAD/CAM系统的集

12、成化方向发展 2向CAD/CAM智能化方向发展 3向CAD/CAM网络化方向发展 4并行工程 5面向先进制造技术的CAD技术的发展 6虚拟设计技术 第三节第三节 CAD/CAMCAD/CAM的发展趋势的发展趋势 26 Unigraphics(UG) UG是UnigraphicsSolutions公司的拳头产品。该公 司首次突破传统CAD/CAM模式，为用户提供一个全面的 产品建模系统。 UG最早应用于美国麦道飞机公司。它是从二维绘图、 数控加工编程、曲面造型等功能发展起来的软件。90年 代初，美国通用汽车公司选中UG作为全公司的 CAD/CAE/CAM/CIM主导系统，进一步推动了UG的发展。

13、 1997年10月UnigraphicsSolutions公司与Intergraph公 司签约，合并了后者的机械CAD产品，将微机版的 SOLIDEDGE软件统一到Parasolid平台上。由此形成了一 个从低端到高端的企业级CAD/CAE/CAM/PDM集成系统。 目前国内国外流行的目前国内国外流行的CAD/CAMCAD/CAM软件软件 国外软件国外软件 27 SOLIDEDGE SOLIDEDGE是真正Windows软件。它不是将工作站软件生 硬地搬到Windows平台上，而是充分利用Windows基于组件对象 模型(COM)的先进技术重写代码。SOLIDEDGE与 MicrosoftOf

14、fice兼容，与Windows的OLE技术兼容，这使得设计 师们在使用CAD系统时，能够进行Windows下字处理、电子报 表、数据库操作等。 SOLIDEDGE具有友好的用户界面，它采用一种称为 SmartRibbon的界面技术，用户只要按下一个命令按钮，既可以 在SmartRibbon上看到该命令的具体的内容和详细的步骤，同时 在状态条上提示用户下一步该做什么。 SOLIDEDGE是基于参数和特征实体造型的新一代机械设计 CAD系统，它是为设计人员专门开发的，易于理解和操作的实体 造型系统。 28 3AutoCAD AutoCAD是Autodesk公司的主导产品。Autodesk公司 是世

15、界第四大PC软件公司。目前在CAD/CAE/CAM工业领域 内，该公司是拥有全球用户量最多的软件供应商，也是全球 规模最大的基于PC平台的CAD和动画及可视化软件企业。 Autodesk公司的软件产品已被广泛地应用于机械设计、建筑 设计、影视制作、视频游戏开发以及Web网的数据开发等重 大领域。 AutoCAD是当今最流行的二维绘图软件，它在二维绘图 领域拥有广泛的用户群。AutoCAD有强大的二维功能，如绘 图、编辑、剖面线和图案绘制、尺寸标注以及二次开发等功 能，同时有部分三维功能。AutoCAD提供LISP、ADS、 ARX作为二次开发的工具。在许多实际应用领域(如机械、建 筑、电子)中

16、，一些软件开发商在AutoCAD的基础上已开发 出许多符合实际应用的软件。目前，Autodesk公司已经发布 AutoCAD2012。 29 4MDT MDT是Autodesk公司在PC平台上开发的三维机械CAD系统。 它以三维设计为基础，集设计、分析、制造以及文档管理等多种 功能为一体；为用户提供了从设计到制造一体化的解决方案。 MDT 具有基于特征的参数化实体造型功能。 基于NURBS的曲面造型，可以构造各种各样的复杂曲面，以 满足如模具设计等方面对复杂曲面的要求。 可以比较方便地完成几百甚至上千个零件的大型装配。 MDT提供相关联的绘图和草图功能，提供完整的模型和绘图 的双向联结。 该软

17、件的推出受到广大用户的普遍欢迎。至今为止，全世界 累计销售已达万套，国内已销售近千套。由于该软件与 AutoCAD同时出自Autodesk公司，因此两者完全融为一体，用户 可以方便地实现三维向二维的转换。MDT为AutoCAD用户向三维 升级提供了一个较好的选择。 30 5SolidWorks 生信国际有限公司推出的基于Windows的机械设计 软件。生信公司是一家专业化的信息高速技术服务公司， 在信息和技术方面一直保持与国际市场同步。该公司提 倡的“基于Windows的CAD/CAE/CAM/PDM桌面集成系 统”是以Windows为平台，以SolidWorks为核心的各种 应用的集成，包括

18、结构分析、运动分析、工程数据管理 和数控加工等，为中国企业提供了梦寐以求的解决方案。 SolidWorks是基于Windows平台的全参数化特征造 型软件，它可以十分方便地实现复杂的三维零件实体造 型、复杂装配和生成工程图。图形界面友好，用户上手 快。该软件可以应用于以规则几何形体为主的机械产品 设计及生产准备工作中，其价位适中。 31 6Cimatron 是以色列Cimatron公司的CAD/CAM/PDM产品，是较早在微 机平台上实现三维CAD/CAM全功能的系统。该系统提供了比较 灵活的用户界面，优良的三维造型、工程绘图，全面的数控加 工，各种通用、专用数据接口以及集成化的产品数据管理。

19、 CimatronCAD/CAM系统自从80年代进入市场以来，在国际 上的模具制造业备受欢迎。近年来，Cimatron公司为了在设计 制造领域发展，着力增加了许多适合设计的功能模块，每年都 有新版本推出，市场销售份额增长很快。1994年北京宇航计算 机软件有限公司(BACS)开始在国内推广Cimatron软件，从8版 本起进行了汉化，以满足国内企业不同层次技术人员应用需求。 用户覆盖机械、铁路、科研、教育等领域，目前已销售200多 套，市场前景看好 32 7. Pro/Engineer Pro/Engineer系统是美国参数技术公司(PTC)的产品。PTC 公司提出了单一数据库、参数化、基于特

20、征、全相关的概念， 这种全新的概念已成为当今世界机械CAD/CAE/CAM领域的新 标准。利用该概念开发出来的Pro/Engineer软件能将设计至生 产全过程集成到一起，让所有的用户能够同时进行同一产品的 设计制造工作，即实现所谓的并行工程。 Pro/Engineer系统实现了真正的全相关性，任何地方的修 改都会自动反映到所有相关地方；具有真正管理并发进程、实 现并行工程的能力；具有强大的装配功能，能够始终保持设计 者的设计意图；容易使用，可以极大地提高设计效率。 Pro/Engineer系统用户界面简洁，概念清晰，符合工程人 员的设计思想与习惯。整个系统建立在统一的数据库上，具有 完整而统

21、一的模型。Pro/Engineer建立在工作站上，系统独立 于硬件，便于移植。 33 1.高华高华CAD 高华CAD是由北京高华计算机有限公司推出的CAD产品。该 公司是由清华大学和广东科龙(容声)集团联合创建的一个专门从 事CAD/CAM/PDM/MIS集成系统的研究、开发、推广、应用、 销售和服务的专业化高技术企业。 高华CAD系列产品包括计算机辅助绘图支撑系统GHDrafting、 机械设计及绘图系统GHMDS、工艺设计系统GHCAPP、三维几 何造型系统GHGEMS、产品数据管理系统GHPDMS及自动数控 编程系统GHCAM。其中GHMDS是基于参数化设计的 CAD/CAE/CAM集成

22、系统，它具有全程导航、图形绘制、明细表 的处理、全约束参数化设计、参数化图素拼装、尺寸标注、标准 件库、图像编辑等功能模块。GHGEMS5.0曾获第二届全国自主 版权CAD支撑软件评测第一名。 目前国内国外流行的目前国内国外流行的CAD/CAMCAD/CAM软件软件国内软件国内软件 34 2CAXA电子图板和电子图板和CAXA-ME制造工程师制造工程师 CAXA电子图板和CAXA-ME制造工程师软件的开发与销售单 位是北京北航海尔软件有限公司(原北京航空航天大学华正软件 研究所)。该公司是从事CAD/CAE/CAM软件与工程服务的专业 化公司。 CAXA电子图板是一套高效、方便、智能化的通用中

23、文设计绘 图软件，可帮助设计人员进行零件图、装配图、工艺图表、平面 包装的设计，适合所有需要二维绘图的场合，使设计人员可以把 精力集中在设计构思上，彻底甩掉图板，满足现代企业快速设计、 绘图、信息电子化的要求。 CAXA-ME是面向机械制造业的自主开发的、中文界面、三维 复杂形面CAD/CAM软件。CAXA制造工程师1.0版于1996年推出， CAXA-ME2.0版于1998年3月发布，CAXA-ME2000版业已发布。 35 3GS-CAD98 GS-CAD98是浙江大天电子信息工程有限公司开发的基于 特征的参数化造型系统。该公司是国家科委高技术研究发展中 心、浙江大学和中国航天总公司CAD

24、/CAM中心在杭州联合创 建的高新技术研究、开发和应用企业。大天公司集软件开发、 工程应用、信息系统集成和计算机类产品销售为一体，是从事 CAD/CAPP/CAM工程数据库和MIS/OA的开发、应用、销售和 服务的专业化高技术公司。 GS-CAD98是一个具有完全自主版权、基于微机、中文 Windows95/NT平台的三维CAD系统。该软件是在国家“七五” 重大攻关及863/CIMS主题目标产品开发成果的基础上，参照 SolidWorks的用户界面风格及主要功能开发完成的。它实现了 三维零件设计与装配设计，工程图生成的全程关联，在任一模 块中所做的变更，在其他模块中都能自动地做出相应变更。 3

25、6 4金银花系统金银花系统 金银花(Lonicera)系统是由广州红地技术有限公司开发的基 于STEP标准的CAD/CAM系统。该系统是国家科委863/CIMS 主题在“九五”期间科技攻关的最新研究成果。 该软件主要应用于机械产品设计和制造中，它可以实现设 计/制造一体化和自动化。该软件以STEP为系统设计的依据， 采用面向对象的技术，使用先进的实体建模、参数化特征造型、 二维和三维一体化、SDAI标准数据存取接口的技术;具备机械产 品设计、工艺规划设计和数控加工程序自动生成等功能;同时还 具有多种标准数据接口，支持产品数据管理(PDM)。 目前金银花系统的系列产品包括:机械设计平台MDA、数

26、控 编程系统NCP、产品数据管理PDS、工艺设计工具MPP。 机械设计平台MDA(MechanicalDesignAssistant)是金银花系 列软件之一，是二维和三维一体化设计系统。目前，MDA1.7版 已投放市场，MDA99版也已发布。“金银花”MDA在国内率先 实现商品化，并向国外三维CAD软件发出了强有力的挑战。 37 5.开目开目CAD 开目CAD是华中理工大学机械学院开发的具有自主版权的 基于微机平台的CAD和图纸管理软件，它面向工程实际， 模拟人的设计绘图思路，操作简便，机械绘图效率比 AutoCAD高得多。 开目CAD支持多种几何约束种类及多视图同时驱动，具有 局部参数化的功

27、能，能够处理设计中的过约束和欠约束的 情况。 开目CAD实现了CAD、CAPP、CAM的集成，适合我国设 计人员的习惯，是全国CAD应用工程主推产品之一。 38 CAD/CAMCAD/CAM系统的选择原则系统的选择原则 一、硬件选择原则一、硬件选择原则 1、系统功能 2、系统的开放性和可移植性 3、系统升级扩展能力、系统可靠性、 可维护性 和服务质量。 39 二、软件选择原则二、软件选择原则 1、软件性能价格比 2、与硬件匹配 3、二次开发环境 4、开放性 5、软件商的综合能力 40 第四节第四节 我国我国CAD/CAMCAD/CAM的发展状况的发展状况 我国开展CAD/CAM技术应用工作并不

28、算晚；通过引 进，不少企业的软、硬件条件与国外相比也相差不大。 但是，国内的CAD/CAM应用与国外先进水平相比存在较 大的差距。原因是： (1) 原有经济体制的弊端。 （2）管理上的缺陷。 （3）人才培养的不足。 41 近年来，我国CAD技术的开发和应用取得了长 足的发展，除对许多国外软件进行了汉化和二次开 发以外，还诞生了不少具有自主版权的CAD系统。 价格便宜，符合本国国情和标准，受到了广泛的欢 迎。 机械制造是最早也是最广泛应用CAD/CAM技术 的领域。随着CAD/CAM技术的发展，建筑、电子、 化工的领域也开始应用该技术，在这些新的应用领 域中，国外软件的优势并不明显。 42 工厂

29、中比较典型的有：工厂中比较典型的有： 第一汽车制造厂和第二汽车制造厂，天津内燃机 研究所完成的“建立汽车计算机 辅助设计和辅助制 造系统”项目 洛阳拖拉机厂开发的轮式拖拉机的计算机辅助设 计系统 杭州汽轮机厂的CAD/CAM系统可以大大提高工厂的 市场的应变能力。 国内国内CAD/CAMCAD/CAM研究和应用成果研究和应用成果 43 国内的高等院校和研究所成果国内的高等院校和研究所成果 典型二维自主版权软件软件有华中科技大学的开目 CAD、凯图CAD， 北京航空航天大学的CAXA软件、 PANDA软件，清华大学和华中科技大学共同研制的 CADMIS系统实现了参数化特征造型、曲面造型、数 控加

30、工、有限元分析的集成。 在数控方面南京航空航天大学的超人CAD/CAM和华 中理工大学的GHNC均实现了复杂曲面的造型和数控 代码的自动生成。 小结小结 通过本章学习，了解CAD/CAM的基本概念、组成、功 能及任务、发展趋势及现在市场上主要CAD/CAM系统软件 。 思考题:1、3、4、5、6、7 44 机械CAD/CAM技术 主编：蔡汉明 陈清奎 机械工业出版社 46 第二章第二章 CADCAD中常用的数据结构中常用的数据结构 第一节 概述 第二节 线性表 第三节 栈、队列和数组 第四节 树结构 47 l用计算机语言编写数值计算程序时，首先需要对变量 进行数据类型说明，才能把数据提供给变量

31、，由计算机 对其进行存取和计算等操作。如C语言中的整型、浮点 型等，数据类型实际上是语言系统提供的数据结构。 l计算机不仅要处理数值计算问题，还要大量地处 理包括图形、图像、文字、表格、声音等各种各样复杂 的问题，这时提供给计算机的已不只是简单的、孤立的 数据，而是存在某些关系的数据。 引言引言 13 35 52 24 41 12 23 34 45 51 X 1 Y 1 X 2 Y 2 X 3 Y 3 X 4 Y 4 X 5 Y 5 (a)五个顶点(b)五边形(c)五角形 (a)五边形与屋角形 12 3 4 5 12 3 4 5 12 3 4 5 49 第一节第一节 概述概述 1、 数据 数据

32、是描述客观事物的数字、字 符及所有能输入到计算机中并可被计算机 接受和处理的各种符号的集合。 2、 数据元素 数据元素是数据的基本单位， 是数据这个集合中的一个个体。 3、 数据的逻辑结构和物理结构 l数据的逻辑结构仅考虑数据之间的 逻辑关系，数据结构一般指数据的 逻辑结构。它独立于数据的存储介 质。 l数据的物理结构也称存储结构，是 数据的逻辑结构在计算机中的映象。 计算机处理数据的最小单位叫做位(Bit)，一个位 表示一个二进制的数，若干位组合起来形成一个 位串。 用一个位串表示一个数据元素，称这个位串为一 个节点。节点是数据元素在计算机中的映象。 映象的方法不同，数据元素在计算机中的存储

33、结 构也不同。顺序映象得到顺序的存储结构，非顺 序映象得到非顺序的存储结构。 4数据类型 数据类型是程序设计语言确定变量所具有的种类 。每种程序设计语言都提供一组基本的数据类型 。如整型、实型、双精度型、复型、逻辑型、字 符型数据类型等； 程序设计语言还可以将不同类型的数据组合成一 个有机的整体，构造出新的数据类型用来实现各 种复杂的数据结构的运算。 1线性表的逻辑结构 第二节第二节 线性表线性表 线性表是一种最常用、最简单的数据结构，是 n(no)个数据元素的有限序列。可表达成下述 逻辑结构： (a1,a2,a3,ai-1,ai,ai+1,an-1,an) 其中ai可以是一个数、是一个符号，

34、还可以是 一个线性表，甚至是更复杂的数据结构。 当no时，线性表中的每一个元素，除第一个 及最后一个外，每个元素有且只有一个直接前趋 ，有且只有一个直接后继。 线性表中数据元素的数量定义为线性表的长度。 2线性表的顺序存储结构线性表的顺序存储结构 线性表在计算机存储器中的存储形式，可以按照 数据元素的逻辑顺序依次存放，即用一组连续的 存储单元依次存放各个数据元素，这种存储形式 称为顺序存储结构。 假定每个数据元素占用l个存储单元，第一个数 据元素占用的第一个存储单元的地址为Loc(a1) ，则第t个数据元素的存储位置为: Loc(at)=Loc(a1)+(t-1)*l 线性表顺序存储结构的持点

35、 (1)均匀性 每个数据元素所占存储空间的长度相同 。 (2)有序性 各数据元素之间的存储顺序与逻辑顺序 一致。 顺序存储情况下线性表的删除和插入 1从线性表中删 除一个数据元 素 2将一个新的 数据元素插入到 线性表 ABCDE ABDE 删除前 删除后 ABCDE ABICDE 插入前 插入后 3、线性表的链式存储结构 1链式存储结构的待点 用一组任意的存储单元存放线性 表的数据元素。由于这些存储单 元可以是不连续的，为了表示这 些元素的线性逻辑关系，除了存 储元素本身的数据信息外，还要 存储这个元素直接后继或直接前 趋的存储位置。 这两种信息的存储映象，称为结 点。结点包含两种域，存放数

36、据 元素本身的域称为数据域，存放 直接后继或直接前趋的域称为指 针域。 数据域 (data) 指针域 (next) 2.单向链表 （1）建立单向链表 （2）删除单向链表的一个元素 ABCDE head ABCDE head 删除前 删除后 /用C语言建立单向链表的程序清单 #include #include #define MAX 5 struct link char data; /定义结点结构 struct link *next; *head; main() int i; struct link *node, *temp; for(i=0; idata=A+i; node-next=NULL

37、; if(i=0) head=temp=node; else temp-next=node; temp=node; /用C语言建立删除单向链表中一个元素的程序清单 void delete_link(struct link *node) int i,j; struct link *temp; printf(删除第几个元素); scanf(%d, if(iMAX) printf(超出链表范围); return(-1); j=1; node=head; if(inext; free(node); return; while(node) if(j+=i-1) temp=node-next; node-

38、next=temp-next; free(temp); return; node=node-next; （3）向单向链表插入一个数据元素 AB CDE head插入前 M AB CDE head插入后 M 双向链表的特点 ： 不但能方便地 找到其直接后继 ，也能方便地找 到其直接前趋 指针域指针域 (next) 数据域数据域 (data) 指针域指针域 (last) 3. 双向链表双向链表 双向链表的建立、删除和插入运算 (1)双向链表的建立 (2) 双向链表的删除 EDCBA rear head EDCBA rear head /用C语言建立双单向链表的程序清单 #include #incl

39、ude #define MAX 5 struct link struct link *last; char data; /定义结点结构 struct link *next; *head,*rear; main() int i; struct link *node, *temp; for(i=0; ilast=NULL; node-data=A+i; node-next=NULL; if(i=0) head=temp=node; else temp-next=node; node-last=temp; temp=node; rear=temp; （3）双向链表的插入 rear EDCBA hea

40、d M rear EDCBA head M 4. 循环链表 ABCDE EDCBA head head 单向循环链表 双向循环链表 链表与线性表相比较，有以下特点： (1)删除或插入运算，数据元素不需要移动； (2)不需要事先分配存储空间，因此不存在空间 浪费； (3)表的容量根据需要实行动态申请和动态释放 ，存储空间利用效率高； (4)按逻辑位置进行查找的速度慢。 因此，链表比较适合用于事先难以确定表的容 量大小，并且增删操作频繁的场合。 第三节 栈和队列 1、栈 栈是一种特殊形式的表。表的一端是封闭的，另 一端是开口的。 对表只能在开口的一端进行删除（出栈）和插入 （进栈）运算，这一端称为

41、栈顶，另一端称为栈底 。 设TOP为栈顶指针，则： 出栈操作 (1） y=S(TOP) (2) TOP=TOP-1 进栈操作 (1）TOP=TOP+1 (2) S(TOP)=s 当栈满时再有元素进栈，栈将溢出，称为“上溢”； 当栈空时作出栈运算，栈也将溢出，称为“下溢”。 an a3 a2 a1 进栈 出栈 栈底 栈顶 2队(或称队列) 队列是一个两端均开口的线性表，元素只能从表的一 端插入，在表的另一端删除。 表中允许插入的一端称为“队尾”，允许删除的一端 称为“队头”。 入队出对 对头指针队尾指针 树是一类重要的非线性数据结构，元素之间存在明显的 层次关系。 几何形体的分解 第四节 树和二

42、叉树 l树的定义： 树是由一个或多个结点组成的有限集T，其中有一个 特定的称为根的结点s其余结点可分为n(no)个互不相 交的有限集T1,T2,T3,Tn其中，每一个集合本身又是一 棵树，并且称为该树的子树。 l树形结构描述了数据之间的分支关系，即层次关系，其 结构形式上很像一棵倒过来的树，树形结构由此得名。 1 树 树的逻辑结构 2 二叉树 1二叉树的定义 二叉树的每个结点至多有两棵子树，子树有左右 之分，不能颠倒。二叉树可以是空的。 二叉树与一般树的区别在于： (1)一般树至少要有一个结点，但二叉树可以是 空的。 (2)一般树的每一个结点可以有任意多个子树， 但在二叉树中，每个结点的子树数

43、不能超过2 。 ” (3)一般树中结点的子树不必区分它们之间的次 序，而二叉树中的子树有左右之分，其次序不 能颠倒。 二叉树的五种基本形态： (a)空二叉树； (b)只有一个根结点的二叉树； (c)只有左子树的二叉树； (d)只有右于树的二叉树， (e)左右子树均存在的完全二叉树。 二叉树的存储结构 二叉树 存储结构形式 结点的构造 遍历二叉树 六种遍历二叉树的方案，令D表示根结点，L表示 左子树、R表示有子树。 (1)左子树、根结点、右子树(LDR)； (2)左子树、右于树、根结点(LRD)； (3)根结点、左子树、右子树(DLR)； (4)根结点、有子树、左子树(DRL); (5)右子树、

44、根结点、左子树(RDL)； (6)右子树、左子树、根结点(RLD)。 如果按先左后右的次序，则只有前三种遍历方式 ： LDR-中序遍历 LRD-后序遍历 DLR-先序遍历 二叉树中序遍历示意图 三种遍历方法遍历该树的结果： (1)中序遍历(LDR)结果：C，B，E，D，A，G，H，I，F，J (2)后序遍历(LRD)结果：C，E，D，B，I，H，G，J，F，A (3)先序遍历(DLR)结果：A，B，C，D，E，F，G，H，I，J 中序遍历的算法 中序遍历示意图 中序遍历的算法框图 TOP 栈顶指针 P指向结点的指针 N Y 3. 二叉排序树 排序就是对一组无序 的数据按递增或递减 的规律重新排

45、列。 二叉排序树是树形结 构的一种简单应用， 它可以把原来是无序 的线性表变成有序的 线性表。 对数组18,14,22,7,17,20,35,27, 11,3,20的排序结果 假设： 如果一棵二叉排序树不空，那么 根结点上所有左子树上的结点都 小于根结点，所有右子树上的结 点都不小于根结点。这个定义也 是一个递归的定义。 建立二叉排序树的算法： 设有一个序列Tt1,t2,t3,tn (1)令t1为二叉树的根结点 (2)以ti与二叉树的根结点作比较：若ti小 于根结点，则将ti插入到左子树中； 否则插入到有子树中； (3)对ti (i2，3，n)所有的递归重 复步骤(2)即可。 中序遍历二叉树变

46、量定义 #include stdafx.h #include stdio.h #include malloc.h typedef struct _tagLink struct _tagLink *LC,*RC; int data; LINK; LINK *Head; int A=18,14,22,7,17,20,35,27,11,3,20; int N=sizeof(A)/sizeof(int); 中序遍历二叉树-建立二叉树 void built() for(int i=0; idata=Ai; Node-LC=Node-RC=NULL; if(i=0) Head=Node; continue

47、; Temp=Head; for(;) if(Aidata) if(Temp-LC=NULL) Temp-LC=Node; break; else Temp=Temp-LC; else if(Temp-RC=NULL) Temp-RC=Node; break; else Temp=Temp-RC; 中序遍历二叉树输出 void output() LINK *stack50; int TOP=0; LINK *P=Head; for(;) if(P!=NULL) stackTOP+=P; P=P-LC; else if(TOP=0) break; P=stack-TOP; printf(%dn,

48、P-data); P=P-RC; 中序遍历二叉树主程序 int main(int argc, char* argv) built(); output(); return 0; 小结小结 通过本章学习，了解CAD/CAM的数据结构基本概念、 线性表、栈、队列、数组以及树和二叉树等数据结构，学 习了树的遍历方法。 思考题:1、2、3 84 机械CAD/CAM技术 主编：蔡汉明 陈清奎 机械工业出版社 86 第三章第三章 计算机辅助图形处理技术计算机辅助图形处理技术 第一节 二维图形变换基本原理 第二节 三维图形变换基本原理 第三节 复合变换 第四节 视窗变换和裁剪 第五节 隐藏线与隐藏面的处理 第

49、六节 图形生成方法 87 图形变换是图形的几何信息经过几何变换后产生新的图 形。 图形变换包括图形的比例、平移、旋转及对称变换等。 图形变换的两种形式为：图形不变，坐标系改变；图形 改变，坐标系 不变。以下是针对坐标系的改变。 引言引言 几何变换基础 图形由图形的、顶点之间的以及组 成图形的面和线的所决定 任何一个图形都可以认为是点之间的连线构成 对一个图形作几何变换，实际上就是对一系列点进行变换 点和图形的表示点和图形的表示 二维平面内，一个点通常用坐标 (x , y) 来表示，矩阵形式为： 或 三角形的三个顶点坐标 a( x1, y1 ), b( x2, y2 ), c( x3, y3 )

50、a( x1, y1 ), b( x2, y2 ), c( x3, y3 )，用矩阵表示： 图形变换基础 1.1.工程图形的齐次坐标矩阵表示工程图形的齐次坐标矩阵表示 齐次坐标：齐次坐标：将一个n维向量用n+1维向量表示 。 例：平面三角形A齐次坐标矩阵表示 12 3 o x y 1 1 1 33 22 11 yx yx yx A 若图形A经过某种变换后得到图形B，则有： B=AT T称为变换矩阵称为变换矩阵，二维：T为3x3矩阵，三维：T为4x4矩阵。 A 点和图形的齐次坐标表示点和图形的齐次坐标表示 是将一个n维空间的点用n1维，即附加一个坐标表示 二维点x y的齐次坐标通常用三维坐标Hx