CH5《数组和字符串》.ppt

《CH5《数组和字符串》.ppt》由会员分享，可在线阅读，更多相关《CH5《数组和字符串》.ppt（73页珍藏版）》请在三一文库上搜索。

1、五、数组和字符串,例：求5名学生某门功课的平均成绩. main ( ) float s1, s2, s3, s4, s5, avg; printf ( “Enter the 5 scores :“); scanf(“%f%f%f%f%f“, , 数组是按序排列的同类型变量的集合，是一组具有 相同名字, 不同下标的下标变量。 下标变量形式 数组名下标 如 s0、s2、s3、s6、s10 数组名表示整个数组，如：s 下标变量又称数组元素 下标指出某个数组元素在数组中的位置 下标可以用常量表示，也可以用变量表示 有1个下标的下标变量所组成的数组称为一维数组； 有2个下标的下标变量所组成的数组称为二维

2、数组； 如：x1、y5 数组x和y都是一维数组 a12、b23 数组a和b都是二维数组,使用数组，上例程序可改写为： main ( ) float s5, avg=0; int i; for (i = 0; i 5; i+) scanf (“%f“, ,5.1 一维数组 5.1.1 一维数组的定义和引用,1. 一维数组的定义 定义形式： 数据类型 数组名常量表达式; 如： int a10; 数据类型 说明该数组中每个元素的数据类型 数组名 数组的名称，命名规则同变量名 常量表达式 表示该数组具有的元素个数， 也称为数组的长度。 说明： 数组中的第一个元素的下标从0开始。, 数组名 ( 如 a

3、) 表示该数组中第一个元素 ( 如 a0 ) 的地址，即a和,2. 一维数组元素的引用 数组不能以整体形式参加数据处理，参加数据处 理的只能是数组元素。数组元素的引用方法有两种： 下标法 引用的一般形式为：数组名下标 其中的下标为整型常量或整型表达式，可以包含 变量，它表示了元素在数组中的顺序号即位置 指针法（第7章中介绍） 【例5.1】输入学生数n（不大于50）及n个学生某门 课程的成绩，计算并输出平均成绩（保留1位小数） 和高于平均成绩的人数。,main( ) int i, n, count, score50; float avg; printf(“Input the student th

4、e number:n“); scanf(“%d“, ,例2：输入一行字符, 以回车表示结束。问输入各数 码的个数。 # include main ( ) char s80, c; int i, nd10; for ( i=0; i=0 ,5.1.2 一维数组的初始化,数组初始化 是在定义数组时对数组元素赋予初值。 一般形式为： 类型说明符 数组名常量表达式=值1,值2,值n； 中的各值为将依次赋予各对应元素的初值，必须 是常量或常量表达式，且类型应与数组的类型一致 int a10=2, 4, 6, 8, 10, 12, 14, 16, 18, 20; 用单个字符作为初值 char b5=C,h

5、,i,n,a;, 用字符串常量作为初值 char c6=“China“; 或 char c6=“China“; 注意：编译系统自动在字符串常量的最后加0 可以不指定数组长度 int a =0, 2, 4, 6, 8; 相当于 int a5=0, 2, 4, 6, 8; char c = “China“; 相当于 char c6= “China“; 允许只给部分元素赋初值 （其余元素初始化为0 ） int a80=0; char b10=C,h,i,n,a; 未指定初始化的数组，各元素的值是随机的未知值 但全局数组和静态数组则会自动初始化为0。,【例5.2】从键盘输入日期（yyyy-mm-dd）

6、，计算并 输出该日期那天是该年的第几天。 分析： 基本算法：将1月至m-1月的各月天数累加，再加 上给定的日d。 每月的天数可用一个一维数组存放，初始化为平 年的天数，然后再根据y年是否为闰年来修正2月 份的天数。 闰年的条件是符合下面两条件之一： 能被4整除，但不能被100整除； 能被400整除 ；,main( ) int a13=0,31,28,31,30,31,30,31,31,30,31,30,31; int y, m, d, i, days; do printf(“Input the date(yyyy-mm-dd):n“); scanf(“%d-%d-%d“, ,运行结果： Inp

7、ut the date(yyyy-mm-dd): 2004-9-12 256 另一种方法是不用数组来存放每月的天数和循 环结构累加各月天数，而是用switch结构直接给出 各月天数并实现累加。,main( ) /* 用switch结构 */ int y, m, d, days, m2=28; do printf(“Input the date(yyyy-mm-dd):n“); scanf(“%d-%d-%d“, ,case 8: days+=31; case 7: days+=31; case 6: days+=30; case 5: days+=31; case 4: days+=30; c

8、ase 3: days+=31; case 2: days +=m2; case 1: days +=31; printf (“n=%dn“, days); ,5.1.3 程序举例,【例5.3】输入10个整数，按从小到大的顺序输出。 这是一个数据排序问题。排序算法有很多种，下 面结合上述实例介绍3种常用的简单排序算法：冒泡 法、选择法和插入法。 1. 冒泡法 冒泡法排序的基本思想是：依次逐个比较相邻的 两个数，如不符合顺序要求，就交换这两个数的位 置。通过一轮比较，就能排定一个数的位置，对于n 个数，进行n-1轮比较即可完成排序, 冒泡法1：,从第n个数开始，依次比较相邻两个数，即第n个与 第

9、n-1个、第n-1个与第n-2个、，每次比较，若不 满足由小到大的顺序，则两者对调位置，通过一轮 比较，参加比较的数中的最小数就“上升”到它们中 最前面的位置，下一轮再把余下的数依次比较，这 样，通过n-1轮比较，就完成了全部n个数的升序排 列。在第i轮比较时，从第 1个位置开始已排序定位 了i-1个数，余下n-i+1个数，需两两比较 n-i次。,冒泡法1流程：,#define N 10 main ( ) int sN, i, j, t ; for ( i=0; i i; j- ) if ( sjsj-1 ) t = sj; sj = sj-1; sj-1 = t; for ( i=0; i

10、N; i+ ) printf (“%d “, si); /* 输出排序结果*/ printf(“n“); , 冒泡法2： 从第1个数开始，依次比较相邻两个数，即第1个与 第2个、第2个与第3个、 ，每次比较，若不满足 由小到大的顺序， 则两者对调位置， 通过一轮比 较，参加比较的数中的最大数就 “ 下沉 ” 到它们中 最后面的位置，下一轮再把余下的数依次比较，这 样，通过n-1轮比较，就完成了全部n个数的升序排 列。在第i轮比较时，从第 n个位置开始向前已排序 定位了i-1个数，余下n-i+1个数，需两两比较n-i次。,#define N 10 main ( ) int s10, i, j,

11、t ; for ( i=0; i sj+1) t = sj; sj = sj+1; sj+1 = t; for ( i=0; i N; i + ) /* 输出排序结果 */ printf (“%d%c“, si, i!=N-1 ? , : n); ,2. 选择法：,选择法排序的基本思想是： 通过比较找到最小数，如不是第1个数，则与第1 个数交换，再在余下的数中找到最小数，如不是第 2 个数，则与第 2 个数交换位置，再在余下的数中 找到最小数，如不是第 3 个数，则与第 3 个数交换 位置，依此进行，n 个数经过 n-1 轮比较即可完成 排序。,#define N 10 /* 每轮比较中：*/

12、 main() /* 最小数位置记入k，结束再与第i个对调*/ int sN, i, j, k, t; for ( i=0; isj) k=j; if(k!=i) t=si; si=sk; sk=t; for(i=0; iN; i+) printf(“%d%c“, si, i!=N-1?,: n); ,#define N 10 /* 每轮比较中： */ main() /* 遇到比第i个小的就与第i个对调*/ int sN, i, j, t; for ( i=0; isj) t=si; si=sj; sj=t; for(i=0; iN; i+) printf(“%d%c“, si, i!=N-1

13、?,: n); ,3. 插入法,插入法排序基本思想是：开始时第1个数已排好 序，首先将第2个数按其与前1个已排好序的数的顺 序关系插入到适当位置，然后将第3个数按其与前2 个已排好序的数的顺序关系插入到适当位置，接着 再将第4个数按其与前3个已排好序的数的顺序关系 插入到适当位置，依次进行下去，直到最后一个数 也按其与前面所有已排好序的数的顺序关系插入到 适当位置。对于n个数，经过n-1轮比较插入即可完 成排序。,main( ) int aN, i, j, k, t; for ( i=0; i =0 ,【例5.4】已知数组a中共有10个已按升序排序的整 数。现从键盘输入一数，请用二分法查找数组

14、a中是 否有此数，如有则打印出此数在数组中的位置，否 则打印找不到。 设：待查数在变量x中； 变量low 用于存放查找范围的顶部位置； 变量m 用于存放查找范围的中间位置； 变量high 用于存放查找范围的底部位置； 二分法的基本步骤： 赋初值：low=0，high9，计算m=(low+high)/2 这样把查找范围分成以am为中点的两段范围。, 判断lowam？ 如是，则x必定落在后半段。以后半段为新查找范 围，再划分两段范围：lowm+1，high不变， m=(low+high)/2。回到第步。 如不是，x必定落在前半段。以前半段为新查找范 围，再划分两段范围： low不变，highm-1

15、， m=(low+high)/2。回到第步。,main ( ) int low, high, m, x ; int a10= -54, -34, -8, 0, 3, 12, 25, 56, 68, 98 ; printf(“Please input x:“); scanf (“%d“, ,【例5.5】 n盏灯从1到n按顺序依次编号，有n个人也 从1到n依次编号，第一个人（1号）将灯全部关闭， 第二个人（2号）将凡是2和2的倍数号的灯打开，第 三个人（3号）将凡是3和3的倍数号的灯做相反处理 （即该灯如为打开的，将它关闭；如为关闭的，将 它打开）。以后的人都和3号一样，将凡是与自己相 同编号的灯

16、和是自己编号倍数的灯做相反处理。n （1n1000）从键盘输入，请问：当第n个人操作 之后，哪几盏灯是关闭的，输出其编号。,main() int a1000=0, n, i, j; /* 第1个人将灯全部关闭 */ scanf(“%d“, ,输入：100 输出：1 4 9 16 25 36 49 64 81 100,5.2 二维数组 5.2.1 二维数组的定义和引用,1. 二维数组的定义 定义形式： 数据类型 数组名常量表达式1 常量表达式2; 如： int a34; 定义a为34（三行四列）的数组, 各个元素皆是整 型量，具体是： a00 a01 a02 a03 a10 a11 a12 a1

17、3 a20 a21 a22 a23 在内存中按行存放。, 二维数组是一维数组的数组 可以把a看作含有a0、a1和a2共3个元素的一 维数组，而a0、a1和a2又都是含有4个元素的 一维数组，a0、a1和a2就是这3个一维数组的 名字，即： a0: a00 a01 a02 a03 a1: a10 a11 a12 a13 a2: a20 a21 a22 a23,2. 二维数组元素的引用 下标法 引用的一般形式为：数组名下标1 下标2 其中的下标1和下标2为整型常量或整型表达式， 可以包含变量，它们分别表示了元素在数组中的 行、列位置。例如： a12 - a 数组第2行第3列元素 a03 - a 数

18、组第1行第4列元素 指针法 （第7章中介绍）,【例5.6】编程计算并输出一个54的整数矩阵周边 各元之和，矩阵各元从键盘输入。 main( ) int a54, i, j, sum=0; for (i=0; i5; i +) /* 输入并计算矩阵各元之和 */ for (j=0; j4; j+) scanf(“%d“, ,5.2.2 二维数组的初始化, 按行分段给二维数组元素赋初值 int a34=8,4,2,1, 5,7,0,3,4,0,9,6; 按行连续给二维数组元素赋初值 int a34=8,4,2,1, 5,7,0,3, 4,0,9,6; 允许只给部分元素赋初值(其余元素初始化为0)

19、int a34=8,4, 5,4; int a34=8,4,2,1,5;, 用字符或字符串常量为初值给字符数组初始化 char s25=b,o,y,0,g,i,r,l,0; char s25=“boy“, “girl“; 当用按行分段方法给出了所有行，或者当用按行 连续方法给出全部数组元素初始化值时，可以省 略第一个下标的长度 char s5=“boy“, “girl“; int a4=8,4, 5,4; int a4= 8,4,2,1, 5,7,0,3, 4,0,9,6; 未指定初始化的数组，各元素的值是随机的未知 值。全局数组和静态数组则会自动初始化为0。,5.2.3 程序举例,【例5.7

20、】把整型矩阵A(2x3)转置成B(3x2)后输出， 矩阵A的各元从键盘输入。 矩阵转置的基本算法是：把原矩阵A的i行j列的元 素，转置成矩阵B的j行i列的元素。 main( ) int a23, b32, i, j; printf(“Please input A:n“); for (i=0; i2; i+) /* 输入矩阵A */ for (j=0; j3; j+) scanf(“%d“, ,for (i=0; i2; i+) /* 矩阵A转置成B */ for(j=0; j3; j+) bji=aij; printf(“Result B: n “); for (i=0; i3; i+) /*

21、 输出矩阵B */ for (j=0; j2; j+) printf(“%d “,bij); printf(“n“) ,运行结果： Please input A: 1 2 3 4 5 6 Result B: 1 4 2 5 3 6,【例5.8】 计算并输出整型矩阵 A(2x3) 和整型矩阵 B(3x4)的乘积，矩阵A和B的各元从键盘输入。 根据矩阵相乘规则，若有矩阵A和B，满足条件A 的列数等于B的行数，则可相乘得矩阵C。C的行数 和列数分别等于A的行数和B的列数。 设A为mn矩阵、B为np矩阵，则C为mp矩阵， 且其元素的数学表达式为：,i=0,m-1 j=0,p-1,#define M 2

22、 #define N 3 #define P 4 main() int aMN, bNP, cMP, i, j, k; printf(“Please input A:n“); for(i=0; iM; i+) /* 输入矩阵A */ for(j=0; jN; j+) scanf(“%d“, ,for(i=0; iM; i+) /* 计算 C */ for(j=0; jP; j+) cij=0; for(k=0; kN; k+) cij+=aik*bkj; printf(“Result C:“); for(i=0; iM; i+) /* 输出C */ printf(“n“); for(j=0;

23、jP; j+) printf(“%5dt“, cij); ,运行结果： Please input A: 1 2 3 4 5 6 Please input B: 11 12 13 14 21 22 23 24 31 32 33 34 Result C: 146 152 158 164 335 350 365 380,5.3 字符串处理 5.3.1 字符数组与字符串, 字符串常量 字符串常量是用双引号括起来的一串字符 字符数组 语言中没有专门的字符串变量，通常是用字符 数组来存放字符串。 一个一维字符数组可存放一个字符串 一个二维字符数组则可看成多个一维字符数组的 组合，即每行可存放一个字符串。,

24、 字符串结束标志0 字符串常量尾部自动含有一个结束符0 用字符串常量初始化字符数组会自动加结束符 0 ，用字符常量初始化字符数组则不会，如： char c=“Hello!“, s=H, e, l, l, o, !, 0 ; 进行字符串处理时，就可以通过检测0来判定 字符串是否结束 字符串长度指的是字符串本身字符的个数，并 不把字符串结束符0计算在内,5.3.2 字符串的输入和输出,1. 逐个字符输入输出 用scanf()和printf()函数的“c”格式符 【例5.10】使用scanf()和printf()函数的“c“格式 符，从键盘输入一字符串，然后输出该字符串。,#include “std

25、io.h“ main( ) char a81; int i; for (i=0; i81; i+) scanf (“%c“, ,运行结果： This is a string. This is a string., 用getchar()和putchar ()函数 【例5.11】使用getchar()和putchar ()函数，从键盘 输入一字符串，然后输出该字符串。 #include “stdio.h“ main( ) char a81; int i=0; while (ai+=getchar()!=n); a-i=0; i=0; while (putchar(ai+)!=0); putchar

26、(n); ,运行结果： This is a string. This is a string.,2. 字符串整体输入和输出 用scanf()和printf()函数的“s”格式符 【例5.12】使用 scanf() 和 printf() 函数的“s”格式 符，从键盘输入一字符串，然后输出该字符串。 main ( ) char c15; scanf (“%s“, c); printf (“%sn“, c); 注意：输入字符串中的空格作为分隔符，空格后的 字符被丢失。,运行结果： worker. worker. I am a worker. I, 用gets()和puts()函数 字符串输入函数ge

27、ts() 原型：char *gets(char *str); 功能：从标准输入设备键盘上输入一个字符串， 按回车键结束，存入起始地址为str的内存中，自 动加结束符0，并返回该字符串首地址。 字符串输出函数puts() 原型：int puts(char *str); 功能：把str指向的字符串输出到标准输出设备显 示器，并添加换行符n，如输出成功，则返回所 输出的最后一个字符，否则返回EOF值，即-1。, gets( )和 puts( )函数包含在stdio.h头文件中，考虑 到其使用频繁，系统允许在使用这两个函数时可 不加编译预处理命令：#include “stdio.h“ 【例5.13】使

28、用gets()和puts()函数，从键盘输入一 字符串，然后输出该字符串。 main( ) char a81; puts(“Input a string:“); gets(a); puts(a); ,运行结果： Input a string: This is a string. This is a string.,5.3.3 字符串处理函数,标准C函数库中提供有许多字符串处理函数，下 面介绍几个最常用的字符串处理函数，这些函数原 型都包含在头文件“string.h“ 中。 1. 字符串长度函数strlen() 原型：int strlen(char *str) 功能：计算字符指针str所指向的字

29、符串的长度 （不含字符串结束标志0） ，返回长度值,2. 字符串拷贝函数strcpy() 原型：char *strcpy(char *str1, char *str2) 功能：把str2指向的字符串拷贝到str1指向的目标 中去，返回目标字符串的指针str1 3. 字符串比较函数strcmp() 格式：int strcmp(char *str1, char *str2) 功能：比较str1和str2分别指向的两个字符串： 字符串str1字符串str2，则返回值0,4. 字符串连接函数strcat() 格式：char *strcat(char *str1, char *str2) 功能：把字符数

30、串str2连接到字符串str1的后面， 并删去原字符串str1后的结束标志0。返 回字符串str1的首地址。 【例5.14】从键盘输入两个字符串，将这两个字符 串连接合并成一新字符串，两个字符串间要加入减 号字符-，然后输出该新字符串。连接合并的规则 是：如果两者长度不相等，则短者在前，长者在后； 否则再比较两者的大小，小者在前，大者在后。如 果两者完全相同，则前后随意。,#include “stdio.h“ #include “string.h“ main( ) char s181, s281, s3200; int first=1; /* first初始化为字符串s1在前 */ gets(

31、s1); /* 输入字符串s1*/ gets(s2); /* 输入字符串s2 */ if (strlen(s1) strlen(s2) /* 如果s2短,则标识s2在前 */ first=2; else if(strlen(s1)=strlen(s2) /* 如果长度相等且s2小,则标识s2在前 */,if (first=1) /* 按first的标识，将s1和s2连接合并成s3 */ strcpy(s3, s1); strcat(s3,“-“); strcat(s3, s2); else strcpy(s3, s2); strcat(s3, “-“); strcat(s3, s1); put

32、s(s3); /* 输出s1和s2连接合并成的字符串s3 */ ,5.3.4 程序举例,【例5.15】从键盘输入一个字符串（不多于80个字 符），将其中的数字字符按原顺序组成一个新字符 串，将其中的英文字母都用大写按原顺序组成另一 个新字符串，再输出这两个新字符串，每个一行。 如原串中没有数字字符或没有英文字母，也要报告 “There are no digits.“或“There are no letters.“。,#include “stdio.h“ main( ) char s81, sa81=0, sn81=0; int i, j, k; printf(“Input a string:n

33、“); gets(s); for (i=j=k=0; si; i+) if (si=0,if (j=0) puts(“There are no digits.“); else puts(sn); if(k=0) puts(“There are no letters.“); else puts(sa); ,运行结果： Input a string: as78 As#a832h ASASAH 78832,【例5.16】从键盘输入一行字符，请分别统计其中 各英文字母出现的次数，统计时不区分大小写，然 后对至少出现过一次的字母，按字母顺序依次输出 其出现的次数，每个字母的输出样式为：大写的该 字母出现

34、次数，各字母间用空格隔开。 分析： 主要是考虑在有相当数量的统计对象时如何计数。 一种可普遍适用的方法是：使用两个数组，其中 一个字符数组存放要统计的字符对象，另一个整型 数组与之对应位置即相同下标的元素作为统计该字 符出现次数的计数器。,另一种方法是：利用英文字母的ASCII码逐一递 增的特点，用一个长度为26的整型数组的各元素 依次作为各字母的出现次数的计数器，因为大写 字母-A和小写字母-a的值正好就是用于该字母计 数的数组元素的下标。,main( ) /* 方法1 */ char a81, letter26=0, tc; int i, j, k, count26=0, tn; gets

35、(a); for (i=0; ai!=0; i+) /* 统计 */ tc=ai; if (tc=a ,for (i=0; letteri+1!=0; i+) /* 选择法排序 */ for (k=i, j=i+1; letterj!=0; j+) if (letterkletterj) k=j; if (k!=i) tc=letterk; letterk=letteri; letteri=tc; tn=countk; countk=counti; counti=tn; for (i=0; letteri!=0; i+) /* 输出 */ printf(“%c=%d “, letteri, c

36、ounti); printf(“n“); ,main( ) /* 方法2 */ char a81; int i, count26=0; printf(“Input a string:n“); gets(a); for (i=0; ai!=0; i+) /* 统计 */ if (ai=A ,for (i=0; i0) printf(“%c=%d “, A+i, counti); printf(“n“); 运行结果： Input a string: Gain new knowledge by reviewing old. A=1 B=1 D=2 E=5 G=3 I=3 K=1 L=2 N=4 O=

37、2 R=1 V=1 W=3 Y=1,【例5.17】从键盘输入一个字符串（不多于80个字 符），将其逆序存放后输出。 #include “stdio.h“ #include “string.h“ main( ) char s81, t; int i, j; printf(“Input a string:n“); gets(s); for (i=0, j=strlen(s)-1; ij; i+, j-) t=si; si=sj; sj=t; puts(s); ,运行结果： Input a string: How are you? ?uoy era woH,【例5.18】输入若干（不多于10）个字符

38、串，每个 字符串长度不超过80个字符，输入空字符串表示输 入结束，然后按从小到大的顺序输出这些字符串 （不包括表示输入结束的空字符串）。 #include “stdio.h“ #include “string.h“ main( ) char a1181, t81; int i, j, k, n;,for (n=0; n0) k=j; if (k!=i) strcpy(t,ai); strcpy(ai,ak); strcpy(ak,t); for (i=0; in; i+) /* 按从小到大顺序输出各字符串 */ puts(ai); ,运行结果： Shanghai Beijing Xiangga

39、ng Tianjin Chongqing Beijing Chongqing Shanghai Tianjin Xianggang,本章结束,5个元素的冒泡法排序过程示意图,j =4; ji; j- i=0 4 8 3 6 1 -2 3 8 3 6 -2 1 2 8 3 -2 6 1 1 8 -2 3 6 1 -2 8 3 6 1 j =4; ji; j- i=1 4 -2 8 3 6 1 3 -2 8 3 1 6 2 -2 8 1 3 6 -2 1 8 3 6,j =4; ji; j- i=2 4 -2 1 8 3 6 3 -2 1 8 3 6 -2 1 3 8 6,j =4; ji; j-

40、 i=3 4 -2 1 3 8 6 -2 1 3 6 8,5个元素的选择法排序过程示意图,j=i+1; j5; j+ i=0 1 8 3 6 1 -2 2 3 8 6 1 -2 3 3 8 6 1 -2 4 1 8 6 3 -2 -2 8 6 3 1 j= i+1; j5; j+ i=1 2 -2 8 6 3 1 3 -2 6 8 3 1 4 -2 3 8 6 1 -2 1 8 6 3,j=i+1; j5; j+ i=2 3 -2 1 8 6 3 4 -2 1 6 8 3 -2 1 3 8 6,j=i+1; j5; j+ i=3 4 -2 1 3 8 6 -2 1 3 6 8,5个元素的插入法

41、排序过程示意图,i=1 j=i-1, t=si;j=0j- 0 8 3 6 1 -2 3 8 6 1 -2,i=4 j=i-1, t=si;j=0j- 3 1 3 6 8 -2 2 1 3 6 8 1 1 3 6 8 0 1 3 6 8 -2 1 3 6 8,两矩阵相乘： a00 a01 a02 a03 b00 b01 c00 c01 m a10 a11 a12 a13 b10 b11 m c10 c11 a20 a21 a22 a23 b20 b21 c20 c21 b30 b31 for(i=0; im; i+) for(j=0; jp; j+) for(k=0; kn; k+) cij+=aik*bkj;,i,k,i,k,j,j,n,n,p,p,i=0,m-1 j=0,p-1,