多態(tài)及其在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用

胡傳福

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

面向?qū)ο蟪绦蛟O(shè)計(jì)的強(qiáng)大之處不僅在于繼承，更在于將派生類(lèi)對(duì)象當(dāng)成基類(lèi)對(duì)象一樣使用的能力。支持這種能力的機(jī)制主要有兩點(diǎn)——多態(tài)和動(dòng)態(tài)綁定。多態(tài)是指同樣的消息被不同類(lèi)型的對(duì)象收到以后會(huì)導(dǎo)致完全不同的行為，這里所說(shuō)的消息是指對(duì)類(lèi)的成員函數(shù)的調(diào)用，不同的行為是指不同的函數(shù)實(shí)現(xiàn)，本質(zhì)上其實(shí)是調(diào)用了完全不同的函數(shù)［1］。

多態(tài) (polymorphism)一詞最早來(lái)源于拉丁語(yǔ)poly(意為多)和morphos(意為形態(tài))，意指具有多種形式或形態(tài)。它反映了人們?cè)谒妓鹘鉀Q問(wèn)題的辦法時(shí)，對(duì)相似的問(wèn)題的一種求解方法，用在C++中一個(gè)最大的特點(diǎn)是它在軟件開(kāi)發(fā)的過(guò)程中具有了“更大的靈活性”和“更多的可重用性”，它可以使得一個(gè)對(duì)象在不同的情況下具有完全不同的表現(xiàn)形態(tài)。多態(tài)的思想允許一個(gè)對(duì)象在不同的環(huán)境中具有不同的解釋?zhuān)M(jìn)而發(fā)揮不同的功能，具有靈活的表述能力，既支持?jǐn)?shù)據(jù)抽象，又方便了軟件設(shè)計(jì)。

1 多態(tài)的類(lèi)型

在面向?qū)ο蟪绦蛟O(shè)計(jì)中，多態(tài)分為四種情況:強(qiáng)制多態(tài)、重載多態(tài)、參數(shù)多態(tài)以及包含多態(tài)。前面兩種是專(zhuān)用多態(tài)，后面兩種是通用多態(tài)［1］。函數(shù)重載屬于重載多態(tài);強(qiáng)制多態(tài)指的是將一個(gè)變?cè)念?lèi)型加以改變，以迎合某個(gè)函數(shù)或是某個(gè)操作的要求;包含多態(tài)是指在一類(lèi)類(lèi) (也就是很多個(gè)具有相似或相關(guān)功能的類(lèi)，也稱(chēng)類(lèi)族)中定義的不同類(lèi)中的同名成員函數(shù)的一種多態(tài)行為，它主要是通過(guò)虛函數(shù)來(lái)實(shí)現(xiàn)的;參數(shù)多態(tài)與類(lèi)模版有關(guān)，在具體使用的時(shí)侯必須要賦給一個(gè)實(shí)際的類(lèi)型才能被實(shí)例化。

2 多態(tài)的實(shí)現(xiàn)

從實(shí)現(xiàn)的角度看，多態(tài)可以分為兩類(lèi):編譯時(shí)的多態(tài)和運(yùn)行時(shí)的多態(tài)。前者是在編譯的時(shí)候確定同名操作的具體操作對(duì)象是哪個(gè)，而后者則需要在程序運(yùn)行的過(guò)程中才能動(dòng)態(tài)地確定操作的對(duì)象是誰(shuí)。這種確定操作的具體對(duì)象的過(guò)程叫綁定或聯(lián)編。綁定是一個(gè)個(gè)計(jì)算機(jī)的程序塊進(jìn)行彼此關(guān)聯(lián)的過(guò)程，例如把一個(gè)標(biāo)識(shí)符和某個(gè)對(duì)象的方法結(jié)合在一起。按照綁定的進(jìn)行階段不同，綁定又分為靜態(tài)綁定和動(dòng)態(tài)綁定兩種不同的方法。這兩種方法則分別對(duì)應(yīng)著多態(tài)的兩種實(shí)現(xiàn)方式。

綁定發(fā)生在編譯連接階段的情況稱(chēng)靜態(tài)綁定。在編譯、連接的過(guò)程中就能根據(jù)類(lèi)型匹配等相關(guān)特征確定出程序中某操作調(diào)用與執(zhí)行該操作代碼的關(guān)系，也即能夠確定某一同名標(biāo)識(shí)是要調(diào)用哪一段程序代碼。重載、強(qiáng)制及參數(shù)多態(tài)都是靜態(tài)綁定的。

綁定發(fā)生在程序運(yùn)行階段的情況稱(chēng)動(dòng)態(tài)綁定。當(dāng)在編譯、連接的過(guò)程中無(wú)法解決某個(gè)綁定問(wèn)題，需要等到程序運(yùn)行之后準(zhǔn)確地說(shuō)是程序運(yùn)行的過(guò)程中才能確定，包含多態(tài)的操作對(duì)象的確定就是這種通過(guò)動(dòng)態(tài)綁定來(lái)完成的。

多態(tài)是有下列4種類(lèi)型和用法。

1)重載多態(tài) 又稱(chēng)函數(shù)重載。當(dāng)兩個(gè)以上具有相同名稱(chēng)的函數(shù)，形參的類(lèi)型或者個(gè)數(shù)不同時(shí)，編譯器會(huì)根據(jù)值參和形式參數(shù)的類(lèi)型、個(gè)數(shù)的最佳匹配，來(lái)自動(dòng)確定調(diào)用哪一個(gè)函數(shù)［1］。其中，形參的類(lèi)型和個(gè)數(shù)共同構(gòu)成函數(shù)的簽名，簽名不同，即為重載函數(shù)。

如:

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

2)強(qiáng)制多態(tài) 是指將一個(gè)變?cè)念?lèi)型加以變化，以滿足某個(gè)函數(shù)或者操作的要求，上例中，加法運(yùn)算符在浮點(diǎn)數(shù)與整型數(shù)相加時(shí)，會(huì)先進(jìn)行類(lèi)型強(qiáng)制轉(zhuǎn)換，把整型數(shù)變?yōu)楦↑c(diǎn)數(shù)，再相加。

3)包含多態(tài) 是指在程序運(yùn)行過(guò)程中動(dòng)態(tài)地確定操作的具體對(duì)象。其技術(shù)基礎(chǔ)是抽象類(lèi)和虛函數(shù)。例如，下面定義了一個(gè)抽象基類(lèi)Machine和兩個(gè)派生于Machine的具體類(lèi)Lathe和Elevator:

通過(guò)指向基類(lèi)Machine的指針來(lái)操縱具體對(duì)象。通過(guò)指向基類(lèi)對(duì)象的指針調(diào)用虛函數(shù)，實(shí)際上調(diào)用的是被指向的那個(gè)具體對(duì)象的類(lèi)的相應(yīng)成員函數(shù)。

//通過(guò)指針working任何Machine

本例中，關(guān)鍵在于多態(tài)的接口元素，也就是虛函數(shù)working()。由于working_Machine()的參數(shù)是指向基類(lèi)Machine的指針，因此在編譯的時(shí)侯無(wú)法確定調(diào)用的是哪一個(gè)類(lèi)的成員函數(shù)working()。而在運(yùn)行的時(shí)侯，為了指派函數(shù)調(diào)用，需要訪問(wèn)虛函數(shù)被調(diào)用的那個(gè)具體對(duì)象的完整的數(shù)據(jù)類(lèi)型。如此一來(lái)，用Lathe對(duì)象調(diào)用working_Machine()，實(shí)際上調(diào)用的是Lathe::working()，而用Elevator對(duì)象卻調(diào)用的是Elevator::working()。

4)參數(shù)多態(tài) 參數(shù)多態(tài)與模版類(lèi)相關(guān)聯(lián)，在使用的時(shí)侯必須賦給具體的類(lèi)型才能被實(shí)例化，這種由類(lèi)模版實(shí)例化的所有的類(lèi)都具有相同的操作，但操作對(duì)象的類(lèi)型卻是各不相同的。下面用參數(shù)多態(tài)重寫(xiě)3)中的例子，不再定義Machine類(lèi)層次結(jié)構(gòu)，只定義兩個(gè)彼此無(wú)關(guān)的具體類(lèi)Lathe和Elevator。

編譯器處理后，會(huì)得到working_Machine＜Lathe＞()和 working_Machine＜Elevator＞()兩個(gè)不同的函數(shù)，這點(diǎn)和動(dòng)態(tài)多態(tài)不同，動(dòng)態(tài)多態(tài)憑借虛函數(shù)分派機(jī)制，在運(yùn)行期只有一個(gè)working_Machine()函數(shù)。

3 多態(tài)在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用

在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)由數(shù)據(jù)項(xiàng)組成;數(shù)據(jù)項(xiàng)是一條信息，或者是其值屬于某種數(shù)據(jù)類(lèi)型的一條記錄，它是數(shù)據(jù)類(lèi)型的成員;類(lèi)型是一組值的集合;數(shù)據(jù)類(lèi)型是指一種類(lèi)型以及定義在該種類(lèi)型上的一組操作;抽象數(shù)據(jù)類(lèi)型 (abstract data type，簡(jiǎn)稱(chēng)ADT)一般是指數(shù)據(jù)結(jié)構(gòu)作為某個(gè)軟件組件的實(shí)現(xiàn)。ADT的接口用一種類(lèi)型加上該種類(lèi)型上的一組操作定義，而每個(gè)操作又由它的輸入和輸出單獨(dú)定義。ADT并不關(guān)心數(shù)據(jù)類(lèi)型如何實(shí)現(xiàn)，實(shí)現(xiàn)細(xì)節(jié)對(duì)于ADT的用戶來(lái)說(shuō)通常是隱藏的，通過(guò)封裝來(lái)阻止外部對(duì)象對(duì)它的訪問(wèn)［3］。

數(shù)據(jù)結(jié)構(gòu)是ADT的實(shí)現(xiàn)。在C++這類(lèi)面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言中，ADT及其實(shí)現(xiàn)一起共同組成了類(lèi)。同ADT有關(guān)的每個(gè)操作全部由成員函數(shù)來(lái)實(shí)現(xiàn)。ADT與具體應(yīng)用無(wú)關(guān)，這樣可以讓程序員把精力更多地用在數(shù)據(jù)及其操作的理想模型上。

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

數(shù)據(jù)結(jié)構(gòu)的ADT的特性和模版類(lèi)的特點(diǎn)可以說(shuō)是相通的。模版類(lèi)對(duì)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)是應(yīng)運(yùn)而生，傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)在模版類(lèi)的描述下更是煥發(fā)出了新的生機(jī)與活力。

4 結(jié)語(yǔ)

動(dòng)態(tài)多態(tài)只需要一個(gè)函數(shù)，生成的可執(zhí)行代碼尺寸比較小，靜態(tài)多態(tài)必須要對(duì)不同的類(lèi)型生成不同的模板實(shí)體，尺寸要大一點(diǎn)，但是因?yàn)椴恍柰ㄟ^(guò)指針進(jìn)行間接操作，所以生成的代碼也會(huì)更快一點(diǎn)。靜態(tài)多態(tài)與動(dòng)態(tài)多態(tài)相比，因?yàn)槿拷壎òl(fā)生在編譯的時(shí)候，所也更加類(lèi)型安全。因?yàn)橄到y(tǒng)不允許將一個(gè)錯(cuò)誤類(lèi)型的對(duì)象插入到從一個(gè)模板類(lèi)實(shí)例化而來(lái)的容器中的。此外，動(dòng)態(tài)多態(tài)在處理異質(zhì)對(duì)象集合上就優(yōu)雅得多了，靜態(tài)多態(tài)卻可以實(shí)現(xiàn)安全、高效的同質(zhì)對(duì)象集合操作，并為C++帶來(lái)了泛型編程的概念。

數(shù)據(jù)結(jié)構(gòu)經(jīng)過(guò)幾十年的發(fā)展，于上個(gè)世紀(jì)成熟穩(wěn)定，許多算法早在20世紀(jì)六、七十年代已成型，不少算法思想早于計(jì)算機(jī)出現(xiàn)。多態(tài)算法思想的提出為古老的數(shù)據(jù)結(jié)構(gòu)注入了新的生機(jī)與活力，必將為計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展提供新的動(dòng)力。

［1］鄭莉，董淵，何江舟．C++語(yǔ)言程序設(shè)計(jì)［M］．4版．北京:清華大學(xué)出版社，2010．

［2］Mark Allen Weiss．?dāng)?shù)據(jù)結(jié)構(gòu)與算法分析C++描述［M］．3版．張懷勇，譯．北京:人民郵電出版社，2007．

［3］Clifford A．Shaffer．?dāng)?shù)據(jù)結(jié)構(gòu)與算法分析(C++版)［M］．2版．張銘，劉曉丹，譯．北京:電子工業(yè)出版社，2002．

［4］Malik D S．C++編程—數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)方法［M］．晏海華，蔡旭輝，常鴻，等譯．北京:電子工業(yè)出版社，2003．