第四章 抽象数据类型 课件 2023—2024学年粤教版（2019）高中信息技术选修1

第四章 抽象数据类型 单击此处添加副标题内容 生活中的问题想要用计算机编程求解，不是用简单的数据类型就能全部实现，还需要用抽象数据类型来描述问题的数据模型和基本操作。除了如线性表这种线性关系，还有很多数据之间的关系是层次或网状的，即以非线性形式存在的。 4 . 1 . 1 　抽象数据类型 在用计算机解决实际问题的过程中，对于要解决的问题，不管用什么语言编写程序，其解决的方法和思路是相同的。为了便于描述问题和抽象问题，在一般数据类型的基础上提出了抽象数据类型，它可以有效地帮助我们思考、描述问题的数据模型和基本操作。 很多高级语言都有“整型”这种数据类型，其实整型也是一种抽象数据类型，因为不同的计算机对整型变量的存储是不一样的。而我们用到整型变量时，并不关心它是如何存储的，只需要了解其取值范围（值域）和能够进行的操作运算（加、减、乘、除、取模等），就可以正确地使用整型变量了。这正体现了抽象数据类型的本质：忽略不同机器、不同语言的实现细节，在更普遍、更高的层次抽象出问题的数据模型，并定义数据模型的相关操作，从而实现对问题的解决。 抽象数据类型（Abstract Data Type，简称ADT）是由一种数据结构和在其上的一组操作（运算）所组成。抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型通常由具体语言系统内部定义，直接提供给用户使用；而抽象数据类型还包括用户在编程处理数据、设计软件系统时自己定义的数据类型，通常由用户自行定义，包括定义其所包含的数据（数据结构）和在这些数据上所进行的操作。在定义抽象数据类型时，就是定义其数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样具有较好的通用性和可移植性，便于用任何一种语言实现。 ADT 抽象数据类型名 { 数据：<数据描述> 操作：<基本操作的定义> }ADT 抽象数据类型名 ADT 复数{ 数据： 实部; 虚部; 操作： 初始化复数; 获取实部; 获取虚部; 获取模; 获取辐角; 复数加法; 复数减法; 复数乘法; 复数除法; }ADT 复数 为了便于理解和表达的简洁，对抽象数据类型定义中的数据（数据结构）及基本操作，我们采用中文说明和类C++语言的形式进行描述（借用C++语言的一些语法元素，但是不严格遵循C++语言）。例如，我们可以定义“复数”这种抽象数据类型来表示数学上的复数： 4 . 1 . 2 　 抽象数据类型的应用 利用抽象数据类型定义复数，并通过编程实现，就可以使用计算机处理复数了。除了数学运算外，在解决现实问题和实际编写计算机应用软件时，因为要解决的问题更复杂， 所以更需要大量应用抽象数据类型来描述问题和设计解决方案。 如项目范例中的俄罗斯方块游戏，方块的颜色、形状都有多种，每一个方块都有左 旋、右旋、左移、右移、下落等多种操作，变化较多。游戏程序实现的关键是如何操控这 些方块，可以定义一种抽象数据类型“方块”，其中包含方块的形状、颜色、中心点等， 以及对它的左旋、右旋、左移、右移、下落等多种操作。类似的，我们还可以将俄罗斯方 块游戏的区域也定义为一种抽象数据类型，从而完成游戏的设计。 （1）象棋游戏里（如图4-3所示），每一个棋子上面的文字都不一样，有的是“马”、有的是“兵”等，对阵双方的棋子颜色一般为黑色和红色，每个棋子必须响应鼠标或键盘的控制动作，实现棋子的拿起、移动、放下等操作。这里可以将棋子定义为一种抽象数据类型，其数据模型包括棋子的颜色、棋子的文字、棋子在棋盘上的坐标等，基本操作包括拿起、移动、放下等。 4 . 1 . 3 　 抽象数据类型的实现 为帮助大家更好地理解，接下来以定义抽象数据类型“长方形”为例，呈现抽象数据 类型的定义过程和程序实现过程。 假定用rectangle来表示“长方形”的抽象数据类型名，其数据部分长、宽用a、b表 示，类型为实数；其基本操作包括初始化、求长方形的周长和求长方形的面积，求周长的 函数名用perimeter表示，求面积的函数名用area表示，则长方形的ADT描述如下： 4.2　用抽象数据类型表示队列和栈 队列和栈是两种典型的抽象数据类型，因为在计算机解决实际问题和很多软件的实现 中，都会用到队列和栈。通过抽象数据类型来表示队列和栈，能够更加清楚地认识和理解 这两种数据类型的特征和操作。 4 . 2 . 1 　 用抽象数据类型表示队列 4 . 2 . 1 　 用抽象数据类型表示队列 队列是线性表的一种，队列的元素之间具有线性关系。另外，队列具有队头、队尾，元素从队尾入队、从队头出队，因此队列具有先进先出（FIFO）的特点。针对队列的操作有：初始化队列、元素入队、元素出队、求队列长度、队列判满、队列判空。我们可以用下面的抽象