資源簡介

(共35張PPT)
第四章
抽象數據類型
生活中的問題想要用計算機編程求解，不是用簡單的數據類型就能全部實現，還需要用抽象數據類型來描述問題的數據模型和基本操作。除了如線性表這種線性關系，還有很多數據之間的關系是層次或網狀的，即以非線性形式存在的。
4 . 1 . 1 　抽象數據類型
在用計算機解決實際問題的過程中，對于要解決的問題，不管用什么語言編寫程序，其解決的方法和思路是相同的。為了便于描述問題和抽象問題，在一般數據類型的基礎上提出了抽象數據類型，它可以有效地幫助我們思考、描述問題的數據模型和基本操作。
很多高級語言都有“整型”這種數據類型，其實整型也是一種抽象數據類型，因為不同的計算機對整型變量的存儲是不一樣的。而我們用到整型變量時，并不關心它是如何存儲的，只需要了解其取值范圍（值域）和能夠進行的操作運算（加、減、乘、除、取模等），就可以正確地使用整型變量了。這正體現了抽象數據類型的本質：忽略不同機器、不同語言的實現細節，在更普遍、更高的層次抽象出問題的數據模型，并定義數據模型的相關操作，從而實現對問題的解決。
抽象數據類型（Abstract Data Type，簡稱ADT）是由一種數據結構和在其上的一組操作（運算）所組成。抽象數據類型包含一般數據類型的概念，但含義比一般數據類型更廣、更抽象。一般數據類型通常由具體語言系統內部定義，直接提供給用戶使用；而抽象數據類型還包括用戶在編程處理數據、設計軟件系統時自己定義的數據類型，通常由用戶自行定義，包括定義其所包含的數據（數據結構）和在這些數據上所進行的操作。在定義抽象數據類型時，就是定義其數據的邏輯結構和操作說明，不考慮數據的存儲結構和操作的具體實現，這樣具有較好的通用性和可移植性，便于用任何一種語言實現。
ADT 抽象數據類型名
{
數據：<數據描述>
操作：<基本操作的定義>
}ADT 抽象數據類型名
ADT 復數{
數據：
實部;
虛部;
操作：
初始化復數;
獲取實部;
獲取虛部;
獲取模;
獲取輻角;
復數加法;
復數減法;
復數乘法;
復數除法;
}ADT 復數
為了便于理解和表達的簡潔，對抽象數據類型定義中的數據（數據結構）及基本操作，我們采用中文說明和類C++語言的形式進行描述（借用C++語言的一些語法元素，但是不嚴格遵循C++語言）。例如，我們可以定義“復數”這種抽象數據類型來表示數學上的復數：
4 . 1 . 2 　 抽象數據類型的應用
利用抽象數據類型定義復數，并通過編程實現，就可以使用計算機處理復數了。除了數學運算外，在解決現實問題和實際編寫計算機應用軟件時，因為要解決的問題更復雜， 所以更需要大量應用抽象數據類型來描述問題和設計解決方案。
如項目范例中的俄羅斯方塊游戲，方塊的顏色、形狀都有多種，每一個方塊都有左 旋、右旋、左移、右移、下落等多種操作，變化較多。游戲程序實現的關鍵是如何操控這 些方塊，可以定義一種抽象數據類型“方塊”，其中包含方塊的形狀、顏色、中心點等， 以及對它的左旋、右旋、左移、右移、下落等多種操作。類似的，我們還可以將俄羅斯方 塊游戲的區域也定義為一種抽象數據類型，從而完成游戲的設計。
（1）象棋游戲里（如圖4-3所示），每一個棋子上面的文字都不一樣，有的是“馬”、有的是“兵”等，對陣雙方的棋子顏色一般為黑色和紅色，每個棋子必須響應鼠標或鍵盤的控制動作，實現棋子的拿起、移動、放下等操作。這里可以將棋子定義為一種抽象數據類型，其數據模型包括棋子的顏色、棋子的文字、棋子在棋盤上的坐標等，基本操作包括拿起、移動、放下等。
4 . 1 . 3 　 抽象數據類型的實現
為幫助大家更好地理解，接下來以定義抽象數據類型“長方形”為例，呈現抽象數據 類型的定義過程和程序實現過程。
假定用rectangle來表示“長方形”的抽象數據類型名，其數據部分長、寬用a、b表 示，類型為實數；其基本操作包括初始化、求長方形的周長和求長方形的面積，求周長的 函數名用perimeter表示，求面積的函數名用area表示，則長方形的ADT描述如下：
4.2　用抽象數據類型表示隊列和棧
隊列和棧是兩種典型的抽象數據類型，因為在計算機解決實際問題和很多軟件的實現 中，都會用到隊列和棧。通過抽象數據類型來表示隊列和棧，能夠更加清楚地認識和理解 這兩種數據類型的特征和操作。
4 . 2 . 1 　 用抽象數據類型表示隊列
4 . 2 . 1 　 用抽象數據類型表示隊列
隊列是線性表的一種，隊列的元素之間具有線性關系。另外，隊列具有隊頭、隊尾，元素從隊尾入隊、從隊頭出隊，因此隊列具有先進先出（FIFO）的特點。針對隊列的操作有：初始化隊列、元素入隊、元素出隊、求隊列長度、隊列判滿、隊列判空。我們可以用下面的抽象數據類型表示隊列：
4 . 2 . 2 　 用抽象數據類型表示棧
棧和隊列一樣，屬于線性表的一種，其元素之間也具有線性關系。與隊列不同的是， 棧元素的入棧、出棧都是從同一頭進行的，所以棧具有后進先出（LIFO）的特點。從抽象 數據類型的角度來看，棧的數據部分包括線性關系的數據元素和棧頂、棧底。關于棧的操 作有：初始化棧、元素入棧、元素出棧、?？张袛?、棧滿判斷、求棧的長度。類似的，我 們可以用下面的抽象數據類型表示棧：
4.3　用抽象數據類型表示二叉樹
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）結點的度。
每個結點具有的子樹數稱作結點的度。例如圖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）樹的深度。
從樹根開始，根結點為第一層，它的孩子結點為第二層，如此類推。樹中所有結點的最大層數稱為樹的深度。圖4-7（a）樹T的深度為4。
4.3.2　二叉樹
如圖4-8所示的是自然界中的二叉樹，它每一個枝都只有個分枝，樹枝的盡頭才是葉子，是不是很有趣呢？
計算機數據結構中的二叉樹是一種特殊樹形結構，它的特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），而且二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹在計算機領域有著廣泛的應用。（優先級隊列，資源管理器，用戶界面）
完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。
4 . 3 . 3 　 二叉樹的抽象數據類型
二叉樹的抽象數據類型的數據部分為一棵用任一種方式表示的二叉樹，操作部分包括初始化二叉樹、建立二叉樹、遍歷二叉樹、查找二叉樹、輸出二叉樹和清除二叉樹等常用操作。
4 . 3 . 4 　 二叉樹的基本操作方法
二叉樹的基本操作較多，下面以遍歷為例，了解二叉樹的基本操作方法。遍歷是二叉樹的一種基本操作，是指按一定的次序訪問樹中所有結點，并且每個結點的值僅被訪問一次的過程。由于二叉樹是非線性結構，因此二叉樹的遍歷實質上是將二叉樹的所有結點轉換成一個線性序列的過程。
根據二叉樹的遞歸定義，一棵非空二叉樹由根結點、左子樹和右子樹所組成。因此，遍歷一棵非空二叉樹的問題可分解為三個子問題：訪問根結點、遍歷左子樹、遍歷右子樹。若用L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹，則對一棵二叉樹的遍歷有DLR、LDR、LRD、DRL、RDL、RLD六種情況，若限定先左后右，則只有前三種情況，分別稱為前序遍歷（或先根遍歷）、中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）
前序遍歷（或先根遍歷）
L
D
R
D L R
中序遍歷（或中根遍歷）
L
D
R
L D R
后序遍歷（或后根遍歷）
L
D
R
L R D
練
前序遍歷為：
中序遍歷為：
后序遍歷 為：
ABDECFG；
DBEACGF；
DEBGFCA。
當完全二叉樹結點總數為偶數時，葉子結點數=結點總數/2。
當完全二叉樹結點總數為奇數時，葉子結點數= (結點總數+1) /2。
二叉樹具有以下重要性質：
性質1
深度為k的二叉樹至多有2-1個結點(k≥1)。
性質2
在二叉樹的第i層至多有2-1個結點(i≥1)。
性質3
如果二又樹的終端結點數為m，度為2的結點數為口則m=n+1
數據類型是一個值的集合和定義在此集合上的一組操作的總稱。
抽象數據類型=邏輯結構＋抽象運算
抽象數據類型暫不考慮計算機的具體存儲結構和運算的具體實現。
抽象數據類型實質上，就是在描述問題本身（與計算機無關）。目標：在不涉及具體的，和計算機系統相關的細節情況下，優先理解問題本身，在此基礎上，實現用計算機求解問題的過程。
ADT <抽象數據類型名>{
數據對象：<數據對象的定義>
數據關系：<數據關系的定義>
基本操作：<基本操作的定義>
} ADT <抽象數據類型名>{
我們可以認為抽象數據類型是包含著數據類型的，也就是說，抽象數據類型是一個更大的概念，
例如：在定義一個學生類型的抽象數據類型時，學生對象既包含整型的年齡，身高，又包含char類型的姓名，這時，我們就可以用一個結構體定義這個學生類型
struct Student {
char sno; //學號
int age; //年齡… …
}
這里，Student是一個抽象數據類型，而里面的int,char類型又是不同的數據類型

展開更多......

收起↑