4.3抽象数据类型课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第四章浙教版（2019）

抽象数据类型 信息技术 选考课程 一、数据类型、数据结构和抽象数据类型 数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 int int int int int int str str str str str str a=1;b=2 c=a+b print(c) a=“1”;b=“2” c=a+b print(c) 一、数据类型、数据结构和抽象数据类型 数据结构指的是数据之间的相互关系，即数据的组织形式 数组 链表 A B C D E F G H 树 逻辑结构+物理结构+操作 一、数据类型、数据结构和抽象数据类型 抽象数据类型( Abstract Data Type,简称ADT)是指一个数学模型及定义在该模型上的一组操作 取字符串长度(len) 截取子串(substr) 拼接字符串(concat) …… 字符串对象 字符串抽象数据类型 数组、链表、队列、栈、树的这些数据结构数据能否抽象？ 数组 数组 数组 数组 数组 二、抽象数据类型的描述 定义一个抽象数据类型： ● 类型名 ● 形式要求(如操作的名字、参数的个数和类型等) ● 功能要求(希望这个操作完成什么样的计算或产生什么效果等) ADT 抽象数据类型名： Data 数据元素之间逻辑关系的定义 Operation 操作1 初始条件 操作结果描述 操作2 …… 操作n …… endADT 构造操作 解析操作 变动操作 二、抽象数据类型的描述 – 以cat为例 ADT cat： cat(name,color,sex,weight) cat_attribute() play(action) feed() endADT class cat: #初始化一只猫 def __init__(self,name,color,sex,weight=2): #查看猫的状况 def attribute(self): #逗猫 def play(self,action): #喂猫 def feed(self): python利用class定义（类定义）实现抽象数据类型 构造一只猫 解析猫的状况 变动猫的属性 二、抽象数据类型的描述 线性表数据结构涉及的操作为例： 1、如何为创建操作提供初始元素序列； 2、检查线性表中是否存在某个特定数据对象； 3、改线性表中的内容，包括加入新元素或删除已有元素等； 4、实现一个或两个表的操作，包括表的组合操作等； 5、实现对线性表中的每一个元素的操作，即对表元素的遍历。 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个元素 #查找元素elem在表中第一次出现的位置 search(self,elem) forall(self,op) #对表中的每个元素执行op操作 二、抽象数据类型的描述 – 课堂练习 结合第三章中栈数据结构的相关操作，尝试定义栈的抽象数据类型。 ADT Stack: Stack(self) #创建空栈 is_empty(self) #判断栈是否为空，空时返回True否则返回False push(self,elem) #将元素elem加入栈，即入栈 pop(self) #删除栈里最后压入的元素并将其返回，即出栈 top(self) #取得栈里最后压入的元素，不删除 三、抽象数据类型的作用 程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析； 可维护性； 便于移植和重用； 程序 = 算法 + 数据结构，降低复杂度，减少差错，提高可靠性，允许数据结构的自由选择，给了算法的优化空间，提高了程序的运行效率。 课堂练习 – AB练P91 A B 课堂练习 – AB练P109 THANKS FOR YOUR WATCHING 谢谢 $$