第5讲数组.pdf

《第5讲数组.pdf》由会员分享，可在线阅读，更多相关《第5讲数组.pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第 1 页 第五讲 数组 5.1 数组概述(P131)编写程序的目的是处理数据,前面我们已经提到,描述程序要处理的数据是程序设计很重要的一个方面。由程序处理的数据可能很简单,也可能很复杂,为了描述各种各样不同的数据,要求语言系统有足够的数据表示能力。和大多数高级语言一样,C语言也采用了下面的数据机制：把语言要处理的数据对象划分为一些类型,每个类型是一个数据值的集合。提供一组基本数据类型,确定书写方式和一组相关基本操作,以支持程序中对基本数据对象的表示和使用。提供一组由简单数据类型、数据对象构造更加复杂的数据类型、数据对象的手段,以满足程序中处理复杂数据的要求。数组是 C 语言对一组相同性质数据

2、的顺序存储管理机制；利用数组可把多个具有相同类型的数据对象组合在一起并作为一个整体来管理,这些数据对象称为数组的元素。C 语言中用 a0、a1 的形式表示数组元素,方括号内的整型数称为数组的下标。使用下标和数组名可以用同一方式处理一批或所有数组元素,也可处理个别元素。数组是最简单的构造类型,但是十分有用,许多问题不用数组几乎难以解决。本章介绍一维和二维数组的定义、数组元素引用、字符数组。字符串和数组应用的基本算法。数组是构造数据类型之一 数组:有序数据的集合,用数组名标识 元素:属同一数据类型,用数组名和下标确定 5.2 一维数组 一、一维数组的定义 1、什么是一维数组 数组的维数是指数组使用

3、的下标个数,如果数组中每个元素只带有一个下标,称为一维数组。2、一维数组的定义形式 类型说明符 数组名 常量表达式；3、说明 类型说明符指出数组元素的数据类型;数组名是标识符;常量表达式必须用方括号括起来,指的是数组的元素个数(长度),它是一个整型值,其中可包含常数和符号常量 。第 2 页 不能用变量定义数组维数,例:int n=10;int an;C 语言规定,数组变量的大小是固定不变的,因此需要在定义时规定元素类型和元素个数。普通变量可以在一个定义语句中定义多个数组,和其他。例如：int a10，b5，c；二、一维数组的存储 1、意义：掌握一维数组在内存中的存储形式,有利于理解数组机制和数

4、组元素的性质。2、存储：系统定义数组时,根据定义语句中的空间需求分配足够的连续存储空间,数组元素顺序存放在这些存储单元中。下标为 0 的元素排在最前面,每个元素占据的存储空间完全相同。3、数组空间开销计算-有两种计算方法。存储容量=元素个数sizeof(元素类型名)存储容量=sizeof(数组名)4、数组名的本质：是数据组的内存起始地址。可以把数组名看作是一个表示存储地址的常量。例如:如果 a 是已有定义的整型数组名,scanf(%d,a);将读入的一个整型数赋给 a 所表示的存储单元,该整型数正好是数组 a 的第一个数组元素的地址。(不能用 scanf(%d,&a);三、一维数组的引用 1、

5、数组元素表示形式：数组名 下标 其中：下标可以是常量或整型表达式 2、说明 数组必须先定义，后使用 只能逐个引用数组元素,不能整体引用 下标是元素相对于数组起始地址的偏移量，所以从 0(下界)开始顺序编号。最后一个元素的下标(上界)值为数组元素个数减一。注意:元素的下标和元素在数组中的序号的关系,如 Ai 表示数组 A 的第 i+1 个元素。注意:C 语言系统并不自动检查数组的下标是否越界，对下标的控制由编称者完成。例:int data5;data5=10;引用数组元素的本质是将数组元素看作简单变量。数组元素可以作为定义类型的变量参加表达式计算和变量操作(引用和赋值)。只能逐个引用数组元素,不

6、能整体引用。四、一维数组初始化 1、概念：在定义数组时,为数组元素赋初值 (在编译阶段使之得到初值)int a6=1,2,3,4,5,6;等价于：a0=1;a1=2;a2=3;a3=4;a4=5;a5=6;第 3 页 2、说明 存储在动态存储区中的(局部)数组不初始化,其元素值为随机数 存储在静态存储区中(static、全局)数组元素不赋初值,系统会自动赋以 0 值 static int a6 等价于：a0=0;a1=0;a2=0;a3=0;a4=0;a5=0;可以只给部分数组元素赋初值 int a6=1,2 等价于：a0=1;a1=2;a2=0;a3=0;a4=0;a5=0;int a3=1

7、,2,3,4 /错误的 全部数组元素赋初值时,可不指定数组长度 int a=1,2,3,4,5,6 五、一维数组实例【例 5.1】用数组处理 fibonacci数列问题。#include void main()int i;int f20=1,1;for(i=2;i20;i+)fi=fi-2+fi-1;for(i=0;i20;i+)if(i%5=0)printf(n);printf(%12d,fi);printf(n);getch();【例 5.2】求一组成绩的平均分数,设给定的数据是 87,90,85,98,65,80,74,67。分析：考虑用数组表示这组成绩,虽然给出的数据全是整数值,但考虑

8、作为成绩及可能需要进行的运算,使用实型数更合适。本例使用数组定义时初始化的方式来表示要计算的数据,其次,为增加程序的通用性,考虑让程序自动判断数据值的个数,用于循环结束的控制条件。程序：#include main()int i,num;float score =87,90,85,98,65,80,74,67 第 4 页 float sum=0.0;num=sizeof(score)/sizeof(float);for(i=0;inum;i+)sum+=scorei;printf(Average:%.1f n,sum/num);运行结果：Average:80.8【例 5.3】编写程序。将前 15

9、 个奇数按每行 5 个的格式正序和反序输出。分析：本例用循环结构控制数组的方法顺序或逆序地逐个引用数组元素的操作,实现换行动作的控制。程序：#include#define M 15 main()int i,k=1,aM;for(i=0;iM;i+,k+=2)ai=k;printf(Sequence Output:n);for(i=0;i0;i-)printf(%4d,ai);if(i%5=0)printf(n);运行结果：Sequence Output:1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Invert Output:29 27 25 23 21 19

10、 17 15 13 11 9 7 5 3 1【例 5.4】编写程序，输入一组整数，将它们排序后由小到大输出。分析：我们使用大家熟悉的冒泡方法来完成排序的操作。它的思路很简单,将相邻两个数组元素进行比较，将小的调整到前面。排序过程：比较第一个数与第二个数,若为逆序 a0a1,则交换；然后比较第二个数与第三个数；依次类推，直至第 n-1个数和第 n个数比较为止第 5 页 第一趟冒泡排序,结果最大的数被安置在最后一个元素位置上 对前 n-1 个数进行第二趟冒泡排序,结果使次大的数被安置在 第 n-1个元素位置 重复上述过程,经 n-1趟冒泡排序后,排序结束 算法举例：对以下序列进行冒泡排序（23、7

11、7、14、89、06、68、23、14、77、06、68）程序：#include main()int a50,num,i,j,t,change=1;printf(n Enter Numbers:);scanf(%d,&num);printf(n Enter Date:);for(i=0;i 0&change;i-)change=0;for(j=1;j aj+1)t=aj;aj=aj+1;aj+1=t;change=1;printf(n Sorted Date:);for(i=0;inum;i+)printf(%d,ai);运行结果：Enter Numbers:6 Enter Date:23 7

12、7 14 89 6 68 Sorted Date:6 14 23 68 77 89 5.3 二维数组(P135)一、二维数组的定义 1、什么是二维数组 如果数组中每个元素带有两个下标，称这样的数组为二维数组。2、二维数组的定义形式 类型说明符 数组名 常量表达式 1常量表达式 2;3、说明 定义中除了使用两个方括号和常量表达式外,与一维数组的要求相同。可把二维数组看成是一个矩阵,常量表达式 1 表示矩阵的行数,常量表达式 2 表示列数。可把二维数组看作一种特殊的一维数组,它的元素又是一维数组。即二维数组是数组的数组。例如 int a34;定义了一个二维数组 a,数组元素是整型数,数第 6 页

13、组有 12(34)个元素,可以看成为 3 行 4 列的矩阵。同时,可以把 a 看作是一个一维数组,它有 3 个元素,名字为 a0、a1、a2,每个元素又是一个包含 4 个元素一维数组：a0:a00,a01,a02,a03 a1:a10,a11,a12,a13 a2:a20,a21,a22,a23 多维数组的实现以二维数组为基础,如把三维数组定义成元素是二维数组的数组。下例定义了一个三维数组：float a234，其元素是两个二维数组,a0 是一个 3 行 4 列的二维数组，a1 也是一个同样的二维数组。二、二维数组的存储 1、存储：二维数组在内存中占据一系列连续的存储单元,数组元素按行顺序存放

14、,先放行下标是 0 的元素，再放行下标是 1 的元素,依此类推。数组 a24 的存储示意图 a00 a01 a02 a03 a10 a11 a12 a13 行下标为 0 的元素 行下标为 1 的元素 2、原因:内存是一维的。三、二维数组的引用 1、数组元素表示形式：数组名 下标1下标2 其中：下标可以是常量或整型表达式 2、说明 每个下标的值不能超越该下标的上界和下界,数组元素可以出现在表达式中,也可以被赋值。对基本数据类型的变量所能进行的操作,也都适合于相同数据类型的 2 维数组元素。不论是一维数组还是二维数组，都要注意数组引用和数组定义表示形式的区别。如定义中出现的 a34 表示数组的维数

15、和各维数的大小,引用时 a34 的 3 和 4 是下标,a34 代表一个数组元素。四、二维数组的初始化 1、作用：二维数组定义时也可以用花括号对全部或前面一部分数组元素进行初始化。通过初始化可以定义二维数组。2、初始化形式 分行初始化 按元素排列顺序初始化 第一维长度省略初始化 3、初始化的原则 分清每行元素的个数和行数，没有赋值的元素初值为 0。五、二维数组实例【例 5.6】通过键盘给 34 的二维数组输入数据,然后分别按行和按列输出数组元素。分析：遍历二维数组的每一个元素经常使用双重循环,本例演示了二维第 7 页 数组的基本输入输出控制方法。程序：#include main()int a3

16、4,i,j;printf(Enter data by line:n);for(i=0;i3;i+)for(j=0;j 4;j+)scanf(%d,&aij);printf(Output by line:n);for(i=0;i3;i+)for(j=0;j 4;j+)printf(%5d,aij);printf(n)printf(Output by column:n);for(i=0;i4;i+)for(j=0;j 3;j+)printf(%5d,aji);printf(n)运行结果：Enter data by line:1 2 3 4 5 6 7 8 9 10 11 12 Output by

17、line:1 2 3 4 5 6 7 8 9 10 11 12 Output by column:1 5 9 2 6 10 3 7 11 4 8 12 5.4 字符数组和字符串 一、字符数组 1、定义：元素数据类型是字符类型的一维数组。例如:char str50；定义了一个有 50 个字符元素的数组 2、字符数组的初始化：方法都与一维数组相同 3、字符数组的引用：字符数组的逐个字符引用，与引用数值数组元素类似。实例：第 8 页 省略数组元素个数 char s =1,2,3,4,5;逐个字符赋值 char c5=H,e,l,l,o;部分字符赋值 char s5=1,2;二、字符串 1、定义：用双

18、引号括起来的任意字符序列。可以包括字母、数字、专用字符、转义字符等。2、存储：无字符串变量,用字符数组连续、顺序存放每一个字符，最后加字符 0 做结束标志。3、结束标志：0 代表 ASCII 码为 0 的字符,表示一个“空操作”,只起一个标志作用。因此可以对字符数组采用另一种方式进行操作了 字符数组的整体操作。例：char str =China；char str =China；定义数组 str 的长度是 6 个字符 char str10=China；str 的前 6 个字符初始化,其他赋 0 char str5morning;用于初始化的数据多于数组的定义，编译出错 4、用字符数组处理字符串应

19、考虑以下问题 定义变量时,可能存储的最长字符串的长度。对字符数组初值赋值方法的扩充问题 三、字符串数组 1、定义：字符串数组就是数组中的每一个元素都是存放字符串的数组。2、存储：利用 C 语言数组构造的特点,二维数组可以看作是一个一维数组,这个一维数组的元素又是一个一维数组。因此,可以将一个二维字符数组看作一个字符串数组。例如，字符串数组 line1080 共有 10 个元素,每个元素可以存放 80 个字符(包括0)例：char str35=a,ab,abc；char str 5=a,ab,abc；3、引用：可以通过二维数组元素的形式引用其中的字符。如:str11 0 c b a str2 0

20、 b a str1 0 a str0 第 9 页 的值是 b。4、符串数组的初始化方法 四、字符数组和字符串实例【例 5.9】编写函数 strcopy(s1,s2)，完成字符串的复制操作。#include void strcopy(char s1,char s2)main()char str120,str26=China;strcopy(s1,s2)puts(s1);void strcopy(char s1,char s2)int i=0 while(s1i!=0)s1i=s2i;i+;s1i=0;程序可进一步修改为：void strcopy(char s1,char s2)int i=0 w

21、hile(s1i=s2i)i+;五、字符串函数 1、概述：字符与字符串是 C 程序处理的重要对象,C 标准函数库中提供了许多相关的函数,它们的原型说明在下面头文件中:ctype.h 说明了一组字符类型判断函数 string.h 说明了许多字符串处理函数 stdio.h 说明了用于字符串 I/O 函数 2、常用的字符串函数（1）字符串输入输出函数(头文件:stdio.h)scanf printf gets puts（2）字符串处理函数(头文件:string.h)strcpy strcat strlen strcmp 3.字符判断函数(头文件:ctype.h)is(1)字符串输入输出 Scanf

22、的 s 格式串可以实现字符串的整体输入 例如：char str20；scanf(%s,str);/*str 是地址*/说明：输入字符依次放入以 str 为起点的存储单元,并自动在末尾加 0。遇到空格、回车和制表符都作为输入数据分隔符而不能被输入。输入字符串的长度不能超过字符数组所能容纳的字符个数。输入项可以是字符串的起始地址,也可以是字符数组元素的地址,第 10 页 将从此地址表示的单元开始输人数据。如 scanf(%s,&str5);。printf 的 s 格式串可以实现字符串的输出 例如：char str20；printf(%s,str);/*str 是地址*/说明：调用 printf 时

23、,将从 str 表示的地址开始输出存储单元中的字符,直到遇到第一个 0 为止。str 也可以是字符数组元素的地址。字符数组操作的关键是理解数组名的地址属性,系统将数组名解释为地址常量,可以引用它定位数组的存储单元,但不能对数组名赋值。gets 用于从终端输入字符串 形式为：gets(str);说明：gets 用来从终端键盘读入字符串(包括空格),直到读入一个换行符为止。换行符不作为字符串的内容,系统自动加 0。str是存放字符串的起始地址。可以是字符数组名、字符数组元素地址或第 7 章将要介绍的字符指针。例如：gets(str);执行时键入以 good morning!,将读入该串并 用 0

24、替代最后的换行符。puts 用于从终端输出字符串 形式为：puts(str);说明：str是输出字符串的起始地址,从这一地址开始,依次输出存储单元中的字符,直到遇到第一个0 为止,并自动输出一个换行符。(2)字符串处理函数 字符串复制函数 strcpy 调用形式:strcpy(s1,s2);说明：s2 可以是字符数组名或字符串常量,s1 是字符数组名 函数把字符串 s1 复制到 s2 所指向的存储空间中,并返回 s1 的值,s1 指向的存储空间必须足够容纳 s2。复制时连同结束符一起复制。例如：char str10;strcpy(str,China);将常量字符串China 复制到字符数组 s

25、tr 中 c h i n a 0 注意：不能用赋值语句将一个字符串常量或者字符数组直接给一个字符数组。例如：Str1=“china”;/错误 第 11 页 Str1=str2;/错误 字符串连接函数 strcat 调用形式:strcat(s1,s2);说明：函数把字符串 s2 接到字符串 s1 的后面,自动覆盖 s1 后面的结束符,返回 s1。数组 s1 的空间必须足够容纳连接后字符串。例如：char str20,s210;strcpy(s1,like);strcpy(s2,school);stcat(s1,s2)s1:l i k e s c h o o l 0 字符串长度函数 strlen

26、调用形式:strlen(s);说明：函数用于计算并返回字符串 s 的长度,不包括末尾的结束符0。例如：执行 strcpy(str,China);strlen(str)的值是 5。字符串比较函数 strcmp 调用形式:strcmp(s1,s2);说明：函数用于比较字符串 s1 和 s2:如果 s1=s2,函数值返回 0；s1 s2,函数值返回正数；s1 s2,函数值返回负数。C 语言中,字符串比较以字符比较为基础,字符比较等价于比较字符的 ASCll 编码。有三种结果：等于、小于、大于。如比较字符 c1 和 c2,如果 c1=c2 为真,结果为 0；如果。c1 c2 为真,结果为正数；c1 c

27、2 为真,结果为负数。字符串比较规则：自左向右逐个字符比较，直到出现不同的字符或遇到 0 为止。如全部字符相同,则两字符串相等；若出现不同字符,则以第一个不同字符的比较结果为准。比较的结果由函数带回。因此，如果两个字符串相等,则它们不仅长度相同,而且对应位置的字符也相等。3.字符判断函数 字符判断函数大部分是用宏实现的。返回值都是真值和假值,即非 0 和 0。如:isalpha(c)判断 c 是否为字母；isdigit(c)判断 c 是否为数字；isupper(c)判断 c 是否为大写字母。第 12 页 合理地使用字符判断函数,可以改善程序的可移植性和可读性,比如程序中我们需要判断字符变量。是

28、否为数字字符,可以这样实现：if(c=48&c=0&c=9)要求使用的编码方案中数字字符的编码连续。若用：if(isdigit(c)则程序与具体系统完全无关,在任何一个系统上运行都不需要进行修改。程序的可读性也通过函数调用得到改善。5.6 数组应用实例 一、数学问题【例 5.10】将字符串转换成等值的机内数。体会 C 系统字面量到机内表示的转换过程。将无符号八进制数串转换成十进制机内数。如：0556 366。分析：根据变换 556=5 8 85 86 =(5 8 5)8 6 得出计算中有一个累加过程,转换方法是:从高位起,累加值=累加值8 本位值。用一维数组表示八进制数串。程序如下：#incl

29、ude main()int i,n;char s8;gets(s);i=0;n=0;while(si!=0)n=n*8+si-0;i+;printf(%d n,n);【例 5.11】将十进制数转换成八进制数串。方法：反复除8 求余数,将余数从右向左排列 程序如下：#include main()int i=0,d,m,n;char s8;scanf(%d,%n);do m=n/8;d=n%8;si=0+d;第 13 页 n=m;i+;while(n!=0);for (i-;i=0;i-)putchar(si);二、排序和查找【例 5.12】用选择法排序。方法：设有 n 个元素,a0,a1,an-

30、1 第一次,从 a0 an-1 中选出最小的元素 amin,将 a0 与 amin 交换，在 a0 中得到最小元素；第二次,从 a1 an-1 中选出最小的元素 amin,将 a1 与 amin 交换，在 a1 中得到次小元素；依次类推。执行 n-1 次选择和交换后，将会得到有序数组。程序如下：#include main()int i,j,n,temp,min,a50;printf(Enter Num:);scanf(%d,&n);printf(Enter data:n);for(i=0;i=n-1;i+)scanf(%d,&ai);printf(The date is:n);for(i=0;

31、i=n-1;i+)printf(%5d,ai);for(i=0;i=n-1;i+)min=i;for(j=i+1;j aj)min=j;if(i!=min)temp=ai;ai=amin;amin=temp;printf(nAfter sorted,the data is:n);for(i=0;i 0;i-)if (ai-1 in)ai=ai-1;/元素往后移动 else break;ai=in;/插入元素 in，插入位置为 i 【例 5.14】设有一个整型数 key，在有序数组 array 中，找到与 key 相等的数,打印下标,找不到则打印信息。中心语句如下：for (i=0;arrayi

32、!=key∈i+);其余程序请读者自己完成,注意循环结束时 i 的值与查找结果的关系。以上三个例子是对线性表的排序、插入和修改的操作过程。三、字符串和字符数组的应用【例 5.15】输入一行字符，统计其中共有多少单词，单词之间用空格分隔开。程序如下：#include void main()char string50,c;int i,num=0,word=0;gets(string);for(i=0;(c=stringi)!=0;i+)if(c=)word=0;else if(word=0)word=1;num+;printf(There are%d words in the line.n,

33、num);【例 5.16】字符串查找的实现(术语叫模式匹配)问题：从字符串对 str 中查找子串 s,找到则报告第一个字符的位第 15 页 置;找不到,打印信息。分析：从 str 的第一个字符开始,比较从此字符开始的字符串是否与合相同,如果相同,则匹配成功，返回这个字符的位置,如果不同,从 str 的下一个字符开始继续这个过程,如果 str 中没有与 s 相同的子串,匹配失败。程序如下：#include main()char str,s10;int re=0,i=0,j;/re为匹配的位置 printf(Enter main str:);gets(str);printf(Enter sub str:);gets(s);while(i=strlen(str)-strlen(s)for(j=0;jstrlen(s);j+)if (stri+j!=sj)i+;break;if (j=strlen(s)re=i;break;/匹配成功，结束循环 if(re)printf(Result:%dn,re);else printf(“Cant find the sub string!n”);