• 抽象數據類型

    編輯
    本詞條由“匿名用戶” 建檔。

    抽象數據類型(了解如何以及何時刪除此模板信息)

    編輯

    計算機科學中,抽象數據類型(ADT)是一種數據類型的數學模型。一個抽象數據類型是由它的行為(語義)定義的,從用戶的角度來看,數據,特別是在可能的值,對這種類型的數據的可能操作,以及這些操作的行為。這種數學模型與數據結構形成對比,后者是數據的具體表示,是實現者而不是用戶的觀點。從形式上看,ADT可以被定義為一類對象,其邏輯行為由一組值和一組操作定義;這類似于數學中的代數結構。行為的含義因作者而異,行為的兩種主要形式規范是公理(代數)規范和抽象模型;它們分別對應于抽象機器的公理語義和操作語義。一些作者還包括計算復雜性(成本),包括時間(用于計算操作)和空間(用于表示數值)。在實踐中,許多常見的數據類型都不是ADT,因為抽象并不完美,用戶必須注意到由于表示方法而導致的算術溢出等問題。例如,整數通常被存儲為固定寬度的值(32位或64位二進制數),因此,如果超過xxx值,會出現整數溢出。ADT是計算機科學中的一個理論概念,用于算法、數據結構和軟件系統設計和分析,并不對應于計算機語言的具體特征--主流計算機語言并不直接支持正式規定的ADT。然而,各種語言特征與ADT的某些方面相對應,并且容易與ADT本身相混淆;這些特征包括抽象類型、不透明數據類型、協議和契約設計。ADTs是由BarbaraLiskov和StephenN.Zilles在1974年首次提出的,作為CLU語言開發的一部分。

    抽象數據類型

    編輯

    例如,整數是一個ADT,定義為...、-2、-1、0、1、2、...等值,以及加、減、乘、除等運算,還有大于、小于等,其行為符合熟悉的數學原理(注意整數除法),與整數如何被計算機表示無關。明確地說,行為包括遵守各種公理(加法的關聯性和互換性等),以及操作的前提條件(不能除以0)。通常情況下,整數在數據結構中被表示為二進制數,最常見的是二的補碼,但也可能是二進制編碼的十進制或一的補碼,但對于大多數目的來說,用戶可以使用抽象而不是具體選擇的表示方法,并且可以簡單地使用數據,好像該類型是真正抽象的。一個ADT不僅包括操作,還包括一個值域,以及對定義操作的約束。一個接口通常只指操作,也許還有對操作的一些約束,如前條件和后條件;但不包括其他約束,如操作之間的關系。例如,一個抽象的堆棧,它是一個后進先出的結構,可以由三個操作來定義:push,在堆棧中插入一個數據項;pop,從堆棧中刪除一個數據項;peek或top,訪問堆棧頂部的一個數據項,而不刪除。一個抽象的隊列,是一個先進先出的結構,也會有三個操作:enqueue,向隊列中插入一個數據項;dequeue,從隊列中移除xxx個數據項;以及front,訪問并提供隊列中的xxx個數據項。

    抽象數據類型

    如果這些是全部的定義,那么就沒有辦法區分這兩種數據類型和它們非常不同的預期排序行為。因此,引入了一個約束條件,對于堆棧來說,每個pop總是返回(和刪除)最近推送的尚未被pop的項目,而對于隊列來說(相反),指定pop操作最近推送的最少的項目。在分析算法的效率時,我們也可以規定,無論有多少數據項被推入堆棧,所有的操作都需要相同的時間,并且堆棧對每個元素使用的存儲量是恒定的。然而,時間界限并不總是被認為是ADT定義的一部分。

    抽象數據類型的引言

    編輯

    抽象數據類型是純粹的理論實體,(除其他外)用于簡化抽象算法的描述,對數據結構進行分類和評估,并正式描述編程語言的類型系統。然而,一個ADT可以通過特定的數據類型或數據結構,以多種方式和多種編程語言來實現。

    內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/170663/

    (5)
    詞條目錄
    1. 抽象數據類型(了解如何以及何時刪除此模板信息)
    2. 抽象數據類型
    3. 抽象數據類型的引言

    輕觸這里

    關閉目錄

    目錄
    91麻精品国产91久久久久