第5讲 数组 5.1 一维数组 5.2 二维数组 5.3 字符串数组 5.4 综合案例分析.

Presentation on theme: "第5讲 数组 5.1 一维数组 5.2 二维数组 5.3 字符串数组 5.4 综合案例分析."— Presentation transcript:

1 第5讲 数组 一维数组 二维数组 字符串数组 综合案例分析

2 学习目标 理解数组的概念和存储方式； 熟练掌握一维、二维数组的定义、初始化和使 用； 熟练掌握字符串数组的定义、初始化和使用；
掌握数组的常用算法。

3 内容 一维数组 二维数组 字符串数组 数组的应用

4 从数字到数组 数字 1; 23; 1.5; … -1 71 39 -7 14 64 73 1.5 23 1 数组 内存

5 数组的基本概念 数组: 数组的维数: 标识数组元素的下标个数; 数组名: 标识数组的名称; 数组的数据类型:
6 数组名: 标识数组的名称; 1 数组: 由相同数据类型的多个数据组成的集合 数组的数据类型: 所存储数据的类型; 5 数组元素： 数组中存储的数据; 2 下标： 数据在数组中的序号,从0开始！ 数组元素标识： 数组名[下标]:唯一标识一个元素; 3 4

6 数组的分类 当数组只有1个下标时，称这样的数组为一维数组。 一维数组 二维数组 高维数组
int a[5]; double b[3][5]; char c[3][4][6]; 一维数组 二维数组 高维数组

7 一维数组 定义方式 类型说明符 数组名[常量表达式]; int a[4]; 若存放首地址为2000H，则在内存中为： 定义类型 元素个数
数组名称 若存放首地址为2000H，则在内存中为： a[3] a[2] a[1] a[0] 2010H 200CH 2008H 2004H 2000H

8 一维数组的引用 只能逐个引用数组元素，不能一次引用整个数组 数组必须先定义，后使用 数组的引用 数组的引用 数组的引用 引用格式：
4 数组的引用 1 数组的引用 数组的引用 引用格式： 数组名[下标] 3 数组元素使用时与变量类似，可进行赋值、运算、输出 数组的引用 2 必须从0开始

9 一维数组的引用 … void main(void ) { int i, a[10]; i=0, a[0]=0
for ( i=0; i<10; i++) a[i]=i; for ( i=9; i>=0 ; i--) cout<<a[i]<<‘\t’; cout<<“\n”;} a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 定义 i=0, a[0]=0 1 i=1, a[1]=1 2 3 4 5 6 7 8 i=2, a[2]=2 赋值 … i=9, a[9]=9 输出 9 输出：9_ _8_ _7_ _6_ _5_ _4_ _3_ _2_ _1_ _0

10 一维数组的初始化 初始化：在定义数组的同时给数组元素赋值。 初始化方法： int a[5]={1,2,3,4,5};
对数组中的每一个元素都赋初值。 int a[5]={0}; 对数组中的一部分元素列举初值，未赋值的部分是0 int a[ ]={1,2,3,4,5}; 不指明数组元素个数，通过初始化数值确定。

11 例1： f [i]=f [i-1]+f [i-2] 求斐波那契（Fibonacci）数列：1,1,2,3,5,8,......的前20个数：
F1= (n=1) F2= (n=2) Fn=Fn-1+Fn (n>=3) 21 13 8 5 3 2 1 .... f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0] f [i]=f [i-1]+f [i-2]

12 例1： 程序 void main (void) { int i; int f [20]={1,1};
for (i=2 ; i<20 ; i++ ) f [i]=f [i-1]+f [i-2]; for ( i=0; i<20; i++) { if (i%5= =0) cout<<“\n”; cout<<f [i]<<‘\t’; } 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

13 内容 一维数组 二维数组 字符串数组 综合案例分析

14 5.2.1 二维数组的定义和初始化 一、定义方式： 类型说明符 数组名[常量表达式][常量表达式]; int a[3][4];
类型说明符 数组名[常量表达式][常量表达式]; 列数 行数 int a[3][4]; 定义类型 数组名 表明a数组由3×4个int型元素组成 其元素分别为：a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3], a[2][0], a[2][1], a[2][2], a[2][3]

15 二维数组的定义 其行列的序号均从0开始。若存放首地址为2000H，则在内存中为：
201cH 2020H 2028H 202cH a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3] 即在内存中，多维数组依然是直线顺序排列的，第一个元素位于最低地址处。

16 二维数组的引用 定义 与一维数组一样，二维数组必须先定义，其维数必须是常量。具体引用时（赋值、运算、输出）其元素等同于变量。 赋值
void main(void) { int a[2][3], i, j; cout<<“Input 2*3 numbers\n”; for (i=0; i<2; i++) /* 输入 */ for(j=0; j<3; j++) cin>>a[i][j]; for (i=0; i<2; i++) /* 输出 */ { for(j=0; j<3; j++) cout<<a[i][j]<<‘\t’; cout<<“\n”; } 与一维数组一样，二维数组必须先定义，其维数必须是常量。具体引用时（赋值、运算、输出）其元素等同于变量。 赋值 输入： <CR> 输出： _ _ _1_ _ _2_ _ _3 _ _ _4_ _ _5_ _ _6 输出

17 二维数组的初始化 在定义数组的同时给数组元素赋值。即在编译阶段给数组所在的内存赋值。 1、分行赋值
int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}; 2、顺序赋值 int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12}; //依次赋值

18 二维数组的初始化 int a[3][4]={{1},{5},{9}}; 1 1
/* a[0][0]=1, a[1][0]=5, a[2][0]=9 其余元素为0 */ 1 5 1 5 9 int a[3][4]={{0,1},{5}}; /* a[0][0]=0, a[0][1]=1, a[1][0]=5 */

19 二维数组的初始化 4、分行或全部赋值时，可以省略第一维，第二维不可省。
int a[ ][4]={{1,2},{5,6,7,8,}{9,10,11,12}}; 5、不能给数组整体赋值，只能一个一个地赋值。 int a[2][3]={1,2,3,.....,12};

20 a[i][j]=a[i-1][a[i-1][j]]+1; else a[i][j]=j;
void main(void) { int a[3][3], i, j; for (i=0; i<3; i++) for (j=0; j<3; j++) { if (i= =2) a[i][j]=a[i-1][a[i-1][j]]+1; else a[i][j]=j; cout<<a[i][j]<<‘\t’; } cout<<“\n”; i=0 a[0][0]=0 a[0][1]=1 a[0][2]=2 i=1 a[1][0]=0 a[1][1]=1 a[1][2]=2 i=2 a[2][0]=a[1][a[1][0]]+1=a[1][0]+1=1 a[2][1]=a[1][a[1][1]]+1=a[1][1]+1=2 a[2][2]=a[1][a[1][2]]+1=a[1][2]+1=3 输出：_ _ _0_ _ _1_ _ _ 2 _ _ _0_ _ _1_ _ _ 2 _ _ _1_ _ _2_ _ _ 3

21 例2： 有一个3×4的矩阵，要求编程序求出其中值最大 的那个元素的值，以及其所在的行号和列号。
有一个3×4的矩阵，要求编程序求出其中值最大 的那个元素的值，以及其所在的行号和列号。 先考虑解此问题的思路。从若干个数中求最大值的方法很多，我 们现在采用“打擂台”算法。如果有若干人比武，先有一人站在 台上，再上去一人与其交手，败者下台，胜者留台上。第三个人 再上台与在台上者比，同样是败者下台，胜者留台上。如此比下 去直到所有人都上台比过为止。最后留在台上的就是胜者。 程序模拟这个方法，开始时把a[0][0]的值赋给变量max，max就是 开始时的擂主，然后让下一个元素与它比较，将二者中值大者保 存在max中，然后再让下一个元素与新的max比，直到最后一个元 素比完为止。max最后的值就是数组所有元素中的最大值。

22 例2：实现程序 max=a[0][0]; for (i=0;i<=2;i++) for (j=0;j<=3;j++)
if (a[i][j]>max { max=a[i][j]; row=i; colum=j; } cout<<row<<‘\t’<<colum<<‘\t’<<max<<endl; //使max开始时取a[0][0]的值 //从第0行到第2行 //从第0列到第3列 )//如果某元素大于max //max将取该元素的值 //记下该元素的行号i //记下该元素的列号j

23 多维数组 多维数组的声明和二维数组相同，只是下标更多， 一般形式如下：
多维数组的声明和二维数组相同，只是下标更多， 一般形式如下： 数据类型 数组名[常量表达式1][常量表达式2]…[常 量表达式n]; 例如，多维数组的声明如下： int a[3][4][5]; int b[4][5][7][8]; 上述两条代码分别定义了一个三维数组和一个四维 数组。由于数组元素的位置都可以通过偏移量计算， 所以对于三维数组a[m][n][p]来说，元素a[i][j][k]所 在的地址是从a[0][0][0]算起到 个单位的 地方。 （i*n*p+j*p+k）

24 内容 一维数组 二维数组 字符串数组 综合案例分析

25 字符数组的定义 一、字符数组的定义 char 数组名[常量表达式]; char c[4]; /*每个元素占一个字节 */
用来存放字符数据的数组是字符数组，字符数组 中的一个元素存放一个字符。 一、字符数组的定义 char 数组名[常量表达式]; 类型 数组名 char c[4]; /*每个元素占一个字节 */ 数组大小 c[0]=‘I’; c[1]=‘m’; c[2]=‘_’；

26 字符数组的初始化 与数值数组的初始化相同，取其相应字符的ASCII值。 char c[10]={‘I’, ‘ ’, ‘a’, ‘m’, ‘ ’, ‘a’, ‘ ’ , ‘b’, ‘o’, ‘y’}; 随机 ‘y’ ‘o’ ‘b’ ‘ ’ ‘a’ ‘m’ ‘I’ c c[0] c[9]

27 字符数组的初始化 char st1[ ]={65, 66, 68}; ‘A’ ‘B’ ‘D’
如果字符个数大于数组长度，做错误处理；如果数值个数小于数组长度，后面的字节全部为‘\0’。 如果省略数组长度，则字符数即为数组长度。 static char c[ ]={‘I’, ‘ ’, ‘a’, ‘m’, ‘ ’, ‘a’, ‘ ’ , ‘g’, ‘i’, ‘r’, ’l’}; 同理，也可定义和初始化一个二维或多维的字符数组。分层或省略最后一维。

28 字符数组的引用 void main(void)
{ char c[10]={‘I’, ‘ ’, ‘a’, ‘m’, ‘ ’, ‘a’, ‘ ’ , ‘b’, ‘o’, ‘y’}; int i; for (i=0; i<10; i++) cout<<c[i]; cout<<“\n”; } 定义 输出

29 字符串和字符串结束标志 C H I N A ‘\0’ C++语言将字符串作为字符数组来处理。

30 字符串与字符数组的区别： char a[ ]={‘C’,’H’,’I’,’N’,’A’}; char c[ ]=“CHINA”; 字符数组
随机 A N I H C 长度占5个字节 char c[ ]=“CHINA”; 字符串 随机 ‘\0’ A N I H C 长度占6个字节

31 用字符串的形式为字符数组赋初值 char c[ ]={“I am a boy”}; /*长度11字节，以‘\0’结尾 */
char a[ ]={‘I’, ‘ ’, ‘a’, ‘m’, ‘ ’, ‘a’, ‘ ’ , ‘b’, ‘o’, ‘y’}; /* 长度10字节 */ 如果数组定义的长度大于字符串的长度，后面均为‘\0’。 char c[10]=“CHINA”; ‘\0’ A N I H C c ‘\0’的ASCII为0，而‘ ’(空格)的ASCII为32。

32 几种字符数组赋初值形式 char w[ ]={‘T’, ‘u’, ‘r’, ‘b’, ‘o’, ‘\0’};
非法 T u r b o ‘\0’ T u r b o ‘\0’ T u r b o ‘\0’

33 二维字符数组 char a[2][5]={“abcd”, “ABCD”}; 不能先定义字符数组然后用赋值语句整体赋值。
‘\0’ A B C D 不能先定义字符数组然后用赋值语句整体赋值。 char str[12]; str=“The String”; char str[12]=“The String”； 定义数组，开辟空间时赋初值 非法，在语句中赋值 str为字符数组在内存中存储的地址，一经定义，便成为常量，不可再赋值。

34 字符数组的输入输出 逐个字符的输入输出。这种输入输出的方法，通常是使用循环语句来实现的。如： char str[10];
cout<<“输入十个字符：”; for(int i=0;i<10;i++) cin>>str[i]; //A ...... A行将输入的十个字符依次送给数组str中的各个元素。 定义 赋值

35 把字符数组作为字符串输入输出 对于一维字符数组的输入，在cin中仅给出数组名； 输出时，在cout中也只给出数组名。
void main (void ) {char s1[50],s2[60]; cout << “输入二个字符串:”; cin >> s1; cin >> s2; cout << “\n s1 = “ << s1; cout << “\n s2 = “ << s2 << “\n”;  } 输入：abcd<CR> string<CR> cin只能输入一个单词，不能输入一行单词。 数组名 数组名 输出到‘\0’为止

36 cin.getline(数组名, 数组空间数);
字符数组的输入输出 当要把输入的一行作为一个字符串送到字符数组中时，则 要使用函数cin.getline( )。这个函数的第一个参数为字符数 组名，第二个参数为允许输入的最大字符个数。 cin.getline(数组名, 数组空间数); 首先开辟空间 参数是数组名 char s1[80]; cin.getline(s1, 80);

37 字符串处理函数 所有字符串处理函数的参数都是字符数组名
C＋＋中没有对字符串变量进行赋值、合并、比 较的运算符，但提供了许多字符串处理函数，用 户可以调用 #include “string.h” 所有字符串处理函数的参数都是字符数组名

38 合并两个字符串的函数 1、合并两个字符串的函数 strcat (str1, str2) 空间足够大
static char str1[20]={“I am a ”}; static char str2[ ]={“boy”}; strcat (str1, str2); I a m '\0' b o y ‘\0’ I a m b o y '\0' 将第二个字符串 str2 接到第一个字符串 str1 后。 注意：第一个字符串要有足够的空间。

39 复制两个字符串的函数 2、复制两个字符串的函数 strcpy (str1, str2) '\0' a m I '\0' y o b '\0'
static char str1[20]={“I am a ”}; static char str2[ ]={“boy”}; strcpy (str1, str2); '\0' a m I str1 '\0' y o b str2 '\0' a y o b str1 字符串正确赋值 strcpy ( str1, “CHINA”); '\0' A N I H C str1 str1=str2; str1=“CHINA”; 均为非法 strcpy (“CHINA”, str1); 39

40 比较两个字符串的函数 3、比较两个字符串的函数 strcmp (str1, str2)
此函数用来比较str1和str2中字符串的内容。函数对字符串中的ASCII字符逐个两两比较，直到遇到不同字符或‘\0’为止。函数值由两个对应字符相减而得。 该函数具有返回值，返回值是两字符串对应的第一个不同的ASCII码的差值。 若两个字符串完全相同，函数值为0。 用来判断两字符串是否相等 if ( strcmp (str1, str2)==0) { }

41 例： static char str1[20]={“CHINA”}; static char str2[ ]={“CHINB”};
cout<< strcmp (str1, str2)<<endl; 输出：-1 static char str1[20]={“CHINA”}; static char str2[ ]={“AHINB”}; cout<<strcmp (str1, str2)<<endl; 输出：2 if (str1= =str2) cout<<“yes\n”; 非法 正确 if (strcmp (str1,str2)= =0) cout<<“yes\n”;

42 其他字符数组操作函数 4 求字符串长度的函数 strlen (str1) 5 将str1中的大写字母转换成小写字母 strlwr(str1)
6 将str1中的小写字母转换成大写字母strupr (str1)

43 内容 一维数组 二维数组 字符串数组 数组的应用

44 数组的应用 1. 票数统计 美国大选 法国大选 韩国大选

45 数组的应用 1. 票数统计 张三 李四 王五 1 a[1] 2 a[2] +1 3 a[3] 1 2 3 +1
编程技巧：先具体,再一般 有n位候选人，m位选民投票。统计每位候选人的得票数。不选或选其他人视为废票，也要统计。 a[0]累加废票数 废票如何计数？ 票数统计 张三 李四 王五 1 a[1] 选票 张 三 李 四 王 五 2 a[2] +1 3 a[3] 1 2 3 +1 static int a[4]; 三个元素a[1],a[2],a[3]

46 select>3或select<1
投票统计的算法 n=0 定义a[4]数组，元素初值都为0 输入一张选票结果select select>3或select<1 a[select]++ Y N n++ a[select]++ a[0]++ Y N n<100 输出结果

47 投票统计的初步程序 main( ) { int n=0,select;static int a[4]; do{
cin>>select; if(select>3||select<1) a[0]++; else a[select]++; }while(n<=100); for(n=0; n<4; n++) cout<<“a[”<<i<<“]=”<<a[i]; }

48 数组的应用2 2.数组的排序 全国城市GDP排序 学生的学习成绩排序 生产小组的生产量排序 代表选举结果的人名排序 工厂中人员按年龄排序
…………

49 冒泡排序 输入N个学生的成绩，按由小到大的顺序 进行排序并输出。 例如：N=8，对以下成绩进行排序:

50 冒泡排序 冒泡排序算法过程：假设对一个整型数组a[N]进行冒泡排序 过程如下： Step.1
比较a[0]与a[1]，如果a[0]>a[1]，则对a[0]与a[1]进行交换；然后比较a[1]与a[2]，如果a[1]>a[2]，则对a[1]与a[2]进行交换，依次类推，直至最后两个数比较为止。经过第一趟冒泡排序，最大的数将被安置在最后一个元素位置上。 Step.2 对前N-1个数进行第二轮冒泡排序，排序方法相同，结果使这N-1个数中的最大数被安置在第N-1个元素的位置上 Step.3 重复上述过程， 通过N-1轮冒泡排 序后，所有的数 按由小到大的进 行排列，整个排 序过程结束。

51 比较a[i]与a[i+1],进行交换,依次类推
冒泡排序 比较a[i]与a[i+1],进行交换,依次类推 9 8 5 4 2 8 9 5 4 2 8 5 9 4 2 8 5 4 9 2 8 5 4 2 9 8 5 4 2 9 第一趟循环5次

52 冒泡排序 8 5 4 2 9 5 8 4 2 9 5 4 8 2 9 5 4 2 8 9 5 4 3 8 9 5 4 3 8 9 4 5 3 8 9 4 3 5 8 9 4 3 5 8 9 4 3 5 8 9 3 4 5 8 9 3 4 5 8 9 3 4 5 8 9 3 4 5 8 9 第二趟 循环4次 第三趟 循环3次 第四趟 循环2次 第五趟 循环1次

53 冒泡排序 总结： n 1 2 3 4 5 5 4 3 2 1 共有6个数 趟数 j(1~n-1) 次数 n-j 程序 修改后程序
for (j=1; j<=n-1; j++) for (i=1; i<=n-j ; i++) { if (a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } for (j=0; j<n-1; j++) for (i=0; i<n-1-j; i++) { if (a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } 元素的序号从0开始

54 全部程序 #include "stdafx.h" #include <iostream> using namespace std; int main(int argc, char* argv[]) { int i,a[6],n,t; cout<<"Please input six numbers"<<endl; for(i=0;i<6;i++) cin>>a[i]; cout<<"The six numbers are"<<endl; for (i=0;i<6;i++) cout<<a[i]<<endl; n=6; for (int j=0; j<n-1; j++) for (i=0; i<n-1-j; i++) { if (a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } cout<<"The numbers in adjusted order"<<endl; for (i=0;i<6;i++) cout<<a[i]<<endl; return 0; 冒泡排序部分

55 数组的应用2 编程技巧：尝试多种方法 基数排序的复杂度中，r代表关键字的基数，d代表长度，n代表关键字的个数 类别 排序方法 时间复杂度
空间复杂度 稳定性 交换排序 冒泡排序 O(n2) O(1) 稳定 快速排序 O(nlog2n) 不稳定 插入排序 直接插入 Shell排序 O(n13) 选择排序 直接选择 堆排序 归并排序 O(n) 基数排序 O(d(r+n)) O(rd+n) 编程技巧：尝试多种方法 基数排序的复杂度中，r代表关键字的基数，d代表长度，n代表关键字的个数

56 例 以下程序用于从键盘上输入若干个学生的成绩，统计出平均成绩，并输出低于平均成绩的学生成绩。输入负数结束 cin>>a
void main() { float x[100],sum=0, ave,a; int n=0,i; cout<<“Input score\n”; _________; while(__________) { x[n]=a; _______; _________ cin>>a; } ave=sum/n; cout<<“ave=“<<ave<<endl; for( i=0; _____;i++) if(__________) cout<<“x[“<<i<<“]=”<<x[i]<<endl; i<n cin>>a x[i]<ave a>=0 sum+=a n++

57 思考题： 在有序数组中插入一个数 例如：3 5 7 12 18 将b=10插入 3 5 7 12 18 a[0] a[1] a[2]
例如： 将b=10插入 (1) 3 5 7 12 18 a[0] a[1] a[2] a[3] a[4] a[5] (2) 3 5 7 12 10 a[0] a[1] a[2] a[3] a[4] a[5] (3) 3 5 7 10 12 a[0] a[1] a[2] a[3] a[4] a[5] 10 18 18 网络课程平台

58 总结： 数组的应用 票数统计 冒泡排序 编程的技巧 先具体再一般 寻找重复步骤 抓住问题的关键 尝试多种方法 关键在实践探索

59 作业 题目1: 题目2: 运用数组编写一个C++程序,计算两个矩阵的乘积,具体 要求为:
输入4*3的二维数组A和3*4的二维矩阵B, 按照两个矩阵相乘的 法则,计算乘积矩阵C, 在屏幕上按照标准4*4矩阵的排列方式显 示出来 题目2: 参照例程, 运用指针变量编写一个C++程序,实现下列两 项功能: 输入字符串A和B,使B接在A后面,形成一个字符串输出(即实现 strcat函数的功能) 输入字符串C和字符d,查找字符串C中第一个与字符d相同字符的 索引(即实现strchr函数的功能)