C语言编程 第五章 数组.ppt

《C语言编程 第五章 数组.ppt》由会员分享，可在线阅读，更多相关《C语言编程 第五章 数组.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第五章第五章指指针针与与数数组组一维数组与指针一维数组与指针一维数组与指针一维数组与指针字符数组、字符串与字符指针字符数组、字符串与字符指针字符数组、字符串与字符指针字符数组、字符串与字符指针字符串处理函数字符串处理函数字符串处理函数字符串处理函数数组的基本概念数组的基本概念C C 数据类型数据类型 基本类（简单类）基本类（简单类）字符型字符型/整型整型/实型实型/枚举型（枚举型（enum）构造类（组合类）构造类（组合类）数组数组/结构体结构体/共用体共用体 指针类指针类 空类型（空类型（void）基本类型基本类型单个出现的变量，每个变量可代表一确定的数据（变量单个出现的变量，每个变量可代表一

2、确定的数据（变量值），且具有一定属性。值），且具有一定属性。【例例】staticintx,y;但变量间不存在确定的相互关系。但变量间不存在确定的相互关系。构造类型构造类型由基本类型按一定规则组成。其中：由基本类型按一定规则组成。其中：数组：由一组有序数据（数组元素）组成。数组：由一组有序数据（数组元素）组成。每个元素：相同类型，统一数组名，由下标定顺序，可各自取值。每个元素：相同类型，统一数组名，由下标定顺序，可各自取值。【例例】staticinta5;其中：其中：表示表示a a是个数组，而不是一个简单变量是个数组，而不是一个简单变量a a。5 5表示该数组共有表示该数组共有5个元素。元素编号

3、从个元素。元素编号从0开始，开始，a0表示第一个元素，表示第一个元素，a4表示第表示第5 5个元素（最个元素（最后一个）。后一个）。数组的基本概念数组的基本概念 数组的用处很多。数组的用处很多。【例例】要读入某班全体要读入某班全体5050位同学某科学习成绩，然后进行简单处理（求平位同学某科学习成绩，然后进行简单处理（求平均成绩、最高分、最低分均成绩、最高分、最低分）。）。若用简单变量，需若用简单变量，需5050个不同变量名，如个不同变量名，如stu1,stu2,stu50，要用很多个，要用很多个scanf命令。命令。而用数组，可共用一个而用数组，可共用一个scanf命令，并利用循环结构读取。命

4、令，并利用循环结构读取。#include#defineNUM50;voidmain(void)inti,scoreNUM,highest;floatsum=0,average;for(i=0;iNUM;i+)scanf(“%d”,&scorei);printf(“全班同学成绩公布如下：全班同学成绩公布如下：n”);for(i=0;iNUM;i+)printf(“%d号同学：号同学：%5dn”,i+1,scorei);for(i=0;iNUM;i+)/*求平均成绩求平均成绩*/sum+=scorei;average=sum/NUM;printf(“全班平均成绩：全班平均成绩：%dn”,avera

5、ge)；highest=a0;for(i=0;ihighest)highest=ai;printf(“最高分是：最高分是：%dn”,highest)；数组的基本概念数组的基本概念 所谓数组，实际为所谓数组，实际为一组同质一组同质(同数据类型同数据类型)元素的有序集合元素的有序集合，数组在内，数组在内存中占用一片存中占用一片连续连续的存储空间，数组元素可通过下标访问任一数组元素。的存储空间，数组元素可通过下标访问任一数组元素。数组元素的数据类型称为数组的基类型。可以是前述的简单类型，也数组元素的数据类型称为数组的基类型。可以是前述的简单类型，也可是指针或构造类型。可是指针或构造类型。许多重要应用

6、皆基于数组。许多重要应用皆基于数组。计算机系统根据数组定义的大小，为数组分配一段连续的内存空间。计算机系统根据数组定义的大小，为数组分配一段连续的内存空间。同一数组的所有元素均保存在此，又因为各元素同质，即所占内存大小相同一数组的所有元素均保存在此，又因为各元素同质，即所占内存大小相等，故可以通过数组下标访问各数组元素。等，故可以通过数组下标访问各数组元素。数组的四大要素：数组的四大要素：数组名，同变量标示符。但数组名后数组名，同变量标示符。但数组名后 不可少。不可少。数组的类型，既数组的基类型。数组的类型，既数组的基类型。数组的结构，用于说明数组的维数和数组元素的个数。数组的结构，用于说明数

7、组的维数和数组元素的个数。数组的存储类型。数组的存储类型。数组的四大要素通过定义数组的说明语句通知编译系统。数组的四大要素通过定义数组的说明语句通知编译系统。一维数组的定义一维数组的定义 与一般变量相同，数组也应当先定义，再引用。与一般变量相同，数组也应当先定义，再引用。格式：格式：类型说明符类型说明符 数组标示符数组标示符 常量表达式常量表达式=；说明数组的数据类型说明数组的数据类型 数组名数组名 表示数组大小表示数组大小 初始化值初始化值【例例】int int arrayarray10,number10,number2020;类型说明符类型说明符 数组标示符数组标示符 常量表达式常量表达式

8、 char ch15;char ch15;【注注】数组标示符与一般变量标示符的区别：数组名后有一对方括号数组标示符与一般变量标示符的区别：数组名后有一对方括号。方括号方括号用于表述数组的维数和大小，必须为常量表达式。用于表述数组的维数和大小，必须为常量表达式。C C语言不支语言不支持变界数组持变界数组(数组定义时必须预先指定数组的大小数组定义时必须预先指定数组的大小)。int i;int i;char chi;/char chi;/非法非法 一维数组名有一维数组名有2 2个含义：表示数组标示符；表示系统分配给数组的存储个含义：表示数组标示符；表示系统分配给数组的存储区的首地址区的首地址(指针指

9、针)。scanf(“%c”,&ch0);scanf(“%c”,ch);与一般变量相同，类型说明含数据类型说明和存储类型说明。与一般变量相同，类型说明含数据类型说明和存储类型说明。数组元素的数组元素的下标值由下标值由0 0开始开始，最大下标值为最大下标值为 中的常量表达式中的常量表达式 1 1。数组名表示数组存储区的首地址，即数组第一个元素存放的地址。数组名表示数组存储区的首地址，即数组第一个元素存放的地址。C C语言中不允许出现动态数组说明，即数组的长度不能依赖运行过程语言中不允许出现动态数组说明，即数组的长度不能依赖运行过程中变化着的变量。中变化着的变量。【例例】inti;scanf(“%d

10、”,&i);chararrayi;数组数组arrayi的长度依赖于变量的长度依赖于变量i的输入结果，这是不允许的。的输入结果，这是不允许的。一维数组的初始化一维数组的初始化 使数组元素得到值，可以有三种基本途径使数组元素得到值，可以有三种基本途径 (1)(1)用赋值语句；用赋值语句；(2)(2)用输入语句；用输入语句；(3)(3)初始化。初始化。前前两两种种方方式式占占运运行行时时间间，而而初初始始化化数数组组，可可以以使使程程序序在在运运行行之之前前的的编译阶段得到初值编译阶段得到初值 。所谓数组的初始化，就是在定义数组时为数组元素赋初值。所谓数组的初始化，就是在定义数组时为数组元素赋初值。

11、类型说明符类型说明符数组标识符数组标识符常量表达式常量表达式=常量表达式常量表达式；其其中中：“=常常量量表表达达式式表表”为为赋赋初初值值部部分分，中中各各常常量量表表达达式式是是对对应的数组元素初始，它们相互之间用逗号分隔。例如：应的数组元素初始，它们相互之间用逗号分隔。例如：inta4=0,1,2,3;它等价于它等价于staticinta4；a0=0;a1=1;a2=2;a3=3;由于数组长度可由初值个数确定，故可以写成：由于数组长度可由初值个数确定，故可以写成：staticinta=0,1,2,3;数组初始化的特点：数组初始化的特点：(1)当当数数组组指指明明的的元元素素个个数数大大于

12、于初初值值个个数数时时，则则表表明明初初值值只只赋赋给给数数组组开开始的若干元素，余下部分为相应类型的缺省值。始的若干元素，余下部分为相应类型的缺省值。例如：例如：staticinta5=0,1,2,3;它表示它表示a0=0，a1=1，a2=2，a3=3，a4=0(2)不不允允许许数数组组指指明明的的元元素素个个数数小小于于初初值值个个数数，否否则则作作语语法法出出错错处处理理。例如：例如：staticinta6=0,1,2,3,4,5,6,7;是错误的。是错误的。(3)不允许对数组元素整体赋值，只能对数组元素逐个赋初值。不允许对数组元素整体赋值，只能对数组元素逐个赋初值。要使数组要使数组a中

13、的全部元素初值为中的全部元素初值为0，可写成：，可写成：staticinta4=0,0,0,0;而不能写成：而不能写成：staticinta4=0*10；其其实实，按按照照上上述述(1)的的规规定定，对对static数数组组不不赋赋初初值值，系系统统会会自自动动对对全全部数组元素赋以部数组元素赋以0值。值。即：即：staticinta4；相当于；相当于a0a3全部都赋以初值全部都赋以初值0。(4)在在对对数数组组元元素素全全部部赋赋初初值值时时，可可以以不不指指定定数数组组长长度度，其其长长度度由由所所赋赋初值的个数自动确定初值的个数自动确定。如：如：staticinta=1,2,3,4；a数

14、组的初值有数组的初值有4个，故系统自动确定个，故系统自动确定a的长度为的长度为4。一维数组的引用一维数组的引用 C C 规定：对数组只能逐个引用，规定：对数组只能逐个引用，不能整体引用不能整体引用。原因：数组是一个数据类型的聚集，它本质上不是基本数据类型。原因：数组是一个数据类型的聚集，它本质上不是基本数据类型。将数组将数组 a a 赋给数组赋给数组 b b：inta10=0,1,2,3,4,5,6,7,8,9,b10,i;for(i=0;i10;i+)ai=bi;/正确正确b=a;/错误错误 通过数组名通过数组名 下标下标 格式，利用下标的变化，可逐个引用数组元素。格式，利用下标的变化，可逐

15、个引用数组元素。引用格式：引用格式：数组名数组名 下标下标 其中，下标必须是整型常量其中，下标必须是整型常量/表达式。表达式。注意：注意：C C 的下标从的下标从 0 0 开始。开始。数组元素的使用方法与同类型变量的使用方法完全相同数组元素的使用方法与同类型变量的使用方法完全相同。C C语言中最常见的错误之一是数组元素的越界使用语言中最常见的错误之一是数组元素的越界使用(访问数组元素的下访问数组元素的下标超出了对数组进行说明时规定的界限。下标越界将会非法地改变其它存标超出了对数组进行说明时规定的界限。下标越界将会非法地改变其它存储单元的内容，有时还会造成严重的错误。储单元的内容，有时还会造成严

16、重的错误。【例例】#includevoidmain(void)inta10,i;for(i=0;i10;i+)ai=i;for(i=0;i10;i+)printf(“a%2d=%dn”,i,ai);多维数组的定义和引用多维数组的定义和引用 将一维数组概念推广，可得多维数组。将一维数组概念推广，可得多维数组。当组成一维数组的每个元素又是数组时，须用两个下标表示，构成了当组成一维数组的每个元素又是数组时，须用两个下标表示，构成了二维数组。将二维数组的概念推广，就可以得到三维、二维数组。将二维数组的概念推广，就可以得到三维、.乃至多维数组。乃至多维数组。格式：格式：类型说明符类型说明符 数组标示符数

17、组标示符 常量表达式常量表达式常量表达式常量表达式；【例例】chara23;/2维，维，23=6个元素个元素 intb234;/3维，维，234=24个元个元素素 多维数组的内存存储顺序：多维数组的内存存储顺序：愈右边的下标愈先变化愈右边的下标愈先变化。对于数组对于数组inta33a00a01a02a10a11a12a20a21a22计算机的内存为一维空间。对于计算机的内存为一维空间。对于C语言的数语言的数组，其在内存中的存储顺序如右图所示。组，其在内存中的存储顺序如右图所示。a00a01a02a10a11a12a20a21a22多维数组的定义和引用多维数组的定义和引用多维数组的初始化：多维数

18、组的初始化：按行对全部元素赋初值按行对全部元素赋初值inta33=1,2,3,4,5,6,7,8,9；按数组元素的存储顺序依次对全部元素赋初值按数组元素的存储顺序依次对全部元素赋初值inta33=1,2,3,4,5,6,7,8,9；对部分元素赋初值对部分元素赋初值staticinta33=1,5,9；等效于；等效于【注注】若是静态类型若是静态类型(static)，则其元素初始值为，则其元素初始值为0(对于整型数对于整型数)。若非静态类。若非静态类型或全局类型，则其元素的初始值随机。型或全局类型，则其元素的初始值随机。若对全部数组元素都赋初值，则第一维长度若对全部数组元素都赋初值，则第一维长度可

19、省略不写可省略不写，但第二及其，但第二及其它维的长度不能省。如：它维的长度不能省。如：inta4=1,2,3,4,5,6,7,8,9,10,11,12;与之等价定义：与之等价定义：inta34=1,2,3,4,5,6,7,8,9,10,11,12;系统根据数据总个数自动分配存储空间，一共系统根据数据总个数自动分配存储空间，一共12个数据，每行个数据，每行4列，列，则确定为则确定为3行。行。多维数组的引用与一维数组相同：数组名多维数组的引用与一维数组相同：数组名下标下标下标下标多维数组仍不允许整体引用。多维数组仍不允许整体引用。【例例】将将2维数组维数组a23中的元素按其存储顺序复制到中的元素按

20、其存储顺序复制到1维数组维数组b6中。中。#includevoidmain(void)inta23=1,2,3,4,5,6;intb6,i,j;for(i=0;i2;i+)for(j=0;j3;j+)bi*3+j=aij;for(i=0;i6;i+)printf(“b%2d=%dn”,i,bi);二维数组二维数组a23向一维数组向一维数组b6按存储顺序复制元素值时，其下标按存储顺序复制元素值时，其下标的对应关系为：的对应关系为：k=i*D+j其中，其中，D为为a23中第二维的大小，其值为中第二维的大小，其值为3，故程序中，故程序中b的下标为的下标为i*3+j。推广到一般，将多维数组按存储顺序转

21、换成一维数组时，其下标的推广到一般，将多维数组按存储顺序转换成一维数组时，其下标的对应关系由下式给出：对应关系由下式给出：k=第一维下标值第一维下标值D2D3Dk+第二维下标值第二维下标值D3D4Dk+第三维下标值第三维下标值D4D5Dk+第第k-1维下标值维下标值Dk+第第k维下标值维下标值其中，其中，Di(i=2，k)是多维数组第是多维数组第i维的长度。维的长度。【例例】查找数组查找数组a222中的最小元素。中的最小元素。#includevoidmain(void)inta222;/3维数组维数组ainti,j,k,min;for(i=0;i2;i+)for(j=0;j2;j+)for(k

22、=0;k2;j+)scanf(“%d”,&aijk);/为数组赋值为数组赋值min=a000;for(i=0;i2;i+)for(j=0;j2;j+)for(k=0;kaijk)min=aijk;/选择最小值选择最小值printf(“最小值最小值=%dn”,min);将将改为改为，则选择最大值，则选择最大值数组的基本操作数组的基本操作一、排序：所谓排序是将一组无序数据按递增或递减顺序进行重新排列，一、排序：所谓排序是将一组无序数据按递增或递减顺序进行重新排列，使其成为一组有序数据。其中，数组排序对计算机用户最有用。使其成为一组有序数据。其中，数组排序对计算机用户最有用。对于数组进行排序的方法一

23、般有对于数组进行排序的方法一般有3种：种：交换排序：交换排序：反复进行比较，必要时交换相邻元素反复进行比较，必要时交换相邻元素。上推排序法（又称冒。上推排序法（又称冒泡排序法）为其一，该法最简单，但效率最低。泡排序法）为其一，该法最简单，但效率最低。上推排序法有上推排序法有2个循环套个循环套。对于有。对于有N个元素的数组，外层循环对数个元素的数组，外层循环对数组扫描组扫描N-1次，以保证在最坏情况下，排序结束时每个元素都能放在适次，以保证在最坏情况下，排序结束时每个元素都能放在适当的位置上。内层循环则进行实际的两两比较和交换。当的位置上。内层循环则进行实际的两两比较和交换。每完成一次内层循环，

24、将使得该轮中的最大每完成一次内层循环，将使得该轮中的最大/小值被安置到合适的小值被安置到合适的位置。其算法如下：位置。其算法如下：/已知整型数组已知整型数组item，其元素个数为，其元素个数为Ninti,j,itemN;inttemp;/临时变量，用于相邻两元素的交换临时变量，用于相邻两元素的交换for(i=1;i=i;j-)/内层循环内层循环if(itemj-1itemj)/对应递增，递减时改为对应递增，递减时改为temp=itemj-1;itemj-1=itemj;itemj=temp;上推排序法的处理时间正比于比较和交换次数，当上推排序法的处理时间正比于比较和交换次数，当N很大时效率低。

25、很大时效率低。【例例5-4】输入输入N个整数，将其由小到大依次排序后输出。个整数，将其由小到大依次排序后输出。#include#defineN5voidmain(void)inti,j,itemN;inttemp;printf(input%dnumbers:n,N);for(i=0;iN;i+)scanf(%d,&itemi);for(i=1;i=i;j-)if(itemj-1itemj)temp=itemj-1;itemj-1=itemj;itemj=temp;printf(n);for(i=0;iN;i+)printf(%d,itemi);上推排序法示意图上推排序法示意图(逆序逆序)数组数

26、组数组数组item0item0item1item1item2item2item3item3item4item4数组的初始状态数组的初始状态823165947第一轮比较结束第一轮比较结束982316547第二轮比较结束第二轮比较结束931824765第三轮比较结束第三轮比较结束931478265第四轮比较结束第四轮比较结束931476582 上推排序法的缺陷：交换次数过多。上推排序法的缺陷：交换次数过多。选择排序：第一步从全部的选择排序：第一步从全部的N个元素中选出最小者，将其与原数组的第一个元素中选出最小者，将其与原数组的第一个元素交换。第二步从余下的个元素交换。第二步从余下的N-1个元素中选

27、出最小者，将其与原数组的个元素中选出最小者，将其与原数组的第二个元素交换。如此下去，直到剩下最后第二个元素交换。如此下去，直到剩下最后2个元素。算法如下：个元素。算法如下：/已知整型数组已知整型数组item，其元素个数为，其元素个数为Ninti,j,k,itemN;inttemp;/临时变量，用于相邻两元素的交换临时变量，用于相邻两元素的交换for(i=0;iN-1;i+)/外层循环外层循环k=i;for(j=i+1;jN;j+)/内层循环内层循环if(itemjtempk)/对应递增，递减时改为对应递增，递减时改为k=j;/保存当前循环中选出的最大值的数组下标保存当前循环中选出的最大值的数组

28、下标/将选出的最大数组元素与将选出的最大数组元素与i数组元素交换数组元素交换temp=item(k);itemk=itemi;itemi=temp;与上推排序法相比，选择排序的比较次数相同，但交换次数减少。与上推排序法相比，选择排序的比较次数相同，但交换次数减少。【例例】输入输入N个整数，使用选择排序法将其由小到大依次排序后输出。个整数，使用选择排序法将其由小到大依次排序后输出。#include#defineN5voidmain(void)inti,j,itemN;inti,j,k,temp;printf(input%dnumbers:n,N);for(i=0;iN;i+)scanf(%d,&

29、itemi);for(i=0;iN-1;i+)k=i;for(j=i+1;jN;j+)if(itemjitemk)k=j;if(itemk!=itemi)temp=itemk;itemk=itemi;itemi=temp;printf(n);for(i=0;iN;i+)printf(%d,itemi);数组数组数组数组item0item0item1item1item2item2item3item3item4item4数组的初始状态数组的初始状态823165947第一轮比较结束第一轮比较结束931658247第二轮比较结束第二轮比较结束931658247第三轮比较结束第三轮比较结束9314782

30、65第四轮比较结束第四轮比较结束931476582选择排序法示意图选择排序法示意图(逆序逆序)插入排序：首先对数组的头插入排序：首先对数组的头2个元素排序，然后根据前个元素排序，然后根据前2个元素的排序情个元素的排序情况将第况将第3个元素插入到相应的位置上。第个元素插入到相应的位置上。第3步，根据前步，根据前3个元素的排序情况个元素的排序情况将第将第4个元素插入到相应的位置（方法：以该元素为标本，其它元素逐个个元素插入到相应的位置（方法：以该元素为标本，其它元素逐个与之比较，无序则后移一步，有序即终止，执行插入）。该过程一直进与之比较，无序则后移一步，有序即终止，执行插入）。该过程一直进行到所

31、有元素都排好序为止。算法如下：行到所有元素都排好序为止。算法如下：/已知整型数组已知整型数组item，其元素个数为，其元素个数为Ninti,j;inttemp;/临时变量临时变量for(i=1;i=0&tempitemj)/对应升序对应升序itemj+1=itemj;j-;itemj+1=temp;与上推和选择排序不同，插入排序的比较次数取决于排序对象开始时的与上推和选择排序不同，插入排序的比较次数取决于排序对象开始时的排列情况。排列情况。数组数组数组数组item0item0item1item1item2item2item3item3item4item4数组的初始状态数组的初始状态823165

32、947第一轮比较结束第一轮比较结束318265947第二轮比较结束第二轮比较结束316582947第三轮比较结束第三轮比较结束931658247第四轮比较结束第四轮比较结束931476582插入排序法示意图插入排序法示意图二、查找：所谓查找是在一组数据二、查找：所谓查找是在一组数据(有序或无序有序或无序)中寻找某一特定数据。中寻找某一特定数据。查找方法一般有查找方法一般有2种：种：顺序查找：遍历数组，即从第一个数组元素开始，逐个检查该数组元素顺序查找：遍历数组，即从第一个数组元素开始，逐个检查该数组元素是否满足条件，直到查找出所需元素或遍历结束而未能找到所需元素。是否满足条件，直到查找出所需元

33、素或遍历结束而未能找到所需元素。顺序查找法可用于未排序或已排序数组，算法简单，但效率不高。当有顺序查找法可用于未排序或已排序数组，算法简单，但效率不高。当有N个数据时，找到所需数据的平均查找次数为个数据时，找到所需数据的平均查找次数为N/2次次(10000数据，数据，5000次次)。算法如下：算法如下：/已知整型数组已知整型数组item，其大小为，其大小为N，所求数据为整数，所求数据为整数data，返回一数组，返回一数组/下标。下标。intFind1(intitem,intN,intdata)inti;for(i=1;iN;i+)if(itemi=data)/找到找到return(i);ret

34、urn(-1);/未找到未找到折半查找：对于折半查找：对于有序数据有序数据，可以采用折半查找法。其方法是：找出数组，可以采用折半查找法。其方法是：找出数组的中项，若它为所求，查找结束。否则舍弃当前数组的一半元素，在新的中项，若它为所求，查找结束。否则舍弃当前数组的一半元素，在新的数组范围内再次找出数组中项并进行比较。的数组范围内再次找出数组中项并进行比较。折半查找法仅能用于排序数组，效率高。当有折半查找法仅能用于排序数组，效率高。当有N个数据时，找到所需数据个数据时，找到所需数据的平均查找次数为的平均查找次数为log2(n)次次(10000数据，数据，20次次)。算法如下：。算法如下：/已知已

35、知升序升序整型数组整型数组item，其元素个数为，其元素个数为N，待查数为整数，待查数为整数data。intFind2(intitem,intN,intdata)intleft=0,right=N-1,middle;/分别为当前查找数组的左右边界和中项分别为当前查找数组的左右边界和中项while(leftright)middle=(left+right)/2;/找出当前查找数组的中项找出当前查找数组的中项if(itemmiddledata)left=+middle;/中项值中项值data)right=-middle;/中项值中项值待查数，舍弃右边待查数，舍弃右边if(itemmiddle=da

36、ta)return(middle)return(-1);【例例】有有15个数存放在一个数组中，输入一个数，用折半查找法找出该数个数存放在一个数组中，输入一个数，用折半查找法找出该数是数组中第几个元素。若该数不在数组中，则打印出是数组中第几个元素。若该数不在数组中，则打印出“Nofound”。#include#defineN15voidmain(void)intNumberN=1,5,2,3,9,6,8,7,14,10,15,22,19,16,18;inti,j,temp,left=0,right=N-1,middle,search=10;for(i=1;i=i;j-)if(Numberj-1N

37、umberj)temp=Numberj-1;Numberj-1=Numberj;Numberj=temp;while(leftright)/查找查找middle=(left+right)/2;/取中点取中点if(Numbermiddlesearch)right=-middle;if(Numbermiddle=search)break;if(leftright)printf(Search:No.%2d,middle+1);elseprintf(Nofound!n);思考：用递归方式表示折半查找法。思考：用递归方式表示折半查找法。三、数组元素的插入和删除三、数组元素的插入和删除#includevo

38、idmain(void)intarray10=1,2,4,5,6,0,0,0,0,0,i;printf(n);for(i=0;i=2;i-)arrayi=arrayi-1;/后移后移9-2=7次次array2=3;for(i=0;i10;i+)printf(%3d,arrayi);printf(n);1 2 4 5 6 0 0 0 0 01 2 3 4 5 6 0 0 0 01 2 4 5 6 0 0 0 0(7)(6)(5)(4)(3)(2)(1)【例例】计算计算2个矩阵个矩阵a，b的乘积。的乘积。矩阵的乘法公式：矩阵的乘法公式：#include#defineM4#defineN2#defi

39、neP3voidmain(void)intaMP,bPN,multiMN;inti,j,k;printf(Inputarraya%2d%2d:n,M,P);for(i=0;iM;i+)/输入矩阵输入矩阵afor(j=0;jP;j+)scanf(%d,&aij);printf(Inputarrayb%2d%2d:n,P,N);for(i=0;iP;i+)/输入矩阵输入矩阵bfor(j=0;jN;j+)scanf(%d,&bij);for(i=0;iM;i+)for(j=0;jN;j+)multiij=0;for(k=0;kP;k+)multiij+=aik*bkj;printf(c%2d%2d=

40、%d,i+1,j+1,multiij);printf(n);【例例】编程求解约瑟夫问题：编程求解约瑟夫问题：M个人围成一圈，从第一个人开始报数，数个人围成一圈，从第一个人开始报数，数到到N的人出圈。再由下一个人开始报数，数到的人出圈。再由下一个人开始报数，数到N的人出圈。的人出圈。打印依次出圈打印依次出圈人的编号。人的编号。M值预先选定，值预先选定，N值由键盘键入。值由键盘键入。例：例：M=8，N=5，则依次出圈的人是，则依次出圈的人是5，2，8，7，【分析分析】约瑟夫问题是一个循环问题。但不是简单循环。原因：约瑟夫问题是一个循环问题。但不是简单循环。原因：当数到第当数到第M个人时，再继续前数

41、，则应重置为个人时，再继续前数，则应重置为0当某人已经出圈，则数到他时，应再向前数当某人已经出圈，则数到他时，应再向前数采用数组来保存已出圈者的信息采用数组来保存已出圈者的信息(初始初始0：未出圈；：未出圈；1：已出圈：已出圈)。一级算法：一级算法：do遍历未出圈者遍历未出圈者N次，使一人出圈次，使一人出圈(需进一步求精需进一步求精)while(出圈人数出圈人数=M);二级算法：二级算法：-1i+(向前数向前数1)-2若已过尾若已过尾(i=M)，则，则i=0-3若若i对应者已出圈，则对应者已出圈，则i+，(可能有连续多人已出圈可能有连续多人已出圈)，直至直至i对应者未出圈对应者未出圈#incl

42、ude#defineM8#defineOUT1voidmain(void)intmenM;inti,N,j=0,count=0;printf(InputN:);scanf(%d,&N);/输入输入N/初始化初始化for(i=0;iM;i+)meni=0;i=-1;do/遍历数组，使遍历数组，使M人出列人出列i+;if(i=M)i=0;/若到尾，则置为若到尾，则置为0/跳过已出圈者跳过已出圈者while(meni=OUT)i+;if(i=M)i=0;/到尾，置到尾，置0if(+j%N=0)/某人数到某人数到N,出圈出圈meni=OUT;count+;printf(%d,i+1);while(co

43、unt!=M);字符型数组格式：格式：char字符数组名字符数组名常量整型表达式常量整型表达式；标识字符数组的长度标识字符数组的长度其中，一个数组元素存放一个其中，一个数组元素存放一个char类型值。类型值。对于局部变量，当未初始化时，字符数组的内容随机。对于局部变量，当未初始化时，字符数组的内容随机。字符数组的初始化有字符数组的初始化有2种方法：种方法：逐个为数组元素指定初值字符逐个为数组元素指定初值字符charstr4=a,b,c,d;用字符串为字符数组整体赋初值（常用）用字符串为字符数组整体赋初值（常用）charstr=“abcd”;charstr=“abcd”;【注注】两种初始化方法的

44、效果不同。两种初始化方法的效果不同。方法方法自动追加空字符自动追加空字符0结束字符数组。结束字符数组。对于字符串的处理，人们关心的是有效字符串的长度，而不是字符数组对于字符串的处理，人们关心的是有效字符串的长度，而不是字符数组的长度。的长度。C语言规定用语言规定用0表示字符串结束标志。程序中大多依靠检表示字符串结束标志。程序中大多依靠检测测0而不是根据字符数组的长度来判断字符串是否结束。系统判而不是根据字符数组的长度来判断字符串是否结束。系统判别一个字符串的长度由字符串的第一个字符别一个字符串的长度由字符串的第一个字符字符字符0所对应的字符所对应的字符个数决定，而不由存放字符串的字符数组的长度

45、决定个数决定，而不由存放字符串的字符数组的长度决定(字符数组的长度字符数组的长度字符串长度字符串长度)。一般的字符数组可不以一般的字符数组可不以0结尾，但字符串一定以结尾，但字符串一定以0结尾。结尾。abcdabcd0字符数组用于通常的字符串处理时，多以字符数组用于通常的字符串处理时，多以0为结尾。为结尾。对于各种字符输出库函数，系统遇对于各种字符输出库函数，系统遇0字符则输出结束。字符则输出结束。C语言多将字符数组视为字符指针处理。语言多将字符数组视为字符指针处理。字符数组的字符数组的I/O逐个字符逐个字符I/O：使用循环结构：使用循环结构charch20;inti;for(i=1;is2，

46、返回大于，返回大于0的整数。的整数。若字符串若字符串s1s2，返回小于，返回小于0的整数。的整数。strlen字符串长度测试函数字符串长度测试函数intsrelen(char*string);返回以空字符返回以空字符0结尾的字符串结尾的字符串string的长度的长度(不计入不计入0字符字符)。字串转换字串转换strcmp()函数函数char*strlwr(char*s);将字串将字串s中的字符转换为小写方式中的字符转换为小写方式(其余不变其余不变)，返回指向，返回指向s串的指针。串的指针。【例例】输入一串字符，分别统计其中数字输入一串字符，分别统计其中数字0，1，2，9出现的次数。出现的次数。

47、#include#includevoidmain(void)charstr80;intc0=0,c1=0,c2=0,c3=0,c4=0,c5=0,c6=0,c7=0,c8=0,c9=0;inti;gets(str);/读串读串for(i=0;istrlen(str);i+)/逐个分析逐个分析switch(stri)case0:c0+;break;case1:c1+;break;case2:c2+;break;case3:c3+;break;case4:c4+;break;case5:c5+;break;case6:c6+;break;case7:c7+;break;case8:c8+;brea

48、k;case9:c9+;printf(0appears%dn,c0);printf(1appears%dn,c1);printf(2appears%dn,c2);printf(3appears%dn,c3);printf(4appears%dn,c4);printf(5appears%dn,c5);printf(6appears%dn,c6);printf(7appears%dn,c7);printf(8appears%dn,c8);printf(9appears%dn,c9);【例例】strlen函数示例。函数示例。#include#includevoidmain(void)char*str

49、ing=BorlandInternational;printf(%dn,strlen(string);【例例】strcpy函数示例。函数示例。#include#includevoidmain(void)charstring10;char*str1=abcdefghi;strcpy(string,str1);printf(%sn,string);【注注】(1)拷贝时连同字符串后面的拷贝时连同字符串后面的0一起拷贝到字符数组一起拷贝到字符数组1中。中。(2)字符串字符串2可以是已赋值的字符数组名，也可以是字符串常量。可以是已赋值的字符数组名，也可以是字符串常量。例：例：strcpy(s1,comp

50、uter);字符数组字符数组1则必须是数组名的形式。则必须是数组名的形式。(3)字符数组字符数组1的长度必须定义得足够大，以便容纳被拷贝的字的长度必须定义得足够大，以便容纳被拷贝的字符串，否则会出错。符串，否则会出错。(4)若将字符串若将字符串2前面的若干个字符拷贝到字符数组前面的若干个字符拷贝到字符数组1中，则可以中，则可以用函数用函数strncpy。例：例：strncpy(s1,s2,4)；(5)试图用赋值语句将一个字符串常量或字符数值直接赋给一个试图用赋值语句将一个字符串常量或字符数值直接赋给一个字符数组是错误的，如字符数组是错误的，如s1=“computer”。赋值语句只能将一。赋值语