本節書摘來自華章出版社《資料結構與算法：python語言描述》一書中的第2章，第2.1節，作者 裘宗燕，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
在讨論具體的資料結構概念和技術之前，本章将首先介紹抽象資料類型的重要概念和python面向對象的程式設計技術。後者可以看作一種實作抽象資料類型的技術，但還有所擴充，它也是本書中實作各種資料結構時使用的基本技術。
抽象資料類型（abstract data type，adt）是計算機領域中被廣泛接受的一種思想和方法，也是一種用于設計和實作程式子產品的有效技術。adt的基本思想是抽象，或者說是資料抽象（與函數定義實作的計算抽象或稱過程抽象對應）。
按照抽象的思想，設計者在考慮一個程式部件時，應該首先給出一個清晰邊界，通過一套接口描述說明這一程式部分的可用功能，但并不限制功能的實作方法。從使用者的角度看，一個程式部件實作了一種功能，如果适合實際需要，就可以通過其接口使用之，并不需要知道其實作的具體細節。python的函數就是一種功能部件，其頭部定義了它的接口，描述了函數的名字及其對參數的要求。使用者隻需要考慮函數的功能是否滿足實際需要，還要保證調用式符合函數頭部的要求，并不需要知道函數實作的任何具體細節。
在程式開發實踐中人們逐漸認識到，僅有計算層面的抽象機制和抽象定義還不夠，還需要考慮資料層面的抽象。能圍繞一類資料建立程式元件，将該類資料的具體表示和相關操作的實作包裝成一個整體，也是組織複雜程式的一種有效技術，可以用于開發出各種有用的程式子產品。要把這種圍繞着一類資料對象構造的子產品做成資料抽象，同樣需要區分子產品的接口和實作。子產品接口提供使用它提供的功能所需的所有資訊，但不涉及具體實作細節。另一方面，子產品實作者則要通過子產品内部的一套資料定義和函數（過程）定義，實作子產品接口的所有功能，從形式上和實際效果上滿足子產品接口的要求。
類型（資料類型）是程式設計領域最重要的基本概念之一。在程式裡描述的、通過計算機去處理的資料，通常都分屬不同的類型，例如整數或浮點數等。每個類型包含一集合法的資料對象，并規定了對這些對象的合法操作。各種程式設計語言都有類型的概念，每種語言都提供了一組内置資料類型，為每個内置類型提供了一批操作。
以python為例，它提供的基本類型包括邏輯類型bool、數值類型int和float等、字元串類型str，還有一些組合資料類型。類型bool包括兩個值（兩個對象）true和false，可用操作包括and、or和not；數值類型int包含很多值（整數對象），對它們可做加減乘除等運算；其他類型的情況相仿。開發程式時，應該根據需要選擇合适的資料類型。
但是，無論程式設計語言提供了多少内置類型，在處理較為複雜的問題時，程式員或早或晚都會遇到一些情況，此時各種内置類型都不能滿足或者不适合于自己的需要。在這種情況下，程式設計語言提供的組合類型有可能幫助解決一些問題。例如，python為資料的組合提供了list、tuple、set、dict等結構（它們也看作是類型），程式設計時可以利用它們把一組相關資料組織在一起，構成一個資料對象，作為一個整體存儲、傳遞和處理。
舉個例子，假設程式裡需要處理有理數。最簡單樸素的想法是用兩個整數表示一個有理數，分别表示其分子和分母，在此基礎上實作所需要的運算和操作。在這種安排下，把有理數3/5存入變量可能寫成：
利用python函數可傳回多對象元組和多項指派的機制，加法函數可以如下定義：
下面是一個簡單的函數使用執行個體：
不難想到，如果真這樣寫程式，很快就會遇到非常麻煩的管理問題：程式設計者需要時時記住哪兩個變量記錄的是一個有理數的分子和分母，操作時不能混淆不同的有理數；如果需要換一個有理數參與運算，也會遇到成對變量名的代換問題。程式比較複雜時，做這類事情很容易出錯，而如果真發現程式有錯誤，确定錯誤的位置和更正也将極其費時費力。總而言之，用獨立的分别存在的兩個整數表示一個有理數，這種技術完全不可取。
一種簡單改進是利用程式設計語言的資料組合機制，把相關的多項簡單資料組合在一起。還是看有理數的例子，可以考慮用一個python元組（tuple）表示一個有理數，約定用其中的第0項表示分子，用第1項表示分母。這樣就可以寫：
現在情況顯然好了很多，許多管理問題得到緩解。這就是資料構造群組織的作用。
但是，如果進一步考慮，就會發現這種做法仍然有多方面的缺陷，例如：
1）在這裡使用的不是特殊的“有理數”，而是普通的元組，是以不能将其與其他元組互相區分。例如，假設程式裡還需要處理平面上的整數格點資料，格點也可能用整數的二進制組表示，例如，(3, 5) 表示平面上x坐标為3而y坐标為5的點。從概念上說，把一個有理數與一個格點相加完全是荒謬的事情。但python程式設計語言，包括上面定義的rational_plus函數都不會認為這樣做是一個錯誤。
2）與有理數相關的操作并沒有綁定于表示有理數的二進制組。由于python不需要說明函數參數的類型，這個問題表現得更加嚴重。
3）在為有理數對象定義運算（函數）時，需要直接按位置取得其元素。對有理數這樣結構很簡單的對象，操作中隻需區分位置0和1，還算比較容易處理，給思維帶來的負擔也還可以忍受。如果需要處理的資料對象更複雜，例如其中包含了十幾甚至幾十個不同成員。在為這種組合資料對象定義操作時，記住每個成員在對象裡的位置并正确使用，也會變成非常麻煩的事情。修改資料表示就更讓人頭痛了。
以上幾點和其他一些情況都說明，簡單地使用語言提供的資料組合機制，對于處理複雜程式裡的資料組織問題是不夠的。上面前兩點表明的主要問題是，按照這種方式構造和使用的“有理數”不是一個類型，是以不能得到python語言裡的類型功能（如類型檢查）的支援。第3點說明，簡單地用元組等表示内部結構複雜的資料，經常會導緻程式不易閱讀和了解，使程式難以編寫正确，難以修改。抽象資料類型的思想和支援這種思想的程式設計語言機制能幫助解決這些問題，至少是使問題大大緩解。
造成前一節中揭示出的程式設計缺陷，最重要的問題之一是資料的表示完全暴露，以及對象使用和操作實作對具體表示的依賴性。要克服這些缺點，就需要把對象的使用與其具體實作隔離開。理想情況是：在程式設計中使用一種對象時，隻需考慮應該如何使用，不需要（最好是根本不能）去關注和觸及對象的内部表示。這樣的資料對象就是一種抽象資料單元，一組這樣的對象構成一個抽象的資料類型，為程式裡的使用提供了一套功能。
抽象資料類型的基本想法是把資料定義為抽象的對象集合，隻為它們定義可用的合法操作，并不暴露其内部實作的具體細節，不論是其資料的表示細節還是操作的實作細節。當然，要使用一種對象，首先需要能構造這種對象，而後能操作它們。抽象資料類型提供的操作應該滿足這些要求。一個資料類型的操作通常可以分為三類：
1）構造操作：這類操作基于一些已知資訊，産生出這種類型的一個新對象。例如，基于一對整數産生出一個有理數對象；或者基于兩個已有的有理數對象，産生出一個表示它們之和的有理數對象；等等。
2）解析操作：這種操作從一個對象取得有用的資訊，其結果反映了被操作對象的某方面特性，但結果并不是本類型的對象。例如，可能需要有兩個操作，分别從一個有理數擷取其分子或者分母，操作的結果應該是整數（整數類型的對象）。
3）變動操作：這類操作修改被操作對象的内部狀态。例如，對于一個銀行賬戶對象，其類型就應該提供檢查餘額和修改餘額的操作等。經過一次變動操作之後，對象還是原來的賬戶對象，仍然表示原來的銀行客戶的有關資訊，但是對象内部記錄的存款餘額改變了，反映了實際客戶賬戶的餘額變動。
當然，一個抽象資料類型還應該有一個名字，用于代表這個類型。
其實，程式設計語言的一個内置類型就可以看作是一個抽象資料類型。python的字元串類型str是一個典型執行個體：字元串對象有一種内部表示形式（無須對外宣布），人們用python程式設計式時并不依賴于實際表示（甚至不知道其具體表示方式）；str提供了一組操作供程式設計使用，每個操作都有明确的抽象意義，不依賴于内部的具體實作技術。易見，python的整數類型int和實數類型float等的情況與str類似。當然，對于内置類型，語言有可能為它們提供一些額外的友善。如python為字元串提供了文字量書寫方式，可以看作簡化的構造操作。從其他角度看，内置類型也就是一種抽象資料類型。
作為資料類型，特别是比較複雜的資料類型，有一個很重要的性質稱為變動性，表示該類型的對象在建立之後是否允許變化。如果某個類型隻提供上面的第1和第2類操作，那麼該類型的對象在建立之後就不會變化，永遠處于一個固定的狀态。這樣的類型稱為不變資料類型，這種類型的對象稱為不變對象。對于這種類型，在程式裡隻能（基于其他資訊或已有對象）構造新對象或者取得已有對象的特性，不能修改已建立的對象。如果一個類型提供了第3類操作，對該類型的對象執行這種操作後，雖然對象依舊，但其内部狀态已經改變。這樣的類型就稱為可變資料類型，其對象稱為可變對象。下面經常把不變資料類型和可變資料類型分别簡稱為不變類型和可變類型。
例如，python語言對str類型隻提供了前兩類操作，是以str是一個不變資料類型；對list類型提供了所有三類操作，它是一個可變資料類型。python語言裡的str、tuple和frozenset是不變資料類型，而list、set和dict是可變資料類型。在程式設計中設計或定義抽象資料類型時，也要根據情況，決定是将其定義為不變類型還是可變類型。
前面的讨論實際上說明，程式員也需要掌握抽象資料類型的思想和技術。同時說明，程式設計語言應支援程式員定義自己的抽象資料類型。下面首先通過一些例子，考察在定義一個抽象資料類型時應該怎樣思考問題，怎樣描述抽象資料類型，描述中應該給出哪些資訊。然後讨論python語言怎樣支援這一類定義。
定義一個抽象資料類型，目的是要定義一類計算對象，它們具有某些特定的功能，可以在計算中使用。這類對象的功能展現為一組可以對它們使用的操作。當然，還需要為這一抽象資料類型确定一個類型名。
下面為抽象資料類型引進一種描述方式，其形式展現了抽象資料類型的主要特點。在後面介紹各種資料結構時，有關章節中也經常是先給出一個抽象資料類型的描述。寫出這種描述的過程本身也很有意義，因為它能幫助開發者理清對希望定義的資料類型的想法，清晰地表述出各方面的形式要求（如操作的名字、參數的個數和類型等）和功能要求（希望這個操作完成什麼樣計算，或産生什麼效果等）。
現在考慮一個簡單的有理數抽象資料類型，有下面描述：
這裡用特殊名字adt表示這是一個抽象資料類型類型的描述，随它之後給出被定義類型的名字。adt定義的主要部分描述了一組操作，每個操作的描述由兩個部分組成：首先是用辨別符或者特殊符号的形式給出的操作名和操作的參數表，随後用類似python注釋的形式給出操作的功能描述。另請注意，在描述操作的參數時，可以考慮在參數名前寫一個類型名，表示這個參數應該具有的類型；也可以省略，通過文字叙述說明。
具體到上面的抽象資料類型，其名字是rational，其中共提供了7個操作。第一個操作以rational作為名字，這種形式表示它是一個最基本的構造操作，從其他類型的參數出發構造本類型的對象。随後的幾個算術運算也是構造操作，它們基于rational類型的對象生成rational類型的新對象。最後兩個是解析操作，取得有理數對象的性質（成分）。
使用抽象資料類型的思想和技術，不但可以描述有理數一類數學類型，也可以描述實際應用中所需的各種類型。例如，下面描述了一個表示日期的抽象資料類型：
在這個描述裡，同樣用注釋的形式給出了每個操作的解釋。注意，上面這個類型裡出現了一個第3類操作adjust。舉例說明其用途：假設在一個實際應用中建立了一個表示開會日期的對象，随後這個對象被系統中的許多地方（展現為具體的功能子產品）共享，如會務、交通、餐飲、住宿等方面的管理子系統。後來出現了一些情況，導緻會議的會期需要修改。這時存在兩種修改方案：其一是用adjust操作去修改那個日期對象，由于對象共享，這樣修改的效果将被各有關機構直接看到；第二個方案是另行構造一個表示新會期的對象，然後重新給各個部門發一輪通知，要求它們都用新日期對象替換原來的對象。顯然這兩種方案都能解決問題，但是基于它們的工作細節卻大不相同。
上面看了兩個抽象資料類型的例子，現在總結其中的一些情況：
一個adt描述由一個頭部和按一定格式給出的一組操作描述構成。
adt的頭部給出類型名，最前面是表示抽象資料類型的關鍵詞adt。
操作的形式描述給出操作的名字、參數的類型和參數名。在adt描述中，參數名主要用在解釋這個操作的功能的地方（上面借用了python的注釋形式）。
各操作的實際功能用自然語言描述，這是一種非形式的說明，主要是為了幫助了解這些操作需要（能夠）做什麼，以便正确地實作和使用它們。
在抽象資料類型的描述中，其他方面都比較清晰和嚴格，用自然語言形式給出的功能描述則不然。自然語言有着天然的非精确性和歧義性，用它寫的描述很難精确無誤。這種描述的意義需要人去了解，誤解是造成錯誤的最重要根源之一。
舉例說，仔細考慮上面有關日期的adt，會發現一些說得不夠清楚的地方。例如，“求出d1和d2的日期差”是什麼意思？是否包含兩端（或者一端）的日期？對整數n“調整n天”的确切含義是什麼？這些可能需要進一步解釋。
實際上，這類問題确實比較難處理，因為上述說明是希望解釋有關操作的“語義”，也就是它的意義、行為或者效果。對各種實際程式部件（或推而廣之，各種程式和實際應用），精确而且正确地了解其中各種操作的功能，顯然是最重要的一件事情。但是，語義的描述卻很不簡單。雖然在有關計算機科學技術的研究中，人們已經提出了一些描述語義的方法，但這些方法都比較複雜，确切的描述仍然不容易寫好，也不容易了解。使用這些描述方式需要特别的學習和鍛煉，絕大部分程式開發者沒有這種經驗，是以在實踐中使用得不多。語義描述方面的進一步情況已經超出了本課程的範圍，這裡不再深入。是以，本書後面的執行個體還将繼續使用自然語言的描述。當然，在寫這種描述時，應該盡可能避免歧義性和誤解。例如，可以在描述中結合使用數學符号和自然語言，對一些一般性情況和特殊情況，給出具體執行個體說明等。這種方式基本上能滿足本書的需要。
adt是一種思想，也是一種組織程式的技術，主要包括：
1）圍繞着一類資料定義程式子產品，如上面的rational和date都是這樣。
2）子產品的接口和實作分離。上面隻給出了子產品的接口規範，包括子產品名、子產品提供的各個操作的名字和參數。每個操作還有非形式化的語義說明。
3）在需要實作時，從所用的程式設計語言裡選擇一套合适的機制，采用合理的技術，實作這種adt的功能，包括具體的資料表示和操作。
如何在python裡實作抽象資料類型，是下一節的主題。