4.3抽象数据类型　课件-2021-2022学年浙教版（2019）高中信息技术选修1（14张PPT）

(共14张PPT)
知识回顾
2.数据类型
数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。数据类型可以分为基本数据类型（也称为原子数据类型）和结构数据类型。
基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。
结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，这种新类型由用户根据实际需要定义，能较好地描述数据元素数据项组成以及数据元素之间的逻辑关系，方便用户根据数据之间逻辑关系的特点进行数据处理，如很多编程语言中提供的记录类型、集合等。
基本数据类型
结构数据类型
CHZX
4.3 抽象数据类型
浙江省高中信息技术 选择性必修一 《数据与数据结构》
数据类型
shujuleixing
数据类型：指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。
基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。
基本数据类型
抽象数据类型
chouxiangshujuleixing
抽象数据类型： ( Abstract Data Type,简称ADT)是指一个数学模型及定义在该模型上的一组操作
ADT的基本思想是抽象，它的定义仅取决于它的一组逻辑特性，把数据结构及其操作作为一个整体来研究，而与其在计算机内部如何表示和实现无关。
1.概念
抽象数据类型
chouxiangshujuleixing
抽象数据类型： ( Abstract Data Type,简称ADT)是指一个数学模型及定义在该模型上的一组操作
1.概念
抽象数据类型除了那些已经定义并实现的数据类型，还可以是
编程者在程序设计时使用的函数或者单独定义的数据类型等。
如使用Python的内建函数时，编程者只需考虑函数的功能是否满
足实际需要，再确保函数调用时的表达式是否符合函数构造的要
求，就可以使用此函数，而不需要知道该函数内部实现的任何具
体细节。
max( )
insert( )
head( )
plot( )
抽象数据类型
chouxiangshujuleixing
定义一个抽象数据类型，需要清晰地表述出各方面的形式要求和功能要求。
2.标准格式
练一练
试一试：定义一个矩形的抽象数据类型
ADT Rectangle
height; #长度数据
width; #宽度数据
calcPerimeter(self) #求矩形的周长
calcArea(self) #求矩形的面积
练一练
矩形抽象数据类型的程序实现
抽象数据类型
chouxiangshujuleixing
在前三章有关线性表数据结构的学习中，已经知道了线性表数据结构会
涉及的一些操作。比如：
1.如何为创建操作提供初始元素序列；
2.检查线性表中是否存在某个特定数据对象；
3.改变线性表中的内容，包括加入新元素或删除已有元素等；
4.实现一个或两个表的操作，包括表的组合操作等；
5.实现对线性表中的每一个元素的操作，即对表元素的遍历。
抽象数据类型
chouxiangshujuleixing
下面呈现的是一个简单的线性表抽象数据类型，其中定义了一组最基本的操作。
ADT List:
List(self) #创建一个新表
is_empty(self) #判断sellf是否为一个空表
len(self) #返回表的长度
prepend(self,elem) #在表头插入元素elem
append(self,elem) #在表尾插入元素elem
insert(self,elem,i) #在表的第i个位置插入元素elem
del_first(self) #删除第一个元素
del_last(self) #删除最后一个元素
del(self,i) #删除第i个元素
search(self,elem) #查找元素elem在表中第一次出现的位置
forall(self,op) #对表中的每个元素执行op操作
练一练
列表，字符串，队列，树等都是抽象数据类型。
列表：
ADT List:
List( self )
is_empty( self )
len( self )
append( self, elem )
instert( self, elem, i )
del( self, i )
字符串：
ADT String:
String( self, sseq )
is_empty( self )
len( self )
char( self, index)
substr( self, a, b)
match( self, string )
队列：
ADT Queue:
Queue( self)
is_empty( self )
enqueue( self, elem )
dequeue( self )
peek( self)
抽象数据类型
chouxiangshujuleixing
3.作用
程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析。
因为模块化的特点，便于改正错误的代码，利于维护系统。
抽象数据类型的表示和实现利于封装，便于代码的移植和重用。
使得算法设计和数据结构设计分开，降低了程序的复杂性，利于编写代码实现的可靠性。
使得数据结构可自由选择，给了算法的优化空间，提高了程序运行的效率。
抽象数据类型
chouxiangshujuleixing
4.应用
·实例（二叉树）
class BTree(object):
# 初始化
def __init__(self, data=None, left=None, right=None):
self.data = data # 数据域
self.left = left # 左子树
self.right = right # 右子树
# 前序遍历
def preorder(self):
if self.data is not None:
print(self.data, end=' ')
if self.left is not None:
self.left.preorder()
if self.right is not None:
self.right.preorder()
# 中序遍历
def inorder(self):
if self.left is not None:
self.left.inorder()
if self.data is not None:
print(self.data, end=' ')
if self.right is not None:
self.right.inorder()
# 后序遍历
def postorder(self):
if self.left is not None:
self.left.postorder()
if self.right is not None:
self.right.postorder()
if self.data is not None:
print(self.data, end=' ')
练一练
2.创建一个简单的ADT，如下所示：
Class Nd( ):
def _init_(self,data):
self.data=data
def judge(self):
if self.data%5==0:
print(self.data,“是5的倍数”)
else:
print(self.data,“不是5的倍数”)
#创建实例
my_data=Nd(10)
my_data.judge ( )
下列有关该抽象数据类型（ADT）实例的说法中，不正确的是（ ）
A.创建的类名称为Nd B.def judge(self)的功能是定义judge函数
C.程序代码执行后的结果为“10是5的倍数”
D.my_data为Nd类的一个对象
B