《Visual C++程序设计》-王永国-电子教案 第4章

第4章 数组、指针与字符串,4.1 数组的基本概念 4.2 一维数组 4.3 二维数组 4.4 字符数组 4.5 指针和数组 4.6 结构体与链表 4.7 常用算法,4.1 数组的基本概念,【问题】从键盘接收10个数，求平均数并输出小于平均数的数,分析：从键盘接收10个数，求平均数很简单，可以采用简单变量和循环结构相结合的方法，程序段如下： float aver=0; for (i=0;iai; aver+=ai; aver=aver/10; / 求10个数的平均数 但是输出小于平均数的数就比较麻烦了，因为从键盘接收的10个数在求和以后没有保存起来，等再比较比平均数小的数就无法实现。若要输出小于平均数的数，必须再重复输入这10个数。这样带来两个问题： （1）输入数据的工作量成倍增加； （2）若本次输入的数与上次不同，则输出的结果不正确。,在程序设计中，我们常把具有相同类型的若干变量按有序的形式组织起来，这些按序排列的同类型数据元素的集合称为数组。数组属于构造类型，在计算机中，一个数组在内存中占用一片连续的存储空间，在程序中用数组名来标识这一数组，而下标指明数组中各元素的序号，用下标变量来标识数组的每个元素。根据下标的个数不同可以把数组分为一维、二维和多维的，本章重点介绍一维和二维数组。 数组在使用前必须先定义（数组名、类型、大小、维数），后使用。,正确： const int s=10; int as; float f5;,错误： int s=10; int as; float b3.4,下标从0开始 数组名是常量，表示数组在内存中的首地址。 数组长度应该为整型常量表达式，不能是变量。 如：,4.2.1 一维数组的定义、存储和初始化 1. 定义形式 数据类型 数组名整型常量表达式; 如： int s5；,4.2 一维数组,2. 数组的初始化,花括号,错误: int a10; a=1,3,5,7,9; /数组名是个地址常量，不能被赋值。 int a10; a10=1,3,5,7,9; /a10不是数组中的元素，不能用花括号为一个元素赋多个值。 int c3=1,2, 3,4; /常量个数超过数组定义的长度。,2) 给部分元素赋初值。 如：int a10=1,3,5,7,9; 花括号内列出的值赋给了前面的若干个元素，其余元素系统自动赋0 。,1) 给所有元素赋初值。 如：int a5=0,2,4,6,8; 或 int a =0,2,4,6,8;,4.2.2 数组元素的引用和基本操作,1数组元素的引用 形式：数组名下标 相当于一个普通变量 如有： int a10=1,2,3,4,5,6,7,8,9,10,b10,i(2)； 则： a3=a0+ai； couta2+i； coutaa3； couta10; /数组下标越界 couta; /对数组一般不能作为一个整体进行操作 b=a;,2基本操作,假设有定义：int aN; N是已定义过的符号常量。 (1) 数组元素的输入 for(j=0; jaj;,(2)通过随机函数rand()产生0100的N个数据 for ( i = 0; iN;i+) /rand()函数产生032727之间的整数 ai=int(rand()%101);,(3) 数组元素的求和 sum=0; for(j=0; jmax)max=aj;,(5) 求最大元素下标 imax=0; /imax代表最大元素下标 for (j=1;jaimax)imax=j;,(6) 将最大元素放于某一特定位置(如放在最前头) imax=0; for(j=1;jaimax)imax=j; if(imax!=0) t=a0;a0=aimax;aimax=t;,4.2.3 数组排序,排序是将一组数按递增或递减的次序排列，如按学生的成绩、球赛积分等排序。常用的算法有:,选择法 () 冒泡法 () 插入法 快速排序法 .,1. 选择法排序 基本思想: (1) 从n个数的序列中选出最小的数(递增), 与第1个数交换位置； (2) 除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置;3) 重复(1)n-1遍，最后构成递增序列。,【例4.2】对存放在数组中的6个数，用选择法按递增排序。,下标 : 0 15 1 25 2 35 3 45 4 5,for( i= 0;i5;i+) min= i; for(j=i+1;j6;j+) if(ajamin)min= j; if(i!=min) temp=ai; ai= amin; amin=temp; ,2. 冒泡法排序,for(i=0;iaj ) temp=aj-1; aj-1=aj; aj=temp; ,思考:当数据未交换,说明数组已有序 ,如何结束排序?,（1）从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较比较完毕，最大的数存放在aN-1中； （2）然后对a0到aN-2的N-1个数进行同(1)的操作，次最大数放入aN-2元素内，完成第二趟排序；依次类推，进行N-1趟排序后，所有数均有序。 【例4.3】用冒泡排序法实现例4.2,基本思想总结：,4.3 二维数组,以“先行后列”的规则连续存放:,序号=当前行号*每行列数+当前列号,4.3.1 二维数组的定义和初始化 1. 数组的定义 形式：数据类型 数组名常量表达式1常量表达式2； 如:float a23;,（1）按在内存排列顺序对所有元素赋初值。 int a23=1,2,3,4,5,6; 或 int a3=1,2,3,4,5,6; （2）按行给所有元素赋初值，每一行的数据放于一个花括号内。 int a23=1,2,3,4,5,6; （3）按行给部分元素赋初值，在静态存贮类型static中省略的元素初值此时自动为0。 static int b34=1,2,0,3,4,0,0,5; 对应的数组b为:,2. 数组的初始化,（4）按行赋初值也可省略第一维的长度。 static int c 3=1, ,2; 对应的数组c为:,4.3.2 二维数组的基本操作,1. 数组的输入、输出 【例4.4】输入两个矩阵A、B的值，求C=A+B 。,分析：A、B矩阵相加，其实质是将两矩阵的对应元素相加。相加的条件是有相同的行、列数。,#include “iostream.h“ #include “iomanip.h“ void main() int a23,b23,c23,i,j; for ( i = 0; iaij; for ( i = 0; ibij; for ( i = 0; i2; i+) /A+B矩阵，每个对应元素相加 for( j =0; j3; j+) cij=aij+bij; for ( i = 0; i2; i+) for( j=0; j3; j+) coutsetw(4)cij; coutendl; ,程序：,2. 求二维数组中最大（或最小）元素及下标,max=a00; imax=0; jmax=0; for ( i = 0; imax) max=aij; imax=i; jmax=j;,【例4.5】对3×3方阵，求最大元素及下标。 与一维数组求最大值的方式相同，但要用双重循环来实现。,3. 矩阵转置,for ( i = 0; i3; i+) for( j=0; ji; j+) t=aij; aij=aji; aji=t; ,将矩阵以主对角线为轴线，将元素的行和列位置调换。 【例4.6】对3×3方阵转置,4. 矩阵相乘,设矩阵A、B为：,则矩阵C为：,即矩阵C的第i行第j列元素可通过下边公式求得：,c00元素的实现： s=0; for(k=0;k3;k+)s+=a0k*bk0; c00=s;,程序： #include “iostream.h“ #define M 2 #define N 3 #define P 4 void main() int aMN=3,5,7,4,6,8,bNP=1,4,7,10,2,5,8,11,3,6,9,12； int cMP,i, j, k, s; for(i=0; iM; i+) for(j=0; jP; j+) s=0; / 求一个元素的值 for(k=0; kN; k+) s+=aik*bkj; cij = s; for(i=0;iM;i+) for(j=0;jP;j+) coutcij“ “; coutendl; ,4.4 字符数组,字符串是由一对双引号作定界符的若干个有效字符组成的字符序列。存储时自动在最后加入结束标志符0 。例如对字符串常量： “ab123“,系统自动添加 0 结束标志符,处理字符串的方法有： 字符数组、CString（string）类和字符指针。,1. 字符数组,如： char s6； char s126；,字符数组,若干个字符,字符串,2.字符数组的初始化,(1) 逐个字符赋初值 char s10='I', ' ', 'a', 'm', ' ','f', 'i', 'n', 'e' /s不是字符串 (2) 用字符串为字符数组初始化 char s10 = “I am fine“; char s10 = “I am fine“; s是字符串， 0 系统自动添加,(3) 字符串数组初始化 对二维数组以字符串形式初始化。 char a48=“FOXPRO“, “FORTRAN“, “BASIC“, “C/C+“;,注意：对于二维字符数组，用两个下标表示数组中的一个字符。,注意不要出现下面的错误:,char s10=“This is a book“; char s10; s = “I am fine“; char s10; s = 'I', ' ', 'a', 'm', ' ' , 'f', 'i', 'n', 'e',3. 字符数组的输入/输出 (1)逐个数组元素的输入/输出,char s110; for (i = 0; is1i; /s1中是字符，不是字符串,注意：输入时各输入项之间不需加空格分隔,(2)字符串整体的输入/输出,char s110,s225; 输入： cins1; gets(s1); for( int i=0; i2;i+) gets(s2i); s1、s2中是字符串， '0'自动添加,注意： 使用cins1;语句，字符串中不能有空格。 函数gets()和puts()是对字符串整体输入/输出 ，应加#include “stdio.h“命令。 gets(字符数组名或字符指针变量名); puts(字符数组名或字符指针变量名);,输出： cout s1; puts(s1); for( i=0; i2;i+) puts(s2i);,#include “stdio.h“ #include