基本介紹
- 中文名：抽象數據結構
- 外文名：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：屬性。返回映射表中所有鍵值的全體集合。
