如何理解ADT（抽象數據類型代數）？

我正在參加CS課程，但坦率地說，我不知道講師講的是什麼抽象數據類型代數。這並不是我很容易在網絡上找到解決方案的原因，我想也許社區中的某個人會對問題有更深刻的洞察力或未解決的問題。如何理解ADT（抽象數據類型代數）？

堆棧：

isempty(createstack()) = true 
isempty(push(n, s)) = false 
top(push(n, s)) = n 
pop(push(n, s)) = s

隊列：

isempty(createqueue()) = true 
isempty(add(n, q)) = false 
front(add(n, q)) = n, if q is empty 
front(add(n, q)) = front(q), if q is not empty removefront(add(n, q)) = q, 
if q is empty  removefront(add(n, q)) = add(n, removefront(q)), 
if q is not empty

符號無疑是一個有點奇怪......什麼是高於平均實質〜我明白隊列的一般行爲和作爲先進先出和先進先出的堆疊。

來源

2013-02-09 peter_gent

沒有那些只是規則描述它是如何工作的？。例如「isempty（add（n，q））= false」...如果將N添加到隊列Q中，Q不是空的...如果將N添加到Q並且Q是空的，前面是N – 2013-02-09 22:28:03

即可。在演講中，演講者將演講者的方括號內的括號括起來，用於某些複雜的抽象運算符。 – 2013-02-09 22:51:49

這裏沒有「ADT代數」。該文章包含操作和*僞代碼*（這意味着，它應該是「在上下文中可理解的」，但沒有其他）描述了預期的操作行爲。分別閱讀堆棧或隊列，以瞭解具體的實現細節/示例和「真實」使用案例。 – 2013-02-09 23:38:36

抽象數據類型可用於描述類型的行爲必須如何指定實現。您將類型定義爲一組公理或規則，用於描述哪些條件必須在每個時刻都適用。 Djikstra曾經說過ADT是描述隊列行爲的非常有用的工具......但是，把Djikstra的着名的超級批評者幽默放在一邊，我可以想到至少有一個ADT的實際應用：assertions。

斷言允許您指定類型如何以正式，可編譯，可運行的語言（與自然語言文檔相反）工作。在Design by contract methodoloy中，它們通常被寫成謂詞，它必須在源語言或某種形式的元語言的方法執行之前或之後（通常是該類型的任何操作）持有。支持斷言的框架（例如.NET的CodeContracts）會自動檢查每個謂詞在應該出現時的狀態。這樣，如果你自己的代碼違反了你的一個斷言，你就知道你有一個bug。因此，從某種意義上說，它可以被看作是單元測試的一種形式，而不是通過指定測試用例（這將是實證測試方法），而是通過指定您的類型必須符合的先決條件，後置條件和不變量（這將是理論測試方法）。

儘管我沒有在主流軟件開發中使用過，但據我所知（檢查斷言可能會影響性能），但它們可以在測試過程中使用。

從純理論的角度來看，ADT就是這樣一種抽象，它允許我們推理類型的行爲，而不管它們的具體實現如何。如果你喜歡形式主義（就像我一樣），沒有什麼比開發人員給你一個定理列表更好，而不是描述他的代碼應該做什麼的模糊喋喋不休。另一方面，諸如邏輯或函數式編程的某些替代編程範例（替代於面向對象的替代，而不是次要的，不重要的等）是基於類型構造的ADT而沉重的。一個非常有趣的例子是Haskell語言。它爲您提供了一個類型，繼承和多態的全新圖片。

來源

2013-02-14 16:24:13

如何理解ADT（抽象數據類型代數）？

回答

相關問題