Data Structure, Algorithm,and Applications in C++

在学习这本书进阶内容之前，我们可以跟着它的第一章部分再巩固和复习。本书由Sartaj Sahni撰写，由王立柱和刘志红翻译。全书通俗易懂，内容丰富，是巩固C++内容的不二选择。希望本文对各位有所帮助。

目录

1.函数与参数

1.1.传值参数

1.2.模板函数

1.3.引用参数

1.4.常量引用参数

1.5.返回值

1.6.重载函数

1.7.练习

2.异常

2.1.抛出异常

2.2.处理异常

2.3.练习

3.动态内存空间分配

3.1.操作符new

3.2.一维数组

3.3.异常处理

3.4.操作符delete

3.5.二维数组

4.自有数据类型

4.1.类 currency

4.2.一种不同的描述方法

4.3.操作符重载

4.4.友元和保护性类成员

4.5.增加#ifndef、#define和#endif语句

5.异常类illegalParameterValue

6.递归函数

6.1.递归的数学函数

6.2.归纳

6.3.C++递归函数

7.标准模板库

7.1.accumulate

7.2.copy和next_permutation

---

1.函数与参数

1.1.传值参数

对于普通的传值参数，我们已经司空见惯了我们一般只要对相应的函数体传入形参，在执行的main函数主体中传入实参就可以调用相应的内容。在运行时，函数体在执行前，把实参复制给形参，复制的过程是由形参类型的复制构造函数来完成的。如果实参和形参的类型不一致，那么就必须进行类型转换，把实参转化为形参的类型，前提也很明确，那就是该类型转换是允许的。在函数结束，系统会调用形参类型的析构函数来释放形式参数。当函数运行结束以后，那么形参的只就不会复制到实参当中去。因此，也就是我们所说的单向值传递。当然，在我们所学习的类与对象板块中，我们也知道了类内的方法就很类似于我们的函数，而且我们还能自己进行编写构造函数和析构函数。

1.2.模板函数

float abc(float a, float b, float c)
{return a + b * c;
}

这种形式过于拘泥，被数据类型限制了，所以我们可以使用模板，对相应的形参进行替换，当我们调用同一个方法的时候，我们就无须再多虑它的数据类型了。

template<class T>
T abc(T a, T b, T c)
{return a + b * c;
}

1.3.引用参数

在使用上面的模板函数时，会增加不少时间开销，这实际上就是因为要重新开辟空间复制形参的原因。而且传入的数据越多，它的负担也就越大，也就导致了相应的时间、空间双重损失。这时候，我们就要是使用引用来减少这种时间和空间上的损失。

template<class T>
T abc(T& a, T& b, T& c)
{return a + b * c;
}

引用的好处就是将原来的形参复制形式转变为了实参直接调用，当然这个函数返回时，也就不会调用析构函数。

1.4.常量引用参数

C++还提供另外一种参数传递模式——常量引用。这种模式指明的引用参数不能被函数修改。这个名字实际上就已经暗示了这一点了，之前我们遇到的常变量、常量指针，都是使用了const，是相应的数值转变为一个不可更改的左值。

template<class T>
T abc(const T& a, const T& b, const T& c)
{return a + b * c;
}

用关键字const来指明函数不可修改的引用参数，在软件工程上具有重要的意义。函数头会告诉用户该函数是不能修改实参的。

改成更通用的版本就是：

template<class Ta, class Tb, class Tc>
T abc(const Ta& a, const Tb& b, const Tc& c)
{return a + b * c;
}

1.5.返回值

一个函数可以返回一个值、一个引用或者一个常量引用。在这种情况下，返回的值会被复制到调用环境中去，也就是我们获得了我们调用函数之后想要得到的那个结果。

1.6.重载函数

一个函数的签名是由这个函数的形参类型以及形参个数所确定的。C++可以定义两个或多个同名函数，但是两个同名函数不能有相同的签名。定义多个同名函数的机制，就是我们所说的函数重载。

int abc(int a, int b, int c)
{return a + b * c;
}
​
float abc(float a, float b, float c)
{return a + b * c;
}
​
int abc(int a, int b)
{return a + b;
}

1.7.练习

练习1：交换函数为什么失败，这是因为这是单向值传递，形参复制了实参，但是无法对实参进行修改，函数运行结束，该形参也被回收了。

练习2：编写一个模板函数count，返回值是数组a[0:n-1]中value出现的次数。

#include<iostream>
using namespace std;
#define N 20
template<class Ta, class Tb, class Tc>int count(Ta& arr, Tb& n, Tc& value)
{int count = 0;for(int i = 0;i < n; i++){if(arr[i] == value){count++;}}return count;
}
​
void menu()
{cout << "使用int 类型————1" << endl;cout << "使用char类型————2" << endl;
}
​
int main()
{int n, arr[N];char arr1[N];cout << "输入个数为：";cin >> n;int value;char value1;int number;menu();cout << "输入类型：";while(1){int val;cin >> val;if(val == 1){for(int i = 0;i < n; i++){cin >> arr[i];}cout << "要查询的值：";cin >> value;number = count(arr, n, value);break;}else if(val == 2){for(int i = 0;i < n; i++){cin >> arr1[i];}cout << "要查询的值：";cin >> value1;number = count(arr1, n, value1);break;}else {cout << "输入错误，请重新输入：";}}cout << "该值个数为：" << number << endl;return 0;
}

练习3：编写一个模板函数fill，给数组a[start:end-1]赋值value

#include<iostream>
using namespace std;
#define N 20
template <class Ta, class Tb, class Tc>
void fill(Ta& arr, Tb& start, Tb& n, Tc& value)
{for(int i = start;i < n; i++){arr[i] = value;}
}
​
int main()
{int arr[N];int n;cout << "输入个数：";cin >> n;for(int i = 0;i < n; i++){arr[i] = i;}int start;while(1){cout << "输入起始位置：";cin >> start;if(start >= 0 && start < n){break;}}int value;cout << "复制的内容为：";cin >> value;fill(arr, start, n, value);cout << "复制后的代码：" << endl;for(int i = 0;i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

此处可以将主函数中的int arr[N]改为char arr[N]之类的类型从而实现类型的差异，或者说也可以像上面的那道题一样准备多个选项进行实现内容。

练习4：编写一个模板函数inner_product，返回值是a[i]*b[i]的总和。

#include<iostream>
using namespace std;
#define N 20
​
template <class T>
T inner_product(T& a, T& b)
{return a * b;
}
​
void test()
{int a[N],b[N];int n;int Count = 0;cout << "请输入数据个数：";cin >> n;for(int i = 0;i < n; i++){cout << "输入a数组的值：";cin >> a[i];}for(int i = 0;i < n; i++){cout << "输入b数组的值：";cin >> b[i];}for(int i = 0;i < n; i++){Count += inner_product(a[i], b[i]); }cout << "Sum的数据：" << Count << endl;
}
​
int main()
{test();return 0;
}

练习5：编写一个模板函数iota，使a[i]=value+i，0≤i＜n。

#include<iostream>
using namespace std;
#define N 20
​
template<class Ta, class Tb>
Ta iota(Ta& i, Tb& value)
{return i + value;
}
​
void test()
{int a[N];int n, value;cout << "请输入个数：";cin >> n;cout << "请输入value值：";cin >> value;for(int i = 0;i < n; i++){a[i] = iota(i, value);}for(int i = 0;i < n; i++){cout << a[i] << " ";}cout << endl;
}
​
int main()
{test();return 0;
}

练习6：编写一个模板函数is_sorted，当且仅当a[0:n-1]有序时，返回值是true。

#include<iostream>
using namespace std;
#define N 20
​
template<class Ta, class Tb>
bool is_sorted(Ta& a, Tb& n)
{for(int i = 1;i < n; i++){if(a[i] < a[i-1])return false;}return true;
}
​
void test()
{int a[N];int n;cout << "输入个数：";cin >> n;for(int i = 0;i < n; i++){cout << "输入数据：";cin >> a[i];}bool j = is_sorted(a, n);if(j == true) cout << "从小到大升序排列" << endl;else cout << "非升序排列" << endl;
}
​
int main()
{test();return 0;
}

练习7：编写一个模板函数mismatch，返回值是使不等式a[i]不等于b[i]成立的最小的索引i，i在0到n之间。

#include<iostream>
using namespace std;
#define N 20
template<class Ta, class Tb>
​
int mismatch(Ta& a, Ta& b, Tb& n)
{for(int i = 0;i < n; i++){if(a[i] != b[i])return i;}return -1;
}
​
int main()
{int a[N], b[N];int n;cout << "输入个数：";cin >> n;for(int i = 0;i < n; i++){cout << "输入a数组：";cin >> a[i];}for(int i = 0;i < n; i++){cout << "输入b数组：";cin >> b[i];}int num = mismatch(a, b, n);if(num == -1) cout << "ab数组完全相等" << endl;else cout << "第一个不相同的下标是：" << num << endl;return 0;
}

2.异常

2.1.抛出异常

异常是表示程序出现错误的信息。比如说b/c，当c=0时，这就是一个错误。对于这个错误，C++检查不出来，但是硬件会检查出来，并抛出一个异常。同样的，当我们学习Python的时候已经接触过它的异常，并做了一些预防措施和代码。

我们可以编写这样的C++程序，它可以对一些异常的情况进行检查，而且当查出一个异常的时候，就抛出这个异常。就如下面的代码一样，程序函数abc可以定义，仅当三个参数都大于0时才进行，只要有一个或多个为0的值，就可以抛出异常，而这个程序抛出的异常类型是char*。

int abc(int a, int b, int c)
{if(a <= 0 || b <= 0 || c <= 0){throw "All parameters should be > 0";}return a + b * c;
}

程序可能抛出的异常有很多，比如0除数、非法参数值、非法输入值、数组下标越界等。如果对每一种类型异常都定义一个异常类，那么异常的处理就有很大灵活性。

2.2.处理异常

一段代码抛出的异常由包含这段代码的try块来处理。紧跟在try之后的是catch块。每一个catch块都有一个参数，参数的类型决定了这个catch块要捕捉的异常类型。

//块
catch(char * e){}
//捕捉的异常类型是char*，而块
catch(bad_alloc e){}
//捕捉的异常类型是bad_alloc
catch(exception & e){}
//捕捉的异常类型是基类型exception以及所有从exception派生的类型（例如bad_alloc和bad_typeid）
catch(...){}

catch块一般包含异常改正之后所恢复的代码。如果不能恢复，那么catch块的代码输出错误的信息。

int main()
{try {cout << abc(2,0,5) << endl};catch(char* e){cout << "The parameters to abc were 2, 0, and 5" << endl;cout << "An exception has been throw" << endl;cout << e << endl;return 1;}return 0;
}
​
//输出结果：
The parameters to abc were 2, 0, and 5
An exception has been throw
All parameters should be > 0

abc函数抛出一个类型为char*的异常。这个异常使函数abc还没有计算表达式的值就停止了。块try也立即停止了，其中的cout语句没有执行完。因为抛出的异常与catch块的参数e是同一种类型，所以异常被这个catch块捕捉，e的赋值是抛出的异常，然后进入catch块。

2.3.练习

练习1：修改上面的程序，使抛出的异常类型是整型。如果a、b、c都小于0，那么抛出的异常值是1；如果a、b、c都等于0，那么抛出的异常值为2；否则没有异常。编写一个主函数，应用修改后的代码；若有异常抛出，则捕捉异常，根据异常值输出信息。

#include<iostream>
using namespace std;
​
int panduan(int a, int b, int c)
{if(a == 0 && b == 0 && c == 0)return 2;else if(a < 0 && b < 0 && c < 0)return 1;else return 0;
}
​
int main()
{int a, b, c;cout << "依次输入a、b、c：";cin >> a >> b >> c;int flag = panduan(a, b, c);catch(flag)return 0;
}

3.动态内存空间分配

3.1.操作符new

C++操作符new用来进行动态存储分配或者运行时存储分配，它的值是一个指针，指向所分配的空间.

#include<iostream>
using namespace std;
int main()
{int * y = new int;*y = 10;//或者可以用如下方式直接进行操作int * x = new int(10);//或者第三种方式int * z;z = new intreturn 0;
}

3.2.一维数组

许多函数中都要用到一维和二维数组，这些数组的大小在编译的时侯可能还是未知的，它们随着函数的调用的变化而变化，因此对这些数组只能进行动态存储分配。

为了在运行时创建一个一维浮点数组，必须把x声明为一个浮点型指针，然后为数组分配充足的空间

#include<iostream>
using namespace std;
int main()
{int n;cin >> n;float * x = new float[n];return 0;
}

使用操作符new为n个浮点数分配了存储空间，并返回第一个浮点数空间的指针。对每个数组的元素的访问都可以使用x[0]，x[1]，x[2]，......，x[n-1]的形式。

3.3.异常处理

#include<iostream>
using namespace std;
int main()
{float * x;try{x = new float [n]};catch(bad_alloc e){cerr << "Out of Memory" << endl;exit(1);}return 0;
}

如果计算机没有充足空间对float数组进行分配时，就会捕捉到异常，主动弹出异常问题，抛出一个bad_alloc的异常，并终止程序利用try-catch结构进行相应的操作

3.4.操作符delete

动态内存的存储空间不再需要时相应的需要进行空间释放，释放的空间可以重新用来动态分配，C++操作符delete用来释放操作符new所分配的空间。

#include<iostream>
using namespace std;
int main()
{int * x = new int(10);delete x;return 0;
}

3.5.二维数组

虽然C++采用多种机制来说明二维数组，但这些机制大多数要求在编译阶段就知道而二维数组的大小。具体来说，使用这些机制很难编写出相应的函数，它的形参是一个第二维大小未知的二维数组。这是因为当形参是二维数组时，必须指定第二维的大小。例如，a[][10]是一个合法的定义，但是a[][]不合法。

而克服这一问题的最佳方法就是采用动态内存分配的形式。

#include<iostream>
using namespace std;
int main()
{int n;cin >> n;char(*c)[5];try{c = new char[n][5];}catch(bad_alloc){cerr << "Out of Memory" << endl;exxit(1);}return 0;
}

在运行时，行数n要么是用户自行输入的，要么就是通过计算确定的，如果数组1的列数在编译阶段是未知的话，那么就不能只调用一次new就能创建二维数组（即使数组的行数是已知的）。要构建这样的二维数组，可以把它看做是由若干行所构成的结构，每一行都是一个能用new来创建的一维数组。指向每一行的指针保存在另外一个一位数组之中。

一个3*4的数组：

x[0]、x[1]、x[2]分别指向第0行、第1行、第2行的首元素，如归x是一个字符数组，那么x[0:2]是指向字符的指针，而x本身就是一个指向指针的指针，x的声明语法：char **x;

#include<iostream>
using namespace std;
template <class T>
bool makeArray(T ** &x, int numberOfRows, int numberOfColumns)
{//创建一个二维数组try{//创建行指针x = new T * [numberOfRows];//为每一行分配空间for(int i = 0;i < numberOfRows; i++){x[i] = new int [numberOfColumns];}return true;}catch (bad_alloc) {return false};
}
​
​
int main()
{int numberOfRows, numberOfColumns;cout << "输入行：";cin >> numberOfRows;cout << "输入列：";cin >> numberOfColumns;char ** x;makeArray(x, numberOfRows, numberOfColumns);//释放空间void deleteArray()return 0;
}

创建一个类型为T的二维数组。这个数组的行数是numberOfRows，列数是numberOfColumns。程序首先为指针x[0]，......，x[numberOfRows-1]申请空间，然后为数组的每一行申请空间。在程序中操作符new被调用了numberOfRows+1次。如果new的某一次调用发生了异常，程序控制将转移到catch块，并返回false。而每一次new的调用都没有任何问题的话，那么数组就创建成功。函数返回true。对于创建的数组x，每个元素都可以使用标准的下标法x[i][j]来引用。0≤i＜numberOfRows, 0≤j＜numberOfColumns。

我们分两步来释放这个二维数组空间首先释放放在for循环中为每一行所分配的空间，然后释放为行指针所分配的空间。x被指为NULL，防止用户继续访问已经释放的空间。

template <class T>
void deleteArray(T ** &x, int numberOfRows)
{//删除二维数组xfor(int i = 0;i < numberOfRows; i++){delete [] x[i];}delete [] x;x = NULL;
}

4.自有数据类型

4.1.类 currency

C++语言支持诸如int、float、和char这样的数据类型。而书本上的许多应用的数据类型是C++不支持的，需要自己定义。定义自有数据类型最灵活的方式就是使用C++的类（class）结构。

假设你想处理货币类型currency的对象（也称实例），这种对象有三个成员：符号+-、美元和美分。对于这些对象我们想要执行的操作如下：

1. 给成员赋值

2. 确定成员值（即符号、美元数和美分数）

3. 两个对象相加

4. 增加成员值

5. 输出

currency类声明：

class currency
{
public://构造函数currency(signType theSign = plus,unsigned long theDollar = 0,unsigned int theCents = 0);//析构函数~currency(){};void setValue(signType, unsigned long, unsigned int);void setValue(double);signType getSign() const {return sign;}unsigned long getDollars() const {return dollars;}unsigned int getCents() const {return cents;}currency add(const currency&) const;currency& increment(const currency&);void output() const;
private:signType sign;//符号unsigned long dollars;//美元unsigned int cents;//美分
};

类的成员声明有两个部分：公有（public）和私有（private），其实还有一个保护（protect）。公有部分所声明的是用来操作类对象（或实例）的成员函数（又称方法）。对类的用户是可见的，是用户与类对象进行交互的唯一手段。私有部分所声明的是用户不可见的数据成员（如简单变量、数组及其他可赋值的结构）和成员函数。通过公有和私有以及保护部分，我们可以让用户只看到他们所看到的部分，同时把其余的部分隐藏起来，这部分通常是与实现细节有关内容。

尽管C++语法可以在公有部分声明数据成员，但是优秀的软件设计者不会这样做。

上面代码中，公有部分的第一个成员函数与类名相同，这种名称与类名相同的成员函数称为构造函数（construction）。构造函数指明了创建一个类对象的方法，而且没有返回值。~加上类名的这种成员函数被称为析构函数（destructor），每当一个类对象超出作用域的时候，析构函数就会自动调用来删除这个对象。

在创建一个class类对象，如果没有构造函数，系统会自动调用空的构造函数，同理，如果没有析构函数，那么也会自动调用回收的系统析构函数。

创建currency类对象的方式有如下两种：

currency f, g(plus, 3, 45), h(minus, 10);
currency *m = new currency(plus, 8, 12);

调用成员函数的方式有：

g.setValue(minus, 33, 0);
h.setValue(20.52);

其中的g和h是currency的类对象，也是函数的赋值对象。而所定义的类对象的关键字const是指这些函数值不会改变调用对象的值。我们把这种成员函数叫做常量函数（constant function）。

当然这里复制构造函数（copy constructor）没有在代码中实现。C++将使用缺省复制构造函数，仅仅复制数据成员。对于这个currency类而言，缺省复制构造函数已经足够了，但是对于很大一部分类，我们最好还是在堆上空间进行开辟空间，也就是自己去定义一个复制构造函数来进行复制数据，缺省复制构造函数已经无法满足程序需要了。

currency的构造函数：

currency::currency(signType theSign, unsigned long theDollars, unsigned int theCents)
{//创建一个currency类对象setValue(theSign, theDollars, theCents);
}

成员函数如果不在类声明体内部实现，而在外部实现，就必须要使用作用域说明符（scope resolution operator）::以指明该函数是currency类的成员函数。因此currency::currency表示currency类的构造函数，而currency::output这表示currency类的output成员函数。

给私有数据成员赋值：

void currency::setValue(signType theSign, unsigned long theDollars, unsigned int theCents)
{//给调用对象的数据成员赋值if(theCent > 99)throw illegalParameterValue("Cents should be < 100");sign = theSign;dollars = theDollars;cents = theCents;
}
​
void currency::setValue(double theAmount)
{//给调用对象的数据成员赋值if(theAmount < 0){sign = minus;theAmount = -theAmount;}else sign = plus;dollars = (unsigned long) theAmount;//提取整数cents = (unsigned int) ((theAmount + 0.001 - dollars) * 100);//提取两位小数
}

这是两个成员函数setValue的代码。第一个成员函数验证参数值的合法性，只有当参数合法了，才能拿来给调用函数的私有数据成员赋值。如果参数不合法，就抛出一个类型为illeaglParametervalue的异常。第二个函数参数不验证参数值的合法性，仅用小数点后面头两位数字。

但是我们知道，用计算机来表示一些小数是不够精确的，比如说，5.29用计算机表示是5.2899，那么加上0.001，在通过强制转换，把它转换为整型，那么再通过*100的操作就可以拿到相应的数据啦。

把两个currency对象的值相加：

currency currency::add(const currency& x) const
{//把x和*this相加long a1, a2, a3;currency result;//把调用对象转化为符号整数a1 = dollars * 100 + cents;if(sign == minus) a1 = -a1;//把x转化为符号整数a2 = x.dollars * 100 + x.cents;if(x.sign == minus) a2 = -a2;a3 = a1 + a2;//转换为currency对象的表达式if(a3 < 0){result.sign = minus;a3 = -a3;}else result.sign = plus;result.dollars = a3 / 100;result.cents = a3 - result.dollars * 100;return result;
}

上述程序是方法add的代码，它首先把要相加的两个对象转化为整数，如$2.32转换为232。引用调用对象的数据成员与引用对象x的数据成员在语法上是有区别的。x.dollars指的是x的数据成员，而前面没有对象名称的dollars指的是调用对象的数据成员。当方法add终止时，局部变量a1、a2、a3和ans被析构函数删除，它们的空间也均被释放。

函数increment和output：

currency& currency::increment(const currency& x)
{//增加x*this = add(x);return *this;
}
​
void currency::output() const
{//输出调用对象的值if(sign == minus) cout << '-';cout << '$' << dollars << '.';if(cents < 10) cout << '0';cout << cents;
}

在C++中，保留关键字this指向调用对象，*this就是调用对象。以调用语句g.increment(h)为例，方法increment第一行语句调用公有函数add，它把x（即h）与调用对象g相加，然后把相加的结果作为返回值，赋值给 *this，而 *this就是g。我们使用了返回引用，这样就省略返回值的复制过程。

类currency的数据成员已经设为私有（private），类的用户不能直接访问这些成员。因此，用户通过下列的语句可以直接改变私有数据成员的值：

h.cents = 20;
h.dollars = 100;
h.sign = plus;

如果数据成员在处理之前是有效的，而且经过成员函数处理之后仍然是有效的，那么我们就能保证它们在经过用户程序处理之后依然是有效的，因为用户程序是通过成员函数来处理数据成员的。构造函数和成员函数setValue的代码在使用数据之前都要验证它的有效性。而其余的函数特性是：如果数据在处理之前有效，那么在处理之后仍然是有效的。

类currency的应用：

#include<iostream>
#include"currency.h"
using namespace std;
​
int main()
{currency g, h(plus, 3, 50), i, j;//使用两种形式的setValue来赋值g.setValue(minus, 2, 25);i.setValue(-6.45);//调用成员函数add和outputj = h.add(g);h.output();cout << " + ";g.output();cout << " = ";j.output();cout << endl;//连续调用两次成员函数addj = i.add(g).add(h);//省略了输出语句//测试异常cout << "Attempting to initalize with cents = 152" << endl;try{i.setValue(plus, 3, 152);}catch(illegalParameterValue e){cout << "Caught thrown exception" << endl;e.outputMessage();}return 0;
}

这段代码假定类声明和类实现都在文件currency.h之中，但是这种分置对后续章节要引入的大量模板函数和模板类是行不通的。

4.2.一种不同的描述方法

假设已经有很多应用程序采用我们上面的currency类的形式，现在我们想要修改对currency类对象的数据描述，是应用最多的两个成员函数add和increment运行更快，进而提高应用程序的执行速度。因为用户仅仅通过公有部分所提供的的接口与currency类进行交互，所以对私有部分的修改不会影响应用程序的正确性。因此，私有部分修改，而应用程序不用改。

类currency的新声明：

class currency
{
public://构造函数currency(signType theSign = plus,unsigned long theDollars = 0,unsigned int theCents = 0);//析构函数~currency(){}void setValue(signType, unsigned long, unsigned int);void setValue(double);signType getSign() const{if(amount < 0) return minus;else return plus;}unsigned long getDollars() const{if(amount < 0) return (-amount) / 100;else return amount / 100;}unsigned int getCents() const{if(amount < 0) return -amount - getDollars() * 100;else retrun amount - getDollars() * 100;}currency add(const currency&) const;currency& increment(const currency& x){amount += x.amount;return *this;}void output() const;
private:long amount;
};

构造函数和成员函数setValue的新代码：

currency::currency(sigeType theSign, unsigned long theDollars, unsigned int theCents)
{//创建一个currency类对象setValue(theSign, theDollars, theCents);
}
​
void currency::setValue(signType theSign, unsigned long theDollars, unsigened int theCents)
{//给调用对象赋值if(theCents > 99)//美分值太大throw illegalParamenterValue("Cents should be < 100");amount = theDollars * 100 + theCents;if(theSign == minus) amount = -amount;
}
​
void currency::setValue(double theAmount)
{//给调用对象赋值if(theAmount < 0)amount = (long) ((theAmount - 0.001) * 100);elseamount = (long) ((theAmount + 0.001) * 100);//取两个十位数
}

成员函数add和output的新代码：

currency currency::add(const currency& x) const
{//把x和*this相加currency y;y.amount = amount + x.amount;return y;
}
​
void currency::output() const
{//输出调用对象的值long theAmount = amount;if(theAmount < 0){cout << '-';theAmount = -theAmount;}long dollars = theAmount / 100;cout << '$' << dollars << '.';int cents = theAmount - dollars * 100;if(cents < 10) cout << '0';cout << cents << endl;
}

4.3.操作符重载

类currency有若干成员函数和C++标准操作符类似。例如，add实施的是+操作，increment实施的是+=操作。使用这些标准的C++操作符比定义新的诸如add和increment的成员函数要自然多得多。为了使用这些操作符+和+=，我们进行操作符重载（operator overloading），它可以扩大C++操作符的应用范围，使其操作新的数据类型或类。

包含操作符重载的类声明：

class currency
{
public://构造函数currency(signType theSign = plus,unsigned long theDollars = 0,unsigned int theCents = 0);//析构函数~currency(){};void setValue(signType, unsigned long, unsigned int);void setValue(double);signType getSign() const{if(amount > 0) return (-amount) / 100;else return amount / 100;} unsigned int getCents() const{if(amount < 0) return -amount - getDollars() * 100;else return amount - getDollars() * 100;}currency operator+(const currency&) const;currency& operator+=(const currency& x){amount += x.amount;return *this;}void output(ostream&) const;
private:long amount;
};

上述代码的类声明分别用操作符+和+=替代了add和increment。成员函数output用一个输入流的名字作为参数。

+、output和<<的代码：

currency currency::operator+(const currency& x) const
{//把参数对象x和调用函数*this相加currency result;result.amount = amount + x.amount;return result;
}
​
void currency::output(ostream& out) const
{//把货币值插入流outlong theAmount = amount;if(theAmount < 0){out << '-';theAmount = -theAmount;}long dollars = theAmount / 100;out << '$' << dollars * 100;int cents = theAmount - dollars * 100;if(cents < 10) out << '0';out << cents;
}
​
//重载 <<
ostream& operator<<(ostream& out, const currency& x)
{x.output(out);return out;
}

上述程序给定add和output的新代码，以及重载的C++流插入操作符<<的代码。

注意，我们重载流插入操作符，但没有把它声明为类的成员函数，而是把重载+和+=声明为类的成员函数。同样，我们也可以重载流提取操作符>>，而没有把它声明为类的成员函数。还要注意，使用成员函数output有助于对流插入操作符<<的重载。因为非成员函数不能访问currency对象的私有成员（重载的<<不是成员函数，而重载的+是），所以重载<<的代码不能直接引用要插入到输出流的对象x的私有成员。

使用重载操作符：

#include<iostream>
#include"currencyOverload.h"
using namespace std;
​
int main()
{currency g, h(plus, 3, 50), i, j;//使用两种形式的setValue来赋值g.setValue(minus, 2, 25);i.setValue(-6.45);//调用成员函数add和outputj = h + g;cout << h << " + " << g << " = " << j  << endl;//连续两次调用成员函数addj = i + g + h;cout << i << " + " << g << " + " << " and then add " << h << endl;//调用成员函数increment和addcout << "Incement " << i << " by " << g << " and then add " << h << endl;j = (i += h) + h;cout << "Result is " << j << endl;cout << "Incemented object is " << i << endl;//测试异常cout << "Attempting to iniitialize with cents = 152" << endl;try{i.setValue(plus, 3, 152);}catch(illegalParameterValue e){cout << "Caught throw exception" << endl;e.outputMessage();}return 0;
}

4.4.友元和保护性类成员

对一个类的私有成员，仅有类的成员函数才能直接访问。我们必须给予别的类和函数直接访问该类私有成员的权利。这就需要这些类和函数声明为该类的友元（friend）。

重载友元操作符<<：

class currency
{friend ostream& operator<<(ostream&, const currency&);public:
};
​
//重载
ostream& operator<<(ostream& out, const currency& x)
{//把货币值插入流outlong theAmount = x.amount;if(theAmount < 0){out << '-';theAmount = -theAmount;}long dollars = theAmount / 100;out << '$' << dollars << '.';int cents = theAmount - dollars * 100;if(cents < 10) out << '0';out << cents;return out;
}

当我们把ostream& operator<<声明为currency类的友元，它就可以直接访问currency类的所有成员（私有和公有），这时也就不用另外定义成员函数output了。为了建立友元，我们在currency类的描述中引入了friend语句。

一个类A从另外一个类B派生，A是派生类（derived class），B是基类（base class）。派生类需要访问基类的部分或所有成员，为此，C++提供了第三方类成员——保护性类成员（protected）。保护性成员类似于私有成员，区别于派生类函数可以访问基类的保护性成员。

用户应用程序可以访问的类成员应该是公开的。数据成员永远不要出现在公有部分，但是他们可以定义为保护性成员或者私有成员。优秀的软件工程师设计原则要求数据成员是私有的。通过成员函数，派生类可以间接访问基类的私有数据成员，同时，修改基类的实现代码时不用修改它的派生类。

4.5.增加#ifndef、#define和#endif语句

在上面的文件currency.h（或者currencyOverload.h）包含了currency类的声明和实现细节。在文件头加上以下的语句：

#ifndef Currency_
#define CUrrency_

在文件尾添加上：

#endif

包含在这组语句之内的代码只能编译一次。

5.异常类illegalParameterValue

定义一个异常类：

class illegalParameterValue
{
public:illegalParameterValue():message("Illegal parameter value"){}illegalParameterValue(char* theMessage){message = theMessage;}void outputMessage(){cout << message << endl;}
private:string message;
};

抛出illegalParameterValue类型的异常：

int abc(int a, int b, int c)
{if(a <= 0 || b <= 0 || c <= 0)throw illegalParameterValue("All parameters should be > 0");return a + b * c;
}

捕捉illegalParameterValue类型的异常：

int main()
{try {cout << abc(2, 0, 4) << endl;}catch(illegalParameterValue e){cout << "The parameters to abc were 2, 0, and 4" << endl;cout << "illegalParameterValue exeception throw" << endl;e.outputMessage();return 1;}return 0;
}

6.递归函数

递归函数（recursive function）或方法自己调用自己。在直接调用直接递归（direct recursion）中，递归函数f的代码包含了调用f的语句，而在间接递归中，递归函数f调用了函数g，g有调用了函数h，如此下去，直到有调用了f。在深入探讨C++递归函数之前，我们来看看两个相关的数学概念——数学函数的递归定义和归纳证明。

6.1.递归的数学函数

数学中经常有这样的函数，它自己定义自己。

在一个基础部分（base component），它包含n的一个或多个值，对这些值，f(n)是直接定的；在递归调用部分（recursive component），右侧f有一个参数小于n，因此重复应用递归部分可以把右侧f的表达式转换为基础部分。

比如说：递归定义的斐波那契数列：

F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 (n>1)

Fibonacci-斐波那契数列问题：

#include<iostream>
using namespace std;
​
int m;//定义要求的第m项斐波那契数列的项
​
int fib(int i)
{if(i == 0) return 0;if(i == 1) return 1;return (fib(i - 1) + fib(i - 2));//递归公式
}
​
int main()
{cout << "请输出fib的项数：";cin >> m;cout << endl;cout << "第" << m << "项的fibonacci = " << fib(m) << endl;return 0;
}

6.2.归纳

现在我们把注意力转移到与递归函数有关的第二个概念——归纳证明。

一般，证明的方法是，首先检验，对n的一个或者多个基础值（一般n=0就可以），公式成立。然后假设当n从0到m时公式成立，其中m是任意一个大于或等于最大基础值的整数。最后，根据这个假设证明，当n等于m+1时公式成立。这种证明方法有三个部分——归纳基础（induction）、归纳假设（induction hypothesis）和归纳步骤（induction step）。

在归纳假设中，假设n≤m时，公式均成立，其中m是任意大于或等于0的整数（假设n=m时，公式成立亦可）。在归纳步骤阶段，要证明当n=m+1时公式成立。

乍一看，归纳证明好像是一个循环证明——因为我们给出的是一个假设为正确的结论，其实不然。就像递归定义并不是循环定义一样。每一个正确的归纳证明都有一个归纳基础部分，它与递归定义的基础部分相似。归纳步骤使用的是在归纳基础部分已经检验的正确结果。反复应用归纳步骤，把证明部分转化为基础部分所具有的形式。

6.3.C++递归函数

使用C++可以编写递归函数。正确的递归函数必须包含基础部分。每一次递归调用，其参数值都比上一次的参数值要小，从而重复调用递归函数使参数值达到基础部分的值。

计算n!的递归函数：

#include<iostream>
using namespace std;
int n;
​
int factorial(int i)
{//计算n!if(i <= 1) return 1;else return i * factorial(i - 1);
}
​
int main()
{scanf("%d", &n);printf("%d!的递归值：%d", n, factorial(n));return 0;
}

阶乘程序是一个典型的C++递归函数，它利用相应的数学公式来计算阶乘n!。基础部分是n≤1.考虑到factorial(2)的计算过程。将factorial(2)挂起来，然后调用factorial(1)。程序状态（即局部变量和传值形参的值、与引用形参绑定的值、代码执行位置等）被保留在递归栈中。当factorial(1)的计算结束时，程序状态恢复。

累加数组元素a[0:n-1]：

#include<iostream>
#define N 1000
using namespace std;
​
template<class T>
T sum(T a[], int n)
{//返回值为数组元素a[0:n-1]的和T theSum = 0;for(int i = 0;i < n; i++){theSum += a[i];}return theSum;
}
​
int main()
{int n, q[N];scanf("%d", &n);for(int i = 0;i < n; i++){scanf("%d", &q[i]);}int total = sum(q, n);printf("%d", total);return 0;
}

模板函数sum对数组元素a[0]至a[n-1]求和，当n=0时，函数返回值是0。

当然累加数组元素也能使用递归代码

template<class T>
T rSum(T a[], int n)
{//返回值为数组元素a[0:n-1]的和if(n > 0){return rSum(a, n-1) + a[n-1];}return 0;
}

排列：

我们常常要从n个不同元素的所有排列中确定一个最佳的排列。例如，a、b和c的排列，就有abc、acb、bac、bca、cab和cba。n个元素的排列个数是n!。

为了输出n个元素的所有排列，编写非递归的C++函数比较困难，但是编写递归函数就没有那么困难了。设E={e1, ..., en}是n个元素的集合，求E的元素的所有排列。令Ei表示从E中去除第i个元素ei以后的集合，令perm(X)的表示集合X所有元素所组成的所有排列，令ei.perm(X)表示在perm(X)中的每个排列加上前缀.ei之后的排列表。

当n=1时，是递归的基础部分。这时的集合E只有一个元素e，因此只有一个排列：perm(E)=(e)。当n>1时，perm(E)是一个表。

使用递归函数生成排列：

template<class T>
void permytations(T list[], int k, int m)
{//生成list[k:m]的所有排列if(k == m){//list[k:m]仅有一个排列，输出它copy(list, list+m+1,ostream_iterator<T>(cout, ""));cout << endl;}else//list[k:m]有多于一个的排列，递归的生成这些排列for(int i = k;i <= m; i++){swap(list[k], list[i]);permytations(list, k+1, m);swap(list[k], list[i]);}
}

7.标准模板库

C++标准模板库（STL）是一个容器、适配器、迭代器、函数对象（也称仿函数）和算法的集合。有效的使用STL，应用程序的设计会简单许多。本书首先使用基本的C++语言结构解决一个问题，以说明求解问题的方法。然后利用STL说明如何使用更简单的方法解决同样的问题。

7.1.accumulate

STL有一个算法accumulate是对顺序表元素顺序累计求和。

它的语法accumulate(start, end, initialValue)

其中的start指向首元素，end指向尾元素的下一个位置，因此要累计求和的元素范围是[start, end]，调用的语句也就是accumulate(a, a+n, theSum);

其中一个a是一维数组。返回值：initialValue+a[i]的和

利用STl的算法accumulate

template<class T>
T sum(T a[], int n)
{//返回数组a[0:n-1]的累计和T thsSum = 0;return accumulate(a, a + n, theSum);
}

STL的算法accumulate利用操作符++，从start开始，到end结束，相继访问要累计求和的顺序表元素。因此，对于任意一个序列，如果他的元素可以通过重复应用操作符++来访问。一维数组和STl的vector容器都是这种顺序表的实例。

STL算法accumulate还有一个更加通用的形式accumulate(start , end, initialValue, operator)

其中，operator是一个函数，它规定了在累计过程中的操作。

计算数组元素a[0:n-1]的乘法

template<class T>
T product(T a[], int n)
{//返回数组a[0:n-1]的累计和T theProduct = 1;return accumulate(a, a+n, theProduct, multiplies<T>());
}

7.2.copy和next_permutation

算法copy是把一个顺序表的元素从一个位置复制到另一个位置上去。语法：copy(start, end, to);其中to给出了第一个元素要复制到的位置。因此，元素从位置start,start+1, ...,end-1依次复制到位置to, to+1,...,to+end-start。

算法next_permutation，其语法为：next_permutation

对范围[start, end)内的元素，按字典顺序，产生下一个更大的排列。当且仅当这个排列存在时，返回true。

使用STL算法next_permutation求排列

template<class T>
void permutation(T list[], int k, int m)
{//生成list[k:m]的所有排列//假设k≤m//将排序逐个输出do{copy(list, listm+1,ostream_iterator<T>(cout, ""));cout << endl;}while(next_permutation(list, list+m+1));
}

next_permutation算法具有更一般的形式，它带有第三个参数compare。而compare函数用来判定一个排列是否比另一个排序小。