资源简介

(共18张PPT)
第四章 树
4.3 抽象数据类型
学习目标
抽象数据类型
数据类型与抽象数据类型
抽象数据类型的应用
数据类型与抽象数据类型
数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
·数据类型的概念
·基本数据类型
整型、实型、布尔型、列表、字符串、字典
·结构数据类型
抽象数据类型（类）
如python语言中的语句：
A=11.4 #定义浮点数变量A并赋值
C=A+5 #定义浮点数变量C并通过表达式赋值
抽象数据类型
数据类型与抽象数据类型
抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。
·抽象数据类型的概念
抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必须的信息，实现抽象化后便于实现功能，提高模块独立性。
程序语言的一个内置类型就可以看作是一个抽象数据类型，如整型（int）就是一个抽象数据类型，在整型对象的内部提供了一组操作可供编程者使用，每个操作都有明确的抽象意义，如“+”、“—”等。
抽象数据类型
字符串数据类型
整型数据类型
数据类型
字符串对象
操作
求串长度
取子串
整型对象
操作
求和
求余数
数据结构
具体
操作
抽象数据类型
法师 -- 甄姬
人物外貌：形象，衣服等
人物皮肤
人物符文
人物特征
人物的移动：左右，上下，闪现，有无鞋子等
人物施放技能：动画，伤害量等
抽象数据类型
数据类型与抽象数据类型
例如：
在王者荣耀中，游戏人物的设定，一般都用抽象数据类型来定义人物对象。
因为所有的人物都符合几个特征：人物形象
人物的符文
人物的移动
人物有三个技能和被动
人物施放技能
人物技能的伤害量
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型的标准格式：
ADT抽象数据类型名：
Data
数据元素之间逻辑关系的定义
Operation
操作1
初始条件
操作结果描述
操作2
......
操作n
......
endADT
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型的标准格式：
ADT抽象数据类型名：
Data
数据元素之间逻辑关系的定义
Operation
操作1
初始条件
操作结果描述
操作2
......
操作n
......
endADT
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型（链表节点）
# # 定义一个链表节点的抽象类
class Node( ):
# 初始化链表节点为空
def __init__(self, value, next=None):
self._value = value
self._next = next
# 取当前节点的数值
def getValue(self):
return self._value
ADT类型：class
抽象数据类型名：Node
初始化条件：__init__函数
操作：getValue函数
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型
列表，字符串，队列，树等都是抽象数据类型。
列表：
ADT List:
List( self ) #创建一个新表
is_empty( self ) #判断self是否为一个空表
len( self ) #返回表的长度
append( self, elem ) #在表尾插入元素elem
insert( self, elem, i ) #在表的第i个位置插入元素elem
del( self, i ) #删除第i个元素
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型
列表，字符串，队列，树等都是抽象数据类型。
字符串：
ADT String:
String( self, sseq )
is_empty( self )
len( self )
char( self, index)
substr( self, a, b)
match( self, string )
#基于字符串序列sseq建立一个字符串
#判断字符串是否空串
#取字符串的长度
#取得字符串中位置index的字符
#取得字符串中[a,b]的字串，左闭右开区间
#查找字符串string在本字符串中第一次出现的位置
现有一字符串对象str,若要获取字符串[a,b](左闭右闭）区间内的字串，正确的调用方式为______.
substr(str,a,b+1）
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型
列表，字符串，队列，树等都是抽象数据类型。
#创建空队列
#判断队列是否为空，空时返回True,否则返回False
#将元素elem加入队列，即入队
#出队
#查看队列里最早进入的元素，不删除
队列：
ADT Queue:
Queue( self)
is_empty( self )
enqueue( self, elem )
dequeue( self )
peek( self)
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型
列表，字符串，队列，树等都是抽象数据类型。
#创建空栈
#判断栈是否为空，空时返回True,否则返回False
#将元素elem加入栈，即入栈
#出栈
#查看栈顶元素，不删除
栈：
ADT Stack:
Stack( self)
is_empty( self )
push( self, elem )
pop( self )
peek( self)
抽象数据类型
数据类型与抽象数据类型
·抽象数据类型的作用
程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析。
因为模块化的特点，便于改正错误的代码，利于维护系统。
抽象数据类型的表示和实现利于封装，便于代码的移植和重用。
使得算法设计和数据结构设计分开，降低了程序的复杂性，利于编写代码实现的可靠性。
使得数据结构可自由选择，给了算法的优化空间，提高了程序运行的效率。
二叉树Python代码实现
class Node: #建立二叉树
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
二叉树Python代码实现
root=Node('A',Node('B',Node('D'),Node('E')),Node('C',rigt=Node('F',Node('G'))))
print("前序遍历：")
preTraverse(root)
print("中序遍历：")
midTraverse(root)
print("后序遍历：")
afterTraverse(root)
if __name__=='__main__’:
二叉树Python代码实现
def preTraverse(root):#前序遍历
if root==None:
return
print(____________)
preTraverse(_____________)
preTraverse(______________)
def midTraverse(root): #中序遍历
if root==None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
def afterTraverse(root): #后序遍历
if root==None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
root.value
root.left
root.right
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
递归的核心是整体的方法和
局部的方法是一致的。
递归需要注意的方面：
（1）递归的参数和返回值
（2）递归的终止条件
（3）对下一项进行函数自身的调用

展开更多......

收起↑