抽象數據結構

抽象數據結構(Abstract Data Type,ADT)是計算機科學中具有類似行為的特定類別的數據結構的數學模型;或者具有類似語義的一種或多種程式設計語言數據類型

抽象數據類型是間接定義的,通過其上的可執行的操作以及這些操作的效果的數學約束(與可能的代價)。

基本介紹

  • 中文名:抽象數據結構
  • 外文名:abstract data type
  • 套用領域:資料庫、C語言等
  • 涉及學科:計算機等
  • 縮寫:ADT
  • 屬於:數據類型
抽象數據結構,抽象數據結構,串(string),數組,排隊和棧(Queue和stack),表,樹,方向圖,堆疊,C#堆疊對象,抽象數據結構的實施,意義,運用數組來實施堆疊,佇列抽象數據結構,映射表抽象數據結構,

抽象數據結構

到目前為止,我們所看到的數據結構都屬於具體的數據結構。所謂具體的數據結構,是指它們的具體結構和對它們的操作方法完全都由我們自己來定義。例如,利用兩個整型的數或者枚舉類型的數來表示撲克牌的Card類,用兩個浮點數來定義的複數類。
抽象數據結構,或者叫做ADT(abstract data type),雖是定義了一系列的操作(或者直接叫方法)和這些操作的作用(它們做什麼),但我們卻並不指定這些操作過程如何具體予以實施的辦法(即不編寫具體的代碼)。這樣出現的數據結構就是抽象數據結構。
例如,抽象的堆疊(stack)由3個操作定義:推入push,彈出pop(接受約束:每次彈出返回的是最新被推入且沒有被彈出的數據,也就是後進先出),查看堆疊頂端數據peek。當分析使用堆疊算法的效率,所有這3個操作用時相同,無論堆疊中包含多少項數據;並且對每項數據棧使用了常量大小的存儲。 抽象數據類型(ADT)是純粹理論實體,用於簡化描述抽象算法,分類與評價數據結構,形式描述程式設計語言的類型系統。一個ADT可以用特定數據類型數據結構實現,在許多程式設計語言中有許多種實現方式;或者用形式規範語言描述。ADT常實現為模組(module):模組的接口聲明了對應於ADT操作的例程(procedure),有時用注釋描述了約束。
這樣虛虛的東西有什麼用?它有下列作用:
  • 可以簡化編寫算法程式的任務。這時,我們可以早早指定某一項操作,但又不必當時就編寫這些操作如何具體實施的代碼。
  • 對應一種抽象數據,可能找到各種各樣實施途徑。於是,當編寫了一個算法後,就可以在相當多的其他類似場合套用和共享。
  • 像本章中即將討論聲名顯赫的堆疊這類抽象數據結構那樣,人們早已編寫了它的實施代碼,並常常被放在標準庫中,以利大家改寫或者直接套用於各種程式場合。
對於抽象數據結構的操作,又為高級語言提供了編寫或者討論算法的最好背景。
當討論抽象數據結構時,我們通常要區分哪些是運用抽象數據結構的代碼(稱為套用代碼),哪些是抽象數據結構的實施代碼(稱為服務代碼)。後者常常提供一系列的標準服務。

抽象數據結構

我們把數據結構定義為一組規則和約束條件,它們表示數據塊之間存在的關係.這種結構並末涉及可能出現的各個數據塊是什麼.在某種意義上講,只要求它們保持這種結構,然而,包含在數據項內的任何信息是不依賴於該結構的.這裡使用了項這個術語去表示一個抽象數據結構的塊.項本身也可以是其他的數據結構,這樣就建立了數據結構的層次集合.

串(string)

串是項的有序集.它可以是變長的,也可以是定長的.每項只有其相鄰項的信息,因此,取一特定項時,必須從串的一端開始,順序進行查找.在串上定義的運算有
(a)兩串的並置;
(b)對兩串作項對項的比較;
(c)把串分成幾部分.

數組

數組A是這樣排列的項的集合:使得一個有序整數集唯一定義數組每項的位置,並提供直接取每項的方法.用ALGOL表示法,如果有序整數集的長度為n,那么,該數組稱為n維的.有序集中各個整數稱為下標.每個下標可以用任意方式定義其界限,而該界限可由若干互不相交的子界限組成。
在編譯程式和程式設計語言中所使用的是數組集的某一特殊子集,即所謂矩形數組集.矩形數組的每個下標界限是不變的和連讀的。

排隊和棧(Queue和stack)

排隊和棧是動態改變的數據結構.任何時候它們都包含一組有序的項.對排隊的情形來說,如果添加一項,就把它放在組的末端,而且只能從定義該排隊組的前面取出或移摔項.列在排隊中的第一項是唯一可取出的項,而且必須先移掉它.對棧的情形來說,添加的項同樣是放在組的末端,不同的是要從組的末端取出和移掉項.此時最後添加的項是唯一可取出的項,並最先被移掉.項可以是可變長度的,並在項中指明其長度.

表由一組項組成,和每項相聯繫的是唯一的名字或關鍵字.通常,每項是由它的關鍵字連同與該關鍵字有關的一些信息所組成.給出項的關鍵字及其有關信息就能把項添到表中.反之,通過關鍵字能從表中取出相應的項來.

樹是由一組結點組成的結構.每個結點(或者項)有這樣的特點:除它所帶的信息外,它還包含低層結點的指示字,在樹的最低層,結點指的是葉子,葉子是由樹外的數據結構組成的.層的思想是基於下述事實得來的:每株樹毖有一最頂的結點,它再無別的結點指示它(通常稱為樹的根),樹中也沒有結點能指示前面已定義的結點.後一條件保證了從根到每一個結點只有唯一的通路.第一層結點是樹根所指的那些結點,第二層的結點是第一層結點所指示的那些結點,等等.

方向圖

除低層結點可指示高層結點外,方向圖是一種類似於樹的結構.所以,一個結點可有幾個結點指示它.因為現在已看不清圖中兩個結點之間的聯線方向,所以,通常在圖中至少要標出向上的指示線.放寬對樹的一些規則的限制,就表明有可能存在一條從某結點出發再回到該結點的通路,即通常所謂的環路.方向圖有一個特殊的子類是無環方向圖.這和樹的定義並不一致,因為,它仍然允許兩個結點指示同一個結點,而這一點在樹的定義中是不允許的.例如,ALGOL語言的複合語句。

堆疊

在此,我們先探討一種通用常見且又名聲顯赫的抽象數據結構——堆疊。堆疊也是一個集合體,包含有許許多多元素。而到目前為止,我們已經學到過的集合體是數組和鍊表。
如同上面已經提及的:一個抽象數據結構,就是對它進行一系列的操作定義。對於著名的堆疊,它的操作定義不多,僅僅包括下列這些東西:
  • Constructor(構造器):創建一個新的空堆疊。
  • Push:在堆疊中增加一個元素。
  • Pop:從堆疊中刪除一個元素,同時返回這個元素,並且,這個元素總是我們最後增加的那個元素。
  • Count:獲取包含在堆疊中的元素數。
堆疊有時也被叫做“後進先出”數據結構,英文是“last in,first out(LIFO)”。之所以這樣取名,是由於最後一個被加進的元素總是首先被刪除。

C#堆疊對象

C#內部已經提供了內置的Stack類,由它來實施堆疊這種抽象數據結構。大家應該花點精力去精確理解和清晰區分這樣的兩類事——抽象數據結構(ADT)和它的C#言實施。現在,我們就來看看c群已經為我們提供的內置堆疊。不過,在使
用Stack類之前,大家先得引人它。
請大家在例檔案的首部鍵人如下內容,以讓編譯器引入位於System.Collections這個命名空間中的Stack類:
LISing System.Collections;
然後在Main方法中創建一個新的堆疊,語法是這樣的:
Stack stack=new Stack();
剛創建的堆疊是空的。是不是這樣?可以用Count屬性進行測試。測試的結果應是零值:
Console.WriteLine(stack.Count)j
堆疊應該是一種通用數據結構。其通用的含義是:大家可以把任何類型的元素添加到堆疊中。但是,在讎語言中,對堆疊的套用卻有些許限制:可以被添加到堆疊中的東西,都必須是引用類型的對象,而不能是值類型對象(其原因待會兒再闡述),比如本書中用得最多、大家最熟悉的整數(int)類型就不行。
在此就給出第一個例子。在此例子中,我們要使用的元素就是上一章的Node(節點)對象。現在就讓我們開始創建並且列印短短的一個鍊表:
list.AddFirst(
list.AddFirst (
list.AddFirst(
liSt.PrintList

抽象數據結構的實施

意義

人們套用抽象數據結構的最主要目的,是為了區分代碼的提供者和代碼的套用者。那些編寫抽象數據結構如何實現或實施代碼的人,就是代碼的提供者;而那些只管把抽象數據結構拿來使用的人,就是代碼的套用者。對於代碼提供者來說,他們主要關心抽象數據結構實施的正確和效率,而不著重於它們的真正套用。
反之,代碼套用者都假定抽象數據結構的實施完全正確和十分有效,他們一般都不關心代碼的細節。我們已經在多處套用過c#的內置類了,我們早已都是它們的套用者了。
當然,如果我們作為代碼提供者的身份,對於已編寫好抽象數據結構的實施代碼,也必須以代碼使用者的身份編寫一些套用代碼,對抽象數據結構進行各種各樣的測試。在編寫和測試階段,大家得仔細想想自己到底是代碼編寫者,還是代碼使用者。
在下面數節內容中,大家都得作為代碼編寫者運用先前已掌握的數組知識編寫一些代碼,來實施抽象數據結構——堆疊。

運用數組來實施堆疊

運用數組實施抽象結構數據——堆疊時,堆疊類的實例變數是什麼?有兩個:一個是由Object類型作為元素所組成的數組,該數組容納被放人堆疊的各個成員;另一個是引用數組中下一個空位的數組索引值,即一個整數。當這個堆疊被初始化時,數組是空的,而對該數組的索引就是0。
為了向堆疊增加(Push)一個新元素,就應該把這個元素放進數組相應位置上,然後再把該數組的索引值增加1。而為了從堆疊中刪除(Pop)一個舊元素成員,先是把該數組的索引值減1,然後再把數組中由該索引值指定的元素返送回來。
下面就是以上用文字說明的堆疊類的定義(堆疊的實施):
public class Stack {protected Obj ect [] array;
protected int index;
public Stack(){
this.array=new Object[128];
this.index=0;
}
}
通常,一旦在類中確定好將要使用的一個實例變數,順理成章地就應該在構造器里先行處理它。在此例中,先定下這個數組的長度是128個“座位”——當然,我們還必須考慮如何處理多於128位“觀眾”的情況,那將在後面提及。
還要定義一個屬性Count,用於檢測堆疊中“東西”的數量:
public int Count{get{return index;}
}
請記住,堆疊中數組裡“有東西”元素的數量並不是數組的長度。初始化後,數組的長度是128,但是數組裡“有東西”元素的數量卻是0。
自然,現在應該是編寫Push和Pop兩個方法實施代碼的時候了:
public void Push(Obj ect item){array[index]=item;
index++;
} ,
public Object Pop(){
index--;
return array[index];
}
為了測試以上代碼運行情況,大家可以重新利用本章中已經套用於讎內置堆疊上的那些代碼。當然,代碼得有一點兒改動。改動之處是在“using System.Collections”這一行開頭之處加上“∥”號,即把這一行的內容變成注釋。這樣,C#運行時就不會引入來自c聊錄準庫里的堆疊,而是運用我們剛才編寫的堆疊了。
如果我們代碼編寫得完全正確,運用內置堆疊或運用自編堆疊運行程式的結果應該完全一樣。這實際例子說明:抽象數據結構運用具有兩面性,可以僅僅改變它的實施部分(提供代碼),而不必改變它的利用部分(套用代碼)。

佇列抽象數據結構

一個抽象的佇列數據結構總得由下列的一些基本操作組成:
  • 構造器:創建一個新的空佇列。
  • Enqueue:向佇列的尾部新增加一項。
  • Dequeue:從佇列中刪除一項且把該項返回,該項應是整個佇列的首項。
  • Count:檢測佇列包含的元素數量。

映射表抽象數據結構

就像另外那些我們已經學過的抽象數據結構一樣,映射表也由一系列應該具有的操作所定義:
  • 構造器:創建一個新的空的映射表。
  • [ ]:索引器。把鍵字作為索引,如果放在賦值號的左邊,存放與鍵字相對應的一個鍵值;如果放在賦值號的右邊,取出與鍵字相對應的一個鍵值。
  • ContainsKey:如果映射表中含有給定鍵字的條目,返回真。
  • Keys:屬性。返回映射表中所有鍵字的全體集合。
  • Values:屬性。返回映射表中所有鍵值的全體集合。

相關詞條

熱門詞條

聯絡我們