摘要：一抽象數據類型，縮寫為是計算機領域一種很基礎的方法，基本的思想就是數據抽象。二抽象數據類型的概念和描述抽象數據類型把數據定義為抽象的對象集合，只為他們定義可用的操作，而不用暴露具體的實現細節。

文章首發于公眾號一件風衣（ID：yijianfengyi）

名人名言強調基礎的重要性的句子不勝枚舉，數據結構與算法作為計算機專業的必學科目，其重要性不言而喻。

在以往的教學體系中，數據結構與算法通常結合C語言進行教學，而近年來Python的興起，已經引起了教學上的變化，據我了解，已經有部分大學把C語言和Python同時作為計算機專業的基礎編程課了。

這個系列就和大家一起學習數據結構與算法的Python實現，據說找工作面試時特別喜歡問基礎的算法問題。

一、抽象數據類型（Abstract Data Type，縮寫為ADT）

ADT是計算機領域一種很基礎的方法，基本的思想就是數據抽象。圍繞抽象出來的數據類型定義各種運算（函數），形成一個完整的模塊，提供接口以供調用，這就有了模塊化的編程思想。

（一）數據類型和數據構造

在任何編程語言中，都定義了一些基本的數據類型，以Python為例，基本類型有邏輯類型bool、數值類型int、float等、字符串類型str和一些組合數據類型。

對于每一種類型，都定義了相應的運算，比如bool類型的值可以為True或False，運算包括and（與）、or（或）、not（非）這類邏輯運算，int類型的值可以為整數，定義了加減乘除等運算……

但是很多時候基本數據類型是不夠用的，比如有理數、復數等，在此以復數為例，數學上復數的形式為a+bi（i為-1的平方根），定義一個復數類型的變量，我們需要兩個值，比如寫為：

a1 = 2 
b1 = 1

就可以表示復數2+i，同樣，可以定義復數上的加法運算函數：

def complex_plus(a1,b1,a2,b2):
    realpart = a1 +a2
    imaginarypart = b1 + b2
    return realpart,imaginarypart

計算2+3i與3-4i的和就可以這么使用：

a3 , b3 = complex_plus(2,3,3,-4)

雖然實現了這個功能，但是用兩個獨立的數來表示一個復數顯然不合適，給后續的使用帶來了很大不便，不過我們可以改進一下，用一個二元組來表示復數，約定第一項為實部，第二項為虛部：

c1 = (2,3)
c2 = (3,-4)

那么加法運算函數可以這么寫：

def complex_plus(c1,c2):
    realpart = c1[0] + c2[0]
    imaginarypart = c1[1] + c2[1]
    return realpart,imaginarypart

調用就可以直接這么寫：

c3 = complex_plus(c1,c2)

雖然改進了使用方式，但是依然有很大的問題：

一是用普通的元組來表示復數，不能和其他的元組相互區分，其他可以用元組表示的類型依然可以進行同樣的運算，比如有理數也用(a,b)來表示，那么可以調用復數的加法運算，把一個復數和一個有理數加起來——實部加分子，虛部加分母，這顯然不科學；

二是復數的形式還算簡潔，只有兩個參數，對于很多參數的數據類型還使用元組的話，那可真是太麻煩了。

總的來說，這樣的表示方法雖然能實現功能，但造成了很差的可讀性，使用和修改起來都會很困難，于是我們需要面向對象的方法來解決這種問題。

（二）抽象數據類型的概念和描述

抽象數據類型把數據定義為抽象的對象集合，只為他們定義可用的操作，而不用暴露具體的實現細節。對一個數據類型的操作分為三類：

1.構造：基于已知的數據類型構造所需要的數據類型，比如基于兩個整數表示一個有理數，或是基于兩個實數表示一個復數等；

2.解析：通過對象獲取需要的信息，比如從一個復數對象中獲取實部或者虛部，從一個有理數對象中獲取分子或者分母；

3.變動：修改對象的內部信息，比如修改復數的實部大小或虛部大小，對象的名稱沒變，但是內部的信息發生了變化。

我們通過一個int之類的名字來代表這個數據類型，就可以使用它了。

編程語言的內置數據類型也是這么一種抽象數據類型，構造是必要的，根據是否有變動我們可以把數據類型分為可變數據類型和不變數據類型，Python中，str就是一種不變數據類型，list就是一種可變數據類型。

那么如何描述一個抽象數據類型呢？

以復數為例，有如下偽代碼：

ADT ComplexNumber:#定義復數抽象數據類型
    ComplexNumber(float a,float b)# 構造復數a+bi
    +(ComplexNumber c1,ComplexNumber c2)# 求復數c1 + c2
    -(ComplexNumber c1,ComplexNumber c2)# 求復數c1 - c2
    *(ComplexNumber c1,ComplexNumber c2)#求復數c1 * c2
    /(ComplexNumber c1,ComplexNumber c2)#求復數c1 / c2
    getReal(ComplexNumber c1)# 獲取c1的實部
    getImaginary(ComplexNumber c1)# 獲取c1的虛部

這里用ADT表示這是一個抽象數據類型，ComplexNumber為類型名稱，同理我們也可以用類似的方法表示一個有理數，一個日期，一個銀行賬戶的基本信息等。

總的來說，ADT就是圍繞某個數據類型定義的模塊，接口和實現分離，提供接口完成該數據類型的各種操作。

二、Python類

Python作為面向對象的編程語言，用類（class）定義所有類型，包括內置的數據類型都是類，我們可以這么理解——類是面向對象編程語言的基本類型，一切數據類型都是基于類定義的。

（一）復數的初階定義

依然以復數為例，我們可以在Python中這么定義一個類：

class ComplexNumber:
    def __init__(self,realpart,imaginarypart=0):
        self.realpart = realpart
        self.imaginarypart = imaginarypart

    def plus(self,another):
        realpart = self.realpart + another.realpart
        imaginarypart = self.imaginarypart + another.imaginarypart
        return ComplexNumber(realpart, imaginarypart)

    def print(self):
        print(str(self.realpart) + “+” +str(self.imaginarypart) + “i”)

class是關鍵字，表示類定義的開始，ComplexNumber就是這個類的名字。

每個類中我們都會定義__init__函數，稱為初始化方法，用于構造一個該類的新對象，我們以類名作為函數創建實例化對象，如：

c1 = ComplexNumber(2,3)

在調用的時候，應當給出除self外的其他參數。

realpart和imaginarypart都是復數類的屬性，不用多帶帶聲明，即使在初始化中沒有，在賦值時也會自動創建，但一般不這么做。

調用其他方法時，也是self表示本實例，應當給出其他參數，比如：

c2 = c1.plus(ComplexNumber(3,-2))

此時c1的值作為plus方法的第一個參數，新構造的復數為第二個。

同理，print函數中只有一個參數self，所以調用的時候這么寫：

c2.print()

執行以上語句后我們可以得到如下輸出：

（二）復數的高階定義
對于復數，我們經常使用模的概念，對于z=a+bi，模|z|定義如下：

所以我們需要函數module()，來求取復數的模。可以定義如下

def module():
    return math.sqrt(self.realpart *self.realpart, self.imaginarypart * self.imaginarypart)

調用輸出一個復數時直接這么寫：

print(c2.module())

其中math.sqrt()是求平方根的函數，需要在程序開頭導入math包：
import math

在定義Python的類時，有這樣的約定，以下劃線開頭的屬性名或函數名都當作內部使用的名字，不能夠在類外使用。此外以兩根下劃線開頭（不以兩根下劃線結尾）的屬性會被特殊處理保護，不得在類外使用。如果我們不希望復數的虛部實部屬性被直接修改，初始化方法中我們可以在屬性前加下劃線，阻止類外的訪問：

def __init__(self,realpart,imaginarypart=0):
        self._realpart = realpart
        self._imaginarypart = imaginarypart

然而我們有時又很需要讀取這兩個屬性，于是我們可以定義解析操作：

def realpart(self): return self._realpart
def imaginarypart(self): return self._imaginarypart

這樣可以讀取受保護的屬性了。

我們再考慮新的問題，在數學上我們可以直接用加減乘除的符號來操作復數，按照我們上面的定義，顯然調用起來很不方便，要是能直接把方法定義在操作符上，那使用起來也就方便多了。

好消息是Python中可以這么做！Python中為所有的運算符都定義了特殊的方法名，這類特殊方法名都以雙下劃線開始，雙下劃線結束，如__add__表示加號，__mul__表示乘號，于是對于復數中的加法，我們可以如下實現：

def __add__(self,another):
    realpart = self._realpart + another.realpart()
    imaginarypart = self._imaginarypart + another.imaginarypart()
    return ComplexNumber(realpart, imaginarypart)

注意這段代碼中self和another獲取屬性的方式的區別。

類似的，我們可以定義其他運算符的操作（包括比較運算符），具體的方法名可以查找Python的文檔。但重載運算符時要注意限制條件，比如虛部實部均為0的復數不能作為除數等。

（三）幾點總結和提示

1.類定義時格式如下：

class <類名>:
    <語句組>

2.對類中的屬性的訪問，采用圓點記法；
3.實例對象初始化時自動調用__init__()，第一個參數self表示正在初始化的對象自身；
4.在定義類時，應當避免屬性名和方法名相同；
5.靜態方法、類方法、作用域、繼承等日后再提。

思考：如果要定義一個學生類，屬性包括姓名，性別，生日，學號，方法包括計算年齡，修改屬性，打印全部屬性，初始化時生成學號，規則是年份+順序五位十進制數，你會怎么實現這個類呢？下一篇中會貼出我的實現方法，歡迎探討。（提示：類中可定義屬性，該屬性不屬于任何實例，只屬于類本身）