C++课件：第3章 数组.ppt

1、第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的数组元素存储分配。这个数组

2、包含7个元素。可以用数组名加上方括号( )中该元素的位置号来引用该元素。数组中的第一个元素称为第0个元素。这样，c数组中的第一个元素为c0，c数组中的第二个元素为c1，c数组中的第七个元素为c6。一般来说，c数组中的第i个元素为ci-1。第3章 数 组图3-1 整型数组c的数组元素存储分配示意 第3章 数 组 方括号中的位置号通常称为下标(subscript)。下标应为整数或整型表达式。 注意：带下标的数组名一般称为下标变量，可用于赋值语句的左边。例如： c3=72;第3章 数 组3.2 一一 维维 数数 组组 3.2.1 一维数组的声明 数组在使用前必须先声明。声明一个一维数组的形式如下：

3、数组长度其中： 数组名必须遵循C+语言对标识符的要求，其命名规则与其它变量名的相同。 数组长度是个常量表达式，它规定了数组的大小，即所声明的数组由多少个数据类型相同的存储空间组成。第3章 数 组 组成数组的对象称为该数组的元素。数组元素可存储的数据类型由声明时指定的C+语言数据类型决定。数组的声明为以后使用数组分配了存储空间，数组中每个元素在内存中是依次排列的。例如，int Score50；定义了名称为Score的一维数组，该数组有50个元素，是int类型的。 在声明数组时，要注意数组的长度只能由常量表达式来决定，不能是变量。即，数组的长度必须是确定的。例如： int nMonth; floa

4、t fSalesnMonth *12;是错误的。这个声明在编译时编译器会给出错误信息。 第3章 数 组 3.2.2 一维数组中的元素访问 数组中的每个元素可以当成普通的变量使用。访问一维数组元素的形式如下： 下标 下标就是元素索引值，它代表了要被访问的数组元素在内存中的相对位置。下标值的允许范围从0开始到数组长度-1。下标等于0代表要访问的元素在数组的第1个位置上，下标等于1代表要访问的元素在数组的第2个位置上，依次类推。 第3章 数 组 例如，声明一个长度为20的整型数组，并将数组中的各个元素按顺序赋予从50到70以1递增的数，即赋予数组的第0个元素的值为50，赋予数组的第1个元素的值为51

5、，依此类推。写出相应的程序段。 注意，必须有一个值从0开始，以1为增量，递增到19的变量作为访问数组时的下标，这样才能访问到数组中所有的元素。 第3章 数 组 用一个简单的for循环就可以做到这一点，而循环控制变量就是最好的下标值。要按顺序给数组元素赋予从50到70的值，也就是让每个数组元素的值等于其下标值加上50，所以只要将循环控制变量加上50赋予相应的数组元素即可。 程序段代码如下： int nData20; for(int nIndex=0;nIndex20;nIndex+) nDatanIndex=nIndex+50;第3章 数 组 【例3-1】 生成一个长度为10的连续偶数序列，该偶

6、数序列从2开始。要求将此序列保存在数组中，并输出此数组的每个元素的值。 分析：显然，先要声明一个长度为10的数组。模仿上面的做法，可以用一个循环来解决对所有数组元素的访问，关键在于生成数列。偶数列是个很简单的数列，如果从0开始， 则规律为：第i个数等于i*2(i=0，1，2，)；如果从2开始，则规律为：第i个数等于i*2+2(i=0，1，2，)。第3章 数 组程序代码如下：#include void main( )int nEven10; /定义用于存放10个偶数的数组int nIndex;for(nIndex=0;nIndex10;nIndex+)nEvennIndex=nIndex *2+

7、2;for(nIndex=0;nIndex10;nIndex+)第3章 数 组coutnEvennIndex ;coutendl;程序运行结果为2 468101214161820第3章 数 组 3.2.3 一维数组的初始化 变量可以在声明时赋初值，数组也可以在声明时给所有或部分数组元素赋初始值。要给一维数组元素赋初始值，有如下两种形式。 形式1： 数组长度=第0个元素值，第1个元素值, , 第n-1个元素值 形式2： =第0个元素值，第1个元素值，第n个元素值第3章 数 组 第一种形式将声明一个长度为“数组长度”的值的数组，然后将花括号内的值依次赋予数组的各个元素。花括号内只能是常量表达式。如

8、果花括号中的常量表达式的个数小于数组长度，则剩余的数组元素就不被赋予初始值；如果花括号中的常量表达式的个数大于数组长度，则编译器会给出错误信息。 第二种形式将声明一个长度为n的数组，并将花括号内的n个值依次赋给数组的各个元素。 第3章 数 组 【例3-2】 一个班级有20名学生，所有学生的英语考试成绩保存在一个一维数组中。编写程序，求出该班学生的英语考试平均成绩，并统计考试成绩在90分以上(包括90分)的学生人数和不及格的学生人数。 分析：为了统计平均成绩，需要有个变量保存所有学生的成绩总和。求总和的方法就是在对每个数组元素访问时，将其值累加到这个变量中，然后由此变量除以学生人数即得平均成绩。

9、要统计考试成绩90分以上的学生人数和不及格的学生人数，第3章 数 组 需要分别设置两个变量。在对每个数组元素进行访问时，如果元素值大于等于90，就将保存考试成绩在90分以上的学生人数的变量值加1；如果元素值小于60，就将保存考试成绩不及格的学生人数的变量值加1。程序代码如下： 第3章 数 组#include void main( )int Score20=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

10、 nHighScoreCount=0; /定义记录90分以上人数的变量int nSum=0; /定义求和的变量第3章 数 组for(int ni=0;ni20;ni+)nSum+=nScoreni;if(nScoreni=90)nHighScoreCount+;cout平均分数为：(float)nSum/20endl;/将总和除以20就是平均成绩。注意这里为了得到精确的结果，第3章 数 组/使用了强制类型转换将nSum从int型转换成float型cout90分以上人数为：nHighScoreCountendl;cout 不及格人数为：nUnPassedCountendl;程序运行结果为平均分数

11、：73.9590分以上人数为：6不及格人数为：4第3章 数 组 3.3 多维数组多维数组 3.3.1 多维数组的声明 声明一个多维数组的形式如下： 长度1长度2长度n 同一维数组相同，多维数组的数组名必须遵循C+语言标识符的命名规则，常量表达式中不能有任何变量出现。为了更直观地介绍多维数组，下面以二维数组为例。第3章 数 组 声明一个二维数组的形式如下： 第1维长度第2维长度 例如，语句float fMatrix34将声明一个数组名为fMatix且第1维长度为3、第2维长度为4的二维数组。在二维数组中，第1维常常称为行，第2维常常称为列。这样，一个二维数组就可同一个二维表格对应起来，如表3-1

12、所示。第3章 数 组 表3-1 二维数组与表格 列行01230fMatrix00fMatrix01fMatrix02fMatrix031fMatrix10fMatrix11fMatrix12fMatrix132fMatrix20fMatrix21fMatrix22fMatrix23第3章 数 组 可以这样理解二维数组：如果只给出二维数组的第1维下标，以一维数组来看二维数组，则这样的数组中每个元素所代表的是另一个一维数组。例如，fMatrix0代表由4个f1oat类型的元素组成的另一个一维数组（数组名为fMatrix0，元素为fMatrix00、fMatrix01、fMatrix02、fMatr

13、ix03）。不难算出，fMatrix中共有3*4=12个fIoat型元素。这12个元素在内存中其实也是按顺序存放的：先存放fMatrix0的4个元素，紧接着存放fMatrix1的4个元素，最后存放fMatrix2的4个元素。第3章 数 组 3.3.2 访问多维数组中的元素 要访问多维数组中的元素，同样需要指定要访问的元素的下标。多维数组的元素有多个下标，其书写形式如下： 第1维下标第2维下标 第n维下标 下标的值也是从0开始，不能超过该维的长度减1。下标的值可以是任意表达式的值，只要其值在该下标的有效范围内即可。第3章 数 组 要访问二维数组中的某个元素，必须给出该元素所在的行和列。例如，fM

14、atrix21代表数组名为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维长度。 在两种形式中，如果花括号中给出的元素个数少于实际的元素

15、个数，则剩余的元素就不会被赋予初始值；如果花括号中给出的元素个数大于实际的元素个数，则编译器会给出错误信息。第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章 数 组 分析：注意到这个方阵的规律在于，偶数行中的元素按升序排列，奇数行中的元素按降序排列，只要逐行处理方阵中的元素，即可得到这种方阵。为了访问二维数组中的所有元素，应使用二重嵌套循环。外层循环的循环控制变量作为当前行，内层循环的循环控制变量作为当前

16、列。在显示这个二维数组时，为了得到理想的显示效果，要对不同的元素指定不同的显示位置。第3章 数 组程序代码如下：#include void main( )int nRow;/控制行的变量 int nCol;/控制列的变量 int nMatrix55;/声明二维数组for(nRow=0;nRow5;nRow+)第3章 数 组for(nCol=0;nCol5;nCol+)if(nRow%2=0)nMatrixnRownCol=nRow*5+nCol+1;elsenMatrixnRow4-nCol=nRow*5+nCol+1;for(nRow=0;nRow5;nRow+)第3章 数 组for(nCo

17、l=0;nCol5;nCol+)coutnMatrixnRownCol;if(nMatrixnRownCol10)/控制输出1位数与2位数时的不同间隔cout ;elsecout ;coutendl;/每输出一行后换行第3章 数 组程序运行结果为 1 2 34510 987611 1213141520 1918171621 22232425第3章 数 组3.4 数组作为函数的参数数组作为函数的参数 在C+语言中，将整个数组作为参数传递给函数要涉及到指针的概念。有关内容将在本书的第6章进一步讨论，这里只结合数组参数的传递过程做简单介绍。 要将数组作为参数传递给函数，可由不带方括号的数组名进行。第

18、3章 数 组例如，如果数组声明如下：int nMatrix20;则将数组传递给函数，可用下列函数调用语句：myArray(nMatrix，20);要传递数组，大体上有以下两种形式。形式1： (类型标识符 数组名 ，int长度)形式2： (类型标识符 数组名长度)第3章 数 组 第一种形式适于处理不同长度的数组，数组的实际长度通过另一个参数传递给函数；而第二种形式只可用于传递长度固定的数组。不管哪一种形式，传递给函数的都不是数组本身，而是保存数组第0个元素的内存单元的地址(即存储数组的起始地址)。通过传递数组的开始地址，被调用函数可得到实际数组的准确存放位置。因此，被调用函数在函数体中修改数组元

19、素时，实际上是修改原内存地址中的数组元素。第3章 数 组 数组名的值实际上就是保存数组中第1个元素的内存地址的变量，这样的变量称为指针型变量。当进行数组传递时，实际参数将此地址值传递给形式参数，使形式参数同实际参数指向同一内存地址。这样在函数中如果改变数组中某个元素的值，在函数外数组中该元素的值也发生改变。第3章 数 组 尽管函数调用按地址传递整个数组，但各个数组元素和简单变量一样是按值传递。这种简单的单个数据称为下标变量或标量(scalar)。要将数组元素传递给函数，可用数组元素的下标名作为函数调用中的参数。 数组元素、数组名与作为函数形式参数的数组名的这种关系可用图3-2来表示。 第3章

20、数 组第3章 数 组 鉴于上述原因，必须考虑在函数体内对作为形式参数传递而来的数组的操作。如果函数体内所有对作为形式参数传递而来的数组的操作只有读操作没有写操作，则不会有任何问题。但如果要改变数组元素的值，就必须考虑函数的调用者是否允许函数改变数组元素的值。如果不允许，在函数内部必须将数组复制，所有的更改操作只能对复制品进行。 【例3-4】 某次歌唱比赛有5名选手参加，有6名评委分别为选手打分，得分如表3-2。第3章 数 组 表3-2 歌唱比赛记分表评委号 选手号12345619.319.209.009.409.359.2029.719.529.509.669.499.5738.898.809

21、.109.258.909.0049.389.509.409.209.908.9059.308.849.409.459.108.89第3章 数 组 规定的积分规则是：每位选手去掉一个最高分，再去掉一个最低分，然后取剩下的得分的平均分。编写程序计算各选手的成绩，并在窗口输出选手号和成绩。 分析：由于二维数组同二维表格有对应关系，可以用一个二维数组保存所有评委给所有选手评出的成绩。这样，数组下标的第1维(行)代表的就是选手号i，第2维(列)代表的是评委号j。 第3章 数 组 在找数组各行元素最大值、最小值的同时还应对数组元素求和，这样，访问完一位选手的所有得分后，就可以得到该选手得分的总和、最高分和

22、最低分。将得分总和减去最高分、最低分，然后再除以4，就得到选手的最后得分。 程序代码如下： #include double Context(double pArry,int nNum)/评分函数 第3章 数 组int nInum;double fMark,fMax,fMin;/定义记录成绩、最高分、最低分的变量fMark=fMax=fMin=pArry0;for(nInum=0;nInumfMax)fMax=pArrynInum;if(pArrynInumfMin)fMin=pArrynInum;第3章 数 组fMark+=pArrynInum; /fMark先记录着所有评委的总分return

23、 (fMark-fMax-fMin)/4; /计算出平均分并返回调用函数void main( )double pfSoreData56 第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;nRow5;nRow+)第3章 数 组 coutnR

24、ow+1 号选手成绩为：;coutContext(pfSoreDatanRow,5)endl; 程序运行结果为 1号选手成绩：9.29 2号选手成绩：9.6 3号选手成绩：8.95 4号选手成绩：9.41 5号选手成绩：9.28第3章 数 组 注意，本例中调用函数形式为Context(pfSoreDatanRow，5)，将二维数组的第1维数组名作为实际参数传递给了形式参数。由此，可进一步理解二维数组是若干个一维数组所组成的概念。第3章 数 组3.5 数组与字符串数组与字符串 本书的第1章中介绍过字符型常量与变量，也介绍过字符串常量，但却对字符串变量只字未提。其实，在C+语言中没有字符串变量类型

25、。为了表示字符串，要用到字符数组，对字符串的处理是通过字符数组的每一个元素保存字符串内的每一个字符来进行处理。而在Visual C+中，是由其MFC类库中提供的功能完善的字符串类CString来完成字符串的各种功能。 第3章 数 组 3.5.1 字符数组 字符型数组就是数组元素的类型是字符型的数组，简称为字符数组。例如，char CBuffer256;、unsigned char pDBufrer580; 都是字符型数组。字符型数组的定义和声明同普通数组没有什么区别，主要的不同之处在于字符数组元素的初始化与使用方法。 字符型数组也可以用通常数组初始化的形式对其元素进行初始化，只不过由于字符型数

26、组中的元素是字符类型，一般用字符型常量给字符型数组赋初值，例如： 第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它等

27、同于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章 数 组 变量可以重复赋值，即

28、变量表示的值在程序运行的过程中可以通过赋值语句改变，但是字符型数组只能改变其元素的值，不能有“数组名=字符串;”这样的赋值语句出现。 数组的长度在声明时就已经确定（字符串中字符个数+1），在使用的过程中不能更改。虽然在程序的运行过程中可以通过改变数组元素的值来改变一个字符型数组所存储的字符串内容，但如果要增加所存的字符串的长度，用静态数组是办不到的。第3章 数 组 3.5.2 字符串的基本运算 C+语言中没有字符串型变量，要实现字符串的运算，例如，连接两个字符串，求字符串长度等，需要另外编写程序对字符型数组进行操作。在C+语言的库函数中提供了各种字符串运算的函数，可以直接调用。我们在此给出其中

29、的求字符串长度、字符串复制和字符串连接三种运算的具体实现方法。理解这些运算，有助于提高对字符串和字符数组的认识与理解。第3章 数 组 1求字符串的长度 C+语言的标准字符串以0结尾，所以求一个字符串的长度，要从字符串的第一个字符算起，直到碰到0为止。 假设字符串保存在数组pString中，求字符串长度的程序段如下： char pString =字符串; int nSize=0; while(pStringnSize!= 0) nSize+; 执行完毕后，整型变量nSize中保存的值就是字符串pString的长度。第3章 数 组 2字符串的复制 字符串的复制就是将一个字符型数组（源字符串）的内容

30、照原样复制到另一个字符型数组中。方法是：把源字符型数组中的字符依次赋给目的字符型数组，直到碰到0为止。 假设源字符串保存在数组pSource中，目的字符型数组为pDestination，则字符串复制的程序段如下： char pSource =字符串; char pDestination =N; /N源字符串长度+1 int nIndex=0;第3章 数 组while(pSourcenSize!= 0)pDestinationnIdex=pSourcenIdex;nIndex+;pDestinationnIdex= 0; /标识字符串结束最后的while循环语句还可简化写为while(pDest

31、inationnIdex=pSourcenIndex+);第3章 数 组 3. 字符串的连接 字符串的连接就是将一个字符串连接到另一个字符串的末尾。在进行字符串的连接时，先要找到要被连接的字符串的尾部，然后从尾部的位置开始将另一个字符串复制过来。 必须注意的是，存储原字符串的数组要有足够的空间来容纳连接进来的另一个字符串，否则在运行时可能产生保护模式错误。 假设原字符串保存在字符数组pDest中，要连接进来的字符串存在字符数组pTocat中，则进行字符串连接的程序段如下：第3章 数 组char pTocat =要连接进来的字符串;char pDestN=现字符串;/N现字符串长度+要连接进来的

32、字符串长度+1int nSize=0;int nIndex=0;while (pDestnSize!=0) /找到要被连接的字符串的尾部nSize+;do第3章 数 组 pDestnSize+=pTocatnIdex; nIdex+; while(pTocatnIdex!= 0);pDestnSize= 0;第3章 数 组3.6 数组应用举例数组应用举例 3.6.1 排序 数组元素排序是与数组有关的最重要的算法。所谓数组元素排序，是指将数组中的所有元素的位置重新排列，使得数组元素的值按照递增或递减有序排列。例如，已知一个一维数组中的元素按顺序是1、7、3、22、9、5，以递增排序后，这个数组中

33、元素的排列就变成了1、3、5、7、9、22。排序有很多方法，本节介绍常用的选择排序法和冒泡排序法。第3章 数 组 【例3-5】 选择排序法例题。 选择排序法是很朴素的排序方法，它的思想很简单：先找到数组中最大的元素，将这个元素放到数组的最前端；然后在剩下的数组元素中再找出最大的元素，把它放在剩下的这些元素的最前端。如此下来，就能使数组中的元素以递减顺序排列了。选择排序法的函数代码如下:第3章 数 组#include void main( )int a6=1,7,3,22,9,5;int i,j,t,p;for(i=0;i6;i+)p=i;for(j=i+1;jaj) p=j; /找本次最小元素

34、的下标t=ai;ai=ap;ap=t;cout排序后的数组为：n;for(i=0;i6;i+)cout ain;程序运行结果为第3章 数 组排序后的数组如下： 1 3 5 7 9 22第3章 数 组 【例3-6】 冒泡排序法例题。 冒泡排序法是交换排序法的一种，其基本思路是：两两比较待排序的序列中的相邻元素，如果不满足顺序要求，就交换这两个元素。这样，第1轮比较完毕后，数组中的最大(或最小)元素就像气泡一样“冒”到数组的最尾部。可以认为由这个元素组成的只有一个元素的子序列是已经排好序的。然后对剩下的元素继续上述过程，直到全部元素有序。 第3章 数 组冒泡排序法的函数代码如下：#include

35、void main( )int a6=1,7,3,22,9,5;int i,j,t,flag;for(i=0;i6;i+)flag=0;第3章 数 组for(j=0;jaj+1) t=aj;aj=aj+1;aj+1=t;flag=1;if(flag=0) break;cout排序后的数组为：n;第3章 数 组for(i=0;i6;i+)cout ain;程序运行结果与例3-5的相同。第3章 数 组 3.6.2 查找 数组元素查找是与数组有关的另一种重要算法。有时候需要知道一个元素在数组中的位置，即要通过元素值找到其下标值，这就需要用到查找算法。 本节介绍两种基本的查找方法：顺序查找法和二分查找

36、法。顺序查找法的思路很朴素，也容易实现，但效率不高；二分查找法的效率很高，但要求数组在查找前已经排好序。这两种方法各有所长，可根据实际情况灵活选用。 第3章 数 组 【例3-7】 顺序查找法例题。 顺序查找法的思路很简单：按顺序逐个访问数组元素，并将其同要找的值比较，直到找到与要查找的值相同的元素。 顺序查找法的函数代码如下： #include void npFind(int DataArray , int nSize,int fValue) /其中参数DataArray 为查找数组,nSize为数组长度, fValue为要查找的值第3章 数 组 int nIndex,flag=nSize;

37、/设置flag为查找标记for(nIndex=0;nIndexnSize;nIndex+)if(DataArraynIndex=fValue)flag=nIndex;break; /退出循环if(flagnSize)cout元素找到了！是第 flag+1 个endl;第3章 数 组elsecout在数组中没有要找的元素！endl;第3章 数 组 【例3-8】 二分查找法例题。 在数组中的元素已经排好序的前提下，使用二分查找法可以极大地提高查找效率。二分查找法的思路是这样的：首先假设数组已经按增序排好序。取位于数组中间的元素同要查找的值比较，如果待查值等于这个元素的值，则查找结束。如果待查值小于

38、这个元素的值，则要查找的元素肯定在数组的左半边，将数组左半边看成完整的数组，继续使用二分查找法查找。如果待查值大于这个元素的值，则要查找的元素肯定在数组的右半边，将数组右半边看成完整的数组，继续使用二分查找法查找。第3章 数 组 二分查找法的函数代码如下： #include void efFind(int DataArray ,int nSize,int fValue) int flag=0; /设置flag为查找标记int nStart=0; /开始元素下标int nEnd=nSize-1; /结尾元素下标int nMid; /二分法中间元素下标第3章 数 组while(nStartData

39、ArraynMid)nStart=nMid+1;elsenEnd=nMid-1;if(flag)cout元素找到了！是第 nMid+1 个endl;elsecout在数组中没有要找的元素！endl;第3章 数 组 3.6.3 统计 统计也是与数组有关的另一种常用算法。当需要知道一个元素在数组中出现的次数时，就要用到统计的算法。 本节通过两个例子介绍两种基本的统计方法：一种是顺序查找统计法，另一种是借用数组下标值的统计方法。实际上，统计方法很多，可根据具体情况灵活运用。 第3章 数 组 【例3-9】 顺序查找统计例题。 顺序查找统计，顾名思义就是按顺序逐个访问数组元素，每找到一个要统计的元素就给

40、计数器变量加1。 顺序查找的程序代码如下： #include void tjData(int DataArray,int nSize,int tjValue) /顺序查找统计函数 int nIndex,tjSum=0; 第3章 数 组for(nIndex=0;nIndexnSize;nIndex+)if(DataArraynIndex=tjValue)tjSum+;if(tjSum)cout元素 tjValue 共有 tjSum 个endl;elsecout没有元素 tjValueendl;#define N 10 void main( )第3章 数 组int aN=1,7,3,7,9,3,1

41、2,7,15,9;int toFind;couttoFind;tjData(a,N,toFind); /调用统计函数程序运行结果为请输入欲统计的元素值：7元素 7共有3个第3章 数 组 【例3-10】 借用数组下标值进行统计例题。 此方法是一种技巧性算法，主要借用统计元素的一些特性(比如整除某数后的商均相等或其值就等于数组下标等)来进行。例如，输入若干整数，其值均在14的范围内，请编写程序用于统计每个整数出现的次数。 程序代码如下： #include void main( ) 第3章 数 组 int tj4=0,0,0,0; /存放统计结果int tjData;cout请输入数据14，输入其它

42、时结束：tjData;while(tjData0&tjDatatjData;cout统计结果为：endl;第3章 数 组for(int i=0;i4;i+)cout i+1 ： tjiendl;程序运行结果为请输入数据14，输入其它时结束：1 2 3 4 1 2 6统计结果：1 22 23 14 1第3章 数 组 3.6.4 字符处理 字符处理是C+语言的特色功能之一，在计算机水平与等级考试中经常遇到。关于字符处理的方法很多，但最主要的还是掌握字符数组下标的灵活运用。由于篇幅有限，这里我们仅举一例给以示范。第3章 数 组 【例3-11】 在给定的由英文单词组成的字符串中，找出其中都包含的最长的

43、单词(同一字母的大小写视为不同字符)。约定单词全由英文字母组成，单词之间由一个或多个空白符分隔。 分析：自左至右顺序扫视字符串，逐个找出单词(单词开始位置和单词长度)。当该单词的长度比已找到的单词更长时，记录该单词的开始位置和长度。继续此过程直至字符串扫视结束，最后输出找到的单词。第3章 数 组程序代码如下：#include void main( )char s =This is C programming test.;int i=0,pLen=0,maxLen=0,pSeat=0,maxlen=0;while(si!=0)while(si!= &si!=0) /区分单词并计算长度第3章 数

44、组 pLen+;i+;if(pLenmaxLen) /记录最长单词的位置与长度pSeat=i-pLen;maxLen=pLen;while(si= ) i+; /跳过单词之间的空格pLen=0; /为计算下一个单词长度赋初值 第3章 数 组cout最长的单词为：;for(i=0;imaxLen;i+) /逐个输出找到的最长单词coutspSeat+i;coutendl;程序运行结果为最长的单词是programming第3章 数 组3.7 构造数据类型构造数据类型 3.7.1 结构体 我们已经知道，数组是若干相同类型的数据元素组成的有序集合，但是在处理实际问题时，经常会遇到由相互关联但类型不同的

45、数据组成的数据结构，比如要描述某一商品的一笔销售情况，就要包括商品号、商品名、单价、数量、金额和销售日期等数据，它们的数据类型各不相同，但属于同一个整体，这样的数据结构在C+中称为结构体。第3章 数 组 1结构体类型的定义 以前我们介绍的基本类型变量和数组，其数据类型是由C+本身定义好的，所以，可以直接用这些类型来声明基本变量和数组，但结构体则不同，它是由多种数据成分组成的复杂的数据类型，是随具体问题的数据结构而变化的。 第3章 数 组 例如，要描述商品信息(商品号、商品名、单价、数量、金额和销售日期等)，就要建立商品类型的结构，要描述学生信息(如学号、姓名、性别、年龄、入学时间、年级、专业等

46、)，就要建立学生类型的结构，它们内部的数据组成截然不同。因此，C+无法事先建立好一个能描述一切事物的统一的结构体类型，而只能提供一个建立结构体类型的规则。 第3章 数 组 因此，要定义描述某一问题的数据结构变量，程序员首先应从实际问题要描述的对象出发，自己建立一个结构体类型(称为结构体类型的定义)，然后再由这个已定义的结构体类型去定义相应的变量。 定义一个结构体类型的一般形式如下： struct 成员名l; 成员名2; 成员名n; ;第3章 数 组 例如，对商品销售记录可定义如下结构体类型：struct Commodityunsigned long No; /商品号char name20; /

47、商品名float price; /单价int number; /销售数量double amount; /销售金额;第3章 数 组 说明： 定义结构体类型时，使用关键字struct。结构体类型名的命名应符合C+语言的标识符命名规则。 结构体中的数据成分被称为成员。成员可以是基本数据类型，也可以是另一个诸如结构体这样的复杂数据类型。 大括号内是一个成员表，成员名可以与程序中的变量名相同，但不能与结构体类型名相同，每个成员的末尾以及大括号后边都要加分号。第3章 数 组 若同一个结构体类型要被多个源文件使用，则经常将这些结构体类型的定义集中存放在一个头文件中，源文件中只要用#include命令包含此头

48、文件即可，不必在每个源文件中重复同样的结构体类型定义。这部分内容将在第5章详细介绍。 这里要强调的是，定义一个结构体类型只是向C+系统通报该结构体类型的名称和各成员的组成，C+对结构体类型并不分配内存，只有在定义结构体变量时，C+才为结构体变量分配内存。第3章 数 组 2结构体变量的声明 结构体是一种数据类型，同基本数据类型一样，可以声明变量、作为函数的参数等。 定义了结构体后，就可以用定义过的结构体类型声明结构体变量了。声明结构体变量一般有两种形式，分别是： 变量名 和 struct 变量名 第二种形式是C语言留下来的，在C+中不常用。第3章 数 组 声明的结构体变量将按照结构体中的各个成员

49、按顺序在内存中分配空间。例如，用上面的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 name2

50、0; float price; int number; double amount; goods1，goods2; 这里既定义了结构体类型Commodity，又定义了结构体变量goods1、goods2，形式比较紧凑。如果以后需要再定义新的结构体变量goods3、goods4，可以直接用语句Commodity goods3，goods4;进行声明。第3章 数 组 3结构体变量的初始化 所谓结构体变量的初始化，就是在定义结构体变量的同时，对它的每个成员赋初值，其语法形式与数组赋初值非常相似： 变量名=表达式1，表达式2，表达式n 其中，n个表达式分别对应于结构体中的n个成员。 第3章 数 组 例