第一节 一维数组
第二节 二维数组
第三节 字符数组和字符串类型
一、为什么要使用数组
通过前面几章的学习，我们已经可以编写程序来解决各种相当复杂的问题了，但是当需要处理的数据比较多时，仅依靠前面的知识是不够的，即使简单的问题也可能需要比较复杂的程序来处理。请看下面的例子：
例题：输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。
【分析】在解决这个问题时，虽然可以通过一个变量来累加读入的50个成绩求出学生的总分，进而求出平均分。但因为只有读入最后一个学生的分数后才能求得平均分，并且要求打印出低于平均分的学生序号和成绩，故必须把50个学生的成绩都保留起来，然后逐个和平均分比较，把低于平均分的成绩打印出来。如果，用简单变量a1，a2,…，a50存储这些数据，要用50个变量保存输入的数据，程序片断如下：
cin>>a1>>a2>>…>>a10;
…
cin>>a41>>a42>>…>>a50;
注意，如果真正要像上面这样编写程序，则上面的所有省略号必须用完整的语句写出来。可以看出，这样的程序是多么繁琐。如果说处理的数据规模达到成千上万，上面的例子单单读入就会异常复杂，电脑的优势没有得到体现。
从以上的讨论可以看出，如果只使用简单变量处理大量数据，就必须使用大量只能单独处理的变量，即使是简单问题也需要编写冗长的程序。
选手们可能已经看出，我们需要把一大批具有相同性质的数据组合成一个新类型的变量，可以用简单的程序（比如循环50次）对这个新变量的各个分量进行相同的处理，每个分量仍然保留单个变量的所有性质（在上面的例子中，各分量是整型变量或实型变量的性质）。
如果能像数学中使用下标变量ai形式表示这50个数，则问题就容易实现。在C++语言中，具有下标性质的数据类型是数组。如果使用数组，上面的问题就变得十分简单、清晰。例如，读入50个学生的成绩，只需写如下语句即可：
for (int i=1;i<=50;++i)
cin>>a[i];
在这里引用了带下标的变量（分量变量称为数组元素）a[i]来代替a1,a2…,a50,方括号中的i称为下标，当循环变量i=1时a[i]就是a[1]；当i=2时a[i]就是a[2]……；当i=50时a[i]就是a[50]。输入的时候，让i从1变化到50，循环体内输入语句中的a[i]也就分别代表了a1,a2…,a50这50个带下标的变量。这样上述问题的程序可写为：
tot = 0; // tot存储50个学生的总分
for (int i=1;i<=50;++i) // 循环读入每一个学生的成绩，并把它累加到总分中
{
cin>>a[i];
tot+=a[i];
}
ave= tot/50; //计算平均分
for (int i=1;i<=50;++i)
if (a[i]<ave) cout<<"No. "<<i<<" "<<a[i];
//如果第i个同学成绩小于平均分，则将输出这个学生的序号和成绩。
要在程序中使用下标变量，必须先说明这些下标变量的整体为数组，即数组是若干个同名（如上面的下标变量的名字都为a）下标变量的集合，这些变量的类型全部一致。
二、一维数组的定义
当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。
数组的定义格式如下：
类型标识符 数组名[常量表达式]
说明：
①数组名的命名规则与变量名的命名规则一致。
②常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量。
例如：
int a[10]; //数组a定义是合法的
int b[n]; //数组b定义是非法的
三、一组数组的引用
通过给出的数组名称和这个元素在数组中的位置编号(即下标)，程序可以引用这个数组中的任何一个元素。
一维数组元素的引用格式：
数组名[下标]
例如：
int a[10];
其中，a是一维数组的数组名，该数组有10个元素，依次表示为：
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]。
需要注意的是：a[10]不属于该数组的空间范围。
当在说明部分定义了一个数组变量之后,C++编译程序为所定义的数组在内存空间开辟一串连续的存储单元。例如：
上例中的a数组在内存的存储如表所示：
a数组共有10个元素组成，在内存中10个数组元素共占10个连续的存储单元。a数组最小下标为0，最大下标9。按定义a数组所有元素都是整型变量。
再次提醒注意：类型和变量是两个不同概念，不能混淆。就数组而言，程序的执行部分使用的不是数组类型而是数组变量。
说明：
(1)下标可以是整型常量或整型表达式。如果使用表达式作为下标，就要计算表达式的值以确定下标。
(2)C++语言中，每个数组第一个元素的下标都是0，因此第一个元素为第0个数组元素。
(3)C++语言只能逐个引用数组元素，而不能一次引用整个数组。
例如：int a[100],b[100]; a=b;这样的写法是非法的。
(4)数组元素可以像同类型的普通变量那样使用，对其进行赋值和运算的操作，和普通变量完全相同。
例如： c[10]=34;实现了给c[10]赋值为34。
四、一维数组的初始化
数组的初始化可以在定义时一并完成。格式：
类型标识符 数组名[常量表达式]={值1，值2，…}
例如：
int a[5]={1,2,3,4,5}
说明：
(1)在初值列表中可以写出全部数组元素的值，也可以写出部分。例如，以下方式可以对数组进行初始化：
int x[10]={0,1,2,3,4};
该方法一次仅对数组的前5个元素依次进行初始化。
(2)对数组元素全部初始化为0，可以简写为：{0}。
例如：
int a[5]={0}; 将数组a的5个元素都初始化为0。
五、一维数组的应用
例5.1 输入n个数,要求程序按输入时的逆序把这n个数打印出来，已知整数不超过100个。也就是说，按输入相反顺序打印这n个数。
【分析】我们可定义一个数组a用以存放输入的n个数, 然后将数组a中的内容逆序输出。
#include<cstdio>
int a[100];
int main()
{
int x,n=0;
while(scanf("%d",&x)==1) a[n++]=x; //相当{a[n]=x;n++;}
for (int i=n-1;i>=1;--i)
printf("%d ",a[i]); //注意%d后面有一个空格，保证行首行尾均无空格
printf("%d\n",a[0]);
return 0;
}
【说明】：
语句int a[100]声明了一个包含100个整型变量的数组，它们是：a[0]，a[1]，a[2]，…，a[99]。注意，没有a[100]。在上述程序中，数组a被声明在main函数的外面。只有放在外面时，数组a才可以开得很大；放在main函数内时，数组稍大就会异常退出。它的道理将在后面讨论，只需要记住规则即可。
数组不能够进行赋值操作：如果声明的是int a[MAXN]，b[MAXN],是不能赋值b=a的(Pascal语言可以的)。如果要从数组a复制k个元素到数组b，可以这样做：memcpy(b,a,sizeof(int)*k)。当然了，如果数组a和b都是浮点型的，复制时要写成memcpy(b,a,sizeof(double)*k)。如果需要把数组a全部复制到数组b中，可以写得简单一些：memcpy(b,a,sizeof(a))。使用memcpy函数要包含头文件cstring。
例5.2 将a数组中第一个元素移到最后数组末尾,其余数据依次往前平移一个位置。
【分析】为完成题目所要求的操作，其算法应该包括以下几个主要步骤：
①把第一个元素的值取出放在一个临时单元 temp中；
②通过 a[2]→a[1], a[3]→a[2], a[4]→a[3]，……， a[n]→a[n-1],实现其余元素前移
③将 temp值送入a[n].
#include<iostream>
#include<iomanip> //调用setw函数需注明使用该库
const int n=10;
using namespace std;
int a[n],temp;
int main()
{
cout<<"read "<<n<<" datas"<<endl;
for (int i=0; i<n; ++i) cin>>a[i];
temp=a[0];
for (int i=0; i<n-1; ++i) a[i]=a[i+1];
a[n-1]=temp;
cout<<"Result:"<<endl;
for (int i=0; i<n; ++i) cout<<setw(3)<<a[i]; //setw函数控制输出场宽
return 0;
}
运行结果 :
read 10 datas:
• 1 2 3 4 5 6 7 8 9 10
Result:
• 2 3 4 5 6 7 8 9 10 1
例5.3 宾馆里有一百个房间，从1-100编了号。第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间“相反处理”，第三个服务员把所有编号是3的倍数的房间作“相反处理”…，以后每个服务员都是如此。当第100个服务员来过后，哪几扇门是打开的。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）
【分析】此题较简单，用a[1],a[2],…,a[n]表示编号为1，2，3，…,n的门是否开着。模拟这些操作即可，参考程序如下：
#include<cstdio>
#include<cstring>
#define MAXN 100+10
int a[MAXN];
int main()
{
int n,k,first=1;
memset(a,0,sizeof(a));
for (int i=1;i<=100;++i)
for (int j=1;j<=100;++j)
if (j%i==0) a[j]=!a[j];
for (int i=1;i<=100;++i)
if (a[i])
{
if(first) first=0;
else printf(" ");
printf("%d",i);
}
printf("\n");
return 0;
}
运行结果：
1 4 9 16 25 36 49 81 100
【说明】：
memset(a,0,sizeof(a))的作用是把数组a清零，它在cstring中定义。虽然也能用for循环完成相同的任务，但是用memset又方便又快捷。另一个技巧在输出：为了避免输出多余空格，设置了一个标志变量first，可以表示当前要输出是否为第一个。第一个变量前不应该有空格，但其他都有。
例5.4 约瑟夫问题：N个人围成一圈，从第一个人开始报数，数到M的人出圈；再由下一个人开始报数，数到M的人出圈；…输出依次出圈的人的编号。N，M由键盘输入。
【分析】 （1）由于对于每个人只有出圈和没有圈两种状态，因此可以用布尔型标志数组存储游戏
过程中每个人的状态。不妨用true表示出圈，false 表示没有出圈。
（2）开始的时候，给标志数组赋初值为false，即全部在圈内。
（3）模拟报数游戏的过程，直到所有的人出圈为止。
程序如下：
#include<iostream>
using namespace std;
int n,m,s,f,t;
bool a[101]; //根据题意开出数组大小
int main()
{
cin>>n>>m; //共n人，报到m出圈
cout<<endl;
for (t=1;t<=n;++t) a[t]=false; //等同于memset(a,0,sizeof(a)),要调用cstring库
f=0; t=0; s=0; //刚开始所有变量默认值也是0,或者用f=t=s=0;
do
{
++t; //逐个枚举圈中的所有位置
if (t==n+1) t=1; //数组模拟环状，最后一个与第一个相连
if (a[t]==false) ++s; //第t个位置上有人则报数
if (s==m) //当前报的数是m
{
s=0; //计数器清零
cout<<t<<" "; //输出出圈人的编号
a[t]=true; //此处的人已出圈，设置为空
f++; //出圈的人数增加一个
}
} while(f!=n); //直到所有的人都出圈为止
return 0;
}
运行结果：
输入： 8 5
输出： 5 2 8 7 1 4 6 3
这是一个在算法设计上很有名气的经典约瑟夫（Josephu）问题，它有很多变例。如猴子选大王、持密码报数、狐狸追兔子等（见上机练习）。
例5.5 输入十个正整数,把这十个数按由大到小的顺序排列。（选择排序 ）
将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序是一种较简单的方法。
【问题分析】
要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……。因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次小的数。于是十个数的顺序排列结束。
如对5个进行排序，这个五个数分别为8 2 9 10 5。按选择排序方法，过程如下：
初始数据 ：8 2 9 10 5
第一次排序：8 2 9 10 5
9 2 8 10 5
10 2 8 9 5
10 2 8 9 5
第二次排序：10 8 2 9 5
10 9 2 8 5
10 9 2 8 5
第三次排序：10 9 8 2 5
10 9 8 2 5
第四次排序：10 9 8 5 2
对于十个数，则排序要进行9次。
程序如下：
#include<iostream>
#include<iomanip>
using namespace std;
int t,a[11];
int main()
{
cout<<"Input 10 intergers:"<<endl;
//读入10个初始数据
for (int i=1; i<=10; ++i) cin>>a[i];
cout<<endl;
for (int i=1; i<=9; ++i) //进行9次排序
for (int j=i+1; j<=10; ++j)
//将第i个数与其后所有数比较
if (a[i]<a[j]) { t=a[i]; a[i]=a[j]; a[j]=t;}
//若有比a[i]大,则与之交换
for (int i=1;i<=10;++i)
cout<<setw(5)<<a[i];
return 0;
}
运行结果：
输入： 8 67 52 189 74 5 58 9 23 41
输出： 189 74 67 58 52 41 23 9 8 5
例5.6 编程输入十个正整数，然后自动按从大到小的顺序输出。（冒泡排序）
【问题分析】
①用循环把十个数输入到A数组中；
②从A[1]到A[10]，相邻的两个数两两相比较，即：
A[1]与A[2]比，A[2]与A[3]比，……A[9]与A[10]比。
只需知道两个数中的前面那元素的标号，就能进行与后一个序号元素（相邻数）比较，可写成通用形式A[i]与A[i+1]比较，那么，比较的次数又可用1～( n-i )循环进行控制(即循环次数与两两相比较时前面那个元素序号有关) ；
③在每次的比较中，若较大的数在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位置。
下面例举5个数来说明两两相比较和交换位置的具体情形：
5 6 4 3 7
5和6比较，交换位置，排成下行的顺序；
6 5 4 3 7
5和4比较，不交换，维持同样的顺序；
6 5 4 3 7
4和3比较，不交换，顺序不变
6 5 4 3 7
3和7比较，交换位置，排成下行的顺序；
6 5 4 7 3
经过（1～（n-1））次比较后，将3调到了末尾
经过第一轮的1～ (N-1)次比较，就能把十个数中的最小数调到最末尾位置，第二轮比较1～ (N-2)次进行同样处理，又把这一轮所比较的“最小数”调到所比较范围的“最末尾”位置；……；每进行一轮两两比较后，其下一轮的比较范围就减少一个。最后一轮仅有一次比较。在比较过程中，每次都有一个“最小数”往下“掉”，用这种方法排列顺序，常被称之为“冒泡法”排序。
程序如下：
#include<iostream>
#include<iomanip>
using namespace std;
const int n=10;
int t,a[n+1]; //定义数组
int main()
{
for (int i=1; i<=n; ++i) cin>>a[i]; //输入十个数
for (int j=1; j<=n-1; ++j) //冒泡法排序
for (int i=1; i<=n-j; ++i) //两两相比较
if (a[i]<a[i+1]) //比较与交换
{t=a[i]; a[i]=a[i+1]; a[i+1]=t;}
for (int i=1; i<=n; ++i)
cout<<setw(5)<<a[i];
//输出排序后的十个数
cout<<endl;
return 0;
}
运行结果：
输入： 2 5 8 6 12 34 65 22 16 55
输出： 65 55 34 22 16 12 8 6 5 2
例5.7 用筛法求出100以内的全部素数，并按每行五个数显示。
【问题分析】
⑴ 把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；
⑵ 在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；
⑶ 从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置 0；
⑷ 让p=p+1，重复执行第②、③步骤，直到minp>floor(sqrt(N)) 为止；
⑸ 打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。
用筛法求素数的过程示意如下（图中用下划线作删去标志）：
① 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 //置数
② 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 //筛去被2整除的数
③ 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 //筛去被3整除的数
……
2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100
//筛去被整除的数
程序如下：
#include<iostream>
#include<math.h>
//在Dev C++中可调用数学函数库cmath
#include<iomanip>
using namespace std;
const int n=100;
int t;
bool a[n+1];
int main()
{
for (int i=0; i<=n; ++i) a[i]=true;
//等同于memset(a,1,sizeof(a)) ,
要调用cstrin库
a[1]=false;
for (int i=2; i<=sqrt(n); ++i)
if (a[i])
for (int j=2; j<=n/i; ++j)
a[i*j]=false;
t=0;
for (int i=2; i<=n; ++i)
if (a[i])
{
cout<<setw(5)<<i;
t++;
if (t%5==0) cout<<endl;
}
return 0;
}
【上机练习5.1】
1、国际象棋盘中，第1格放1粒米，第2格放2粒米，第3格放4粒米，第4格放8粒米，第5格放16粒米，．．．．．．问：16个格子总共可以放多少粒米？
【分析】第i个格子可放多少粒米：2i–1
2、输出斐波列契数列的前N项（5个1行）
0 1 1 2 3 5 8 13 21 ．．．．．．．．．．
3、输入N个整数，找出最大数所在位置，并将它与第一个数对调位置。
4、将一个数组中的所有元素倒序存放 。
【分析】A[1]←→A[N] A[2] ←→A[N-1]…… A[I] ←→A[J]
I 从1开始，每交换1次，I 加1；直到 I = N DIV 2
5、读入n个数，打印其中的最大数及其位置号。
6、有52张朴克牌，使它们全部正面朝上。从第2张牌开始，把凡是2的倍数位置上的牌翻成正面朝下；接着从第3张牌开始，把凡是3的倍数位置上的牌正面朝上的翻成正面朝下，正面朝下的翻成正面朝上；接着从第4张牌开始，把凡是4的倍数位置上的牌按此规律翻转；依此类推，直到第1张要翻的牌是第52张为止。统计最后有几张牌正面朝上，并打印出它们的位置。
7、围绕着山顶有10个洞，一只狐狸和一只兔子各住一个洞。狐狸总想吃掉兔子。一天兔子对狐狸说：“你想吃我有一个条件，先把洞从1～10编上号，你从10号洞出发，先到1号洞找我；第二次隔1个洞找我，第三次隔2个洞找我，以后依此类推，次数不限。若能找到我，你就可以饱餐一顿。不过在没有找到我以前不能停下来。”狐狸满口答应就开始找了，它从早到晚找了1000次洞，累得昏了过去也没有找到兔子。请问，免子躲在几号洞里？【答案】2，4，7，9
第二节 二维数组
一、二维数组的定义
当一维数组元素的类型也是一维数组时，便构成了“数组的数组”，即二维数组。二维数组定义的一般格式：
数据类型 数组名[常量表达式1] [常量表达式2] ；
例如：int a[4][10];
a数组实质上是一个有4行、10列的表格，表格中可储存40个元素。第1行第1列对应a数组的a[0][0]，第n行第m列对应数组元素a[n-1][m-1]。
说明：当定义的数组下标有多个时，我们称为多维数组，下标的个数并不局限在一个或二个，可以任意多个，如定义一个三维数组a和四维数组b：
int a[100][3][5];
int b[100][100][3][5];
多维的数组引用赋值等操作与二维数组类似。
二、二维数组元素的引用
二维数组的数组元素引用与一维数组元素引用类似，区别在于二维数组元素的引用必须给出两个下标。
引用的格式为：
<数组名>[下标1][下标2]
说明：显然，每个下标表达式取值不应超出下标所指定的范围，否则会导致致命的越界错误。
例如,设有定义：int a[3][5];
则表示a是二维数组（相当于一个3*5的表格），共有3*5=15个元素，它们是：
a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
a[2][0] a[2][1] a[2][2] a[2][3] a[2][4]
因此可以看成一个矩阵（表格），a[2][3]即表示第3行第4列的元素。
三、二维数组的初始化
二维数组的初始化和一维数组类似。可以将每一行分开来写在各自的括号里，也可以把所有数据写在一个括号里。
例如：
int direct[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}
int direct[4][2] = {1,0,0,1,-1,0,0,-1} //尽量不要用
四、二维数组程序设计
例5.8 设有一程序
三、二维数组的初始化
二维数组的初始化和一维数组类似。可以将每一行分开来写在各自的括号里，也可以把所有数据写在一个括号里。
例如：
int direct[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}
int direct[4][2] = {1,0,0,1,-1,0,0,-1} //尽量不要用
四、二维数组程序设计
例5.8 设有一程序
#include<cstdio>
#include<iostream>
#include<iomanip>
const int n=3;
using namespace std;
int a[n+1][n+1];
int main()
{
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=n; ++j)
cin>>a[i][j];
getchar();
}
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=n; ++j)
cout<<setw(5)<<a[j][i];
cout<<endl;
}
return 0;
}
程序的输入:
2 1 3
3 3 1
1 2 1
程序的输出:
2 3 1
1 3 2
3 1 1
例5.9 已知一个6*6的矩阵（方阵），把矩阵二条对角线上的元素值加上10，然后输出这个新矩阵。
【分析】 矩阵即表格，是一个二维数组，有6行6列共36个元素，每个矩阵都有二条对角线，本题难点在于对角线的元素怎么确定。
#include<iostream>
#include<iomanip>
using namespace std;
int a[7][7];
int main()
{
for (int i=1; i<=6; ++i) //输入矩阵元素
for (int j=1; j<=6; ++j)
cin>>a[i][j];
for (int i=1; i<=6; ++i) //更改对角线上元素的值
for (int j=1; j<=6; ++j)
if ((i==j)||(i+j==7)) a[i][j]+=10; //寻找对角线的特征
for (int i=1; i<=6; ++i) //输出6行6列的矩阵元素
{
for (int j=1; j<=6; ++j)
cout<<setw(5)<<a[i][j];
cout<<endl;
}
return 0;
}
例5.10 大部分元素是0的矩阵称为稀疏矩阵，假设有k个非0元素，则可把稀疏矩阵用K*3的矩阵简记之，其中第一列是行号，第二列是列号，第三列是该行、该列下的非元素的值。如：
0 0 0 5 写简记成： 1 4 5 //第1行第4列有个数是5
0 2 0 0 2 2 2 //第2行第2列有个数是2
0 1 0 0 3 2 1 //第3行第2列有个数是1
试编程读入一稀疏矩阵，转换成简记形式，并输出。
【分析】 本题中需要解决的主要问题是查找非零元素并记忆位置。将原始矩阵存于数组a。转换后的矩阵存于数组b，当然b数组的行数可以控制在一个小范围内。
#include<iostream>
#include<iomanip>
const int n=3,m=5;
using namespace std;
int main()
{
int a[n+1][m+1],b[101][4],k=0;
for (int i=1; i<=n; ++i) //矩阵初始
for (int j=1; j<=m; ++j)
cin>>a[i][j];
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
if (a[i][j]!=0) //找到非零值，存储
{
++k;
b[k][1]=i;
b[k][2]=j;
b[k][3]=a[i][j];
}
for (int i=1; i<=k; ++i) //输出
{
for (int j=1; j<=3; ++j)
cout<<setw(3)<<b[i][j];
cout<<endl;
}
return 0;
}
运行结果：
输入： 0 0 0 0 5
0 0 4 0 0
1 0 0 0 1
输出： 1 5 5
2 3 4
3 1 1
3 5 1
例5.11 打印杨辉三角形的前10行。杨辉三角形如下图：
1 1
1 1 1 1
1 2 1 1 2 1
1 3 3 1 1 3 3 1
1 4 6 4 1 1 4 6 4 1
[图5-1] [图5-2]
【问题分析】观察图5-1，大家不容易找到规律，但是如果将它转化为图5-2，不难发现杨辉三角形其实就是一个二维表的小三角形部分，假设通过二维数组yh存储，每行首尾元素为1，且其中任意一个非首位元素yh[i][j]的值其实就是yh[i-1][j-1]与yh[i-1][j]的和，另外每一行的元素个数刚好等于行数。有了数组元素的值，要打印杨辉三角形，只需要控制好输出起始位置就行了。
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
int a[11][11];
a[1][1]=1; //设定第一行的值
for (int i=2; i<=10; ++i) //从第二行开始推
a[i][1]=1; a[i][i]=1; //设定每一行的首尾值为1
for (int j=2; j<=i-1; ++j) //当前行非首尾的数
a[i][j]=a[i-1][j-1]+a[i-1][j]; //每个数等于上一行的二个数之和
}
for (int i=1; i<=10; i++)
{
if (i!=10) cout<<setw(30-3*i)<<" "; //控制每行的起始位置，即空格数量
for (int j=1; j<=i; j++) cout<<setw(6)<<a[i][j];
cout<<endl;
}
return 0;
}
例5.12 输入一串字符,字符个数不超过100,且以“.”结束。 判断它们是否构成回文。
【分析】所谓回文指从左到右和从右到左读一串字符的值是一样的，如12321,ABCBA,AA等。先读入要判断的一串字符（放入数组letter中），并记住这串字符的长度，然后首尾字符比较，并不断向中间靠拢，就可以判断出是否为回文。
程序如下：
#include<iostream>
using namespace std;
int main()
{ char ch,letter[101];
int i=0,j=1;
cout<<"Input a string:";
cin>>ch;
while (ch!='.') //读入一个字符串以'.'号结束
{
++i;
letter[i]=ch;
cin>>ch;
}
while ((j<i)&&(letter[j]==letter[i])) //判断它是否是回文
{
--i; ++j;
}
if (j>=i) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
例5.13 蛇形填数
在n*n方阵里填入1,2,3,…,n*n，要求填成蛇形。例如n=4时方阵为：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出，n<=8。
【分析】：
类比数学中的矩阵，我们可以用一个所谓的二维数组来储存题目中的方阵。只需声明一个int a[MAXN][MAXN]，就可以获得一个大小为MAXN×MAXN的方阵。在声明时，两维的大小不必相同，因此也可以声明int a[30][50]这样的数组，第一维下标范围是0,1,2,…,29，第二维下标范围是0,1,2,…,49。
让我们从1开始依次填写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行，第n-1列（别忘了行列的范围是0到n-1，没有第n列）。“笔”的移动轨迹是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如4→5），或者再走就要走到以前填过的格子（例如12→13）。如果我们把所有格子初始为0，就能很方便地加以判断。
#include<cstdio>
#include<cstring>
#define MAXN 10
int a[MAXN][MAXN];
int main()
{
int n,x,y,tot=0;
scanf("%d",&n);
memset(a,0,sizeof(a));
tot=a[x=0][y=n-1]=1;
while (tot<n*n)
{
while (x+1<n && !a[x+1][y]) a[++x][y]=++tot;
while (y-1>=0 && !a[x][y-1]) a[x][--y]=++tot;
while (x-1>=0 && !a[x-1][y]) a[--x][y]=++tot;
while (y+1<n && !a[x][y+1]) a[x][++y]=++tot;
}
for(x=0;x<n;++x)
{
for (y=0;y<n;++y) printf("%3d",a[x][y]);
printf("\n");
}
return 0;
}
【说明】：
这段程序充分利用了C++语言简洁的优势。首先，赋值x=0和y=n-1后马上要把它们作为a数组的下标，因此可以合并完成；tot和a[0][n-1]都要赋值1，也可以合并完成。这样，我们用一条语句完成了多件事情，而且并没有牺牲程序的可读性，这段代码的含义显而易见。
那4条while语句有些难懂，不过十分相似，因此只需介绍其中的第一条：不断向下走，并且填数。我们的原则是：先判断，再移动，而不是走一步以后发现越界了再退回来。这样，我们需要进行“预判”，即是否越界，以及如果继续往下走会不会到达一个已经填过的格子。越界只需判断x+1<n，因为y值并没有修改；下一个格子是(x+1,y)，因此只需a[x+1][y]==0，简写成!a[x+1][y]（其中!是“逻辑非”运算符）。
细心的读者也许会发现这里的一个“潜在bug”；如果越界，x+1会等于n，a[x+1][y]将访问非法内存！幸运的是，这样的担心是不必要的。&&是短路运算符。如果x+1<n为假，将不会计算!a[x+1][y]，也就不会越界了。
至于为什么是++tot而不是tot++，留给读者思考。
【上机练习5.2】
1、输入一个二维数组，找出其中最小的数，输出它的值以及所在行号和列号。
2、输入M行N列数组，将第I行与第J行元素对调（I，J < M）。
3、输入4×4方阵，分别求两条对角线上元素之和。
4、矩阵的转置：
A: B:
1 2 3 转置为 1 4 7 10
4 5 6 2 5 8 11
7 8 9 3 6 9 12
10 11 12
5、给一维数组输入M个整数，假设M=6，数组元素分别为 7 4 8 9 1 5 ，
要求建立一个如下数组（矩阵）：
7 4 8 9 1 5
4 8 9 1 5 7
8 9 1 5 7 4
9 1 5 7 4 8
1 5 7 4 8 9
5 7 4 8 9 1
6、设数组a是有n个元素的整数数组，从中找出最大和子序列。
7、打印杨辉三角形的前10行。
第三节 字符数组和字符串类型
无论数组的下标有几个，类型如何，但数组中全体元素的类型必须相同。数组元素的类型可以是任何类型，当它是字符型时，我们称它为字符数组。由于字符数组与字符类型的应用是计算机非数值处理的重要方面之一，所以我们把它们两个放在一起进行讨论。
下面我们举例说明字符数组的应用。
一、字符类型
字符类型为由一个字符组成的字符常量或字符变量。
字符常量定义:
const
字符常量=‘字符’
字符变量定义:
char 字符变量;
字符类型是一个有序类型, 字符的大小顺序按其ASCⅡ代码的大小而定。
例5.14 按字母表顺序和逆序每隔一个字母打印。即打印出：
a c e g i k m o q s u w y
z x r v t p n l j h f d b
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
for (char letter='a'; letter<='z'; letter+=2)
cout<<setw(3)<<letter;
cout<<endl;
for (char letter='z'; letter>='a'; letter-=2)
cout<<setw(3)<<letter;
return 0;
}
【说明】程序中，我们利用了字符类型是顺序类型这一特性，灵活利用字符变量当作循环变量，使程序处理起来比较直观。
二、字符数组
字符数组是指元素为字符的数组。字符数组是用来存放字符序列或字符串的。字符数组也有一维、二维和三维之分。
1、字符数组的定义格式
字符数组定义格式同于一般数组，所不同的是数组类型是字符型，第一个元素同样是从ch1[0]开始，而不是ch1[1]。具体格式如下：
[存储类型] char 数组名[常量表达式1]…
例如：
char ch1[5]; //数组ch1是一个具有5个字符元素的一维字符数组
char ch2[3][5]; //数组ch2是一个具有15个字符元素的二维字符数组
2.字符数组的赋值
字符数组赋值类似于一维数组，赋值分为数组的初始化和数组元素的赋值。初始化的方式有用字符初始化和用字符串初始化两种，也有用初始值表进行初始化的。
(1).用字符初始化数组
例如：
char chr1[5]={‘a’,’b’,’c’,’d’,’e’};
初始值表中的每个数据项是一个字符，用字符给数组chr1的各个元素初始化。当初始值个数少于元素个数时，从首元素开始赋值，剩余元素默认为空字符。
字符数组中也可以存放若干个字符，也可以来存放字符串。两者的区别是字符串有一结束符(’\0’)。反过来说，在一维字符数组中存放着带有结束符的若干个字符称为字符串。字符串是一维数组，但是一维字符数组不等于字符串。
例如：
char chr2[5]={‘a’,’b’,’c’,’d’,’\0’}; 即在数组chr2中存放着一个字符串“abcd”。
(2).用字符串初始化数组
用一个字符串初始化一个一维字符数组，可以写成下列形式：
char chr2[5]=”abcd”;
使用此格式均要注意字符串的长度应小于字符数组的大小或等于字符数组的大小减1。同理，对二维字符数组来讲，可存放若干个字符串。可使用由若干个字符串组成的初始值表给二维字符数组初始化。
例如：char chr3[3][4]={“abc”,“mno”,“xyz”};在数组ch3中存放3个字符串，每个字符串的长度不得大于3。
(3).数组元素赋值
字符数组的赋值是给该字符数组的各个元素赋一个字符值。
例如：
char chr[3];
chr[0]=’a’; chr[1]=’b’;chr[2]=’c’;
对二维、三维字符数组也是如此。当需要将一个数组的全部元素值赋予另一数组时，不可以用数组名直接赋值的方式，要使用字符串拷贝函数来完成。
(4).字符常量和字符串常量的区别
①两者的定界符不同，字符常量由单引号括起来，字符串常量由双引号括起来。
②字符常量只能是单个字符，字符串常量则可以是多个字符。
③可以把一个字符常量赋给一个字符变量，但不能把一个字符串常量赋给一个字符变量。
④字符常量占一个字节，而字符串常量占用字节数等于字符串的字节数加1。增加的一个字节中存放字符串结束标志“\0”。例如：字符常量’a’占一个字节，字符串常量“a”占二个字节。
三、字符串的输入与输出
字符串可以作为一维字符数组来处理，那么字符串的输入和输出也可以按照数组元素来处理，本节不再做介绍。本节仅介绍将字符串作为一个整体进行输入和输出的语句。
1、输入
从键盘输入一个字符数组可以使用scanf语句或gets语句。
(1)scanf语句
格式：scanf(“%s”,字符串名称);
说明：
①这里的字符串名称之前不加&这个取地址符。例如：scanf(“%s”,&s1)是错误的。
②系统会自动在输入的字符串常量后添加’\0’标志，因此输入时，仅输入字符串的内容即可。
③输入多个字符串时，以空格分隔。
例如：scanf(“%s%s%s”,s1,s2,s3)；从键盘分别输入Let us go，则三个字符串分别获取了三个单词。反过来可以想到，如果仅有一个输入字符串名称的情况下，字符串变量仅获取空格前的内容。
例如：scanf(“%s”,s1)；从键盘分别输入Let us go，则仅有第一个单词被获取，即s1变量仅获取第一个单词Let。
(2)gets语句
格式：gets(字符串名称)；
说明：
使用gets只能输入一个字符串。
例如：gets(s1,s2)；是错误的。使用gets，是从光标开始的地方读到换行符也就是说读入的是一整行，而使用scanf是从光标开始的地方到空格，如果这一行没有空格，才读到行尾。
例如：scanf(“%s”,s1)；gets(s2)；对于相同的输入Hello World!。s1获取的结果仅仅是Hello，而s2获取的结果则是Hello World!
2、输出
向屏幕输出一个字符串可以使用printf语句或puts语句。
(1)printf语句
格式：printf(“%s”,字符串名称);
说明：
①用%s格式输出时，printf的输出项只能是字符串(字符数组)名称，而不能是数组元素。例如：printf(“%s”,a[5]);是错误的。
②输出字符串不包括字符串结束标志符’\0’。
(2) puts语句
格式：puts(字符串名称);
说明：puts语句输出一个字符串和一个换行符。对于已经声明过的字符串a，printf(“%s\n”,a)和 puts(a)是等价的。
例5.15 C++中，一个字符串中的字符可以通过其对应的下标灵活使用。
#include<cstdio> // gets()调用cstdio库
#include<iostream>
#include<cstring> //strlen()调用cstring库, 调用string库在高版C++下编译出错
using namespace std;
int main()
{
char st[100];
gets(st); //gets为专门读字符串的
函数, 读取一行字符串
for (int i=0; i<strlen(st); ++i) //输出st串中的第i个字符
cout<<st[i];
return 0;
}
【参考程序2】（详见第八章第一节和第三节）
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
string cname[10];
int main(){
for (int i=0;i!=10;++i) getline(cin,cname[i]);
sort(cname,cname+10); //利用C++库函数排序
for (int i=0;i!=10;++i) cout<<cname[i]<<endl;
return 0;
}
三、字符串处理函数
系统提供了一些字符串处理函数，用来为用户提供一些字符串的运算。常用的字符串函数介绍如下。
四、应用举例
例5.17 数字统计(Noip2010)
【问题描述】
请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。
比如给定范围[2, 22] ，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6 次。
【输入】
输入文件名为two.in 。
输入共1 行，为两个正整数L 和R，之间用一个空格隔开。
【输出】
输出文件名为two.out 。
输出共1 行，表示数字2 出现的次数。
【输入样例1】two.in
2 22
【输出样例1】two.out
6
【输入样例2】two.in
2 100
【输出样例2】two.out
20
【数据范围】
1 ≤L ≤R ≤10000
【算法分析1】
枚举[L,R]区间的所有整数，对于每个整数x：
1.将整数x转化成字符串s，可以用sprintf(s,"%d",x)来实现；
2.枚举字符串s的每个字符判断是否为2。
【参考程序1】
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[10];
int main()
{
int l,r,ans=0;
cin>>l>>r;
for (int i=l; i<=r; ++i)
{
sprintf(s,"%d",i);
l=strlen(s);
for (int j=0; j<=l-1; ++j)
if (s[j]=='2') ++ans;
}
cout<<ans;
return 0;
}
【算法分析2】
枚举[L,R]区间的所有整数，对于每个整数x：
先判断x的最后一位是否为2（即 x%10==2），然后将x的最后一位删除（即 x/=10），循环操作，直到x值为0。
【参考程序2】
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
int l,r,ans=0;
cin>>l>>r;
for (int i=l; i<=r; ++i)
{
int x=i;
while (x>0)
{
if (x%10==2) ++ans;
x/=10;
}
}
cout<<ans;
return 0;
}
例5.18 数字反转(Noip2011)
【问题描述】
给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。
【输入】
输入文件名为reverse.in。
输入共1 行，一个整数N。
【输出】
输出文件名为reverse.out。
输出共1 行，一个整数，表示反转后的新数。
【输入样例1】
123
【输出样例1】
321
【输入样例2】
-380
【输出样例2】
-83
【数据范围】
-1,000,000,000 ≤ N≤ 1,000,000,000。
【算法分析1】
1.将整数N转化成字符串s，可以用sprintf(s,"%d",N)来实现；
2.对字符串进行反转操作；
3.将字符串s转换成数字N,可以用sscanf(s,"%d",&N)来实现。
4.输出数字N。
【参考程序1】
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[100],c[100];
int main()
{
int n,l;
cin>>n;
sprintf(s,"%d",n);
l=strlen(s);
for (int i=0; i<=l-1; ++i) c[l-i-1]=s[i];
if (n<0) cout<<"-";
sscanf(c,"%d",&n);
cout<<n;
return 0;
}
【算法分析2】
判断数字是否为负数，如果是则先输出符号，并将数字取绝对值；
将数字从后往前转换成字符串；
去掉前导0，然后输出数字。
【参考程序2】
#include<iostream>
#include<cstdio>
using namespace std;
string s;
void Solve(int x) //数字从后往前转换成字符串
{
while (x>0) { s+=x%10+48; x/=10; }
}
int main()
{
int n;
scanf("%d",&n);
if (n<0) { cout<<"-"; n=-n;}
Solve(n);
int j=0,len=s.size();
while ( (j+1!=len) && (s[j]=='0')) ++j; //去掉前导0
for (;j<len; ++j) cout<<s[j];
return 0;
}
例5.19 统计单词数(Noip2011)
【问题描述】
一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。
现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。
【输入】
输入文件名为stat.in，2 行。
第1 行为一个字符串，其中只含字母，表示给定单词；
第2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。
【输出】
输出文件名为stat.out。
只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。
【输入样例1】
To
to be or not to be is a question
【输出样例1】
2 0
【输入输出样例1说明】
输出结果表示给定的单词To 在文章中出现两次，第一次出现的位置为0。
【数据范围】
1 ≤ 单词长度≤ 10。
1 ≤ 文章长度≤ 1,000,000。
【算法分析】
枚举文章中的每个单词；
判断两个单词长度是否相同；
枚举单词中的每个字母，判断是否都相同，如果都相同则答案加一。
【参考程序】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
int i,j,t=0,tt=0;
char s[1000001],ss[11];
cin.getline(ss,11);
cin.getline(s,1000001);
for(i=0;i<=strlen(s)-strlen(ss);++i)
{
for (j=0;j<=strlen(ss)-1;++j)
{
if (toupper(s[j+i])!=toupper(ss[j])) break;
if (i>0&&s[i-1]!=' ') break;
}
if (j==strlen(ss)&&(s[j+i]==' '||j+i==strlen(s)))
{t++;if (t==1) tt=i;}
}
if (t==0) printf("-1");
else printf("%d %d\n",t,tt);
return 0;
}
【算法分析2】（详见第八章第三节）
1.先预处理将所有字母转为大写,将pos置为0；
2.利用string类的find(word,pos)函数查找是否存在单词；
3.如果存在，累加答案，更新pos，返回第二步，否则退出。
【参考程序2】
//string::size_type 为 string 定义的无符整形
#include<algorithm>
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
string word,str;
int main(){
int first=0,ans=0;
cin>>word; word=" "+word+" ";
for (string::size_type i=0;i!=word.size();++i)//string::size_type为无符类型
word[i]=toupper(word[i]);
getline(cin,str); //当我们读完word后，还有换行符
getline(cin,str); str=" "+str+" ";
for (string::size_type i=0;i!=str.size();++i)
str[i]=toupper(str[i]);
for (string::size_type i=str.find(word);i<str.size();
i=str.find(word,i+word.size()-1),++ans) {
if (!ans) first=i; //如果是第一次找到，记录位置
}
if (ans) cout<<ans<<' '<<first<<endl;
else cout<<-1<<endl;
return 0;
}
BC20270380
LV 3
@
2025-3-14 17:11:30