抽象數(shù)據(jù)類型 課件 【考點(diǎn)打靶+定向訓(xùn)練】 浙教版（2019）高中信息技術(shù)選修1

4.3抽象數(shù)據(jù)類型在程序開發(fā)實(shí)踐中，僅有計(jì)算層面的抽象還不夠，還需要考慮數(shù)據(jù)層面的抽象。抽象數(shù)據(jù)類型能夠?qū)?shù)據(jù)定義表示與數(shù)據(jù)操作實(shí)現(xiàn)分離，以更好地支持程序的模塊化組織，它也是分解和實(shí)現(xiàn)大型復(fù)雜系統(tǒng)的最重要基礎(chǔ)技術(shù)。Sum()Average()Sin()tan()cos()數(shù)據(jù)類型與抽象數(shù)據(jù)類型數(shù)據(jù)類型是程序設(shè)計(jì)領(lǐng)域最重要的基本概念之一，它是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。使用計(jì)算機(jī)程序處理的數(shù)據(jù)，通常屬于不同的類型，如整數(shù)型、浮點(diǎn)數(shù)型或邏輯型等。每種程序設(shè)計(jì)語言都提供了一些內(nèi)置數(shù)據(jù)類型，并為每個(gè)內(nèi)置類型提供了一批操作。例如，有下列Python程序語句：a=13#語句1b=10#語句2c=a+b#語句3print(c)整型變量抽象是指抽取出事物具有的普遍性本質(zhì)，是對(duì)具體事物的一個(gè)概括。抽象是一種思考問題的方式，它隱藏了繁雜的細(xì)節(jié)，只保留實(shí)現(xiàn)目標(biāo)所必需的信息，實(shí)現(xiàn)抽象化后有利于對(duì)事物的抽象，便于實(shí)現(xiàn)功能、提高模塊獨(dú)立性。人們對(duì)已有數(shù)據(jù)類型進(jìn)行抽象，就有了抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型（AbstractDataType，簡(jiǎn)稱ADT）是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。ADT的基本思想是抽象，它的定義僅取決于它的一組邏輯特性，把數(shù)據(jù)結(jié)構(gòu)及其操作作為一個(gè)整體來研究，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。取字符串長(zhǎng)度（len）截取子串（substr）拼接字符串（concat）替換子串（subst）操作編程者字符串抽象數(shù)據(jù)類型的內(nèi)部表現(xiàn)抽象數(shù)據(jù)類型除了那些已經(jīng)定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還可以是編程者在程序設(shè)計(jì)時(shí)使用的函數(shù)或者單獨(dú)定義的數(shù)據(jù)類型等。如使用Python的內(nèi)建函數(shù)時(shí)，編程者只需考慮函數(shù)的功能是否滿足實(shí)際需要，再確保函數(shù)調(diào)用時(shí)的表達(dá)式是否符合函數(shù)構(gòu)造的要求，就可以使用此函數(shù)，而不需要知道該函數(shù)內(nèi)部實(shí)現(xiàn)的任何具體細(xì)節(jié)。max()insert()head()plot()根據(jù)抽象數(shù)據(jù)類型的定義，它還包括定義在該模型上的一組操作，即一個(gè)數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象中各數(shù)據(jù)元素之間的關(guān)系及對(duì)數(shù)據(jù)元素的操作。唱歌跳躍吃飯抽象數(shù)據(jù)類型的描述定義一個(gè)抽象數(shù)據(jù)類型，需要清晰地表述出各方面的形式要求（如操作的名字、參數(shù)的個(gè)數(shù)和類型等）和功能要求（希望這個(gè)操作完成什么樣的計(jì)算或產(chǎn)生什么效果等）。這類對(duì)象的功能體現(xiàn)為一組可以對(duì)它們使用的操作。當(dāng)然，還需要為這一抽象數(shù)據(jù)類型確定一個(gè)類型名。為了便于對(duì)抽象數(shù)據(jù)類型進(jìn)行規(guī)范的描述，下面給出了描述抽象數(shù)據(jù)類型的標(biāo)準(zhǔn)格式：ADT抽象數(shù)據(jù)類型名：Data

數(shù)據(jù)元素之間邏輯關(guān)系的定義Operation

操作1

初始條件

操作結(jié)果描述操作2……

操作n……endADT

在前三章有關(guān)線性表數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，已經(jīng)知道了線性表數(shù)據(jù)結(jié)構(gòu)會(huì)涉及的一些操作。比如：1.如何為創(chuàng)建操作提供初始元素序列；2.檢查線性表中是否存在某個(gè)特定數(shù)據(jù)對(duì)象；3.改變線性表中的內(nèi)容，包括加入新元素或刪除已有元素等；4.實(shí)現(xiàn)一個(gè)或兩個(gè)表的操作，包括表的組合操作等；5.實(shí)現(xiàn)對(duì)線性表中的每一個(gè)元素的操作，即對(duì)表元素的遍歷。下面呈現(xiàn)的是一個(gè)簡(jiǎn)單的線性表抽象數(shù)據(jù)類型，其中定義了一組最基本的操作。ADTList:List(self)#創(chuàng)建一個(gè)新表is_empty(self)#判斷sellf是否為一個(gè)空表len(self)#返回表的長(zhǎng)度prepend(self,elem)#在表頭插入元素elemappend(self,elem)#在表尾插入元素eleminsert(self,elem,i)#在表的第i個(gè)位置插入元素elemdel_first(self)#刪除第一個(gè)元素del_last(self)#刪除最后一個(gè)元素del(self,i)#刪除第i個(gè)元素search(self,elem)#查找元素elem在表中第一次出現(xiàn)的位置forall(self,op)#對(duì)表中的每個(gè)元素執(zhí)行op操作抽象數(shù)據(jù)類型的作用抽象數(shù)據(jù)類型主要體現(xiàn)了程序設(shè)計(jì)中問題分解、抽象和信息隱藏的特征。它把實(shí)際生活中的問題分解成多個(gè)規(guī)模較小且容易處理的問題，然后建立一個(gè)計(jì)算機(jī)能處理的數(shù)據(jù)模型，把每個(gè)功能模塊作為一個(gè)獨(dú)立單元，隱藏具體的實(shí)現(xiàn)過程，通過一次或多次的模塊調(diào)用來實(shí)現(xiàn)整個(gè)問題的解決。抽象數(shù)據(jù)類型能給算法和程序設(shè)計(jì)帶來很多好處，主要有：使用抽象數(shù)據(jù)類型編寫出來的程序結(jié)構(gòu)清晰、層次分明，便于程序正確性的證明和復(fù)雜性的分析；因?yàn)槠淠K化的特點(diǎn)，在程序設(shè)計(jì)中容易糾正，具有很好的可維護(hù)性；由于抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，便于移植和重用；因?yàn)樗惴ㄔO(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的隔開，降低了算法和程序設(shè)計(jì)的復(fù)雜度，有助于在開發(fā)過程中少出差錯(cuò)，保證編寫的程序有較高的可靠性，同時(shí)，允許數(shù)據(jù)結(jié)構(gòu)的自由選擇，給了算法的優(yōu)化空間，提高了程序運(yùn)行的效率。拓展鏈接常見數(shù)據(jù)結(jié)構(gòu)中的抽象數(shù)據(jù)類型定義一個(gè)簡(jiǎn)單的字符串ADT，其中定義了一些字符串操作：ADTString:String(self,sseq)#基于字符序列sseq建立一個(gè)字符串is_empty(self)#判斷本字符串是否空串len(self)#取得字符串的長(zhǎng)度char(self,index)#取得字符串中位置index的字符substr(self,a,b)#取得字符串中[a:b]的子串，左閉右開區(qū)間match(self,string)#查找串string在本字符串中第一次出現(xiàn)的

位置concat(self,string)#獲得本字符串與另一個(gè)字符串string的拼

接串subst(self,str1,str2)#獲得將本字符串里的子串str1替換為str2的結(jié)果串隊(duì)列的操作通常采用另一套習(xí)慣的操作名（enqueue/dequeuer/peek）。下面為一個(gè)簡(jiǎn)單的隊(duì)列抽象數(shù)據(jù)類型：ADTQueue:Queue(self)#創(chuàng)建空隊(duì)列is_empty(self)#判斷隊(duì)列是否為空，空時(shí)返回True，

否則返回Falseenqueue(self,elem)#將元素elem加入隊(duì)列，即入隊(duì)dequeue(self)#刪除隊(duì)列里最早進(jìn)的元素并將其返回，即出隊(duì)peek(self)#查看隊(duì)列里最早進(jìn)入的元素，不刪除定義二叉樹抽象數(shù)據(jù)類型時(shí)，主要考慮如下幾個(gè)方面：節(jié)點(diǎn)是二叉樹的基礎(chǔ)，通常主要用節(jié)點(diǎn)保存與應(yīng)用有關(guān)的信息；作為二叉樹的表示，還需要記錄二叉樹的結(jié)構(gòu)信息，至少需要保證能夠檢查節(jié)點(diǎn)的父子關(guān)系，例如，能從一個(gè)節(jié)點(diǎn)找到其左/右子節(jié)點(diǎn)。下面是一個(gè)基本的二叉樹抽象數(shù)據(jù)類型的定義：ADTBinTree:#一個(gè)二叉樹抽象數(shù)據(jù)類型BinTree(self,data,left,right)#構(gòu)造操作，創(chuàng)建一個(gè)新二叉樹is_empty(self)#判斷self是否為一個(gè)空二叉樹num_nodes(self)#求二叉樹的節(jié)點(diǎn)個(gè)數(shù)data(self)#獲取二叉樹根節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)left(self)#獲得二叉樹的左子樹right(self)#獲得二叉樹的右子樹self_left(self,btree)#用btree取代原來的左子樹self_right(self,btree)#用btree取代原來的右子樹traversal(self)#遍歷二叉樹中各節(jié)點(diǎn)數(shù)據(jù)的迭代器forall(self,op)#對(duì)二叉樹中的每個(gè)節(jié)點(diǎn)的數(shù)據(jù)執(zhí)行op操作練一練1.下列關(guān)于抽象數(shù)據(jù)類型的說法，不正確的是（）A.程序設(shè)計(jì)語言的一個(gè)內(nèi)置類型可以看作是一個(gè)抽象數(shù)據(jù)類型B.抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，與其在計(jì)算機(jī)內(nèi)部的表示與實(shí)現(xiàn)無關(guān)C.定義一個(gè)抽象數(shù)據(jù)類型，只需要清晰地表達(dá)出各方面的形式要求即可D.使用抽象數(shù)據(jù)類型編寫的程序結(jié)構(gòu)清晰、層次分明，也便于程序的移植和重用C2.創(chuàng)建一個(gè)簡(jiǎn)單的ADT，如下所示：classNd():def_init_(self,data):self.data=datadefjudge(self):ifself.data%5==0:print(self.data,“是5的倍數(shù)”)