下载

    第1章 C + +程序设计

    大家好!现在我们将要开始一个穿越“数据结构、算法和程序”这个抽象世界的特殊旅程，以解决现实生活中的许多难题。在程序开发过程中通常需要做到如下两点：一是高效地描述数

    据；二是设计一个好的算法，该算法最终可用程序来实现。要想高效地描述数据，必须具备数

    据结构领域的专门知识；而要想设计一个好的算法，则需要算法设计领域的专门知识。

    在着手研究数据结构和算法设计方法之前，需要你能够熟练地运用 C + +编程并分析程序，这些基本的技能通常是从C + +课程以及其他分散的课程中学到的。本书的前两章旨在帮助你回

    顾一下这些技能，其中的许多内容你可能已经很熟悉了。

    本章我们将回顾C++ 的一些特性。因为不是针对C++ 新手，因此没有介绍诸如赋值语句、if 语句和循环语句(如for 和w h i l e)等基本结构，而是主要介绍一些可能已经被你忽略的 C + +

    特性：

    参数传递方式(如传值、引用和常量引用) 。

    函数返回方式(如返值、引用和常量引用) 。

    模板函数。

    递归函数。

    常量函数。

    内存分配和释放函数：n e w与d e l e t e。

    异常处理结构：t r y, c a t c h和t h r o w。

    类与模板类。

    类的共享成员、保护成员和私有成员。

    友元。

    操作符重载。

    本章中没有涉及的其他C + +特性将在后续章节中在需要的时候加以介绍。本章还给出了如

    下应用程序的代码：

    一维和二维数组的动态分配与释放。

    求解二次方程。

    生成n 个元素的所有排列方式。

    寻找n个元素中的最大值。

    此外，本章还给出了如何测试和调试程序的一些技巧。

    1.1 引言

    在检查程序的时候我们应该问一问：

    它正确吗？

    第一部分 预 备 知 识? 它容易读懂吗？

    它有完善的文档吗？

    它容易修改吗？

    它在运行时需要多大内存？

    它的运行时间有多长？

    它的通用性如何？能不能不加修改就可以用它来解决更大范围的问题？

    它可以在多种机器上编译和运行吗？或者说需要经过修改才能在不同的机器上运行吗？

    上述问题的相对重要性取决于具体的应用环境。比如，如果我们正在编写一个只需运行一

    次即可丢弃的程序，那么主要关心的应是程序的正确性、内存需求、运行时间以及能否在一台

    机器上编译和运行。不管具体的应用环境是什么，正确性总是程序的一个最重要的特性。一个

    不正确的程序，不管它有多快、有多么好的通用性、有多么完善的文档，都是毫无意义的(除

    非它变正确了) 。尽管我们无法详细地介绍提高程序正确性的技术，但可以为大家提供一些程

    序正确性的验证方法以及公认的一些良好的程序设计习惯，它们可以帮助你编写正确的代码。

    我们的目标是教会你如何开发正确的、精致的、高效的程序。

    1.2 函数与参数

    1.2.1 传值参数

    考察函数A b c(见程序1 - 1) 。该函数用来计算表达式 a+b+bc+ (a+b-c) (a+b) + 4，其中a，b

    和c 是整数，结果也是一个整数。

    程序1-1 计算一个整数表达式

    int Abc(int a, int b, int c)

    {

    return a+b+bc+(a+b-c)(a+b)+4;

    }

    在程序1 - 1中，a，b和c 是函数Abc 的形式参数(formal parameter) ，类型均为整型。如果

    在如下语句中调用函数A b c：

    z = Abc(2,x,y)

    那么，2，x 和y 分别是对应于a，b 和c 的实际参数(actual parameter) 。当A bc ( 2 ,x,y) 被执

    行时，a 被赋值为2；b 被赋值为x；c 被赋值为y。如果x 和 或y 不是int 类型，那么在把它们

    的值赋给b 和c 之前，将首先对它们进行类型转换。例如，如果x 是float 类型，其值为3 . 8，那

    么b 将被赋值为3。在程序1 - 1中，形式参数a，b 和c 都是传值参数(value parameter) 。

    运行时，与传值形式参数相对应的实际参数的值将在函数执行之前被复制给形式参数，复

    制过程是由该形式参数所属数据类型的复制构造函数( copy constructor)完成的。如果实际参

    数与形式参数的数据类型不同，必须进行类型转换，从实际参数的类型转换为形式参数的类型，当然，假定这样的类型转换是允许的。

    当函数运行结束时，形式参数所属数据类型的析构函数(d e s t r u c t o r)负责释放该形式参数。

    当一个函数返回时，形式参数的值不会被复制到对应的实际参数中。因此，函数调用不会修改

    实际参数的值。

    2 第一部分 预 备 知 识

    下载1.2.2 模板函数

    假定我们希望编写另外一个函数来计算与程序 1 - 1相同的表达式，不过这次a，b和c是f l o a t

    类型，结果也是f l o a t类型。程序1 - 2中给出了具体的代码。程序1 - 1和1 - 2的区别仅在于形式参数

    以及函数返回值的数据类型。

    程序1-2 计算一个浮点数表达式

    float Abc(float a, float b, float c)

    {

    return a+b+bc+(a+b-c)(a+b)+4;

    }

    实际上不必对每一种可能的形式参数的类型都重新编写一个相应的函数。可以编写一段通

    用的代码，将参数的数据类型作为一个变量，它的值由编译器来确定。程序 1 - 3中给出了这样

    一段使用t e m p l a t e语句编写的通用代码。

    程序1-3 利用模板函数计算一个表达式

    template

    T Abc(T a, T b, T c)

    {

    return a+b+bc+(a+b-c)(a+b)+4;

    }

    利用这段通用代码，通过把T替换为i n t，编译器可以立即构造出程序1 - 1，把T 替换为f l o a t

    又可以立即构造出程序1 - 2。事实上，通过把T替换为d o u b l e或l o n g，编译器又可以构造出函数

    A b c的双精度型版本和长整型版本。把函数 Abc 编写成模板函数可以让我们不必了解形式参数

    的数据类型。

    1.2.3 引用参数

    程序1 - 3中形式参数的用法会增加程序的运行开销。例如，我们来考察一下函数被调用以

    及返回时所涉及的操作。假定a，b 和c 是传值参数，在函数被调用时，类型T 的复制构造函数

    把相应的实际参数分别复制到形式参数a，b 和c 之中，以供函数使用；而在函数返回时，类型

    T的析构函数会被唤醒，以便释放形式参数a，b 和c。

    假定数据类型为用户自定义的 M a t r i x，那么它的复制构造函数将负责复制其所有元素，而析构函数则负责逐个释放每个元素(假定 Matrix 已经定义了操作符+，和 ) 。如果我们用

    具有1 0 0 0个元素的Matrix 作为实际参数来调用函数 A b c，那么复制三个实际参数给 a，b 和c

    将需要3 0 0 0次操作。当函数A b c返回时，其析构函数又需要花费额外的 3 0 0 0次操作来释放a，b和c。

    在程序1 - 4所示的代码中， a，b 和c 是引用参数( reference parameter) 。如果用语句

    A bc (x, y, z) 来调用函数A b c，其中x、y 和z 是相同的数据类型，那么这些实际参数将被分别赋

    予名称a，b 和c，因此，在函数Abc 执行期间，x、y 和z 被用来替换对应的a，b 和c。与传值参

    数的情况不同，在函数被调用时，本程序并没有复制实际参数的值，在函数返回时也没有调用

    析构函数。

    第1章 C ++程序设计 3 下载程序1-4 利用引用参数计算一个表达式

    template

    T Abc(T a, T b, T c)

    {

    return a+b+bc+(a+b-c)(a+b)+4;

    }

    我们可以考察一下当a，b 和c 所对应的实际参数x，y 和z 分别是具有1 0 0 0个元素的矩阵时

    的情形。由于不需要把x，y 和z 的值复制给对应的形式参数，因此我们可以节省采用传值参数

    进行参数复制时所需要的3 0 0 0次操作。

    1.2.4 常量引用参数

    C + +还提供了另外一种参数传递方式——常量引用( const reference) ，这种模式指出函数

    不得修改引用参数。例如，在程序1 - 4中，a，b 和c 的值不能被修改，因此我们可以重写这段

    代码，见程序1 - 5。

    程序1-5 利用常量引用参数计算一个表达式

    template

    T Abc(const T a, const T b, const T c)

    {

    return a+b+bc+(a+b-c)(a+b)+4;

    }

    使用关键字const 来指明函数不可以修改引用参数的值，这在软件工程方面具有重要的意

    义。这将立即告诉用户该函数并不会修改实际参数。

    对于诸如i n t、float 和char 的简单数据类型，当函数不会修改实际参数值的时候我们可以

    采用传值参数；对于所有其他的数据类型(包括模板类型) ，当函数不会修改实际参数值的时

    候可以采用常量引用参数。

    采用程序1 - 6的语法，我们可以得到程序1 - 5的一个更通用的版本。在新的版本中，每个形

    式参数可能属于不同的数据类型，函数返回值的类型与第一个参数的类型相同。

    程序1-6 程序1 - 5的一个更通用的版本

    template

    Ta Abc (const Ta a, const Tb b, const Tc c)

    {

    return a+b+bc+(a+b-c)(a+b)+4;

    }

    1.2.5 返回值

    函数可以返回值，引用或常量引用。在前面的例子中，函数 Abc 返回的都是一个具体值，在这种情况下，被返回的对象均被复制到调用(或返回)环境中。对于函数 Abc 的所有版本来

    说，这种复制过程都是必要的，因为函数所计算出的表达式的结果被存储在一个局部临时变量

    中，当函数返回时，这个临时变量(以及所有其他的临时变量和传值形式参数)所占用的空间

    4 第一部分 预 备 知 识

    下载将被释放，其值当然也不再有效。为了避免丢失这个值，在释放临时变量以及传值形式参数的

    空间之前，必须把这个值从临时变量复制到调用该函数的环境中去。

    如果需要返回一个引用，可以为返回类型添加一个前缀。如：

    T X(int i, T z)

    定义了一个函数X，它返回一个引用参数Z。可以使用下面的语句返回z：

    return z；

    这种返回形式不会把z 的值复制到返回环境中。当函数X返回时，传值形式参数i 以及所有局部

    变量所占用的空间都将被释放。由于z 是对一个实际参数的引用，因此，它不会受影响。

    如果在函数名之前添加关键字c o n s t，那么函数将返回一个常量引用，例如：

    const T X (int i, T z)

    除了返回的结果是一个不变化的对象之外，返回一个常量引用与返回一个引用是相同的。

    1.2.6 递归函数

    递归函数(recursive function)是一个自己调用自己的函数。递归函数包括两种：直接递

    归(direct recursion)和间接递归(indirect recursion) 。直接递归是指函数F的代码中直接包含

    了调用F的语句，而间接递归是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又

    被调用。在深入探讨C + +递归函数之前，我们来考察一下来自数学的两个相关概念——数学函

    数的递归定义以及归纳证明。

    在数学中经常用一个函数本身来定义该函数。例如阶乘函数f (n) =n!的定义如下：

    其中n 为整数。

    从该定义中可以看到，当n 小于或等于1时，f (n)的值为1，如 f (-3) = f (0) = f (1) =1。当n

    大于1时，f (n)由递归形式来定义，在定义的右侧也出现了 f 。在右侧使用f 并不会导致循环定

    义，因为右侧f 的参数小于左侧f 的参数。例如，从公式(1 - 1)中可以得到f ( 2 ) = 2f ( 1 )，由于我

    们已经知道f ( 1 ) = 1，因此 f ( 2 ) = 2 1 = 2。以此类推，f ( 3 ) = 3f ( 2 ) = 3 2 = 6。

    对于函数f (n) 的一个递归定义(假定是直接递归) ，要想使它成为一个完整的定义，必须

    满足如下条件：

    定义中必须包含一个基本部分(b a s e) ，其中对于n 的一个或多个值，f (n)必须是直接定

    义的(即非递归) 。为简单起见，我们假定基本部分包含了n≤k 的情况，其中k 为常数。 (在基

    本部分中指定n≥k 的情形也是可能的，但较少见。 )

    在递归部分(recursive component)中，右侧所出现的所有f 的参数都必须有一个比n 小，以便重复运用递归部分来改变右侧出现的f ，直至出现f 的基本部分。

    在公式(1 - 1)中，基本部分是：当n≤1时f (n) = 1；递归部分是f (n) = nf (n- 1 )，其中右侧f

    的参数为n- 1，比n 要小。重复应用递归部分可把f (n- 1 )变换成对f (n- 2 )，f (n- 3 )，…，直到f ( 1 )

    的调用。例如：

    f (5) = 5f (4) = 20 f (3) = 60 f (2) = 120f ( 1 )

    注意每次应用递归部分的结果是更趋近于基本部分，最后，根据基本部分的定义可以得到

    f (5) = 120。从这个例子中可以看出，对于n≥1有 f (n) = n (n-1) (n- 2 )…1。

    作为递归定义的另外一个例子，我们来考察一下斐波那契数列的定义：

    第1章 C ++程序设计 5 下载

    (1 - 1)F0

    = 0，F1

    = 1，Fn

    =Fn - 1

    +Fn -2

    (n> 1) (1 - 2)

    在这个定义中，F0

    = 0和F1

    =1 构成了定义的基本部分，Fn

    =Fn - 1

    +Fn -2

    是定义的递归部分。右

    侧函数的参数都小于n。为使公式(1 - 2)成为F 的一个完整的递归定义，对于任何 n> 1的斐波

    那契数，对递归部分的重复应用应能把右侧出现的所有F 变换成基本部分的形式。因为对一个

    n> 1的整数重复减去 1或2会得到0或1，因此右侧F 的出现总可以被变换成基本定义。比如，F4

    =F3

    +F2

    =F2

    +F1

    +F1

    +F0

    = 3F1

    + 2F0

    = 3。

    现在我们把注意力转向与计算机递归函数相关的第二个概念——归纳证明。在归纳证明中，可以按照如下步骤来证明一个命题的正确性，比如证明如下公式：

    首先我们可以验证，对于n 的一个或多个基本的值(如n = 0或n = 0 , 1)该公式是成立的；然

    后假定当n? ( 0 ~m)时公式是成立的，其中m 是一个任意整数(大于等于验证时所取的最大值) ，如果能够证明对于n 的下一个值(如m+ 1)公式也是成立的，那么就可以确定该公式是成立的。

    这种证明方法可以归纳为三个部分——归纳初值( induction base) ，归纳假设( i n d u c t i o n

    h y p o t h e s i s)和归纳步证明(induction step) 。

    下面通过对n 进行归纳来证明公式(1 - 3) 。在归纳初值部分，取n= 0来进行验证，由于公

    式的左边 0

    i =1

    i= 0，公式的右边也为0，所以当n= 0时公式(1 - 3)是成立的。在归纳假设部分假

    定当n≤m 时公式是成立的，其中m 是任意大于等于0的整数(对于接下来的归纳证明，只需假

    定n = m 时公式是成立的即可) 。在归纳证明中需要证明当n =m+1 时公式(1 - 3)是成立的。对

    于n=m+ 1，公式左边为 m+1

    i =1

    i=m+ 1+

    m

    i =1

    i，从归纳假设中可以知道

    m

    t=1

    i=m (m+ 1 ) 2，所以当n =m+ 1

    时左边变成m+ 1 +m (m+1)2 =(m+1) (m+ 2 ) 2，正好与公式右边相等。

    乍看起来，归纳证明好象是一个循环证明——因为我们建立了一个假设为正确的结论。不

    过，归纳证明并不是循环证明，就像递归定义并不是循环定义一样。每个正确的归纳证明都会

    有一个基本值验证部分，它与递归定义的基本部分相类似，在归纳证明时我们利用了比 n 值小

    时结论的正确性来证明取值为n 时结论的正确性。重复应用归纳证明，可以减少对基本值验证

    的应用。

    C + +允许我们编写递归函数。一个正确的递归函数必须包含一个基本部分。函数中递归调

    用部分所使用的参数值应比函数的参数值要小，以便函数的重复调用能最终获得基本部分所提

    供的值。

    例1-1 [阶乘] 程序1 - 7给出了一个利用公式(1 - 1)计算n! 的C + +函数。函数的基本部分包含了

    n≤1的情形。考虑调用F a c t o r i a l ( 2 )。为了计算e l s e语句中的2 Factorial(1)，需要挂起F a c t o r i a l ( 2 )，然后进入调用F a c t o r i a l ( 1 )。当Factorial(2) 被挂起时，程序的状态(如局部变量、传值形式参数

    的值、引用形式参数的值以及代码的执行位置等)被保留在递归栈中，在执行完 F a c t o r i a l ( 1 )时

    这些程序状态又立即恢复。调用Factorial(1) 所得到的返回值为1，之后，F a c t o r i a l ( 2 )恢复运行，计算表达式2 1，并将结果返回。

    程序1-7 计算n!的递归函数

    int Factorial (int n)

    { 计算n!

    6 第一部分 预 备 知 识

    下载

    (1 - 3)if (n<=1) return 1;

    else return n Factorial(n- 1 ) ;

    }

    在计算F a c t o r i a l ( 3 )时，当到达e l s e语句时，计算过程被挂起以便先计算出 F a c t o r i a l ( 2 )。我

    们已经看到F a c t o r i a l ( 2 )是怎样获得最终结果2的。当F a c t o r i a l ( 2 )返回时，F a c t o r i a l ( 3 )继续运行，计算出最后的结果3 2。

    鉴于程序1 - 7的代码与公式(1 - 1)的相似性，该程序的正确性与公式(1 - 1)的正确性是等

    价的。

    例1-2 模板函数S u m (见程序1-8) 统计元素a [ 0 ]至a[n-1] 的和(简记为a [ 0 : n - 1 ]) 。从代码中我们

    可以得到这样的递归公式：当n = 0时，和为0；当n > 0时，n个元素的和是前面n - 1个元素的和加

    上最后一个元素。见程序1 - 9。

    程序1-8 累加a [ 0：n - 1 ]

    template

    T Sum(T a[], int n)

    { 计算a[0: n-1]的和

    T tsum=0;

    f or (int i = 0; i < n; i++)

    tsum += a[i];

    return tsum;

    }

    程序1-9 递归计算a [ 0：n - 1 ]

    template

    T Rsum(T a[], int n)

    { 计算a[0: n-1]的和

    if (n > 0)

    return Rsum(a, n-1) + a[n-1];

    return 0;

    }

    例1-3 [排列] 通常我们希望检查n 个不同元素的所有排列方式以确定一个最佳的排列。比如，a，b 和c 的排列方式有：a b c, a c b, b a c, b c a, cab 和c b a。n 个元素的排列方式共有n ! 种。

    由于采用非递归的C + +函数来输出n 个元素的所有排列方式很困难，所以可以开发一个递

    归函数来实现。令E= {e1

    , ..., en

    }表示n 个元素的集合，我们的目标是生成该集合的所有排列方

    式。令Ei

    为E中移去元素i 以后所获得的集合，perm (X) 表示集合X 中元素的排列方式，ei

    . p e r m

    (X)表示在perm (X) 中的每个排列方式的前面均加上 ei

    以后所得到的排列方式。例如，如果

    E= {a, b, c}，那么E1

    = {b, c}，perm (E1) = (b c, c b)，e1

    .perm (E1) = (a b c, a c b)。

    对于递归的基本部分，采用 n = 1。当只有一个元素时，只可能产生一种排列方式，所以

    perm (E) = ( e)，其中e 是E 中的唯一元素。当 n > 1时，perm (E) = e1

    .perm (E1) +e2

    .p e r m

    (E2) +e3

    .perm (E3) +…+en

    .perm (En)。这种递归定义形式是采用n 个perm (X) 来定义perm (E), 其

    中每个X 包含n- 1个元素。至此，一个完整的递归定义所需要的基本部分和递归部分都已完成。

    第1章 C ++程序设计 7 下载当n= 3并且E=(a, b, c)时，按照前面的递归定义可得perm (E) =a.perm ( {b, c} ) +b.perm ( {a,c} ) +c.perm ( {a, b} )。同样，按照递归定义有 perm ( {b, c} ) =b.perm ( {c} ) +c.perm ( {b}), 所以

    a.perm ( {b, c} ) = ab.perm ( {c} ) + ac.perm ( {b}) = a b . c + ac.b = (a b c, a c b)。同理可得

    b.perm ( {a, c}) = ba.perm ( {c}) + bc.perm ( {a}) = b a . c + b c . a = (b a c, b c a)，c.perm ( {a, b}) =

    ca.perm ( {b}) + cb.perm ( {a}) = c a . b + c b . a = (c a b, c b a)。所以perm (E) = (a b c, a c b, b a c, b c a,c a b, c b a)。

    注意a.perm ( {b, c} )实际上包含两个排列方式：abc 和a c b，a 是它们的前缀，perm ( {b, c} )

    是它们的后缀。同样地，ac.perm ( {b}) 表示前缀为a c、后缀为perm ( {b}) 的排列方式。

    程序1 - 1 0把上述perm (E) 的递归定义转变成一个C++ 函数，这段代码输出所有前缀为l i s t [ 0：

    k-1], 后缀为l i s t [ k：m] 的排列方式。调用Perm(list, 0, n-1) 将得到list[0: n-1] 的所有n! 个排列方

    式，在该调用中，k=0, m= n - 1，因此排列方式的前缀为空，后缀为list[0: n-1] 产生的所有排列

    方式。当k =m 时，仅有一个后缀l i s t [ m ]，因此list[0: m] 即是所要产生的输出。当k
    用list[k] 与l i s t [ k：m] 中的每个元素进行交换，然后产生list[k+1: m] 的所有排列方式，并用它

    作为list[0: k] 的后缀。S w a p是一个inline 函数，它被用来交换两个变量的值，其定义见程序1 -

    11。P e r m的正确性可用归纳法来证明。

    程序1-10 使用递归函数生成排列

    template

    void Perm(T list[], int k, int m)

    { 生成list [k：m ]的所有排列方式

    int i;

    if (k == m) {输出一个排列方式

    for (i = 0; i <= m; i++)

    cout << list [i];

    cout << endl;

    }

    else list[k：m ]有多个排列方式

    递归地产生这些排列方式

    for (i=k; i <= m; i++) {

    Swap (list[k], list[i]);

    Perm (list, k+1, m);

    Swap (list [k], list [i]);

    }

    }

    程序1 - 11 交换两个值

    template

    inline void Swap(T a, T b)

    { 交换a和b

    T temp = a; a = b; b = temp;

    }

    练习

    1. 试编写一个模板函数I n p u t，它要求用户输入一个非负数，并负责验证用户所输入的数是

    8 第一部分 预 备 知 识

    下载否真的大于或等于0，如果不是，它将告诉用户该输入非法，需要重新输入一个数。在函数非

    成功退出之前，应给用户三次机会。如果输入成功，函数应当把所输入的数作为引用参数返回。

    输入成功时，函数应返回true, 否则返回f a l s e。上机测试该函数。

    2. 试编写一个模板函数，用来测试数组a中的元素是否按升序排列(即a [ i ]≤a [ i + 1 ] ,其中0≤

    i
    3. 试编写一个非递归函数来计算n!，并上机测试函数的正确性。

    4. 1) 试编写一个计算斐波那契数列Fn

    的递归函数，并上机测试其正确性。

    2) 试说明对于任何n> 2的整数，调用1)中的函数计算Fn

    时，同一个Fi

    会被处理至少一次。

    3) 试编写一个非递归的函数来计算斐波那契数列Fn

    ，该函数应能直接计算出每个斐波那

    契数。上机测试代码的正确性。

    5. 试编写一个递归函数，用来输出n 个元素的所有子集。例如，三个元素{a, b, c} 的所有

    子集是：{ }(空集) ，{a}, {b}, {c}, {a, b}, {a, c}, {b, c} 和{a, b, c}。

    6. 试编写一个递归函数来确定元素x 是否属于数组a[ 0：n- 1 ]。

    1.3 动态存储分配

    1.3.1 操作符n e w

    C + +操作符n e w可用来进行动态存储分配，该操作符返回一个指向所分配空间的指针。例

    如，为了给一个整数动态分配存储空间，可以使用下面的语句来说明一个整型指针变量：

    int y；

    当程序需要使用该整数时，可以使用如下语法来为它分配存储空间：

    y = new int;

    操作符n e w分配了一块能存储一个整数的空间，并将指向该空间的指针返回给 y，y是对整数指

    针的引用，而 y则是对整数本身的引用。为了在刚分配的空间中存储一个整数值，比如 1 0，可

    以使用如下语法：

    y = 10;

    我们可以把上述三步(说明y, 分配存储空间，为y 赋值)进行适当的合并，如下例所示：

    int y = new int;

    y = 10;

    或

    int y = new int (10);

    或

    int y;

    y = new int (10);

    1.3.2 一维数组

    在本书的许多示例程序中都使用了一维或二维数组，这些数组的大小在编译时可能是未知

    的，事实上，它们可能随着函数调用的变化而变化。因此，对于这些数组必须进行动态存储

    分配。

    为了在运行时创建一个一维浮点数组x，首先必须把x说明成一个指向f l o a t的指针，然后为

    数组分配足够的空间。例如，一个大小为n 的一维浮点数组可以按如下方式来创建：

    float x = new float [n];

    第1章 C ++程序设计 9 下载操作符n e w分配n 个浮点数所需要的空间，并返回指向第一个浮点数的指针。可以使用如下语

    法来访问每个数组元素：x[0], x[1], ..., x[n-1]。

    1.3.3 异常处理

    在执行语句

    float x = new float [n];

    时，如果计算机不能分配足够的空间怎么办？在这种情况下， new 不能够分配所需数量的存储

    空间，将会引发一个异常(e x c e p t i o n) 。在Borland C++中，当new 不能分配足够的空间时，它

    会引发(t h r o w)一个异常xalloc (在except.h 中定义)。可以采用try - catch 结构来捕获(c a t c h)

    new 所引发的异常：

    float x;

    try {x = new float [n];}

    catch (xalloc) { 仅当new 失败时才会进入

    cerr << Out of Memory << endl;

    e x i t ( 1 ) ; }

    当一个异常出现时，程序进入与该异常相对应的c a t c h语句块中执行。在上面的例子中，只

    有在执行try 语句时产生了xalloc 异常，才会进入catch (xalloc) 语句块，由语句exit (1) 终止程

    序的运行。 (exit 在stdlib.h 中定义。 )

    在C++ 程序中处理错误条件的常用方法就是每当检测到这样的条件时就引发一个异常。当

    一个异常被引发时，必须指明它的类型(如前面的x a l l o c) 。我们把可能会产生异常的程序代码

    放入try 块中，在try 块之后放上一个或多个catch 块，每个catch 块用来处理一个特定类型的异

    常。例如catch (xalloc) 块仅处理xalloc 异常。语法catch (...) 定义了一个能捕获所有异常的c a t c h

    块。当一个异常被引发时，检查在程序执行过程中所遇到的最接近的 try-catch 代码，如果其中

    的一个catch 块能够处理所产生的异常，程序将从这个catch 块中继续执行，否则，继续检查直

    到找到与异常相匹配的块。如果找不到能处理该异常的 c a t c h块，程序将显示信息“A b n o r m a l

    program termination(异常程序终结) ”并终止运行。如果一个try 块没有引发异常，程序的执

    行将越过与该t r y块相对应的c a t c h块。

    1.3.4 操作符d e l e t e

    动态分配的存储空间不再需要时应该被释放， 所释放的空间可重新用来动态创建新的结构。

    可以使用C + +操作符d e l e t e来释放由操作符n e w所分配的空间。下面的语句可以释放分配给 y的

    空间以及一维数组x：

    delete y;

    delete [ ] x;

    1.3.5 二维数组

    虽然C + +提供了多种机制用来说明二维数组，但其中的多数机制都要求在编译时明确地知

    道每一维的大小。而且，在使用这些机制时，很难编写出一个允许形式参数是一个第二维大小

    未知的二维数组的函数。之所以如此，是因为当形式参数是一个二维数组时，必须指定其第二

    维的大小。例如，a[ ][10]是一个合法的形式参数，而a[ ][ ] 不是。

    克服这种限制的一条有效途径就是对于所有的二维数组使用动态存储分配。本书从头至尾

    1 0 第一部分 预 备 知 识

    下载使用的都是动态分配的二维数组。

    当一个二维数组每一维的大小在编译时都是已知时，可以采用类似于创建一维数组的语法

    来创建二维数组。例如，一个类型为c h a r的7×5数组可用如下语法来定义：

    char c[7][5];

    如果在编译时至少有一维是未知的，必须在运行时使用操作符 n e w来创建该数组。一个二

    维字符型数组，假定在编译时已知其列数为5，可采用如下语法来分配存储空间：

    char (c)[5];

    try { c = new char [n][5];}

    catch (xalloc) {仅当n e w失败时才会进入

    cerr << Out of Memory << endl;

    exit (1);}

    在运行时，数组的行数n要么通过计算来确定，要么由用户来指定。如果在编译时数组的

    列数也是未知的，那么不可能调用一次 n e w就能创建该数组(即使数组的行数是已知的) 。构

    造二维数组时，可以把它看成是由若干行组合起来的，每一行都是一个一维数组，可以按照前

    面讨论的方式用n e w来创建，指向每一行的指针可以保存在另外一个一维数组之中。图 1 - 1给出

    了建立一个3×5数组所需要的结构。

    x[0], x[1], x[2]分别指向第0行，第1行和第2行的第一个元素。所以，如果x是一个字符数组，那么x [ 0 : 2 ]是指向字符的指针，而x本身是一个指向指针的指针。可用如下语法来说明x :

    char x;

    为了创建如图1 - 1所示的存储结构，可以使用程序1 - 1 2中的代码，该程序创建一个类型为T

    的二维数组，这个数组有r o w s行和c o l s列。程序首先为指针x [ 0 ] , . . , x [ r o w s - 1 ]申请空间，然后为

    数组的每一行申请空间。在程序中操作符 n e w被调用了r o w s + 1次。如果n e w的某一次调用引发

    了一个异常，程序控制将转移到c a t c h块中，并返回f a l s e。如果没有出现异常，数组将被成功创

    建，函数M a k e 2 D A r r a y返回t r u e。对于所创建的数组x中的元素，可以使用标准的用法来引用，如x [ i ] [ j ] ,其中0≤i
    图1-1 一个3×5数组的存储结构

    程序1-12 为一个二维数组分配存储空间

    template

    bool Make2DArray ( T x, int rows, int cols)

    { 创建一个二维数组

    t r y {

    创建行指针

    x = new T [rows];

    为每一行分配空间

    第1章 C ++程序设计 1 1 下载for (int i = 0 ; i < rows; i++)

    x[i] = new int [cols];

    return true;

    }

    catch (xalloc) {return false;}

    }

    在程序1 - 1 2中，函数通过返回布尔值false 把n e w所产生的异常(如果有的话)告诉调用者。

    当然，M a k e 2 D A r r a y失败时也可以什么都不做，这样也能使调用者知道产生了异常。如果使用

    程序1 - 1 3中的代码，调用者可以捕获由n e w所产生的任何异常。

    程序1-13 创建一个二维数组但不处理异常

    template

    void Make2DArray( T x, int rows, int cols)

    { 创建一个二维数组

    不捕获异常

    创建行指针

    x = new T [rows];

    为每一行分配空间

    for (int i = 0 ; i
    x[i] = new int [cols];

    }

    当M a k e 2 D A r r a y按程序1 - 1 3定义时，可以使用如下代码来确定存储分配是否成功：

    try { Make2DArray (x, r, c);}

    catch (xalloc) {cerr<< Could bot create x << endl;

    e x i t ( 1 ) ; }

    在M a k e 2 D A r r a y中不捕获异常不仅简化了函数的代码设计，而且可以使用户在一个更合适

    的地方捕获异常，以便更好地报告出错误的明确含义或进行错误恢复。

    可以按如下两步来释放程序1 - 1 2中为二维数组所分配的空间。首先释放在f o r循环中为每一

    行所分配的空间，然后释放为行指针所分配的空间，具体实现见程序 1 - 1 4。注意在程序1 - 1 4中

    x被置为0，以便阻止用户继续访问已被释放的空间。

    程序1-14 释放由M a k e 2 D A r r a y所分配的空间

    template

    void Delete2DArray( T x, int rows)

    { 删除二维数组x

    释放为每一行所分配的空间

    for (int i = 0 ; i < rows ; i++)

    delete [ ] x[i];

    删除行指针

    delete [] x;

    x = 0;

    }

    1 2 第一部分 预 备 知 识

    下载练习

    7. 假定用一维数组 a [ 0：s i z e - 1 ]来存储一组元素。如果有 n个元素，可以把它们存储在

    a [ 0 ] , . . , a [ n - 1 ]中。当n超过s i z e时，数组将不足以存储所有元素，必须分配一个更大的数组。类

    似地，如果元素的数目比s i z e小很多，我们又可能希望减少数组的大小，以便释放出多余的空

    间为其他地方所用。试编写一个模板函数C h a n g e S i z e 1 D把数组a的大小从s i z e变成To S i z e。函数

    首先应该分配一个新的、大小为To S i z e的数组，然后把原数组a中的n个元素复制到新数组a中，最后释放原数组a所占用的空间。上机测试该函数。

    8. 试编写一个函数ChangeSize2D 来改变一个二维数组的大小(见练习7) 。上机测试该函数。

    1.4 类

    1.4.1 类C u r r e n c y

    C + +语言支持诸如i n t , f l o a t和c h a r之类的数据类型，在本书所提供的许多应用中还使用了

    C + +语言不直接支持的数据类型。用C + +来定义自有数据类型最灵活的方式就是使用类(c l a s s)

    结构。假定你想处理类型C u r r e n c y的对象，其实例拥有三个成员：符号(+或-) ，美元和美

    分。举两个例子，如2.35 (符号是+，2美元，3 5美分)和- 6 . 0 5 (符号是-，6美元，5美分)。对

    这种类型的对象我们想要执行的操作如下：

    1) 设置成员的值。

    2) 确定各成员的值(如指出符号，美元数目和美分数目) 。

    3) 增加两种货币类型。

    4) 增加成员的值。

    5) 输出。

    假定用无符号长整型变量d o l l a r s、无符号整型变量c e n t s和s i g n类型的变量s g n来描述货币对

    象，其中s i g n类型的定义如下：

    enum sign { plus, minus};

    可以使用程序1 - 1 5中的语法来定义C + +类C u r r e n c y。第一行简单地说明一个名为C u r r e n c y的类，然后在一对括号({ })之间给出类描述。类描述被分成两个部分： public 和p r i v a t e。public 部

    分用于定义一些函数(又称方法) ，这些函数可对C u r r e n c y类对象(或实例)进行操作，它们

    对于C u r r e n c y类的用户是可见的，是用户与C u r r e n c y对象进行交互的唯一手段。p r i v a t e部分用

    于定义函数和数据成员(如简单变量，数组及其他可赋值的结构) ，这些函数和数据成员对于

    用户来说是不可见的。借助于 p u b l i c部分和p r i v a t e部分，我们可以使用户只看到他(或她)需

    要看到的部分，同时把其余信息隐藏起来。尽管 C + +语法允许在p u b l i c部分定义数据成员，但

    在软件工程实践中不鼓励这种做法。

    程序1-15 定义C u r r e n c y类

    class Currency {

    p u b l i c :

    构造函数

    Currency(sign s = plus, unsigned long d = 0, unsigned int c = 0);

    析构函数

    第1章 C ++程序设计 1 3 下载~Currency {}

    bool Set(sign s, unsigned long d, unsigned int c);

    bool Set(float a);

    sign Sign const {return sgn;}

    unsigned long Dollars const {return dollars;}

    unsigned int Cents const {return cents;}

    Currency Add(const Currency x) const;

    Currency Increment(const Currency x);

    void Output const;

    p r i v a t e :

    sign sgn;

    unsigned long dollars;

    unsigned int cents;

    } ;

    p u b l i c部分的第一个函数与C u r r e n c y类同名，这种函数称之为构造函数。构造函数指明如

    何创建一个给定类型的对象，它不可以有返回值。在本例中，构造函数有三个参数，其缺省值

    分别是plus, 0和0，构造函数的具体实现在本节稍后给出。在创建一个C u r r e n c y类对象时，构造

    函数被自动唤醒。可以采用如下两种方式来创建C u r r e n c y类对象：

    Currency f, g (plus, 3,45), h (minus, 10);

    Currency m = new Currency ( plus, 8, 12);

    第一行定义了三个C u r r e n c y类变量(f，g 和h) ，其中f 被初始化为缺省值plus, 0和0，而g被初

    始化为 3 . 4 5，h 被初始化为- 1 0 . 0 0。注意初始值从左至右分别对应构造函数的每个参数。如

    果初始值的个数少于构造函数参数的个数，剩下的参数将取缺省值。在第二行， m被定义为指

    向一个C u r r e n c y对象的指针。我们调用n e w函数来创建一个C u r r e n c y对象，并把对象的指针存

    储在m中。所创建的对象被初始化为 8 . 1 2。

    下一个函数为~ C u r r e n c y，与类名相比多了一个前缀(~) ，这个函数被称为析构函数。每

    当一个C u r r e n c y对象超出作用域时将自动调用析构函数。这个函数用来删除对象。在本例中析

    构函数被定义为空函数({ }) 。对于其他类，由于类的构造函数可能会创建一些动态数组，那

    么当对象超出作用域时，析构函数需要释放这些空间。与构造函数一样，析构函数也不可以有

    返回值。

    接下来的两个函数允许用户为C u r r e n c y类成员赋值。其中第一个函数要求用户提供三个参

    数，而第二个函数需要一个浮点数作为参数。如果成功，两个函数均返回 true, 否则返回f a l s e。

    这两个函数的具体实现在本节稍后给出。请注意，这两个函数具有相同的名字，但编译器和用

    户都很容易区分它们，因为它们具有不同的参数集合。 C + +允许函数名的重用，只要它们的参

    数表不同。还需要注意的是，没有指定欲赋值(符号，美元，美分)对象的名称，这是因为调

    用类成员函数的语法如下：

    g . S e t ( m i n u s , 3 3 , 0 ) ;

    h . S e t ( 2 0 . 5 2 ) ;

    其中g 和h 是Currency 类变量。在第一个句子中，g 是唤醒Set 的对象，而在第二个句子中h是

    唤醒Set 的对象。在为函数S e t编写代码时，我们有办法访问调用本函数的对象，因此，不需要

    把对象的名称放入参数表中。

    函数S i g n，D o l l a r s和C e n t s返回对象的相应数据成员，关键字 c o n s t指出这些函数不会修改

    数据成员。我们把这种类型的函数称之为常元函数(constant function) 。

    1 4 第一部分 预 备 知 识

    下载函数S u m把当前对象的货币数量与对象x的货币数量相加，然后返回所得结果，因此A d d函

    数不会修改当前对象，是一个常元函数。函数 I n c r e m e n t把对象x 的货币数量添加到当前对象

    上，这个函数修改了当前对象，因此不是一个常元函数。最后一个函数是 O u t p u t，它显示当前

    对象的货币数量。函数Output 不会修改当前对象，因此是一个常元函数。

    尽管A d d和I n c r e m e n t都返回C u r r e n c y类对象，但A d d返回的是值，而I n c r e m e n t返回的是引

    用。如1 . 2 . 5节所提到的，返回值和返回引用分别与传值参数和引用参数有相同的作用。在返回

    一个值的情况下，返回的对象被复制到所返回的环境，而返回引用则避免了这种复制，在返回

    的环境中可以直接使用该对象。返回引用比返回值要快，因为省去了复制过程。从 A d d的代码

    中可以看出，它返回了一个局部对象，在函数终止时该对象将被删除，因此， r e t u r n语句必须

    复制该对象。而I n c r e m e n t返回的是一个全局对象，因而不需要复制。

    复制构造函数被用来执行返回值的复制及传值参数的复制。程序 1 - 1 5中没有给出复制构造

    函数，所以C + +将使用缺省的复制构造函数，它仅可进行数据成员的复制。对于类 C u r r e n c y来

    说，使用省缺的复制构造函数已经足够。后面还将看到许多类，对于这些类缺省的复制构造函

    数已难以胜任它们的复制工作。

    在p r i v a t e部分，定义了三个数据成员，它们对于一个 C u r r e n c y对象来说是必须的。每一个

    C u r r e n c y对象都拥有自己的这三个数据成员。

    由于在类定义的内部没有给出函数的具体实现，因此必须在其他地方给出。在具体实现时，必须在每个函数名的前面加上 C u r r e n c y： ： ，以指明该函数是 C u r r e n c y类的成员函数。所以

    C u r r e n c y： ：C u r r e n c y表示该函数是C u r r e n c y类的构造函数，而C u r r e n c y： ：O u t p u t表示该函数是

    C u r r e n c y类的O u t p u t函数。程序1 - 1 6给出了C u r r e n c y类的构造函数。

    程序1-16 Currency类的构造函数

    Currency::Currency(sign s, unsigned long d, unsigned int c)

    { 创建一个C u r r e n c y对象

    if(c > 99)

    { 美分数目过多

    cerr << Cents should be < 100 << endl;

    e x i t ( 1 ) ; }

    sgn = s; dollars = d; cents = c;

    }

    构造函数在初始化当前对象的 sgn, dollars 和cents 数据成员之前需要验证参数的合法性。

    如果参数值出现错误，构造函数将输出一个错误信息，然后调用函数 e x i t ( )终止程序的运行。

    在本例中，仅需要验证c 的值。

    程序1 - 1 7给出了两个S e t函数的代码。第一个函数首先验证参数的合法性，如果参数合法，则用它们来设置p r i v a t e成员变量。第二个函数不执行参数合法性验证，它仅使用小数点后面的

    头两个数字。形如d1

    .d2

    d3

    的数可能没有一个精确的计算机表示，例如，用计算机所描述的数

    5 . 2 9实际上要比真正的5 . 2 9稍微小一点。当用如下语句

    cents = (a - dollars) 100

    抽取cents 成员时，这种描述方法可能会带来一个错误，因为 (a - dollars) 100稍微小于2 9，当程序把(a - dollars) 100转换成一个整数时，c e n t s得到的将是2 8而不是2 9。只要d1

    .d2

    d3

    的计

    算机表示与实际值相比不少于0 . 0 0 1或不多于0 . 0 0 9，就可以采用为a 加上0 . 0 0 1来解决我们的问

    第1章 C ++程序设计 1 5 下载题。例如，如果5 . 2 9的计算机表示是5 . 2 8 9 9 9，那么加上0 . 0 0 1将得到5 . 2 9 0 9 9 ,由此所计算出的

    c e n t s就是2 9。

    程序1-17 设置p r i v a t e数据成员

    bool Currency::Set(sign s, unsigned long d, unsigned int c)

    { 取值

    if (c > 99) return false;

    sgn = s; dollars = d; cents = c;

    return true;

    }

    bool Currency::Set(float a)

    { 取值

    if (a < 0) {sgn = minus; a = -a;}

    else sgn = plus;

    dollars = a; 抽取整数部分

    获取两个小数位

    cents = (a + 0.005 - dollars) 100;

    return true;

    }

    程序1 - 1 8给出了函数A d d的代码，该函数首先把要累加的两个货币数量转换成整数，如

    2.32 变成整数2 3 2，- 4 . 7 5变成整数-4 7 5。请注意引用当前对象的数据成员与引用参数 x的

    数据成员在语法上有所区别。x . d o l l a r s指定x 的数据成员dollars ，而当前对象使用d o l l a r s时可

    以直接引用d o l l a r s而不必在它的前面加上对象名。当函数 A d d终止时，局部变量a 1 , a 2 , a 3和a n s

    被l o n g数据类型的析构函数删除，这些变量所占用的空间也将被释放。由于 C u r r e n c y对象a n s将

    被作为调用结果返回，因此必须把它复制到调用者的环境中，所以A d d返回的是值。

    程序1-18 累加两个C u r r e n c y

    Currency Currency::Add(const Currency x) const

    { 把 x累加到 t h i s .

    long a1, a2, a3;

    Currency ans;

    把当前对象转换成带符号的整数

    a1 = dollars 100 + cents;

    if (sgn == minus) a1 = -a1;

    把x转换成带符号的整数

    a2 = x.dollars 100 + x.cents;

    if (x.sgn == minus) a2 = -a 2 ;

    a3 = a1 + a2;

    转换成 currency 形式

    if (a3 < 0) {ans.sgn = minus; a3 = -a 3 ; }

    else ans.sgn = plus;

    ans.dollars = a3 100;

    1 6 第一部分 预 备 知 识

    下载ans.cents = a3 - ans.dollars 100;

    return ans;

    }

    程序1 - 1 9给出了函数I n c r e m e n t和O u t p u t的代码。在C + +中，保留关键字t h i s用于指向当前对

    象，this 代表对象本身。看一下调用g . I n c r e m e n t ( h )。函数I n c r e m e n t的第一行调用了p u b l i c成员

    函数A d d，它把x (这里是h) 加到当前对象上(这里是 g) ，所得结果被返回，并被赋给 t h i s， t h i s就是当前对象。由于该对象不是函数I n c r e m e n t的局部对象，因此当函数结束时，该对象不

    会自动被删除。所以可以返回一个引用。

    程序1-19 Increment与O u t p u t

    Currency Currency::Increment(const Currency x)

    { 增加量 x .

    this = Add(x);

    return this;

    }

    void Currency::Output const

    { 输出currency 的值

    if (sgn == minus) cout << '-';

    cout << '' << dollars << '.';

    if (cents < 10) cout << 0;

    cout << cents;

    }

    通过把C u r r e n c y类的成员变成私有(p r i v a t e),我们可以拒绝用户访问这些成员，所以用户

    不能使用如下的语句来改变这些成员的值：

    h.cents = 20;

    h.dollars = 100;

    h.sgn = plus;

    利用成员函数来设置数据成员的值可以确保数据成员拥有合法的值。构造函数和 S e t函数

    已经做到了这一点，其他函数当然也应该保证数据成员的合法性。因此，在诸如 A d d和O u t p u t

    函数的代码中不必验证c e n t s是否介于0到1 0 0之间。如果数据成员被声明为p u b l i c成员，它们的

    合法性将难以保证。用户可能会错误地把 c e n t s设置成3 0 5，因而将导致一些函数(如O u t p u t函

    数)产生错误结果，所以，所有的函数在处理任务之前都必须验证数据的合法性。这种验证将

    会降低代码的执行速度，同时也使代码不够优雅。

    程序1 - 2 0给出了类C u r r e n c y的应用示例。这段代码假定类定义及实现都在文件c u r r 1 . h之中。

    我们一般把类定义和类实现分放在不同的文件中，然而，这种分开放置的方法可能会对后续章

    节中大量使用模板函数和模板类带来困难。

    函数m a i n的第一行定义了四个C u r r e n c y类变量：g, h, i 和j。除h 具有初值 3 . 5 0外，构造函

    数把它们都初始化为 0 . 0 0。在接下来的两行中，g 和i 分别被设置成- 2 . 2 5和- 6 . 4 5，之后

    调用函数A d d把g 和h 加在一起，并把所返回的对象(值为 1 . 2 5)赋给j。为此，需使用缺省的

    赋值过程把右侧对象的各数据成员分别复制到左侧对象相应的数据成员之中，复制的结果是使

    j 具有值 1 . 2 5，这个值在下一行被输出。

    第1章 C ++程序设计 1 7 下载下两行语句把i 累加到h 上，并输出i的新值- 2 . 9 5。接下来的一行首先把 i和g加在一起，然后返回一个临时对象(其值为- 5 . 2 0) ，此后，把h 加到这个临时对象上并返回一个新的临

    时对象，其值为- 1 . 7 0。新的临时对象被复制到j 中，然后输出j 的值(为- 1 . 7 0) 。注意‘.’

    序列的处理顺序是从左到右。

    接下来的一行语句首先使用I n c r e m e n t为i累加g，它返回一个引用给i。A d d把i和h的和返回

    给j，最后输出j 的结果为- 1 . 7 0，i 的结果为- 5 . 2 0。

    程序1-20 Currency类应用示例

    include

    include curr1.h

    void main (void)

    {

    Currency g, h(plus, 3, 50), i, j;

    g.Set(minus, 2, 25);

    i . S e t ( - 6 . 4 5 ) ;

    j = h.Add(g);

    j.Output; cout << endl;

    i . I n c r e m e n t ( h ) ;

    i.Output; cout << endl;

    j = i.Add(g).Add(h);

    j.Output; cout << endl;

    j = i.Increment(g).Add(h);

    j.Output; cout << endl;

    i.Output; cout << endl;

    }

    1.4.2 使用不同的描述方法

    假定已经有许多应用采用了程序1 - 1 5中所定义的C u r r e n c y类，现在我们想要对C u r r e n c y类

    的描述进行修改，使其应用频率最高的两个函数A d d和I n c r e m e n t可以运行得更快，从而提高应

    用程序的执行速度。由于用户仅能通过 p u b l i c部分所提供的接口与C u r r e n c y类进行交互，因此

    对p r i v a t e部分的修改并不会影响应用代码的正确性。所以可以修改 p r i v a t e部分而不会使应用发

    生变化。

    在C u r r e n c y对象新的描述中，仅有一个私有数据成员，其类型为 l o n g。数1 3 2代表 1 . 3 2 ,而-2 0代表- 0 . 2 0。程序1-21, 1-22, 1-23中给出了C u r r e n c y类的新的描述方法以及各成员函数的

    具体实现。

    注意，如果把新代码放在文件c u r r 1 . h中，则可以运行程序1 - 2 0中的代码而不需要做任何修

    改。对用户隐藏实现细节的一个重大好处在于可以用新的、更高效的描述来取代以前的描述而

    不需要改变应用代码。

    程序1-21 Currency类的新定义

    class Currency {

    p u b l i c :

    构造函数

    1 8 第一部分 预 备 知 识

    下载Currency(sign s = plus, unsigned long d = 0, unsigned int c = 0);

    析构函数

    ~Currency {}

    bool Set(sign s, unsigned long d, unsigned int c);

    bool Set(float a);

    sign Sign const

    {if (amount < 0) return minus;

    else return plus;}

    unsigned long Dollars const

    {if (amount < 0) return (-amount) 100;

    else return amount 100;}

    unsigned int Cents const

    {if (amount < 0)

    return -amount - Dollars 100;

    else return amount - Dollars 100;}

    Currency Add(const Currency x) const;

    Currency Increment(const Currency x)

    {amount += x.amount; return this;}

    void Output const;

    p r i v a t e :

    long amount;

    } ;

    程序1-22 新的构造函数及S e t函数

    Currency::Currency(sign s, unsigned long d, unsigned int c)

    { 创建Currency 对象

    if (c > 99)

    { 美分数目过多

    cerr << Cents should be < 100 << endl;

    e x i t ( 1 ) ; }

    amount = d 100 + c;

    if (s == minus) amount = -amount;

    }

    bool Currency::Set(sign s, unsigned long d,unsigned int c)

    { 取值

    if (c > 99) return false;

    amount = d 100 + c;

    if (s == minus) amount = -amount;

    return true;

    }

    bool Currency::Set(float a)

    { 取值

    第1章 C ++程序设计 1 9 下载sign sgn;

    if (a < 0) {sgn = minus; a = -a;}

    else sgn = plus;

    amount = (a + 0.001) 100;

    if (sgn == minus) amount = -amount;

    return true;

    }

    程序1-23 函数A d d和O u t p u t的新代码

    Currency Currency::Add(const Currency x) const

    { 把x 累加至 t h i s .

    Currency y;

    y.amount = amount + x.amount;

    return y;

    }

    void Currency::Output const

    { 输出currency 的值

    long a = amount;

    if (a < 0) {cout << '-' ; a = -a;}

    long d = a 100; 美元

    cout << '' << d << '.';

    int c = a-d 100; 美分

    if (c < 10) cout << 0;

    cout << c;

    }

    1.4.3 操作符重载

    C u r r e n c y类包含了几个与 C + +标准操作符相类似的成员函数，例如， A d d进行+操作，I n c r e m e n t进行+ =操作。直接使用这些标准的 C + +操作符比另外定义新的函数(如 A d d，I n c r e m e n t)要自然得多。可以借助于操作符重载(operator overloading)的过程来使用+和+ =。

    操作符重载允许扩充现有C + +操作符的功能，以便把它们直接应用到新的数据类型或类。

    程序1 - 2 4给出了把A d d和I n c r e m e n t分别替换为+和+ =的类描述。O u t p u t函数采用一个输出

    流的名字作为参数。这些变化仅需修改A d d和O u t p u t的代码(见程序1 - 2 3) 。程序1 - 2 5给出了修

    改后的代码。在这个程序还给出了重载C + +流插入操作符< <的代码。

    注意在C u r r e n c y类中重载了流插入操作符，但没有定义相应的成员函数，而重载 +和+ =时

    则把它们定义为类成员。同样，也可以重载流抽取操作符> >而不需要把它定义为类成员。请留

    意，是函数O u t p u t支持了< <的重载。由于C u r r e n c y对象的p r i v a t e成员对于非类成员函数来说不

    可访问(被重载的< <不是类成员，而+是) ，所以，重载< <的代码不能引用对象x的私有成员

    (在< <操作中x将被插入到输出流中) 。特别地，下面的代码是错误的，因为成员 a m o u n t是不可

    访问的。

    重载< <

    ostream operator<< ( ostream out, const Currency x)

    { out << x.amount; return out; }

    2 0 第一部分 预 备 知 识

    下载程序1-24 使用操作符重载的类定义

    class Currency {

    p u b l i c :

    构造函数

    Currency(sign s = plus, unsigned long d = 0, unsigned int c = 0);

    析构函数

    ~Currency {}

    bool Set(sign s, unsigned long d, unsigned int c);

    bool Set(float a);

    sign Sign const

    {if (amount < 0) return minus;

    else return plus;}

    unsigned long Dollars const

    {if (amount < 0) return (-amount) 100;

    else return amount 100;}

    unsigned int Cents const

    {if (amount < 0)

    return -amount - Dollars 100;

    else return amount - Dollars 100;}

    Currency operator+(const Currency x) const;

    Currency operator+=(const Currency x)

    {amount += x.amount; return this;}

    void Output(ostream out) const;

    p r i v a t e :

    long amount;

    } ;

    程序1-25 +，O u t p u t和< <的代码

    Currency Currency::operator+(const Currency x) const

    { 把 x 累加至 t h i s .

    Currency y;

    y.amount = amount + x.amount;

    return y;

    }

    void Currency::Output(ostream out) const

    { 将currency 的值插入到输出流

    long a = amount;

    if (a < 0) {out << '-' ; a = -a ; }

    long d = a 100; 美元

    out << '' << d << '.' ;

    int c = a - d 100; 美分

    if (c < 10) out << 0;

    out << c;

    }

    重载< <

    ostream operator<<(ostream out, const Currency x)

    第1章 C ++程序设计 2 1 下载{x.Output(out); return out;}

    程序1 - 2 6是程序1 - 2 0的另一个版本，它假定操作符都已经被重载，程序 1 - 2 4和1 - 2 5的代码

    位于文件c u r r 3 . h之中。

    程序1-26 操作符重载的应用

    include

    include curr3.h

    void main(void)

    {

    Currency g, h(plus, 3, 50), i, j;

    g.Set(minus, 2, 25);

    i . S e t (-6 . 4 5 ) ;

    j = h + g;

    cout << j << endl;

    i += h;

    cout << i << endl;

    j = i + g + h;

    cout << j << endl;

    j = (i+=g) + h;

    cout << j << endl;

    cout << i << endl;

    }

    1.4.4 引发异常

    诸如构造函数和S e t函数这样的类成员在执行预定的任务时有可能会失败。在构造函数中

    处理错误条件的方法是退出程序，而在 S e t中则返回一个失败信号(f a l s e)给调用者。实际上

    可以通过引发异常来处理这些错误，以便在程序最合适的地方捕获异常并进行处理。为了引发

    异常，必须首先定义一个异常类，比如B a d I n i t i a l i z e r s (见程序1 - 2 7 )。

    程序1-27 异常类B a d I n i t i a l i z e r s

    初始化失败

    class BadInitializers {

    p u b l i c :

    BadInitializers {}

    } ;

    我们可以修改程序1 - 2 1中S e t函数的描述，使其返回v o i d类型。也可以修改构造函数的代码

    以及程序1 - 2 8中定义的第一个S e t函数的代码。其他的代码不做修改。

    程序1-28 引发异常

    Currency::Currency(sign s, unsigned long d, unsigned int c)

    { 创建一个C u r r e n c y对象

    if (c > 99) throw BadInitializers;

    amount = d 100 + c;

    2 2 第一部分 预 备 知 识

    下载if (s == minus) amount = -amount;

    }

    void Currency::Set(sign s, unsigned long d, unsigned int c)

    { 取值

    if (c > 99) throw BadInitializers;

    amount = d 100 + c;

    if (s == minus) amount = -amount;

    }

    1.4.5 友元和保护类成员

    正如前面所指出的那样，一个类的p r i v a t e成员仅对于类的成员函数是可见的。在有些应用

    中，必须把对这些p r i v a t e成员的访问权授予其他的类和函数，做法是把这些类和函数定义为友

    元(f r i e n d) 。

    在C u r r e n c y类例子中(见程序1 - 2 4) ，定义了一个成员函数O u t p u t以便于对操作符< <的重载。

    定义这个函数是必要的，因为如下函数：

    ostream operator <<(ostream out, const Currency x)

    不能访问p r i v a t e成员a m o u n t。我们可以把ostream operator<<描述为C u r r e n c y类的友元，从而

    避免定义附加的函数，这样就把 C u r r e n c y所有成员(包括p r i v a t e成员及p u b l i c成员)的访问权

    都授予了该函数。为了产生友元，需要在 C u r r e n c y类描述中引入friend 语句。为一致起见，总

    是把friend 语句放在类标题语句中，如：

    class Currency {

    friend ostream operator<< (ostream, const Currency);

    p u b l i c :

    有了这个友元，就可以使用程序1 - 2 9中的代码来重载操作符< <。当C u r r e n c y的p r i v a t e成员

    发生变化时，必须检查它的友元以便做出相应的变化。

    程序1-29 重载友元< <

    重载 < <

    ostream operator<<(ostream out, const Currency x)

    { 把currency 的值插入到输出流

    long a = x.amount;

    if (a < 0) {out << '-' ; a = -a;}

    long d = a 100; 美元

    out << '' << d << '.' ;

    int c = a - d 100; 美分

    if (c < 10) out << 0;

    out << c;

    return out;

    }

    稍后我们将看到如何从一个类B派生出另外一个类A， 此时类A被称为派生类 (drived class) ，类B被称为基类(base class) 。派生类需要访问基类的部分或所有数据成员。为了便于传递这

    些访问权，C + +提供了第三类成员——保护类成员(p r o t e c t e d) 。保护类成员类似于私有成员，第1章 C ++程序设计 2 3 下载区别在于派生类可以访问保护类成员。

    用户应用程序可以访问的类成员应被声明为 p u b l i c成员，数据成员尽量不要定义为这种类

    型，其他成员应分成p r i v a t e和p r o t e c t e d两部分。软件工程实践告诉我们，数据成员应尽量保持

    为p r i v a t e成员。通过增加保护类成员来访问和修改数据成员的值，派生类可以间接访问基类的

    数据成员。同时，可以修改基类的实现细节而不会影响派生类。

    1.4.6 增加ifndef, define和 e n d i f语句

    文件c u r r 1 . h (或c u r r 3 . h )的全部内容包含了C u r r e n c y类的描述及实现细节。在文件头，必须

    放上如下语句：

    ifndef Currency_

    define Currency_

    而在文件尾需要放上语句：

    e n d i f

    这些语句确保C u r r e n c y的代码仅被程序包含(i n c l u d e)和编译一次。建议你为本书中所提

    供的其他类定义也加上相应的语句。

    练习

    9. 1) 采用程序1 - 1 5中的描述，所能表示的最大和最小货币值分别是多少？假定用四个字节

    表示一个l o n g型数据，用两个字节表示一个i n t型数据，则一个unsigned long数介于0～2

    3 2

    - 1之间，一个unsigned int数介于0～6 5 5 3 5之间。

    2) 采用程序1 - 1 5中的描述，把d o l l a r s和c e n t s变成i n t型，此时所能表示的最大和最小货币值

    分别是多少？

    3) 如果用函数A d d(见程序1 - 1 8)来累加两个货币值，为了确保从 C u r r e n c y类型转换成

    long int类型时不会发生错误，a 1和a 2最大可能的值应是多少？

    10. 试扩充程序1 - 1 5中的C u r r e n c y类，为该类添加如下的p u b l i c成员函数：

    1) Input——从标准输入流中接收一个货币值，并把它返回给调用者。

    2) Subtract(x)——从当前对象中减去对象x的值，并把结果返回。

    3) Percent(x)——返回一个C u r r e n c y对象，其值为当前对象的x %，其中, x是一个浮点数。

    4) Multiply(x)——返回一个C u r r e n c y对象，其值为当前对象乘以浮点数x。

    5) Devide(x)——返回一个C u r r e n c y对象，其值为当前对象除以浮点数x。

    11. 采用程序1 - 2 1中的描述来完成练习1 0。

    12. 1) 采用程序1 - 2 4中的描述来完成练习1 0。重载操作符> > , - , % , 和。在重载操作符> >时，可把它定义成一个友元函数，不必专门定义一个p u b l i c输入函数。

    2) 利用重载赋值操作符 =来替换两个S e t函数。把一个整数赋值给一个 C u r r e n c y对象可用

    operator=(int x) 来表示，它可用来替换第一个S e t函数，其中x表示一个包含符号、美元和美分

    的整数。同样，operator=(float x)可用来替换第二个S e t函数。

    1.5 测试与调试

    1.5.1 什么是测试

    如1 . 1节所示，正确性是一个程序最重要的属性。由于采用严格的数学证明方法来证明一

    2 4 第一部分 预 备 知 识

    下载个程序的正确性是非常困难的(哪怕是一个很小的程序) ，所以我们想转而求助于程序测试

    (program test)过程来实施这项工作。所谓程序测试是指在目标计算机上利用输入数据，也称

    之为测试数据(test data)来实际运行该程序，把程序的实际行为与所期望的行为进行比较。

    如果两种行为不同，就可判定程序中有问题存在。然而，不幸的是，即使两种行为相同，也不

    能够断定程序就是正确的，因为对于其他的测试数据，两种行为又可能不一样。如果使用了许

    多组测试数据都能够看到这两种行为是一样的，我们可以增加对程序正确性的信心。通过使用

    所用可能的测试数据，可以验证一个程序是否正确。然而，对于大多数实际的程序，可能的测

    试数据的数量太大了，不可能进行穷尽测试，实际用来测试的输入数据空间的子集称之为测试

    集(test set) 。

    例1-4 [二次方程求解] 一个关于变量x 的二次函数形式如下：

    a x

    2

    + b x +c

    其中a, b, c 的值是已知的，且a≠0。3x

    2

    -2x+4, -9x

    2

    -7x, 3.5x

    2

    + 4以及5 . 8x

    2

    + 3 . 2x+ 5都是二次函数

    的实例。5x+ 3不是二次函数。

    二次函数的根是指使函数的值为 0的那些x。例如，函数f (x) =x

    2

    -5x+ 6的根为2和3，因为

    f ( 2) = f (3) =0。每个二次函数都会有两个根，这两个根可用如下公式给出：

    对于函数f (x) = x

    2

    -5x+6, a=1, b=-5, c= 6 ,把a, b, c 代入以上公式，可得：

    所以f (x) 的根是x = 3和x = 2。

    当d=b

    2

    -4ac =0 时，所得到的两个根是一样的；当d >0 时，两个根不同且是实数；当d <0

    时，两个根也不相同且为复数，此时，每个根都有一个实部( r e a l)和一个虚部(i m a g i n a r y),实部为-b 2a，虚部为 。复数根为“实部+虚部i ”和“实部-虚部i” ，其中i = 。

    函数O u t p u t R o o t s(见程序1 - 3 0)计算并输出一个二次方程的根。我们不去试图对该函数的

    正确性进行形式化证明，而是希望通过测试来验证其正确性。对于该程序来说，所有可能的输

    入数据的数目实际上就是所有不同的三元组(a, b, c)的数目，其中a≠0。即使a, b和c 都被限

    制为整数，所有可能的三元组的数目也是非常巨大，要想测试所有的三元组是不可能的。若整

    数的长度为1 6位，b 和c 都有2

    16

    种不同取值，a 有2

    1 6

    -1种不同取值(因为a 不能为0) ，所有不

    同三元组的数目将达到2

    3 2

    (2

    1 6

    -1) 。如果目标计算机能按每秒钟1 000 000个三元组的速率进行

    测试，那么至少需要9年才能完成!如果使用一个更快的计算机，按每秒测试1 000 000 000 个

    三元组的速度，也至少需要三天才能完成。所以一个实际使用的测试集仅是整个测试数据空间

    中的一个子集。

    程序1-30 计算并输出一个二次方程的根

    template

    void OutputRoots(T a, T b, T c)

    { 计算并输出一个二次方程的根

    T d = bb-4 a c ;

    -1 - d

    第1章 C ++程序设计 2 5 下载if (d > 0) { 两个实数根

    float sqrtd = sqrt(d);

    cout << There are two real roots

    << (-b+sqrtd)(2a) << and

    << (-b-sqrtd)(2a)

    << endl;}

    else if (d == 0)

    两个根相同

    cout << There is only one distinct root

    << -b(2a)

    << endl;

    else 复数根

    cout << The roots are complex

    << endl

    << The real part is

    << -b(2a) << endl

    << The imaginary part is

    << sqrt(-d)(2a) << endl;

    }

    如果使用数据(a, b, c)=(1, -5, 6)来进行测试，程序将输出2和3，程序的行为与期望的行

    为是一致的，因此可以推断对于该输入数据，程序是正确的。然而，使用一个适当的测试数据

    子集来验证所观察行为与所期望行为的一致性并不能证明对于所有的输入数据，程序都能够正

    确工作。

    由于可以提供给一个程序的不同输入数据的数目一般都非常巨大，所以测试通常都被限制

    在一个很小的子集中进行。使用子集所完成的测试不能完全保证程序的正确性。所以，测试的

    目的不是去建立正确性认证，而是要暴露程序中的错误!必须选择能暴露程序中所存在错误的

    测试数据，不同的测试数据可以暴露程序中不同的错误。

    例1-5 测试数据(a, b, c)=(1, -5, 6) 可以使函数OutputRoots 执行产生两个实数根的代码，如果

    输出了2和3，可以有一些信心地认为在本次测试中所执行的代码是正确的。注意，一段错误的

    代码也可能给出正确的结果。例如，如果在关于d的表达式中忽略a，将其错误地写成：

    T d = b b - 4 c;

    d的值与所测试的结果相同，因为 a = 1。由于使用测试数据(1，-5，6)未能执行完代码中的

    所有语句，故我们对尚未执行的语句还没有多大的信心。

    测试集{(1, -5, 6), (1, 3, 2), (2, 5, 2)} 仅可用来暴露OutputRoots 前7行语句中存在的错误，因为这个测试集中的每个三元组仅需要执行代码的前7行语句。然而，测试集{(1, -5, 6), (1, -8 ,16), (1, 2, 5)} 可使OutputRoots 中的每行语句都得到执行，所以该测试集将可以暴露较多的错误。

    1.5.2 设计测试数据

    在设计测试数据的时候，应当牢记：测试的目标是去披露错误。如果用来寻找错误的测试

    数据找不到错误，我们就可以有信心相信程序的正确性。为了弄清楚对于一个给定的测试数据，程序是否存在错误，首先必须知道对于该测试数据，程序的正确结果应是什么。

    例1-6 对于二次方程求解的例子，可以用如下两种方法之一来给定任意测试数据时程序的正

    2 6 第一部分 预 备 知 识

    下载确输出。第一种方法是，计算出所测试二次方程的根。例如，系数(a, b, c)=(1, -5, 6)的二次

    方程的根为2和3。对于测试数据(1, -5, 6) ，可以把程序所输出的根与2和3进行比较，以验证

    程序1 - 3 0的正确性。第二种可行的方法是把程序所产生的根代入二次函数以验证函数的值是否

    真为0。所以，如果程序输出的是2和3，可以计算出f (2) = 22-52 + 6=0, f ( 3) = 3 2-5 3 + 6 = 0。

    可以把这种验证方法用计算机程序来实现。对于第一种方法，测试程序输入三元组( a, b, c)

    和期望的根，然后把程序计算出的根与期望的根进行比较。对于第二种方法，可以编写代码来

    计算对于程序输出的根，二次函数的相应函数值，然后验证这个值是否为0。

    可以采用下面的条件来计算任何候选的测试数据：

    这个数据能够发现错误的潜力如何？

    能否验证采用这个数据时程序的正确性？

    设计测试数据的技术分为两类：黑盒法(black box method)和白盒法(white box method) 。

    在黑盒法中，考虑的是程序的功能，而不是实际的代码。在白盒法中，通过检查程序代码来设

    计测试数据，以便使测试数据的执行结果能很好地覆盖程序的语句以及执行路径。

    1. 黑盒法

    最流行的黑盒法是IO 分类及因果图，本节仅探讨I O分类。在这种方法中，输入数据和

    或输出数据空间被分成若干类，不同类中的数据会使程序所表现出的行为有质的不同，而相同

    类中的数据则使程序表现出本质上类似的行为。二次方程求解的例子中有三种本质上不同的行

    为：产生复数根，产生实数根且不同，产生实数根且相同。可以根据这三种行为把输入空间分

    为三类。第一类中的数据将产生第一种行为；第二类中的数据将产生第二种行为；而第三类中

    的数据将产生第三种行为。一个测试集应至少从每一类中抽取一个输入数据。

    2. 白盒法

    白盒法基于对代码的考察来设计测试数据。对一个测试集最起码的要求就是使程序中的每

    一条语句都至少执行一次。这种要求被称为语句覆盖( statement coverage) 。对于二次方程求

    解的例子，测试集{ (1, -5, 6) ， (1，-8，1 6) ， (1，2，5) } 将使程序中的每一条语句都得以执

    行，而测试集{ (1，-5，6) ， (1，3，2) ， (2，5，2) } 则不能提供语句覆盖。

    在分支覆盖(decision coverage)中要求测试集要能够使程序中的每一个条件都分别能出

    现t r u e和f a l s e两种情况。程序1 - 3 0中的代码有两个条件：d > 0和d = = 0。在进行分支覆盖测试时，要求测试集至少能使条件d > 0和d = = 0分别出现一次为t r u e、一次为f a l s e的情况。

    例1-7 [求最大元素] 程序1 - 3 1用于返回数组a [ 0 : n-1 ]中最大元素所在的位置。它依次扫描a [ 0 ]到

    a [ n-1 ]，并用变量p o s来保存到目前为止所能找到的最大元素的位置。数据集 a [ 0 : 4 ] = [ 2 , 4 , 6 , 8 , 9 ]

    能够提供语句覆盖，但不能提供分支覆盖，因为条件a [ p o s ] < a [ i ]不会变成f a l s e。数据集[ 4，2，6，8，9 ]既能提供语句覆盖也能提供分支覆盖。

    程序1-31 寻找最大元素

    template

    int Max(T a[], int n)

    { 寻找 a [ 0 : n - 1 ]中的最大元素

    int pos = 0;

    for (int i = 1; i < n; i++)

    if (a[pos] < a[i])

    pos = i;

    第1章 C ++程序设计 2 7 下载return pos;

    }

    可以进一步加强分支覆盖的条件，要求每个条件中的每个从句(c l a u s e)既能出现t r u e也能

    出现f a l s e的情况，这种加强的条件被称之为从句覆盖(clause coverage) 。一个从句在形式上被

    定义成一个不包含布尔操作符(如 , | | , !)的布尔表达式。表达式x > y，x + y < y z以及c ( c是一

    个布尔类型)都是从句的例子。考察如下语句：

    if((C1 C2) || (C3 C4)) S1;

    else S2;

    其中C 1，C 2，C 3和C 4是从句，S 1和S 2是语句。在分支覆盖方式下，需要使用一个能使 ( ( C 1

    C2) || (C3 C4))为t r u e的测试数据以及一个能使该条件为 f a l s e的测试数据。而从句覆盖

    则要求测试数据能使四个从句C 1 , C 2 , C 3和C 4都分别至少取一次t r u e值和至少取一次f a l s e值。

    还可以继续加强从句覆盖的条件，要求测试各从句值的所有可能组合。对于上面的条件

    ((C1 C2) || (C3 C4))，加强后的从句覆盖要求使用1 6个测试数据集：每个测试集对应于

    四个从句值组合后的情形。不过，其中有些组合是不可能的。

    如果按照某个测试数据集来排列程序语句的执行次序，可以得到一条执行路径( e x e c u t i o n

    p a t h) 。不同的测试数据可能会得到不同的执行路径。程序 1 - 3 0仅存在三条执行路径——第1行

    至第7行，第1、2、8～1 2行，第1、2、8、1 3～1 9行。而程序1 - 3 1中的执行路径则随着n的增加

    而增加。当n= 1时，仅有一条执行路径——1、2、5行；当n= 2时，有两条路径——1、2、3、2、5和1、2、3、4、2、5行；当n = 3时，有四条路径——1、2、3、2、3、2、5行， 1、2、3、4、2、3、2、5行，1、2、3、2、3、4、2、5行，1、2、3、4、2、3、4、5行。执行路径覆盖要求

    测试数据集能使每条执行路径都得以执行。对于二次方程求解程序，语句覆盖、分支覆盖、从

    句覆盖以及执行路径覆盖都是等价的，但对于程序 1 - 3 1，语句覆盖、分支覆盖、和执行路径覆

    盖是不同的，而分支覆盖和从句覆盖是等价的。

    在这些白盒测试方法中，一般要求实现执行路径覆盖。一个能实现全部执行路径覆盖的测

    试数据同样能实现语句覆盖和分支覆盖，然而，它可能无法实现从句覆盖。全部执行路径覆盖

    通常会需要无数的测试数据或至少是非常可观的测试数据，所以在实践中一般不可能进行全部

    执行路径覆盖。

    本书中的许多练习都要求你测试所编代码的正确性。你所使用的测试数据应至少提供语句

    覆盖。此外，你必须测试那些可能会使你的程序出错的特定情形。例如，对于一个用来对 n≥0

    个元素进行排序的程序，除了测试n 的正常取值外，还必须测试n= 0 , 1这两种特殊情形。如果该

    程序使用数组a[0:99], 还需要测试n= 1 0 0的情形。n= 0 , 1和1 0 0分别表示边界条件为空，单值和全

    数组的情形。

    1.5.3 调试

    测试能够发现程序中的错误。一旦测试过程中产生的结果与所期望的结果不同，就可以了

    解到程序中存在错误。确定并纠正程序错误的过程被称为调试( d e b u g) 。尽管透彻地研究程序

    调试的方法超出了本书的范围，但我们还是提供一些好的建议给大家：

    可以用逻辑推理的方法来确定错误语句。如果这种方法失败，还可以进行程序跟踪，以

    确定程序什么时候开始出现错误。如果对于给定的测试数据程序需要运行很多指令，因而需要

    跟踪太多语句，很难人工确定错误，此时，这种方法就不太可行了，在这种情况下，必须试着

    把可疑的代码分离出来，专门跟踪这段代码。

    2 8 第一部分 预 备 知 识

    下载? 不要试图通过产生异常来纠正错误。异常的数量可能会迅速增长。必须首先找到需要纠

    正的错误，然后根据需要重新设计。

    在纠正一个错误时，必须保证不会产生一个新的、以前没有的错误。用原本能使程序正

    确运行的测试数据来运行纠正过错误的程序，确信对于该数据，程序仍然正确。

    在测试和调试一个有错的程序时，从一个与其他函数独立的函数开始。这个函数应该是

    一个典型的输入或输出函数。然后每次引入一个尚未测试的函数，测试并调试更大一些的程序。

    这种策略被称为增量测试与调试(incremental test and debug) 。在使用这种策略时，可以有理

    由认为产生错误的语句位于刚刚引入的函数之中。

    练习

    13. 证明能够为程序1 - 3 0提供语句覆盖的测试集也能提供分支覆盖和执行路径覆盖。

    14. 为程序1 - 3 1设计一个n = 4的测试数据集，要求该测试集能提供执行路径覆盖。

    15. 程序1 - 8中有多少条执行路径？

    16. 程序1 - 9中有多少条执行路径？

    1.6 参考及推荐读物

    1) J.Cohoon, J.Davidson. C++ P rogram Design: An Introduction to Programming and Object-

    Oriented Design. Richard D.Irwin, 1997。

    2) H.Deitel, P.Deitel. C++ How to Pro g r a m. Prentice Hall, 1994。

    以上两本书是比较好的C + +语言入门教材。

    3) G.Myers. The Art of Software Te s t i n g. John Wi l e y, 1979。

    4) Boris Beizer. S o f t w a re Testing Techniques 第2版. Van Nostrand Reinhold, 1990。

    后两本书对于软件测试及调试技术有更透彻的介绍。

    第1章 C ++程序设计 2 9 下载下载下载

    第2章 程 序 性 能

    以下是本章中所介绍的有关程序性能分析与测量的概念：

    确定一个程序对内存及时间的需求。

    使用操作数和执行步数来测量一个程序的时间需求。

    采用渐进符号描述复杂性，如O、 、 、o。

    利用计时函数测量一个程序的实际运行时间。

    除了上述概念以外，本章还给出了许多应用代码，在后续章节中将可以看到，这些代码有

    很多用处。这些应用包括：

    在一个数组中搜索具有指定特征的元素。本章中所使用的方法是顺序搜索和折半搜索。

    对数组元素进行排序。本章给出了计数排序、选择排序、冒泡排序及插入排序的实现

    代码。

    采用Horner 法则计算一个多项式。

    执行矩阵运算，如矩阵加、矩阵转置和矩阵乘。

    2.1 引言

    所谓程序性能( program performance) ，是指运行一个程序所需要的内存大小和时间。

    可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在进行

    性能分析( performance analysis)时，采用分析的方法，而在进行性能测量( p e r f o r m a n c e

    m e a s u r e m e n t)时，借助于实验的方法。

    程序的空间复杂性(space complexity)是指运行完一个程序所需要的内存大小。对一个程

    序的空间复杂性感兴趣的主要原因如下：

    如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。

    对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。

    一个问题可能有若干个内存需求各不相同的解决方案。比如，对于你的计算机来说，某

    个C + +编译器仅需要1 M B的空间，而另一个C + +编译器可能需要4 M B的空间。如果你的计算机

    中内存少于4 M B，你只能选择1 M B的编译器。如果较小编译器的性能比得上较大的编译器，即

    使用户的计算机中有额外的内存，也宁愿使用较小的编译器。

    可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。例如，有一个电路模

    拟程序，用它模拟一个有 c个元件、w个连线的电路需要2 8 0 K + 1 0 (c+w)字节的内存。如果

    可利用的内存总量为6 4 0 K字节，那么最大可以模拟c+w≤3 6 K的电路。

    程序的时间复杂性(time complexity)是指运行完该程序所需要的时间。对一个程序的时

    间复杂性感兴趣的主要原因如下：

    有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。

    一种简易的办法是简单地指定时间上限为几千年。然而这种办法可能会造成严重的财政问题，因为如果由于数据问题导致你的程序进入一个死循环，你可能需要为你所使用的机时付出巨额

    资金。因此我们希望能提供一个稍大于所期望运行时间的时间上限。? 正在开发的程序可能需要提供一个满意的实时响应。例如，所有交互式程序都必须提

    供实时响应。一个需要 1分钟才能把光标上移一页或下移一页的文本编辑器不可能被众多的

    用户接受；一个电子表格程序需要花费几分钟才能对一个表单中的单元进行重新计值，那

    么只有非常耐心的用户才会乐意使用它；如果一个数据库管理系统在对一个关系进行排序

    时，用户可以有时间去喝两杯咖啡，那么它也很难被用户接受。为交互式应用所设计的程

    序必须提供满意的实时响应。根据程序或程序模块的时间复杂性，可以决定其响应时间是

    否可以接受，如果不能接受，要么重新设计正在使用的算法，要么为用户提供一台更快的

    计算机。

    如果有多种可选的方案来解决一个问题，那么具体决定采用哪一个主要基于这些方案之

    间的性能差异。对于各种解决方案的时间及空间复杂性将采用加权的方式进行评价。

    练习

    1. 给出两种以上的原因说明为什么程序分析员对程序的空间复杂性感兴趣？

    2. 给出两种以上的原因说明为什么程序分析员对程序的时间复杂性感兴趣？

    2.2 空间复杂性

    2.2.1 空间复杂性的组成

    程序所需要的空间主要由以下部分构成：

    指令空间(instruction space) 指令空间是指用来存储经过编译之后的程序指令所需的

    空间。

    数据空间(data space) 数据空间是指用来存储所有常量和所有变量值所需的空间。数

    据空间由两个部分构成：

    1) 存储常量(见程序1 - 1至1 - 9中的数0、1和4)和简单变量(见程序1 - 1至1 - 6中的a、b和c)

    所需要的空间。

    2) 存储复合变量(见程序1 - 8和1 - 9中的数组a)所需要的空间。这一类空间包括数据结构

    所需的空间及动态分配的空间。

    环境栈空间(environment stack space) 环境栈用来保存函数调用返回时恢复运行所需要

    的信息。例如，如果函数f u n 1调用了函数f u n 2，那么至少必须保存f u n 2结束时f u n 1将要继续执

    行的指令的地址。

    1. 指令空间

    程序所需要的指令空间的数量取决于如下因素：

    把程序编译成机器代码的编译器。

    编译时实际采用的编译器选项。

    目标计算机。

    在决定最终代码需要多少空间的时候，编译器是一个最重要的因素。图 2 - 1给出了用来计

    算表达式a + b + b c + ( a + b - c ) ( a + b ) + 4的三段可能的代码，它们都执行完全相同的算术操作(如，每个操作符都有相同的操作数) ，但每段代码所需要的空间都不一样。所使用的编译器将确定

    产生哪一种代码。

    第2章 程 序 性 能 3 1 下载L O A D a L O A D a L O A D a

    A D D b A D D b A D D b

    S TO R E t 1 S TO R E t 1 S TO R E t 1

    L O A D b S U B c S U B c

    M U LT c D I V t 1 D I V t 1

    S TO R E t 2 S TO R E t 2 S TO R E t 2

    L O A D t 1 L O A D b L O A D b

    A D D t 2 M U L c M U L c

    S TO R E t 3 S TO R E t 3 A D D t 2

    L O A D a L O A D t 1 A D D t 1

    A D D b A D D t 3 A D D 4

    S U B c A D D t 2

    S TO R E t 4 A D D 4

    L O A D a

    A D D b

    S TO R E t 5

    L O A D t 4

    D I V t 5

    S TO R E t 6

    L O A D t 3

    A D D t 6

    A D D 4

    a ) b ) c )

    图2-1 三段等价的代码

    即使采用相同的编译器，所产生程序代码的大小也可能不一样。例如，一个编译器可能为

    用户提供优化选项，如代码优化以及执行时间优化等。比如，在图 2 - 1中，在非优化模式下，编译器可以产生图2-1b 的代码。在优化模式下，编译器可以利用知识 a + b + b c = b c + ( a + b )来产

    生图2-1c 中更短、更高效的代码。使用优化模式通常会增加程序编译所需要的时间。

    从图2 - 1的例子中可以看到，一个程序还可能需要其他额外的空间，即诸如临时变量 t1, t2,..., t6 所占用的空间。

    另外一种可以显著减少程序空间的编译器选项就是覆盖选项，在覆盖模式下，空间仅分配

    给当前正在执行的程序模块。在调用一个新的模块时，需要从磁盘或其他设备中读取，新模块

    的代码将覆盖原模块的代码。所以程序空间就等价于最大的模块所需要的空间(而不是所有模

    块之和) 。

    目标计算机的配置也会影响代码的规模。如果计算机具有浮点处理硬件，那么每个浮点操

    作可以转换成一条机器指令。如果没有安装浮点处理硬件，必须生成仿真的浮点计算代码。

    2. 数据空间

    对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器以及变量与常量

    的数目。之所以如此是因为我们通常关心所需内存的字节数。由于每字节所占用的位数依赖于

    具体的机器环境，因此每个变量所需要的空间也会有所不同。此外，存储 2

    100

    也将比存储2

    3

    需

    要更多的位数。

    3 2 第一部分 预 备 知 识

    下载图2 - 2中列出了Borland C++中每种简单变量所占用的空间。对于一个结构变量，可以把它

    的每个成员所占用的空间累加起来即可得到该变量所需要的内存。类似地，可以得到一个数组

    变量所需要的空间，方法是用数组的大小乘以单个数组元素所需要的空间。

    类 型 占用字节数 范 围

    c h a r 1 - 1 2 8 ~ 1 2 7

    unsigned char 1 0 ~ 2 5 5

    s h o r t 2 -32 768~32 767

    i n t 2 -32 768~32 767

    unsigned int 2 0~65 535

    l o n g 4 - 2

    3 1

    ~ 2

    3 1

    - 1

    unsigned long 4 0 ~ 2

    3 2

    - 1

    f l o a t 4 ±3 . 4 E±3 8

    d o u b l e 8 ±1 . 7 E±3 0 8

    long double 1 0 3. 4E-4932~1.1E+4932

    p o i n t e r 2 ( n e a r, _cs, _ds, _es, _ss指针)

    p o i n t e r 4 ( f a r, huge指针)

    注意：在3 2位Borland C++程序中，i n t类型的长度为4

    图2-2 Borland C++中每种简单变量所占用的空间(摘自Borland C++

    Programmer's Guide，Borland 公司，加州Scotts Va l l e y, 1996)

    考察如下的数组定义：

    double a[100];

    int maze[rows][cols];

    数组a 需要的空间为1 0 0个d o u b l e类型元素所占用的空间，若每个元素占用 8个字节，则分

    配给该数组的空间总量为8 0 0字节。数组m a z e有r o w s c o l s个i n t类型的元素，它所占用的总空间

    为2 r o w s c o l s字节。

    3. 环境栈

    在刚开始从事性能分析时，分析员通常会忽略环境栈所需要的空间，因为他们不理解函数

    是如何被调用的以及在函数调用结束时会发生什么。每当一个函数被调用时，下面的数据将被

    保存在环境栈中：

    返回地址。

    函数被调用时所有局部变量的值以及传值形式参数的值(仅对于递归函数而言) 。

    所有引用参数及常量引用参数的定义。

    每当递归函数R s u m (见程序1 - 9 )被调用时，不管该调用是来自外部或第4行，a的当前赋值、n的值以及程序运行结束时的返回地址都被存储在环境栈之中。

    值得注意的是，有些编译器在保留局部变量的值、传值形式参数的值以及引用参数和常量

    引用参数的定义时，对于递归函数和非递归函数一视同仁，而有些编译器则仅为递归函数保存

    上述内容。所以实际使用的编译器将影响环境栈所需要的空间。

    4. 小结

    程序所需要的空间取决于多种因素，有些因素在构思或编写程序时是未知的(如将要使用

    第2章 程 序 性 能 3 3 下载的计算机及编译器) ，不过即使这些因素已经完全确定，我们也无法精确地分析一个程序所需

    要的空间。

    然而，我们可以确定程序中某些部分的空间需求，这些部分依赖于所解决实例的特征。一

    般来说，这些特征包含决定问题规模的那些因素(如，输入和输出的数量或相关数的大小) 。

    例如，对于一个对n 个元素进行排序的程序，可以确定该程序所需要的空间为 n 的函数；对于

    一个累加两个n×n 矩阵的程序，可以使用n 作为其实例特征；而对于累加两个m×n 矩阵的程

    序，可以使用m 和n 作为实例特征。

    指令空间的大小对于所解决的特定问题不够敏感。常量及简单变量所需要的数据空间也独

    立于所解决的问题，除非相关数的大小对于所选定的数据类型来说实在太大，这时，要么改变

    数据类型，要么使用多精度算法重写该程序，然后再对新程序进行分析。

    复合变量及动态分配所需要的空间同样独立于问题的规模。而环境栈通常独立于实例的特

    征，除非正在使用递归函数。在使用递归函数时，实例特征通常(但不总是)会影响环境栈所

    需要的空间数量。

    递归函数所需要的栈空间通常称之为递归栈空间(recursion stack space) 。对于每个递归函

    数而言，该空间主要依赖于局部变量及形式参数所需要的空间。除此以外，该空间还依赖于递

    归的深度(即嵌套递归调用的最大层次) 。在程序1 - 9中嵌套递归调用一直进行到 n = 0，这时，嵌套调用的层次关系如图2 - 3所示。该程序的最大递归深度为n + 1。

    Rsum(a, n)

    Rsum(a, n-1)

    Rsum(a, n-2)

    .

    .

    .

    Rsum(a, 1)

    Rsum(a, 0)

    图2-3 程序1 - 9的嵌套调用层次

    至此，可以把一个程序所需要的空间分成两部分：

    固定部分，它独立于实例的特征。一般来说，这一部分包含指令空间(即代码空间) 、简

    单变量及定长复合变量所占用空间、常量所占用空间等等。

    可变部分，它由以下部分构成：复合变量所需的空间(这些变量的大小依赖于所解决的

    具体问题) ，动态分配的空间(这种空间一般都依赖于实例的特征) ，以及递归栈所需的空间

    (该空间也依赖于实例的特征) 。

    任意程序P 所需要的空间S (P)可以表示为：

    S (P) = c + Sp(实例特征)

    其中c 是一个常量，表示固定部分所需要的空间， Sp

    表示可变部分所需要的空间。一个

    精确的分析还应当包括在编译期间所产生的临时变量所需要的空间(如图 2 - 1所示) ，这种空

    间是与编译器直接相关的，除依赖于递归函数外，它还依赖于实例的特征。本书将忽略这

    种空间。

    在分析程序的空间复杂性时，我们将把注意力集中在估算 Sp(实例特征)上。对于任意给

    3 4 第一部分 预 备 知 识

    下载定的问题，首先需要确定实例的特征以便于估算空间需求。实例特征的选择是一个很具体的问

    题，我们将求助于介绍各种可能性的实际例子。一般来说，我们的选择受到相关数的数量以及

    程序输入和输出的规模的限制。有时还会使用更复杂的估算数据，这些数据来自于数据项之间

    的相互关系。

    2.2.2 举例

    例2-1 考察程序1 - 4。在估算Sp

    之前，必须选择分析所使用的实例特征。两种可能性是：( 1 )数

    据类型T；(2) a, b 和c 的大小。假定使用T作为实例特征。由于a, b和c是引用参数，所以在函数

    中不需要为它们的值分配空间，但是必须保存指向这些参数的指针。如果每个指针需要 2个字

    节，那么共需要6个字节的指针空间。因此函数所需要的总空间是一个常量，SA b c

    (实例特征) = 0。

    如果函数Abc 的参数是传值参数，那么每个参数需要分配大小为sizeof (T) 的空间。在本例中，a, b 和c 所需要的空间为 3sizeof (T)。所需要的其他空间都独立于 T。因此SA b c

    (实例特

    征) =3sizeof (T)。如果使用a, b 和c 的大小作为实例特征，则不管使用引用参数还是使用传值

    参数，都有 SA b c

    (实例特征) = 0。注意在传值参数的情形下，分配给每个 a , b和c的空间均为

    s i z e o f ( T )，而不考虑存储在这些变量中的实际值是多大。例如，如果T是d o u b l e类型，那么每个

    字节将被分配8个字节的空间。

    例2-2 [顺序搜索] 程序2 - 1从左至右检查数组a [ 0 : n - 1 ]中的元素，以查找与x相等的那些元素。

    如果找到一个元素与x 相等，则函数返回x 第一次出现所在的位置。如果在数组中没有找到这

    样的元素，函数返回- 1。

    程序2-1 顺序搜索

    template

    int SequentialSearch(T a[], const T x, int n)

    { 在未排序的数组a [ 0 : n-1 ]中搜索 x

    如果找到，则返回所在位置，否则返回- 1

    int i;

    for (i = 0; i < n a[i] != x; i++);

    if (i == n) return -1 ;

    return i;

    }

    我们希望采用实例特征n 来估算该函数的空间复杂性。假定T 为int 类型，则数组a 中的每

    个元素需要2个字节，实参x需要2个字节，传值形式参数n 需要2个字节，局部变量i 需要2个字

    节，每个整型常量0和-1也分别需要2个字节。因此，所需要的总的数据空间为 1 2字节。因为

    该空间独立于n，所以S顺序搜索(n)= 0。

    注意数组a 必须足够大以容纳所查找的n 个元素。不过，该数组所需要的空间已在定义实际

    参数(对应于a)的函数中分配，所以，不需要把该数组所需要的空间加到函数S e q u e n t i a l S e a r c h

    所需要的空间上去。

    例2-3 考察函数Sum (见程序1 - 8 )。假定我们有兴趣把该函数所需要的空间看成欲累加元素的总

    数的函数。在该函数中，a, n, i 和tsum 需要分配空间，所以程序所需要的空间与n 无关，因此

    有SS u m (n) = 0。

    第2章 程 序 性 能 3 5 下载例2-4 考察函数Rsum (见程序1 - 9 )。如上例一样，假定实例特征为 n。递归栈空间包括形式

    参数a和n以及返回地址的空间。对于a，需要保留一个指针，而对于n 则需要保留一个int 类型

    的值。如果假定指针为near 指针，则该指针需要2个字节的存储空间。如果同时假定返回地址

    也占用2个字节，那么根据int 类型需要2个字节的常识，可以确定每一次调用Rsum 需要6个字

    节的栈空间。由于递归的深度为 n + 1，所以需要 6 ( n + 1 )字节的递归栈空间，因而 SRsum

    ( n)=

    6 ( n + 1 )。

    程序1 - 8所需要的空间比程序1 - 9所需要空间要小。

    例2-5 [阶乘运算] 通过分析程序1 - 7中计算阶乘的函数可知，该程序的空间复杂性是n的函数而

    不是输入(只有一个)或输出(也只有一个)个数的函数。递归深度为 max {n, 1}。每次调用

    函数Factorial 时，递归栈需要保留返回地址(2个字节)和n 的值(2个字节) 。此外没有其他

    依赖于n 的空间，所以SF a c t o r i a l

    (n) = 4max {n, 1}。

    例2-6 [排列方式] 程序1 - 1 0输出一组元素的所有排列方式。对于初始调用Perm (list, 0, n-1 )，递归的深度为n。由于每次调用需要1 0个字节的递归栈空间(每个返回地址、 l i s t、k、m以及i

    各需要2个字节) ，所以需要10n 字节的递归栈空间，SPerm

    (n) = 10n。

    练习

    3. 试采用两种C + +编译器编译同一个C + +程序，所得代码的长度相同吗？

    4. 给出可能影响程序空间复杂性的其他因素。

    5. 使用图2 - 2所提供的数据来计算如下数组所需要的字节数：

    1) int matrix[10][100]

    2) double x[100][5][20]

    3) long double y[3]

    4) float z[10][10][10][5]

    5) short z[2][3][4]

    6) long double b[3][3][3][3]

    6. 程序2 - 2给出了一个在数组a [ 0 : n - 1 ]中查找元素x的递归函数。如果找到x ,则函数返回x在a

    中的位置，否则返回-1。试计算SP

    (n) 。

    程序2-2 执行顺序搜索的递归函数

    template

    int SequentialSearch(T a[], const T x, int n)

    { 在未排序的数组a [ 0 : n-1 ]中查找x

    如果找到则返回所在位置，否则返回- 1

    if (n <1) return -1 ;

    if (a[n-1] == x) return n-1 ;

    return SequentialSearch(a,x,n-1 ) ;

    }

    7. 编写一个非递归函数计算n!(例1 - 1) ，并比较该函数的空间复杂性与程序1 - 7中递归函数

    的空间复杂性。

    3 6 第一部分 预 备 知 识

    下载2.3 时间复杂性

    2.3.1 时间复杂性的组成

    影响一个程序空间复杂性的因素也都能影响程序的时间复杂性。一个程序在一台每秒钟能

    执行1 0

    9

    条指令的机器上运行要比在每秒仅能执行1 0

    6

    条指令的机器上快得多。图2-1c 中的代码

    要比图2-1a 中的代码运行时间更少。较小的问题所需要的运行时间通常要比较大的问题需要的

    时间少。

    一个程序P所占用的时间T (P)=编译时间+运行时间。编译时间与实例的特征无关。另外，可以假定一个编译过的程序可以运行若干次而不需要重新编译。因此我们将主要关注程序的运

    行时间。运行时间通常用“t

    p (实例特征)”来表示。

    由于在构思一个程序时，影响t p 的许多因素还是未知的，所以我们有理由仅仅对t p 进行估

    算。如果我们了解所用编译器的特征，就可以确定代码P 进行加、减、乘、除、比较、读、写

    等所需要的时间，从而可以得到一个计算t

    p 的公式。令n 代表实例的特征，可以得到如下形式

    的表达式：

    t

    p (n) = ca

    ADD (n) + cs

    SUB (n) + cm MUL (n) + cd

    DIV (n) + …

    其中ca

    , cs

    , cm 和cd

    分别表示一个加、减、乘和除操作所需要的时间，函数A D D、S U B、M U L和

    D I V分别表示代码P中所使用的加、减、乘和除操作的次数。

    存在这样一个事实：一个算术操作所需要的时间取决于操作数的类型( int, float, double

    等) ，这个事实增加了获得一个精确的计算公式的烦琐程度。所以必须按照数据类型对操作进

    行分类。

    有两个更可行的方法可用来估算运行时间： 1)找出一个或多个关键操作，确定这些关键

    操作所需要的执行时间；2)确定程序总的执行步数。

    2.3.2 操作计数

    估算一个程序或函数的时间复杂性的一种方式就是首先选择一种或多种操作 (如加、乘和

    比较等)，然后确定这种(些)操作分别执行了多少次。这种方法是否成功取决于识别关键操作的

    能力，这些关键操作对时间复杂性的影响最大。下面给出的几个例子都采用了这种方法。

    例2-7 [最大元素] 程序1 - 3 1返回数组a [ 0 : n - 1 ]中最大元素的位置。我们可以根据数组元素之间

    所进行的比较数目来估算其时间复杂性。for 循环中的每一次循环都需要执行一次这样的比较，所以总的比较次数为n - 1。函数M a x还执行了其他的比较(for 循环中的每一次循环之前都要比

    较一下i 和n) ，这些比较没有包含在上述估算之中。其他的操作，比如初始化p o s以及循环控制

    变量i 的每次增值也没有包含在估算之中。如果把这些操作都纳入计数，则操作计数将增加一

    个常量。

    例2-8 [多项式求值] 考察多项式P (x)=

    n

    i = 0

    ci

    x

    n。如果cn

    ≠0，则P 是一个n 维多项式。程序2 - 3可

    用来计算对于给定的值x，P(x)的实际取值。假定根据f o r循环内部所执行的加和乘的次数来

    估算时间复杂性。可以使用维数n 作为实例特征。进入f o r循环的总次数为n，每次循环执行1次

    加法和2次乘法(这种操作计数不包含循环控制变量i 每次递增所执行的加法) 。加法的次数为n，乘法的次数为2 n。

    第2章 程 序 性 能 3 7 下载程序2-3 对多项式进行求值的函数

    template

    T PolyEval(T coeff[], int n, const T x)

    { 计算n次多项式的值，c o e ff [ 0 : n ]为多项式的系数

    T y=1, value= coeff [ 0 ] ;

    for ( int i = 1; i <= n; i++)

    { 累加下一项

    y = x;

    value += y coeff [ i ] ;

    }

    return value;

    }

    Horner 法则采用如下的分解式计算一个多项式：

    P (x) = (…(cn

    x + cn -1) x + cn -2) x + cn -3) x + …) x + c0

    相应的C + +函数见程序2 - 4。采用与程序2 - 3相同的方法，可以估算出该程序的时间复杂性

    为n 次加法和n 次乘法。由于函数PolyEval 所执行的加法数与Horner 相同，而乘法数是H o r n e r

    的两倍，因此，函数Horner 应该更快。

    程序2-4 利用Horner 法则对多项式进行求值

    template

    T Horner(T coeff[], int n, const T x)

    { 计算n次多项式的值，c o e ff [ 0 : n ]为多项式的系数

    T value= coeff [ n ] ;

    for( int i = 1; i <= n; i++)

    value = value x + coeff [ n-i ] ;

    return value;

    }

    例2-9 [计算名次] 元素在队列中的名次(r a n k)可定义为队列中所有比它小的元素数目加上在

    它左边出现的与它相同的元素数目。例如，给定一个数组 a=[4, 3, 9, 3, 7]作为队列，则各元素

    的名次为r =[2, 0, 4, 1, 3]。函数R a n k(见程序2 - 5)可用来计算数组a[0: n-1]中各元素的名次。

    可以根据a的元素之间所进行的比较操作来估算程序的时间复杂性。这些比较操作是由 i f语句来

    完成的。对于i 的每个取值，执行比较的次数为 i ,所以总的比较次数为1 + 2 + 3 +…+n-1 = (n-1)

    n 2。

    程序2-5 计算名次

    template

    void Rank(T a[], int n, int r[])

    { 计算a [ 0 : n - 1 ]中n个元素的排名

    for ( int i = 1; i < n; i++)

    r[i] = 0; 初始化

    逐对比较所有的元素

    for ( int i = 1; i < n; i++)

    for ( int j = 1; j < i; j++)

    3 8 第一部分 预 备 知 识

    下载if (a [j] <= a[ i]) r[ i ] + + ;

    else r[j ] + + ;

    }

    注意在估算时间复杂性时没有考虑for 循环的额外开销、初始化数组r 的开销以及每次比较

    a 中两个元素时对r进行增值的开销。

    例2-10 [按名次排序] 一旦使用程序2 - 5计算出数组中每个元素的名次，就可以利用元素名次按

    照递增的次序对数组中的元素进行重新排列，使得a [ 0 ]≤a [ 1 ]≤…≤a [ n-1 ]。如果能够使用一个

    附加的数组u, 那么可以采用程序2 - 6中给出的函数R e a r r a n g e来重新排列元素的次序。

    在函数R e a r r a n g e执行期间移动元素的次数为2 n。 (练习11要求怎样才能将移动次数减至n) 。

    完成整个排序需要执行(n-1)n 2次比较操作和2 n次移动操作。这种排序方法被称为计数排序

    (rank sort)。另外一种重排元素的函数见程序2 - 11，该函数没有使用附加数组u。

    程序2-6 利用附加数组重排数组元素

    template

    void Rearrange (T a[], int n, int r[])

    { 按序重排数组a中的元素，使用附加数组u

    T u = new T[n+1];

    在u中移动到正确的位置

    for ( int i = 1; i < n; i++)

    u[r[i]] = a[i];

    移回到a中

    for ( int i = 1; i < n; i++)

    a [ i ] = u [ i ] ;

    delete [ ]u;

    }

    例2 - 11 [选择排序] 例2 - 1 0给出了一种按递增次序重排数组a中元素的方法。另外一种可选的方

    法是：首先找出最大的元素，把它移动到 a [ n-1 ]，然后在余下的n-1个元素中寻找最大的元素

    并把它移动到a [ n-2 ]，如此进行下去，这种排序方法为选择排序(selection sort) ，程序2 - 7中给

    出了实现这一过程的C + +函数S e l e c t i o n S o r t，其中函数M a x在程序1 - 3 1中已经给出。可以按照元

    素的比较次数来估算函数的时间复杂性。从例 2 - 7中已经知道每次调用 M a x ( a , s i z e )需要执行

    s i z e-1次比较，所以总的比较次数为1 + 2 + 3 +…+ n-1 = ( n-1 ) n 2。元素的移动次数为3 ( n-1 )。选

    择排序所需要的比较次数与按名次排序(见程序 2 - 1 0)所需要的比较次数相同，但所需要的元

    素移动次数多出5 0 %。本节的后面将介绍另外一种选择排序的方法。

    程序2-7 选择排序

    template

    void SelectionSort (T a[], int n)

    { 对数组a [ 0 : n-1 ]中的n个元素进行排序

    for ( int size = n; size > 1; size- -) {

    int j= Max(a, size);

    S w a p ( a [ j ] , a [ s i z e-1 ] ) ;

    }

    }

    第2章 程 序 性 能 3 9 下载例2-12 [冒泡排序] 冒泡排序(bubble sort)是另一种简单的排序方法。这种排序采用一种

    “冒泡策略”把最大元素移到右部。在冒泡过程中，对相邻的元素进行比较，如果左边的元素

    大于右边的元素，则交换这两个元素。假定我们有四个元素 [ 5 , 3 , 7 , 1 ]。首先对5和3进行比较并

    交换，得到[ 3 , 5 , 7 , 1 ]，然后对5和7进行比较，两者无须交换，接下来比较 7和1并交换，得到

    [ 3 , 5 , 1 , 7 ]。在一次冒泡过程结束后，可以确信最大的元素肯定在最右边的位置上。函数

    B u b b l e (见程序2 - 8 )执行一次冒泡过程，其中元素比较的次数为n-1。

    程序2-8 一次冒泡

    template

    void Bubble (T a[], int n)

    { 把数组a [ 0 : n-1 ]中最大的元素通过冒泡移到右边

    for ( int i = 0; i < n-1; i++)

    if( a[i] > a[i +1]) Swap(a[i], a[i + 1 ] ) ;

    }

    由于函数B u b b l e可以把最大的元素移到最右边，因此可以用它来替换 S e l e c t i o n S o r t中的

    M a x，从而得到一个新的排序函数(见程序 2 - 9) 。在新函数中，元素比较的次数为 ( n - 1 ) n 2，与函数S e l e c t i o n S o r t相同。

    程序2-9 冒泡排序

    template

    void BubbleSort (T a[], int n)

    { 对数组a [ 0 : n-1 ]中的n个元素进行冒泡排序

    for ( int i = n; i>1; i- -)

    B u b b l e ( a , i ) ;

    }

    最好、最坏和平均操作数

    到目前为止，在给出的例子中所使用的实例特征都很简单(如输入数和 或输出数) ，操作

    计数都是这些特征的良性函数(nice function) 。如果把其他的一些操作也计算在内，其中有些

    例子就可能变得很复杂了。例如，由 B u b b l e (见程序2 - 8 )所执行的交换次数不仅依赖于问题 n，而且依赖于数组a 中的具体值。交换次数可在0到n-1之间变化。由于操作计数不总是由所选择

    的实例特征唯一确定，那么我们可能会问，最好的、最坏的和平均的操作数分别是多少。下面

    就来讨论这个问题。

    令P 是一个程序。假定把操作计数OP

    (n1

    , n2

    , ..., nk) 视为实例特征n1

    , n2

    , ..., nk

    的函数。对于

    任意程序实例I, 令o p e r a t i o nP

    (I ) 为该实例的操作计数，令S (n1

    , n2

    , ..., nk) 为集合{I |I 具有特征

    n1

    , n2

    , ..., nk

    }。则P最好的操作计数为：

    OP

    B C

    (n1

    , n2..., nk) = m i n { o p e r a t i onP

    (I ) | I∈S(n1

    , n2

    , ..., nk) }

    P最坏的操作计数为：

    OP

    W C

    (n1

    , n2..., nk) =m a x { o p e r a t i o nP

    (I ) | I∈S(n1

    , n2

    , ..., nk) }

    P平均或期望的操作计数为：

    4 0 第一部分 预 备 知 识

    下载公式OP

    AV G

    假定所有的I∈S都是完全相似的实例，否则该公式必须修改为：

    其中p (I ) 是实例I 可以被成功解决的概率(=次数 |S(n1

    , n2

    , ..., nk) |) 。

    确定平均操作数通常是十分困难的，因此，在下面的几个例子中，仅分析最好和最坏的操

    作数。

    例2-13 [顺序搜索] 在执行程序2 - 1顺序搜索的代码期间，我们想知道x 与a 中元素之间的比较

    次数，一个很自然的实例特征就是 n。不幸的是，比较的次数不是由 n 唯一确定的。例如，如

    果n = 1 0 0且x = a [ 0 ]，那么仅需要执行一次操作；如果x 不等于a 中的任何一个元素，则需要执行

    1 0 0次比较。

    当x 是a 中的一员时称查找是成功的，其他情况都称为不成功查找。每当进行一次不成功

    查找，就需要执行n 次比较。对于成功查找来说，最好的比较次数是 1，最坏的比较次数为n。

    为了计算平均查找次数，假定所有的数组元素都是不同的，并且每个元素被查找的概率是相同

    的。成功查找的平均比较次数如下：

    例2-14 [向有序数组中插入元素] 程序2 - 1 0向一个有序数组a [ 0 : n - 1 ]中插入一个元素。a中的元

    素在执行插入之前和插入之后都是按递增顺序排列的。例如，如果向数组a[0:5] = [1, 2, 6, 8, 9,11 ]中插入4，所得到的结果为a[0:6] = [1, 2, 4, 6, 8, 9, 11 ]。当我们为新元素找到欲插入的位置

    时，必须把该位置右边的所有元素分别向右移动一个位置。对于本例，需要移动 11, 9, 8和6，并把4插入到新空出来的位置a [ 2 ]中。

    程序2-10 向一个有序数组中插入元素

    template

    void Insert(T a[], int n, const T x)

    { 向有序数组 a [ 0 : n-1 ]中插入元素x

    假定a 的大小超过 n

    int i;

    for (i = n-1; i >= 0 x < a[i]; i- -)

    a[i+1] = a[i];

    a[i+1] = x;

    n++; 添加了一个元素

    }

    现在我们想知道执行程序2 - 1 0时，x 与a 中元素之间的比较次数。一个很自然的实例特征

    就是初始数组a 的大小n。最好或最少的比较次数为1，这种情况发生在x被插入到数组尾部的

    时候。最大的比较次数为n，这发生在x 被插入到a 的首部之时。为了估算平均比较次数，假定

    x 有相等的机会被插入到任一个可能的位置上(共有 n + 1个可能的插入位置) 。如果x 最终被插

    入到a 的i + 1处，i≥0，则执行的比较次数为n - i。如果x 被插入到a [ 0 ]，则比较次数为n。所以平

    均比较次数为：

    第2章 程 序 性 能 4 1 下载例2-15 [再看按名次排序] 假定已经使用函数R a n k (见例2 - 9中的程序2 - 5 )计算出一个数组中每

    个元素的名次，可以在原地把该数组中的元素按序重排，方法是从 a[0] 开始，每次检查一个元

    素。如果当前正在检查的元素为a[i] 且r [ i ] = i，那么可以跳过该元素，继续检查下一个元素；如

    果r [ i ]≠i, 可以把a [ i ]与a[r[i]] 进行交换，交换的结果是把原a[i] 中的元素放到正确的排序位置

    (r [ i ])上去。这种交换操作在位置i 处重复下去，直到应该排在位置i 处的元素被交换到位置i

    处。之后，继续检查下一个位置。程序2 - 11给出了原地重排数组元素的函数R e a r r a n g e。

    程序2 - 11 原地重排数组元素

    template

    void Rearrange(T a[], int n, int r[])

    { 原地重排数组元素

    for (int i = 0; i < n; i++)

    获取应该排在a [ i ]处的元素

    while (r[i] != i) {

    int t = r[i];

    Swap(a[i], a[t]);

    Swap(r[i], r[t]);

    }

    }

    程序2 - 11执行的最少交换次数为0(初始数组已经是按序排列) ，最大的交换次数为2 (n-1) 。

    注意每次交换操作至少把一个元素移到正确位置(如a [ i ]) ，所以在n-1次交换之后，所有的n个

    元素已全部按序排列。因此，在最好的情况下，交换次数为 0，最坏情况下为2 ( n-1 ) (包括名次

    交换)。当使用本函数来代替程序2 - 6中的函数时，最坏情况下所需要的执行时间将增加，因为

    需要移动更多的元素(每次交换需要移动三次) ，不过程序所需要的内存减少了。

    例2-16 [再看选择排序] 程序2 - 7中选择排序函数的一个缺点是：即使元素已经按序排列，程序

    仍然继续运行。例如，即使在第二次循环过后数组元素可能已经按序排列， f o r循环仍需要执

    行n - 1次。为了终止不必要的循环，在查找最大元素期间，可以顺便检查数组是否已按序排列。

    程序2 - 1 2给出了一个按照这种思想实现的选择排序函数。在该函数中，把查找最大元素的循环

    直接与函数S e l e c t i o n S o r t合并在一起，而不是把它作为一个独立的函数。

    程序2-12 及时终止的选择排序

    template

    void SelectionSort(T a[], int n)

    { 及时终止的选择排序

    bool sorted = false;

    for (int size = n; !sorted (size > 1); size- -) {

    int pos = 0;

    sorted = true;

    找最大元素

    for (int i = 1; i < size; i++)

    if (a[pos] <= a[i]) pos = i;

    else sorted = false; 未按序排列

    Swap(a[pos], a[size - 1 ] ) ;

    4 2 第一部分 预 备 知 识

    下载}

    }

    对于程序2 - 1 2中的函数，其最好的情况出现在数组 a最初已是有序数组的情形，此时，外

    部f o r循环仅执行一次，a 中元素之间的比较次数为n-1。在最坏的情况下，外部f o r循环一直循

    环到s i z e = 1，执行的比较次数为(n-1)n 2。最好和最坏情况下的交换次数与程序2 - 7完全相同。

    注意在最坏的情况下，程序2 - 1 2可能要略微慢一些，因为它必须进行变量维护的额外工作。

    例2-17 [再看冒泡排序] 与选择排序的情形一样，可以重新设计一个及时终止的冒泡排序函数。

    如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列，没有必要再继续进行冒

    泡过程。程序2 - 1 3给出了一个及时终止的冒泡排序函数。在最坏情况下所执行的比较次数与原

    来的函数(见程序2 - 9)一样。在最好情况下比较次数为n-1。

    程序2-13 及时终止的冒泡排序

    template

    bool Bubble(T a[], int n)

    { 把 a[0:n-1] 中最大元素冒泡至右端

    bool swapped = false; 尚未发生交换

    for (int i = 0; i < n - 1; i++)

    if (a[i] > a[i+1]) {

    Swap(a[i], a[i + 1]);

    swapped = true; 发生了交换

    }

    return swapped;

    }

    template

    void BubbleSort(T a[], int n)

    { 及时终止的冒泡排序

    for (int i = n; i > 1 Bubble(a, i); i- -) ;

    }

    例2-18 [插入排序] 程序2 - 1 0可以作为一个排序函数的基础。因为只有一个元素的数组是一个

    有序数组，所以可以从仅包含欲排序的n 个元素的第一个元素的数组开始。通过把第二个元素

    插入到这个单元数组中，可以得到一个大小为 2的有序数组。插入第三个元素可以得到一个大

    小为3的有序数组。按照这种方法继续进行下去，最终将得到一个大小为 n的有序数组，这种排

    序方式为插入排序(insertion sort) ，函数InsertionSort (见程序2-14) 正是按照这种思想实现的。

    为此，重写了函数Insert (见程序2 - 1 0 )，因为它执行了一些不必要的操作。实际上，还可以把

    Insert 的代码直接嵌入到函数InsertionSort 之中， 从而得到另外一个插入排序函数 (见程序2 - 1 5) 。

    等价地，也可以把函数Insert 作为一个内联(i n l i n e)函数。注意，如果用代码Insert (a, i, a[i])

    取代InsertionSort 函数中的for 循环体，则程序将无法运行，因为I n s e r t的形式参数是一个引用

    参数。

    程序2-14 插入排序

    template

    void Insert(T a[], int n, const T x)

    第2章 程 序 性 能 4 3 下载{ 向有序数组 a [ 0 : n - 1 ]中插入元素x

    int i;

    for (i = n-1; i >= 0 x < a[i]; i- -)

    a[i+1] = a[i];

    a[i+1] = x;

    }

    template

    void InsertionSort(T a[], int n)

    { 对 a [ 0 : n-1 ]进行排序

    for (int i = 1; i < n; i++) {

    T t = a[i];

    Insert(a, i, t);

    }

    }

    程序2-15 另外一种插入排序

    template

    void InsertionSort(T a[], int n)

    for (int i = 1; i < n; i++) {

    将a [ i ]插入a [ 0 : i-1 ]

    T t = a[i];

    int j ......