第5章 数组、字符串、指针.ppt

1、,第5章 数组,教学内容 理解数组数据类型 掌握一维数组与二维数组的定义、存放、初始化和基本操作 掌握数组与指针的关系 掌握字符串的相关操作 熟悉使用指针处理字符串的方法 掌握数组的常用算法 教学重点 字符串的相关操作 数组的常用算法 教学难点 数组的常用算法,数组概念,数组是一种构造数据类型 数组是相同类型有序数据的集合 数组中的每一个数据称为数组的一个元素 数组中的元素可以通过统一的数组名和下标来唯一确定 C编译器给数组分配一块连续存储空间依次存放数组的各个元素,一维数组,只用一个下标的数组称为一维数组 定义 类型说明符 数组名常量表达式; 例：int a10,b2*3; 常见错误 int

2、 a(10); int n; scanf(“%d”,#define N 10 int aN;,一维数组,初始化：在定义数组的同时给数组元素赋初值 基本方法：int a5=1,2,3,4,5; 其它方法：教材P127 存放,引用数组元素 形式：数组名下标 下标可以是常量，也可以是变量 下标取值范围从0开始,一维数组的基本操作,输入输出 一次处理一个元素 循环实现 main() int a10,i; for(i=0;i10;i+) scanf(“%d”, ,一维数组的基本操作,求最值 逐个判断 #define N 10 main() int aN,i,p,max; /*p存放最大值下标,max存放

3、最大值*/ /*输入数组元素*/ max=a0; p=0; for(i=0;imax)max=ai;p=i; printf(“The max number a%d=%d”,p,max); ,一维数组的基本操作,倒置 ai与aN-i-1交换 N个元素交换N/2次 for(i=0;iN/2;i+) t=ai; ai=aN-i-1; aN-i-1=t; ,一维数组应用举例,例5-4：求某班20个学生某门课程考试的平均成绩及高于平均成绩的学生人数。P130 程序流程 输入数据：20个成绩 处理数据：求平均分,统计高于平均分的人数 输出结果：平均分,人数,源程序,#define NUM 20 main(

4、) int aNUM,n,i; float sum,aver; sum=0; for(i=0;iaver)n+; printf(“%dn”,n);,二维数组,使用两个下标的数组称为二维数组 定义 类型说明符 数组名常量表达式常量表达式; 例：int a34; 初始化 基本方法： int a34=1,2,3,4,5,6,7,8,9,10,11,12; 其它方法：教材P135,二维数组,存放：二维表格，按行存储,引用数组元素 形式：数组名下标 下标 下标可以是常量，也可以是变量 下标取值范围从0开始,二维数组应用举例,例:设一个学习小组有5个学生,每个学生有3门课的考试成绩,求全组每个学生的平均成

5、绩. 分析:处理一批性质相同的数据时,可以考虑使用数组,并根据数据间的逻辑关系选择数组的维数 用一个二维数组存放考试成绩 用一个一维数组存放平均成绩,源程序,main() int a53,aver5,sum,i,j; for(i=0;i5;i+) for(j=0;j3;j+) scanf(“%d”, ,如何找出最高成绩?,sum=0;,printf(“n”);,矩阵操作,相乘P136 Cm,n=Am,l*Bl,n,(i=1,2,m; j=1,2,n),for(i=0;iM;i+) for(j=0;jN;j+),cij=0; for(k=0;kL;k+) cij= cij+aik*bkj;, ,

6、矩阵操作,转置P137 方阵转置:可以不定义新数组 非方阵转置:需要定义新数组,147 258 369,123 456 789,对角线上的元素不交换,行列下标相同,i=j,aij与aji交换,逐行处理,第i行需要处理N-i-1个元素,指向一维数组的指针,可将某个数组元素的地址存放在一个指针变量中 前提:定义一个基类型与数组元素数据类型相同的指针变量 例:输入输出一维数组中的所有元素 下标法 #include #define N 10 void main() int aN,i; for(i=0;iN;i+) scanf(%d, ,/*等价于scanf(%d,a+i);*/,/*等价于printf

7、(%d,*(a+i);*/,指向一维数组的指针,指针法 #include #define N 10 void main() int aN,i,*p; for(p=a;pa+N;p+) scanf(%d,p); for(p=a;pa+N;p+) printf(%d,*p); ,二维数组的存储与访问,以int a23为例,数组a,二维数组的存储与访问,数组是一种构造数据类型，构成数组的元素是既可以是整型等基本数据类型，也可以是数组数据类型 一个二维数组就是一维数组，其中每个元素又都是一个一维数组,a0,a1,a,2000,a+1,2006,二维数组的存储与访问,二维数组的存储与访问,a0=*(a+

8、0)=*a=2000 for(i=0;iM;i+) for(j=0;jN;j+) scanf(%d,scanf(%d,ai+j);,printf(%d,*(ai+j);,指向二维数组的指针,指针法 #include #define M 4 #define N 5 void main() int aMN,i,*p; for(p= ,p=a,虽然a+1的值与a10的地址相等，但p+1却指向a01，因为p的基类型为整型，每执行一次p+，指针将移动2个字节.,指向二维数组的指针,#include #define M 4 #define N 5 void main() int aMN,i; int (*

9、p)N; /*定义一个指向包含N个元素的整型一维数组的指针变量*/ for(p=a;paM;p+) for(i=0;iN;i+) scanf(%d,*p+i); for(p=a;paM;p+) for(i=0;iN;i+) printf(%d,*(*p+i); printf(n); ,指针变量p的基类型为包含N个元素的整型一维数组。 每执行一次p+，指针将移动2*N个字节，即指向二维数组的下一行 *p+i指向当前行第i个元素，*(*p+i)为当前行第i个元素的值,不要将int (*p)N;写成int *pN;，后者表示定义一个包含N个元素的一维数组，每个元素为基类型为整型的指针变量,字符数组,

10、用于存放字符数据的数组，字符数组中的一个元素存放一个字符 定义 char 数组名常量表达式; 初始化 char c7=W, e, l, c, o, m, e; 引用 数组名下标,字符串,C语言中没有字符串数据类型，而是使用字符数组来处理字符串 系统自动为字符串常量增加一个字符串结束标志0（ASCII码为0） 字符串“Welcome”的存放形式,8个字节,char c=“Welcome”;数组c的存放形式,8个元素,c0 c1 c2 c3 c4 c5c6 c7,不等价于char c7=W, e, l, c, o, m, e;,字符数组,输入 逐个字符输入 for(i=0;iN;i+)scanf(

11、“%c”,%s格式符使用说明:P99100 输出时,遇0结束且不输出0 输入输出时,均使用数组名作参数,scanf函数以空格和回车作为输入结束标志 gets函数以回车作为输入结束标志,字符串函数,P157162 #include 字符串连接：strcat 字符串复制：strcpy 字符串比较：strcmp 字符串长度：strlen 字符串小写：strlwr 字符串大写：strupr,字符数组应用举例,例5-32：加密问题教材P173 程序流程 输入数据：一行字符（原文） 处理数据：字母字符按规律转换，非字母字符不变 输出结果：密文 算法分析 逐一判断是否为字母，对字母进行转换 解决方案：循环

12、循环条件 循环变量初始化 改变循环变量的值,当前字符不是结束标志0,取第一个字符,取下一个字符,流程图,A B C D E F G H I J Z K Y L X M W V U T S R Q P O N,源程序,#include #define K 3 main() char st80,strp80,tmp; int i=0; printf(“Enter a stringn”); gets(st); while(sti!=0) if(sti =a,是否可改为: if(sti =a,字符数组应用举例,例5-33：统计单词个数P175 程序流程 输入数据：一行字符 处理数据：统计 输出结果：单

13、词个数 算法分析 问题实质：统计问题 解决方案： 单词之间以空格或其它标点符号进行分隔 如果当前字符不是分隔符,而前一个字符是分隔符,则表示一个新单词开始 实现形式：循环,流程图,逐个判断,源程序,#include main() char st80,last= ,ch; int i=0,nw=0; printf(“Enter a stringn”); gets(str); while(ch=sti)!=0) if(!(ch= |ch=,|ch=;|ch=! |ch=.) if(last= |last=,|last=; |last=!|last=.) nw+; last=ch; i+; prin

14、tf(“%d wordsn”,nw);,字符串,长度 strlen(“Hello World!”) strlen(“Hello World!n”) strlen(“Hello0World!n”),s1,存储 char s1= “Hello World!n”; char s2= “Hello0World!n”;,12,13,5,访问 下标法:s1i 等价于*(s1+i),指向字符串的指针,使用字符数组处理字符串的缺点 不能直接将一个字符串赋值给一个已经定义好的数组 只能将各个字符逐一赋值给数组中各元素 并且数组中能够存放的字符串不能超过数组长度 使用指针处理字符串的方法 定义一个基类型为字符型为

15、指针变量 char *s; 将需要处理的字符串直接赋值 s=“Welcome”;,指向字符串的指针,例5-19:字符串复制P154 使用字符数组 #include void main() char s1=Hello World!n,s220;/*数组s2的长度要定义合适*/ int i; for(i=0;s1i!=0;i+) s2i=s1i; s2i=0; /*复制循环中未复制的字符串结束标志*/ puts(s1);/*printf(“%s”,s1);*/ puts(s2); ,指向字符串的指针,使用指针变量 #include #include #include void main() cha

16、r *s1=Hello World!n,*s2,*t; puts(s1); /*初始化s2，使其指向一块能够容纳所复制字符串的存储空间*/ s2=calloc(strlen(s1)+1,sizeof(char); t=s2; while(*s1!=0) *s2=*s1; s1+; s2+; *s2=0;/*复制循环中未复制的字符串结束标志*/ s2=t; puts(s2);,常用算法,排序 选择法排序 冒泡法排序 查找 顺序查找 二分查找（折半查找） 插入,选择法排序,算法描述（递增） 从n个数中选出最小的数与第1个数交换位置 除第1个数外，从剩下n-1个数中选出最小的数与第2个数交换位置 重

17、复上述步骤n-1次得到一个递增序列,排序过程示意图,数组 a0a1a2a3a4 排序前：53691 第1次选择后：13695 第2次选择后：13695 第3次选择后：13596 第4次选择后：13569,第i次选择的范围为第i个到第n-1个元素 第i次选择出的元素与第i个元素交换,0 1 2 3,流程图,注意：变量i除了控制选择次数外，还表示本次选出的元素将要存放的位置,源程序,#define N 20 main() int aN,i,j,p,t; for(i=0;iN;i+)scanf(“%d”, ,冒泡法排序,算法描述（递增） 第1趟从第1个数到第n个数，将相邻的两个数进行比较，并将小的数

18、调到前面 第2趟将除第n个数外所有相邻的两个数进行比较，并将小的数调到前面 重复n-1趟得到一个递增序列,排序过程示意图,数组 a0a1a2a3a4 排序前：53691 第1趟：35691 35691 35691 35619 第2趟：35169 第3趟：31569 第4趟：13569,第i趟比较的范围为第0个到第n-i-1个元素 每趟都是将第j个元素与第j+1个元素比较,0 1 2 3,流程图,源程序,#define N 10 main() int aN,i,j,k,t; for(i=0;iaj+1) t=aj;aj=aj+1;aj+1=t; for(i=0;iN;i+)printf(“%d”

19、,ai); ,顺序查找,算法描述 将待查数据依次与各个元素进行比较，若找到则返回元素下标，若均不相等，则表明查无此数 流程图,正常出口,紧急出口,源程序,#define N 10 main() int aN,i,n; for(i=0;i=N)printf(“not findn”); ,与教材P168程序进行比较,体会变量index的用途,二分查找,前提：在有序数列中查找 算法描述（以递增序列为例） 用top代表当前查找起始范围，用bot代表当前查找终止范围 计算当前查找范围中间位置mid=(top+bot)/2 将待查数x与第mid个数进行比较，若相等则返回mid，若大于第mid个数则bot=

20、m+1，若小于第m个数则top=mid-1 重复上述步骤直到找到，或发现topbot，此时表明查无此数,查找过程示意图,数组 a0a1a2a3a4 原始数据：13579 待查数据：3 次数bottopmid 1042 2010 3111 4,8 bottopmid 042 343 444 43 ,流程图,紧急出口,正常出口,源程序,#define N 10 main() int aN=1,2,3,4,5,6,7,8,9,10; int bot,top,mid,x; scanf(“%d”, ,与教材P169程序进行比较,体会变量find的用途,插入法,把一个给定的数据x按大小顺序插入已排好序的数组中,插入后数组元素仍然有序 算法分析 确定插入位置 空出插入位置 插入元素,50,40,30,25,源程序,#define N 10 /* N代表数据的个数 */ void main() /* 定义N+1个元素的数组 */ int aN+1=1,4,7,13,16,19,28,36,49,60; int x,p,i; printf( Befor Inserted:n); for(i=0;iN;i+) /* 输出插入前的数据序列 */ prin