多態及其在數據結構中的應用

胡傳福

(東莞理工學院 計算機學院，廣東東莞 523808)

面向對象程序設計的強大之處不僅在于繼承，更在于將派生類對象當成基類對象一樣使用的能力。支持這種能力的機制主要有兩點——多態和動態綁定。多態是指同樣的消息被不同類型的對象收到以后會導致完全不同的行為，這里所說的消息是指對類的成員函數的調用，不同的行為是指不同的函數實現，本質上其實是調用了完全不同的函數［1］。

多態 (polymorphism)一詞最早來源于拉丁語poly(意為多)和morphos(意為形態)，意指具有多種形式或形態。它反映了人們在思索解決問題的辦法時，對相似的問題的一種求解方法，用在C++中一個最大的特點是它在軟件開發的過程中具有了“更大的靈活性”和“更多的可重用性”，它可以使得一個對象在不同的情況下具有完全不同的表現形態。多態的思想允許一個對象在不同的環境中具有不同的解釋，進而發揮不同的功能，具有靈活的表述能力，既支持數據抽象，又方便了軟件設計。

1 多態的類型

在面向對象程序設計中，多態分為四種情況:強制多態、重載多態、參數多態以及包含多態。前面兩種是專用多態，后面兩種是通用多態［1］。函數重載屬于重載多態;強制多態指的是將一個變元的類型加以改變，以迎合某個函數或是某個操作的要求;包含多態是指在一類類 (也就是很多個具有相似或相關功能的類，也稱類族)中定義的不同類中的同名成員函數的一種多態行為，它主要是通過虛函數來實現的;參數多態與類模版有關，在具體使用的時侯必須要賦給一個實際的類型才能被實例化。

2 多態的實現

從實現的角度看，多態可以分為兩類:編譯時的多態和運行時的多態。前者是在編譯的時候確定同名操作的具體操作對象是哪個，而后者則需要在程序運行的過程中才能動態地確定操作的對象是誰。這種確定操作的具體對象的過程叫綁定或聯編。綁定是一個個計算機的程序塊進行彼此關聯的過程，例如把一個標識符和某個對象的方法結合在一起。按照綁定的進行階段不同，綁定又分為靜態綁定和動態綁定兩種不同的方法。這兩種方法則分別對應著多態的兩種實現方式。

綁定發生在編譯連接階段的情況稱靜態綁定。在編譯、連接的過程中就能根據類型匹配等相關特征確定出程序中某操作調用與執行該操作代碼的關系，也即能夠確定某一同名標識是要調用哪一段程序代碼。重載、強制及參數多態都是靜態綁定的。

綁定發生在程序運行階段的情況稱動態綁定。當在編譯、連接的過程中無法解決某個綁定問題，需要等到程序運行之后準確地說是程序運行的過程中才能確定，包含多態的操作對象的確定就是這種通過動態綁定來完成的。

多態是有下列4種類型和用法。

1)重載多態 又稱函數重載。當兩個以上具有相同名稱的函數，形參的類型或者個數不同時，編譯器會根據值參和形式參數的類型、個數的最佳匹配，來自動確定調用哪一個函數［1］。其中，形參的類型和個數共同構成函數的簽名，簽名不同，即為重載函數。

如:

根據函數的簽名不同，addDigit(123，321)、addDigit(1.2345f，3.4678f)和 addDigit(12，22，32)分別被編譯成對 addDigit(int，int)、addDigit(float，float)和addDigit(int，int，int)的調用。原理在于編譯器會根據不同的參數列表對同名函數進行名字重整，然后這些同名函數就會變成不同的函數。比如說某個編譯器會它們的名字分別重整為addDigit_int()、addDigit_float()和addDigit_tri_int()。

2)強制多態 是指將一個變元的類型加以變化，以滿足某個函數或者操作的要求，上例中，加法運算符在浮點數與整型數相加時，會先進行類型強制轉換，把整型數變為浮點數，再相加。

3)包含多態 是指在程序運行過程中動態地確定操作的具體對象。其技術基礎是抽象類和虛函數。例如，下面定義了一個抽象基類Machine和兩個派生于Machine的具體類Lathe和Elevator:

通過指向基類Machine的指針來操縱具體對象。通過指向基類對象的指針調用虛函數，實際上調用的是被指向的那個具體對象的類的相應成員函數。

//通過指針working任何Machine

本例中，關鍵在于多態的接口元素，也就是虛函數working()。由于working_Machine()的參數是指向基類Machine的指針，因此在編譯的時侯無法確定調用的是哪一個類的成員函數working()。而在運行的時侯，為了指派函數調用，需要訪問虛函數被調用的那個具體對象的完整的數據類型。如此一來，用Lathe對象調用working_Machine()，實際上調用的是Lathe::working()，而用Elevator對象卻調用的是Elevator::working()。

4)參數多態 參數多態與模版類相關聯，在使用的時侯必須賦給具體的類型才能被實例化，這種由類模版實例化的所有的類都具有相同的操作，但操作對象的類型卻是各不相同的。下面用參數多態重寫3)中的例子，不再定義Machine類層次結構，只定義兩個彼此無關的具體類Lathe和Elevator。

編譯器處理后，會得到working_Machine＜Lathe＞()和 working_Machine＜Elevator＞()兩個不同的函數，這點和動態多態不同，動態多態憑借虛函數分派機制，在運行期只有一個working_Machine()函數。

3 多態在數據結構中的應用

在數據結構中，數據由數據項組成;數據項是一條信息，或者是其值屬于某種數據類型的一條記錄，它是數據類型的成員;類型是一組值的集合;數據類型是指一種類型以及定義在該種類型上的一組操作;抽象數據類型 (abstract data type，簡稱ADT)一般是指數據結構作為某個軟件組件的實現。ADT的接口用一種類型加上該種類型上的一組操作定義，而每個操作又由它的輸入和輸出單獨定義。ADT并不關心數據類型如何實現，實現細節對于ADT的用戶來說通常是隱藏的，通過封裝來阻止外部對象對它的訪問［3］。

數據結構是ADT的實現。在C++這類面向對象的程序設計語言中，ADT及其實現一起共同組成了類。同ADT有關的每個操作全部由成員函數來實現。ADT與具體應用無關，這樣可以讓程序員把精力更多地用在數據及其操作的理想模型上。

而所謂參數化多態，本質上就是將程序要處理的對象的數據類型參數化，使一段程序可以用來處理多種不同類型的對象。類模版能讓用戶為類聲明一種模式，使得類中的數據成員、成員函數的參數、成員函數的返回值可以取任意類型［4］。

數據結構的ADT的特性和模版類的特點可以說是相通的。模版類對數據結構來說是應運而生，傳統的數據結構在模版類的描述下更是煥發出了新的生機與活力。

4 結語

動態多態只需要一個函數，生成的可執行代碼尺寸比較小，靜態多態必須要對不同的類型生成不同的模板實體，尺寸要大一點，但是因為不需通過指針進行間接操作，所以生成的代碼也會更快一點。靜態多態與動態多態相比，因為全部綁定發生在編譯的時候，所也更加類型安全。因為系統不允許將一個錯誤類型的對象插入到從一個模板類實例化而來的容器中的。此外，動態多態在處理異質對象集合上就優雅得多了，靜態多態卻可以實現安全、高效的同質對象集合操作，并為C++帶來了泛型編程的概念。

數據結構經過幾十年的發展，于上個世紀成熟穩定，許多算法早在20世紀六、七十年代已成型，不少算法思想早于計算機出現。多態算法思想的提出為古老的數據結構注入了新的生機與活力，必將為計算機科學技術的發展提供新的動力。

［1］鄭莉，董淵，何江舟．C++語言程序設計［M］．4版．北京:清華大學出版社，2010．

［2］Mark Allen Weiss．數據結構與算法分析C++描述［M］．3版．張懷勇，譯．北京:人民郵電出版社，2007．

［3］Clifford A．Shaffer．數據結構與算法分析(C++版)［M］．2版．張銘，劉曉丹，譯．北京:電子工業出版社，2002．

［4］Malik D S．C++編程—數據結構與程序設計方法［M］．晏海華，蔡旭輝，常鴻，等譯．北京:電子工業出版社，2003．