C++程序设计第07章-数组课件

1、第7章 数组本章要点了解数组理解怎样定义数组以及怎样操纵数组中的数据理解“数组下标越界”的含义了解数组处理中的一些限制了解怎样将数组作为参数传递给函数理解怎样使用字符串函数处理C-string了解怎样向C-string输入数据以及怎样从C-string输出数据理解怎样操纵二维数组中的数据了解多维数组问题的提出统计某一地区每岁年龄的人数，以及总人数，假定不超过120岁。用120个变量： int age1, age2, age3, . age119, age120程序age1=0;age2=0; cout age1endl; cout age2x; cout age1200)&(xx;程序结构庞大

2、，机械重复，于是引入数组数组（构造数据类型）一维数组二维数组字符数组一维数组的定义 数组（整体）int a10;数组名数组元素个数数组类型引用时不能超出下标 最大值引用下标 int i=3, j=2, a10; 引用 ai, ai+2, ai+j, a0, a1, a2, . a9数组是一个整体概念，数组元素是个体概念，此例： 每一个元素都是一个整数注意：下标从09统计各年龄段的人数问题：统计某一地区每岁年龄的人数，以及总人数，假定不超过120岁。 a0, a1, a2, . a1191 岁人数2 岁人数3 岁人数120 岁人数定义其他类型数组float b5;char c20;b0, b1,

3、 . b4c0, c1, . c19定义引用数组初始化在定义数组时赋初值int a3=1，3，5;float b2=3.14，5.18;char c5=a, b, c, d, e;亦可 int a =1，2，3，4，5; 编译系统自动确定元素个数 int b10=1，2; 前两个元素的值为1、2，其他元素为0数组在内存中的存放在内存中占据：一片连续的存储区例： int a20;VC+中，一个整型变量占用 4 个字节内存。.内存a0.a1a2a18a19注意C+不允许在数组上进行整体操作不能整体赋值不能比较不能整体输入输出赋值：for(i=0;i10;i+) yi=xi;输入：for(i=0;i

4、 yi;输出：for(i=0;i10;i+) cout=yi)一维数组应用逆序数的分解求Fibonacci数列问题排序插入查找（顺序、折半）合并逆序输出 例7.1 问题：程序使a0到a9的值为09，然后按逆序输出。程序：#include #include using namespace std;int main( )int i,a10;for (i=0;i=0;i-)coutsetw(4)ai;coutendl;return 0;运行结果如下： 9 8 7 6 5 4 3 2 1 0将一个数组中的数逆序后再放回原数组,如何做？求Fibonacci数列问题 例7.3 问题：用数组求Fibonac

5、ci数列的前20项和前20项之和。程序：#include using namespace std;int main( )int i, f20=1, 1, sum=f0+f1; for (i=2; i20; i+)fi=fi-2+fi-1; sum+=fi;for (i=0; i20; i+)if (i%5=0) coutn;coutfit;coutn前20项和为：sumn; return 0;数的分解 例7.4 问题：将一个数分解到数组中，然后正向，反向输出。 分解得到的各位数字放在数组a中个位放在a0中十位放在a1中百位放在a2中数的分解#include using namespace st

6、d;int main( )int i, j=0, k, a20;couti;k=i;while(k0) aj+=k%10;k=k/10;cout正向输出序列:=0; k-) coutakt;coutendl;cout反向输出序列:endl;for(k=0; kj; k+) coutakt;coutm，则 a 数组比 b 数组大如果 jbi 的次数 k是 ai=bi 的次数m 是 aiy) flag=1; else if (xy) flag= -1; else flag=0; return(flag);比较数组大小(续)#include using namespace std;int main(

7、 )int large(int,int);int a10,b10,i,j=0,k=0,m=0,n;coutn;cout输入数组a:n;for (i=0;iai;coutn;cout输入数组b:n;for (i=0;ibi;coutn;比较数组大小(续)for (i=0; i10; i+)if (large(ai,bi)=1) j=j+1;else if ( large(ai,bi)=0 ) k=k+1;else m=m+1;cout ai大于bi的次数 jendl;cout ai等于bi的次数 kendl;cout ai小于bi的次数 mm) cout数组 a 大于数组 bn;else if

8、(jm)cout数组 a 小于数组 bn;else coutbi 的次数 k是 ai=bi 的次数m 是 aibi 的次数数组名作函数参数 例7.6 问题：将数组元素逆向存放。原：7 2 5 4 3 6 1 现：1 6 3 4 5 2 7#include using namespace std;#define N 7void reverse(int b , int n) int i, j, t; i=0; j=n-1; while(ij) t=bi; bi=bj; bj=t; i+; j- -; int main( )int aN= 7, 2, 5, 4, 3, 6, 1, i;cout原始数

9、组元素为:endl;for(i=0; iN; i+)coutait;coutn;inverse(a, N);cout逆序后的数组元素为:endl;for( i=0; iN; i+)coutait;coutn;return 0;将数组元素逆向存放（续）实参 a形参 b实参数组与形参数组元素共享存储单元 a0 a1 a2 . a5 a6 . b0 b1 b2 . b5 b6i=0i ji+，j- -j=6冒泡法(起泡法)排序 例7.7 用冒泡法对6个数排序（由小到大）8，4，9，6，5，22，4，5，6， 8，9目标冒泡法的思想是： 顺序扫描数组元素， 将相邻两个数进行比较，将小数调到前面如果有

10、n 个数，则要进行 n-1次扫描。在第 j 次扫描中，要进行 n-j 次两两比较，两两比较时，第一个元素的下标从 1 变化到 n-j 冒泡法排序程序用冒泡法对6个数排序（由小到大）#include using namespace std;#define N 6int main( )int aN;int i,j,t;cout请输入 N 个数:endl;for(i=0;iai;冒泡法排序程序bubble_sort(a, N);cout排好序的数为:endl;for(i=0; iN; i+) coutait;coutendl;return 0;冒泡法排序程序 / 排序程序的核心 void bubbl

11、e_sort(int a,int n)int i, j, t;for(i=0; in-1; i+) / i 控制扫描次数 for(j=0; jaj+1)t=aj; aj=aj+1; aj+1=t;冒泡法排序算法缺点：经常交换执行效率低？能否降低交换次数用选择法排序选择法排序选择法的思想是：例7.8 （假定6个元素存放在a0a5中）第一趟扫描，将a0到a5中最小数的下标找到，设为p， 若 p!=0，则a0与ap交换位置。第二趟扫描，将a1到a5中最小数的下标找到，设为p， 若 p!=1，则a1与ap交换位置。 依此类推，共需5次扫描，第i次扫描时（i=04） 第一个元素的下标为 i， 最后一个元

12、素的下标为5数组名作函数参数问题：编写一个函数实现选择法排序。例7.8 #include using namespace std;void sort(int a10)int i,j,k,t;for(i=0;i9;i+) /选择法排序k=i;for(j=i+1;j10;j+)if(ajak)k=j;if(k!=i)t=ak; ak=ai; ai=t; 有无缺点没有通用性数组名作函数参数int main( )int array10,i;cout请输入数组的元素:endl;for(i=0;iarrayi;sort(array);cout排好序的数组元素为:endl;for(i=0;i10;i+)co

13、utarrayit;coutendl; return 0;内存工作区示意图 5 8 2 9 1 3 6 4 10 7arraya地址传递对前例的修改#include using namespace std;void sort(int a ,int n)int i,j,k,t;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+) if(ajak)k=j;if(k!=i) t=ak; ak=ai; ai=t;对前例的修改int main( )int array100,i,n;cout请输入数组元素个数:n;cout请输入数组的元素:endl;for(i=0;iarrayi;so

14、rt(array,n);cout排好序的数组元素为:endl;for(i=0;in;i+)coutarrayit;coutendl;选择法的另一种实现方法#include /li0708_1.cpp 选择法排序的变种using namespace std; #define N 6 void select_sort(int a, int n)int i ,j,t;for(i=0; in-1; i+) /按升序排序for(j=i; jaj)t=ai; ai=aj; aj=t; int main( ) int aN, i;cout请输入6个数:endl;for(i=0; iai;select_sor

15、t(a, N);cout排好序的数为:endl;for(i=0; iN; i+) coutait;coutendl;return 0;插入例 例7.9 问题：已有一个排好序的数组，今输入一个数要求按原来排序规律将它插入数组中。算法思想0 5 8 10 18 20如插入21，直接插入到20右边如插入6，则把8及其后面的数据全部向右移动一个位置，把6插在8的位置（找到该位置有两种方法：自左向右前插；自右向左后插）后插排序void ba_ins_sort(int a , int n) /li0709.cpp 直接插入排序后插算法int i, j, p; for(i=1; i=0&paj; j-) /

16、将比p大的元素依次右移一个位置aj+1=aj;aj+1=p;筛选法求素数 例7.10 问题：用筛选法求1100之间所有素数，每行输出5个素数。下标i从198下标j从i+199筛选法求素数#include using namespace std;#define N 100void prime(int a,int n)int i, j;for(i=1; in-1; i+) /a0不是素数，因此从a1开始判断 for(j=i+1; jn; j+)if(ai!=0&aj!=0)if(aj%ai=0) aj=0;筛选法求素数int main( )int aN, i, n;for(i=0; iN; i+)

17、 ai=i+1; /赋初值prime(a, N);cout1100内的素数为:endl;for(i=1, n=0; iN; i+) if(ai!=0)coutait;n+;if(n%5=0) coutn; return 0;顺序查找 例7.11问题：在一维数组a 中查找 x 是否存在，若存在，返回其下标，否则返回-1。 6 3 18 24 9 32 6 46 1 12如查找9顺序查找#include using namespace std;#define M 10int search(int a , int x, int n)int i; for(i=0; in; i+)if(x=ai) re

18、turn i;return -1;顺序查找int main( )int array =6, 3, 18, 24, 9, 32, 6, 46, 1, 12, i, p, x;coutx;p=search(array, x, M);cout原始数组元素为:endl;for(i=0; iM; i+) coutarrayi=0) cout查找成功！数组元素的下标为pendl;else cout未查找到！up，则检索失败，算法结束，否则，转第三步； mid=(low+up)/2;若x=amid，则检索成功，算法结束，否则转第五步；xamid，则置up=mid-1，转第二步；否则置low=mid+1，转第

19、二步；折半查找程序#include using namespace std;#define M 10int bi_search(int a , int x, int n)int low=0, mid, up=n-1; while (low=up)mid=(low+up)/2;if(x=amid) return mid; else if(xamid)up=mid-1;else low=mid+1;return -1;折半查找程序int main( )int array =1, 3, 6, 24, 30, 32, 36, 46, 100, 120, i, p, x;coutx;p=bi_searc

20、h(array, x, M);cout原始数组元素为:endl;for(i=0; iM; i+)coutarrayi=0) cout查找成功！数组元素的下标为pendl;else cout未查找到！endl; return 0;求集合的交集 例7.13#include using namespace std;int search(int b , int x, int n) /例7.11中的函数int i;for(i=0; in; i+)/顺序查找法if(x=bi) return i;return -1;int intersection(int a , int b , int c , int m

21、, int n)int i, j, k=0;for(i=0; im; i+)if(j=search(b, ai, n)!=-1) /用数组元素作为函数的实参 ck+=bj; return k;求集合的交集 例7.13int main( )int a =4, 8, 2, 1, 9, 10,b =2, 5, 3, 9, 7, c20, count, i;count=intersection(a, b, c, 6, 5); /用数组名作为函数的实参cout数组a和数组b的交集:;for(i=0; icount; i+) coutcit;coutendl;cout数组a和数组b交集中元素的个数:cou

22、ntendl;return 0;问题 课程1 课程2 课程3 学生1 89 78 56学生2 88 99 100 学生3 72 80 61学生4 60 70 75二维表格求每门课程的平均成绩，一列的平均值求一个学生的平均成绩，一行的平均值 二维数组的定义 数组（整体）int a43;数组名行数列数数组类型元素的引用int a43 代表12个简单变量：a00 a01 a02a10 a11 a12a20 a21 a22a30 a31 a32行号从 0 开始，列号也从 0 开始，元素的引用问题： 课程1 课程2 课程3 学生1 89 78 56 学生2 88 99 100 学生3 72 80 61

23、学生4 60 70 75二维表格元素(个体)int a43 代表12个简单变量 如 a00 、a12、a32 aij行下标列下标二维数组在内存中的存储占据一片连续存储区a00 a01 a02a10 a11 a12a20 a21 a22a30 a31 a32按行存放第0 行a00a01a02a10a11a12第 1 行a30a31a32第 3 行.内存二维数组的初始化 int a43= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ; 四行三列 int a43= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ; 存储顺序 int a43

24、= 1, 4, 7, 10 ; 给每一行的第1个元素赋值，其余为零二维数组的初始化int a 4=1,2,3,4,5,6,7,8,9,10,11,12;第一维的长度可不指定第二维的长度不能省二维数组的应用问题： 课程1 课程2 课程3 aver数组 学生1 89 78 56 aver0 学生2 88 99 100 aver1 学生3 72 80 61 aver2 学生4 60 70 75 aver3？求每个学生的平均成绩，即求各行的平均值程序主要部分int a43=., aver4; int i, j;for(i=0; i4; i+) /* i 控制行数 */ averi = 0; for(j

25、=0; j3; j+) averi + = aij; /* j 控制列数 */ averi / = 3; for(i=0; i4; i+) cout averi endl ; 上例解法二解2： 课程1 课程2 课程3 空列 学生1 89 78 56 a03 学生2 88 99 100 a13 学生3 72 80 61 a23 学生4 60 70 75 a33数组中多定义一列，让其初值为零，用来存放平均值。解法二程序片段 /* 多定义一列 ，存放平均值 */int a44 89, 78, 56, 0 . ; int i, j; for(i=0; i4; i+) /* i 控制行数 */ for(

26、j=0; j3; j+) a i3 + = aij; /* j 控制列数 */ a i3 / = 3; for(i=0; i4; i+) cout a i3 endl ; 二维数组名用作函数参数数组元素作函数参数与用变量做实参一样单向值传递数组名作函数参数实参与形参均用数组名实参和形参可用指针（ch9介绍）二维数组元素作函数参数问题：有两个二维数组a34和b34，统计两个数组中对应元素相等的个数。算法：判断对应元素是否相等，等，则记数器加1 统计两个数组中对应元素相等的个数 #include /二维数组元素作为函数参数using namespace std;int main( )int equ

27、al(int, int);int a34=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, b34=12, 2, 3, 4, 10, 6, 7, 11, 9, 5, 8, 1, i, j, k=0;for (i=0; i3; i+)for(j=0; j4; j+)if (equal(aij,bij)= =1) k+;cout两个数组中对应元素相等的个数为:kendl; return 0;int equal(int x, int y)int flag;if (x=y) flag=1;else flag=0;return(flag);求矩阵中的最小值 例7.15问题：有

28、一个34 的矩阵，要求编程求出其中值最小的元素，以及其所在的行号和列号。算法：假定数组中第0行第0列的元素最小其他的元素与它比较，只要比它小，则将该值记下并记下它所在的行和列的下标求矩阵中的最小值#include using namespace std;int min_element(int a 4, int &row, int &colum)int i, j, min;min=a00;for (i=0; i=2; i+)for (j=0; j=3; j+)if (aijmin)min=aij;row=i;colum=j;return min;求矩阵中的最小值int main( )int i,

29、 j, row=0, colum=0, min;int a34;cout请输入3行4列的二维数组:;for (i=0; i=2; i+)for (j=0; jaij;min=min_element(a, row, colum);cout最小值=minendl;cout所在行号=row 所在列号=columendl; return 0;矩阵转置 例7.16问题：将一个二维数组行和列元素互换存到另一个二维数组中。（矩阵转置）程序： 矩阵转置#include using namespace std;void transpose(int a3, int b3)for (int i=0; i3; i+)

30、for (int j=0; j3; j+) bji=aij;int main( )int a33=1, 2, 3, 4, 5, 6, 7, 8, 9;int b33, i, j;cout数组a:endl;for (i=0; i3; i+)for (j=0; j3; j+) coutaijt;coutn;transpose(a, b);矩阵转置cout数组 b:n;for (i=0; i3; i+)for(j=0; j3; j+) coutbijt;coutn; return 0;问题：在一个矩阵中如何转置（对方阵而言）？对方阵的转置#include using namespace std;in

31、t main( ) int a33= . ; int t, i, j ; 输出数组 a ; for(i=0; i3; i+) for(j=i+1; j3; j+) /对右上三角形循环t=aij; aij=aji; aji=t; 输出转置后的数组 a ; return 0;对左下三角形元素循环，如何实现字符数组定义和引用定义：char c10;引用： c0，c1，c2， c9 每个元素都是一个简单的字符变量 ci=a; for(i=0; i ci ; for(i=4; i=0; i- -) cout 数组长度：出错初值个数数组长度：其余元素自动定为空字符即 0 初值个数=数组长度：定义时可省略数

32、组长度字符串例：字符串常数China， OK! 占6个字节 占4个字节一般存放到一维字符数组中，即用一维字符数组实现字符串。China00OK!. 0 为字符串结尾标志字符串的输入输出-逐个字符输入输出 将字符串存放到一维字符数组中 例：char s110= C , h , i , n , a , 0 ; 简写为：char s110=China; 再简写为：char s110=China; 只用字符数组的前六个字节空间输出一个三角形图形演示例7.20#include using namespace std;int main( )char star5= , ,*, ,*, ,*,*, ,*, ,

33、*;for(int i=0;i3;i+)for(int j=0;ji+3;j+) /输出空字符时，什么也不输出cout starij;coutendl; return 0;字符串的输入输出(作为整体输入输出)例7.21#include using namespace std;int main( )char str120,str220;cout输入两个字符串：str1;cinstr2;cout字符串1str1endl;cout字符串2str2endl; return 0;输入China good演示结论不能输入带空格的字符串使用 cin.getline ( )函数实现字符串输入例7.22#inc

34、lude using namespace std;int main( )char str180;char str24=G,o,o,d;cout请输入一行字符串：endl;cin.getline(str1,80); /表示最多输入79个字符，系统自动在最后加一个0coutstr1=str1endl;coutstr2=str2endl; return 0;输入aaa bbb ccc字符串运算函数1. strlen(字符数组) 求字符串长度(STRing LENgth ) 例：char s110=ABCD ; char s210=12n ; char s310=An0121; int x, y, z

35、, i; x = strlen(s1); y = strlen(s2); z = strlen(s3); i = strlen(XYZ0ABC);x = 4y = 4z = 7 i = 3sizeof(s1)sizeof(s2) sizeof(s3)结果均为10字符串运算函数2. strcat(字符数组1, 字符数组2) 连接两个字符串(STRing conCATenate )， 将 字符数组2 的内容连接到 字符数组1 之后。 例：char s110=AB, s210=CD； strcat(s1,s2); couts1; couts2; strcat(s1, EF); couts1;输出 A

36、BCD输出 CD输出 ABCDEF注意此时s1的空间应定义得足够大。字符串运算函数3. strcpy(字符数组1, 字符数组2) 字符串复制(STRing CoPY ) 将字符串2 的值复制到字符数组1中例：char s110, s210； strcpy(s1, ABCD); strcpy(s2, XYZ); strcpy(s1,s2); couts1; cout字符串2,函数值为一正数字符串1字符串2,函数值为一负数对两个字符串比较不能用str1= =str2其他一些字符串运算函数8. strncpy(字符数组1, 字符数组2, len) 功能：将字符串2 的前 len 个字符， 拷入字符数组15. strlwr(字符数组) /(STRing LoWeRcase ) 功能：将字符串中字符全部转换成小写。6. strupr(字符数组) /(STRing UPpeRcase ) 功能：将字符串中字符全部