多态及其在数据结构中的应用

胡传福

(东莞理工学院 计算机学院，广东东莞 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．