第2章 cad中常用的数据结构

1第 2章 CAD中常用的数据结构l 基本概念l 线性表l 栈和队列l 树2第 2章 CAD中常用的数据结构l 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。 l 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的 关系 称为 结构 (Structure)。l 数据结构 是一堆数据元素和这些数据元素之间的关系的总和。3按数据元素之间关系的不同特性，通常有 4类基本结构（ 1）集合 结构中的数据元素除了 “同属于一个集合 ”外，别无其它关系。（ 2）线性结构 结构中的数据元素之间存在一对一的关系。（ 3）树型结构 结构中的数据元素之间存在一对多的关系。（ 4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。etc user集合集合数据元素之间无特殊关系数据元素之间无特殊关系devlibbin devetc user4按数据元素之间关系的不同特性，通常有 4类基本结构（ 1）集合 结构中的数据元素除了 “同属于一个集合 ”外，别无其它关系。（ 2）线性结构 结构中的数据元素之间存在一对一的关系。（ 3）树型结构 结构中的数据元素之间存在一对多的关系。（ 4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。线性结构线性结构数据元素之间存在着一个对一个的关系数据元素之间存在着一个对一个的关系bin dev etc lib user5按数据元素之间关系的不同特性，通常有 4类基本结构（ 1）集合 结构中的数据元素除了 “同属于一个集合 ”外，别无其它关系。（ 2）线性结构 结构中的数据元素之间存在一对一的关系。（ 3）树型结构 结构中的数据元素之间存在一对多的关系。（ 4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。树形结构树形结构数据元素之间存在着一个对多个的关系数据元素之间存在着一个对多个的关系树树 二叉树二叉树 二叉搜索树二叉搜索树141312112 3 45 6 7 8 9 10 31 587101199874 5 662 3 13116按数据元素之间关系的不同特性，通常有 4类基本结构（ 1）集合 结构中的数据元素除了 “同属于一个集合 ”外，别无其它关系。（ 2）线性结构 结构中的数据元素之间存在一对一的关系。（ 3）树型结构 结构中的数据元素之间存在一对多的关系。（ 4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。图形（网状）结构图形（网状）结构数据元素之间存数据元素之间存在着多对多的关系。在着多对多的关系。1524367第 2章 CAD中常用的数据结构问题：为什么要学习数据结构？l 计算机的主要用途：l 早期： 主要用于数值计算。l 后来：l 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。8问题：学习数据结构有什么用？答：计算机内的数值运算依靠 数学方程， 而非数值运算（如表、树、图等）则要依靠 数据结构。l 同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。l 程序设计的实质是对 实际问题选择一个好的数据结构，加之设计一个好的算法。 而好的算法在很大程度上取决于描述实际问题的数据结构。 算法 +数据结构 =程序 92.1 基本概念1. 数据（ data）：数据是信息的载体，是描述客观事物的数字、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合 , 是计算机程序加工的 ” 原料 ” 。 2.数据元素（ data element）l 数据的 基本单位。 在计算机程序中常作为一个整体进行考虑和处理。 数据可以是简单的，也可能是复杂的，只是相对独立的单元。产品 部件；部件 零件；零件 基本形体l 数据元素又称为元素、结点、记录。103、数据的逻辑结构和物理结构l 数据的逻辑结构从 逻辑关系 上描述数据，可以看作是从具体问题抽象出来的 数据模型 ，与数据的存储无关，也与数据元素本身的形式、内容、相对位置无关；线性表、栈、队列 、串、树 11数据的物理结构l 数据结构在 计算机中的表示 (或称映象） 称为 数据的物理结构，又称为存储结构。 它包括 数据元素的表示 和 关系的表示 。（ 1）数据元素的表示：计算机处理数据的最小单位叫做 位 (Bit)，一个位表示一个二进制的数，若干位组合起来形成一个 位串 。用一个位串表示一个数据元素，称这个位串为一个 结点 。结点是数据元素在计算机中的 映象 。（ 2）关系的表示 两种基本的存储结构： 顺序映像（顺序存储结构） 非顺序映像（链式存储结构） 12u 顺序存储结构 :所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内仍然相邻。u 链式存储结构：在每一个数据元素中增加一个存放地址的指针，借助该指针来表示数据元素之间的逻辑关系。所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址（指针）确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。13顺序存储结构14链式存储结构l struct linkl l char name;l struct link *nextl ;15l 数据类型是程序设计语言确定变量所具有的种类。l 每种程序设计语言都提供一组基本的数据类型。l C语言提供 字符型、整型、浮点型和双精度 型 4种基本数据类型；l 程序设计语言还可以将不同类型的数据组合成一个有机的整体，构造出新的数据类型用来实现各种复杂的数据结构的运算。4.数据类型16l 线性表：是 n(n o)个数据元素的 有限序列 。逻辑结构如下： (a1,a2,a3, ,ai-1,ai,ai+1, ,an-1,an)其中 ai可以是一个数、是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。l 当 n o时，除第一个及最后一个元素外，线性表中每个元素有且只有一个 直接前趋 ，有且只有一个 直接后继 。l 线性表中数据元素的数量定义为线性表的 长度 。 2.2 线性表2.2.1 线性表的逻辑结构17减速器零件清单可构成一个线性表，数据元素是由 4个数据项组成的一个记录。18l 线性表的顺序存储是指 用一组地址连续的存储单元 依次存储线性表中的各个元素。20 31 45 34 25 35 1 2 3 4 5 6 data用物理位置来表示逻辑结构。LOC(ai+1)=LOC(ai)+l ; LOC(ai)=LOC(a1)+(i-1)*l 特点：是一种 随即存取 的存储结构，只要确定了起始位置，就可以访问表中的任何一个元素。2.2.2 线性表的顺序存储结构19(1)均匀性 每个数据元素所占存储空间的长度相同。(2)有序性 各数据元素之间的存储顺序与逻辑顺序一致。线性表顺序存储结构的特点l 顺序表容易实现访问操作，可随机存取元素。但插入和 删除操作主要是移动元素。l 数组可以看成是线性表定义的扩充。201.从线性表中删除一个数据元素 l 分析： “删除元素 ” 线性表的逻辑结构发生什么变化？假设删除线性表的第 i个元素保存在变量 e中。l 删除元素时，线性表的逻辑结构由 (a1, ,ai-1, ai, ,an) (a1, , ai-1, ai+1, , an)a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 ai+1eanai212.将一个新的数据元素插入到线性表l 分析： “插入元素 ”使线性表的逻辑结构发生什么变化？假设在线性表的第 i个元素之前插入一个元素 e。l 插入元素时，线性表的逻辑结构由 (a1, ,ai-1, ai, ,an) (a1, , ai-1, e, ai, , an), a1 a2 ai-1 ai ana1 a2 ai-1 aiean22顺序存储结构的优缺点l 优点 逻辑相邻，物理相邻 可访问和修改任一元素方便 存储空间使用紧凑l 缺点 插入、删除操作需要移动大量的元素，增加运算时间 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充多用于长度变化不大，查找频繁，很少增删的场合。231.链式存储结构的特点： 用一组 任意的存储单元 存储线性表的数据元素 利用 指针 实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素， 除存储本身信息外，还需存储其 直接后继 或直接前驱 的 存储位置 结点 :指这两种信息组成数据元素的存储映像。 l数据域： 元素本身信息l指针域： 指示直接后继 或直接前驱 的存储位置 ，指针数据域 指针域结点2.2.3 线性表的链式存储结构数据域(data)指 针 域(next)24ZHAO QIAN SUN LIZHOU WU ZHENG WANG H线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域 指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针25l 定义：结点中只含一个指针域的链表。l 特征： 每个元素由结点 (Node)构成。 线性结构 结点可以不连续存储 表可扩充Ha1 a2 a3 a4 nextdata2. 单向链表26头指针、头结点、第一个元素结点 以线性表中第一个数据元素 a1 的存储地址作为线性表的地址，称作线性表的 头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点 ”（表头），以指向头结点的指针为链表的头指针 .a1 a2 a3 a4 空指针头指针头结点 线性表为空表时，头结点的指针域为空27单链表存储结构的实现定义结点结构：struct Link char data;struct Link *next; * Node, * Head; ;p 结点（ *p）(*p) 表示 p所指向的结点(*p).data p-data 表示 p指向结点的 数据域(*p).next p-next 表示 p指向结点的 指针域Head Node Nodenextdata28l 生成一个 Node型 新结点：p=(struct Link *)malloc(sizeof(LNode);l 单链表特点 : 它是一种动态结构，整个存储空间为多个链表共用 不需预