抽象数据类型　 【核心知识精讲精析】 浙教版（2019）高中信息技术选修1

第四章

树

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

抽象数据类型

数据类型与抽象数据类型·抽象数据类型（链表节点）##定义一个链表节点的抽象类classNode(

):

#初始化链表节点为空def__init__(self,value,next=None):self._value=valueself._next=next

#取当前节点的数值defgetValue(self):returnself._valueADT类型：class抽象数据类型名：Node初始化条件：__init__函数操作：getValue函数

抽象数据类型

数据类型与抽象数据类型·抽象数据类型列表，字符串，队列，树等都是抽象数据类型。列表：ADTList:List(self)#创建一个新表is_empty(self)#判断self是否为一个空表len(self)#返回表的长度append(self,elem)#在表尾插入元素elem

insert(self,elem,i)#在表的第i个位置插入元素elemdel(self,i)#删除第i个元素

抽象数据类型

数据类型与抽象数据类型·抽象数据类型列表，字符串，队列，树等都是抽象数据类型。字符串：ADTString: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加入队列，即入队#出队#查看队列里最早进入的元素，不删除队列：ADTQueue:

Queue(self)is_empty(self)

enqueue(self,elem)

dequeue(self)peek(self)

抽象数据类型

数据类型与抽象数据类型·抽象数据类型列表，字符串，队列，树等都是抽象数据类型。#创建空栈#判断栈是否为空，空时返回True,否则返回False#将元素elem加入栈，即入栈#出栈#查看栈顶元素，不删除栈：ADTStack:

Stack(self)is_empty(self)

push(self,elem)

pop(self)peek(self)

抽象数据类型

数据类型与抽象数据类型·抽象数据类型的作用程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析。因为模块化的特点，便于改正错误的代码，利于维护系统。抽象数据类型的表示和实现利于封装，便于代码的移植和重用。使得算法设计和数据结构设计分开，降低了程序的复杂性，利于编写代码实现的可靠性。使得数据结构可自由选择，给了算法的优化空间，提高了程序运行的效率。二叉树Python代码实现classNode:#建立二叉树

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代码实现defpreTraverse(root):#前序遍历ifroot==None: returnprint(____________)preTraverse(_____________)preTraverse(______________)defmidTraverse(root):#中序遍历

ifroot==None:returnmidTraverse(root.left)print(root.value)midTraverse(root.right)defafterTraverse(root):#后序遍历

ifroot==None:returnafterTraverse(root.left)afterTraverse(root.right)print(root.value)root.valueroot.leftroot.rightifroot==None:

returnpr