第3章 数 组
数组是类型名、标识符和维数组成的复合数据类型。类型名规定了存放在数组中元素的类型，标识符也就是数组名称，而维数则指定数组中包含元素的个数。数组实际上是内存中连续存储的一组同种数据类型的元素（变量），每个数组有一个唯一的名称，通过在名称后面加索引（index）的方式可以引用它的每一个元素。本章举的实例都是关于数组的，如一维和多维数组元素排序，从一个数组赋值到另一个数组，数组在内存中占用的字节数。
本章重点讲解了多维数组、字符数组的实际应用实例，初学者应反复多实践，加深理解。另外还举了综合应用的实例，涉及类模板的概念，读者应举一反三，提高编程能力。
3.1 什么是数组
数组是在内存中连续存储的一组同种数据类型的元素（变量），每个数组有一个唯一的名称，通过在名称后面加索引（index）的方式可以引用它的每一个元素。
案例3-1 推箱子（数组元素移动）
【案例描述】
数组是数目固定、类型相同的若干个变量的有序集合，它在实际应用中非常广泛。本实例用数组存储箱子的体积，用适当的方法把箱子按体积从小到大排放好，结果如图3-1所示。
图3-1 推箱子（数组元素移动）
【实现过程】
首先定义存放箱子体积的数组v[n]，数组大小为n = 10，用一个for语句输出排序前数组中每个元素的值；然后采用的是冒泡排序，该算法是依次比较相邻的两个数，将小数放在前面，大数放在后面，对排序后的数组再用一个for输出显示数组中每个元素的值。代码如下：
#include <iostream>
using namespace std;
int main ()
{
const int n = 10; //数组大小
//定义双精度型并初始化
double v[n] = { 20.5, 35.8, 43.3, 32.5, 36.9,
22.3, 29.4, 33.7, 25.9, 30.6 };
cout << "排序前数组的值为:\n";
for (int i=0; i<n; i++) cout << " " << v[i]; //打印数组的值
cout << endl;
//实现冒泡排序
bool changed;
do{
changed = false;
for (int i=0; i<n-1; i++) { //for循环实现从1到n
if ( v[i] > v[i+1] ){ //交换记录
double swap = v[i]; //swap仅作暂存单元
v[i] = v[i+1];
v[i+1] = swap;
changed = true;
}
}
}while (changed);
cout << "排序后数组的值为:\n";
for ( i=0; i<n; i++) cout << " " << v[i]; //打印数组的值
cout << endl;
system("pause");
return 0;
}
【案例分析】
（1）一种典型的数组声明格式为：type name [elements];，这里的type可以是任何一种有效的对象数据类型，如 int、float等，name是一个有效的变量标识，而由方括号[]引起来的elements域指明数组的大小，即可以存储多少个元素。代码中声明数组double v[n];，数据类型为double，v为变量标识，n表示数组的大小。
（2）上述代码采用冒泡排序算法，其中用到了do{…}while和for两个循环，循环中采用交换数值。double swap = v[i]; v[i] = v[i+1]; v[i+1] = swap;这3句，实现了移动数组元素把小数放到前面的功能。
注意：C++允许数组初始化时方括号[ ]中的内容为空白，而数组的长度将由后面的花括号{}中数值的个数决定。如double v[] = { 20.5, 35.8, 43.3};，数组长度为3。
案例3-2 一个简单的数据统计系统 (综合)
【案例描述】
本实例是综合的例子，目的是对C++的特点做进一步理解。如定义字符串、输入字符串、比较字符串大小并进行统计、打印字符串等。本例效果如图3-2所示。
图3-2 一个简单的数据统计系统（综合）
【实现过程】
定义字符数组s[100]，读取字符数组，利用for循环进行统计，然后打印出统计结果。其代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int a,b,c; //定义统计小写字母、大写字母和阿拉伯数字的变量
char s[100]; //定义输入字符数组
a=0,b=0,c=0; //初始化
cout<<"请输入测试的字符串："<<endl;
gets(s); //读取字符串
for(int i=0;i<strlen(s);i++)
{
if(s[i]>='a'&&s[i]<='z') a++; //小写字母个数
if(s[i]>='A'&&s[i]<='Z') b++; //大写字母个数
if(s[i]>='0'&&s[i]<='9') c++; //阿拉伯数字
}
cout<<"小写字母个数："<<a<<endl; //打印结果
cout<<"大写字母个数："<<b<<endl;
cout<<"阿拉伯数字个数："<<c<<endl;
system("pause");
}
【案例分析】
（1）库函数gets()实现从标准输入设备（键盘）读取字符串，直到读取换行符结束，但读取的换行符会被丢弃，最后在末尾添加'\0'字符。调用格式gets(s);， s为字符串变量，可以是字符串数组名或字符串指针。
（2）库函数strlen()实现取字符串长度。上述代码s[i]>='a'用于比较字符的大小。
注意：gets(s)函数中的变量s为一个字符串或字符指针。如果为单个字符，编译连接不会有错误，但运行后会出现“Null pointer asignment”的错误。
案例3-3 输出字符串的每个字符（for访问数组）
【案例描述】
字符串用来存储一个以上字符的非数字值的变量，在编程中会经常用到。编程中定义了字符串或字符串数组并赋值，需要输出字符串的每个字符，如下载一个文本文件，若其内容存储在字符串中，需要一个字符一个字符地读取。本实例输出一个字符串和钻石图形，效果如图3-3所示。
【实现过程】
程序分两个演示：demo1()定义1个字符串c[12]，并进行初始化，用for语句逐个输出单字符；demo2()代码定义和初始化一个二维字符串数组，然后逐个引用数组元素，每次输出一个字符，打印出一个漂亮的钻石图形。代码如下：
#include <iostream>
using namespace std;
int demo1()
{
//字符串进行初始化
static char c[12]="I am happy!";
int i;
for(i=0;i<12;i++) //用for循环逐个引用数组元素
cout<<c[i]; //每次输出一个字符
cout<<endl;
return 0;
}
void demo2( )
{
//二维字符串数组初始化
char diamond[][7]={" *"," * *","* *","* *","* *"," * *"," *"};
int i,j;
for (i=0;i<7;i++)
{
for (j=0;j<7;j++)
cout<<diamond[i][j]; //逐个引用数组元素，每次输出一个字符
cout<<endl;
}
}
int main()
{
demo1();
cout <<"\n"; //换行
demo2();
cout << "\n";
system("pause");
return 0;
}
【案例分析】
（1）C++语言将字符串按字符数组来处理。例如，字符串常量GOOD!"，在机器内被处理成一个无名的字符型一维数组，存储为" GOOD!"和'\0'。C++语言中约定用'\0'作为字符串的结束标志，结束标志占内存空间，但不计入串的长度。有了结束标志'\0'，程序就依据标志判断字符串是否结束，而不是根据定义时设定的长度。可以用字符串的形式为字符数组赋初值，如代码char c[12]="I am happy!";，长度为12字节，以'\0'结尾。
（2）代码char diamond[][7]={}定义为1个二维字符串数组并初始化。二维字符串数组的一般格式为：类型说明符 数组名[常量表达式1][常量表达式2]，如float a[3][4]，千万不能写成floata[3,4]，分行给二维数组初始化如int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}，一一对应赋值如int a[3][4]={{1,2,3,4,5,6,7,8,9,10,11,12}}，如果数组的元素都赋值，第一维可以省略，但第二维必须有。
注意：字符串与字符数组的区别在于：字符数组char a[ ]={'C','H','I','N','A'};，在内存中以'A'结束，长度占5字节；而字符串char c[ ]="CHINA"; ，在内存中以'\0'结束，长度占6字节。
案例3-4 循环改写一段字符串（for访问数组）
【案例描述】
在实际编程中，应对指定的符合条件的字符串进行相应的处理。本例将一行姓名字符串中的每个单词的第一个字母改成大写，效果如图3-4所示。
【实现过程】
程序定义字符串st和name，提示输入测试人数，输入每个人的姓名，将姓名字符串中每个单词的第一个字母改写成大写。代码如下：
图3-4 循环改写一段字符串（for访问数组）
#include<iostream.h>
#include<iostream>
#include<stdio.h>
int main(void)
{
char st[1000];
char name[12];
int i=0;
char c;
int num; //输入测试人数
cout<<"姓名字符串中的每个单词的第一个字母改写成大写:"<<endl;
strcpy( st, "" ); //字符串清空
cout <<"输入测试人数:"<<endl;
cin >> num;
cout << "输入每个人姓名："<<endl;
do {
cin >> name; //输入每个人的姓名
strcat( st,name); //连接两个字符串
if(i<num)
strcat( st," " );
i++;
} while (i<num); //如果大于测试人数，则退出主程序
st[strlen(st)-1]='\0'; //字符串最后一个字母为'\0'
cout<<"输入的所有人的名字:"<<endl;
cout<<st<<endl;
if(st[0]>='a'&&st[0]<='z') //首字母改为大写
st[0]=st[0]-32;
for(i=0;c=st[i]!='\0';i++)
{
if(st[i]==' '&&st[i+1]!=' ')
st[i+1]=st[i+1]-32; //每个单词的第一个字母改写成大写
}
cout<<"最后第一个字母改写成大写结果为:"<<endl;
cout<<st<<endl;
system("pause");
return 0;
}
【案例分析】
（1）库函数strcat( st,name)实现连接两个字符串的功能。代码char st[1000]和char name[12]，strcpy( st, "" );，把空字符串赋值给char st[1000]，也就是st清空。
（2）代码中st[0]=st[0]-32;的作用是将首字母改为大写。这是因为字母中ASCII值的大写和小写字母相差32，if(st[i]==' '&&st[i+1]!=' ')表示字符串中的字符为空格。
注意：字符串如char str[12]="The String";，其中str为字符数组在内存中存储的地址，它一经定义，便成为常量不可再赋值。
3.2 一维数组
案例3-5 内存输出（打印数据）
【案例描述】
数组是数目固定、类型相同的若干个变量的有序集合，它存储在内存中占用内存空间，通过编程，可以取得内存中的地址。本实例取数组和指定元素在内存中的地址，结果如图3-5所示。
【实现过程】
子程序demo1()定义存储9个整数的数组Number，逐个显示数组元素，因为数组也是一个变量声明，所以能找到地址；demo2()中显示输出Number、取地址&Number和第一个元素地址&Number[0]；demo3()中显示输出数组Number，取第一个元素地址&Number[0]，移动数组1的位置，取第二个元素地址&Number[1]，再移动数组1的位置，取第三个元素地址&Number[2]地址。代码如下：
#include <iostream>
using namespace std;
int demo1()
{
int Number[] = { 61, 38, 31, 30, 31, 30, 31, 31, 30 };
cout << "显示数组元素：";
cout << "\nNumber 1: " << Number[0]; //打印Number[0]
cout << "\nNumber 2: " << Number[1];
cout << "\nNumber 3: " << Number[2];
cout << "\nNumber 4: " << Number[3];
cout << "\nNumber 5: " << Number[4];
cout << "\nNumber 6: " << Number[5];
cout << "\nNumber 7: " << Number[6];
cout << "\nNumber 8: " << Number[7];
cout << "\nNumber 9: " << Number[8];
cout << endl;
return 0;
}
int demo2()
{
int Number[] = { 61, 38, 31, 30, 31, 30, 31, 31, 30 };
cout << "\n Number : " << Number; //打印Number内容
cout << "\n&Number : " << &Number; //打印取地址&Number内容
//打印第一个元素地址&Number[0]的内容
cout << "\n&Number[0] : " << &Number[0] << endl;
cout << endl;
return 0;
}
int demo3()
{
int Number[] = { 61, 38, 31, 30, 31, 30, 31, 31, 30 };
cout << "整数(integer)占用字节： " << sizeof(int) << " bytes";
cout << "\n Number: " << Number; //打印Number的内容
cout << "\n&Number[0]: " << &Number[0] ; //打印第1个元素地址&Number[0]的内容
cout << "\n Number+1: " << Number+1;
cout << "\n&Number:[1] " << &Number[1] ; //打印第2个元素地址&Number[1]的内容
cout << "\n Number+2: " << Number+2;
cout << "\n&Number:[2] " << &Number[2]<<endl ;//打印第3个元素地址&Number[2]的内容
return 0;
}
void main()
{
demo1();
demo2();
demo3();
system("pause");
return;
}
【案例分析】
（1）demo2()表明数组Number、数组地址&Number和第一个元素地址&Number[0]具有相同的值。C++语言的指针使用符号“&”来取得变量的地址。因此，&Number表示取得数组变量地址。数组Number、数组地址&Number具有相同的值，而且在代码中看到Number、&Number和&Number[0]都有相同的值，这表明变量的名字实际上代表第一个元素地址。
（2）demo3 ()中int占用4字节，存在int数据类型的数组Number移动一个位置，存储空间移动4字节，这样就能很好地理解代码。
注意：这里举的是一维数组的实例，二维或多维存储在内存中的地址是不是与一维同样规律？读者可修改代码看看。
案例3-6 一维数组的应用
【案例描述】
本实例输入数据到一维数组中，然后读取存储在数组中的数据进行运算。本例效果如图3-6所示。
图3-6 一维数组的应用
【实现过程】
从键盘接收10个整数实现求其平均数和输出小于平均数的功能。代码如下：
#include <iostream>
using namespace std;
main()
{
int a[10],i,sum=0; //定义数组和整型变量
float ave=0; //存储平均值
for(i=0;i<=9;i++) //从0到9循环
{
cout<<"请输入整数：";
cin>>a[i]; //输入整数
sum=sum+a[i]; //求输入整数和
}
ave=sum/10.0; //求整数和的平均
cout<<"平均数:"<<ave;
cout<<"小于平均数:";
for(i=0;i<=9;i++) //从0到9循环
{
if(a[i]<ave)
cout<<" "<<a[i]<<endl; //输出整数
}
system("pause");
}
【案例分析】
（1）这是简单的一维数组的应用，定义数组a[10]，然后进行赋值和读取。一维数组是由数字组成的、以单纯的排序结构排列的、结构单一的数组，是二维数组和多维数组的基础。
（2）数组是一个由若干同类型变量组成的集合，引用这些变量时可用同一个名字。
（3）数组均由连续的存储单元组成，最低地址对应数组的第一个元素，最高地址对应最后一个元素。数组可以是一维的，也可以是多维的。
案例3-7 整数从大到小排序（比较法）
【案例描述】
继续演示一维数组应用的例子。本实例是读取数组中的元素并进行排序，效果如图3-7所示。
图3-7 整数从大到小排序（比较法）
【实现过程】
用比较法对10个整数按从大到小的顺序进行排序。代码如下：
#include <iostream>
using namespace std;
main()
{
int a[10]={7, 15, 4, 12, 9, 3, 10, 0, 24, 6}; //定义数组
int i,j,temp; //定义整数变量
for(i=0;i<9;i++) //从0到9循环
for(j=i+1;j<10;j++) //从0到9循环
if (a[i]<a[j]) //a[i]与a[j]比较
{
temp=a[i];a[i]=a[j];a[j]=temp; //a[i]与a[j]交换
}
for(i=0;i<=9;i++) //输出比较后的整数
cout<<" "<<a[i];
cout<<endl; //换行
system("pause"); }
【案例分析】
（1）定义数组时赋初值，即数组的初始化。例如：
int a[5]={ 1,2,3,4,5 };
（2）利用比较法进行比较。
① 将a[1]～a[9]与a[0]进行比较，若比a[0]大，则与a[0]进行交换，保证a[0]是最大数。
② 将a[2]～a[9]与a[1]进行比较，若比a[1]大，则与a[1]进行交换，保证a[1]是次大数。
③ 依此类推。
注意：在对全部的数组元素赋初值时，允许省略数组元素的个数。如int a[]={ 1,2,3,4,5 };也就等价于int a[5]={ 1,2,3,4,5 }。
实例3-8 传统杀毒软件基本实现原理（文件关键字定位）
【案例描述】
反病毒软件的任务是实时监控和扫描磁盘。部分反病毒软件通过在系统中添加驱动程序的方式进驻系统，并且随操作系统一起启动。大部分杀毒软件还具有防火墙功能。本例演示的是进程中是否包含可疑文件名，有则杀掉，效果如图3-8所示。
图3-8 传统杀毒软件基本实现原理（文件关键字定位）
【实现过程】
反病毒软件的实时监控方式因软件而异。有的反病毒软件，是通过在内存里划分一部分空间，将电脑中流过内存的数据与反病毒软件自身所带的病毒库（包含病毒定义）的特征码相比较，以判断是否为病毒。另一些则在所划分到的内存空间中，虚拟执行系统或用户提交的程序，根据其行为或结果作出判断。而扫描磁盘的方式，即和上面提到的实时监控的第一种工作方式基本一样，稍有不同的是反病毒软件会将磁盘上所有的文件（或者用户自定义扫描范围内的文件）做一次检查。部分代码如下：
BOOL ProcessVXER (void) //扫描进程
{
DWORD lpidProcess[1024],cbNeeded_1,cbNeeded_2;
HANDLE hProc;
HMODULE hMod[1024];
char ProcFile[MAX_PATH];
char FileName[FIVE]={LOW};
BOOL returnvalue=FALSE;
int Pcount=LOW;
int i;
EnablePrivilege(SE_DEBUG_NAME); //提升权限
//枚举进程
if (!(EnumProcesses(lpidProcess,sizeof(lpidProcess),&cbNeeded_1)))
{ printf("EnumProcesses() GetLastError reports %d\n",erron);
return 0; }
for (i=LOW;i<(int)cbNeeded_1/4;i++)
{ //打开找到的第一个进程
hProc=OpenProcess(PROCESS_ALL_ACCESS,FALSE,(unsigned long)lpidProcess);
if (hProc)
{ //枚举进程模块
if (EnumProcessModules(hProc,hMod,sizeof(hMod),&cbNeeded_2))
{ //枚举进程模块文件名，包含全路径
if (GetModuleFileNameEx(hProc,hMod[0],ProcFile,sizeof(ProcFile)))
{ printf("[%5d]\t%s\n",lpidProcess,ProcFile); //输出进程
//可以考虑将其注释掉，这样就不会输出进程列表了
Pcount++;
strcpy(FileName,"C:\\WINNT\\system32\\");
strcat(FileName,name); //把文件名+路径复制到FileName变量中
//查找进程中是否包含FileName
if (strcmp(FileName,ProcFile)==LOW)
{
//如果包含，则杀掉；KillProc为自定义的杀进程函数
if (!(KillProc(lpidProcess)))
{ printf("KillProc() GetLastError reports %d\n",erron);
CloseHandle(hProc);
exit(0); }
DeleteFile(FileName); //进程杀掉后，再将文件删除
} } } } }
CloseHandle(hProc); //关闭进程句柄
printf("\nProcess total:%d\n",Pcount); //打印进程各数
returnvalue=TRUE;
return 0;
}
【案例分析】
（1）一个杀毒软件一般由扫描器、病毒库与虚拟机组成，并由主程序将它们组合为一体。简单地说杀毒软件的实现原理就是匹配特征码。当扫描得到一个文件时，杀毒软件会检测这个文件中是否包含病毒库中所包含的特征码。如果有则查杀；如果没有即使这个文件确实是一个病毒，它也会把它当作正常文件来看待。
（2）上面代码主要进程操作函数如：EnumProcessModules枚举进程，GetModuleFileNameEx枚举进程模块文件名。
注意：程序编译时用到psapi.lib，运行时用到psapi.dll；在VC++使用时，需加入以下代码：#include "PSAPI.H" ，#pragma comment (lib,"Psapi.lib")。
3.3 多维数组
多维数组（Multidimensional Arrays）可以描述为数组的数组。例如，一个二维数组可以想象成一个有同一数据类型的二维表格。多维数组并不局限于二维。若需要可以定义任意多维，不过程序编写中需要三维以上的时候并不多。
案例3-9 数据复制（复制一组数组到另一组数组）
【案例描述】
数组存储的元素可以从一个数组复制到另一个数组，通过在数组名称后面加索引（如a[2]），实现对指定位置的元素进行复制操作。本实例将一个二维数组a的行和列的元素互换，然后存到另一个二维数组b中，结果如图3-9所示。
【实现过程】
程序初始化一个二维数组a，定义一个二维数组b，执行两个for循环，按行、列的顺序输出a的值，同时把值赋给b中对应的列、行中；再执行两个for循环按行、列的顺序输出b的值，把数组b
中的值加10后赋值给对应列、行的数组a中；最后执行两个for循环按行、列的顺序输出a的值。代码如下：
#include<iostream>
using namespace std;
int main()
{
int a[2][3] = {{10,20,30},{40,50,60}};
int b[3][2];
int i,j;
cout<<"array a:"<<endl;
for(i=0;i<=1;i++) //i取值为0、1，对应数组a的行（数组是从0开始算的）
{
for(j=0;j<=2;j++) //j取值为0、1、2，对应数组a的列
{
cout<<a[i][j]<<" ";
b[j][i]=a[i][j];
}
cout<<endl;
}
cout<<"array b:"<<endl;
for(i=0;i<=2;i++) //i取值为0、1、2，对应数组b的行
{
for(j=0;j<=1;j++) //j取值为0、1，对应数组b的列
{
cout<<b[i][j]<<" ";
a[j][i]=b[i][j]+10;
}
cout<<endl;
}
cout<<"array a:"<<endl;
for(i=0;i<=1;i++) //i取值为0、1，对应数组a的行（数组是从0开始算的）
{
for(j=0;j<=2;j++) //j取值为0、1、2，对应数组a的列
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
system("pause");
return 0;
}
【案例分析】
（1）代码int a[2][3] = {{1,2,3},{4,5,6}};，定义为整型的二维2´3数组，并且初始化值。
（2）代码中第一次是两个for循环，实现二维数组a、b的行和列的元素互换。数组的索引总是从0开始，如a数组中第2行第3列元素的表达式为：a [1][2]。
注意：多维数组只是一个抽象的概念，因为只需要把各个索引的乘积放入一个简单的数组中，就可以获得同样的结果。例如：a[4][5];，效果上等价于a [20]; (4 * 5 = 20)，唯一的区别是编译器能帮我们记住每一个想象中的维度的深度。
案例3-10 查找二维坐标点（二维for）
【案例描述】
二维数组编程中经常要排序和查找元素。本实例定义一组二维坐标，要求对坐标按照x从小到大排序，如果两个点的x坐标相同，那么就按照点的y坐标从小到大排序。本例效果如图3-10所示。
图3-10 查找二维坐标点（二维for）
【实现过程】
（1）定义一个二维坐标点结构Point，对x和y的坐标值进行冒泡排序，输出排序后点的坐标。每行包括两个用空格分隔的整数，分别是点的x坐标和点的y坐标。代码如下：
#include <iostream>
#include <iostream.h>
typedef struct Point //定义一个二维点
{
int x;
int y;
}Po;
//对坐标按照x从小到大排序，如果两个点的x坐标相同，则按照点的y坐标从小到大排序
void Sort(Po P[], int m)
{
int i,j;
int tx,ty; //交换用的临时变量
int flag;
for(i=m-1;i>0;i--) //冒泡排序
{
flag=0;
for(j=0;j<=i-1;j++)
{
if(P[j].x>P[j+1].x) //大于后一个数组点
{
tx=P[j].x;
ty=P[j].y;
P[j].x=P[j+1].x;
P[j].y=P[j+1].y;
P[j+1].x=tx;
P[j+1].y=ty;
flag=1;
}
//如果两个点的x坐标相同，那么就按照点的y坐标从小到大排序
else if(P[j].x==P[j+1].x&&P[j].y>P[j+1].y)
{
tx=P[j].x;
ty=P[j].y;
P[j].x=P[j+1].x;
P[j].y=P[j+1].y;
P[j+1].x=tx;
P[j+1].y=ty;
flag=1;
}
}
if(flag==0)break; //这轮没有交换，不用进入下一轮排序
}
cout <<"排序后的坐标 :"<<endl;
for(i=0;i<m;i++)
{
cout <<P[i].x<<" "<<P[i].y<<endl;
}
cout <<endl;
}
（2）主程序提示输入一个正整数n，表示有n组测试用例。对于每组测试用例，会提示输入一个正整数m，表示需要排序的点的数量，然后循环m次，提示每行输入两个整数，分别表示点的x坐标和y坐标。代码如下：
void main()
{
Po P[5];
int i;
int n,m;
cout <<"输入你要多少组测试用 :"<<endl;
cin>>n; //输入一个正整数n，表示有n组测试用例
while(n!=0)
{
cout <<"需要排序的坐标点的数量 :"<<endl;
cin >>m; //每组测试会输入一个正整数m，表示需要排序的点的数量
cout <<"开始输入点的X和Y坐标 :"<<endl;
for(i=0;i<m;i++) //m行，每行包括两个整数
{
cin >>P[i].x>>P[i].y; //分别表示点的x坐标和y坐标
}
Sort(P,m);
n--;
}
system("pause");
}
【案例分析】
（1）数组声明的语法形式为：type name [elements];，type可以是任何一种有效的对象数据类型，如int、float等；也可以是一个结构，如本例二维坐标点结构typedef struct Point。
（2）在Sort()函数中，用两个for循环实现x和y坐标值的冒泡排序，该算法是依次比较相邻的两个数，将小数放在前面，大数放在后面。
注意：从这个实例可以知道数组的数据类型可以是一个结构，后面实例还演示了数组是类模板的数据类型。
案例3-11 查找矩阵中最大的元素（二维for）
【案例描述】
继续037实例的内容。编程中会碰到查找矩阵中最大的元素，如矩阵存储的是一个年级的学生成绩，需要找到最高分及其学生所在的班级。本例效果如图3-11所示。
图3-11 查找矩阵最大的元素（二维for）
【实现过程】
定义一个二维数组，存储矩阵的值，有一个3´4的矩阵，要求编程找出矩阵中值最大的那个元素以及它所在的行和列。代码如下：
#include <iostream>
using namespace std;
main()
{
int a[3][4]={{3,5,1,8},{4,6,11,7}, {9,3,5,2}}; //定义数组
int i,j,row,col,max; //定义整型变量
max=a[0][0]; //存储最大的元素
for(i=0;i<3;i++) //从0到3循环
for(j=0;j<4;j++) //从0到4循环
{
if(a[i][j]>max) //a[i]与max比较
{
max=a[i][j];row=i; col=j; //max与a[i][j]
}
}
cout<<"矩阵最大的元素："<<max<<endl;
cout<<"所在的行："<<row<<",列："<<col<<endl;
system("pause");
}
【案例分析】
（1）二维数组初始化与一维数组类似，如：
int a[4][3]={{1，2，3},{4，5，6},{7，8，9}, {10，11，12}};
（2）在初始化二维数组时，如果给出数组中所有元素的初值，可以不写第一维的长度，但第二维的长度不可省略。如：
int a[4][3]={{1，2，3},{4，5，6},{7，8，9},{10，11，12}};
等价于
int a[][3]={ {1，2，3},{4，5，6},{7，8，9},{10，11，12}};
注意：只对部分二维数组元素初始化时，其他元素会自动为0，例如：int a[3][3]={{0,1},{0,0,2},{3}};。初始化后各元素值为：a[0][0]=0 a[0][1]=1 a[0][2]=0 a[1][0]=0 a[1][1]=0 a[1][2]=2 a[2][0]=3 a[2][1]=0 a[2][2]=0。
案例3-12 二分法查找（二维for）
【案例描述】
本实例初始化10个数，然后按从小到大的顺序存放在一个数组中。再输入一个数，要求用二分法查找该数。本例效果如图3-12所示。
图3-12 二分法查找（二维for）
【实现过程】
有10个数按从小到大的顺序存放在一个数组中，输入一个数要求用二分法查找该数是否是该数组中某个元素的值。如果找不到，则打印“无”；如果找到，则输出该数的位置。代码如下：
#include <iostream>
using namespace std;
main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10}; //定义一维数组
int n,front,back,mid; //定义整数
cout<<"请输入整数：";
cin>>n; //输入一个整数
front=0; //开始值
back=9; //结束值
while(back!=front) //直到与开始值相等
{
mid=(front+back+1)/2; //求平均值
if(n<a[mid]) //n与a[mid]比较
{
back=mid; //结束值等于平均值
}
else if(n>a[mid]) //输入整数大于a[mid]
front=mid; //开始值等于平均值
else {
cout<<"输入整数在数组位置："<<a[mid-1]<<endl;
break;
}
}
if (back<=front) //结束值小于或等于开始值
cout<<"输入整数不在数组内"<<endl;
system("pause");
}
【案例分析】
（1）采用二分法查找时，数据必须是排好序的。
（2）二分法查找的基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值，则在数列的后半段中继续查找，直到找到为止。
注意：当数据量很大时，适宜采用二分法查找。
案例3-13 查找三维坐标点（三维for）
【案例描述】
继续039实例的演示，在三维数组编程中实现排序和查找元素。本实例定义一组三维坐标，要求对坐标值按照x从小到大排序；如果两个点的x坐标相同，那么就按照点的y坐标从小到大排序，若y坐标相同，则按z坐标从小到大排序。本例效果如图3-13所示。
图3-13 查找三维坐标点（三维for）
【实现过程】
（1）定义一个三维坐标点结构Point，运行x、y和z坐标值的冒泡排序，排序结束后输出排序好点的坐标。每行包括3个用空格分隔的整数，分别是点的x、y和z坐标值。代码如下：
#include <iostream>
#include <iostream>
#include <iostream.h>
typedef struct Point //定义一个三维点
{
int x;
int y;
int z;
}Po;
//对坐标按照x从小到大排序，如果两个点的x坐标相同，则按照点的 y 坐标从小到大排序
void Sort(Po P[], int m)
{
int i,j;
int tx,ty,tz; //交换用的临时变量
int flag;
for(i=m-1;i>0;i--) //冒泡排序
{
flag=0;
for(j=0;j<=i-1;j++)
{
//如x坐标大于后一个数组点
if(P[j].x>P[j+1].x)
{
tx=P[j].x;
ty=P[j].y;
tz=P[j].z;
P[j].x=P[j+1].x;
P[j].y=P[j+1].y;
P[j].z=P[j+1].z;
P[j+1].x=tx;
P[j+1].y=ty;
P[j+1].z=tz;
flag=1;
}
//x坐标相同，y坐标大于后一个数组点
else if(P[j].x==P[j+1].x&&P[j].y>P[j+1].y)
{
tx=P[j].x;
ty=P[j].y;
tz=P[j].z;
P[j].x=P[j+1].x;
P[j].y=P[j+1].y;
P[j].z=P[j+1].z;
P[j+1].x=tx;
P[j+1].y=ty;
P[j+1].z=tz;
flag=1;
}
//两个点的x、y坐标相同，z坐标值大于后一个数组
else if(P[j].x==P[j+1].x&&P[j].y==P[j+1].y&&P[j].z>P[j+1].z)
{
tx=P[j].x;
ty=P[j].y;
ty=P[j].z;
P[j].x=P[j+1].x;
P[j].y=P[j+1].y;
P[j].z=P[j+1].z;
P[j+1].x=tx;
P[j+1].y=ty;
P[j+1].z=tz;
flag=1;
}
}
if(flag==0)break; //这轮没有交换，不用进入下一轮排序
}
cout <<"排序后的坐标 :"<<endl;
for(i=0;i<m;i++)
{
cout <<P[i].x<<" "<<P[i].y<<" "<<P[i].z<<endl;
}
cout <<endl;
}
（2）主程序提示输入一个正整数n，表示有n组测试用例。对于每组测试用例，会提示输入一个正整数m，表示需要排序的点的数量；然后是m行，提示每行输入3个整数，分别表示点的x、y和z坐标值。代码如下：
void main()
{
Po P[5];
int i;
int n,m;
cout <<"输入你要多少组测试用 :"<<endl;
cin>>n; //输入一个正整数n，表示有n组测试用例
while(n!=0)
{
cout <<"需要排序的坐标点的数量 :"<<endl;
cin >>m; //每组测试会输入一个正整数m，表示需要排序的点的数量
cout <<"开始输入点的X和Y坐标 :"<<endl;
for(i=0;i<m;i++) //m行，每行包括两个整数
{
//分别表示点的x坐标和y坐标
cin >>P[i].x>>P[i].y>>P[i].z;
}
Sort(P,m);
n--;
}
system("pause");
}
【案例分析】
（1）数组的声明可以是任何一种有效的对象数据类型，如int、float等；也可以是一个结构，如本实例定义的三维坐标点结构typedef struct Point。在Sort()函数中，用3个for循环实现x、y和z坐标值的冒泡排序，与上例不同的是，本例用了3个if判断进行坐标值交换。
（2）函数void Sort(Po P[], int m)中的Po P[]是函数数组，也就是把数组参数传递给函数。函数参数的传递是将实参的值赋给形参，但对于数组作为参数是一个例外。因为数组的数据太多，将其一一赋值既麻烦，又浪费空间，所以数组作为参数传递给函数的只是数组首元素的地址，函数在需要用到后面的元素时，再按照这个地址和数组下标去查找。也就是说，后面的元素根本没进入函数中，所以在函数里求不出数组的大小。
注意：一个函数的输入参数是一个数组时，必须让这个函数知道数组的大小，因为数组传递给函数的是数组首元素在内存中的地址。
案例3-14 按位数排列
【案例描述】
编程的目的是解决存在的现实问题，本实例把千位数的数字存储在不同的数组中，用for循环和if比较的方法，由小到大排序。本例效果如图3-14所示。
图3-14 按位数排列
【实现过程】
有20个4位数，编程将这些数按千位由小到大排列，若千位相同，则按十位排列。代码如下：
#include <iostream>
using namespace std;
int main()
{
int a[10][3]={{1631},{2845},{6456},{1467},{4566},
{4518},{5605},{5706},{1365},{3458}};
int i,j,k;
int t[3];
for(i=0;i<10;i++)
{a[i][1]=a[i][0]/1000; //千位数
a[i][2]=a[i][0]/10%10; //十位数
}
for(i=0;i<10;i++) //for循环
for(j=i+1;j<10;j++)
{ if(a[i][1]<a[j][1]) //千位数比较
for(k=0;k<2;k++)
{ t[k]=a[j][k]; a[j][k]=a[i][k]; a[i][k]=t[k]; }//交换
else if (a[i][1]==a[j][1]) //千位数相同
if(a[i][2]<a[j][2]) //十位数比较
for(k=0;k<2;k++)
{ t[k]=a[j][k]; //交换
a[j][k]=a[i][k];
a[i][k]=t[k]; }
}
cout<<"输出排序后的数："<<endl;
for(i=0;i<10;i++)
printf("%6d\n",a[i][0]); //输出排序后的数
system("pause");
return 0;
}
【案例分析】
for循环中对千位数进行比较，然后进行交换；如果千位数相同，那么就进行十位数比较，交换数字。
案例3-15 统计班上男生和女生的人数（数组随机访问）
【案例描述】
现演示一个有趣的程序。班上有26个学生（包括男生和女生），随机安排在10´10的教室里，上下左右移动，哪里有空位置，就安排到那里，最后统计每排男生和女生的数量。本例效果如图3-15所示。
图3-15 统计班上男生和女生的人数（数组随机访问）
【实现过程】
定义二维数组laby2存储10´10教室的值，一维数组all_letter存储班上男生和女生的值；4个方位变量up、down、right和left，初始化值为true；用两个for循环数组laby，每个元素赋值为'.'；然后用while循环对26个学生（代码中是27个，“#”结束指示用）都随机安排位置，是随机算法step=rand()%4，其功能是随机产生一个数和4进行取模运算，switch(step)表示上、下、左和右方向。其代码如下：
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
#define ROW 10
#define COL 10
//A至L代表男生，M至Z代表女生
int main()
{
//定义1个二维数组并赋初值
int laby[ROW][COL],all_letter[27]={'A','B','C','D','E','F','G','H','I','J',
'K','L','M','N','O','P','Q','R','S','T',
'U','V','W','X','Y','Z','#'};
int row,col,letter,step;
bool up,down,right,left;
up=down=right=left=true; //4个方向都通
for(row=0;row<ROW;row++) //执行2次for循环
for(col=0;col<COL;col++)
laby[row][col]='.'; //数组laby初始化为'.'
srand((unsigned int) time(NULL));
row=col=letter=0;
laby[row][col]=all_letter[letter++];
//std::cout<<row<<col<<all_letter[letter]<<endl;
while(letter<27) //全部输出26个字母
{
step=rand()%4; //值为0、1、2、3
//step取值0、1、2和3，表示向上、下、左和右方向移动
switch(step)
{
case 0:if(up=((row-1>=0)&&(laby[row-1][col]=='.')))
{
// std::cout<<row<<col<<endl;
row--;
laby[row][col]=all_letter[letter++];
break;
}
case 1:if(down=((row+1<ROW)&&(laby[row+1][col]=='.')))
{
//std::cout<<row<<col<<endl;
row++;
laby[row][col]=all_letter[letter++];
break;
}
case 2:if(left=((col-1>=0)&&(laby[row][col-1]=='.')))
{
//std::cout<<row<<col<<endl;
col--;
laby[row][col]=all_letter[letter++];
break;
}
case 3:if(right=((col+1<COL)&&(laby[row][col+1]=='.')))
{
//std::cout<<row<<col<<endl;
col++;
laby[row][col]=all_letter[letter++];
break;
}
}
if(!up&&!down&&!left&&!right) //4个方向都堵住了
break;
up=down=right=left=true; //4个方向都设置为true
}
for(row=0;row<ROW;row++) //输出数组的值
{
for(col=0;col<COL;col++)
printf("%3c",laby[row][col]);
cout<<endl;
}
int sex1=0,sex0=0;
for(col=0;col<COL;col++) //输出数组的值
{
for(row=0;row<ROW;row++)
{
if((laby[col][row]>='A')&&(laby[col][row]<='L'))
sex1++;
else if(laby[col][row]!='.')
sex0++;
}
std::cout<<"第 "<<col<<"排男生人数："<<sex1<<" "<<"女生人数："<<sex0<<endl ;
sex1=0;sex0=0;
// printf("%3c",laby[row][col]);
cout<<endl;
}
return 0;
}
【案例分析】
（1）本实例用到两个数组laby和all_letter，数据类型都是整型。数组赋值的时候是字符，其原理是赋值给数组的是字符的ASCII码值；数组all_letter的值从位置0开始，也就是从'A'开始往后移动，数组laby[row][col]的下标是随机的。
（2）代码中if ((a%num)!=0)使用了if控制结构；（%）取模运算，step=rand()%4取值固定为0、1、2、3，switch(step)取值是4种可能；for和while表示循环。
注意：从本实例中可知道数组下标是随机的，即随便移到哪个下标都可以赋值。
案例3-16 内存指令表（数组+开关）
【案例描述】
本实例涉及使用数组元素作为开关，用switch编写统计输入的一串字母中元音字母（a、e、i、o、u）的总个数和每个元音字母出现的次数。当输入“#”时结束输入。本例效果如图3-16所示。
【实现过程】
定义一个字符数组c[]，定义变量并初始化a=e=i=o=u=sum=0;，分别为a、e、i、o、u和sum出现的次数及它们的总次数，执行一个循环for，遍历数组的每个元素，循环中用开关语句switch(c[i1])，累加指定字符出现的次数，计算总次数，并且输出每个字符出现的次数及总次数。其代码如下：
#include <iostream>
using namespace std;
int main()
{
int a,e,i,o,u,sum;
char c[]="(*paeNumabieros)[0]#";
a=e=i=o=u=sum=0; //初始化
const int len = sizeof( c ) / sizeof( c[0] ); //数组长度
for (int i1=0;i1<len;i1++) //循环
{
if(c[i1]=='#')
break;
switch(c[i1]) //累加指定字符出现的次数
{
case 'a': a++;break;
case 'e': e++;break;
case 'i': i++;break;
case 'o': o++;break;
case 'u': u++;break;
default :break;
}
// cout<<"c[i1]="<<c[i1]<<endl;
}
sum=a+e+i+o+u;
cout<<"每个字符出现次数及它们的和："<<endl;
cout<<"'a'="<<a<<" "<<"'e'="<<e<<" "<<"'i'="<<i<<" "<<"'o'="<<o<<" "<<"'u'="<<u<<" "<<"sum="<<sum<<endl;
system("pause");
return 0;
}
【案例分析】
（1）step=rand()%4取值固定为0到4的数，同理，(rand()%26)取值固定为0到26的数。前面学过选择结构的格式switch (expression) {case constant1:block 1 break;default:default block of instructions}。计算表达式expression的值，并检查它是否与第一个常量constant1相等，如果相等，程序执行常量1后面的语句块block 1，直到碰到关键字break，然后程序跳转到switch选择结构的结尾处。代码中用c[i1]作为表达式。
（2）字符数组c[]中存储的是字符。同样，字符数组和其他的数组操作是一样的，它与其他的数组遵循同样的规则，代码中，switch(c[i1])取得下标i1对应的元素值。
注意：switch (expression)开关表达式中，expression是一个可变的值，如代码中switch(c[i1])表达式是一个字符的数组。
案例3-17 同学姓名册（字符数组）
【案例描述】
本实例是简单处理学生信息的小程序，功能是输入学生姓名、性别和年龄，定义一个类，并利用类的成员函数依次显示学生信息。本例用到了字符数组，最终的效果如图3-17所示。
说明：本例会涉及第9章类的概念。
图3-17 同学姓名册（字符数组）
【实现过程】
（1）定义一个学生信息的数据结构，结构的成员有存储姓名的字符指针name、bool类型的性别、整型变量age，以及定义一个指针指向下一个结构的值；定义一个类Student，构造函数Student::Student赋值给类姓名、性别、年龄和人数，析构函数Student::~Student释放类内存空间；定义一个成员函数print()显示输出学生情况。其代码如下：
#include<iostream.h>
#include<string.h>
#include<stdio.h>
struct std //定义一个学生信息结构
{
char* name; //姓名
bool sex; //性别
unsigned int age; //年龄
std* next; //指针为指向下一个
};
class Student //定义一个类
{
public:
Student(char a[][15],bool b[],unsigned int c[],int n);
~Student();
void print(); //输出学生信息
private:
std*num,*head,*p;
int size;
};
//构造函数
Student::Student(char a[][15],bool* b,unsigned int* c,int n)
{
size=n;
head=new std;
head->next=NULL;
num=head;
for(int i=0;i<size;i++)
{
p=new std;
p->name=a[i];
p->sex=*(b+i);
p->age=*(c+i);
p->next=NULL;
num->next=p;
num=p;
}
}
Student::~Student() //析构函数
{
p=head->next;
for(int i=0;i<size;i++)
{
num=p->next;
delete p;
p=num;
}
delete head;
// cout<<"析构函数在这里被自动调用！";
cout<<endl;
}
void Student::print() //输出学生的信息
{
p=head->next;
cout<<"学生情况如下：（1代表男性，0代表女性）"<<endl;
cout<<"姓名"<<" "<<"性别"<<" "<<"年龄"<<endl;
for(int i=0;i<size;i++)
{
cout<<p->name<<" "<<p->sex<<" "<<p->age<<endl;
p=p->next;
}
}
（2）主函数定义3个数组，分别存储姓名二维数组stdn、存储性别bool类型数组stds和存储年龄unsigned int类型的数组stda；输入学生姓名、性别、年龄和人数，定义一个Student属性的类SA，为类赋值，并输入学生情况，之后程序依次显示学生信息。代码如下：
void main()
{
const int N=3; //学生个数
char stdn[N][15]; //姓名
bool stds[N]; //性别
unsigned int stda[N]; //年龄
int stdsex;
unsigned int stdage;
for(int i=0;i<N;i++) //输入每个学生的数据
{
char* stdname;
stdname=new char[10];
cout<<"输入学生姓名： NO."<<i+1<<":";
cin>>stdname;
strcpy(stdn[i],stdname);
cout<<"输入学生性别： NO."<<i+1<<"(1--male,0--female)"<<":";
cin>>stdsex;
if(stdsex)
stds[i]=true;
else
stds[i]=false;
cout<<"输入学生年龄： NO."<<i+1<<":";
cin>>stdage;
stda[i]=stdage;
}
Student SA(stdn,stds,stda,N);
SA.print();
cout<<endl;
getchar();
// SA.Student::~Student(); 错误：析构函数不能被显式调用
}
【案例分析】
（1）字符串实际上就是一串连续字符的序列，所以也可以用简单的字符数组来定义。代码char stdn[N][15];，存储N个最长15个字符的二维数组，字符串中有效内容的结尾处加一个空字符来表示字符结束，它的常量表示可写为0或'\0'。
（2）构造函数如代码中Student::Student，也就是当且仅当声明一个新的对象，或给该类的一个对象分配内存的时候，这个构造函数将自动被调用。析构函数如代码中Student::~Student完成相反的功能，析构函数不能被显式调用，也就是自动释放内存空间。
注意：数组其实只是一个指向被分配的内存块的常量指针，数组自己不能够被赋予任何数值，但可以给数组中的每一个元素赋值。
案例3-18 图书管理系统（字符数组综合）
【案例描述】
本实例涉及第9章类的概念，是一个综合例子，实现图书管理中的增、删、改、查功能。程序也提到了类模板的概念，这些对初学者可能比较难理解，后面会有详细的讲解。本例效果如图3-18所示。
图3-18 图书管理系统（字符数组综合）
【实现过程】
（1）定义图书类CBook，成员有编号、书名和价格，构造函数取得图书的编号、书名和价格，成员函数Display()显示图书；定义一个图书类模板BOOKARRAY，定义图书类模板BOOKARRAY，定义图书管理类CbookManager成员函数有AddBook()、DeleteBook()、ModifyBook()和SearchBook()，实现图书管理中的增、删、改、查功能。代码如下：
#include <iostream>
using namespace std;
#include <vector>
using namespace std;
#include <string.h>
//图书类
class CBook
{
public:
int m_ID; //编号
char m_name[200]; //书名
float m_price; //价格
public:
CBook(int _ID,char* _name,float _price = 0.0f);
public:
void Display(); //输出
};
CBook::CBook(int _ID,char* _name,float _price)
{
this->m_ID = _ID;
strcpy(this->m_name,_name);
this->m_price = _price;
}
void CBook::Display()
{
printf("%d\t%s\t%.2f\n",this->m_ID,this->m_name,this->m_price);
}
typedef vector<CBook*> BOOKARRAY; //定义图书类模板
//图书管理类
class CBookManager
{
public:
BOOKARRAY m_bookarray; //图书集合
public:
void AddBook(CBook* book); //增加图书
void DeleteBook(int id); //根据编号删除图书
void ModifyBook(CBook* book); //修改图书
void SearchBook(int id); //根据编号查找
void SearchBook(char* name); //根据书名查找
void SearchBook(float price); //根据价格查找
};
void CBookManager::AddBook(CBook* book) //增加图书
{
this->m_bookarray.push_back(book);
}
void CBookManager::DeleteBook(int id) //根据编号删除图书
{
BOOKARRAY::iterator it = this->m_bookarray.begin();
while (it != this->m_bookarray.end())
{
if((*it)->m_ID == id)
{
this->m_bookarray.erase(it);
return;
}
++it;
}
}
void CBookManager::ModifyBook(CBook* book) {…//修改图书，代码略}
void CBookManager::SearchBook(int id) {…//根据编号查找，代码略}
void CBookManager::SearchBook(char* name) {…//根据书名查找，代码略}
void CBookManager::SearchBook(float price) {…///根据价格查找，代码略}
（2）主函数演示添加图书、显示所有的图书、按编号删除图书、修改某个编号图书的价格、按书名查找图书。代码如下：
int main()
{
CBookManager bookmanager;
//添加图书
bookmanager.AddBook(new CBook(1, "真相大白/朱振藩著",52.4f));
…
cout <<"显示所有图书:\n";
int len = bookmanager.m_bookarray.size();
cout<<"///////////////////////////\n";
for(int i=0;i<len;i++)
{
bookmanager.m_bookarray[i]->Display();
}
cout<<"///////////////////////////\n";
cout <<"删除编号为15的图书\n";
//删除编号为15的图书
bookmanager.DeleteBook(15);
//修改图书
cout <<"修改编号为3的价格为50.2f\n";
CBook book(3,"味蕾上的情慾/江映瑤著",50.2f);
bookmanager.ModifyBook(&book);
cout <<"显示所有图书:\n";
int len2 = bookmanager.m_bookarray.size();
for( i=0;i<len2;i++)
{
bookmanager.m_bookarray[i]->Display();
}
cout<<"///////////////////////////\n";
//查找图书
cout <<"查找味蕾上的情慾/江映瑤著\n";
bookmanager.SearchBook("味蕾上的情慾/江映瑤著");
system("pause");
return 0;
}
【案例分析】
这是一个综合实例，程序用到类和字符数组书名m_nam。m_name[200]存储最多200个字符数据的数组。代码中CBook* book是指向图书类Cbook的指针。
定义类模板，使得一个类可以基于通用类型的成员，而不需要在类生成的时候定义具体的数据类型。如代码中typedef vector<CBook*> BOOKARRAY;，其功能是实现线性表的功能。
注意：第1、2章演示了类的实例，本章也演示了类的实例，C++语言中，类的概念非常重要，本实例提到的类模板概念将会在第8章详细介绍。
案例3-19 约瑟问题（把异教徒投入海中排法）
【案例描述】
定义不同的数组可以存储不同的值，再加上一定的算法，就能编程实现不少经典的数学问题。如有个数学问题：15名基督教徒和15名异教徒同乘一条船航行，因航行途中出现危机，领航者为全船覆没，唯一的方法是将全船的一半人投入海中其余人就能幸免。程序演示求把异教徒投入海中的排法。本例效果如图3-19所示。
图3-19 约瑟问题（把异教徒投入海中排法）
【实现过程】
编程思想是假定把30个人围成一圈；由第一个人起报数，每数至第9人，便把他投入海中，下一个接着从1开始报数，第9人又被投入海中，依此循环，直至剩下15人为止。问题是如何排列使投入海中的人全为异教徒？代码实现如下：
#include <iostream>
using namespace std;
void main()
{
int i,k,m,s,sh,num[30],sea[15],ship[15];
for (i=0;i<30;i++)
num[i]=i+1; //1至30给每人编号
i=0; //i为每次循环时的计数变量
k=0; //k为按1，2，...，9报数时的计数变量
m=0; //m为退出人数
s=0; //存储被投入海者数组的下标
sh=0; //存储在船上的人编号数组的下标
while (m<15)
{
if (num[i]!=0) k++;
if (k==9)
{
sea[s]=num[i];
s++;
num[i]=0;
k=0;
m++;
}
i++;
if (i==30) i=0;
}
for(i=0;i<30;i++) //打印结果
if (num[i]!=0)
{
ship[sh]=num[i];
sh++;
}
cout<<"被投入海的序号为："<<endl;
for(i=0;i<15;i++)
{
cout<<sea[i]<<" ";
}
cout<<endl<<"留在船上的序号为："<<endl;
for(i=0;i<15;i++)
{
cout<<ship[i]<<" ";
}
cout<<endl;
system("pause");
}
【案例分析】
（1）17世纪法国数学家加斯帕的一本《数学的游戏问题》描述了许多有趣的问题，约瑟问题就是其中一个。
（2）输出结果：9 18 27 6 16 26 7 19 30 12 24 8 22 5 23，经过sort排序后输出的结果为：5 6 7 8 9 12 16 18 19 22 23 24 26 27 30，这15个位置就是异教徒的位置了。
案例3-20 数组转置
【案例描述】
数组是连续存储数据的单元，可以对里面的数据进行处理。如存储在数组中的是字库，可以实现字库中数据的转置，从而实现字库旋转的功能。本例是对存储在数组中的值实现行和列转置，效果如图3-20所示。
图3-20 数组转置
【实现过程】
（1）定义两个二维数组array[M][N]、b[N][M]，定义函数输入转置前和转置后的数组。代码实现如下：
# include <iomanip.h>
# include <iostream>
# include <iostream.h>
# define M 3
# define N 2
int array[M][N],b[N][M]; //定义两个二维数组
void fun(int array[M][N],int b[N][M]) //输入转置前和转置后的数组
{
int i,j;
for (i=0;i<M;i++) //for循环
for (j=0;j<N;j++)
{
b[j][i]=array[i][j]; //数组转置
}
}
（2）主函数for循环输入转置前数组，调用转置函数fun()实现转置功能，打印转置后的数组。代码实现如下：
void main()
{
int i,j;
cout<<"输入数组元素："<<endl;
for (i=0;i<M;i++)
for (j=0;j<N;j++) //for循环
cin>>array[i][j]; //取得输入数组
cout<<" 数组是："<<endl;
for (i=0;i<M;i++) //for循环
{
for (j=0;j<N;j++)
cout<<setw(5)<<array[i][j]<<" ";//打印输入数组
cout<<endl;
}
fun(array,b); //调用转置函数
cout<<"转置后数组是： "<<endl;
for (i=0;i<N;i++) //for循环
{
for (j=0;j<M;j++)
cout<<setw(5)<<b[i][j]<<" "; //打印转置数组
cout<<endl;
}
system("pause");
}
【案例分析】
（1）代码中用两个for循环输入数值，cin>>array[i][j];是输入数组。
（2）函数void fun(int array[M][N],int b[N][M])输入的参数是数组，array是转置前的数组，b[N][M]是转置后的数组。
实例3-21 0-1背包问题
【案例描述】
有N件物品和一个容量为V的背包，假设第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包，可使这些物品的费用总和不超过背包容量，且价值总和最大。本例效果如图3-21所示。
图3-21 0-1背包问题
【实现过程】
定义物品数量、背包容量，主函数定义物品权重、物品大小，调用Package()函数用状态转移方程实现。代码实现如下：
#include <iostream>
#include <vector>
using namespace std;
const int MIN=0x80000000;
const int N=3; //物品数量
const int V=5; //背包容量
int f[N+1][V+1];
int Package(int *W,int *C,int N,int V);
void main(int argc,char *argv[])
{
int W[4]={0,7,5,8}; //物品权重
int C[4]={0,2,3,4}; //物品大小
int result=Package(W,C,N,V);
if(result>0)
{
cout<<endl;
cout<<"the opt value:"<<result<<endl;
int i=N,j=V;
while(i)
{
if(f[i][j]==(f[i-1][j-C[i]]+W[i]))
{
cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<endl; //输出物品权重、物品大小
j-=C[i];
}
i--;
}
}
else
cout<<"can not find the opt value"<<endl;
return;
}
int Package(int *W,int *C,int N,int V)
{
int i,j;
memset(f,0,sizeof(f)); //初始化为0
for(i=0;i<=N;i++)
for(j=1;j<=V;j++)
//此步骤是解决是否恰好满足背包容量
//若“恰好”满足背包容量，即正好装满背包，则加上此步骤，若不需要“恰好”，则初始化为0
f[i][j]=MIN;
for(i=1;i<=N;i++)
for(j=C[i];j<=V;j++)
{
f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]); //状态转移方程
cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl; //输出结果
}
return f[N][V];
}
【案例分析】
背包问题的状态转移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}，这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
注意：f[i][v]有意义的条件是，当且仅当存在一个前i件物品的子集其费用总和为v。所以按照这个方程递推完后，最终的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。
3.4 本章练习