第三章cadcam软件基础（教学讲义）.pptVIP

第三章 CAD/CAM软件基础 数据的有关基本概念 数据结构 工程数据库 软件工程方法和开发过程 数据的基本概念 数据 是一个集合的概念，是对客观事物的符号表示，指所有能被输入到计算机中，并被计算机处理的符号的总称 符号：数字、字符和其他能输入到计算机并被计算机识别和处理的字符 “123”、“a3”、” tea”、”汉字”等 数据元素 数据的基本单位，数据的一个个体 又称为“记录”或“表目” 本身可以复杂，也可以简单 数据项：数据的不可分割的最小单位。数据元素是数据项的集合 数据对象：是性质相同的数据元素的集合，是数据的一个子集 数据项组成数据元素，数据元素组成数据对象，数据对象组成数据 数据类型 程序设计语言确定变量所具有的种类 确定数据按苏在计算机内部所占位串的大小 如（int /32 float /32 byte /8）等 数据结构（Data Structure） 是信息的组织方式 ，用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构 分为数据逻辑结构和物理结构 逻辑结构：成分数据之间的逻辑关系，独立于存储介质 物理结构：也称存储结构，反映成分数据在计算机内部的存储安排 对于相同的算法，用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率 DS研究的对象 主要研究三个方面 逻辑结构 存储结构 对数据的各种操作（即算法） 数据的逻辑结构 集合结构 数据元素之间除了同属于一个集合的关系外别无其他关系 线性结构 数据元素之间存在一个对一个的前趋后继关系 树形结构 数据元素之间存在一个对多个的关系 图状结构（网状结构） 多个对多个的关系 线性表逻辑结构 是n个（n0）数据元素的有限集合 表示为（a(1),a(2),…a(n-1),a(n)） 数据元素的数量定义为线性表的长度 特点： 有且仅有一个元素无前趋元素 有且仅有一个元素无后继元素 其余任何一个元素均有且仅有一个前趋有且仅有一个后继元素 线性表顺序存储结构 顺序存储结构 用一组连续的存储单元依次存放各个数据元素 存放地址与逻辑顺序存在一一对应关系 特点 均匀性：各元素所占存储空间长度相同 有序性：存储顺序与逻辑顺序一致 线性表链式存储结构 存储单元可以不连续 除了存储元素本身数据信息外，还要存储该元素直接后继或直接前趋位置。称为结点 结点含两部分：数据域和指针（域） 顺序存储结构线性表的操作 删除 被删除元素后的所有数据元素均应向前移动一个数据元素所占的存储空间长度，以保持有序性和均匀性 插入到第 i 位置 先将从第 i 元素起后面的所有元素向后移动一个元素存储长度，后将新元素插入第 i 位置 访问、修改方便；删除、插入等难 需按照最大长度来分配空间 单向链表 仅一个指针域 表头（head） 结构与链结点同 指针指向第一个结点的地址 数据可以是空，或为表长 表最后一个结点，指针为空 单向链表操作 建立 定义数据类型，指针域存放下一个结点地地址 表长可动态申请 删除第 i 结点 先找到第 i-1结点并将其指针域指向第 i 结点指针域中的数据，即第 i+1 结点的地址 释放第 i 结点所占的空间 须从第 1 结点开始查找 插入第 i 结点 先申请一个空间，得一新结点 找到第 i-1结点并将其指针域指向新结点 新结点指针指向第 i 结点 双向链表 两个指针域（前趋last和后继next） 表头（head） 结构与链结点同 后继指针指向第一个结点的地址 前趋指针是空 第一个结点前趋指针是空(图3-2) 表尾（rear） 结构与链结点同 前趋指针指向最后一个结点的地址 后继指针是空 双向链表操作 建立 定义数据类型，next指向直接后继结点地址，last指向直接后继结点地址 删除第 i结点 将第 i-1结点next指针域指向第 i+1结点，将第 i+1 结点的last地址指向第 i-1结点 释放第 i结点所占的空间 插入第 i结点 先申请一个空间，得一新结点 将第 i-1结点next指针域指向新结点，新结点last指向i-1结点 新结点next指针指向i+1结点, i+1结点last指向新结点 循环链表 最后结点不是空指针，而是指向表头的指针 闭环 运算时可以从任意位置开始查找（单向只能从表头开始） 图3-4 链表与线性表比较 树 非线性数据结构，元素间存在层次关系 由1个或多个元素组成的有限集，其中有一个特定的结点称为根结点，其余结点可分为n(n=0)个互不相交的有限集，每个结点可以看成子树 至少有一个根结点 子树相互独立、互不相交 有且只有一个前趋，称为双亲 无次序之分 二叉树 每个节点至多有2棵子树 子树有左右之分 可以为空（一般树至少要1个节点） 图3-6二叉树的5种基本形态 二叉树的遍历（共六种） 二叉树不是树的