1、第四章抽象数据类型生活中的问题想要用计算机编程求解，不是用简单的数据类型就能全部实现，还需要用抽象数据类型来描述问题的数据模型和基本操作。除了如线性表这种线性关系，还有很多数据之间的关系是层次或网状的，即以非线性形式存在的。4.1.1 抽象数据类型在用计算机解决实际问题的过程中，对于要解决的问题，不管用什么语言编写程序，其解决的方法和思路是相同的。为了便于描述问题和抽象问题，在一般数据类型的基础上提出了抽象数据类型，它可以有效地帮助我们思考、描述问题的数据模型和基本操作。很多高级语言都有“整型”这种数据类型，其实整型也是一种抽象数据类型，因为不同的计算机对整型变量的存储是不一样的。而我们用到整
2、型变量时，并不关心它是如何存储的，只需要了解其取值范围（值域）和能够进行的操作运算（加、减、乘、除、取模等），就可以正确地使用整型变量了。这正体现了抽象数据类型的本质：忽略不同机器、不同语言的实现细节，在更普遍、更高的层次抽象出问题的数据模型，并定义数据模型的相关操作，从而实现对问题的解决。抽象数据类型（抽象数据类型（Abstract Data Type，简称，简称ADT）是由一种数据结构和在其上的一组操作（运算）所组成。抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型通常由具体语言系统内部定义，直接提供给用户使用；而抽象数据类型还包括用户在编程处理数据、设计
3、软件系统时自己定义的数据类型，通常由用户自行定义，包括定义其所包含的数据（数据结构）和在这些数据上所进行的操作。在定义抽象数据类型时，就是定义其数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样具有较好的通用性和可移植性，便于用任何一种语言实现。ADT 抽象数据类型名 数据：操作：ADT 抽象数据类型名ADT 复数数据：实部;虚部;操作：初始化复数;获取实部;获取虚部;获取模;获取辐角;复数加法;复数减法;复数乘法;复数除法;ADT 复数为了便于理解和表达的简洁，对抽象数据类型定义中的数据（数据结构）及基本操作，我们采用中文说明和类C+语言的形式进行描述（借用C+语言的一些语
4、法元素，但是不严格遵循C+语言）。例如，我们可以定义“复数”这种抽象数据类型来表示数学上的复数：4.1.2 抽象数据类型的应用利用抽象数据类型定义复数，并通过编程实现，就可以使用计算机处理复数了。除了数学运算外，在解决现实问题和实际编写计算机应用软件时，因为要解决的问题更复杂，所以更需要大量应用抽象数据类型来描述问题和设计解决方案。如项目范例中的俄罗斯方块游戏，方块的颜色、形状都有多种，每一个方块都有左 旋、右旋、左移、右移、下落等多种操作，变化较多。游戏程序实现的关键是如何操控这 些方块，可以定义一种抽象数据类型“方块”，其中包含方块的形状、颜色、中心点等，以及对它的左旋、右旋、左移、右移、
5、下落等多种操作。类似的，我们还可以将俄罗斯方 块游戏的区域也定义为一种抽象数据类型，从而完成游戏的设计。（1）象棋游戏里（如图4-3所示），每一个棋子上面的文字都不一样，有的是“马”、有的是“兵”等，对阵双方的棋子颜色一般为黑色和红色，每个棋子必须响应鼠标或键盘的控制动作，实现棋子的拿起、移动、放下等操作。这里可以将棋子定义为一种抽象数据类型，其数据模型包括棋子的颜色、棋子的文字、棋子在棋盘上的坐标等，基本操作包括拿起、移动、放下等。4.1.3 抽象数据类型的实现为帮助大家更好地理解，接下来以定义抽象数据类型“长方形”为例，呈现抽象数据 类型的定义过程和程序实现过程。假定用rectangle来
6、表示“长方形”的抽象数据类型名，其数据部分长、宽用a、b表 示，类型为实数；其基本操作包括初始化、求长方形的周长和求长方形的面积，求周长的 函数名用perimeter表示，求面积的函数名用area表示，则长方形的ADT描述如下：4.2用抽象数据类型表示队列和栈队列和栈是两种典型的抽象数据类型，因为在计算机解决实际问题和很多软件的实现 中，都会用到队列和栈。通过抽象数据类型来表示队列和栈，能够更加清楚地认识和理解 这两种数据类型的特征和操作。4.2.1 用抽象数据类型表示队列4.2.1 用抽象数据类型表示队列队列是线性表的一种，队列的元素之间具有线性关系。另外，队列具有队头、队尾，元素从队尾入队
7、、从队头出队，因此队列具有先进先出（FIFO）的特点。针对队列的操作有：初始化队列、元素入队、元素出队、求队列长度、队列判满、队列判空。我们可以用下面的抽象数据类型表示队列：4.2.2 用抽象数据类型表示栈栈和队列一样，属于线性表的一种，其元素之间也具有线性关系。与队列不同的是，栈元素的入栈、出栈都是从同一头进行的，所以栈具有后进先出（LIFO）的特点。从抽象 数据类型的角度来看，栈的数据部分包括线性关系的数据元素和栈顶、栈底。关于栈的操 作有：初始化栈、元素入栈、元素出栈、栈空判断、栈满判断、求栈的长度。类似的，我 们可以用下面的抽象数据类型表示栈：4.3用抽象数据类型表示二叉树4.3.1树
8、1树 树是n（n0）个结点的有限集。在任意一棵非空树中：有且仅有一个特定的称为 根的结点；当n1时，其余结点分为m（m0）棵互不相交的有限子树，每棵子树又是一 棵树。如图4-7所示，树T由根结点A及两棵子树T1、T2组成。同样，T1中，B是根结点，其 下又可以细分出三棵子树（D、EHI及F）；T2中，C是根结点，其下又可以细分出1棵子树（GJ）。2树的基本概念（1）结点的度。每个结点具有的子树数称作结点的度。例如图4-7（a）树T中，B结点的度为3，I结点的度为0。2树的基本概念（2）分支结点和叶子结点。在一棵树中，度等于0的结点称作叶子结点。度大于0的结点称为分支结点或非终端结点。树T中，D
9、、H、I、F、J为叶子结点，A、B、C、E、G为分支结点。2树的基本概念3）孩子结点、双亲结点、兄弟结点。在一棵树中，每个结点的子树的根，称为该结点的孩子结点，相应地，该结点被称为孩子结点的双亲、父亲或父母。具有同一双亲的孩子互称兄弟。在图4-7（a）树T中，结点B是结点A的孩子结点，结点A是结点B的双亲结点，结点B和C互为兄弟。2树的基本概念（4）树的深度。从树根开始，根结点为第一层，它的孩子结点为第二层，如此类推。树中所有结点的最大层数称为树的深度。图4-7（a）树T的深度为4。4.3.2二叉树如图4-8所示的是自然界中的二叉树，它每一个枝都只有个分枝，树枝的尽头才是叶子，是不是很有趣呢？
10、计算机数据结构中的二叉树是一种特殊树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），而且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树在计算机领域有着广泛的应用。（优先级队列，资源管理器，用户界面）完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。4.3.3 二叉树的抽象数据类型二叉树的抽象数据类型的数据部分为一棵用任一种方式表示的二叉树，操作部分包括初始化二叉树、建立二叉树、遍历二叉树、查找二叉树、输出二叉树和清除二叉树等常用操作。4.3.4 二叉树
11、的基本操作方法二叉树的基本操作较多，下面以遍历为例，了解二叉树的基本操作方法。遍历是二叉树的一种基本操作，是指按一定的次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。由于二叉树是非线性结构，因此二叉树的遍历实质上是将二叉树的所有结点转换成一个线性序列的过程。根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树所组成。因此，遍历一棵非空二叉树的问题可分解为三个子问题：访问根结点、遍历左子树、遍历右子树。若用L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有DLR、LDR、LRD、DRL、RDL、RLD六种情况，若限定先左后右，则只有前三种情况，分别称为
12、前序遍历（或先根遍历）、中序遍历（或中根遍历）、后序遍历（或后根遍历）前序遍历（或先根遍历）LDRD L R中序遍历（或中根遍历）LDRL D R后序遍历（或后根遍历）LDRL R D练前序遍历为：中序遍历为：后序遍历 为：ABDECFG；DBEACGF；DEBGFCA。当完全二叉树结点总数为偶数时，叶子结点数=结点总数/2。当完全二叉树结点总数为奇数时，叶子结点数=(结点总数+1)/2。二叉树具有以下重要性质：性质1深度为k的二叉树至多有2-1个结点(k1)。性质2在二叉树的第i层至多有2-1个结点(i1)。性质3如果二又树的终端结点数为m，度为2的结点数为口则m=n+1数据类型是一个值的集
13、合和定义在此集合上的一组操作的总称。抽象数据类型=逻辑结构抽象运算抽象数据类型暂不考虑计算机的具体存储结构和运算的具体实现。抽象数据类型实质上，就是在描述问题本身（与计算机无关）。目标：在不涉及具体的，和计算机系统相关的细节情况下，优先理解问题本身，在此基础上，实现用计算机求解问题的过程。ADT 数据对象：数据关系：基本操作：ADT 我们可以认为抽象数据类型是包含着数据类型的，也就是说，抽象数据类型是一个更大的概念，例如：在定义一个学生类型的抽象数据类型时，学生对象既包含整型的年龄，身高，又包含char类型的姓名，这时，我们就可以用一个结构体定义这个学生类型struct Student char sno;/学号int age;/年龄 这里，Student是一个抽象数据类型，而里面的int,char类型又是不同的数据类型
