在學(xué)習(xí)這本書進(jìn)階內(nèi)容之前，我們可以跟著它的第一章部分再鞏固和復(fù)習(xí)。本書由Sartaj Sahni撰寫，由王立柱和劉志紅翻譯。全書通俗易懂，內(nèi)容豐富，是鞏固C++內(nèi)容的不二選擇。希望本文對各位有所幫助。

目錄

1.函數(shù)與參數(shù)

1.1.傳值參數(shù)

1.2.模板函數(shù)

1.3.引用參數(shù)

1.4.常量引用參數(shù)

1.5.返回值

1.6.重載函數(shù)

1.7.練習(xí)

2.異常

2.1.拋出異常

2.2.處理異常

2.3.練習(xí)

3.動態(tài)內(nèi)存空間分配

3.1.操作符new

3.2.一維數(shù)組

3.3.異常處理

3.4.操作符delete

3.5.二維數(shù)組

4.自有數(shù)據(jù)類型

4.1.類 currency

4.2.一種不同的描述方法

4.3.操作符重載

4.4.友元和保護(hù)性類成員

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

5.異常類illegalParameterValue

6.遞歸函數(shù)

6.1.遞歸的數(shù)學(xué)函數(shù)

6.2.歸納

6.3.C++遞歸函數(shù)

7.標(biāo)準(zhǔn)模板庫

7.1.accumulate

7.2.copy和next_permutation

1.函數(shù)與參數(shù)

1.1.傳值參數(shù)

對于普通的傳值參數(shù)，我們已經(jīng)司空見慣了我們一般只要對相應(yīng)的函數(shù)體傳入形參，在執(zhí)行的main函數(shù)主體中傳入實參就可以調(diào)用相應(yīng)的內(nèi)容。在運行時，函數(shù)體在執(zhí)行前，把實參復(fù)制給形參，復(fù)制的過程是由形參類型的復(fù)制構(gòu)造函數(shù)來完成的。如果實參和形參的類型不一致，那么就必須進(jìn)行類型轉(zhuǎn)換，把實參轉(zhuǎn)化為形參的類型，前提也很明確，那就是該類型轉(zhuǎn)換是允許的。在函數(shù)結(jié)束，系統(tǒng)會調(diào)用形參類型的析構(gòu)函數(shù)來釋放形式參數(shù)。當(dāng)函數(shù)運行結(jié)束以后，那么形參的只就不會復(fù)制到實參當(dāng)中去。因此，也就是我們所說的單向值傳遞。當(dāng)然，在我們所學(xué)習(xí)的類與對象板塊中，我們也知道了類內(nèi)的方法就很類似于我們的函數(shù)，而且我們還能自己進(jìn)行編寫構(gòu)造函數(shù)和析構(gòu)函數(shù)。

1.2.模板函數(shù)

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

這種形式過于拘泥，被數(shù)據(jù)類型限制了，所以我們可以使用模板，對相應(yīng)的形參進(jìn)行替換，當(dāng)我們調(diào)用同一個方法的時候，我們就無須再多慮它的數(shù)據(jù)類型了。

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

1.3.引用參數(shù)

在使用上面的模板函數(shù)時，會增加不少時間開銷，這實際上就是因為要重新開辟空間復(fù)制形參的原因。而且傳入的數(shù)據(jù)越多，它的負(fù)擔(dān)也就越大，也就導(dǎo)致了相應(yīng)的時間、空間雙重?fù)p失。這時候，我們就要是使用引用來減少這種時間和空間上的損失。

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

引用的好處就是將原來的形參復(fù)制形式轉(zhuǎn)變?yōu)榱藢崊⒅苯诱{(diào)用，當(dāng)然這個函數(shù)返回時，也就不會調(diào)用析構(gòu)函數(shù)。

1.4.常量引用參數(shù)

C++還提供另外一種參數(shù)傳遞模式——常量引用。這種模式指明的引用參數(shù)不能被函數(shù)修改。這個名字實際上就已經(jīng)暗示了這一點了，之前我們遇到的常變量、常量指針，都是使用了const，是相應(yīng)的數(shù)值轉(zhuǎn)變?yōu)橐粋€不可更改的左值。

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

用關(guān)鍵字const來指明函數(shù)不可修改的引用參數(shù)，在軟件工程上具有重要的意義。函數(shù)頭會告訴用戶該函數(shù)是不能修改實參的。

改成更通用的版本就是：

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

1.5.返回值

一個函數(shù)可以返回一個值、一個引用或者一個常量引用。在這種情況下，返回的值會被復(fù)制到調(diào)用環(huán)境中去，也就是我們獲得了我們調(diào)用函數(shù)之后想要得到的那個結(jié)果。

1.6.重載函數(shù)

一個函數(shù)的簽名是由這個函數(shù)的形參類型以及形參個數(shù)所確定的。C++可以定義兩個或多個同名函數(shù)，但是兩個同名函數(shù)不能有相同的簽名。定義多個同名函數(shù)的機(jī)制，就是我們所說的函數(shù)重載。

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.練習(xí)

練習(xí)1：交換函數(shù)為什么失敗，這是因為這是單向值傳遞，形參復(fù)制了實參，但是無法對實參進(jìn)行修改，函數(shù)運行結(jié)束，該形參也被回收了。

練習(xí)2：編寫一個模板函數(shù)count，返回值是數(shù)組a[0:n-1]中value出現(xiàn)的次數(shù)。

#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 << "輸入個數(shù)為：";
 ? ?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 << "該值個數(shù)為：" << number << endl;
 ? ?return 0;
}

練習(xí)3：編寫一個模板函數(shù)fill，給數(shù)組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 << "輸入個數(shù)：";
 ? ?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 << "復(fù)制的內(nèi)容為：";
 ? ?cin >> value;
 ? ?fill(arr, start, n, value);
 ? ?cout << "復(fù)制后的代碼：" << endl;
 ? ?for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?cout << arr[i] << " ";
 ?  }
 ? ?cout << endl;
 ? ?return 0;
}

此處可以將主函數(shù)中的int arr[N]改為char arr[N]之類的類型從而實現(xiàn)類型的差異，或者說也可以像上面的那道題一樣準(zhǔn)備多個選項進(jìn)行實現(xiàn)內(nèi)容。

練習(xí)4：編寫一個模板函數(shù)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 << "請輸入數(shù)據(jù)個數(shù)：";
 ? ?cin >> n;
 ? ?for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?cout << "輸入a數(shù)組的值：";
 ? ? ? ?cin >> a[i];
 ?  }
 ? ?for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?cout << "輸入b數(shù)組的值：";
 ? ? ? ?cin >> b[i];
 ?  }
 ? ?
 ?  for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?Count += inner_product(a[i], b[i]); 
 ?  }
 ? ?
 ? ?cout << "Sum的數(shù)據(jù)：" << Count << endl;
}
?
int main()
{
 ? ?test();
 ? ?return 0;
}

練習(xí)5：編寫一個模板函數(shù)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 << "請輸入個數(shù)：";
 ? ?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;
}

練習(xí)6：編寫一個模板函數(shù)is_sorted，當(dāng)且僅當(dāng)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 << "輸入個數(shù)：";
 ? ?cin >> n;
 ? ?for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?cout << "輸入數(shù)據(jù)：";
 ? ? ? ?cin >> a[i];
 ?  }
 ? ?bool j = is_sorted(a, n);
 ? ?if(j == true) cout << "從小到大升序排列" << endl;
 ? ?else cout << "非升序排列" << endl;
}
?
int main()
{
 ? ?test();
    return 0;
}

練習(xí)7：編寫一個模板函數(shù)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 << "輸入個數(shù)：";
 ? ?cin >> n;
 ? ?for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?cout << "輸入a數(shù)組：";
 ? ? ? ?cin >> a[i];
 ?  }
 ? ?for(int i = 0;i < n; i++)
 ?  {
 ? ? ? ?cout << "輸入b數(shù)組：";
 ? ? ? ?cin >> b[i];
 ?  }
 ? ?int num = mismatch(a, b, n);
 ? ?if(num == -1) cout << "ab數(shù)組完全相等" << endl;
 ? ?else cout << "第一個不相同的下標(biāo)是：" << num << endl;
 ? ?return 0;
}

2.異常

2.1.拋出異常

異常是表示程序出現(xiàn)錯誤的信息。比如說b/c，當(dāng)c=0時，這就是一個錯誤。對于這個錯誤，C++檢查不出來，但是硬件會檢查出來，并拋出一個異常。同樣的，當(dāng)我們學(xué)習(xí)Python的時候已經(jīng)接觸過它的異常，并做了一些預(yù)防措施和代碼。

我們可以編寫這樣的C++程序，它可以對一些異常的情況進(jìn)行檢查，而且當(dāng)查出一個異常的時候，就拋出這個異常。就如下面的代碼一樣，程序函數(shù)abc可以定義，僅當(dāng)三個參數(shù)都大于0時才進(jìn)行，只要有一個或多個為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除數(shù)、非法參數(shù)值、非法輸入值、數(shù)組下標(biāo)越界等。如果對每一種類型異常都定義一個異常類，那么異常的處理就有很大靈活性。

2.2.處理異常

一段代碼拋出的異常由包含這段代碼的try塊來處理。緊跟在try之后的是catch塊。每一個catch塊都有一個參數(shù)，參數(shù)的類型決定了這個catch塊要捕捉的異常類型。

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

catch塊一般包含異常改正之后所恢復(fù)的代碼。如果不能恢復(fù)，那么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;
}
?
//輸出結(jié)果：
The parameters to abc were 2, 0, and 5
An exception has been throw
All parameters should be > 0

abc函數(shù)拋出一個類型為char*的異常。這個異常使函數(shù)abc還沒有計算表達(dá)式的值就停止了。塊try也立即停止了，其中的cout語句沒有執(zhí)行完。因為拋出的異常與catch塊的參數(shù)e是同一種類型，所以異常被這個catch塊捕捉，e的賦值是拋出的異常，然后進(jìn)入catch塊。

2.3.練習(xí)

練習(xí)1：修改上面的程序，使拋出的異常類型是整型。如果a、b、c都小于0，那么拋出的異常值是1；如果a、b、c都等于0，那么拋出的異常值為2；否則沒有異常。編寫一個主函數(shù)，應(yīng)用修改后的代碼；若有異常拋出，則捕捉異常，根據(jù)異常值輸出信息。

#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.動態(tài)內(nèi)存空間分配

3.1.操作符new

C++操作符new用來進(jìn)行動態(tài)存儲分配或者運行時存儲分配，它的值是一個指針，指向所分配的空間.

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

3.2.一維數(shù)組

許多函數(shù)中都要用到一維和二維數(shù)組，這些數(shù)組的大小在編譯的時侯可能還是未知的，它們隨著函數(shù)的調(diào)用的變化而變化，因此對這些數(shù)組只能進(jìn)行動態(tài)存儲分配。

為了在運行時創(chuàng)建一個一維浮點數(shù)組，必須把x聲明為一個浮點型指針，然后為數(shù)組分配充足的空間

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

使用操作符new為n個浮點數(shù)分配了存儲空間，并返回第一個浮點數(shù)空間的指針。對每個數(shù)組的元素的訪問都可以使用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;
}

如果計算機(jī)沒有充足空間對float數(shù)組進(jìn)行分配時，就會捕捉到異常，主動彈出異常問題，拋出一個bad_alloc的異常，并終止程序利用try-catch結(jié)構(gòu)進(jìn)行相應(yīng)的操作

3.4.操作符delete

動態(tài)內(nèi)存的存儲空間不再需要時相應(yīng)的需要進(jìn)行空間釋放，釋放的空間可以重新用來動態(tài)分配，C++操作符delete用來釋放操作符new所分配的空間。

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

3.5.二維數(shù)組

雖然C++采用多種機(jī)制來說明二維數(shù)組，但這些機(jī)制大多數(shù)要求在編譯階段就知道而二維數(shù)組的大小。具體來說，使用這些機(jī)制很難編寫出相應(yīng)的函數(shù)，它的形參是一個第二維大小未知的二維數(shù)組。這是因為當(dāng)形參是二維數(shù)組時，必須指定第二維的大小。例如，a[][10]是一個合法的定義，但是a[][]不合法。

而克服這一問題的最佳方法就是采用動態(tài)內(nèi)存分配的形式。

#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;
}

在運行時，行數(shù)n要么是用戶自行輸入的，要么就是通過計算確定的，如果數(shù)組1的列數(shù)在編譯階段是未知的話，那么就不能只調(diào)用一次new就能創(chuàng)建二維數(shù)組（即使數(shù)組的行數(shù)是已知的）。要構(gòu)建這樣的二維數(shù)組，可以把它看做是由若干行所構(gòu)成的結(jié)構(gòu)，每一行都是一個能用new來創(chuàng)建的一維數(shù)組。指向每一行的指針保存在另外一個一位數(shù)組之中。

一個3*4的數(shù)組：

x[0]、x[1]、x[2]分別指向第0行、第1行、第2行的首元素，如歸x是一個字符數(shù)組，那么x[0:2]是指向字符的指針，而x本身就是一個指向指針的指針，x的聲明語法：char **x;

#include<iostream>
using namespace std;
template <class T>
bool makeArray(T ** &x, int numberOfRows, int numberOfColumns)
{
 ? ?//創(chuàng)建一個二維數(shù)組
 ? ?try{
 ? ? ? ?//創(chuàng)建行指針
 ? ? ? ?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;
}

創(chuàng)建一個類型為T的二維數(shù)組。這個數(shù)組的行數(shù)是numberOfRows，列數(shù)是numberOfColumns。程序首先為指針x[0]，......，x[numberOfRows-1]申請空間，然后為數(shù)組的每一行申請空間。在程序中操作符new被調(diào)用了numberOfRows+1次。如果new的某一次調(diào)用發(fā)生了異常，程序控制將轉(zhuǎn)移到catch塊，并返回false。而每一次new的調(diào)用都沒有任何問題的話，那么數(shù)組就創(chuàng)建成功。函數(shù)返回true。對于創(chuàng)建的數(shù)組x，每個元素都可以使用標(biāo)準(zhǔn)的下標(biāo)法x[i][j]來引用。0≤i＜numberOfRows, 0≤j＜numberOfColumns。

我們分兩步來釋放這個二維數(shù)組空間首先釋放放在for循環(huán)中為每一行所分配的空間，然后釋放為行指針?biāo)峙涞目臻g。x被指為NULL，防止用戶繼續(xù)訪問已經(jīng)釋放的空間。

template <class T>
void deleteArray(T ** &x, int numberOfRows)
{
 ? ?//刪除二維數(shù)組x
 ? ?for(int i = 0;i < numberOfRows; i++)
 ?  {
 ? ? ? ?delete [] x[i];
 ?  }
 ? ?
 ? ?delete [] x;
 ? ?x = NULL;
}

4.自有數(shù)據(jù)類型

4.1.類 currency

C++語言支持諸如int、float、和char這樣的數(shù)據(jù)類型。而書本上的許多應(yīng)用的數(shù)據(jù)類型是C++不支持的，需要自己定義。定義自有數(shù)據(jù)類型最靈活的方式就是使用C++的類（class）結(jié)構(gòu)。

假設(shè)你想處理貨幣類型currency的對象（也稱實例），這種對象有三個成員：符號+-、美元和美分。對于這些對象我們想要執(zhí)行的操作如下：

1. 給成員賦值

2. 確定成員值（即符號、美元數(shù)和美分?jǐn)?shù)）

3. 兩個對象相加

4. 增加成員值

5. 輸出

currency類聲明：

class currency
{
public:
 ? ?//構(gòu)造函數(shù)
 ? ?currency(signType theSign = plus,
 ? ? ? ? ? ?unsigned long theDollar = 0,
 ? ? ? ? ? ?unsigned int theCents = 0);
 ? ?//析構(gòu)函數(shù)
 ? ?~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），其實還有一個保護(hù)（protect）。公有部分所聲明的是用來操作類對象（或?qū)嵗┑某蓡T函數(shù)（又稱方法）。對類的用戶是可見的，是用戶與類對象進(jìn)行交互的唯一手段。私有部分所聲明的是用戶不可見的數(shù)據(jù)成員（如簡單變量、數(shù)組及其他可賦值的結(jié)構(gòu)）和成員函數(shù)。通過公有和私有以及保護(hù)部分，我們可以讓用戶只看到他們所看到的部分，同時把其余的部分隱藏起來，這部分通常是與實現(xiàn)細(xì)節(jié)有關(guān)內(nèi)容。

盡管C++語法可以在公有部分聲明數(shù)據(jù)成員，但是優(yōu)秀的軟件設(shè)計者不會這樣做。

上面代碼中，公有部分的第一個成員函數(shù)與類名相同，這種名稱與類名相同的成員函數(shù)稱為構(gòu)造函數(shù)（construction）。構(gòu)造函數(shù)指明了創(chuàng)建一個類對象的方法，而且沒有返回值。~加上類名的這種成員函數(shù)被稱為析構(gòu)函數(shù)（destructor），每當(dāng)一個類對象超出作用域的時候，析構(gòu)函數(shù)就會自動調(diào)用來刪除這個對象。

在創(chuàng)建一個class類對象，如果沒有構(gòu)造函數(shù)，系統(tǒng)會自動調(diào)用空的構(gòu)造函數(shù)，同理，如果沒有析構(gòu)函數(shù)，那么也會自動調(diào)用回收的系統(tǒng)析構(gòu)函數(shù)。

創(chuàng)建currency類對象的方式有如下兩種：

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

調(diào)用成員函數(shù)的方式有：

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

其中的g和h是currency的類對象，也是函數(shù)的賦值對象。而所定義的類對象的關(guān)鍵字const是指這些函數(shù)值不會改變調(diào)用對象的值。我們把這種成員函數(shù)叫做常量函數(shù)（constant function）。

當(dāng)然這里復(fù)制構(gòu)造函數(shù)（copy constructor）沒有在代碼中實現(xiàn)。C++將使用缺省復(fù)制構(gòu)造函數(shù)，僅僅復(fù)制數(shù)據(jù)成員。對于這個currency類而言，缺省復(fù)制構(gòu)造函數(shù)已經(jīng)足夠了，但是對于很大一部分類，我們最好還是在堆上空間進(jìn)行開辟空間，也就是自己去定義一個復(fù)制構(gòu)造函數(shù)來進(jìn)行復(fù)制數(shù)據(jù)，缺省復(fù)制構(gòu)造函數(shù)已經(jīng)無法滿足程序需要了。

currency的構(gòu)造函數(shù)：

currency::currency(signType theSign, unsigned long theDollars, unsigned int theCents)
{
 ? ?//創(chuàng)建一個currency類對象
 ? ?setValue(theSign, theDollars, theCents);
}

成員函數(shù)如果不在類聲明體內(nèi)部實現(xiàn)，而在外部實現(xiàn)，就必須要使用作用域說明符（scope resolution operator）::以指明該函數(shù)是currency類的成員函數(shù)。因此currency::currency表示currency類的構(gòu)造函數(shù)，而currency::output這表示currency類的output成員函數(shù)。

給私有數(shù)據(jù)成員賦值：

void currency::setValue(signType theSign, unsigned long theDollars, unsigned int theCents)
{
 ? ?//給調(diào)用對象的數(shù)據(jù)成員賦值
 ? ?if(theCent > 99)
 ? ? ? ?throw illegalParameterValue("Cents should be < 100");
 ? ?
 ? ?sign = theSign;
 ? ?dollars = theDollars;
 ? ?cents = theCents;
}
?
void currency::setValue(double theAmount)
{
 ? ?//給調(diào)用對象的數(shù)據(jù)成員賦值
 ? ?if(theAmount < 0)
 ?  {
 ? ? ? ?sign = minus;
 ? ? ? ?theAmount = -theAmount;
 ?  }
 ? ?else sign = plus;
 ? ?dollars = (unsigned long) theAmount;//提取整數(shù)
 ? ?cents = (unsigned int) ((theAmount + 0.001 - dollars) * 100);//提取兩位小數(shù)
}

這是兩個成員函數(shù)setValue的代碼。第一個成員函數(shù)驗證參數(shù)值的合法性，只有當(dāng)參數(shù)合法了，才能拿來給調(diào)用函數(shù)的私有數(shù)據(jù)成員賦值。如果參數(shù)不合法，就拋出一個類型為illeaglParametervalue的異常。第二個函數(shù)參數(shù)不驗證參數(shù)值的合法性，僅用小數(shù)點后面頭兩位數(shù)字。

但是我們知道，用計算機(jī)來表示一些小數(shù)是不夠精確的，比如說，5.29用計算機(jī)表示是5.2899，那么加上0.001，在通過強(qiáng)制轉(zhuǎn)換，把它轉(zhuǎn)換為整型，那么再通過*100的操作就可以拿到相應(yīng)的數(shù)據(jù)啦。

把兩個currency對象的值相加：

currency currency::add(const currency& x) const
{
 ? ?//把x和*this相加
 ? ?long a1, a2, a3;
 ? ?currency result;
 ? ?//把調(diào)用對象轉(zhuǎn)化為符號整數(shù)
 ? ?a1 = dollars * 100 + cents;
 ? ?if(sign == minus) a1 = -a1;
 ? ?
 ? ?//把x轉(zhuǎn)化為符號整數(shù)
 ? ?a2 = x.dollars * 100 + x.cents;
 ? ?if(x.sign == minus) a2 = -a2;
 ? ?
 ? ?a3 = a1 + a2;
 ? ?
 ? ?//轉(zhuǎn)換為currency對象的表達(dá)式
 ? ?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的代碼，它首先把要相加的兩個對象轉(zhuǎn)化為整數(shù)，如$2.32轉(zhuǎn)換為232。引用調(diào)用對象的數(shù)據(jù)成員與引用對象x的數(shù)據(jù)成員在語法上是有區(qū)別的。x.dollars指的是x的數(shù)據(jù)成員，而前面沒有對象名稱的dollars指的是調(diào)用對象的數(shù)據(jù)成員。當(dāng)方法add終止時，局部變量a1、a2、a3和ans被析構(gòu)函數(shù)刪除，它們的空間也均被釋放。

函數(shù)increment和output：

currency& currency::increment(const currency& x)
{
 ? ?//增加x
 ? ?*this = add(x);
 ? ?return *this;
}
?
void currency::output() const
{
 ? ?//輸出調(diào)用對象的值
 ? ?if(sign == minus) cout << '-';
 ? ?cout << '$' << dollars << '.';
 ? ?if(cents < 10) cout << '0';
 ? ?cout << cents;
}

在C++中，保留關(guān)鍵字this指向調(diào)用對象，*this就是調(diào)用對象。以調(diào)用語句g.increment(h)為例，方法increment第一行語句調(diào)用公有函數(shù)add，它把x（即h）與調(diào)用對象g相加，然后把相加的結(jié)果作為返回值，賦值給 *this，而 *this就是g。我們使用了返回引用，這樣就省略返回值的復(fù)制過程。

類currency的數(shù)據(jù)成員已經(jīng)設(shè)為私有（private），類的用戶不能直接訪問這些成員。因此，用戶通過下列的語句可以直接改變私有數(shù)據(jù)成員的值：

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

如果數(shù)據(jù)成員在處理之前是有效的，而且經(jīng)過成員函數(shù)處理之后仍然是有效的，那么我們就能保證它們在經(jīng)過用戶程序處理之后依然是有效的，因為用戶程序是通過成員函數(shù)來處理數(shù)據(jù)成員的。構(gòu)造函數(shù)和成員函數(shù)setValue的代碼在使用數(shù)據(jù)之前都要驗證它的有效性。而其余的函數(shù)特性是：如果數(shù)據(jù)在處理之前有效，那么在處理之后仍然是有效的。

類currency的應(yīng)用：

#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);
 ? ?
 ? ?//調(diào)用成員函數(shù)add和output
 ? ?j = h.add(g);
 ? ?h.output();
 ? ?cout << " + ";
 ? ?g.output();
 ? ?cout << " = ";
 ? ?j.output();
 ? ?cout << endl;
 ? ?
 ? ?//連續(xù)調(diào)用兩次成員函數(shù)add
 ? ?j = 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;
}

這段代碼假定類聲明和類實現(xiàn)都在文件currency.h之中，但是這種分置對后續(xù)章節(jié)要引入的大量模板函數(shù)和模板類是行不通的。

4.2.一種不同的描述方法

假設(shè)已經(jīng)有很多應(yīng)用程序采用我們上面的currency類的形式，現(xiàn)在我們想要修改對currency類對象的數(shù)據(jù)描述，是應(yīng)用最多的兩個成員函數(shù)add和increment運行更快，進(jìn)而提高應(yīng)用程序的執(zhí)行速度。因為用戶僅僅通過公有部分所提供的的接口與currency類進(jìn)行交互，所以對私有部分的修改不會影響應(yīng)用程序的正確性。因此，私有部分修改，而應(yīng)用程序不用改。

類currency的新聲明：

class currency
{
public:
 ? ?//構(gòu)造函數(shù)
 ? ?currency(signType theSign = plus,
 ? ? ? ? ? ?unsigned long theDollars = 0,
 ? ? ? ? ? ?unsigned int theCents = 0);
 ? ?//析構(gòu)函數(shù)
 ? ?~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;
};

構(gòu)造函數(shù)和成員函數(shù)setValue的新代碼：

currency::currency(sigeType theSign, unsigned long theDollars, unsigned int theCents)
{
 ? ?//創(chuàng)建一個currency類對象
 ? ?setValue(theSign, theDollars, theCents);
}
?
void currency::setValue(signType theSign, unsigned long theDollars, unsigened int theCents)
{
 ? ?//給調(diào)用對象賦值
 ? ?if(theCents > 99)
 ? ? ? ?//美分值太大
 ? ? ? ?throw illegalParamenterValue("Cents should be < 100");
 ? ?amount = theDollars * 100 + theCents;
 ? ?if(theSign == minus) amount = -amount;
}
?
void currency::setValue(double theAmount)
{
 ? ?//給調(diào)用對象賦值
 ? ?if(theAmount < 0)
 ? ? ? ?amount = (long) ((theAmount - 0.001) * 100);
 ? ?else
 ? ? ? ?amount = (long) ((theAmount + 0.001) * 100);//取兩個十位數(shù)
}

成員函數(shù)add和output的新代碼：

currency currency::add(const currency& x) const
{
 ? ?//把x和*this相加
 ? ?currency y;
 ? ?y.amount = amount + x.amount;
 ? ?return y;
}
?
void currency::output() const
{
 ? ?//輸出調(diào)用對象的值
 ? ?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有若干成員函數(shù)和C++標(biāo)準(zhǔn)操作符類似。例如，add實施的是+操作，increment實施的是+=操作。使用這些標(biāo)準(zhǔn)的C++操作符比定義新的諸如add和increment的成員函數(shù)要自然多得多。為了使用這些操作符+和+=，我們進(jìn)行操作符重載（operator overloading），它可以擴(kuò)大C++操作符的應(yīng)用范圍，使其操作新的數(shù)據(jù)類型或類。

包含操作符重載的類聲明：

class currency
{
public:
 ? ?//構(gòu)造函數(shù)
 ? ?currency(signType theSign = plus,
 ? ? ? ? ? ?unsigned long theDollars = 0,
 ? ? ? ? ? ?unsigned int theCents = 0);
 ? ?//析構(gòu)函數(shù)
 ? ?~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。成員函數(shù)output用一個輸入流的名字作為參數(shù)。

+、output和<<的代碼：

currency currency::operator+(const currency& x) const
{
 ? ?//把參數(shù)對象x和調(diào)用函數(shù)*this相加
 ? ?currency result;
 ? ?result.amount = amount + x.amount;
 ? ?return result;
}
?
void currency::output(ostream& out) const
{
 ? ?//把貨幣值插入流out
 ? ?long 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++流插入操作符<<的代碼。

注意，我們重載流插入操作符，但沒有把它聲明為類的成員函數(shù)，而是把重載+和+=聲明為類的成員函數(shù)。同樣，我們也可以重載流提取操作符>>，而沒有把它聲明為類的成員函數(shù)。還要注意，使用成員函數(shù)output有助于對流插入操作符<<的重載。因為非成員函數(shù)不能訪問currency對象的私有成員（重載的<<不是成員函數(shù)，而重載的+是），所以重載<<的代碼不能直接引用要插入到輸出流的對象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);
 ? ?
 ? ?//調(diào)用成員函數(shù)add和output
 ? ?j = h + g;
 ? ?
 ? ?cout << h << " + " << g << " = " << j ?<< endl;
 ? ?
 ? ?//連續(xù)兩次調(diào)用成員函數(shù)add
 ? ?j = i + g + h;
 ? ?cout << i << " + " << g << " + " << " and then add " << h << endl;
 ? ?
 ? ?//調(diào)用成員函數(shù)increment和add
 ? ?cout << "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.友元和保護(hù)性類成員

對一個類的私有成員，僅有類的成員函數(shù)才能直接訪問。我們必須給予別的類和函數(shù)直接訪問該類私有成員的權(quán)利。這就需要這些類和函數(shù)聲明為該類的友元（friend）。

重載友元操作符<<：

class currency
{
    friend ostream& operator<<(ostream&, const currency&);
 ? ?public:
};
?
//重載
ostream& operator<<(ostream& out, const currency& x)
{
 ? ?//把貨幣值插入流out
 ? ?long 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;
}

當(dāng)我們把ostream& operator<<聲明為currency類的友元，它就可以直接訪問currency類的所有成員（私有和公有），這時也就不用另外定義成員函數(shù)output了。為了建立友元，我們在currency類的描述中引入了friend語句。

一個類A從另外一個類B派生，A是派生類（derived class），B是基類（base class）。派生類需要訪問基類的部分或所有成員，為此，C++提供了第三方類成員——保護(hù)性類成員（protected）。保護(hù)性成員類似于私有成員，區(qū)別于派生類函數(shù)可以訪問基類的保護(hù)性成員。

用戶應(yīng)用程序可以訪問的類成員應(yīng)該是公開的。數(shù)據(jù)成員永遠(yuǎn)不要出現(xiàn)在公有部分，但是他們可以定義為保護(hù)性成員或者私有成員。優(yōu)秀的軟件工程師設(shè)計原則要求數(shù)據(jù)成員是私有的。通過成員函數(shù)，派生類可以間接訪問基類的私有數(shù)據(jù)成員，同時，修改基類的實現(xiàn)代碼時不用修改它的派生類。

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

在上面的文件currency.h（或者currencyOverload.h）包含了currency類的聲明和實現(xiàn)細(xì)節(jié)。在文件頭加上以下的語句：

#ifndef Currency_
#define CUrrency_

在文件尾添加上：

#endif

包含在這組語句之內(nèi)的代碼只能編譯一次。

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.遞歸函數(shù)

遞歸函數(shù)（recursive function）或方法自己調(diào)用自己。在直接調(diào)用直接遞歸（direct recursion）中，遞歸函數(shù)f的代碼包含了調(diào)用f的語句，而在間接遞歸中，遞歸函數(shù)f調(diào)用了函數(shù)g，g有調(diào)用了函數(shù)h，如此下去，直到有調(diào)用了f。在深入探討C++遞歸函數(shù)之前，我們來看看兩個相關(guān)的數(shù)學(xué)概念——數(shù)學(xué)函數(shù)的遞歸定義和歸納證明。

6.1.遞歸的數(shù)學(xué)函數(shù)

數(shù)學(xué)中經(jīng)常有這樣的函數(shù)，它自己定義自己。

在一個基礎(chǔ)部分（base component），它包含n的一個或多個值，對這些值，f(n)是直接定的；在遞歸調(diào)用部分（recursive component），右側(cè)f有一個參數(shù)小于n，因此重復(fù)應(yīng)用遞歸部分可以把右側(cè)f的表達(dá)式轉(zhuǎn)換為基礎(chǔ)部分。

比如說：遞歸定義的斐波那契數(shù)列：

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

Fibonacci-斐波那契數(shù)列問題：

#include<iostream>
using namespace std;
?
int m;//定義要求的第m項斐波那契數(shù)列的項
?
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的項數(shù)：";
 ? ?cin >> m;
 ? ?cout << endl;
 ? ?cout << "第" << m << "項的fibonacci = " << fib(m) << endl;
 ? ?return 0;
}

6.2.歸納

現(xiàn)在我們把注意力轉(zhuǎn)移到與遞歸函數(shù)有關(guān)的第二個概念——歸納證明。

一般，證明的方法是，首先檢驗，對n的一個或者多個基礎(chǔ)值（一般n=0就可以），公式成立。然后假設(shè)當(dāng)n從0到m時公式成立，其中m是任意一個大于或等于最大基礎(chǔ)值的整數(shù)。最后，根據(jù)這個假設(shè)證明，當(dāng)n等于m+1時公式成立。這種證明方法有三個部分——歸納基礎(chǔ)（induction）、歸納假設(shè)（induction hypothesis）和歸納步驟（induction step）。

在歸納假設(shè)中，假設(shè)n≤m時，公式均成立，其中m是任意大于或等于0的整數(shù)（假設(shè)n=m時，公式成立亦可）。在歸納步驟階段，要證明當(dāng)n=m+1時公式成立。

乍一看，歸納證明好像是一個循環(huán)證明——因為我們給出的是一個假設(shè)為正確的結(jié)論，其實不然。就像遞歸定義并不是循環(huán)定義一樣。每一個正確的歸納證明都有一個歸納基礎(chǔ)部分，它與遞歸定義的基礎(chǔ)部分相似。歸納步驟使用的是在歸納基礎(chǔ)部分已經(jīng)檢驗的正確結(jié)果。反復(fù)應(yīng)用歸納步驟，把證明部分轉(zhuǎn)化為基礎(chǔ)部分所具有的形式。

6.3.C++遞歸函數(shù)

使用C++可以編寫遞歸函數(shù)。正確的遞歸函數(shù)必須包含基礎(chǔ)部分。每一次遞歸調(diào)用，其參數(shù)值都比上一次的參數(shù)值要小，從而重復(fù)調(diào)用遞歸函數(shù)使參數(shù)值達(dá)到基礎(chǔ)部分的值。

計算n!的遞歸函數(shù)：

#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++遞歸函數(shù)，它利用相應(yīng)的數(shù)學(xué)公式來計算階乘n!?；A(chǔ)部分是n≤1.考慮到factorial(2)的計算過程。將factorial(2)掛起來，然后調(diào)用factorial(1)。程序狀態(tài)（即局部變量和傳值形參的值、與引用形參綁定的值、代碼執(zhí)行位置等）被保留在遞歸棧中。當(dāng)factorial(1)的計算結(jié)束時，程序狀態(tài)恢復(fù)。

累加數(shù)組元素a[0:n-1]：

#include<iostream>
#define N 1000
using namespace std;
?
template<class T>
T sum(T a[], int n)
{
 ? ?//返回值為數(shù)組元素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;
}

模板函數(shù)sum對數(shù)組元素a[0]至a[n-1]求和，當(dāng)n=0時，函數(shù)返回值是0。

當(dāng)然累加數(shù)組元素也能使用遞歸代碼

template<class T>
T rSum(T a[], int n)
{
 ? ?//返回值為數(shù)組元素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個元素的排列個數(shù)是n!。

為了輸出n個元素的所有排列，編寫非遞歸的C++函數(shù)比較困難，但是編寫遞歸函數(shù)就沒有那么困難了。設(shè)E={e1, ..., en}是n個元素的集合，求E的元素的所有排列。令Ei表示從E中去除第i個元素ei以后的集合，令perm(X)的表示集合X所有元素所組成的所有排列，令ei.perm(X)表示在perm(X)中的每個排列加上前綴.ei之后的排列表。

當(dāng)n=1時，是遞歸的基礎(chǔ)部分。這時的集合E只有一個元素e，因此只有一個排列：perm(E)=(e)。當(dāng)n>1時，perm(E)是一個表。

使用遞歸函數(shù)生成排列：

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.標(biāo)準(zhǔn)模板庫

C++標(biāo)準(zhǔn)模板庫（STL）是一個容器、適配器、迭代器、函數(shù)對象（也稱仿函數(shù)）和算法的集合。有效的使用STL，應(yīng)用程序的設(shè)計會簡單許多。本書首先使用基本的C++語言結(jié)構(gòu)解決一個問題，以說明求解問題的方法。然后利用STL說明如何使用更簡單的方法解決同樣的問題。

7.1.accumulate

STL有一個算法accumulate是對順序表元素順序累計求和。

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

其中的start指向首元素，end指向尾元素的下一個位置，因此要累計求和的元素范圍是[start, end]，調(diào)用的語句也就是accumulate(a, a+n, theSum);

其中一個a是一維數(shù)組。返回值：initialValue+a[i]的和

利用STl的算法accumulate

template<class T>
T sum(T a[], int n)
{
 ? ?//返回數(shù)組a[0:n-1]的累計和
 ? ?T thsSum = 0;
 ? ?return accumulate(a, a + n, theSum);
}

STL的算法accumulate利用操作符++，從start開始，到end結(jié)束，相繼訪問要累計求和的順序表元素。因此，對于任意一個序列，如果他的元素可以通過重復(fù)應(yīng)用操作符++來訪問。一維數(shù)組和STl的vector容器都是這種順序表的實例。

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

其中，operator是一個函數(shù)，它規(guī)定了在累計過程中的操作。

計算數(shù)組元素a[0:n-1]的乘法

template<class T>
T product(T a[], int n)
{
 ? ?//返回數(shù)組a[0:n-1]的累計和
 ? ?T theProduct = 1;
 ? ?return accumulate(a, a+n, theProduct, multiplies<T>());
}

7.2.copy和next_permutation

算法copy是把一個順序表的元素從一個位置復(fù)制到另一個位置上去。語法：copy(start, end, to);其中to給出了第一個元素要復(fù)制到的位置。因此，元素從位置start,start+1, ...,end-1依次復(fù)制到位置to, to+1,...,to+end-start。

算法next_permutation，其語法為：next_permutation

對范圍[start, end)內(nèi)的元素，按字典順序，產(chǎn)生下一個更大的排列。當(dāng)且僅當(dāng)這個排列存在時，返回true。

使用STL算法next_permutation求排列

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

next_permutation算法具有更一般的形式，它帶有第三個參數(shù)compare。而compare函數(shù)用來判定一個排列是否比另一個排序小。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-599722.html

到了這里，關(guān)于Data Structure, Algorithm,and Applications in C++的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！