資源簡介

(共17張PPT)
抽象數據類型
年 級：高二
學 科：高中信息技術（浙教版）
抽象是指抽取出事物具有的普遍性本質，是對具體事物的一個概括。
抽象是一種思考問題的方式，它隱藏了繁雜的細節，只保留實現目標所必需的信息。
姓名
班級
學號
各科成績
抽象
數據類型是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
每種程序設計語言都提供了一些內置數據類型，并為每個內置類型提供了一批操作。
a=13 #語句1
b=10 #語句2
c=a+b #語句3
數據類型
1 抽象數據類型
抽象數據類型（Abstract Data Type），簡稱ADT，可理解為對數據類型的進一步抽象，是指一個數學模型及定義在該模型上的一組操作。
它的基本思想是抽象。它的定義僅取決于它的一組邏輯特性，把數據結構及其操作作為一個整體來研究，而與其在計算機內部如何表示和實現無關。
1 抽象數據類型
1 抽象數據類型
抽象數據類型除了那些已經定義并實現的數據類型，還可以是編程者在程序設計時使用的函數或者單獨定義的數據類型等。
max()
min()
abs()
1 抽象數據類型
根據抽象數據類型的定義，它還包括定義在該模型上的一組操作，即一個數據對象、數據對象中各數據元素之間的關系及對數據元素的操作。
跑動
跳躍
下蹲
定義一個抽象數據類型，需要清晰地表述出各方面的形式要求（操作的名字、參數的個數和類型等）和功能要求（希望這個操作完成什么樣的計算或產生什么效果等）。
當然，還需要為這一抽象數據類型確定一個類型名。
2 抽象數據類型的描述
描述抽象數據類型的標準格式：
如何定義一個矩形抽象數據類型？
ADT jx:
chang; #長度數據
kuan; #寬度數據
zc(self) #求矩形的周長
mj(self) #求矩形的面積
試一試
class jx:
def __init__(self,c=None,k=None):
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在表中第一次出現的位置
forall(self,op) #對表中的每個元素執行op操作
ADT String:
String(self,sseq)
is_empty(self)
len(self)
char(self,index)
substr(self,a,b)
match(self,string)
concat(self,string)
subst(self,str1,str2)
字符串ADT
ADT Queue:
Queue(self)
is_empty(self)
enqueue(self,elem)
dequeue(self)
peek(self)
隊列ADT
試一試
練一練
class BTree:
def __init__(self, data=None, left=None, right=None):
self.data = data #數據域
self.left = left #左子樹
self.right = right #右子樹
def preorder(self): #前序遍歷
# 代碼略
def inorder(self): #中序遍歷
# 代碼略
def postorder(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_tree
tree.right = right_tree
tree.preorder()
tree.inorder()
tree.postorder()
8
5
6
1
3
4
2
5
1
3
6
4
2
1、使用抽象數據類型編寫出的程序結構清晰、層次分明，便于程序正確性的證明和復雜性的分析
2、代碼模塊化，在程序設計中容易糾正，具有很好的可維護性
3、抽象數據類型表示和實現都可以封裝起來，便于代碼的移植和重用
3 抽象數據類型的作用
4、隔開算法設計與數據結構設計，降低算法和程序設計復雜度，有助于在開發過程中少出差錯，編寫程序有較高的可靠性
5、允許數據結構的自由選擇，給了算法的優化空間，提高了程序運行的效率
3 抽象數據類型的作用
課堂小結
1、數據類型與抽象數據類型
2、抽象數據類型的描述
3、抽象數據類型的作用
感謝聆聽！同學們再見！

展開更多......

收起↑