高中信息技术浙教版 (2019)选修1 数据与数据结构4.3 抽象数据类型精品课件ppt

这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构4.3 抽象数据类型精品课件ppt，共17页。PPT课件主要包含了各科成绩，数据类型，max，min，abs，试一试，字符串ADT，队列ADT，练一练，课堂小结等内容，欢迎下载使用。

抽象是指抽取出事物具有的普遍性本质，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。
数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
每种程序设计语言都提供了一些内置数据类型，并为每个内置类型提供了一批操作。
a=13#语句1b=10#语句2c=a+b#语句3
抽象数据类型（Abstract Data Type），简称ADT，可理解为对数据类型的进一步抽象，是指一个数学模型及定义在该模型上的一组操作。它的基本思想是抽象。它的定义仅取决于它的一组逻辑特性，把数据结构及其操作作为一个整体来研究，而与其在计算机内部如何表示和实现无关。
抽象数据类型除了那些已经定义并实现的数据类型，还可以是编程者在程序设计时使用的函数或者单独定义的数据类型等。
根据抽象数据类型的定义，它还包括定义在该模型上的一组操作，即一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。
定义一个抽象数据类型，需要清晰地表述出各方面的形式要求（操作的名字、参数的个数和类型等）和功能要求（希望这个操作完成什么样的计算或产生什么效果等）。当然，还需要为这一抽象数据类型确定一个类型名。
描述抽象数据类型的标准格式：
如何定义一个矩形抽象数据类型？
ADT jx: chang; #长度数据 kuan; #宽度数据 zc(self) #求矩形的周长 mj(self) #求矩形的面积
class jx: def __init__(self,c=Nne,k=Nne): self.chang=c self.kuan=k def zc(self): return (self.chang+self.kuan)*2 def mj(self): return (self.chang*self.kuan)a=jx(10,8)print("周长：",a.zc())print("面积：",a.mj())
定义矩形抽象数据类型的程序实现及应用：
ADT List: List(self)#创建一个新表 is_empty(self) #判断sellf是否为一个空表 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在表中第一次出现的位置 frall(self,p)#对表中的每个元素执行p操作
ADT String: String(self,sseq) is_empty(self) len(self) char(self,index) substr(self,a,b) match(self,string) cncat(self,string) subst(self,str1,str2)
ADT Queue: Queue(self) is_empty(self) enqueue(self,elem) dequeue(self) peek(self)
class BTree: def __init__(self, data=Nne, left=Nne, right=Nne): self.data = data#数据域 self.left = left#左子树 self.right = right#右子树 def prerder(self):#前序遍历 # 代码略 def inrder(self): #中序遍历 # 代码略 def pstrder(self):#后序遍历 # 代码略
right_tree = BTree(6)right_tree.left = BTree(2)right_tree.right = BTree(4)left_tree = BTree(5)left_tree.left = BTree(1)left_tree.right = BTree(3)tree = BTree(8)tree.left = left_treetree.right = right_treetree.prerder()tree.inrder()tree.pstrder()
1、使用抽象数据类型编写出的程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析2、代码模块化，在程序设计中容易纠正，具有很好的可维护性3、抽象数据类型表示和实现都可以封装起来，便于代码的移植和重用
4、隔开算法设计与数据结构设计，降低算法和程序设计复杂度，有助于在开发过程中少出差错，编写程序有较高的可靠性5、允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率
1、数据类型与抽象数据类型2、抽象数据类型的描述3、抽象数据类型的作用