(
课件网) 第四章 树 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） 抽象数据类型 数据类型与抽象数据类型 ·抽象数据类型 列表，字符串，队列，树等都是 ... ...
