资源简介

(共41张PPT)
课时3　抽象数据类型
第四章　树
1.理解抽象数据的概念，理解并体会抽象数据类型对数据处理的重要性。2.能用抽象数据类型表示栈、队列、二叉树，并定义其数据及基本操作，并尝试编写程序实现，进而提高学生的知识迁移能力。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.数据类型与抽象数据类型
(1)数据类型是指一组____________的值的集合及定义在此集合上的一些______的总称。
(2)抽象数据类型是指一个____________及定义在该模型上的一组操作，即一个____________、数据对象中______________________________以及对_____________________。
性质相同
操作
数学模型　
数据对象
各数据元素之间的关系
数据元素的操作
抽象数据类型与数据结构的关系。
抽象数据类型与数据结构是两个不同的概念，不能混为一谈。具体为：
①数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。
②抽象数据类型是指一个数学模型及定义在该模型上的一组操作，“抽象数据类型”本质是“数据类型”。我们可以用“抽象数据类型”来实现“数据结构”。
2.抽象数据类型(ADT)的描述
(1)定义一个抽象数据类型(ADT)，需要清晰地表述出________________________(如操作的名字、参数的个数和类型等)和____________(这个操作完成什么样的计算或产生什么效果等)。
(2)描述抽象数据类型的标准格式：
ADT 抽象数据类型名：
Data
数据元素之间逻辑关系的定义
Operation
各方面的形式要求
功能要求
操作1
　　　　 　初始条件
　　　　 　操作结果描述
操作2
　　　　　 ……
操作n
　　　　　 ……
end ADT
(3)线性表抽象数据类型
ADT List：
List(self)　　　#创建一个新表
is_empty(self)　#判断self是否为一个空表
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操作
3.抽象数据类型的作用
(1)_________________________________，便于程序正确性的证明和复杂性的分析；
(2)因为其_________的特点，在程序设计中容易纠正，具有很好的____________；
(3)由于抽象数据类型的表示和实现都可以封装起来，_____________________；
(4)_________算法与程序设计的复杂度，有助于在开发过程中少出差错，保证编写的程序有较高的_________，有益于算法的______，提高程序的____________。
程序结构清晰、层次分明
模块化
可维护性
便于移植和重用
降低了
可靠性
优化
运行效率
例题精析
2
例1 抽象数据类型的三个组成部分分别为数据对象、数据关系和(　　)
B
解析　本题主要考查的是抽象数据类型的组成。抽象数据类型的三个组成部分分别为数据对象、数据对象中各数据元素之间的关系和对数据元素的操作，因此答案为B。
A.数据类型 B.基本操作 C.数据结构 D.数据元素
变式训练　下列有关抽象数据类型的说法，正确的是(　　)
解析　本题主要考查的是抽象数据类型的定义。抽象数据类型是由一种数据结构和在其上的一组操作(运算)所组成，因此A选项错误；抽象数据类型和其在计算机内部如何表示和实现无关，因此B选项错误；定义一个抽象数据类型，不仅需要清晰表述出各方面的形式要求，还需要清晰表达出功能要求，因此D选项错误；Python的整型、字符串类型等也是一种抽象数据类型，因此答案为C。
C
A.抽象数据类型其实就是数据结构
B.抽象数据类型和其在计算机内部如何表示和实现有关
C.Python的整型其实也是一种抽象数据类型
D.定义一个抽象数据类型，只需要清晰表述出各方面的功能要求即可
例2 创建一个简单的ADT，如下所示：
class odd()：
def _ _init _ _(self，data)：
″″″初始化属性data″″″
self.data＝data
def pd(self)：
if self.data % 2＝＝0：
　　　　print(self.data，″是偶数″)
else：
　　　　print(self.data，″是奇数″)
# 创建实例：
my_pro＝odd(12)
my_pro.pd()
解析　本题主要考查的是抽象数据类型(ADT)的组成。def pd(self)的功能是定义pd操作，而不是函数。因此，不正确的是B。
B
A.创建的类名称为odd
B.def pd(self)的功能是定义pd函数
C.程序代码执行后的结果为“12是偶数”
D.my_pro为odd类的一个对象
变式训练　用抽象数据类型实现栈操作的代码如下：
class Stack()：
def _ _init_ _(self)：
self.my_stack＝[]
def my_push(self)：　#入栈操作
　　________________________
def my_pop(self)：　 #出栈操作
return self.my_stack.pop()
def size(self)：　　 #测试栈长度
return len(self.my_stack)
def isEmpty(self)：　 #判断栈是否为空
return self.my_stack＝＝[]
请在程序划线处填入合适的语句。
答案　self.my_stack.append(data)
解析　本题主要考查的是用抽象数据类型表示栈操作。栈的特点是先进后出，元素入栈时是从栈的首部插入，因此代码为self.my_stack.append(data)。
随堂检测
3
1.下列关于抽象对象的作用的说法中，正确的是(　　)
A
解析　本题主要考查的是抽象对象的作用。使用抽象数据类型编写出来的程序结构清晰、层次分明，便于程序正确性的证明和复杂度的分析；抽象数据类型的表示和实现都可以封装起来，便于移植和重用；使用抽象数据类型编写程序，降低了算法和程序设计的复杂度，有助于在开发过程中少出差错，保证编写程序有较高的可靠性，同时允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率。因此，答案为A。
A.使用抽象数据类型编写出来的程序结构清晰、层次分明
B.使用抽象数据类型编写出来的程序，其正确性得不到保障
C.使用抽象数据类型编写出来的程序，移植性较差
D.使用抽象数据类型编写程序，算法复杂度较高，一般情况不建议使用
A.len() B.append() C.del D.values()
B
解析　选项B的append()是列表数据类型在尾部添加数据项的方法，字典中添加新的键值对的方法为dic[新键]＝值。
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，″不是水仙花数″)
C
# 创建实例：
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。
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)
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)请在程序划线处填入合适的语句。
答案　(1)2*6＝12　(2)①self.ch＝ch
②c＝self.data1/self.data2
解析　本题主要考查的是定义一个抽象数据类型。(1)根据语句my_operator＝operator(2，6，″*″)可知，数据data1和data2进行乘法运算，因此输出结果为2*6＝12。(2)划线①处的语句功能是初始化属性ch，因此填入的代码为self.ch＝ch。②处代码表示data1和data2进行除法运算，结果存储在变量c中，因此，②处应填入的代码为c＝self.data1/self.data2。
4
巩固与提升
基础巩固
能力提升
A.抽象数据是指一个数学模型及定义在该模型上的一组操作
B.Python的一个内置类型不是一个抽象数据类型
C.抽象数据类型是一种思想，也是一种技术
D.定义一个抽象数据类型(ADT)，目的是要定义一类计算对象，使它们具有某些特定的功能
B
解析　Python的一个内置类型也可以看作是一个抽象数据类型，因此不正确的是B。
2.下列选项中属于Python抽象数据类型(ADT)优点的是(　　)
C
A.使用抽象数据类型编写的程序结构不清晰、层次不分明
B.抽象数据类型的模块化特点，在程序设计中容易纠正，但不易维护
C.由于抽象数据类型的表示和实现都可以封装起来，便于移植和重用
D.使用抽象数据类型编写程序，增加了算法复杂度，降低了程序运行的效率
解析　使用抽象数据类型编写的程序结构清晰、层次分明，因此A选项错误；抽象数据类型的模块化特点，在程序设计中容易纠正，具有良好的维护性，因此B选项错误；使用抽象数据类型编写程序时，因为算法设计与数据结构设计的隔开，降低了算法复杂度，同时允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率，因此D选项错误；由于抽象数据类型的表示和实现都可以封装起来，便于移植和重用，是正确的。因此，答案为C。
3.下列是一个简单的ADT：
class Sstring：
def _ _init _ _(self，str1)：
self.ss＝str1
def substr(self，a，b)：
return self.ss[a－1：b]
def concat(self，str2)：
return self.ss＋str2
sstr1＝Sstring(″Python″)　　　　
print(sstr1.substr(2，4))
print(sstr1.concat(″ is so easy！″))
D
解析　执行代码“print(sstr1.concat(″is so easy！″))”，输出结果为“Python is so easy！”，因此，答案为D。
A.Sstring为抽象数据类型名
B.sstr1为Sstring类的一个对象
C.执行代码“print(sstr1.substr(2，4))”，输出结果为“yth”
D.执行代码“print(sstr1.concat(″is so easy！″))”，输出结果为“yth is so easy！”
4.下列是一个简单的ADT：
class xcal：
def _ _init _ _(self，numx，numy)：
self.numx＝numx
self.numy＝numy
def xadd(self，another)：
numx＝self.numx*another.numx
numy＝self.numy*another.numy
return xcal(numx，numy)
def print(self)：
print(str(self.numx)＋'/'＋str(self.numy))
x＝xcal(2，3)
y＝x.xadd(xcal(4，5))
D
y.print()程序运行后，输出的结果为(　　)
A.6/20 B.15/8 C.10/12 D.8/15
解析　根据xadd操作中的语句可知，程序运行后的结果为8/15，因此，答案为D。
5.用抽象数据类型实现队列操作的代码如下，请回答下列问题：
class Queue：
def _ _init _ _(self)：
self.queue＝[]
def isEmpty(self)：
return self.queue＝＝[]
def enqueue(self，data)：　#入队操作
　　　　①________________
def dequeue(self)：　 #出队操作
if len(self.queue)：
　　　__②________________
def size(self)：　　 #测试队列长度
return len(self.queue)
q＝Queue()
q.enqueue(8)
q.enqueue(9)
q.enqueue(10)
while not q.isEmpty()：
print(q.dequeue()，end＝″″)
(1)程序运行后，输出的结果是__________________________________________。
(2)请在程序划线处填入合适的代码。
答案　(1)8 9 10
(2)①self.queue.insert(0，data) ②return self.queue.pop()
解析　本题主要考查的是用抽象数据类型表示队列操作。队列的特点是先进先出，元素入队时是从队列的首部插入，因此代码为self.queue.insert(0，data)；②处代码为出队操作，通过pop()方法实现，将元素从队尾取出，因此代码为return self.queue.pop()。
6.创建一个ADT，实现如下功能：输入一个18位的身份证号码，输出该身份证的人的性别。
判断方法：根据身份证号的第17位上的数字来判断，若是奇数，则表示是位男士；若是偶数，则表示是位女士。
程序运行示例如图所示：
请输入身份证号：330425198202261156
身份证号为：330425198202261156是位男士。
实现上述功能的代码如下，请回答下列问题：
class sexpd：
def _ _init _ _(self，sfzcode)：
　　　self.code＝sfzcode
def isxb(self)：
　　xbcode＝int(self.code[16])



sfzcode＝input(″请输入身份证号：″)
sfz1＝sexpd(sfzcode)
sfz1.isxb()
(1)程序运行时，若输入的18位身份证号为“330425198002251269”，则输出结果为____________________________。
(2)完善isxb(self)操作中的程序代码。
答案　(1)身份证号为：330425198002251269 是位女士
(2)isxb(self)操作中的程序代码如下：
if xbcode % 2＝＝1：
print(″身份证号为：″，self.code，″是位男士。″)
else：
print(″身份证号为：″，self.code，″是位女士。″)
解析　本题主要考查的是ADT的实际应用。(1)身份证号330425198002251269的第17位上的数字是6，是偶数，因此该身份证号的人的性别是位女士，参考输出示例可知，输出结果为“身份证号为：330425198002251269 是位女士。”。(2)isxb(self)操作中的代码的功能是：根据身份证号的第17位上(索引位置为16)的数字的奇偶性来判断性别，因此使用if语句来实现，方法不唯一，只要输出结果正确即可。课时3　抽象数据类型
课时目标
1.理解抽象数据的概念，理解并体会抽象数据类型对数据处理的重要性。2.能用抽象数据类型表示栈、队列、二叉树，并定义其数据及基本操作，并尝试编写程序实现，进而提高学生的知识迁移能力。
1.数据类型与抽象数据类型
(1)数据类型是指一组____________的值的集合及定义在此集合上的一些________的总称。
(2)抽象数据类型是指一个________________及定义在该模型上的一组操作，即一个____________、数据对象中______________以及对________________。
抽象数据类型与数据结构的关系。
抽象数据类型与数据结构是两个不同的概念，不能混为一谈。具体为：
①数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。
②抽象数据类型是指一个数学模型及定义在该模型上的一组操作，“抽象数据类型”本质是“数据类型”。我们可以用“抽象数据类型”来实现“数据结构”。
2.抽象数据类型(ADT)的描述
(1)定义一个抽象数据类型(ADT)，需要清晰地表述出____________________(如操作的名字、参数的个数和类型等)和____________(这个操作完成什么样的计算或产生什么效果等)。
(2)描述抽象数据类型的标准格式：
ADT 抽象数据类型名：
Data
数据元素之间逻辑关系的定义
Operation
操作1
　　　　 　初始条件
　　　　 　操作结果描述
操作2
　　　　　 ……
操作n
　　　　　 ……
end ADT
(3)线性表抽象数据类型
ADT List：
List(self)　　　#创建一个新表
is_empty(self)　#判断self是否为一个空表
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操作
3.抽象数据类型的作用
(1)________________________，便于程序正确性的证明和复杂性的分析；
(2)因为其________的特点，在程序设计中容易纠正，具有很好的________；
(3)由于抽象数据类型的表示和实现都可以封装起来，__________________；
(4)________算法与程序设计的复杂度，有助于在开发过程中少出差错，保证编写的程序有较高的________，有益于算法的________，提高程序的____________。
例1 抽象数据类型的三个组成部分分别为数据对象、数据关系和(　　)
A.数据类型 B.基本操作
C.数据结构 D.数据元素
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　下列有关抽象数据类型的说法，正确的是(　　)
A.抽象数据类型其实就是数据结构
B.抽象数据类型和其在计算机内部如何表示和实现有关
C.Python的整型其实也是一种抽象数据类型
D.定义一个抽象数据类型，只需要清晰表述出各方面的功能要求即可
例2 创建一个简单的ADT，如下所示：
class odd()：
def _ _init _ _(self，data)：
″″″初始化属性data″″″
self.data＝data
def pd(self)：
if self.data % 2＝＝0：
　　　　print(self.data，″是偶数″)
else：
　　　　print(self.data，″是奇数″)
# 创建实例：
my_pro＝odd(12)
my_pro.pd()
下列有关该抽象数据类型(ADT)实例的说法中，不正确的是(　　)
A.创建的类名称为odd
B.def pd(self)的功能是定义pd函数
C.程序代码执行后的结果为“12是偶数”
D.my_pro为odd类的一个对象
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　用抽象数据类型实现栈操作的代码如下：
class Stack()：
def _ _init_ _(self)：
self.my_stack＝[]
def my_push(self)：　#入栈操作
　　________________________
def my_pop(self)：　 #出栈操作
return self.my_stack.pop()
def size(self)：　　 #测试栈长度
return len(self.my_stack)
def isEmpty(self)：　 #判断栈是否为空
return self.my_stack＝＝[]
请在程序划线处填入合适的语句。
1.下列关于抽象对象的作用的说法中，正确的是(　　)
A.使用抽象数据类型编写出来的程序结构清晰、层次分明
B.使用抽象数据类型编写出来的程序，其正确性得不到保障
C.使用抽象数据类型编写出来的程序，移植性较差
D.使用抽象数据类型编写程序，算法复杂度较高，一般情况不建议使用
2.Python中有字典数据类型，以下不属于该类型内建函数的方法的是(　　)
A.len() B.append() C.del D.values()
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类的一个对象
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)
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)请在程序划线处填入合适的语句。
课时3　抽象数据类型
知识梳理
1.(1)性质相同　操作　(2)数学模型　数据对象　各数据元素之间的关系　数据元素的操作
2.(1)各方面的形式要求　功能要求
3.(1)程序结构清晰、层次分明　(2)模块化　可维护性　(3)便于移植和重用　(4)降低了　可靠性　优化　运行效率
例题精析
例1　B　[本题主要考查的是抽象数据类型的组成。抽象数据类型的三个组成部分分别为数据对象、数据对象中各数据元素之间的关系和对数据元素的操作，因此答案为B。]
变式训练　C　[本题主要考查的是抽象数据类型的定义。抽象数据类型是由一种数据结构和在其上的一组操作(运算)所组成，因此A选项错误；抽象数据类型和其在计算机内部如何表示和实现无关，因此B选项错误；定义一个抽象数据类型，不仅需要清晰表述出各方面的形式要求，还需要清晰表达出功能要求，因此D选项错误；Python的整型、字符串类型等也是一种抽象数据类型，因此答案为C。]
例2　B　[本题主要考查的是抽象数据类型(ADT)的组成。def pd(self)的功能是定义pd操作，而不是函数。因此，不正确的是B。]
变式训练　self.my_stack.append(data)
解析　本题主要考查的是用抽象数据类型表示栈操作。栈的特点是先进后出，元素入栈时是从栈的首部插入，因此代码为self.my_stack.append(data)。
随堂检测
1.A　[本题主要考查的是抽象对象的作用。使用抽象数据类型编写出来的程序结构清晰、层次分明，便于程序正确性的证明和复杂度的分析；抽象数据类型的表示和实现都可以封装起来，便于移植和重用；使用抽象数据类型编写程序，降低了算法和程序设计的复杂度，有助于在开发过程中少出差错，保证编写程序有较高的可靠性，同时允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率。因此，答案为A。]
2.B　[选项B的append()是列表数据类型在尾部添加数据项的方法，字典中添加新的键值对的方法为dic[新键]＝值。]
3.C　[本题主要考查的是定义一个抽象数据类型(ADT)的。创建的抽象数据类型名称为flower，因此A选项错误；程序代码执行后的结果为“153是水仙花数”，因此B选项错误；my_num为flower类的一个对象，因此D选项错误。def pdflowernum(self)的功能是定义flower类的一个操作，因此，正确的是C。]
4.(1)2*6＝12　(2)①self.ch＝ch　②c＝self.data1/self.data2
解析　本题主要考查的是定义一个抽象数据类型。(1)根据语句my_operator＝operator(2，6，″*″)可知，数据data1和data2进行乘法运算，因此输出结果为2*6＝12。(2)划线①处的语句功能是初始化属性ch，因此填入的代码为self.ch＝ch。②处代码表示data1和data2进行除法运算，结果存储在变量c中，因此，②处应填入的代码为c＝self.data1/self.data2。

展开更多......

收起↑