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

第四章

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

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

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

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

旋、右旋、左移、右移、下落等多種操作，變化較多。游戲程序實現(xiàn)的關鍵是如何操控這

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

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

中，都會用到隊列和棧。通過抽象數(shù)據(jù)類型來表示隊列和棧，能夠更加清楚地認識和理解

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

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

樹是n（n≥0）個結點的有限集。在任意一棵非空樹中：①有且僅有一個特定的稱為根的結點；②當n>1時，其余結點分為m（m>0）棵互不相交的有限子樹，每棵子樹又是一棵樹。

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