计算机辅助制造CADCAM-.ppt

第4章 几何造型系统的数据结构 主要内容 概述 数据结构的基本知识 几何体在计算机中的表示 三维形体的原理及表达 一、概述 何谓计算机造型？ 计算机就是以计算机能够理解的方式，对实体进行确切的定义，赋予一定的数学描述，再以一定的数据结构形式对所定义的几何实体加以描述，从而在计算机内部构造一个实体的模型。 完整性 惟一性 几何造型 几何造型是指点线面体等几何元素通过一系列几何变换和集合运算生成的物体模型。 基本几何元素在计算机内的存储和组织是几何造型的关键技术。 几何造型的任务 几何造型的重要性 如何在计算机中表示现实世界？ 二、数据结构知识 数据元素、数据项 数据元素是数据的基本单位，它由不可分割的数据项组成 数据对象 是性质相同的数据元素的集合。 如上例：一个班级的成绩表可以看作一个数据对象。 数据结构及其种类 数据元素集合（也可称数据对象）中各元素间相互关系。 常用的数据结构 线性表 树形结构 理解线性表 一个线性表是n个数据元素的有限序列。 线性表是最常用且最简单的一种数据结构。 数据元素可以是一个数、一个符号、也可以是一幅图或更复杂的信息。 线性表中的数据元素类型多种多样 同一线性表中的元素必定具有相同特性，即属同一数据对象 每个数据元素有且只有一个直接前趋和直接后继 线性表中元素的个数n定义为线性表的长度，为0时称为空表。 在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。 线性表的存储结构有两种：顺序存储结构和链式存储结构 顺序存储结构 顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放。 假定每个数据元素占用m个存储单元，每个数据元素第1个单元的存储位置为该数据元素的存储位置，第1个数据元素的存储位置为b，则第t个数据元素的存储位置为 　　　Loc(at)=b+(t-1)×m 顺序存储结构的特点 有序性： 各数据元素之间的存储顺序与逻辑顺序一致。 均匀性： 每个数据元素所占存储空间的长度相等。 链式存储结构 线性表中的数据元素可以用任意的存储单元来存储。 线性表中逻辑相邻的两元素的存储空间可以是不连续的。 表的每个数据元素除存储本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映象，称为结点。结点有两种域：存放数据元素本身的数据域和存放其直接前趋或直接后继的指针域。 用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。 链式存储结构又分为单向链表和双向链表 单向链表 单向链表的指针域只有一个，通常存放直接后继的地址。第一个元素的地址需要专门存放在指定的指针型变量中，或者设置一个与链表结点相同的一个结点，它的数据域可以是空的，也可以存放表长等附加信息，指针域存放第一个元素的地址。 双向链表 单向链表的结点只有一个存放直接后继的指针域，因此某个结点出发只能向后寻找其他结点。如果结点再增设一个指针域，存放它的直接前趋的地址，就可以方便地从每个结点向前寻找其他结点，这样的链表称为双向链表。 链式存储结构与顺序存储比较 删除或插入运算速度快。 不需事先分配存储空间，以免不能充分利用所用空间。 表的容量容易扩充。 按逻辑顺序查找的速度慢。 比相等长度的顺序存储多占用作为指针域的存储空间。 树形结构 树形结构的简称为树，它是一种重要的非线性数据结构，它为计算机应用中出现的具有层次关系或分支的数据提供了一种自然的表示方法。 树形结构的特点 除根结点外，每个结点有且只有一个直接前趋； 除终端点外，每个结点可以有不只一个直接后继。 结点的直接前趋称为该结点的双亲，结点的直接后继称为该结点的孩子，同一双亲的孩子间称兄弟。 树是具有层次关系的数据结构，层次的数量称为树的高度。 结点的孩子数量称为度。树的所有结点中最大的度数称为这棵树的度数。 定长链式存储方式 以具有最大度数的结点的结构作为该树所有结点的结构。 不定长链式存储方式 每个结点增加一个存放度数的域，结点的长度随着度数的增加而增加 二叉树 二叉树是一种不同于树的数据结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 由上述定义可以看出，二叉树和树是两个不同的概念 树的每一个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2； 树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后继为左儿子，右后继为右儿子。 ??? 二叉树的五种基本形态 二叉树的两个特殊形态 满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。可以验证具有n个叶结点的满二叉树共