资源简介

(共17张PPT)
三、 抽象数据类型
第四章　树
知识过关
1. 数据类型
数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。每种程序设计语言都提供了一些内置数据类型,并为每个内置类型提供了一些操作,如Python语言中的语句:
a=5　　　　 #定义了整型变量a并赋值
b=1.3　　 　#定义了浮点数变量b并赋值
c=a*2+b　　　#定义了浮点数变量c并通过表达式赋值
其中,整型、浮点数型等是Python中内置的数据类型,而运算“+”是定义在内置类型上的一种操作。这样的内置数据类型和操作在Python语言中还有很多。
2. 抽象数据类型
抽象数据类型(ADT)是一个数学模型及其定义在该模型上的一组操作。程序设计语言中的内置类型可以看作是一种抽象数据类型。如Python语言中的字符串类型就可以看作是一种抽象数据类型。在字符串数据类型中提供了一组可供编程者直接使用的操作。如Python语言中的语句:
n=len(s)　#利用len操作获取字符串长度
抽象数据类型主要包括程序设计语言内置的数据类型(如整型)、程序设计语言的内建函数(如len)和自定义的数据类型和操作等。其中自定义的操作包括一个数据对象、数据对象各元素之间的关系及对数据元素的操作。
3. 抽象数据类型的描述
定义一个抽象数据类型,需要清晰地表述各方面的形式要求和功能要求。
(1)形式要求:类型的名称、操作的名字、参数的个数和类型。
(2)功能要求:操作所能完成的计算和产生的效果等,主要体现为一组可以对它们使用的操作。
具体格式如下:
ADT 抽象数据类型名:
Data
　　数据元素之间逻辑关系的定义
Operation
　　操作1
　　　　初始条件
　　　　操作结果描述
　　操作2
　　　　......
　　操作n
　　　　......
endADT
4. 抽象数据类型的作用
抽象数据类型主要体现了程序设计中问题分解、抽象和信息隐藏的特征。主要表现为:能够使编写出来的程序结构清晰、层次分明、具有很好的可维护性、便于移植和重用;降低算法和程序设计的复杂度、编写的程序有较高的可靠性,容易优化算法和提高程序的运行效率。
典例精选
【例1】 下列关于抽象及抽象数据类型的说法,错. 误. 的是(　　)
A. 抽象是指抽取出事物具有的普遍性本质,是对具体事物的一个概括,并隐藏了繁杂的细节
B. 使用抽象数据类型编写的程序具有模块化特点,但丧失了可维护性
C. Python程序设计语言的一个内置类型就可以看作一个抽象数据类型
D. 在Python语言中,字符串数据类型的“+”操作在字符串类中已经有定义
【解析】 Python的字符串类型(str)就是一个抽象数据类型,在字符串对象的内部提供了一组操作可供编程者使用,每个操作都有明确的抽象意义,编程者不必受制于操作内部的具体实现技术,在程序设计时可以直接使用,D符合题意。
D
【例2】 下面给出了字符串抽象数据类型的部分描述信息:
ADT String:
　　String(self,sseq)　 #基于字符序列sseq建立一个字符串
　　is_empty(self)　　 #判断本字符串是否空串
　　len(self)　　　　　 #取得字符串的长度
　　char(self,index)　 #取得字符串中位置index的字符
　　substr(self,a,b)　 #取得字符串中[a:b]的子串,左闭右开区间
　　match(self,string) #查找串string在本字符串中第一次出现的位置
　　concat(self,string) #获得本字符串与另一个字符串string的拼接串
　　subst(self,str1,str2) #获得将本字符串里的子串str1替换为str2
现有一个字符串对象s,请回答下列问题:
(1)根据字符串抽象数据类型的描述,若要获取字符串[m:n](左闭右闭)区间内容的子串,
正确的调用方式为____________________。若要将字符串中的“app”替换为“see”,正确的调用方式为________________________。
(2)当s=""时,is_empty(s)的返回值为True,则当s="Python 3"时,is_empty(s)的返回值为__________,len(s)的返回值为__________。
(3)当要调用match方法时,需要提供的参数个数为__________个。
【解析】 (3)根据文字说明可知,self是类方法中默认的参数,代表当前对象的地址,当要调用match方法时不必传入相应的参数,故只需要1个参数。
substr(s,m,n+1)
subst(s,"app","see")
False
8
1
自我检测
1. 下列关于抽象对象的作用的说法,正确的是(　　)
A. 使用抽象数据类型编写出来的程序结构清晰、层次分明
B. 使用抽象数据类型编写出来的程序,其正确性得不到保障
C. 使用抽象数据类型编写出来的程序,移植性较差
D. 使用抽象数据类型编写程序,算法复杂度较高,一般情况下不建议使用
【解析】 本题考查抽象对象的作用。使用抽象数据类型编写出来的程序结构清晰、层次分明,便于程序正确性的证明和复杂度的分析,A正确,B错误。抽象数据类型的表示和实现都可以封装起来,便于移植和重用,C错误。使用抽象数据类型编写程序,降低了算法和程序设计的复杂度,有助于在开发过程中少出差错,保证编写程序有较高的可靠性,同时允许数据结构的自由选择,给了算法的优化空间,提高了程序运行的效率,D错误。
A
2. Python中有字典数据类型,下列不. 属. 于. 该类型内建函数的方法的是(　　)
A. len() B. append()
C. del D. values()
【解析】 append()是列表数据类型在尾部添加数据项的方法,字典中添加新的键值对的方法为dic[新键]=值,B符合题意。
B
3. 下面是一个判断三位数整数是否为水仙花数的简单ADT:
class flower():
　　def _ init _ (self,data):
　　　　#初始化属性data
　　　　self.data=data
　　def pdflowernum(self):
　　　　a=self.data∥100
　　　　b=self.data∥10%10
　　　　c=self.data%10
　　　　if a**3+b**3+c**3==self.data:
　　　　　　print(self.data,"是水仙花数")
　　　　else:
　　　　　　print(self.data,"不是水仙花数")
# 创建实例:
my_num=flower(153)
my_num.pdflowernum()
下列关于该抽象数据类型(ADT)实例的说法,正确的是(　　)
A. 创建的抽象数据类型名称为pdflowernum
B. 程序代码执行后的结果为“153不是水仙花数”
C. def pdflowernum(self)的功能是定义flower类的一个操作
D. flower为my_num类的一个对象
【解析】 本题考查定义一个抽象数据类型(ADT)。创建的抽象数据类型名称为flower,A错误。程序代码执行后的结果为“153是水仙花数”,B错误。my_num为flower类的一个对象,D错误。def pdflowernum(self)的功能是定义flower类的一个操作,C正确。
C
4. 下面是一个加减乘除四则运算的ADT,请回答下列问题:
class operator():
　def_init_(self,data1,data2,ch):
　　　self.data1=data1
　　　self.data2=data2
　　　①________________
　def cal(self):
　　　if self.ch=="+":
　　　　　c=self.data1+self.data2
　　　　　print(self.data1,"+",self.data2,"=",c)
　　　if self.ch=="－":
　　　　　c=self.data1－self.data2
　　　　　print(self.data1,"－",self.data2,"=",c)
　　　if self.ch=="*":
　　　　　c=self.data1*self.data2
　　　　　print(self.data1,"*",self.data2,"=",c)
self. ch=ch
【解析】 本题考查定义一个抽象数据类型。(1)根据语句my_operator=operator(2,6,"*")可知,数据data1和data2进行乘法运算,因此输出结果为2*6=12。(2)①处的语句功能是初始化属性ch,因此填入的代码为self. ch=ch。②处代码表示data1和data2进行除法运算,结果存储在变量c中,因此,②处应填入的代码为c=self. data1/self. data2。
　　　if self.ch=="/":
　　　　　if self.data2 !=0:
　　　　　　②_______________________
　　　　　　print(self.data1,"/",self.data2,"=",c)
　　　　else:
　　　　　　print("分母不能为0")
# 创建实例:
my_operator=operator(2,6,"*")
my_operator.cal()
(1)程序运行后,输出的结果是__________。
(2)请在画线处填入合适的代码。
c=self. data1/self. data2
2*6=12

展开更多......

收起↑