第5章机械CAD中常见的数据结构.ppt

第四章机械CAD中常见的数据结构 本章介绍 CAD系统进行工程或者产品设计的过程，实质上就是应用计算机进行信息处理的过程。在这个过程中会产生大量用于表达产品信息的数据、文字和图形。如何有效的使用和管理各类数据，是CAD技术的重要指标。 对于CAD系统，各类支撑软件是其重要组成部分。所以，软件设计技术的理论基础，“数据结构”就不仅仅是计算机学科的核心课程，也应该是所有应用计算机的其他学科，譬如机械CAD所应该掌握的课程 课程内容　1、基本概念和术语　2、数据的物理结构　3、数据的逻辑结构 4.1、基本概念和术语 数据（Data） 数据对客观事物的符号表示，是信息的载体。它能够被计算机识别、存储和加工处理，的符号的总称，是计算机程序加工的“原料”。 随着计算机应用领域的扩大，数据的范畴包括：　　整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位，是数据这个集合中相对独立的个体。数据元素也称元素、结点、顶点、记录。??? 　一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。??? 　数据项是具有独立含义的最小标识单位。 数据类型 数据类型是程序设计语言提供的变量类别。每一种程序设计语言都提供一组基本的数据类型 对于C语言，它提供了字符型、整型、浮点型和枚举型四种基本数据类型，和结构型数据类型。数据类型确定了数据元素的基本特点和允许的操作。 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ① 数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；??? 　数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 例如：见课本p56页，汽车的数据结构。 ② 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；??? 　数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），是数据元素和它们之间的关系在计算机中的表示。它依赖于计算机语言。结点是一个数据元素对应的位串，是数据元素在计算机中的映象。 ③ 数据的运算，即对数据施加的操作。　　数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。??? 　所谓抽象的操作，是指我们只知道这些操作是做什么，而无须考虑如何做。只有确定了存储结构之后，才考虑如何具体实现这些运算。 为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】 学生成绩表，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 （1）逻辑结构　　表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中马二所在结点的直接前趋结点和直接后继结点分别是丁一和张三所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 （2）存储结构　　该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3）数据的运算　　在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。??? 搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。 数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。??? 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。 数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的