第四章 抽象數(shù)據(jù)類(lèi)型 課件 2023-2024學(xué)年粵教版（2019）高中信息技術(shù)選修1

第四章

抽象數(shù)據(jù)類(lèi)型單擊此處添加副標(biāo)題內(nèi)容生活中的問(wèn)題想要用計(jì)算機(jī)編程求解，不是用簡(jiǎn)單的數(shù)據(jù)類(lèi)型就能全部實(shí)現(xiàn)，還需要用抽象數(shù)據(jù)類(lèi)型來(lái)描述問(wèn)題的數(shù)據(jù)模型和基本操作。除了如線(xiàn)性表這種線(xiàn)性關(guān)系，還有很多數(shù)據(jù)之間的關(guān)系是層次或網(wǎng)狀的，即以非線(xiàn)性形式存在的。4.1.1抽象數(shù)據(jù)類(lèi)型在用計(jì)算機(jī)解決實(shí)際問(wèn)題的過(guò)程中，對(duì)于要解決的問(wèn)題，不管用什么語(yǔ)言編寫(xiě)程序，其解決的方法和思路是相同的。為了便于描述問(wèn)題和抽象問(wèn)題，在一般數(shù)據(jù)類(lèi)型的基礎(chǔ)上提出了抽象數(shù)據(jù)類(lèi)型，它可以有效地幫助我們思考、描述問(wèn)題的數(shù)據(jù)模型和基本操作。很多高級(jí)語(yǔ)言都有“整型”這種數(shù)據(jù)類(lèi)型，其實(shí)整型也是一種抽象數(shù)據(jù)類(lèi)型，因?yàn)椴煌挠?jì)算機(jī)對(duì)整型變量的存儲(chǔ)是不一樣的。而我們用到整型變量時(shí)，并不關(guān)心它是如何存儲(chǔ)的，只需要了解其取值范圍（值域）和能夠進(jìn)行的操作運(yùn)算（加、減、乘、除、取模等），就可以正確地使用整型變量了。這正體現(xiàn)了抽象數(shù)據(jù)類(lèi)型的本質(zhì)：忽略不同機(jī)器、不同語(yǔ)言的實(shí)現(xiàn)細(xì)節(jié)，在更普遍、更高的層次抽象出問(wèn)題的數(shù)據(jù)模型，并定義數(shù)據(jù)模型的相關(guān)操作，從而實(shí)現(xiàn)對(duì)問(wèn)題的解決。抽象數(shù)據(jù)類(lèi)型（AbstractDataType，簡(jiǎn)稱(chēng)ADT）是由一種數(shù)據(jù)結(jié)構(gòu)和在其上的一組操作（運(yùn)算）所組成。抽象數(shù)據(jù)類(lèi)型包含一般數(shù)據(jù)類(lèi)型的概念，但含義比一般數(shù)據(jù)類(lèi)型更廣、更抽象。一般數(shù)據(jù)類(lèi)型通常由具體語(yǔ)言系統(tǒng)內(nèi)部定義，直接提供給用戶(hù)使用；而抽象數(shù)據(jù)類(lèi)型還包括用戶(hù)在編程處理數(shù)據(jù)、設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類(lèi)型，通常由用戶(hù)自行定義，包括定義其所包含的數(shù)據(jù)（數(shù)據(jù)結(jié)構(gòu)）和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類(lèi)型時(shí)，就是定義其數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說(shuō)明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣具有較好的通用性和可移植性，便于用任何一種語(yǔ)言實(shí)現(xiàn)。ADT抽象數(shù)據(jù)類(lèi)型名{

數(shù)據(jù)：<數(shù)據(jù)描述>

操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類(lèi)型名ADT復(fù)數(shù){數(shù)據(jù)：實(shí)部;虛部;操作：初始化復(fù)數(shù);獲取實(shí)部;獲取虛部;獲取模;獲取輻角;復(fù)數(shù)加法;復(fù)數(shù)減法;復(fù)數(shù)乘法;復(fù)數(shù)除法;}ADT復(fù)數(shù)為了便于理解和表達(dá)的簡(jiǎn)潔，對(duì)抽象數(shù)據(jù)類(lèi)型定義中的數(shù)據(jù)（數(shù)據(jù)結(jié)構(gòu)）及基本操作，我們采用中文說(shuō)明和類(lèi)C++語(yǔ)言的形式進(jìn)行描述（借用C++語(yǔ)言的一些語(yǔ)法元素，但是不嚴(yán)格遵循C++語(yǔ)言）。例如，我們可以定義“復(fù)數(shù)”這種抽象數(shù)據(jù)類(lèi)型來(lái)表示數(shù)學(xué)上的復(fù)數(shù)：4.1.2抽象數(shù)據(jù)類(lèi)型的應(yīng)用利用抽象數(shù)據(jù)類(lèi)型定義復(fù)數(shù)，并通過(guò)編程實(shí)現(xiàn)，就可以使用計(jì)算機(jī)處理復(fù)數(shù)了。除了數(shù)學(xué)運(yùn)算外，在解決現(xiàn)實(shí)問(wèn)題和實(shí)際編寫(xiě)計(jì)算機(jī)應(yīng)用軟件時(shí)，因?yàn)橐鉀Q的問(wèn)題更復(fù)雜，

所以更需要大量應(yīng)用抽象數(shù)據(jù)類(lèi)型來(lái)描述問(wèn)題和設(shè)計(jì)解決方案。如項(xiàng)目范例中的俄羅斯方塊游戲，方塊的顏色、形狀都有多種，每一個(gè)方塊都有左

旋、右旋、左移、右移、下落等多種操作，變化較多。游戲程序?qū)崿F(xiàn)的關(guān)鍵是如何操控這

些方塊，可以定義一種抽象數(shù)據(jù)類(lèi)型“方塊”，其中包含方塊的形狀、顏色、中心點(diǎn)等，以及對(duì)它的左旋、右旋、左移、右移、下落等多種操作。類(lèi)似的，我們還可以將俄羅斯方塊游戲的區(qū)域也定義為一種抽象數(shù)據(jù)類(lèi)型，從而完成游戲的設(shè)計(jì)。（1）象棋游戲里（如圖4-3所示），每一個(gè)棋子上面的文字都不一樣，有的是“馬”、有的是“兵”等，對(duì)陣雙方的棋子顏色一般為黑色和紅色，每個(gè)棋子必須響應(yīng)鼠標(biāo)或鍵盤(pán)的控制動(dòng)作，實(shí)現(xiàn)棋子的拿起、移動(dòng)、放下等操作。這里可以將棋子定義為一種抽象數(shù)據(jù)類(lèi)型，其數(shù)據(jù)模型包括棋子的顏色、棋子的文字、棋子在棋盤(pán)上的坐標(biāo)等，基本操作包括拿起、移動(dòng)、放下等。4.1.3抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)為幫助大家更好地理解，接下來(lái)以定義抽象數(shù)據(jù)類(lèi)型“長(zhǎng)方形”為例，呈現(xiàn)抽象數(shù)據(jù)類(lèi)型的定義過(guò)程和程序?qū)崿F(xiàn)過(guò)程。

假定用rectangle來(lái)表示“長(zhǎng)方形”的抽象數(shù)據(jù)類(lèi)型名，其數(shù)據(jù)部分長(zhǎng)、寬用a、b表示，類(lèi)型為實(shí)數(shù)；其基本操作包括初始化、求長(zhǎng)方形的周長(zhǎng)和求長(zhǎng)方形的面積，求周長(zhǎng)的函數(shù)名用perimeter表示，求面積的函數(shù)名用area表示，則長(zhǎng)方形的ADT描述如下：4.2用抽象數(shù)據(jù)類(lèi)型表示隊(duì)列和棧隊(duì)列和棧是兩種典型的抽象數(shù)據(jù)類(lèi)型，因?yàn)樵谟?jì)算機(jī)解決實(shí)際問(wèn)題和很多軟件的實(shí)現(xiàn)

中，都會(huì)用到隊(duì)列和棧。通過(guò)抽象數(shù)據(jù)類(lèi)型來(lái)表示隊(duì)列和棧，能夠更加清楚地認(rèn)識(shí)和理解

這兩種數(shù)據(jù)類(lèi)型的特征和操作。4.2.1用抽象數(shù)據(jù)類(lèi)型表示隊(duì)列4.2.1用抽象數(shù)據(jù)類(lèi)型表示隊(duì)列隊(duì)列是線(xiàn)性表的一種，隊(duì)列的元素之間具有線(xiàn)性關(guān)系。另外，隊(duì)列具有隊(duì)頭、隊(duì)尾，元素從隊(duì)尾入隊(duì)、從隊(duì)頭出隊(duì)，因此隊(duì)列具有先進(jìn)先出（FIFO）的特點(diǎn)。針對(duì)隊(duì)列的操作有：初始化隊(duì)列、元素入隊(duì)、元素出隊(duì)、求隊(duì)列長(zhǎng)度、隊(duì)列判滿(mǎn)、隊(duì)列判空。我們可以用下面的抽象數(shù)據(jù)類(lèi)型表示隊(duì)列：4.2.2用抽象數(shù)據(jù)類(lèi)型表示棧棧和隊(duì)列一樣，屬于線(xiàn)性表的一種，其元素之間也具有線(xiàn)性關(guān)系。與隊(duì)列不同的是，

棧元素的入棧、出棧都是從同一頭進(jìn)行的，所以棧具有后進(jìn)先出（LIFO）的特點(diǎn)。從抽象數(shù)據(jù)類(lèi)型的角度來(lái)看，棧的數(shù)據(jù)部分包括線(xiàn)性關(guān)系的數(shù)據(jù)元素和棧頂、棧底。關(guān)于棧的操作有：初始化棧、元素入棧、元素出棧、?？张袛?、棧滿(mǎn)判斷、求棧的長(zhǎng)度。類(lèi)似的，我們可以用下面的抽象數(shù)據(jù)類(lèi)型表示棧：4.3用抽象數(shù)據(jù)類(lèi)型表示二叉樹(shù)4.3.1樹(shù)1．樹(shù)

樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中：①有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；②當(dāng)n>1時(shí)，其余結(jié)點(diǎn)分為m（m>0）棵互不相交的有限子樹(shù)，每棵子樹(shù)又是一棵樹(shù)。

如圖4-7所示，樹(shù)T由根結(jié)點(diǎn)A及兩棵子樹(shù)T1、T2組成。同樣，T1中，B是根結(jié)點(diǎn)，其下又可以細(xì)分出三棵子樹(shù)（D、EHI及F）；T2中，C是根結(jié)點(diǎn)，其下又可以細(xì)分出1棵子樹(shù)（GJ）。2．樹(shù)的基本概念（1）結(jié)點(diǎn)的度。每個(gè)結(jié)點(diǎn)具有的子樹(shù)數(shù)稱(chēng)作結(jié)點(diǎn)的度。例如圖4-7（a）樹(shù)T中，B結(jié)點(diǎn)的度為3，I結(jié)點(diǎn)的度為0。2．樹(shù)的基本概念（2）分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)。在一棵樹(shù)中，度等于0的結(jié)點(diǎn)稱(chēng)作葉子結(jié)點(diǎn)。度大于0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹(shù)T中，D、H、I、F、J為葉子結(jié)點(diǎn)，A、B、C、E、G為分支結(jié)點(diǎn)。2．樹(shù)的基本概念3）孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)。在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的子樹(shù)的根，稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，相應(yīng)地，該結(jié)點(diǎn)被稱(chēng)為孩子結(jié)點(diǎn)的雙親、父親或父母。具有同一雙親的孩子互稱(chēng)兄弟。在圖4-7（a）樹(shù)T中，結(jié)點(diǎn)B是結(jié)點(diǎn)A的孩子結(jié)點(diǎn)，結(jié)點(diǎn)A是結(jié)點(diǎn)B的雙親結(jié)點(diǎn)，結(jié)點(diǎn)B和C互為兄弟。2．樹(shù)的基本概念（4）樹(shù)的深度。從樹(shù)根開(kāi)始，根結(jié)點(diǎn)為第一層，它的孩子結(jié)點(diǎn)為第二層，如此類(lèi)推。樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的深度。圖4-7（a）樹(shù)T的深度為4。4.3.2二叉樹(shù)如圖4-8所示的是自然界中的二叉樹(shù)，它每一個(gè)枝都只有個(gè)分枝，樹(shù)枝的盡頭才是葉子，是不是很有趣呢？計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)中的二叉樹(shù)是一種特殊樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)），而且二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。二叉樹(shù)在計(jì)算機(jī)領(lǐng)域有著廣泛的應(yīng)用。（優(yōu)先級(jí)隊(duì)列，資源管理器，用戶(hù)界面）完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。4.3.3二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型的數(shù)據(jù)部分為一棵用任一種方式表示的二叉樹(shù)，操作部分包括初始化二叉樹(shù)、建立二叉樹(shù)、遍歷二叉樹(shù)、查找二叉樹(shù)、輸出二叉樹(shù)和清除二叉樹(shù)等常用操作。4.3.4二叉樹(shù)的基本操作方法二叉樹(shù)的基本操作較多，下面以遍歷為例，了解二叉樹(shù)的基本操作方法。遍歷是二叉樹(shù)的一種基本操作，是指按一定的次序訪(fǎng)問(wèn)樹(shù)中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪(fǎng)問(wèn)一次的過(guò)程。由于二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)，因此二叉樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的所有結(jié)點(diǎn)轉(zhuǎn)換成一個(gè)線(xiàn)性序列的過(guò)程。根據(jù)二叉樹(shù)的遞歸定義，一棵非空二叉樹(shù)由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)所組成。因此，遍歷一棵非空二叉樹(shù)的問(wèn)題可分解為三個(gè)子問(wèn)題：訪(fǎng)問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)。若用L、D、R分別表示遍歷左子樹(shù)、訪(fǎng)問(wèn)根結(jié)點(diǎn)和遍歷右子樹(shù)，則對(duì)一棵二叉樹(shù)的遍歷有DLR、LDR、LRD、DRL、RDL、RLD六種情況，若限定先左后右，則只有前三種情況，分別稱(chēng)為前序遍歷（或先根遍歷）、中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）前序遍歷（或先根遍歷）LDRDLR中序遍歷（或中根遍歷）LDRLDR后序遍歷（或后根遍歷）LDRLRD練前序遍歷為：中序遍歷為：后序遍歷為：ABDECFG；DBEACGF；DEBGFCA。當(dāng)完全二叉樹(shù)結(jié)點(diǎn)總數(shù)為偶數(shù)時(shí)，葉子結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)總數(shù)/2。當(dāng)完全二叉樹(shù)結(jié)點(diǎn)總數(shù)為奇數(shù)時(shí)，葉子結(jié)點(diǎn)數(shù)=(結(jié)點(diǎn)總數(shù)+1)/2。二叉樹(shù)具有以下重要性質(zhì)：性質(zhì)1深度為k的二叉樹(shù)至多有2-1個(gè)結(jié)點(diǎn)(k≥1)。性質(zhì)2在二叉樹(shù)的第i層至多有2-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)3如果二又樹(shù)的終端結(jié)點(diǎn)數(shù)為m，度為2的結(jié)點(diǎn)數(shù)為口則m=n+1數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在此集合上的一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型=邏輯結(jié)構(gòu)＋抽象運(yùn)算抽象數(shù)據(jù)類(lèi)型暫不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)。抽象數(shù)據(jù)類(lèi)型實(shí)質(zhì)上，就是在描述問(wèn)題本身（與計(jì)算機(jī)無(wú)關(guān)）。目標(biāo)：在不涉及具體的，和計(jì)算機(jī)系統(tǒng)相關(guān)的細(xì)節(jié)情況下，優(yōu)先理解問(wèn)題本身，在此基礎(chǔ)上，實(shí)現(xiàn)用計(jì)算機(jī)求解問(wèn)題的過(guò)程。ADT<抽象數(shù)據(jù)類(lèi)型名>{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT<抽象數(shù)據(jù)類(lèi)