第 3章 数 组第 3章 数 组
3.1 数组的基本概念
3.2 一维数组
3.3 多维数组
3.4 数组作为函数的参数
3.5 数组与字符串
3.6 数组应用举例
3.7 构造数据类型第 3章 数 组
3.1 数组的基本概念数组是一种构造数据类型,是具有统一名称和相同类型的一组数据元素的集合,它占用连续内存单元进行存储 。 要引用数组中的特定位置或元素,就要指定数组中的特定位置或元素的位置号 (position number)。
第 3章 数 组图 3-1显示了整型数组 c的数组元素存储分配 。 这个数组包含 7个元素 。 可以用数组名加上方括号 ([ ])中该元素的位置号来引用该元素 。 数组中的第一个元素称为第 0个元素 。 这样,c数组中的第一个元素为 c[0],c
数组中的第二个元素为 c[1],…,c数组中的第七个元素为 c[6]。 一般来说,c数组中的第 i个元素为 c[i-1]。
第 3章 数 组图 3-1 整型数组 c的数组元素存储分配示意第 3章 数 组方括号中的位置号通常称为下标 (subscript)。 下标应为整数或整型表达式 。
注意：带下标的数组名一般称为下标变量,可用于赋值语句的左边 。 例如：
c[3]=72;
第 3章 数 组
3.2 一 维 数 组
3.2.1 一维数组的声明数组在使用前必须先声明 。 声明一个一维数组的形式如下：
<类型标识符 > <数组名 >[数组长度 ]其中：
① 数组名必须遵循 C++语言对标识符的要求,其命名规则与其它变量名的相同 。
② 数组长度是个常量表达式,它规定了数组的大小,
即所声明的数组由多少个数据类型相同的存储空间组成 。
第 3章 数 组组成数组的对象称为该数组的元素 。 数组元素可存储的数据类型由声明时指定的 C++语言数据类型决定 。
数组的声明为以后使用数组分配了存储空间,数组中每个元素在内存中是依次排列的 。 例如,int Score[50]；定义了名称为 Score的一维数组,该数组有 50个元素,是
int类型的 。
在声明数组时,要注意数组的长度只能由常量表达式来决定,不能是变量 。 即,数组的长度必须是确定的 。
例如：
int nMonth;
float fSales[nMonth *12];
是错误的。这个声明在编译时编译器会给出错误信息。
第 3章 数 组
3.2.2 一维数组中的元素访问数组中的每个元素可以当成普通的变量使用 。 访问一维数组元素的形式如下：
<数组名 >[下标 ]
下标就是元素索引值，它代表了要被访问的数组元素在内存中的相对位置。下标值的允许范围从 0开始到数组长度 -1。下标等于 0代表要访问的元素在数组的第 1个位置上，下标等于 1代表要访问的元素在数组的第 2个位置上，依次类推。
第 3章 数 组例如,声明一个长度为 20的整型数组,并将数组中的各个元素按顺序赋予从 50到 70以 1递增的数,即赋予数组的第 0个元素的值为 50,赋予数组的第 1个元素的值为 51,依此类推 。 写出相应的程序段 。
注意，必须有一个值从 0开始，以 1为增量，递增到 19的变量作为访问数组时的下标，这样才能访问到数组中所有的元素。
第 3章 数 组用一个简单的 for循环就可以做到这一点,而循环控制变量就是最好的下标值 。 要按顺序给数组元素赋予从 50到 70的值,也就是让每个数组元素的值等于其下标值加上 50,所以只要将循环控制变量加上 50赋予相应的数组元素即可 。
程序段代码如下：
int nData[20];
for(int nIndex=0;nIndex<20;nIndex++)
nData[nIndex]=nIndex+50;
第 3章 数 组
【 例 3-1】 生成一个长度为 10的连续偶数序列,该偶数序列从 2开始 。 要求将此序列保存在数组中,并输出此数组的每个元素的值 。
分析：显然,先要声明一个长度为 10的数组 。 模仿上面的做法,可以用一个循环来解决对所有数组元素的访问,关键在于生成数列 。 偶数列是个很简单的数列,如果从 0开始,则规律为：第 i个数等于 i*2(i=0，
1,2,…)；如果从 2开始,则规律为：第 i个数等于
i*2+2(i=0,1,2,…)。
第 3章 数 组程序代码如下：
#include <iostream.h>
void main( )
{
int nEven[10]; //定义用于存放 10个偶数的数组
int nIndex;
for(nIndex=0;nIndex<10;nIndex++)
nEven[nIndex]=nIndex *2+2;
for(nIndex=0;nIndex<10;nIndex++)
{
第 3章 数 组
cout<<nEven[nIndex]<<" ";
}
cout<<endl;
}
程序运行结果为
2 4 6 8 10 12 14 16 18 20
第 3章 数 组
3.2.3 一维数组的初始化变量可以在声明时赋初值,数组也可以在声明时给所有或部分数组元素赋初始值 。 要给一维数组元素赋初始值,有如下两种形式 。
形式 1：
<类型标识符 > <数组名 >[数组长度 ]={第 0个元素值,第 1个元素值,…,第 n-1个元素值 }
形式 2：
<类型标识符 > <数组名 >[ ]={第 0个元素值,第 1个元素值,…,第 n个元素值 }
第 3章 数 组第一种形式将声明一个长度为,数组长度,的值的数组,然后将花括号内的值依次赋予数组的各个元素 。 花括号内只能是常量表达式 。 如果花括号中的常量表达式的个数小于数组长度,则剩余的数组元素就不被赋予初始值；如果花括号中的常量表达式的个数大于数组长度,则编译器会给出错误信息 。
第二种形式将声明一个长度为 n的数组,并将花括号内的 n个值依次赋给数组的各个元素 。
第 3章 数 组
【 例 3-2】 一个班级有 20名学生,所有学生的英语考试成绩保存在一个一维数组中 。 编写程序,求出该班学生的英语考试平均成绩,并统计考试成绩在 90分以上
(包括 90分 )的学生人数和不及格的学生人数 。
分析：为了统计平均成绩,需要有个变量保存所有学生的成绩总和 。 求总和的方法就是在对每个数组元素访问时,将其值累加到这个变量中,然后由此变量除以学生人数即得平均成绩 。 要统计考试成绩 90分以上的学生人数和不及格的学生人数,
第 3章 数 组需要分别设置两个变量 。 在对每个数组元素进行访问时,如果元素值大于等于 90,就将保存考试成绩在 90
分以上的学生人数的变量值加 1；如果元素值小于 60，
就将保存考试成绩不及格的学生人数的变量值加 1。 程序代码如下：
第 3章 数 组
#include <iostream.h>
void main( )
{
int
nScore[20]={90,88,45,92,76,59,89,93,60,51,91,65,82,74,92,
35,66,78,62,91};
//用数组初始化的方法将成绩存于数组 nScore
中
int nUnPassedCount=0; //定义记录不及格人数的变量
int nHighScoreCount=0; //定义记录 90分以上人数的变量
int nSum=0; //定义求和的变量第 3章 数 组
for(int ni=0;ni<20;ni++)
{
nSum+=nScore[ni];
if(nScore[ni]<60)
nUnPassedCount++;
if(nScore[ni]>=90)
nHighScoreCount++;
}
cout<<"平均分数为,"<<(float)nSum/20<<endl;
//将总和除以 20就是平均成绩 。 注意这里为了得到精确的结果,
第 3章 数 组
//使用了强制类型转换将 nSum从 int型转换成 float型
cout<<"90分以上人数为,"<<nHighScoreCount<<endl;
cout<<" 不及格人数为,"<<nUnPassedCount<<endl;
}
程序运行结果为平均分数,73.95
90分以上人数为,6
不及格人数为,4
第 3章 数 组
3.3 多维数组
3.3.1 多维数组的声明声明一个多维数组的形式如下：
<类型标识符 > <数组名 >[长度 1][长度 2]…[长度 n]
同一维数组相同,多维数组的数组名必须遵循 C++
语言标识符的命名规则,常量表达式中不能有任何变量出现 。 为了更直观地介绍多维数组,下面以二维数组为例 。
第 3章 数 组声明一个二维数组的形式如下：
<类型标识符 > <数组名 >[第 1维长度 ][第 2维长度 ]
例如,语句 float fMatrix[3][4]将声明一个数组名为
fMatix且第 1维长度为 3,第 2维长度为 4的二维数组 。 在二维数组中,第 1维常常称为行,第 2维常常称为列 。
这样,一个二维数组就可同一个二维表格对应起来,
如表 3-1所示 。
第 3章 数 组表 3-1 二维数组与表格列行 0 1 2 3
0 fMatrix[0][0] fMatrix[0][1] fMatrix[0][2] fMatrix[0][3]
1 fMatrix[1][0] fMatrix[1][1] fMatrix[1][2] fMatrix[1][3]
2 fMatrix[2][0] fMatrix[2][1] fMatrix[2][2] fMatrix[2][3]
第 3章 数 组可以这样理解二维数组：如果只给出二维数组的第 1维下标,以一维数组来看二维数组,则这样的数组中每个元素所代表的是另一个一维数组 。 例如,
fMatrix[0]代表由 4个 f1oat类型的元素组成的另一个一维数组 （ 数组名为 fMatrix[0],元素为 fMatrix[0][0],
fMatrix[0][1],fMatrix[0][2],fMatrix[0][3]） 。 不难算出,fMatrix中共有 3*4=12个 fIoat型元素 。 这 12个元素在内存中其实也是按顺序存放的：先存放 fMatrix[0]的 4
个元素,紧接着存放 fMatrix[1]的 4个元素,最后存放
fMatrix[2]的 4个元素 。
第 3章 数 组
3.3.2 访问多维数组中的元素要访问多维数组中的元素,同样需要指定要访问的元素的下标 。 多维数组的元素有多个下标,其书写形式如下：
<数组名 >[第 1维下标 ][第 2维下标 ] … [第 n维下标 ]
下标的值也是从 0开始,不能超过该维的长度减 1。
下标的值可以是任意表达式的值,只要其值在该下标的有效范围内即可 。
第 3章 数 组要访问二维数组中的某个元素,必须给出该元素所在的行和列 。 例如,fMatrix[2][1] 代表数组名为
fMatrix的二维数组中位于第 2(从 0开始 )行,第 1(从 0开始 )列的元素 。 同一维数组一样,二维数组的元素也可以当成变量进行赋值或参与各种表达式的计算 。
第 3章 数 组
3.3.3 二维数组的初始化同一维数组一样,二维数组也可以在声明时赋初始值,其形式如下 。 形式 1：
<类型标识符 > <数组名 >[第 1维长度 ][第 2维长度 ]={第 0
个第 2维数据组 }，
{第 1个第 2维数据组 },…,{第 n-1个第 2维数据组 }}
其中,n等于第 1维长度 。
第 3章 数 组形式 2：
<类型标识符 > <数组名 >[第 1维长度 ][第 2维长度 ]={第 0个元素值,
第 1个元素值,…,第 m个元素值 }
其中,m小于或等于第 1维长度乘以第 2维长度 。
在两种形式中,如果花括号中给出的元素个数少于实际的元素个数,则剩余的元素就不会被赋予初始值；如果花括号中给出的元素个数大于实际的元素个数,则编译器会给出错误信息 。
第 3章 数 组
【 例 3-3】 生成如下格式的方阵,将其存入二维数组中,并输出这个二维数组所有元素的值 。
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
第 3章 数 组分析：注意到这个方阵的规律在于,偶数行中的元素按升序排列,奇数行中的元素按降序排列,只要逐行处理方阵中的元素,即可得到这种方阵 。 为了访问二维数组中的所有元素,应使用二重嵌套循环 。 外层循环的循环控制变量作为当前行,内层循环的循环控制变量作为当前列 。 在显示这个二维数组时,为了得到理想的显示效果,要对不同的元素指定不同的显示位置 。
第 3章 数 组程序代码如下：
#include <iostream.h>
void main( )
{
int nRow; //控制行的变量
int nCol; //控制列的变量
int nMatrix[5][5]; //声明二维数组
for(nRow=0;nRow<5;nRow++)
第 3章 数 组
{
for(nCol=0;nCol<5;nCol++)
{
if(nRow%2==0)
nMatrix[nRow][nCol]=nRow*5+nCol+1;
else
nMatrix[nRow][4-nCol]=nRow*5+nCol+1;
}
}
for(nRow=0;nRow<5;nRow++)
{
第 3章 数 组
for(nCol=0;nCol<5;nCol++)
{
cout<<nMatrix[nRow][nCol];
if(nMatrix[nRow][nCol]<10) //控制输出 1位数与 2位数时的不同间隔
cout<<" ";
else
cout<<" ";
}
cout<<endl; //每输出一行后换行
}
}
第 3章 数 组程序运行结果为
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
第 3章 数 组
3.4 数组作为函数的参数在 C++语言中,将整个数组作为参数传递给函数要涉及到指针的概念 。 有关内容将在本书的第 6章进一步讨论,这里只结合数组参数的传递过程做简单介绍 。
要将数组作为参数传递给函数,可由不带方括号的数组名进行 。
第 3章 数 组例如,如果数组声明如下：
int nMatrix[20];
则将数组传递给函数,可用下列函数调用语句：
myArray(nMatrix,20);
要传递数组,大体上有以下两种形式 。
形式 1：
<类型标识符 > <函数名 >(类型标识符 数组名 [ ],int长度 )
形式 2：
<类型标识符 > <函数名 >(类型标识符 数组名 [长度 ])
第 3章 数 组第一种形式适于处理不同长度的数组,数组的实际长度通过另一个参数传递给函数；而第二种形式只可用于传递长度固定的数组 。 不管哪一种形式,传递给函数的都不是数组本身,而是保存数组第 0个元素的内存单元的地址 (即存储数组的起始地址 )。 通过传递数组的开始地址,被调用函数可得到实际数组的准确存放位置 。 因此,被调用函数在函数体中修改数组元素时,实际上是修改原内存地址中的数组元素 。
第 3章 数 组数组名的值实际上就是保存数组中第 1个元素的内存地址的变量,这样的变量称为指针型变量 。 当进行数组传递时,实际参数将此地址值传递给形式参数,
使形式参数同实际参数指向同一内存地址 。 这样在函数中如果改变数组中某个元素的值,在函数外数组中该元素的值也发生改变 。
第 3章 数 组尽管函数调用按地址传递整个数组,但各个数组元素和简单变量一样是按值传递 。 这种简单的单个数据称为下标变量或标量 (scalar)。 要将数组元素传递给函数,可用数组元素的下标名作为函数调用中的参数 。
数组元素、数组名与作为函数形式参数的数组名的这种关系可用图 3-2来表示。
第 3章 数 组第 3章 数 组鉴于上述原因,必须考虑在函数体内对作为形式参数传递而来的数组的操作 。 如果函数体内所有对作为形式参数传递而来的数组的操作只有读操作没有写操作,则不会有任何问题 。 但如果要改变数组元素的值,就必须考虑函数的调用者是否允许函数改变数组元素的值 。 如果不允许,在函数内部必须将数组复制,
所有的更改操作只能对复制品进行 。
【 例 3-4】 某次歌唱比赛有 5名选手参加,有 6名评委分别为选手打分,得分如表 3-2。
第 3章 数 组表 3-2 歌唱比赛记分表评委号选手号 1 2 3 4 5 6
1 9.31 9.20 9.00 9.40 9.35 9.20
2 9.71 9.52 9.50 9.66 9.49 9.57
3 8.89 8.80 9.10 9.25 8.90 9.00
4 9.38 9.50 9.40 9.20 9.90 8.90
5 9.30 8.84 9.40 9.45 9.10 8.89
第 3章 数 组规定的积分规则是：每位选手去掉一个最高分,再去掉一个最低分,然后取剩下的得分的平均分 。 编写程序计算各选手的成绩,并在窗口输出选手号和成绩 。
分析：由于二维数组同二维表格有对应关系，可以用一个二维数组保存所有评委给所有选手评出的成绩。
这样，数组下标的第 1维 (行 )代表的就是选手号 —— i，
第 2维 (列 )代表的是评委号 —— j。
第 3章 数 组在找数组各行元素最大值,最小值的同时还应对数组元素求和,这样,访问完一位选手的所有得分后,
就可以得到该选手得分的总和,最高分和最低分 。 将得分总和减去最高分,最低分,然后再除以 4,就得到选手的最后得分 。
程序代码如下：
#include <iostream.h>
double Context(double pArry[],int nNum)//评分函数
{
第 3章 数 组
int nInum;
double fMark,fMax,fMin; //定义记录成绩,最高分,最低分的变量
fMark=fMax=fMin=pArry[0];
for(nInum=0;nInum<nNum;nInum++)
{
if(pArry[nInum]>fMax)
fMax=pArry[nInum];
if(pArry[nInum]<fMin)
fMin=pArry[nInum];
第 3章 数 组
fMark+=pArry[nInum];
//fMark先记录着所有评委的总分
}
return (fMark-fMax-fMin)/4;
//计算出平均分并返回调用函数
}
void main( )
{
double pfSoreData[5][6]
{
第 3章 数 组
{
{9.31,9.20,9.00,9.40,9.35,9.20},
{9.71,9.52,9.50,9.66,9.49,9.57},
{8.89,8.80,9.10,9.25,8.90,9.00},
{9.38,9.50,9.40,9.20,9.90,8.90},
{9.30,8.84,9.40,9.45,9.10,8.89}
};
int nRow;
cout.precision(3); //设置小数点后的位数
for(nRow=0;nRow<5;nRow++)
第 3章 数 组
{
cout<<nRow+1<<" 号选手成绩为,";
cout<<Context(pfSoreData[nRow],5)<<endl;
}
}
程序运行结果为
1号选手成绩,9.29
2号选手成绩,9.6
3号选手成绩,8.95
4号选手成绩,9.41
5号选手成绩,9.28
第 3章 数 组注意，本例中调用函数形式为
Context(pfSoreData[nRow],5)，将二维数组的第 1维数组名作为实际参数传递给了形式参数。由此，可进一步理解二维数组是若干个一维数组所组成的概念。
第 3章 数 组
3.5 数组与字符串本书的第 1章中介绍过字符型常量与变量，也介绍过字符串常量，但却对字符串变量只字未提。其实，
在 C++语言中没有字符串变量类型。为了表示字符串，
要用到字符数组，对字符串的处理是通过字符数组的每一个元素保存字符串内的每一个字符来进行处理。
而在 Visual C++中，是由其 MFC类库中提供的功能完善的字符串类 CString来完成字符串的各种功能。
第 3章 数 组
3.5.1 字符数组字符型数组就是数组元素的类型是字符型的数组,
简称为字符数组 。 例如,char CBuffer[256];,unsigned
char pDBufrer[5][80]; 都是字符型数组 。 字符型数组的定义和声明同普通数组没有什么区别,主要的不同之处在于字符数组元素的初始化与使用方法 。
字符型数组也可以用通常数组初始化的形式对其元素进行初始化，只不过由于字符型数组中的元素是字符类型，一般用字符型常量给字符型数组赋初值，
例如：
第 3章 数 组
char myChars[ ]={'T','h','i','s',' ','a',' ','c'，
'o','m','p','u','t','e','r'};
除此以外,字符型数组常用两种特殊的初始化方法,
形式如下：
形式 1：
char <数组名 >[ ]="字符串 "
形式 2：
char <数组名 >[ ]={"字符串 "}
这两种形式产生的效果是相同的，它们会产生一个以字符串常量中的每个字符为数组元素且在末尾加个
,\0”的特殊数组。例如：
第 3章 数 组
char pMyStrinq[ ]="This is a computer";
执行后,pMyString数组中的元素依次是：
'T','h','i','s',' ','a','','c','o','m','p','u','t','e'，
'r ','\0'
它等同于
char pMyString[ ]={'T','h','i','s',' ','a',' ','c','o'，
'm','p','u','t','e','r ','\0'};
或
char pMyStrinq[ ]={"This is a computer"};
第 3章 数 组说明：
① 转义字符,\0”表示的是字符串常量中字符串的结束标志,在末尾保存了 0的字符型数组,也可以当成字符串来使用 。 在程序中,凡是可以使用字符串常量的地方,可以使用字符型数组来代替 。
② 字符型数组也是数组,只不过赋初值的方法有点特殊,但不能用赋值的方法进行赋初值 。 例如：
char pMyStrinq[ ];
pMyStrinq[ ]="This is a computer";
是错误的 。
第 3章 数 组
③ 变量可以重复赋值,即变量表示的值在程序运行的过程中可以通过赋值语句改变,但是字符型数组只能改变其元素的值,不能有,数组名 ="字符串 ";”这样的赋值语句出现 。
④ 数组的长度在声明时就已经确定 （ 字符串中字符个数 +1）,在使用的过程中不能更改 。 虽然在程序的运行过程中可以通过改变数组元素的值来改变一个字符型数组所存储的字符串内容,但如果要增加所存的字符串的长度,用静态数组是办不到的 。
第 3章 数 组
3.5.2 字符串的基本运算
C++语言中没有字符串型变量,要实现字符串的运算,例如,连接两个字符串,求字符串长度等,需要另外编写程序对字符型数组进行操作 。 在 C++语言的库函数中提供了各种字符串运算的函数,可以直接调用 。 我们在此给出其中的求字符串长度,字符串复制和字符串连接三种运算的具体实现方法 。 理解这些运算,有助于提高对字符串和字符数组的认识与理解 。
第 3章 数 组
1,求字符串的长度
C++语言的标准字符串以 '\0'结尾,所以求一个字符串的长度,要从字符串的第一个字符算起,直到碰到 '\0'为止 。
假设字符串保存在数组 pString中,求字符串长度的程序段如下：
char pString[ ]="字符串 ";
int nSize=0;
while(pString[nSize]!= '\0')
nSize++;
执行完毕后,整型变量 nSize中保存的值就是字符串
pString的长度 。
第 3章 数 组
2,字符串的复制字符串的复制就是将一个字符型数组 （ 源字符串 ）
的内容照原样复制到另一个字符型数组中 。 方法是：把源字符型数组中的字符依次赋给目的字符型数组,直到碰到 '\0'为止 。
假设源字符串保存在数组 pSource中,目的字符型数组为 pDestination,则字符串复制的程序段如下：
char pSource[ ]="字符串 ";
char pDestination[ ]=[N]; //N≥源字符串长度 +1
int nIndex=0;
第 3章 数 组
while(pSource[nSize]!= '\0')
{
pDestination[nIdex]=pSource[nIdex];
nIndex++;
}
pDestination[nIdex]= '\0'; //标识字符串结束最后的 while循环语句还可简化写为
while(pDestination[nIdex]=pSource[nIndex++]);
第 3章 数 组
3,字符串的连接字符串的连接就是将一个字符串连接到另一个字符串的末尾 。 在进行字符串的连接时,先要找到要被连接的字符串的尾部,然后从尾部的位置开始将另一个字符串复制过来 。
必须注意的是,存储原字符串的数组要有足够的空间来容纳连接进来的另一个字符串,否则在运行时可能产生保护模式错误 。
假设原字符串保存在字符数组 pDest中,要连接进来的字符串存在字符数组 pTocat中,则进行字符串连接的程序段如下：
第 3章 数 组
char pTocat[ ]="要连接进来的字符串 ";
char pDest[N]="现字符串 "; //N≥现字符串长度 +要连接进来的字符串长度 +1
int nSize=0;
int nIndex=0;
while (pDest[nSize]!=0) //找到要被连接的字符串的尾部
nSize++;
do
{
第 3章 数 组
pDest[nSize++]=pTocat[nIdex];
nIdex++;
} while(pTocat[nIdex]!= '\0');
pDest[nSize]= '\0';
第 3章 数 组
3.6 数组应用举例
3.6.1 排序数组元素排序是与数组有关的最重要的算法 。 所谓数组元素排序,是指将数组中的所有元素的位置重新排列,使得数组元素的值按照递增或递减有序排列 。
例如,已知一个一维数组中的元素按顺序是 1,7,3、
22,9,5,以递增排序后,这个数组中元素的排列就变成了 1,3,5,7,9,22。 排序有很多方法,本节介绍常用的选择排序法和冒泡排序法 。
第 3章 数 组
【 例 3-5】 选择排序法例题 。
选择排序法是很朴素的排序方法,它的思想很简单：先找到数组中最大的元素,将这个元素放到数组的最前端；然后在剩下的数组元素中再找出最大的元素,把它放在剩下的这些元素的最前端 。 如此下来,
就能使数组中的元素以递减顺序排列了 。 选择排序法的函数代码如下,
第 3章 数 组
#include <iostream.h>
void main( )
{
int a[6]={1,7,3,22,9,5};
int i,j,t,p;
for(i=0;i<6;i++)
{
p=i;
for(j=i+1;j<6;j++)
第 3章 数 组
if(a[p]>a[j]) p=j; //找本次最小元素的下标
t=a[i];
a[i]=a[p];
a[p]=t;
}
cout<<"排序后的数组为,\n";
for(i=0;i<6;i++)
cout<<" "<<a[i]<<"\n";
}
程序运行结果为第 3章 数 组排序后的数组如下：
1
3
5
7
9
22
第 3章 数 组
【 例 3-6】 冒泡排序法例题 。
冒泡排序法是交换排序法的一种，其基本思路是：
两两比较待排序的序列中的相邻元素，如果不满足顺序要求，就交换这两个元素。这样，第 1轮比较完毕后，
数组中的最大 (或最小 )元素就像气泡一样“冒”到数组的最尾部。可以认为由这个元素组成的只有一个元素的子序列是已经排好序的。然后对剩下的元素继续上述过程，直到全部元素有序。
第 3章 数 组冒泡排序法的函数代码如下：
#include <iostream.h>
void main( )
{
int a[6]={1,7,3,22,9,5};
int i,j,t,flag;
for(i=0;i<6;i++)
{
flag=0;
第 3章 数 组
for(j=0;j<6-i-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
flag=1;
}
if(flag==0) break;
}
cout<<"排序后的数组为,\n";
第 3章 数 组
for(i=0;i<6;i++)
cout<<" "<<a[i]<<"\n";
}
程序运行结果与例 3-5的相同 。
第 3章 数 组
3.6.2 查找数组元素查找是与数组有关的另一种重要算法 。
有时候需要知道一个元素在数组中的位置,即要通过元素值找到其下标值,这就需要用到查找算法 。
本节介绍两种基本的查找方法：顺序查找法和二分查找法 。 顺序查找法的思路很朴素,也容易实现,
但效率不高；二分查找法的效率很高,但要求数组在查找前已经排好序 。 这两种方法各有所长,可根据实际情况灵活选用 。
第 3章 数 组
【 例 3-7】 顺序查找法例题 。
顺序查找法的思路很简单：按顺序逐个访问数组元素,并将其同要找的值比较,直到找到与要查找的值相同的元素 。
顺序查找法的函数代码如下：
#include <iostream.h>
void npFind(int DataArray[ ],int nSize,int fValue)
//其中参数 DataArray[ ]为查找数组,nSize为数组长度,
fValue为要查找的值第 3章 数 组
{
int nIndex,flag=nSize; //设置 flag为查找标记
for(nIndex=0;nIndex<nSize;nIndex++)
if(DataArray[nIndex]==fValue)
{
flag=nIndex;
break; //退出循环
}
if(flag<nSize)
cout<<"元素找到了 ！ 是第 "<<flag+1<<" 个 "<<endl;
第 3章 数 组
else
cout<<"在数组中没有要找的元素 ！ "<<endl;
}
第 3章 数 组
【 例 3-8】 二分查找法例题 。
在数组中的元素已经排好序的前提下,使用二分查找法可以极大地提高查找效率 。 二分查找法的思路是这样的：首先假设数组已经按增序排好序 。 取位于数组中间的元素同要查找的值比较,如果待查值等于这个元素的值,则查找结束 。 如果待查值小于这个元素的值,则要查找的元素肯定在数组的左半边,将数组左半边看成完整的数组,继续使用二分查找法查找 。
如果待查值大于这个元素的值,则要查找的元素肯定在数组的右半边,将数组右半边看成完整的数组,继续使用二分查找法查找 。
第 3章 数 组二分查找法的函数代码如下：
#include <iostream.h>
void efFind(int DataArray[ ],int nSize,int fValue)
{
int flag=0; //设置 flag为查找标记
int nStart=0; //开始元素下标
int nEnd=nSize-1; //结尾元素下标
int nMid; //二分法中间元素下标第 3章 数 组
while(nStart<=nEnd)
{
nMid=(nStart+nEnd)/2; //计算中间元素下标
if(DataArray[nMid]==fValue)
{
flag=1; //标记查找成功
break; //退出循环
}
/*如果待查找的值大于中间元素的值,取后半边继续查找；
否则,取前半边继续查找 */
第 3章 数 组
if(fValue>DataArray[nMid])
nStart=nMid+1;
else
nEnd=nMid-1;
}
if(flag)
cout<<" 元素找到了 ！ 是第 "<<nMid+1<<" 个
"<<endl;
else
cout<<"在数组中没有要找的元素 ！ "<<endl;
}
第 3章 数 组
3.6.3 统计统计也是与数组有关的另一种常用算法 。 当需要知道一个元素在数组中出现的次数时,就要用到统计的算法 。
本节通过两个例子介绍两种基本的统计方法：一种是顺序查找统计法，另一种是借用数组下标值的统计方法。实际上，统计方法很多，可根据具体情况灵活运用。
第 3章 数 组
【 例 3-9】 顺序查找统计例题 。
顺序查找统计,顾名思义就是按顺序逐个访问数组元素,每找到一个要统计的元素就给计数器变量加 1。
顺序查找的程序代码如下：
#include <iostream.h>
void tjData(int DataArray[],int nSize,int tjValue) //顺序查找统计函数
{
int nIndex,tjSum=0;
第 3章 数 组
for(nIndex=0;nIndex<nSize;nIndex++)
if(DataArray[nIndex]==tjValue)
tjSum++;
if(tjSum)
cout<<"元素 "<<tjValue<<" 共有 "<<tjSum<<" 个
"<<endl;
else
cout<<"没有元素 "<<tjValue<<endl;
}
#define N 10
void main( )
第 3章 数 组
{
int a[N]={1,7,3,7,9,3,12,7,15,9};
int toFind;
cout<<"请输入欲统计的元素值,";
cin>>toFind;
tjData(a,N,toFind); //调用统计函数
}
程序运行结果为请输入欲统计的元素值,7
元素 7共有 3个第 3章 数 组
【 例 3-10】 借用数组下标值进行统计例题 。
此方法是一种技巧性算法,主要借用统计元素的一些特性 (比如整除某数后的商均相等或其值就等于数组下标等 )来进行 。 例如,输入若干整数,其值均在
1～ 4的范围内,请编写程序用于统计每个整数出现的次数 。
程序代码如下：
#include <iostream.h>
void main( )
{
第 3章 数 组
int tj[4]={0,0,0,0}; //存放统计结果
int tjData;
cout<<"请输入数据 1～ 4,输入其它时结束,"<<endl;
cin>>tjData;
while(tjData>0&&tjData<5) //限定数据范围的循环
{
tj[tjData-1]++; //注意数组 tj的下标 [tjData-
1]作用
cin>>tjData;
};
cout<<"统计结果为,"<<endl;
第 3章 数 组
for(int i=0;i<4;i++)
cout<<" "<<i+1<<","<<tj[i]<<endl;
}
程序运行结果为请输入数据 1～ 4,输入其它时结束：
1 2 3 4 1 2 6
统计结果：
1∶ 2
2∶ 2
3∶ 1
4∶ 1
第 3章 数 组
3.6.4 字符处理字符处理是 C++语言的特色功能之一,在计算机水平与等级考试中经常遇到 。 关于字符处理的方法很多,
但最主要的还是掌握字符数组下标的灵活运用 。 由于篇幅有限,这里我们仅举一例给以示范 。
第 3章 数 组
【 例 3-11】 在给定的由英文单词组成的字符串中,
找出其中都包含的最长的单词 (同一字母的大小写视为不同字符 )。 约定单词全由英文字母组成,单词之间由一个或多个空白符分隔 。
分析：自左至右顺序扫视字符串,逐个找出单词
(单词开始位置和单词长度 )。 当该单词的长度比已找到的单词更长时,记录该单词的开始位置和长度 。 继续此过程直至字符串扫视结束,最后输出找到的单词 。
第 3章 数 组程序代码如下：
#include <iostream.h>
void main( )
{
char s[ ]="This is C programming test.";
int i=0,pLen=0,maxLen=0,pSeat=0,maxlen=0;
while(s[i]!='\0')
{
while(s[i]!=' '&&s[i]!='\0') //区分单词并计算长度第 3章 数 组
{
pLen++;
i++;
}
if(pLen>maxLen) //记录最长单词的位置与长度
{
pSeat=i-pLen;
maxLen=pLen;
}
while(s[i]==' ') i++; //跳过单词之间的空格
pLen=0; //为计算下一个单词长度赋初值
}
第 3章 数 组
cout<<"最长的单词为,";
for(i=0;i<maxLen;i++) //逐个输出找到的最长单词
cout<<s[pSeat+i];
cout<<endl;
}
程序运行结果为最长的单词是 programming
第 3章 数 组
3.7 构造数据类型
3.7.1 结构体我们已经知道,数组是若干相同类型的数据元素组成的有序集合,但是在处理实际问题时,经常会遇到由相互关联但类型不同的数据组成的数据结构,比如要描述某一商品的一笔销售情况,就要包括商品号,
商品名,单价,数量,金额和销售日期等数据,它们的数据类型各不相同,但属于同一个整体,这样的数据结构在 C++中称为结构体 。
第 3章 数 组
1,结构体类型的定义以前我们介绍的基本类型变量和数组，其数据类型是由 C++本身定义好的，所以，可以直接用这些类型来声明基本变量和数组，但结构体则不同，它是由多种数据成分组成的复杂的数据类型，是随具体问题的数据结构而变化的。
第 3章 数 组例如,要描述商品信息 (商品号,商品名,单价,
数量,金额和销售日期等 ),就要建立商品类型的结构,
要描述学生信息 (如学号,姓名,性别,年龄,入学时间,年级,专业等 ),就要建立学生类型的结构,它们内部的数据组成截然不同 。 因此,C++无法事先建立好一个能描述一切事物的统一的结构体类型,而只能提供一个建立结构体类型的规则 。
第 3章 数 组因此,要定义描述某一问题的数据结构变量,程序员首先应从实际问题要描述的对象出发,自己建立一个结构体类型 (称为结构体类型的定义 ),然后再由这个已定义的结构体类型去定义相应的变量 。
定义一个结构体类型的一般形式如下：
struct <结构体类型名 >
{
<类型标识符 > 成员名 l;
<类型标识符 > 成员名 2;
<类型标识符 > 成员名 n;
};
第 3章 数 组例如,对商品销售记录可定义如下结构体类型：
struct Commodity
{
unsigned long No; //商品号
char name[20]; //商品名
float price; //单价
int number; //销售数量
double amount; //销售金额
};
第 3章 数 组说明：
① 定义结构体类型时,使用关键字 struct。 结构体类型名的命名应符合 C++语言的标识符命名规则 。
② 结构体中的数据成分被称为成员 。 成员可以是基本数据类型,也可以是另一个诸如结构体这样的复杂数据类型 。
③ 大括号内是一个成员表,成员名可以与程序中的变量名相同,但不能与结构体类型名相同,每个成员的末尾以及大括号后边都要加分号 。
第 3章 数 组
④ 若同一个结构体类型要被多个源文件使用,则经常将这些结构体类型的定义集中存放在一个头文件中,源文件中只要用 #include命令包含此头文件即可,
不必在每个源文件中重复同样的结构体类型定义 。 这部分内容将在第 5章详细介绍 。
这里要强调的是,定义一个结构体类型只是向
C++系统通报该结构体类型的名称和各成员的组成,
C++对结构体类型并不分配内存,只有在定义结构体变量时,C++才为结构体变量分配内存 。
第 3章 数 组
2,结构体变量的声明结构体是一种数据类型,同基本数据类型一样,
可以声明变量,作为函数的参数等 。
定义了结构体后,就可以用定义过的结构体类型声明结构体变量了 。 声明结构体变量一般有两种形式,
分别是：
<结构体类型名 > 变量名和
struct <结构体类型名 > 变量名第二种形式是 C语言留下来的,在 C++中不常用 。
第 3章 数 组声明的结构体变量将按照结构体中的各个成员按顺序在内存中分配空间 。 例如,用上面的 Commodity结构体声明一个变量：
Commodity MyComputer;
则 MyComputer将在内存中占用 120个字节,其中
No(商品号 )占 32个,name(商品名 )占 20个,price(单价 )
占 32个,number(销售数量 )占 4个,amount(销售金额 )
占 32个 。
另外,声明结构体变量也可在定义结构体类型的同时进行,其形式如下：
第 3章 数 组
struct [结构体类型名 ]
{
<类型标识符 > 成员名 l;
<类型标识符 > 成员名 2;
<类型标识符 > 成员名 n;
} [变量 1,变量 2,…,变量 n];
例如：
struct Commodity
{
第 3章 数 组
unsigned long No;
char name[20];
float price;
int number;
double amount;
}goods1,goods2;
这里既定义了结构体类型 Commodity,又定义了结构体变量 goods1,goods2,形式比较紧凑 。 如果以后需要再定义新的结构体变量 goods3,goods4,可以直接用语句 Commodity goods3,goods4;进行声明 。
第 3章 数 组
3,结构体变量的初始化所谓结构体变量的初始化,就是在定义结构体变量的同时,对它的每个成员赋初值,其语法形式与数组赋初值非常相似：
<结构体类型 > 变量名 ={表达式 1,表达式 2,…，
表达式 n}
其中,n个表达式分别对应于结构体中的 n个成员。
第 3章 数 组例如：
Commodity goods1={210003,"Computer",6600，
3,19800};
注意：
① 表达式各类型要与结构体成员的类型对应一致 。
② 只可对结构体变量在定义时进行初始化,不可对结构体类型初始化 。 例如：
struct Commodity
{
unsigned long No=210003;
char name[20]= "Computer"：
第 3章 数 组
float price=6600;
int number=3;
double amount=19800;
};
是错误的 。
第 3章 数 组
4,结构体变量的引用一个结构体变量应该以其成员为单位进行访问 。
依照某个成员的数据类型,可以按照相应数据类型的操作规范进行访问,换句话说,可以将一个结构体变量中的成员当成普通变量来使用 。 访问一个结构体变量的成员的形式如下：
<结构体变量名 >.<成员名 >
其中,,,”称为成员运算符,它的优先级高于所有的算术运算符,条件运算符和逻辑运算符 。
第 3章 数 组例如,对由结构体类型 Commodity定义的变量 goods1、
goods2,可以进行以下操作：
Commodity goods1={210003,"Computer",6600,3,
19800},goods2;
//定义结构体变量 goods1,goods2,同时对
goods1进行初始化
int TotalAmount; //定义一普通变量
goods2.No=110011;
strcpy(goods2.name,"Television"); //用字符串复制函数 strcpy给 goods2的 name成员赋值,
第 3章 数 组
//注意不能用赋值语句,goods2.name="Televsion";”给
//goods2的 name成员赋值
goods2.price=8000;
goods2.number=2;
goods2.amount=goods2.number*goods2.price;
TotalAmount=goods1.amount+goods2.amount;
如果一个结构体中包含另一个结构体作为成员,则访问该成员中的成员时,要使用如下形式：
<结构体变量名 >.<结构体成员名 >.<成员名 >
第 3章 数 组例如,我们仍以商品销售记录为例,对其结构体类型增加一个销售日期成员 Buydate(结构体类型 )：
struct Buydate
{
int year;
int month;
int day;
};
struct Commodity
{
unsigned long No;
char name[20]：
第 3章 数 组
float price;
int number;
double amount;
Buydate date; //此时的成员名是 date,是一结构体类型 (Buydate)
}goods1;
则要访问结构体变量 goods1中的二级成员 year,month、
day,须用形式：
goods1.date.year; goods1.date.month; goods1.date.day;
第 3章 数 组另外,在此要特别说明的是,结构体变量本身不代表一个特定的值,所以对结构体变量进行各种运算
(算术运算,比较运算,逻辑运算等 )均无实际意义 。 但结构体变量可以作为函数参数,同类型结构体变量之间也可以赋值,其赋值规则是,按成员依次赋值 。
例如,goods1 和 goods2 是 由 同 一 结 构 体 类 型
Commodity定义的,所以可以相互赋值：
goods2=goodsl; //合法表示将 goodsl的每个成员的值赋给 goods2的对应成员,使这两个结构体变量所有成员的值完全相同 。
第 3章 数 组
5,结构体数组多个同一类型的结构体变量也可以用数组的形式来处理,即结构体数组 。
结构体数组在内存中的存放格式类似于普通数组,
仍然是按元素顺序排列,只不过每个元素占用的字节数一般比普通数组要多 。 下面我们举例来说明其应用 。
第 3章 数 组
【 例 3-12】 有 6个学生,每个学生的数据包括学号,
姓名,三门课的成绩,设计程序实现：
(1) 计算出每个学生的平均成绩 。
(2) 将学生数据按平均成绩从高到低排序 。
程序代码如下：
#include <iostream.h>
struct student //定义结构体类型
{
int no;
第 3章 数 组
char name[15];
int c[3];
float aver;
};
#define N 6
void output(student a[N]) //输出学生数据函数
{
cout<<"\n 学 生 数 据 表 \n\n";
cout<<"学号 姓 名 成绩 1 成绩 2 成绩 3 平均成绩 \n";
cout.precision(4); //设定小数部分第 3章 数 组
for(int i=0;i<N;i++)
{
cout<<a[i].no;
cout.width(16); //设定输出宽度
cout<<a[i].name;
cout.width(8);
cout<<a[i].c[0]<<" "<<a[i].c[1]<<" "<<a[i].c[2];
cout<<" "<<a[i].aver<<endl;
}
}
第 3章 数 组
void main( )
{
int i,j,k;
student cs[N]={{1001,"Gao na",98,88,76},{1002,"Wang
jianjun",95,90,88},
{1003,"Liou
yao",76,78,84},{1004,"Ma ailian",56,60,72},
{1005,"Li
ming",96,93,90},{1006,"Cheng jiantao",86,79,90}};
student temp;
for(i=0;i<N;i++)
第 3章 数 组
cs[i].aver=float(cs[i].c[0]+cs[i].c[1]+cs[i].c[2])/3;
for(i=0;i<N-1;i++)
{
k=i;
for(j=i+1;j<N;j++)
if(cs[k].aver<cs[j].aver) k=j;
{temp=cs[i];cs[i]=cs[k];cs[k]=temp;} //用结构体变量直接进行交换
}
output(cs);
}
第 3章 数 组程序运行结果为学 生 数 据 表学号 姓 名 成绩 1 成绩 2 成绩 3 平均成绩
1005 Li ming 96 93 90 93
1002 Wang jianjun 95 90 88 91
1001 Gao na 98 88 76 87.33
1006 Cheng jiantao 86 79 90 85
1003 Liou yao 76 78 84 79.33
1004 Ma ailian 56 60 72 62.67
第 3章 数 组
3.7.2 共用体
C++语言中允许同一段内存空间存储不同类型的数据,主要用于节省内存空间与进行数据共享 。 在需要用同一段内存空间保存不同类型数据时,就必须使用共用体类型 。 共用体类型在定义上和使用上同结构体很相似,不同之处在于结构体中的成员所占用的空间是分开的,而共用体中的成员所占用的空间是共享的,即对其中一个成员的赋值,将影响到其它所有成员的值 。
第 3章 数 组同样,在使用共用体类型前,必须先定义一个共用体类型,其方法同定义结构体也很相似：
union [共用体名 ]
{
<类型标识符 > 成员名 1；
<类型标识符 > 成员名 2；
<类型标识符 > 成员名 n；
}[变量 1,变量 2,…,变量 k];
第 3章 数 组例如：
union UnionDate
{
int nIntData;
char cCharData;
float fRealData;
};
声明共用体变量的形式如下：
<共用体类型名 > 变量名注意,共用体变量不允许赋初始值 。
第 3章 数 组同结构体一样,共用体变量本身不代表任何值,
共用体变量的成员才保存实际的数据 。 对共用体变量中成员的访问方法同结构体变量一样,形式如下：
<共用体变量名 >.<成员名 >
由于共用体中的成员共享存储空间，所以在任何一个时刻，共用体变量中的成员只有一个是有效的。
例如，由共用体类型 UnionDate定义共用体变量
MyUnion：
第 3章 数 组
union UnionDate
{
int nIntData;
char cCharData;
float fRealData;
} MyUnion;
如果对 nIntData成员赋值：
MyUnion.nIntData=65535;
第 3章 数 组则会影响 MyUnion 的 另 两 个 成 员 cCharData,
fRealData的值,即 cCharData成员 (只占 1个字节 ) 与
nIntData成员的前 1个字节相同,fRealData成员 (占 32个字节 )的前 4个字节与 nIntData成员的 4个字节相同 。
第 3章 数 组
3.7.3 枚举类型枚举类型也是一种构造类型,是一种允许用符号代表数据的 C++语言的数据类型 。 它是一系列有标识名的整型常量的集合,其主要功能是增加程序代码的可读性 。 枚举类型的定义形式如下：
enum <枚举类型名 >{<枚举常量表 >}[枚举变量 ]
其中,enum是关键字 。 枚举常量表中的枚举常量名之间用逗号分隔,例如：
enum Days {Sun,Mon,Tue,Wed,Thu,Fri，
Sat} today;
第 3章 数 组说明,Days是自己定义的 1个枚举类型名,它有 7
个枚举常量 (又称枚举值,枚举元素 )。 缺省时,系统为每一个枚举常量都对应 1个整数,并从 0开始,逐个增 1。 也就是说,枚举常量 Sun等于 0,Mon等于 1，
Tue等于 2,等等 。 这些缺省的值也可重新指定,例如：
enum Colors{Black,Blue,Green=4,Cyan,Red=8，
Yellow,White};
则各枚举常量对应的整数依次为 0,1,4,5,8、
9,10。
第 3章 数 组上述定义中,today是在定义枚举类型 Days时被定义的变量,也可以用下列形式来定义：
enum Days today；
或
Days today; //省略 enum关键字枚举变量的取值只能等于该枚举类型中的某个枚举常量,而不能用一个整型数据或其它类型数据直接赋值 。 例如：
today=Mon; //合法,值为 1
int i=today; //合法,值为 1
today=3; //不合法,不能直接赋值第 3章 数 组需要注意的是,不要在定义枚举类型的同时,再对枚举常量,枚举变量及枚举类型名重新定义 。 例如,
下列的定义是不合法的：
int today;
int Sun;
第 3章 数 组
3.7.4 类型自定义语句用户使用 typedef语句可以将一个标识符定义为数据类型标识符,即可以将一个已有的类型名用一个新的类型名 (别名 )来代替 。 typedef语句的形式如下：
typedef <已有的类型名 > <类型别名 >
例如：
tvpedef float FLOAT;
typedef char CH10[10];
第 3章 数 组
typedef语句只是对已有的数据类型定义新的类型标识符,几乎可以对所有的数据类型定义别名,但却不能像 struct,union,enum等一样用来构造新的数据类型,当然也不能用来定义变量 。 下面再举两个示例以帮助理解：
typedef unsigned long ULONG;
ULONG uLint; //等价于,unsigned
long uLint;”
第 3章 数 组
typedef struct MySynopsis
{
char name[10];
int age;
float salary;
}MYNOTES;
MYNOTES ms; //等价于,struct MySynopsis ms;”
3.1 数组的基本概念
3.2 一维数组
3.3 多维数组
3.4 数组作为函数的参数
3.5 数组与字符串
3.6 数组应用举例
3.7 构造数据类型第 3章 数 组
3.1 数组的基本概念数组是一种构造数据类型,是具有统一名称和相同类型的一组数据元素的集合,它占用连续内存单元进行存储 。 要引用数组中的特定位置或元素,就要指定数组中的特定位置或元素的位置号 (position number)。
第 3章 数 组图 3-1显示了整型数组 c的数组元素存储分配 。 这个数组包含 7个元素 。 可以用数组名加上方括号 ([ ])中该元素的位置号来引用该元素 。 数组中的第一个元素称为第 0个元素 。 这样,c数组中的第一个元素为 c[0],c
数组中的第二个元素为 c[1],…,c数组中的第七个元素为 c[6]。 一般来说,c数组中的第 i个元素为 c[i-1]。
第 3章 数 组图 3-1 整型数组 c的数组元素存储分配示意第 3章 数 组方括号中的位置号通常称为下标 (subscript)。 下标应为整数或整型表达式 。
注意：带下标的数组名一般称为下标变量,可用于赋值语句的左边 。 例如：
c[3]=72;
第 3章 数 组
3.2 一 维 数 组
3.2.1 一维数组的声明数组在使用前必须先声明 。 声明一个一维数组的形式如下：
<类型标识符 > <数组名 >[数组长度 ]其中：
① 数组名必须遵循 C++语言对标识符的要求,其命名规则与其它变量名的相同 。
② 数组长度是个常量表达式,它规定了数组的大小,
即所声明的数组由多少个数据类型相同的存储空间组成 。
第 3章 数 组组成数组的对象称为该数组的元素 。 数组元素可存储的数据类型由声明时指定的 C++语言数据类型决定 。
数组的声明为以后使用数组分配了存储空间,数组中每个元素在内存中是依次排列的 。 例如,int Score[50]；定义了名称为 Score的一维数组,该数组有 50个元素,是
int类型的 。
在声明数组时,要注意数组的长度只能由常量表达式来决定,不能是变量 。 即,数组的长度必须是确定的 。
例如：
int nMonth;
float fSales[nMonth *12];
是错误的。这个声明在编译时编译器会给出错误信息。
第 3章 数 组
3.2.2 一维数组中的元素访问数组中的每个元素可以当成普通的变量使用 。 访问一维数组元素的形式如下：
<数组名 >[下标 ]
下标就是元素索引值，它代表了要被访问的数组元素在内存中的相对位置。下标值的允许范围从 0开始到数组长度 -1。下标等于 0代表要访问的元素在数组的第 1个位置上，下标等于 1代表要访问的元素在数组的第 2个位置上，依次类推。
第 3章 数 组例如,声明一个长度为 20的整型数组,并将数组中的各个元素按顺序赋予从 50到 70以 1递增的数,即赋予数组的第 0个元素的值为 50,赋予数组的第 1个元素的值为 51,依此类推 。 写出相应的程序段 。
注意，必须有一个值从 0开始，以 1为增量，递增到 19的变量作为访问数组时的下标，这样才能访问到数组中所有的元素。
第 3章 数 组用一个简单的 for循环就可以做到这一点,而循环控制变量就是最好的下标值 。 要按顺序给数组元素赋予从 50到 70的值,也就是让每个数组元素的值等于其下标值加上 50,所以只要将循环控制变量加上 50赋予相应的数组元素即可 。
程序段代码如下：
int nData[20];
for(int nIndex=0;nIndex<20;nIndex++)
nData[nIndex]=nIndex+50;
第 3章 数 组
【 例 3-1】 生成一个长度为 10的连续偶数序列,该偶数序列从 2开始 。 要求将此序列保存在数组中,并输出此数组的每个元素的值 。
分析：显然,先要声明一个长度为 10的数组 。 模仿上面的做法,可以用一个循环来解决对所有数组元素的访问,关键在于生成数列 。 偶数列是个很简单的数列,如果从 0开始,则规律为：第 i个数等于 i*2(i=0，
1,2,…)；如果从 2开始,则规律为：第 i个数等于
i*2+2(i=0,1,2,…)。
第 3章 数 组程序代码如下：
#include <iostream.h>
void main( )
{
int nEven[10]; //定义用于存放 10个偶数的数组
int nIndex;
for(nIndex=0;nIndex<10;nIndex++)
nEven[nIndex]=nIndex *2+2;
for(nIndex=0;nIndex<10;nIndex++)
{
第 3章 数 组
cout<<nEven[nIndex]<<" ";
}
cout<<endl;
}
程序运行结果为
2 4 6 8 10 12 14 16 18 20
第 3章 数 组
3.2.3 一维数组的初始化变量可以在声明时赋初值,数组也可以在声明时给所有或部分数组元素赋初始值 。 要给一维数组元素赋初始值,有如下两种形式 。
形式 1：
<类型标识符 > <数组名 >[数组长度 ]={第 0个元素值,第 1个元素值,…,第 n-1个元素值 }
形式 2：
<类型标识符 > <数组名 >[ ]={第 0个元素值,第 1个元素值,…,第 n个元素值 }
第 3章 数 组第一种形式将声明一个长度为,数组长度,的值的数组,然后将花括号内的值依次赋予数组的各个元素 。 花括号内只能是常量表达式 。 如果花括号中的常量表达式的个数小于数组长度,则剩余的数组元素就不被赋予初始值；如果花括号中的常量表达式的个数大于数组长度,则编译器会给出错误信息 。
第二种形式将声明一个长度为 n的数组,并将花括号内的 n个值依次赋给数组的各个元素 。
第 3章 数 组
【 例 3-2】 一个班级有 20名学生,所有学生的英语考试成绩保存在一个一维数组中 。 编写程序,求出该班学生的英语考试平均成绩,并统计考试成绩在 90分以上
(包括 90分 )的学生人数和不及格的学生人数 。
分析：为了统计平均成绩,需要有个变量保存所有学生的成绩总和 。 求总和的方法就是在对每个数组元素访问时,将其值累加到这个变量中,然后由此变量除以学生人数即得平均成绩 。 要统计考试成绩 90分以上的学生人数和不及格的学生人数,
第 3章 数 组需要分别设置两个变量 。 在对每个数组元素进行访问时,如果元素值大于等于 90,就将保存考试成绩在 90
分以上的学生人数的变量值加 1；如果元素值小于 60，
就将保存考试成绩不及格的学生人数的变量值加 1。 程序代码如下：
第 3章 数 组
#include <iostream.h>
void main( )
{
int
nScore[20]={90,88,45,92,76,59,89,93,60,51,91,65,82,74,92,
35,66,78,62,91};
//用数组初始化的方法将成绩存于数组 nScore
中
int nUnPassedCount=0; //定义记录不及格人数的变量
int nHighScoreCount=0; //定义记录 90分以上人数的变量
int nSum=0; //定义求和的变量第 3章 数 组
for(int ni=0;ni<20;ni++)
{
nSum+=nScore[ni];
if(nScore[ni]<60)
nUnPassedCount++;
if(nScore[ni]>=90)
nHighScoreCount++;
}
cout<<"平均分数为,"<<(float)nSum/20<<endl;
//将总和除以 20就是平均成绩 。 注意这里为了得到精确的结果,
第 3章 数 组
//使用了强制类型转换将 nSum从 int型转换成 float型
cout<<"90分以上人数为,"<<nHighScoreCount<<endl;
cout<<" 不及格人数为,"<<nUnPassedCount<<endl;
}
程序运行结果为平均分数,73.95
90分以上人数为,6
不及格人数为,4
第 3章 数 组
3.3 多维数组
3.3.1 多维数组的声明声明一个多维数组的形式如下：
<类型标识符 > <数组名 >[长度 1][长度 2]…[长度 n]
同一维数组相同,多维数组的数组名必须遵循 C++
语言标识符的命名规则,常量表达式中不能有任何变量出现 。 为了更直观地介绍多维数组,下面以二维数组为例 。
第 3章 数 组声明一个二维数组的形式如下：
<类型标识符 > <数组名 >[第 1维长度 ][第 2维长度 ]
例如,语句 float fMatrix[3][4]将声明一个数组名为
fMatix且第 1维长度为 3,第 2维长度为 4的二维数组 。 在二维数组中,第 1维常常称为行,第 2维常常称为列 。
这样,一个二维数组就可同一个二维表格对应起来,
如表 3-1所示 。
第 3章 数 组表 3-1 二维数组与表格列行 0 1 2 3
0 fMatrix[0][0] fMatrix[0][1] fMatrix[0][2] fMatrix[0][3]
1 fMatrix[1][0] fMatrix[1][1] fMatrix[1][2] fMatrix[1][3]
2 fMatrix[2][0] fMatrix[2][1] fMatrix[2][2] fMatrix[2][3]
第 3章 数 组可以这样理解二维数组：如果只给出二维数组的第 1维下标,以一维数组来看二维数组,则这样的数组中每个元素所代表的是另一个一维数组 。 例如,
fMatrix[0]代表由 4个 f1oat类型的元素组成的另一个一维数组 （ 数组名为 fMatrix[0],元素为 fMatrix[0][0],
fMatrix[0][1],fMatrix[0][2],fMatrix[0][3]） 。 不难算出,fMatrix中共有 3*4=12个 fIoat型元素 。 这 12个元素在内存中其实也是按顺序存放的：先存放 fMatrix[0]的 4
个元素,紧接着存放 fMatrix[1]的 4个元素,最后存放
fMatrix[2]的 4个元素 。
第 3章 数 组
3.3.2 访问多维数组中的元素要访问多维数组中的元素,同样需要指定要访问的元素的下标 。 多维数组的元素有多个下标,其书写形式如下：
<数组名 >[第 1维下标 ][第 2维下标 ] … [第 n维下标 ]
下标的值也是从 0开始,不能超过该维的长度减 1。
下标的值可以是任意表达式的值,只要其值在该下标的有效范围内即可 。
第 3章 数 组要访问二维数组中的某个元素,必须给出该元素所在的行和列 。 例如,fMatrix[2][1] 代表数组名为
fMatrix的二维数组中位于第 2(从 0开始 )行,第 1(从 0开始 )列的元素 。 同一维数组一样,二维数组的元素也可以当成变量进行赋值或参与各种表达式的计算 。
第 3章 数 组
3.3.3 二维数组的初始化同一维数组一样,二维数组也可以在声明时赋初始值,其形式如下 。 形式 1：
<类型标识符 > <数组名 >[第 1维长度 ][第 2维长度 ]={第 0
个第 2维数据组 }，
{第 1个第 2维数据组 },…,{第 n-1个第 2维数据组 }}
其中,n等于第 1维长度 。
第 3章 数 组形式 2：
<类型标识符 > <数组名 >[第 1维长度 ][第 2维长度 ]={第 0个元素值,
第 1个元素值,…,第 m个元素值 }
其中,m小于或等于第 1维长度乘以第 2维长度 。
在两种形式中,如果花括号中给出的元素个数少于实际的元素个数,则剩余的元素就不会被赋予初始值；如果花括号中给出的元素个数大于实际的元素个数,则编译器会给出错误信息 。
第 3章 数 组
【 例 3-3】 生成如下格式的方阵,将其存入二维数组中,并输出这个二维数组所有元素的值 。
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
第 3章 数 组分析：注意到这个方阵的规律在于,偶数行中的元素按升序排列,奇数行中的元素按降序排列,只要逐行处理方阵中的元素,即可得到这种方阵 。 为了访问二维数组中的所有元素,应使用二重嵌套循环 。 外层循环的循环控制变量作为当前行,内层循环的循环控制变量作为当前列 。 在显示这个二维数组时,为了得到理想的显示效果,要对不同的元素指定不同的显示位置 。
第 3章 数 组程序代码如下：
#include <iostream.h>
void main( )
{
int nRow; //控制行的变量
int nCol; //控制列的变量
int nMatrix[5][5]; //声明二维数组
for(nRow=0;nRow<5;nRow++)
第 3章 数 组
{
for(nCol=0;nCol<5;nCol++)
{
if(nRow%2==0)
nMatrix[nRow][nCol]=nRow*5+nCol+1;
else
nMatrix[nRow][4-nCol]=nRow*5+nCol+1;
}
}
for(nRow=0;nRow<5;nRow++)
{
第 3章 数 组
for(nCol=0;nCol<5;nCol++)
{
cout<<nMatrix[nRow][nCol];
if(nMatrix[nRow][nCol]<10) //控制输出 1位数与 2位数时的不同间隔
cout<<" ";
else
cout<<" ";
}
cout<<endl; //每输出一行后换行
}
}
第 3章 数 组程序运行结果为
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
第 3章 数 组
3.4 数组作为函数的参数在 C++语言中,将整个数组作为参数传递给函数要涉及到指针的概念 。 有关内容将在本书的第 6章进一步讨论,这里只结合数组参数的传递过程做简单介绍 。
要将数组作为参数传递给函数,可由不带方括号的数组名进行 。
第 3章 数 组例如,如果数组声明如下：
int nMatrix[20];
则将数组传递给函数,可用下列函数调用语句：
myArray(nMatrix,20);
要传递数组,大体上有以下两种形式 。
形式 1：
<类型标识符 > <函数名 >(类型标识符 数组名 [ ],int长度 )
形式 2：
<类型标识符 > <函数名 >(类型标识符 数组名 [长度 ])
第 3章 数 组第一种形式适于处理不同长度的数组,数组的实际长度通过另一个参数传递给函数；而第二种形式只可用于传递长度固定的数组 。 不管哪一种形式,传递给函数的都不是数组本身,而是保存数组第 0个元素的内存单元的地址 (即存储数组的起始地址 )。 通过传递数组的开始地址,被调用函数可得到实际数组的准确存放位置 。 因此,被调用函数在函数体中修改数组元素时,实际上是修改原内存地址中的数组元素 。
第 3章 数 组数组名的值实际上就是保存数组中第 1个元素的内存地址的变量,这样的变量称为指针型变量 。 当进行数组传递时,实际参数将此地址值传递给形式参数,
使形式参数同实际参数指向同一内存地址 。 这样在函数中如果改变数组中某个元素的值,在函数外数组中该元素的值也发生改变 。
第 3章 数 组尽管函数调用按地址传递整个数组,但各个数组元素和简单变量一样是按值传递 。 这种简单的单个数据称为下标变量或标量 (scalar)。 要将数组元素传递给函数,可用数组元素的下标名作为函数调用中的参数 。
数组元素、数组名与作为函数形式参数的数组名的这种关系可用图 3-2来表示。
第 3章 数 组第 3章 数 组鉴于上述原因,必须考虑在函数体内对作为形式参数传递而来的数组的操作 。 如果函数体内所有对作为形式参数传递而来的数组的操作只有读操作没有写操作,则不会有任何问题 。 但如果要改变数组元素的值,就必须考虑函数的调用者是否允许函数改变数组元素的值 。 如果不允许,在函数内部必须将数组复制,
所有的更改操作只能对复制品进行 。
【 例 3-4】 某次歌唱比赛有 5名选手参加,有 6名评委分别为选手打分,得分如表 3-2。
第 3章 数 组表 3-2 歌唱比赛记分表评委号选手号 1 2 3 4 5 6
1 9.31 9.20 9.00 9.40 9.35 9.20
2 9.71 9.52 9.50 9.66 9.49 9.57
3 8.89 8.80 9.10 9.25 8.90 9.00
4 9.38 9.50 9.40 9.20 9.90 8.90
5 9.30 8.84 9.40 9.45 9.10 8.89
第 3章 数 组规定的积分规则是：每位选手去掉一个最高分,再去掉一个最低分,然后取剩下的得分的平均分 。 编写程序计算各选手的成绩,并在窗口输出选手号和成绩 。
分析：由于二维数组同二维表格有对应关系，可以用一个二维数组保存所有评委给所有选手评出的成绩。
这样，数组下标的第 1维 (行 )代表的就是选手号 —— i，
第 2维 (列 )代表的是评委号 —— j。
第 3章 数 组在找数组各行元素最大值,最小值的同时还应对数组元素求和,这样,访问完一位选手的所有得分后,
就可以得到该选手得分的总和,最高分和最低分 。 将得分总和减去最高分,最低分,然后再除以 4,就得到选手的最后得分 。
程序代码如下：
#include <iostream.h>
double Context(double pArry[],int nNum)//评分函数
{
第 3章 数 组
int nInum;
double fMark,fMax,fMin; //定义记录成绩,最高分,最低分的变量
fMark=fMax=fMin=pArry[0];
for(nInum=0;nInum<nNum;nInum++)
{
if(pArry[nInum]>fMax)
fMax=pArry[nInum];
if(pArry[nInum]<fMin)
fMin=pArry[nInum];
第 3章 数 组
fMark+=pArry[nInum];
//fMark先记录着所有评委的总分
}
return (fMark-fMax-fMin)/4;
//计算出平均分并返回调用函数
}
void main( )
{
double pfSoreData[5][6]
{
第 3章 数 组
{
{9.31,9.20,9.00,9.40,9.35,9.20},
{9.71,9.52,9.50,9.66,9.49,9.57},
{8.89,8.80,9.10,9.25,8.90,9.00},
{9.38,9.50,9.40,9.20,9.90,8.90},
{9.30,8.84,9.40,9.45,9.10,8.89}
};
int nRow;
cout.precision(3); //设置小数点后的位数
for(nRow=0;nRow<5;nRow++)
第 3章 数 组
{
cout<<nRow+1<<" 号选手成绩为,";
cout<<Context(pfSoreData[nRow],5)<<endl;
}
}
程序运行结果为
1号选手成绩,9.29
2号选手成绩,9.6
3号选手成绩,8.95
4号选手成绩,9.41
5号选手成绩,9.28
第 3章 数 组注意，本例中调用函数形式为
Context(pfSoreData[nRow],5)，将二维数组的第 1维数组名作为实际参数传递给了形式参数。由此，可进一步理解二维数组是若干个一维数组所组成的概念。
第 3章 数 组
3.5 数组与字符串本书的第 1章中介绍过字符型常量与变量，也介绍过字符串常量，但却对字符串变量只字未提。其实，
在 C++语言中没有字符串变量类型。为了表示字符串，
要用到字符数组，对字符串的处理是通过字符数组的每一个元素保存字符串内的每一个字符来进行处理。
而在 Visual C++中，是由其 MFC类库中提供的功能完善的字符串类 CString来完成字符串的各种功能。
第 3章 数 组
3.5.1 字符数组字符型数组就是数组元素的类型是字符型的数组,
简称为字符数组 。 例如,char CBuffer[256];,unsigned
char pDBufrer[5][80]; 都是字符型数组 。 字符型数组的定义和声明同普通数组没有什么区别,主要的不同之处在于字符数组元素的初始化与使用方法 。
字符型数组也可以用通常数组初始化的形式对其元素进行初始化，只不过由于字符型数组中的元素是字符类型，一般用字符型常量给字符型数组赋初值，
例如：
第 3章 数 组
char myChars[ ]={'T','h','i','s',' ','a',' ','c'，
'o','m','p','u','t','e','r'};
除此以外,字符型数组常用两种特殊的初始化方法,
形式如下：
形式 1：
char <数组名 >[ ]="字符串 "
形式 2：
char <数组名 >[ ]={"字符串 "}
这两种形式产生的效果是相同的，它们会产生一个以字符串常量中的每个字符为数组元素且在末尾加个
,\0”的特殊数组。例如：
第 3章 数 组
char pMyStrinq[ ]="This is a computer";
执行后,pMyString数组中的元素依次是：
'T','h','i','s',' ','a','','c','o','m','p','u','t','e'，
'r ','\0'
它等同于
char pMyString[ ]={'T','h','i','s',' ','a',' ','c','o'，
'm','p','u','t','e','r ','\0'};
或
char pMyStrinq[ ]={"This is a computer"};
第 3章 数 组说明：
① 转义字符,\0”表示的是字符串常量中字符串的结束标志,在末尾保存了 0的字符型数组,也可以当成字符串来使用 。 在程序中,凡是可以使用字符串常量的地方,可以使用字符型数组来代替 。
② 字符型数组也是数组,只不过赋初值的方法有点特殊,但不能用赋值的方法进行赋初值 。 例如：
char pMyStrinq[ ];
pMyStrinq[ ]="This is a computer";
是错误的 。
第 3章 数 组
③ 变量可以重复赋值,即变量表示的值在程序运行的过程中可以通过赋值语句改变,但是字符型数组只能改变其元素的值,不能有,数组名 ="字符串 ";”这样的赋值语句出现 。
④ 数组的长度在声明时就已经确定 （ 字符串中字符个数 +1）,在使用的过程中不能更改 。 虽然在程序的运行过程中可以通过改变数组元素的值来改变一个字符型数组所存储的字符串内容,但如果要增加所存的字符串的长度,用静态数组是办不到的 。
第 3章 数 组
3.5.2 字符串的基本运算
C++语言中没有字符串型变量,要实现字符串的运算,例如,连接两个字符串,求字符串长度等,需要另外编写程序对字符型数组进行操作 。 在 C++语言的库函数中提供了各种字符串运算的函数,可以直接调用 。 我们在此给出其中的求字符串长度,字符串复制和字符串连接三种运算的具体实现方法 。 理解这些运算,有助于提高对字符串和字符数组的认识与理解 。
第 3章 数 组
1,求字符串的长度
C++语言的标准字符串以 '\0'结尾,所以求一个字符串的长度,要从字符串的第一个字符算起,直到碰到 '\0'为止 。
假设字符串保存在数组 pString中,求字符串长度的程序段如下：
char pString[ ]="字符串 ";
int nSize=0;
while(pString[nSize]!= '\0')
nSize++;
执行完毕后,整型变量 nSize中保存的值就是字符串
pString的长度 。
第 3章 数 组
2,字符串的复制字符串的复制就是将一个字符型数组 （ 源字符串 ）
的内容照原样复制到另一个字符型数组中 。 方法是：把源字符型数组中的字符依次赋给目的字符型数组,直到碰到 '\0'为止 。
假设源字符串保存在数组 pSource中,目的字符型数组为 pDestination,则字符串复制的程序段如下：
char pSource[ ]="字符串 ";
char pDestination[ ]=[N]; //N≥源字符串长度 +1
int nIndex=0;
第 3章 数 组
while(pSource[nSize]!= '\0')
{
pDestination[nIdex]=pSource[nIdex];
nIndex++;
}
pDestination[nIdex]= '\0'; //标识字符串结束最后的 while循环语句还可简化写为
while(pDestination[nIdex]=pSource[nIndex++]);
第 3章 数 组
3,字符串的连接字符串的连接就是将一个字符串连接到另一个字符串的末尾 。 在进行字符串的连接时,先要找到要被连接的字符串的尾部,然后从尾部的位置开始将另一个字符串复制过来 。
必须注意的是,存储原字符串的数组要有足够的空间来容纳连接进来的另一个字符串,否则在运行时可能产生保护模式错误 。
假设原字符串保存在字符数组 pDest中,要连接进来的字符串存在字符数组 pTocat中,则进行字符串连接的程序段如下：
第 3章 数 组
char pTocat[ ]="要连接进来的字符串 ";
char pDest[N]="现字符串 "; //N≥现字符串长度 +要连接进来的字符串长度 +1
int nSize=0;
int nIndex=0;
while (pDest[nSize]!=0) //找到要被连接的字符串的尾部
nSize++;
do
{
第 3章 数 组
pDest[nSize++]=pTocat[nIdex];
nIdex++;
} while(pTocat[nIdex]!= '\0');
pDest[nSize]= '\0';
第 3章 数 组
3.6 数组应用举例
3.6.1 排序数组元素排序是与数组有关的最重要的算法 。 所谓数组元素排序,是指将数组中的所有元素的位置重新排列,使得数组元素的值按照递增或递减有序排列 。
例如,已知一个一维数组中的元素按顺序是 1,7,3、
22,9,5,以递增排序后,这个数组中元素的排列就变成了 1,3,5,7,9,22。 排序有很多方法,本节介绍常用的选择排序法和冒泡排序法 。
第 3章 数 组
【 例 3-5】 选择排序法例题 。
选择排序法是很朴素的排序方法,它的思想很简单：先找到数组中最大的元素,将这个元素放到数组的最前端；然后在剩下的数组元素中再找出最大的元素,把它放在剩下的这些元素的最前端 。 如此下来,
就能使数组中的元素以递减顺序排列了 。 选择排序法的函数代码如下,
第 3章 数 组
#include <iostream.h>
void main( )
{
int a[6]={1,7,3,22,9,5};
int i,j,t,p;
for(i=0;i<6;i++)
{
p=i;
for(j=i+1;j<6;j++)
第 3章 数 组
if(a[p]>a[j]) p=j; //找本次最小元素的下标
t=a[i];
a[i]=a[p];
a[p]=t;
}
cout<<"排序后的数组为,\n";
for(i=0;i<6;i++)
cout<<" "<<a[i]<<"\n";
}
程序运行结果为第 3章 数 组排序后的数组如下：
1
3
5
7
9
22
第 3章 数 组
【 例 3-6】 冒泡排序法例题 。
冒泡排序法是交换排序法的一种，其基本思路是：
两两比较待排序的序列中的相邻元素，如果不满足顺序要求，就交换这两个元素。这样，第 1轮比较完毕后，
数组中的最大 (或最小 )元素就像气泡一样“冒”到数组的最尾部。可以认为由这个元素组成的只有一个元素的子序列是已经排好序的。然后对剩下的元素继续上述过程，直到全部元素有序。
第 3章 数 组冒泡排序法的函数代码如下：
#include <iostream.h>
void main( )
{
int a[6]={1,7,3,22,9,5};
int i,j,t,flag;
for(i=0;i<6;i++)
{
flag=0;
第 3章 数 组
for(j=0;j<6-i-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
flag=1;
}
if(flag==0) break;
}
cout<<"排序后的数组为,\n";
第 3章 数 组
for(i=0;i<6;i++)
cout<<" "<<a[i]<<"\n";
}
程序运行结果与例 3-5的相同 。
第 3章 数 组
3.6.2 查找数组元素查找是与数组有关的另一种重要算法 。
有时候需要知道一个元素在数组中的位置,即要通过元素值找到其下标值,这就需要用到查找算法 。
本节介绍两种基本的查找方法：顺序查找法和二分查找法 。 顺序查找法的思路很朴素,也容易实现,
但效率不高；二分查找法的效率很高,但要求数组在查找前已经排好序 。 这两种方法各有所长,可根据实际情况灵活选用 。
第 3章 数 组
【 例 3-7】 顺序查找法例题 。
顺序查找法的思路很简单：按顺序逐个访问数组元素,并将其同要找的值比较,直到找到与要查找的值相同的元素 。
顺序查找法的函数代码如下：
#include <iostream.h>
void npFind(int DataArray[ ],int nSize,int fValue)
//其中参数 DataArray[ ]为查找数组,nSize为数组长度,
fValue为要查找的值第 3章 数 组
{
int nIndex,flag=nSize; //设置 flag为查找标记
for(nIndex=0;nIndex<nSize;nIndex++)
if(DataArray[nIndex]==fValue)
{
flag=nIndex;
break; //退出循环
}
if(flag<nSize)
cout<<"元素找到了 ！ 是第 "<<flag+1<<" 个 "<<endl;
第 3章 数 组
else
cout<<"在数组中没有要找的元素 ！ "<<endl;
}
第 3章 数 组
【 例 3-8】 二分查找法例题 。
在数组中的元素已经排好序的前提下,使用二分查找法可以极大地提高查找效率 。 二分查找法的思路是这样的：首先假设数组已经按增序排好序 。 取位于数组中间的元素同要查找的值比较,如果待查值等于这个元素的值,则查找结束 。 如果待查值小于这个元素的值,则要查找的元素肯定在数组的左半边,将数组左半边看成完整的数组,继续使用二分查找法查找 。
如果待查值大于这个元素的值,则要查找的元素肯定在数组的右半边,将数组右半边看成完整的数组,继续使用二分查找法查找 。
第 3章 数 组二分查找法的函数代码如下：
#include <iostream.h>
void efFind(int DataArray[ ],int nSize,int fValue)
{
int flag=0; //设置 flag为查找标记
int nStart=0; //开始元素下标
int nEnd=nSize-1; //结尾元素下标
int nMid; //二分法中间元素下标第 3章 数 组
while(nStart<=nEnd)
{
nMid=(nStart+nEnd)/2; //计算中间元素下标
if(DataArray[nMid]==fValue)
{
flag=1; //标记查找成功
break; //退出循环
}
/*如果待查找的值大于中间元素的值,取后半边继续查找；
否则,取前半边继续查找 */
第 3章 数 组
if(fValue>DataArray[nMid])
nStart=nMid+1;
else
nEnd=nMid-1;
}
if(flag)
cout<<" 元素找到了 ！ 是第 "<<nMid+1<<" 个
"<<endl;
else
cout<<"在数组中没有要找的元素 ！ "<<endl;
}
第 3章 数 组
3.6.3 统计统计也是与数组有关的另一种常用算法 。 当需要知道一个元素在数组中出现的次数时,就要用到统计的算法 。
本节通过两个例子介绍两种基本的统计方法：一种是顺序查找统计法，另一种是借用数组下标值的统计方法。实际上，统计方法很多，可根据具体情况灵活运用。
第 3章 数 组
【 例 3-9】 顺序查找统计例题 。
顺序查找统计,顾名思义就是按顺序逐个访问数组元素,每找到一个要统计的元素就给计数器变量加 1。
顺序查找的程序代码如下：
#include <iostream.h>
void tjData(int DataArray[],int nSize,int tjValue) //顺序查找统计函数
{
int nIndex,tjSum=0;
第 3章 数 组
for(nIndex=0;nIndex<nSize;nIndex++)
if(DataArray[nIndex]==tjValue)
tjSum++;
if(tjSum)
cout<<"元素 "<<tjValue<<" 共有 "<<tjSum<<" 个
"<<endl;
else
cout<<"没有元素 "<<tjValue<<endl;
}
#define N 10
void main( )
第 3章 数 组
{
int a[N]={1,7,3,7,9,3,12,7,15,9};
int toFind;
cout<<"请输入欲统计的元素值,";
cin>>toFind;
tjData(a,N,toFind); //调用统计函数
}
程序运行结果为请输入欲统计的元素值,7
元素 7共有 3个第 3章 数 组
【 例 3-10】 借用数组下标值进行统计例题 。
此方法是一种技巧性算法,主要借用统计元素的一些特性 (比如整除某数后的商均相等或其值就等于数组下标等 )来进行 。 例如,输入若干整数,其值均在
1～ 4的范围内,请编写程序用于统计每个整数出现的次数 。
程序代码如下：
#include <iostream.h>
void main( )
{
第 3章 数 组
int tj[4]={0,0,0,0}; //存放统计结果
int tjData;
cout<<"请输入数据 1～ 4,输入其它时结束,"<<endl;
cin>>tjData;
while(tjData>0&&tjData<5) //限定数据范围的循环
{
tj[tjData-1]++; //注意数组 tj的下标 [tjData-
1]作用
cin>>tjData;
};
cout<<"统计结果为,"<<endl;
第 3章 数 组
for(int i=0;i<4;i++)
cout<<" "<<i+1<<","<<tj[i]<<endl;
}
程序运行结果为请输入数据 1～ 4,输入其它时结束：
1 2 3 4 1 2 6
统计结果：
1∶ 2
2∶ 2
3∶ 1
4∶ 1
第 3章 数 组
3.6.4 字符处理字符处理是 C++语言的特色功能之一,在计算机水平与等级考试中经常遇到 。 关于字符处理的方法很多,
但最主要的还是掌握字符数组下标的灵活运用 。 由于篇幅有限,这里我们仅举一例给以示范 。
第 3章 数 组
【 例 3-11】 在给定的由英文单词组成的字符串中,
找出其中都包含的最长的单词 (同一字母的大小写视为不同字符 )。 约定单词全由英文字母组成,单词之间由一个或多个空白符分隔 。
分析：自左至右顺序扫视字符串,逐个找出单词
(单词开始位置和单词长度 )。 当该单词的长度比已找到的单词更长时,记录该单词的开始位置和长度 。 继续此过程直至字符串扫视结束,最后输出找到的单词 。
第 3章 数 组程序代码如下：
#include <iostream.h>
void main( )
{
char s[ ]="This is C programming test.";
int i=0,pLen=0,maxLen=0,pSeat=0,maxlen=0;
while(s[i]!='\0')
{
while(s[i]!=' '&&s[i]!='\0') //区分单词并计算长度第 3章 数 组
{
pLen++;
i++;
}
if(pLen>maxLen) //记录最长单词的位置与长度
{
pSeat=i-pLen;
maxLen=pLen;
}
while(s[i]==' ') i++; //跳过单词之间的空格
pLen=0; //为计算下一个单词长度赋初值
}
第 3章 数 组
cout<<"最长的单词为,";
for(i=0;i<maxLen;i++) //逐个输出找到的最长单词
cout<<s[pSeat+i];
cout<<endl;
}
程序运行结果为最长的单词是 programming
第 3章 数 组
3.7 构造数据类型
3.7.1 结构体我们已经知道,数组是若干相同类型的数据元素组成的有序集合,但是在处理实际问题时,经常会遇到由相互关联但类型不同的数据组成的数据结构,比如要描述某一商品的一笔销售情况,就要包括商品号,
商品名,单价,数量,金额和销售日期等数据,它们的数据类型各不相同,但属于同一个整体,这样的数据结构在 C++中称为结构体 。
第 3章 数 组
1,结构体类型的定义以前我们介绍的基本类型变量和数组，其数据类型是由 C++本身定义好的，所以，可以直接用这些类型来声明基本变量和数组，但结构体则不同，它是由多种数据成分组成的复杂的数据类型，是随具体问题的数据结构而变化的。
第 3章 数 组例如,要描述商品信息 (商品号,商品名,单价,
数量,金额和销售日期等 ),就要建立商品类型的结构,
要描述学生信息 (如学号,姓名,性别,年龄,入学时间,年级,专业等 ),就要建立学生类型的结构,它们内部的数据组成截然不同 。 因此,C++无法事先建立好一个能描述一切事物的统一的结构体类型,而只能提供一个建立结构体类型的规则 。
第 3章 数 组因此,要定义描述某一问题的数据结构变量,程序员首先应从实际问题要描述的对象出发,自己建立一个结构体类型 (称为结构体类型的定义 ),然后再由这个已定义的结构体类型去定义相应的变量 。
定义一个结构体类型的一般形式如下：
struct <结构体类型名 >
{
<类型标识符 > 成员名 l;
<类型标识符 > 成员名 2;
<类型标识符 > 成员名 n;
};
第 3章 数 组例如,对商品销售记录可定义如下结构体类型：
struct Commodity
{
unsigned long No; //商品号
char name[20]; //商品名
float price; //单价
int number; //销售数量
double amount; //销售金额
};
第 3章 数 组说明：
① 定义结构体类型时,使用关键字 struct。 结构体类型名的命名应符合 C++语言的标识符命名规则 。
② 结构体中的数据成分被称为成员 。 成员可以是基本数据类型,也可以是另一个诸如结构体这样的复杂数据类型 。
③ 大括号内是一个成员表,成员名可以与程序中的变量名相同,但不能与结构体类型名相同,每个成员的末尾以及大括号后边都要加分号 。
第 3章 数 组
④ 若同一个结构体类型要被多个源文件使用,则经常将这些结构体类型的定义集中存放在一个头文件中,源文件中只要用 #include命令包含此头文件即可,
不必在每个源文件中重复同样的结构体类型定义 。 这部分内容将在第 5章详细介绍 。
这里要强调的是,定义一个结构体类型只是向
C++系统通报该结构体类型的名称和各成员的组成,
C++对结构体类型并不分配内存,只有在定义结构体变量时,C++才为结构体变量分配内存 。
第 3章 数 组
2,结构体变量的声明结构体是一种数据类型,同基本数据类型一样,
可以声明变量,作为函数的参数等 。
定义了结构体后,就可以用定义过的结构体类型声明结构体变量了 。 声明结构体变量一般有两种形式,
分别是：
<结构体类型名 > 变量名和
struct <结构体类型名 > 变量名第二种形式是 C语言留下来的,在 C++中不常用 。
第 3章 数 组声明的结构体变量将按照结构体中的各个成员按顺序在内存中分配空间 。 例如,用上面的 Commodity结构体声明一个变量：
Commodity MyComputer;
则 MyComputer将在内存中占用 120个字节,其中
No(商品号 )占 32个,name(商品名 )占 20个,price(单价 )
占 32个,number(销售数量 )占 4个,amount(销售金额 )
占 32个 。
另外,声明结构体变量也可在定义结构体类型的同时进行,其形式如下：
第 3章 数 组
struct [结构体类型名 ]
{
<类型标识符 > 成员名 l;
<类型标识符 > 成员名 2;
<类型标识符 > 成员名 n;
} [变量 1,变量 2,…,变量 n];
例如：
struct Commodity
{
第 3章 数 组
unsigned long No;
char name[20];
float price;
int number;
double amount;
}goods1,goods2;
这里既定义了结构体类型 Commodity,又定义了结构体变量 goods1,goods2,形式比较紧凑 。 如果以后需要再定义新的结构体变量 goods3,goods4,可以直接用语句 Commodity goods3,goods4;进行声明 。
第 3章 数 组
3,结构体变量的初始化所谓结构体变量的初始化,就是在定义结构体变量的同时,对它的每个成员赋初值,其语法形式与数组赋初值非常相似：
<结构体类型 > 变量名 ={表达式 1,表达式 2,…，
表达式 n}
其中,n个表达式分别对应于结构体中的 n个成员。
第 3章 数 组例如：
Commodity goods1={210003,"Computer",6600，
3,19800};
注意：
① 表达式各类型要与结构体成员的类型对应一致 。
② 只可对结构体变量在定义时进行初始化,不可对结构体类型初始化 。 例如：
struct Commodity
{
unsigned long No=210003;
char name[20]= "Computer"：
第 3章 数 组
float price=6600;
int number=3;
double amount=19800;
};
是错误的 。
第 3章 数 组
4,结构体变量的引用一个结构体变量应该以其成员为单位进行访问 。
依照某个成员的数据类型,可以按照相应数据类型的操作规范进行访问,换句话说,可以将一个结构体变量中的成员当成普通变量来使用 。 访问一个结构体变量的成员的形式如下：
<结构体变量名 >.<成员名 >
其中,,,”称为成员运算符,它的优先级高于所有的算术运算符,条件运算符和逻辑运算符 。
第 3章 数 组例如,对由结构体类型 Commodity定义的变量 goods1、
goods2,可以进行以下操作：
Commodity goods1={210003,"Computer",6600,3,
19800},goods2;
//定义结构体变量 goods1,goods2,同时对
goods1进行初始化
int TotalAmount; //定义一普通变量
goods2.No=110011;
strcpy(goods2.name,"Television"); //用字符串复制函数 strcpy给 goods2的 name成员赋值,
第 3章 数 组
//注意不能用赋值语句,goods2.name="Televsion";”给
//goods2的 name成员赋值
goods2.price=8000;
goods2.number=2;
goods2.amount=goods2.number*goods2.price;
TotalAmount=goods1.amount+goods2.amount;
如果一个结构体中包含另一个结构体作为成员,则访问该成员中的成员时,要使用如下形式：
<结构体变量名 >.<结构体成员名 >.<成员名 >
第 3章 数 组例如,我们仍以商品销售记录为例,对其结构体类型增加一个销售日期成员 Buydate(结构体类型 )：
struct Buydate
{
int year;
int month;
int day;
};
struct Commodity
{
unsigned long No;
char name[20]：
第 3章 数 组
float price;
int number;
double amount;
Buydate date; //此时的成员名是 date,是一结构体类型 (Buydate)
}goods1;
则要访问结构体变量 goods1中的二级成员 year,month、
day,须用形式：
goods1.date.year; goods1.date.month; goods1.date.day;
第 3章 数 组另外,在此要特别说明的是,结构体变量本身不代表一个特定的值,所以对结构体变量进行各种运算
(算术运算,比较运算,逻辑运算等 )均无实际意义 。 但结构体变量可以作为函数参数,同类型结构体变量之间也可以赋值,其赋值规则是,按成员依次赋值 。
例如,goods1 和 goods2 是 由 同 一 结 构 体 类 型
Commodity定义的,所以可以相互赋值：
goods2=goodsl; //合法表示将 goodsl的每个成员的值赋给 goods2的对应成员,使这两个结构体变量所有成员的值完全相同 。
第 3章 数 组
5,结构体数组多个同一类型的结构体变量也可以用数组的形式来处理,即结构体数组 。
结构体数组在内存中的存放格式类似于普通数组,
仍然是按元素顺序排列,只不过每个元素占用的字节数一般比普通数组要多 。 下面我们举例来说明其应用 。
第 3章 数 组
【 例 3-12】 有 6个学生,每个学生的数据包括学号,
姓名,三门课的成绩,设计程序实现：
(1) 计算出每个学生的平均成绩 。
(2) 将学生数据按平均成绩从高到低排序 。
程序代码如下：
#include <iostream.h>
struct student //定义结构体类型
{
int no;
第 3章 数 组
char name[15];
int c[3];
float aver;
};
#define N 6
void output(student a[N]) //输出学生数据函数
{
cout<<"\n 学 生 数 据 表 \n\n";
cout<<"学号 姓 名 成绩 1 成绩 2 成绩 3 平均成绩 \n";
cout.precision(4); //设定小数部分第 3章 数 组
for(int i=0;i<N;i++)
{
cout<<a[i].no;
cout.width(16); //设定输出宽度
cout<<a[i].name;
cout.width(8);
cout<<a[i].c[0]<<" "<<a[i].c[1]<<" "<<a[i].c[2];
cout<<" "<<a[i].aver<<endl;
}
}
第 3章 数 组
void main( )
{
int i,j,k;
student cs[N]={{1001,"Gao na",98,88,76},{1002,"Wang
jianjun",95,90,88},
{1003,"Liou
yao",76,78,84},{1004,"Ma ailian",56,60,72},
{1005,"Li
ming",96,93,90},{1006,"Cheng jiantao",86,79,90}};
student temp;
for(i=0;i<N;i++)
第 3章 数 组
cs[i].aver=float(cs[i].c[0]+cs[i].c[1]+cs[i].c[2])/3;
for(i=0;i<N-1;i++)
{
k=i;
for(j=i+1;j<N;j++)
if(cs[k].aver<cs[j].aver) k=j;
{temp=cs[i];cs[i]=cs[k];cs[k]=temp;} //用结构体变量直接进行交换
}
output(cs);
}
第 3章 数 组程序运行结果为学 生 数 据 表学号 姓 名 成绩 1 成绩 2 成绩 3 平均成绩
1005 Li ming 96 93 90 93
1002 Wang jianjun 95 90 88 91
1001 Gao na 98 88 76 87.33
1006 Cheng jiantao 86 79 90 85
1003 Liou yao 76 78 84 79.33
1004 Ma ailian 56 60 72 62.67
第 3章 数 组
3.7.2 共用体
C++语言中允许同一段内存空间存储不同类型的数据,主要用于节省内存空间与进行数据共享 。 在需要用同一段内存空间保存不同类型数据时,就必须使用共用体类型 。 共用体类型在定义上和使用上同结构体很相似,不同之处在于结构体中的成员所占用的空间是分开的,而共用体中的成员所占用的空间是共享的,即对其中一个成员的赋值,将影响到其它所有成员的值 。
第 3章 数 组同样,在使用共用体类型前,必须先定义一个共用体类型,其方法同定义结构体也很相似：
union [共用体名 ]
{
<类型标识符 > 成员名 1；
<类型标识符 > 成员名 2；
<类型标识符 > 成员名 n；
}[变量 1,变量 2,…,变量 k];
第 3章 数 组例如：
union UnionDate
{
int nIntData;
char cCharData;
float fRealData;
};
声明共用体变量的形式如下：
<共用体类型名 > 变量名注意,共用体变量不允许赋初始值 。
第 3章 数 组同结构体一样,共用体变量本身不代表任何值,
共用体变量的成员才保存实际的数据 。 对共用体变量中成员的访问方法同结构体变量一样,形式如下：
<共用体变量名 >.<成员名 >
由于共用体中的成员共享存储空间，所以在任何一个时刻，共用体变量中的成员只有一个是有效的。
例如，由共用体类型 UnionDate定义共用体变量
MyUnion：
第 3章 数 组
union UnionDate
{
int nIntData;
char cCharData;
float fRealData;
} MyUnion;
如果对 nIntData成员赋值：
MyUnion.nIntData=65535;
第 3章 数 组则会影响 MyUnion 的 另 两 个 成 员 cCharData,
fRealData的值,即 cCharData成员 (只占 1个字节 ) 与
nIntData成员的前 1个字节相同,fRealData成员 (占 32个字节 )的前 4个字节与 nIntData成员的 4个字节相同 。
第 3章 数 组
3.7.3 枚举类型枚举类型也是一种构造类型,是一种允许用符号代表数据的 C++语言的数据类型 。 它是一系列有标识名的整型常量的集合,其主要功能是增加程序代码的可读性 。 枚举类型的定义形式如下：
enum <枚举类型名 >{<枚举常量表 >}[枚举变量 ]
其中,enum是关键字 。 枚举常量表中的枚举常量名之间用逗号分隔,例如：
enum Days {Sun,Mon,Tue,Wed,Thu,Fri，
Sat} today;
第 3章 数 组说明,Days是自己定义的 1个枚举类型名,它有 7
个枚举常量 (又称枚举值,枚举元素 )。 缺省时,系统为每一个枚举常量都对应 1个整数,并从 0开始,逐个增 1。 也就是说,枚举常量 Sun等于 0,Mon等于 1，
Tue等于 2,等等 。 这些缺省的值也可重新指定,例如：
enum Colors{Black,Blue,Green=4,Cyan,Red=8，
Yellow,White};
则各枚举常量对应的整数依次为 0,1,4,5,8、
9,10。
第 3章 数 组上述定义中,today是在定义枚举类型 Days时被定义的变量,也可以用下列形式来定义：
enum Days today；
或
Days today; //省略 enum关键字枚举变量的取值只能等于该枚举类型中的某个枚举常量,而不能用一个整型数据或其它类型数据直接赋值 。 例如：
today=Mon; //合法,值为 1
int i=today; //合法,值为 1
today=3; //不合法,不能直接赋值第 3章 数 组需要注意的是,不要在定义枚举类型的同时,再对枚举常量,枚举变量及枚举类型名重新定义 。 例如,
下列的定义是不合法的：
int today;
int Sun;
第 3章 数 组
3.7.4 类型自定义语句用户使用 typedef语句可以将一个标识符定义为数据类型标识符,即可以将一个已有的类型名用一个新的类型名 (别名 )来代替 。 typedef语句的形式如下：
typedef <已有的类型名 > <类型别名 >
例如：
tvpedef float FLOAT;
typedef char CH10[10];
第 3章 数 组
typedef语句只是对已有的数据类型定义新的类型标识符,几乎可以对所有的数据类型定义别名,但却不能像 struct,union,enum等一样用来构造新的数据类型,当然也不能用来定义变量 。 下面再举两个示例以帮助理解：
typedef unsigned long ULONG;
ULONG uLint; //等价于,unsigned
long uLint;”
第 3章 数 组
typedef struct MySynopsis
{
char name[10];
int age;
float salary;
}MYNOTES;
MYNOTES ms; //等价于,struct MySynopsis ms;”
