机械CAD中常用的数据结构

第四章 机械CAD中常用的数据结构 第一节 基本概念 第二节 线性表 第三节 栈 第四节 树 第五节 二叉树

第四章 机械CAD中常用的数据结构 本 章 要 点 数据结构的基本概念 树与二叉树

4.1 基本概念 数据 — 数据是指用来描述客观事物的、能输入到计算机中并被计算机接受和处理的符号的总称。用文字符号、数字符号及其它规定的符号对现实世界的事物及其活动的抽象描述。 数据元素 —数据元素是数据的基本单位，是数 据这个集合的一个个体。例如在设计产品的过程中， 可以把该产品的每个部件的每一个零件看作一个相对 独立的单元，这时每个零件就是一个数据元素。

§4－1 基本概念 数据结构 ◎数据结构是指数据及其相互之间的联系 ◎数据结构有逻辑结构和物理结构之分 ◎数据的逻辑结构仅考虑数据之间的逻辑关系，它独立于数据的存储介质。所关注的是数据之间的联系，是这种联系的抽象描述。 ◎数据的物理结构也称存储结构，是数据结构在计算机中的映象。是一种逻辑结构在存储器中的存储方式，存贮方式有顺序、链接、索引、散列等多种，所以一种逻辑结构可以采用多种物理结构存贮。 ◎通常所说的数据结构就是指逻辑结构

数据结构的分类及表示方法 实例：教务处人事简表（表1—1） ◎目录行包括六个数据项，这些定义了表的结构 职工号 姓名 性别 出生日期 职务 部门 01 02 03 04 05 06 07 08 09 10 万明华 赵宁 张利 赵书芳 刘永年 王明理 王敏 张才 马立仁 邢怀常 男 女 52.3.20 58.6.14 54.12.7 62.8.5 49.8.15 65.4.1 62.6.28 57.3.17 65.10.12 66.7.5 处长 科长 科员 教务处 教学科 学籍科 考务科 ◎目录行包括六个数据项，这些定义了表的结构 ◎共有十条记录，一个记录就是一个数据元素 ◎“职工号”的值能唯一地标识一个记录，该数据项叫做 关键项

1、线性结构 设表1—1中只考虑年龄大小的排列 ◎图形表示 07 04 06 09 10 05 01 03 08 02 ◎结构特点：数据元素之间最多只有一个前驱，最多只有一个后继，元素之间是一对一联系，即1︰1

2、树形结构 ◎图形表示 设表1—1中只考虑领导和被领导关系 05 01 03 08 02 07 04 06 09 10 ◎结构特点：每个元素最多有一个前驱，但可有多个后继，元素之间是一对多关系，即1︰N，有层次关系。

§4－2 线性表 一、线性表的逻辑结构 线性表是一种最常用且最简单的数据结构，是n个数据元素的有限序列：(a1, a2, a3 , … ai, …, an) 其中 数据元素ai可以是一个数，可以是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。

§4－2 线性表 线性表具有以下特点： 线性表是数据元素的一个有限序列 线性表中数据元素的个数定义为线性表的长度，当n =0时，为空表 数据元素在线性表的位置取决于它们自己的序号，数据元素之间的相对位置是线性的，如a1是第一个元素，an是最后一个元素。 除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。当1< i < n时，ai的前一个元素ai-1是它的直接前趋，ai的后一个元素ai+1是它的直接后继。i =1, 2, …, n-1的元素ai有且只有一个直接后继, i =2, 3, …, n的元素ai有且只有一个直接前趋 。

§4－2 线性表 二、线性表的存储结构 图 4-2 线性表的顺序存储结构示意图 1、顺序存储就是用一组连续的存储单元，按照数据元素的逻辑 顺序依次存放。 假定一个线性表A(n)，它的每个数据元素占m个存储单元，第一个数据元素在内存中的开始地址为b，那么，第i个数据元素的存储位置为： L(ai)=b+(i-1)m 元素序号 1 2 3 … i n 内存内容 a 1 2 3 存储地址 b +m +2m b+（i－1）m b+(n-1)×m 图 4-2 线性表的顺序存储结构示意图

§4－2 线性表 线性表的顺序存储结构的特点 有序性：各数据元素之间的存储顺序与逻辑顺序一致。 均匀性：每个数据元素所占存储空间的长度是相等的。 因此对表中数据元素进行的访问、修改运算速度快。在删除或插入运算时，必须进行大量数据元素的移动，增加运算时间。 这种存储结构多用于查找频繁、很少增删的场合。如工程手册中的数表。向量、数组、栈、队列属于顺序存储结构。

§4－2 线性表 2、线性表的链式存储结构 用一组任意的存储单元存放表中的数据元素。由于存储单元可以是不连续的，因此为了表示表中元素的逻辑关系，除了存储元素本身的信息之外，还要存储这个元素直接后继或直接前趋的存储位置。这两种信息组成数据元素的存储映象，称为结点。结点包括两种域，存放数据元素本身的域称为数据域，存储直接后继或直接前趋地址指针的域称为指针域。 a) 结点 b) 单向链表 图 4-5 链表结构 数据域 指针域 D ata Link Data2 Link2 Data n Ù Data1 Link1 … H head

§4－3 栈 一、栈的逻辑结构 栈也是线性表，它与普通线性表的区别就在于对它的运算仅限定在表尾。 进栈 出栈 栈顶 a n … 3 2 栈底 1 图4-13 - 栈的逻辑结构 假定栈s=(a1, a2, a3, ,…,, ai, …, an)，则a1称为栈底元素，an为栈顶元素。进栈的顺序是a1, a2, a3, ,…, an)，出栈的顺序是an, an-1, …, a3, a2, a1。它的显著特点是后进先出(LIFO --- Last In First Out) 。

§4－3 栈 二、栈的运算 建立一个栈 栈的存储结构用数组s[n]。设m为栈的上界，则在C语言中，由于第1个数组元素是s[0]，所以栈的上界m等于n-1。设一栈顶指针为TOP，它不必指向数据元素的实际地址，只记录数据元素的逻辑序号即可。当元素尚未进栈时，令TOP等于-1。 进栈 如果有元素进栈，首先检查栈顶指针TOP，如果TOP等于m，表示栈满，显示栈满信息，否则将发生上溢。如果TOP<m，令TOP=TOP+1，将该元素赋给s[TOP]。 出栈 出栈即取走栈顶元素。首先检查栈顶指针TOP，如果TOP=-1，表示栈空，显示出错信息，否则将发生下溢。如果TOP>-1，出栈元素为s[TOP]，然后令TOP=TOP-1。

§4－4 树 一、树的逻辑结构 A B C D F G H I E L K J 第 1 层 2 3 4 树根 子树根 树叶 图 - 17 树的逻辑结构 树是由一个或一个以上结点组成的有限集T，其中一个结点称为根，其余结点可分为若干个互不相交的有限集T1，T2，T3，…，Tn，每一个集合本身又是一棵树，称为根的子树。可见，树结构是一个递归定义。

§4－4 树 A B C D F G H I E L K J 图 - 17 树的逻辑结构 结点的度：结点的孩子(子树)的数量称为度。 树的度：树中所有结点中最大的度数称为这个树的度数。图4-17所示的树，其度数为4。 根结点：没有直接前趋的结点，A为根结点。 分支结点：度不为0的结点，或者有直接后继的结点。如结点B，F，D，J。每个分支结点可以有不只一个直接后继。 叶结点：没有直接后继的结点，或者说度为0的结点。如结点E，K，G，H，C，I，L都是树叶，也称终端结点。 A B C D F G H I E L K J 第 1 层 2 3 4 树根 子树根 树叶 图 - 17 树的逻辑结构

§4－4 树 A B C D F G H I E L K J 图 - 17 树的逻辑结构 边：结点间的连线 孩子：结点的直接后继称为该结点的孩子。如B是A的孩子。 兄弟：同一双亲的孩子间称为兄弟。如E，F，G，H 堂兄弟：双亲在同一层的结点互为堂兄弟。如G与I，J互为堂兄弟。 深度：树的最大层次数量称为树的深度或高度。 祖先：从根到该结点所经的所有结点都是该结点的祖先。如结点L的祖先是A，D，J结点。 子孙：以该结点为根的子树中的任一结点都是该结点的子孙。如I，J，L是D的子孙，结点A的子孙则是树中其余的11个结点。 A B C D F G H I E L K J 第 1 层 2 3 4 树根 子树根 树叶 图 - 17 树的逻辑结构

§4－4 树 二、树的存储结构 用定长或不定长两种方式描述树的结点。 1. 定长方式 以最大度数结点的结构作为该树的所有结点的结构 ，每个结点都有 相同数量的子树域。 数据域 指向直接后继 1 的指针 2 … n a) 定长方式的结点 A 0 H C G b) 树结构 A B C D E F G H B E D F c)定长结点的链表结构

§4－4 树 2. 不定长方式 每个结点增加一个存放度数的域，结点长度随着度数不同而不同。 … a) 不定长结点 b) 不定长结点的链表结构 数据域 结点的度 指向直接后继 1的指针 2的指针 n的指针 … a) 不定长结点 A 2 B 3 E 1 D C G H F b) 不定长结点的链表结构 不定长结点表示的树

§4－4 二叉树 一、二叉树的逻辑结构 1. 定义 二叉树是树结构的一种，但不同于一般树结构，即每个结点至多有两棵子树，并有左右之分，不能颠倒。二叉树可以是空的，一般树则至少有一个结点。 二叉树的深度和度的定义与树一致 。 基本形态 空 只有根结点 根的右子 树为空 根的左子 树为空 根的左右子 树都不空

二叉树的性质 第0层（根） 第1层 第2层 第3层(h=3) 1、若层次从0开始，则第i层最多有2 个结点

§4－4 二叉树 2. 几种特殊二叉树 （1）深度为k的有2k-1 个结点的二叉树称为满二叉树。 （2）深度为k，结点为n的二叉树，它从1到n的标号，如果与深度为k的满二叉树的标号一致，就称为顺序二叉树。 （3）结点的度数或者为零，或者为2的二叉树称为完全二叉树。 1 A 2 B 3 C 4 D 5 E F 6 G 7 (a) 1 A 2 B 3 C 4 D 5 E F 6 1 A 2 B 3 C 4 D 5 E (b) (c)

请判断以下哪个是完全二叉树？ （1） （2） 5 （4） （5） （3） （6） （8） （7） （9） 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 （1） （2） 5 1 2 3 4 1 2 3 4 5 6 7 8 9 （4） （5） （3） 1 2 3 4 5 1 2 （6） （8） （7） （9） 1 1 （10）

§4－4 二叉树 二、二叉树的存储结构 对于满二叉树或顺序二叉树，存储结构可采用顺序存储形式 。 性质：如果i =1，此结点是根结点。如果i =k，k/2是结点i的双亲结点，2k是i的左孩子，2k+1是i的右孩子。 A B C D E F 1 2 3 4 5 6 1 A 2 B 3 C 4 D 5 E F 6 特点：这种存储结构的特点是节省空间，可以利用公式随机地访问每个结点和它的双亲及左右孩子，但不便删除或插入运算。 对于一般二叉树，通常采用多重链表结构。每个结点设三个域：数据域存放结点的值，左子树域存放左子树的地址，右子树域存放右子树的地址 。 图4-25 顺序二叉树的顺序存储

§4－4 二叉树 图4－26 二叉树的链式存储结构

§4－4 二叉树 二、二叉树的遍历 遍历二叉树是指按一定规律走遍二叉树的每个结点，每个结点访问一次且只访问一次。 根据根结点、左子树、右子树三者不同的先后次序，有6种遍历二叉树的方案。 根结点、左子树、右子树 左子树、根结点、右子树 左子树、右子树、根结点 根结点、右子树、左子树 右子树、根结点、左子树 右子树、左子树、根结点 前三种是按着先左后右的次序，属于常用的遍历方式。

§4－4 二叉树 1. 先根遍历 先根遍历的次序是：先访问根结点，再访问左子树，最后访问右子树。遍历结果如下：A，B，D，H，E，C，F，G，I。 图4-27 二叉树 A B D E F G C H I F A B D E G C H I 图4-28 先根遍历

§4－4 二叉树 2. 中根遍历 中根遍历的次序是：先访问左子树，再访问根结点，最后访问右子树。遍历结果如下： D，H，B，E，A，F，C，I，G。 3. 后根遍历 后根遍历的次序是：先访问左子树，再访问右子树，最后访问根结点。遍历结果如下：H，D，E，B，F，I，G，C，A。 A B D E F G C H I A B D E F G C H I 图 4 - 29 中根遍历 图 4 - 30 后根遍历

例如：次序（V—根，L—左子树，R—右子树） 先序遍历 中序遍历 后序遍历 先右后左： VRL RVL RLV 先左后右： VLR LVR LRV bt A B C D E F G H I J VLR输出序列：A B D E G HI J C F LVR输出序列：D B G EI H J A C F LRV输出序列：D G I JH E B F C A

§4－4 二叉树 三、树的二叉树表示 用二叉树表示一般树可以节省存储空间，一般树转换为二叉树的规则是： 树的根结点为二叉树的根结点； 保留根结点的孩子(从左到右)第一个孩子作为二叉树的左子 树。 根结点的其余孩子作为该左子树的右子树(与左子树原属于兄 弟关系，现变为父子关系)。

§4－4 二叉树 例题： 1. 保留每个结点与最左孩子的边，去掉其余各边。 2. 连接同一双亲的所有兄弟。 3. 以树根结点为轴心，将整棵树顺时针旋转45即可得到转换 后的二叉树 。 A A E F G B C D H I A B C E F G D H I B C D E F G H I 图4-31 树转换为二叉树

§4－4 二叉树 三、二叉树应用举例 利用二叉树排序 排序就是对一组无序的数据递增或递减的规律重新排列。 用二叉树排序的过程分为两步： 先构造这棵二叉树 对这棵二叉树进行遍历 例如: 对一组数据(a1, a2, a3, ,…, ai-1, ai, ai+1, …, an)按递增的规律排序。

§4－4 二叉树 (1) 构造二叉树 每一个数据将对应二叉树的一个结点。 该结点在二叉树上的位置是这样确定的： 第一个数据元素a1作为这棵二叉树的根结点； 若 a2< a1，a2作为a1的左子树，否则作为a1的右子树； 第i个数据元素ai首先同这棵二叉树的根结点比较，若 ai< a1，则aI应位于a1的左边，再同a1的左子树结点比较，否则同a1的右子树结点比较，以此类推，直到找到该数据元素的位置为止。 建立数组(9, 36, 45, 13，26，7，12，48)的二叉排序树。

§4－4 二叉树 (2) 中根遍历二叉排序树 用中根遍历方式遍历该二叉树，图3-24所示的二叉树排序的结果是： 7, 9, 12, 13, 26, 36, 45, 48 图3-24 建立的二叉树