第4章 数组.ppt

1、C+语言程序设计,第4章 数 组,4.1 一维数组 4.2 二维数组 4.3 字符数组,数组是一个在内存中顺序排列的、由若干相同数据类型的元素组成的数据集合。其所有元素共用一个名字，即数组名。数组的每个元素都有唯一的下标，通过数组名和下标，可以访问数组中的元素，因此数组元素也称为下标变量。下标实际上就是数组元素在数组中的位置值，不能超出数组下标的取值范围。数组分一维数组和多维数组。 数组属于构造类型。,基 本 术 语,4.1 一 维 数 组,4.4.1 一维数组的定义 数组必须先声明，后使用。 一般声明形式为: 数据类型 数组名常量表达式； 例如：int a 10；,数据类型是数组的数据类型，

2、也就是每一个数组元素的类型，可以是C+中任何一种数据类型。(如int,char,float或double或构造类型) 数组名是标识符,遵循标识符的命名规则。除了作为数组的标识外，同时还代表该数组存储空间的首地址，也就是第一个数组元素的地址，因此，数组名本身还是一个地址量。,说 明：,一维数组在内存中所占用的 总字节数 = 数据类型长度数组长度 例如： int a10; /占用40个字节 double b10; /占用80个字节,数组中的所有数组元素是连续存储的。 例如：int a10； 如果该数组存放的首地址为2000H,常量表达式 表示该数组中的元素的个数，它规定了数组的大小，只能为正整数。

3、数组的下标范围为“0”到“常量表达式-1”，即最小下标为0，最大下标为“常量表达式-1”。 常量表达式中可以包含常量或符号常量，不能是变量，即在C+中不允许对数组进行动态定义。 一个声明语句可以同时声明多个类型相同的变量和数组，各变量和数组之间要用逗号分开。,说 明：,数组a10的10个数组元素分别为：a0、a1、a2、a3、a4、a5、a6、a7、a8、a9。 注意: 不存在a10数组元素。,int m; cinm; int am; /错误,非法,const int M=10; int aM; /正确,合法,例如：char a3,b4,x,y;,4.1.2 一维数组元素的引用,C+语言规定不

4、能一次引用整个数组，只能逐个引用数组中的某个数组元素。 对数组的使用实际上是对数组元素的使用。数组元素的引用格式(访问一维数组元素的形式)为：数组名下标 其中下标就是被访问的数组元素在所定义的数组中的相对位置。下标等于0代表要访问的数组元素在数组的第一个位置上，下标等于1代表要访问的数组元素在数组的第二个位置上，依此类推。,例如：int x，count10; 则下面引用是合法的 count0=100； x+=count5； 下面引用是不合法的： count10=20; /越界 count=20; /数组不能整体赋值,下标不要越界,特别强调：在运行C+语言程序过程中，系统并不自动检验数组元素的下

5、标是否越界。因此在编写程序时，保证数组下标不越界是十分重要的。,#include void main( ) int i,a10; for(i=0; i10; i+) ai=i*2+2; /通过一赋值表达式给各数组元素赋值 for(i=0;i10;i+) coutai“ ”; coutendl; ,程序运行结果如下： 2 4 6 8 10 12 14 16 18 20, 例4.1 数组元素的引用,在定义数组时对数组元素赋值，叫做数组的初始化。 用赋值表达式或输入函数也可以对数组元素进行赋值，但这种方法要占用运行时间。而对数组初始化使数组元素在程序运行之前即在编译时就得到初值（静态数组）。,4.1

6、.3 一维数组的初始化,一维数组的初始化其实现方法如下： 在定义数组时对数组的全部元素赋初值。如： int a10= 0,1,2,3,4,5,6,7,8,9 ； 可以只给前面部分数组元素赋初值，未赋值的数组元素系统自动赋初值0。如： int a10=0,1,2,3,4,5; /a6-a9的初值自动为0 实际上，对static数组不赋初值，系统会对所有数组元素自动赋以0值。如： static int a10； /a0-a9全部被赋初值0。 对全部数组元素赋初值时，可以不指定数组长度，系统会自动按初值的个数设定数组长度，为数组分配足够的存储空间。如： int a =1,2,3,4,5； /a数组的

7、长度为5,#include void main() int i ,math40,n; double aver=0.0; int unpassedcount=0; int highscorecount=0;, 例4.2 成绩统计,一个班级有若干名学生，试编写程序，求出该班学生的数学考试平均成绩，并统计考试成绩在90分以上的（包括90分）的学生人数和不及格的学生人数。 分析：对于同一门课程的n个学生成绩，可以用同一个名称但不同的下标来区别，因此用一维数组来表示和保存这些成绩。, 例4.2 成绩统计,coutn; coutmathi; aver+=mathi; aver/=n; for ( i=0;

8、 i=90 ) highscorecount +; cout平均分为：averendl; cout90分以上人数为：highscorecountendl; cout不及格人数为：unpassedcountendl; ,程序的运行结果为： please input the number of student :10 please iput score: 75 80 65 88 90 67 78 63 59 60 平均分为：72.5 90分以上人数为：1 不及格人数为：1, 例4.3 求最大数,1. 设计算法实现求最大数。 2. 修改程序，思考并增加如下功能： (1) 同时求出最小数和平均数； (

9、2) 不使用数组，能否解决问题，如何解决？,基本思路：将n个数据两两进行比较，较大的数向后移动，经过一轮比较后，将最大的数移动到末尾（沉底），而小的数“上浮” 。然后再对剩下的n-1个数进行两两比较，得到次大数。如此反复使大数向后移动、小数向前移动，最后得到一个有序的数组。就像水底的气泡一样逐渐向上冒，故得名。, 例4.4 冒泡法排序,下面以六个数 9、8、5、4、2、0 为例分析冒泡法排序算法。 第1趟比较（下图1） 第2趟比较（下图2）,第1趟比较后，剩5个数未排好序；两两比较5次 第2趟比较后，剩4个数未排好序；两两比较4次 第3趟比较后，剩3个数未排好序；两两比较3次 第4趟比较后，剩

10、2个数未排好序；两两比较2次 第5趟比较后，全部排好序；两两比较1次 算法结论： 对于 n个数的排序，需进行 n-1 趟比较， 第j 趟比较需进行 n-j 次两两比较。, 例4.4 冒泡法排序,程序流程图：（用两层嵌套循环实现）,设需排序的数有10个，可以定义数组大小为11，使用a1a10存放10个数，a0不用，以符合人们的习惯。,对于 n个数的排序，需进行 n-1 趟比较,第j 趟比较需进行 n-j 次两两比较。,这时的数组元素已是排好序的了。, 例4.4 冒泡法排序,程序流程图：（用两层嵌套循环实现）,#include #include void main() int a11, i, j,

11、 t; coutai; /输入数组元素 coutai+1) t=ai; ai=ai+1; ai+1=t; /排序 coutthe sorted numbers are : ; for(i=1;i11;i+) cout ai; /输出数组元素 coutendl; ,运行结果为： please input 10 numbers: 12 34 2 80 3 78 42 1 10 0 the numbers are: 12 34 2 80 3 78 42 1 10 0 the sorted numbers are: -3 0 1 2 10 12 34 42 78 80, 例 用数组来处理Fibonac

12、ci数列问题,#include #include using namespace std; void main() int i; int f40=1,1; for(i=2;i40;i+) fi=fi-2+fi-1; for(i=0;i40;i+) if(i%5=0) coutendl; cout fi; coutendl; ,思考1：与循环方法 相比思路上的差别？,循环中每次求出2个数立即输出，数组先求出全部40个数存入数组，最后一起输出。, 例 用数组来处理Fibonacci数列问题,#include #include using namespace std; void main() int

13、 i; int f40=1,1; for(i=2;i40;i+) fi=fi-2+fi-1; for(i=0;i40;i+) if(i%5=0) coutendl; cout fi; coutendl; ,思考2：求出前40个 数中有多少个是3位数？,for (i=0;i99 ,将一个数组的内容按颠倒的次序重新存放。 例如，数组元素原来的值依次为： 8、3、5、1、9、7、2 倒置后变为： 2、7、9、1、5、3、8, 思考题倒置排放,分析： 设a数组有n个元素，将a数组中的内容按颠倒的次序重新存放，只需将元素a0的内容与元素an-1的内容交换，将元素a1的内容与元素an-2的内容交换，将元素

14、ai的内容与元素an-i-1的内容交换即可。,思考：已知一个数组a10，判断其是否前后对称。,2.编写函数int CH(int M)，判断M是否为回文数。如果是回文数则返回1，否则返回0。, 思考题回文数,分析： M的位数不确定。 首先要分解M，提取M的每一位数字，并依次赋给一维数组int a10。 判断a数组是否对称。如对称，则表明M是回文数。 如1，11，121，12321等。,3.已知一个有十个元素的数组int a10，将其中值为偶数的元素调到数组前端，将值为奇数的元素调到数组后端。 要求：元素交换次数、比较次数尽量最少。, 课后思考题,设已有一按从小到大次序排序好的数组，现输入一数X，

15、要求按原来的排序规律，将X插入到数组中。, 思考题-插入元素,分析： 定位。确定插入位置i。 后移。将i后面的元素依次后移，空出插入位置。 再插入。将X插入i位置。,查找指定下标的元素； 查找指定值的元素； 多个元素值相同的情况。, 思考题-查找元素,删除指定下标的元素。 删除值为指定值X的元素。 删除多个具有相同值的元素。, 思考题-删除元素,筛法求素数 将十进制正整数M转化为任意T进制数。其中M、T由键盘输入。 将数组int a10中的元素循环右移N位。N由键盘输入。如果要求只有一个数组元素大小的附加空间要求只有一个数组元素大小的附加空间。, 练习题,用筛法求素数的基本思想是： 把从1开始

16、的、某一范围内的正整数从小到大顺序排列，1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。 如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30, 练习题筛法求素数,4.2 二 维 数 组,定义的一般形式为： 数据类型 数组名常量表达式1常量表达式2; 其中，常量表达式1表示数组的行数(第一维) ， 常量表达式2表示数组的列数(第二维) 。 例如： float a23,b510； / OK float a2,3,b5;10,b5

17、,10 ； /ERROR,4.2.1 二维数组的定义, C+语言对二维数组采用这样的定义方式:把二维数组看作是一种特殊的一维数组，它的每个元素又是一个一维数组。 二维数组中的数组元素按行优先的顺序存放在连续的存储空间，即在内存中先顺序存放第一行的元素,再存放第二行的元素,这样按照存储顺序存取元素时，第一维的下标变化最慢，最右边的下标变化最快。 二维数组中的每个数组元素都有两个下标，且必须分别放在单独的“ ”内。如：a3,4 ,说 明：,4.2.2 二维数组元素的引用,对多维数组的引用也是对数组各个元素的使用，而不是对数组名。二维数组元素的引用格式为： 数组名下标 下标 例如：a11、b32。

18、下标也可以是整型表达式，如 a2-12*2-3。 数组元素可以出现在表达式中，也可以被赋值。例如： a23=a11+a21。 注意：在使用数组元素时，数组下标值应在已定义的数组大小的范围内。与一维数组一样，注意不要出现下标越界的错误。,按行为二维数组赋初值。如： int a34=1,2,3,4,5,6,7,8,9,10,11,12； 按数组元素的存储顺序赋初值。如： int a34=1,2,3,4,5,6,7,8,9,10,11,12；,4.2.3 二维数组的初始化,给部分元素赋初值。 ).只对各行第一列元素赋初值，如： int a34=1,3,5; /其余元素值为0 ).对各行中的某一元素赋

19、初值。如： int a34=1,0,3,0,0,5; ).只对某几行的部分元素赋初值。如： int a34=1,3,5; /第三行不赋初值 int a34=1,0,3,5; /第二行不赋初值,1 0 0 0 3 0 0 0 5 0 0 0,1 0 0 0 0 3 0 0 0 0 5 0,1 0 0 0 3 5 0 0 0 0 0 0,1 0 0 0 0 0 0 0 3 5 0 0,4.2.3 二维数组的初始化,当对二维数组的全部元素或部分赋初值时，定义数组时第一维的长度可省略，但第二维的长度必须给出，系统会根据数据的总个数分配存储空间。如： int a34=1, 2, 3, 4, 5, 6,

20、7, 8, 9, 10, 11, 12； int a 4=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12； int a 4=1,2, 3, 4,5, 6, 7, 8,9, 10, 11, 12； int a 4=0,0, 4,0,0, 10；,例：以下不能正确定义二维数组的语句是 。 A) int a22=1,2; B) int a 2=1,2,3,4 ; C) int a22=1,2,3; D) int a2 =1,2,3,4;,假设：#define M 10 #define N 10 int arrMN; 创建二维数组 显示二维数组 求整个数组的和、均值 求数组

21、某行（P）/列（Q）的和、均值 求整个数组的最大/最小值（元素） 求数组某行/列的最大/最小值（元素）, 练习题, 例4.6 找出二维数组中的最大值及其位置,从键盘上为数组a23输入任意整数值，显示该数组，找出该数组的最大元素及其下标。,#include #include using namespace std; void main() int a23,i,j; for(i=0;iaij; for (i=0;i2;i+) for (j=0;j3;j+) cout aij; coutendl; int h,l,Max=a00; for (i=0;i2;i+) for (j=0;j3;j+) if

22、 (Maxaij) Max=aij;h=i;l=j; coutMax: ahl=ahlendl; ,运行结果： a00=1 a01=9 a02=2 a10=8 a11=5 a12=6 1 9 2 8 5 6 Max:a01=9, 例4.6 找出二维数组中的最大值及其位置,从键盘上为数组a23输入任意整数值，显示该数组，找出该数组的最大元素及其下标。,#include #include using namespace std; void main() long int a23, i, j; srand(100); for (i=0;i2;i+) for (j=0;j3;j+) aij=rand(

23、 ); for (i=0;i2;i+) for (j=0;j3;j+) coutsetw(8)leftaij; coutendl; int h,l,Max=a00; for (i=0;i2;i+) for (j=0;j3;j+) if (Maxaij) Max=aij;h=i;l=j; coutMax: ahl=ahlendl; ,介绍两个产生随机数的函数： rand( ) : 每次调用时均返回032767之间的一个整数。 srand( unsigned int ); 本函数为rand( )所生成的随机数设置起始点。,4.2.4 二维数组程序举例, 例4.5 二维数组的初始化与输出,生成如下格

24、式的方阵，将其存入二维数组中，并输出这个二维数组所有元素的值。,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,分析：这个方阵的规律是，偶数行中的元素按升序排列，奇数行中的元素按降序排列，只要逐行处理方阵中的元素，即可得到这种方阵。为了访问二维数组中的所有元素，应使用二重嵌套循环。外层循环变量控制行，内层循环变量控制列。,#include #include using namespace std; void main( ) int i, j; int a55; for(i=0;i5;i+) for(j=0;j5

25、;j+) if(i%2=0) aij=i*5+j+1; else ai4-j=i*5+j+1; for(i=0;i5;i+) for(j=0;j5;j+) cout aij; coutendl; ,二维数组的输入,二维数组的输出,所谓鞍点，是指在所在行上最大而在列上最小的元素。, 练习题鞍点,6是鞍点。,二维数组多用来处理矩阵问题，这是很重要的编程基础。课后自己找资料，编程： 将一个矩阵行和列的元素与换，存到另一个二维数组中，并分别输出前后两个矩阵。如： 两个矩阵相加后，生成一个新的矩阵。 (3) 两个矩阵的乘积。注意两个矩阵相加或相乘的条件。, 思考题,1. 矩阵转置 矩阵的转置就是把矩阵的

26、行和列互换，比如一个3*4的矩阵。 2. 有5个学生4门课的成绩： 找出成绩最高的学生序号和课程; 找出不及格课程的学生序号及其各门课的全部成绩; 求全部学生各门课程的平均分数; 求出总分前三名。 3. 用二维数组法打印杨辉三角形。 4. 一群小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。究竟胜利者是第几个小孩呢?,4.3 字符数组,用来存放字符数据的数组是字符数组，字符数组中的一个单元存放一个字符，字符数组也有一维及多维之分。字符数组中可以用来存放多个字符，也可以用来存放字符串。字符

27、数组中存放的是字符还是字符串，其区别在于数组元素中是否有字符串结束标志（0）。,一般形式为： char 数组名 常量表达式 ； 例如：char c10; /占用存储空间为10个字节,4.3.1 字符数组的定义,4.3.2 字符数组的初始化,用字符赋初值：如:char a13=I, B, M; 说明： 如果花括弧中提供的初值个数(即字符个数)大于数组长度，则在编译时，系统会提示为语法错误。如果初值个数小于数组长度，则只将这些字符赋给数组中前面那些元素，其余元素由系统自动定为空字符（即0）。如： char c10=C, h, i, n, a 如果提供的初值个数与定义的数组长度相同，则在定义数组时可

28、以省略数组长度说明，系统会自动根据初值个数确定数组长度。如 char c =a,b,c,d,e,f,g,h,i,j；,4.3.2 字符数组的初始化,(2) 用字符串赋初值： char c = “happen”；或 char c = “happen”； 说明： 在C和C+语言中，没有字符串数据类型，因此常常将字符串作为字符数组来处理。转义字符 0 表示的是字符串常量中字符串的结束标志，在末尾保存了0 的字符型数组，也可以当成字符串来使用。也就是说，在遇到字符 0 时，表示字符串结束，由它前面的字符组成字符串。系统对字符串常量也自动加一个0 作为结束符。例如： Program共有7个字符，但在内存

29、中占8个字节，最后一个字节 0 是由系统自动加上的。,在程序中往往依靠检测0 的位置来判定字符串是否结束，而不是根据数组的长度来决定字符串长度。当然，在定义字符数组时应估计实际字符串长度，保证数组长度始终大于字符串实际长度。如果在一个字符数组中先后存放多个不同长度的字符串，则应使数组长度大于最长的字符串的长度。,例.设有数组定义：char array=“china”; ，则数组所占的空间为 。 A)4个字节 B)5个字节 C)6个字节 D)7个字节,4.3.2 字符数组的初始化,(2) 用字符串赋初值： char c = “happen”；或 char c = “happen”； 说明： 在定

30、义数组长度时，应在字符串应有的最大长度的基础上加1，为字符串结束标志预留空间。例如定义一个有10个字符的字符串，应定义字符数组长度为11，即：char c11；,4.3.2 字符数组的初始化,(2) 用字符串赋初值： char c = “happen”；或 char c = “happen”； 说明： 不用单个字符做初值，而是用一个字符串做初值，这种方法比较直观、方便，更符合人们的习惯。 需要说明的是：对于字符数组并不要求它的最后一个字符必须为0，甚至可以不包含0，下面这种定义完全正确： char c5= C , h , i , n , a ； 只要用字符串常量赋初值时，就会自动加一个0。有时

31、，人们为了保持处理的一致性，便于测定字符串的实际长度，以及在程序中作相应的处理，在用单个字符赋初值时往往人为地加上0，如：char c6= C , h , i , n , a , 0；,47. 下列叙述正确的是 。 A) 字符串是由若干个字符组成的。 B) 字符串肯定是一个一维的字符数组。 C) 一维字符数组都是字符串。 D) 带有结束符的一维字符数组才是字符串。,4.3.3 字符数组的使用,(1)对字符数组的赋值：(两种方法) 在声明语句中对字符数组赋初值。 例如：char s1 =program; char s2 =B , A , S , I , C ; 在程序中对字符数组的下标变量赋值(

32、直接利用赋值语句赋值)。 例如： char s4; s0= A ;s1= B ;s2= C ;s3= 0 ;,(2)字符数组的输入输出：(两种方法),将整个字符数组作为字符串处理 对于数值型数组，只能逐个元素地进行输入和输出。而对于字符数组可以作为字符串一次性地进行输入和输出。 例如：如下语句直接对字符数组s进行输入输出： char s30; cins; /输入数据: happy cout“s=”s; /输出结果: s=happy,若输入数据: happy birthday 则输出结果: s=happy,注意: 输入字符时的结束标志,在使用cin 进行输入时，系统会一直读取字符，直到遇到空格或

33、回车符才停止,并在字符尾自动加上0 。而用 cout 输出字符数组时，如果遇到结束标记0 ,则输出结束。所以只有空格前的字符被输出。如果希望读取含有空格的字符串或有多行的数据，可以使用cin.getline( )，格式如下： cin.getline ( 字符数组名,字符串长度,规定的结束符） 其中getline( )是输入流的成员函数，使用时，前面必须加cin。作用是输入一系列字符，直到输入流中出现规定的结束符或所读字符个数已达到字符数组的长度。当“规定的结束符”省略不写时，默认此时的结束符为Enter 键。当按下Enter键时，cin.getline( ) 停止读取字符串的操作，并自动在输入

34、的字符后面加上 0 。,cins; / s接收一个不含空格的字符串(以空格结束字符串的读取) cin.getline(s,50); / s可接收一个含空格的一行字符串(以回车键结束字符串的读取) cin.getline(s,50,$); / s可接收一个含空格的多行字符串(以$结束字符串的读取) 注：以上均是以回车键结束字符串的输入。,例4.7 输入一个含有空格的字符串，并将其输出。 #include void main( ) char c50; cout Please input strings: endl; cin.getline(c,50); / 默认结束符为Enter键 cout Th

35、e string is : endl; coutc endl; ,程序的运行结果为： Please input strings: This is a C+ program The string is : This is a C+ program,字符串处理函数都定义在头文件 string.h 中。 (1) 求字符串长度函数 strlen（字符数组） 功能：测试字符串的长度，即字符串中包含的字符的个数，不包括字符串结束标志0在内。该函数的返回值为字符的个数。,4.3.5 字符串处理函数,例4.10 输入任意字符串，求出其长度。 #include #include void main( ) cha

36、r s50; couts; cout“The length of string ” s“ isstrlen(s)endl; ,运行结果为： Please input a string : Hello The length of string Hello is 5,(2) 字符串复制函数 strcpy (字符数组1,字符数组2),功能：将字符数组2中的字符串复制到字符数组1中。串结束标志0也一同复制。字符数组2也可以是一个字符串常量。这时相当于把一个字符串赋予一个字符数组。如： char s110,s2 =“Hello”; strcpy (s1,s2); 说明： 字符数组1的长度必须定义的足够容纳被拷贝的字符串2。 字符数组1必须写成数组名形式（如s1），字符数组2可以是字符数组名，也可以是字符串常量。 数组之间不能相互赋值。,4.3.5 字符串处理函数,0 0 0 0,strcpy (s1,“Hello”);,s1=“Hello”; /error s2=s1; /error,(2) 字符串复制函数 strcpy (字符数组1,字符数组2),功能：将字符数组2中的字符串复制到字符数组1中。串结束标志0也一同复制。字符数组2也可以是一个字符串常量。这时相当于把一个字符串赋予一个字符数组。如： c