《数组和字符串》ppt课件

1、 数组的概念；数组的概念；数组的运用；数组的运用；数组的定义；数组的定义； 字符串字符串本章授课内容本章授课内容 常见错误常见错误5.1 数组的概念数组的概念 数组是一组有序数据的集合；数组中的每一个元素都数组是一组有序数据的集合；数组中的每一个元素都属于同一个数据类型。用一个一致的数组名和下标来独属于同一个数据类型。用一个一致的数组名和下标来独一确实定数组中的元素。一确实定数组中的元素。 在科学计算和数据处置中，要用到成批数据，这些在科学计算和数据处置中，要用到成批数据，这些数据类型一样，且彼此间存在一定的顺序关系，为了数据类型一样，且彼此间存在一定的顺序关系，为了便于处置一批类型一样的数据

2、便于处置一批类型一样的数据,引入了数组。引入了数组。一维数组一维数组a0a1a2a3a4a5数列数列583296例例4.1.1:4.1.1:某班有某班有4040名学生名学生, ,求该班成果的平均分求该班成果的平均分 #include void main( ) int j , sum , score ; float ave ; sum=0; for(j=1; jscore; sum=sum+score; ave=sum/40; cout “ave=ave;假设如今要求保管每个学生的成果假设如今要求保管每个学生的成果, ,那就不能只运用一个变量那就不能只运用一个变量scorescore了了, ,而

3、需求而需求4040个变量个变量, ,但这样一来输入、但这样一来输入、输出、计算都会变得繁琐输出、计算都会变得繁琐. . 在这种在这种情况下情况下, ,我们可以运用数组类型我们可以运用数组类型, ,阐阐明一个含有明一个含有4040个元素的数组个元素的数组, ,每个每个数组元素存放一个成果数组元素存放一个成果, ,成果的输成果的输入、输出、计算都可经过循环来实入、输出、计算都可经过循环来实现。现。一、数组的引入一、数组的引入#include void main( ) int j , sum , score 40 ; float ave ; sum=0; for(j=0; jscore j; sum

4、=sum+score j; ave=sum/40; cout “ave=ave;1.1.数组数组: :由具有一样类型由具有一样类型的的 固定数量的元素组成固定数量的元素组成的构造。的构造。2.2.数组元素数组元素: :每一个数组元素每一个数组元素 都是一个变量都是一个变量, ,为了与普通为了与普通 的变量相区别的变量相区别, ,我们称数组我们称数组 元素为下标变量。元素为下标变量。注：直接前驱和直接后继的概念注：直接前驱和直接后继的概念3.3.下标变量在数组中的位置下标变量在数组中的位置 序号称下标序号称下标 下标变量的数据类型称为下标变量的数据类型称为 下标类型下标类型( (或元素类型或元素

5、类型) )二、数组的概念二、数组的概念5.2 一维数组一维数组一、一维数组的定义一、一维数组的定义二、一维数组的存储构造二、一维数组的存储构造三、数组元素的援用方式三、数组元素的援用方式四、一维数组的初始化四、一维数组的初始化六、一维数组程序设计举例算法六、一维数组程序设计举例算法五、一维数组的输入和输出五、一维数组的输入和输出_ 数组数组 由一组具有同一数据类型由一组具有同一数据类型 的变量有序的变量有序_ 集合。集合。 例如： int a10; 数组名数组名常量表达式常量表达式类型阐明类型阐明一、一维数组的定义一、一维数组的定义_ 格式格式 :常量表达式常量表达式 _ =;int a10;

6、_ 数组名命名规那么同标识符数组名命名规那么同标识符_数组名表示了一个存储区的首地址数组名表示了一个存储区的首地址 (即第一个即第一个数组元素的地址数组元素的地址)int n;cinn;int an;._ 常量表达式中不能有变量常量表达式中不能有变量_常量表达式的值不能是实数常量表达式的值不能是实数_ 下标从下标从0开场开场, a0 , a1 a9，没有，没有a10;_ 常量表达式的值为元素的个数常量表达式的值为元素的个数错误错误二、一维数组的存储构造二、一维数组的存储构造a数组首地址数组首地址_ 一个数组的一切元素都是延续存储的一个数组的一切元素都是延续存储的_ 数组元素为数组元素为: a0

7、,a1,a2.a9int a10;_ 所占空间为所占空间为: 类型空间类型空间*元素个数元素个数 84 : 66 80 95101010141018 :1036a0a1a2 :a9三、数组元素的援用方式三、数组元素的援用方式_ 数组元素的援用数组元素的援用: 数组名数组名下标下标_ 其中，其中， 为下标运算符为下标运算符a0 = a2+a4*2240int a10;a0=2;int a10,b10;下标下标 阐明阐明(1) 下标可以是整型常量或整型表达式下标可以是整型常量或整型表达式 如如: a1 , a2*3(2) 数组定义为数组定义为 int a5 , 数组长度为数组长度为5 而下标在而下

8、标在0 - 4之内之内, 即即a0 - a4留意留意: 假设出现假设出现 a5 = 72 ; 编译时不会指出错误编译时不会指出错误, 系统会系统会将将a4后下一个存储单元后下一个存储单元 赋值为赋值为72, 但这样可以会破坏数但这样可以会破坏数组以外其他变量的值。组以外其他变量的值。四、一维数组的初始化四、一维数组的初始化1. 概念概念 : 在定义一维数组时对各元素指定初始值称为在定义一维数组时对各元素指定初始值称为 数组的初始化。数组的初始化。如如: int a5 = 1 , 3 , 5 , 7 , 9 ;2. 阐明阐明 对数组的全体元素指定初值对数组的全体元素指定初值, 初值用初值用 括起

9、来括起来, 数据数据 之间用逗号分开之间用逗号分开. 在这种情况下在这种情况下, 可以不指明数组的可以不指明数组的 长度长度, 系统会根据系统会根据 内数据的个数确定数组的长度内数据的个数确定数组的长度 。 如如 : int a = 1 , 3 , 5 , 7 , 9 ;(2) 对数组中部分元素指定初值对数组中部分元素指定初值 ( 这时不能省略数组长度这时不能省略数组长度 ) 如如 : int a5 = 1 , 3 , 5 ; 注：后面的两个元素自动注：后面的两个元素自动初始化为初始化为0。(3) 使数组中的全部元素初始值都为使数组中的全部元素初始值都为 0 如如: int a5 = 0 ,

10、0 , 0 , 0 , 0 ;更简单的写法更简单的写法: int a5= 0 ;注：double a为错误例例5.2.1: 输入输入n个成果个成果,求平均分求平均分;输出高于平均分的成果输出高于平均分的成果#includevoid main()int sc,n,i;float aver=0.0;cinn;for(i=0;isc; aver+=sc;aver/=n;coutaversci;aver+=sci;aver/=n;for(i=0 ; iaver)coutsciai;输入整个数组元素：输入整个数组元素：for (i=0;iai;输出方法：输出方法：输出第i个数组元素：coutai;输出整

11、个数组元素：输出整个数组元素：for (i=0;i10;i+)coutai;_例例5.2.2:用一维数组求用一维数组求Fibonacci 数列数列(斐波纳契数列斐波纳契数列#includevoid 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) coutn ;coutt fi; coutn;六、一维数组程序设计举例六、一维数组程序设计举例 1 1 0 0 0 0 : 0f0f1f2f3f4f5 :f19i=2f2=f0+f1i=3f3=f1+f2i=4f4=f2+f

12、323586765例例5.2.3: 输入一个数据，在知数组中查找能否有该数据输入一个数据，在知数组中查找能否有该数据 5 8 0 1 9 2 6 3 7 49a0a1a2a3a4a5a6a7a8a9#include void main() int i , x ; int a10= 5, 8, 0, 1, 9, 2, 6, 3, 7, 4 ; cinx; for ( i=0 ; i10 ; i+) if ( x=ai ) coutfind! endl; break; if ( i=10 ) cout no find! endl; 注：注：if(x=aibreak;是是for循环体语循环体语句，后

13、面的语句不是句，后面的语句不是for循环体语句。循环体语句。5.3 二维数组二维数组一、二维数组的定义一、二维数组的定义二、二维数组的存储构造二、二维数组的存储构造三、二维数组的初始化三、二维数组的初始化四、二维数组元素的援用方式四、二维数组元素的援用方式五、二维数组的输入和输出五、二维数组的输入和输出六、二维数组程序设计举例六、二维数组程序设计举例一、二维数组的定义一、二维数组的定义_格式格式: =,;int b23;b为为232行行3列的数组列的数组b0b1b-b00 b01 b02-b10 b11 b12b0b1b00 b01b02b10 b11b12二、二维数组的存储构造二、二维数组的

14、存储构造int b23；b0b1b10b11b12b00b01b02_ 存放顺序：按行存放，先顺序存放第存放顺序：按行存放，先顺序存放第 一行一行_ 的元素，再存放第二行的元素。的元素，再存放第二行的元素。a10a11a12a20a21a22a00a01a02a00a01a02a10a11a12a20a21a22101010141018102210261030103410381042数组的元素在内存中是延续存放的数组的元素在内存中是延续存放的 int a33 ; 的存放方式如下的存放方式如下 :a0a1a2三、二维数组的初始化三、二维数组的初始化 int b23 = 1,2,3,4,5,6;

15、int b23 = 1,2,3,4,5,6; int b3 = 1,2,3,4,5,6;int b5int b;int b=1,2,3,4,5,6;int bnm;错错 !_ 分行赋值分行赋值_ 按数组陈列的顺序赋值按数组陈列的顺序赋值_ 假设全部都赋初值，第一维长度可省略假设全部都赋初值，第一维长度可省略123456留意留意: 此方法数据没有明显的界限此方法数据没有明显的界限, 当数据较多时容易出错当数据较多时容易出错 将数据依次赋给元素将数据依次赋给元素 b00 , b01 b12 四、二维数组元素的援用方式四、二维数组元素的援用方式数组名数组名下标下标1下标下标2b02 = b10+b0

16、0-b02;4 132_数组元素可以出如今表达式中，也可以被赋值数组元素可以出如今表达式中，也可以被赋值_援用方式：援用方式：int a34;.a34=4;错错 !留意留意 : (1) 每个下标都要用每个下标都要用 括起来括起来 如如 a 2 1 不能写成不能写成 a 2,1 (2) 下标不要超越定义的范围下标不要超越定义的范围五、二维数组的输入和输出五、二维数组的输入和输出数组的输入和输出只能逐个对数组元素进展操作数组的输入和输出只能逐个对数组元素进展操作字符数组例外字符数组例外int b23,i,j;输入方法：输入方法：输入第输入第i行第行第j列元素：列元素：cinaij;输入整个数组元素

17、：输入整个数组元素：for (i=0;i2;i+)for(j=0;jaij;输出方法：输出方法：输出第输出第i行第行第j列元素：列元素：coutaij;输出整个数组元素：输出整个数组元素：for (i=0;i2;i+)for(j=0;j3;j+)coutaij;六、二维数组程序设计举例六、二维数组程序设计举例例例5.3.4: 有一个有一个3*4的矩阵的矩阵, 编编程求出其中的最大值及其所在程求出其中的最大值及其所在的行号和列号。的行号和列号。52093712610418maxrowcol1212#include void main( ) int i,j,row=0,col=0,max; int

18、 a34=5,2,0,9,3,7,12,6,10,4,1,8; max=a00; for (i=0;i3;i+) for (j=0;jmax) max=aij; row=i; col=j ; coutmax=maxendl; coutmax=arowcolendl;输出输出:max=12max=a12例例5.3.5: 将一个矩阵进展转置将一个矩阵进展转置(即原来的行变为列即原来的行变为列)5209371261041853102740121968#includevoid main( ) int a34,b43,i,j; for(i=0;i3;i+) for(j=0;jaij; for(i=0;i

19、3;i+) for (j=0;j4;j+) bji=aij; for(i=0;i4;i+) for(j=0;j3;j+) coutbijsetw(3); coutendl; 输入数组输入数组a进展矩阵转置进展矩阵转置输出数组输出数组ba02b20a21b125.3* 三维数组的定义和运用三维数组的定义和运用 C+言语可以定义和运用三维及更高维言语可以定义和运用三维及更高维的数组。的数组。 格式：格式： =, 例如：例如：int sP M N;5.4 运用运用typedef语句定义数组类型语句定义数组类型 可以利用可以利用typedef语句先定义出数据类型，再据语句先定义出数据类型，再据此定义出

20、相应的数组变量。此定义出相应的数组变量。 1. 一维数组类型的定义语句一维数组类型的定义语句格式：格式：typedef ； 举例：举例：1typedef int vector10;/定义一个一维数定义一个一维数 据类型据类型vector vector v1,v2; /定义定义vector类型的两个对象类型的两个对象 v1,v25.4 运用运用typedef语句定义数组类型语句定义数组类型 1. 一维数组类型的定义语句一维数组类型的定义语句 (2) typedef char strings80; strings s1, s2=define type; (3) typedef short int

21、arrayN; array a=25,36,19,48,44,50; /假定假定N为为 大于等于大于等于6的某个常数的某个常数5.4 运用运用typedef语句定义数组类型语句定义数组类型 2. 二维数组类型的定义语句二维数组类型的定义语句格式：格式：typedef ；举例举例: (1)typedef int matrix55; matrix mx=0; (2)typedef char nameTable10NN; nameTable nt=“; /或运用等同的或运用等同的0初初始化始化(0为空字符为空字符 (3)typedef double DataTypeM+1N+1; DataType

22、dd=0.0;5.4 运用运用typedef语句定义数组类型语句定义数组类型 注：注：可以是可以是C+言语中预定言语中预定义的任何一种数据类型或用户已定义的任何一种数义的任何一种数据类型或用户已定义的任何一种数据类型。据类型。 如：如：typedef vector vectorSet20; /数组共数组共20行行10列列 vectorSet vs;5.4 运用运用typedef语句定义数组类型语句定义数组类型3.对已有类型定义别名 举例：typedef int inData; inData x,y;5.5.1 5.5.1 数值计算数值计算 书中给出了三个例子，一个是计算个人所得税书中给出了三个

23、例子，一个是计算个人所得税P126(1)P126(1)，二是进展矩阵求和，二是进展矩阵求和P128(2)P128(2)，三，三是按月进展公司产值计算，都具有代表性是按月进展公司产值计算，都具有代表性 P128(2)P128(2)5.5 数组的运用数组的运用5.5.2 5.5.2 统计统计 书中给出了两个例子，一是统计每个候选人的书中给出了两个例子，一是统计每个候选人的选票选票P130(1)P130(1)，二是统计每个用电区间的居民户，二是统计每个用电区间的居民户数数:P130(1):P130(1)5.5.3 5.5.3 排序排序 书中引见了两种方法：选择排序和插入排序书中引见了两种方法：选择排

24、序和插入排序(P132 P133(P132 P133见后见后) )5.5.4 5.5.4 查找查找 书中引见了两种方法：顺序查找不要求数书中引见了两种方法：顺序查找不要求数组元素有序陈列组元素有序陈列P134(1)P134(1)和二分查找要求数组和二分查找要求数组元素有序陈列元素有序陈列P(1)P(1)5.5.1 5.5.1 数值计算数值计算 例例5-1-15-1-1 P126(1)P126(1)计算个人所得税计算个人所得税 我国目前对个人工资月收入征收所得税我国目前对个人工资月收入征收所得税的方法如表的方法如表5-15-1所示，编一程序，根据一个所示，编一程序，根据一个人的工资月收入计算出应

25、交纳的税额和税人的工资月收入计算出应交纳的税额和税后所得的金额。后所得的金额。表5-1 个人月收入所得税表级数 级距 税率（%） 级数 级距 税率（%）1 1600元及以下部分 06 21 60041 600元之间 25 部分2 16002100元之间部分 57 41 60061 600元之间 30 部分 3 21003600元之间部分 108 61 60081 600元之间 35 部分4 36006600元之间部分 159 81 600101 600元之间 40 部分 5 660021 600元之间部分 2010 101 600元以上部分 45例例5-1-1 5-1-1 计算个人所得税计算个

26、人所得税 分析：每一级的级距上界10级上界用1e9来表示,设一0级，上界设为0构成一个数列a；每一级税率组成一个数列b。 a=(0,1600,2100,3600,6600,21600,41600,61600,81600, 101600,1e9) b=(0,0,0.05,0.10,0.15,0.20,0.25,0.30,0.35,0.40,0.45) 假设用x表示一个人的工资月收入，用i表示x所对应的级数，用y表示工资月收入为x应交纳的税额，那么y的计算公式为：jjijjiibaabaxy)()(1111其中101i例例5-1-1 5-1-1 计算个人所得税计算个人所得税#includecons

27、t int N=11;void main()double aN=0,1600,2100,3600,6600,21600,41600,61600,81600,101600,1e9;double bN=0,0,0.05,0.10,0.15,0.20,0.25,0.30,0.35,0.40,0.45;double x,y;coutx;int i,j;for(i=1;iN;i+) if(x=1;j-) y+=(aj-aj-1)*bj;cout月工资所得税：yendl;cout税后实发金额：x-yendl;例5-1-2P128(2) 求两矩阵和 知两个矩阵知两个矩阵A和和B如下，编一程序计算出它如下，编

28、一程序计算出它们的和。们的和。2- 4- 16- 8 23 5- 7A7- 2- 52 8 29- 6 3B例5-1-2P128(2) 求两矩阵和#includeconst int N=3;void main()int aNN=7,-5,3,2,8,-6,1,-4,-2;int bNN=3,6,-9,2,-8,3,5,-2,-7;int i,j,cNN;for(i=0;iN;i+) /计算矩阵计算矩阵C for(j=0;jN;j+)cij=aij+bij;例5-1-2P128(2) 求两矩阵和for(i=0;iN;i+) /输出矩阵输出矩阵Cfor(j=0;jN;j+)coutsetw(5)c

29、ij;coutendl;例5-1-3P128(2)按月进展公司产值计算 例例5-1-3 有一家公司，消费五种型号的有一家公司，消费五种型号的产品，上半年各月份的产量如表产品，上半年各月份的产量如表5-2所示，所示，每种型号产品的单价如表每种型号产品的单价如表5-3所示，编一程所示，编一程序计算出该公司上半年的总产值。序计算出该公司上半年的总产值。型型号号产产量量月月份份TV-29TV-34TV-37TV-40TV-46一一438269738624513二二340420572726612三三455286615530728四四385324713594544五五402382550633654六六42

30、4400625578615表表5-2 产量统计表产量统计表表5-3 单价表型号型号单价（元）单价（元）TV-291500TV-342550TV-373640TV-405200TV-467360例5-1-3P128(2)按月进展公司产值计算#includevoid main()int b65=438,269,738,624,513,340,420,572,726,612,455,286,615,530,728,385,324,713,594,544,402,382,550,633,654,424,400,625,578,615; int c5=1500,2550,3640,5200,7360;d

31、ouble d6=0;double sum=0;例5-1-3P128(2)按月进展公司产值计算int i,j;cout.precision(10); /使输出最多保管10位数字精度，默以为6 位for(i=0;i6;i+)for(j=0;j5;j+) /计算出第i+1月份的产值di+=bij*cj;couti+1月份：di元n; /输出第i+1月份的产值sum+=di; /把第i+1月份的产值累加到sum中coutendl“总产值：sum“元endl; /输出上半年总 产值5.5.2 统计统计 例例5-2-1P130) 假定有一个协会在换届选举中由全领会员无记假定有一个协会在换届选举中由全领会

32、员无记名投票直选主席，共有名投票直选主席，共有5名侯选人，每个人的代号名侯选人，每个人的代号分别用分别用1、2、3、4、5表示，每名会员填写一张选表示，每名会员填写一张选票，假设赞同某名候选人那么在其姓名及代号后票，假设赞同某名候选人那么在其姓名及代号后打上对号即可，当然每张选票只能有一个对号，打上对号即可，当然每张选票只能有一个对号，否那么无效。编一程序根据一切选票统计出每位否那么无效。编一程序根据一切选票统计出每位候选人所得票数，其中每张选票上所写候选人的候选人所得票数，其中每张选票上所写候选人的代号由键盘输入，当输入完一切选票后用代号由键盘输入，当输入完一切选票后用-1作为作为终止数据输

33、入的标志。终止数据输入的标志。 分析：设一个一维数组分析：设一个一维数组a6代表候选人，下标代表候选人，下标为为0不用，下标不用，下标1，2，3，4，5分别代表候选人分别代表候选人15。例例5-2-1P130)#includevoid main()int i,a6=0; /作为统计而运用的数组，每个元素初始值作为统计而运用的数组，每个元素初始值为为0couti;while(i!=-1) if(i=1 & ii;for (i=1;i=5;i+) couti: aiendl;例例5-2-2P131) 某研讨机构对我国职工工资情况进展某研讨机构对我国职工工资情况进展调查，把工资划分为调查，把

34、工资划分为11个区段，每隔个区段，每隔1000为一个区段，即为一个区段，即1999为第为第1区段，区段，10001999为第为第2区段，区段，10 000及以上为及以上为第第11区段。编一程序，首先把调查得到的区段。编一程序，首先把调查得到的一批职工的工资数据输入到一个数组中，一批职工的工资数据输入到一个数组中，然后分别统计出每个区段内的职工人数及然后分别统计出每个区段内的职工人数及占总职工数的百分比。占总职工数的百分比。例例5-2-2P131) 分析：用c11表示11个区段，用aN保管N个职工的工资，N为一个符号常量。 先定义aN并输入各元素值，工资小于等于0那么终了输入；接着c11初始元素

35、值都为0，依次读取aN中各元素值，对1000整除确定出相应的统计区段，使c数组中相应的元素值增1；最后计算出百分比并输出。例例5-2-2P131)#includeconst int N=100; /假定假定N的值为的值为100void main()double aN;int i=0; double x;coutx;if (x=N) cout数据输入终了！数据输入终了！n;break;ai+=x;附录经过程序查看i+及while循环终了后的i例例5-2-2P131)int c11=0; /初始化初始化c数组中的每个元素值为数组中的每个元素值为0int k=i-1; /k的值为的值为a数组中保管的

36、最后一个工资的下标值数组中保管的最后一个工资的下标值for(i=0;i=k;i+) if(ai10000) cint(ai)/1000+;else c10+;for(i=0;i10;i+) couti*1000i*1000+999:;coutci, int(ci*1.0/(k+1)*100)%n;cout10000及以上：及以上：;coutci, int(c10*1.0/(k+1)*100)aj+1真假aj aj+1/*排序排序*/for (i=0; iN-1; i+)for ( j=0;jaj+1) t =aj; aj=aj+1; aj+1=t;前往趟每趟比较次数#include#defin

37、e N 5void main()int i,j,aN,t;for(i=0;iai;for(i=0;iN;i+)/*输出*/coutai ;coutn;/*排序排序*/for (i=0;iN-1;i+)for(j=0;jaj+1)t=aj; aj=aj+1; aj+1=t;for(i=0;iN;i+) /*输出输出*/coutai ; coutn;源程序源程序: 例例5.5.1 (2)选择法排序选择法排序 特点：比较后不立刻互换元素，而是记下其位置并特点：比较后不立刻互换元素，而是记下其位置并在每一轮比较终了后和在每一轮比较终了后和a互换互换 首先，比较的元素不同，以降序为例，是当前元素首先，比

38、较的元素不同，以降序为例，是当前元素与上次比较后的最大元素进展比较，因此，在进展比较与上次比较后的最大元素进展比较，因此，在进展比较之前，要有一个初始化最大元素的过程之前，要有一个初始化最大元素的过程 其次，确定终了的元素的互换是在每一轮完成后进其次，确定终了的元素的互换是在每一轮完成后进展的，而不是在比较后进展的展的，而不是在比较后进展的 再次，互换元素的不同，为再次，互换元素的不同，为ai和和aiMax举例：例举例：例5.5.2原始数据：原始数据： 3，5，7，9，4 要求：降序要求：降序第一轮比较，初始化设最大元素下标为第一轮比较，初始化设最大元素下标为 k03579k=0 3579 k

39、=13579 k=23579k=3k=3a(i) 与与 a(k)交换的结果交换的结果:9573/*设置变量设置变量k用以存储当前最大数的下标用以存储当前最大数的下标*/#include void main( ) int a5,i,j,k,t; for ( i=0;iai; for ( i=0;i4;i+) k=i; for ( j=i+1;j5;j+) if (akaj ) k=j ; if (k!=i) t=ai; ai=ak; ak=t; for ( i=0;i5;i+) coutai ; coutendl;源程序源程序:例例5.5.2例5-3-1P132)选择法排序 知有10个常数为42

40、、65、80、74、36、44、28、65、94、72，编一程序，采用选择排序方法，按照从小到大的顺序输出。例5-3-1P132)选择法排序#include const n=10;int an=42,65,80,74,36,44,28,65,94,72;void SelectSort() /选择排序算法选择排序算法int i,j,k;for(i=1;in;i+) /进展进展n-1次选择和交换次选择和交换k=i-1; /给给k赋初值赋初值例5-3-1P132)选择法排序for(j=i;jn;j+) /选择出当前区间内的最小值选择出当前区间内的最小值akif(ajak) k=j;int x=ai-

41、1; ai-1=ak; ak=x; /交换交换ai-1与与ak的值的值void main()SelectSort(); /调用函数对数组调用函数对数组an进展选择排序进展选择排序for(int i=0;in;i+) coutai ;/依次输出数组依次输出数组an中中的每个元素值的每个元素值coutendl;注：不同把注：不同把“int x=ai-1; ai-1=ak; ak=x; 这条语句中的这条语句中的i看成看成j。例5-3-2P133)插入法排序 知有10个常数为42、65、80、74、36、44、28、65、94、72，编一程序，采用插入排序方法，按照从小到大的顺序输出。 思绪：将数组a

42、n中的元素看成一个有序表和一个无序表，开场有序表只需一个元素a0，无序表中有a1an-1个元素，从无序表中每次取出第一个元素插入有序表的适宜位置，循环进展这一步骤，经过n-1次插入过程后整个数组就是一个有序表。 例5-3-2P133)插入法排序#include const n=10;int a10=42,65,80,74,36,44,28,65,94,72;void InsertSort() /插入排序算法插入排序算法int i,j,x;for(i=1;i=0;j-) /为为x顺序向前寻觅插入位置顺序向前寻觅插入位置if(xaj) aj+1=aj;/*元素值后移元素值后移*/ else bre

43、ak;aj+1=x; /将将x插入已找到的插入位置插入已找到的插入位置void main()InsertSort(); /调用函数对数组调用函数对数组an进展选择排序进展选择排序for(int i=0;in;i+) coutai ;/依次输出数依次输出数组组an中的每个元素值中的每个元素值coutendl;2.在有序数组中插入一个数后使原数组依在有序数组中插入一个数后使原数组依然有序然有序例如：例如：3 5 7 12 18， 将将b=10插入插入步骤：步骤：(1)要找到要找到b在数组中的位置在数组中的位置(2)给给b让位置让位置(3)将将b放到该位置上放到该位置上3571218(2)35712

44、1218(3)for(i=0;ib)break;for(j=4;j=i;j-) aj+1=aj;ai=b;121810(1)3571218a0a1a2a3a4a5程序见例5.5.3例5.5.3#include const n=5;int a5=3,5,7,12,18;void main()int i,j,b=10;for(i=0;ib)break;for(j=4;j=i;j-) aj+1=aj; ai=b; for(i=0;i6;i+) coutai ; coutendl;3 5 7 10 12 18， 将将b=10删除删除步骤：步骤：(1) 要找到要找到b在数组中的位置在数组中的位置(2)

45、后面的数组元素依次前移后面的数组元素依次前移,覆盖该位置覆盖该位置上的数组元素即可实现删除上的数组元素即可实现删除3.在有序数组中删除一个数在有序数组中删除一个数例例5.5.4357101218(1)357101218(2)357121218for(i=0;i6;i+)if(ai=b)break;101218for(j=i;j5;j+) aj=aj+1;例5.5.4#include const n=5;int a5=3,5,7,10,12,18;void main()int i,j,b=10;for(i=0;i6;i+)if(ai=b)break;for(j=i;j5;j+) aj=aj+1;

46、 for(i=0;i5;i+) coutai ; coutendl; 是对有序数列进展查找的一种高效查找方法，其根本思想是逐渐减少查找范围，采取半分作为分割范围可使比较次数最少. 比较过程:设数列已做降序排序处置 设置三个变量,分别代表数组序列 s 的Top,Bottom和Middle位置,其中Middle=(Top+Bottom)/2,进展以下判别1 3 4 6 8 10 12 15 18 20 25 BottomTopMiddleX = 155.5.4 查找查找1 1顺序查找顺序查找2 2折半查找法：对有序数组折半查找法：对有序数组程序见例5-4-1(P134) 例5-4-2P)1顺序查找

47、顺序查找 例5-4-1(P134) 假定在一维数组a10中保管着10个整数42、55、73、28、48、66、30、65、94、72，编一程序从中顺序查找出具有给定值x的元素，假设查找胜利那么前往该元素的下标位置，否那么阐明查找失败前往-1。例5-4-1(P134)#includeconst int N=10; /假定把数组中保管的整数个数用符号常量N表示int SequentialSearch(int a,int n,int x) /从数组an中顺序查找值为x的算法for(int i=0;in;i+)if(x=ai) return i; /查找胜利前往元素ai的下标值return -1; /

48、查找失败前往-1思索：第3行后面加上“;，会怎样？例5-4-1(P134)void main() int aN=42,55,73,28,48,66,30,65,94,72;int x,y;while(1) coutx;if(x0) cout程序运转终了！n;return;y=SequentialSearch(a,N,x); /前往元素下标或-1赋给yif(y=-1) cout查找x失败！endl;else cout查找x胜利！下标为yendl;2折半查找法二分查找：对有序数组折半查找法二分查找：对有序数组例5-4-2P) 假定一维数组aN中的N个元素是一个从小到大顺序陈列的有序表，编一程序从a

49、中二分查找出其值等于给定值x的元素。例5-4-2P)#includeconst int N=10; /假定把数组中保管的整数个数用假定把数组中保管的整数个数用符号常量符号常量N表示表示int BinarySearch(int a,int n,int x) /从数组从数组an所存的有序表中二分查找值为所存的有序表中二分查找值为x的算的算法法int low=0, high=n-1; /定义并初始化区间下界和定义并初始化区间下界和上界变量上界变量int mid; /定义保管中点元素下标的变量定义保管中点元素下标的变量例5-4-2Pwhile(low=high) /进展二分查找的循环过程进展二分查找的

50、循环过程mid=(low+high)/2; /计算出中点元素的下标计算出中点元素的下标if(x=amid) return mid; /查找胜利前往查找胜利前往else if(xamid) high=mid-1; /修正修正high得到得到左区间左区间else low=mid+1; /修正修正low得到右区间得到右区间return -1; 例5-4-2Pvoid main()int aN=12,26,37,45,48,52,60,66,73,90; /定义数定义数组组aN并初始化并初始化int x,y;while(1) coutx;if(x0) cout程序运转终了！程序运转终了！n;retur

51、n;y=BinarySearch(a,N,x); /前往元素下标或前往元素下标或-1赋给赋给yif(y=-1) cout查找查找x失败！失败！endl;else cout查找查找x胜利！胜利！下标为下标为yendl;思索：数组改为无序数组结果会怎样？5.6 字符串字符串二、字符串及字符串终了标志二、字符串及字符串终了标志四、字符数组的输入和输出四、字符数组的输入和输出七、字符串处置函数七、字符串处置函数八、字符数组程序运用八、字符数组程序运用一、字符数组的定义一、字符数组的定义 三、字符数组的初始化三、字符数组的初始化五、利用二维数组存储字符串五、利用二维数组存储字符串六、二维数组的输入输出六

52、、二维数组的输入输出一、字符数组一、字符数组用来存放字符数据的数组为字符数组。用来存放字符数据的数组为字符数组。char c10； char c10=k, , A, m, , K, a, p, P, y ;假设初值个数小于数组长度，剩余元素自动定为空字符假设初值个数小于数组长度，剩余元素自动定为空字符 char c12=c, , p, r, o, g, r , a, m;cprogram 000int c10；_定义定义_初始化初始化二者存储空间不二者存储空间不同同#includevoid main()char c12=c, , p, r, o, g, r , a, m;int i;for(i

53、=0;i12;i+)cout第i个元素为ciendl;二、字符串和字符串终了标志二、字符串和字符串终了标志_ C+中没有专门的字符串变量中没有专门的字符串变量, 因此字符串存放因此字符串存放在字符数组中在字符数组中, 字符串以字符串以“0作为终了标志作为终了标志_字符串字符串: 由假设干个有效字符组成的序列由假设干个有效字符组成的序列 _ 有效字符包括字母有效字符包括字母, 数字数字, 公用字符公用字符, 本义字符本义字符 _ 如如 : “bfer “a45-7 “mtkn例例 : char c5 ; c0=O ; c1=K ; c2=! ;O K!O K! 0 c0=O; c1=K; c2=

54、!; c3=0 ;留意留意 : 字符数组与字符串并不一样字符数组与字符串并不一样阐明：阐明：p注：一个字符串的长度等于双引号内一切字符长度注：一个字符串的长度等于双引号内一切字符长度之和。每个之和。每个ASC码字符或本义字符的长度为码字符或本义字符的长度为1，每个区位码如汉字的长度为每个区位码如汉字的长度为2。 特殊地，当一个字符串不含有任何字符时，称特殊地，当一个字符串不含有任何字符时，称为空串，其长度为为空串，其长度为0，是一个空串。一个空串是一个空串。一个空串和一个空格串是不同的，空串的长度是和一个空格串是不同的，空串的长度是0，空格串，空格串的长度是的长度是1。 coutc0c1c2

55、; for ( i=0 ; i ci ;2. 整个数组的输入输出整个数组的输入输出,即按数组名输入即按数组名输入输出输出 (仅用于字符数组仅用于字符数组)，因数组名本身，因数组名本身代表数组的首地址代表数组的首地址留意留意 : (1) 输入、输出字符串时不包括输入、输出字符串时不包括“ (2) cin输入时系统不断读取字符输入时系统不断读取字符,直到遇直到遇“空格，空格，“Tab键和键和“回车符为止。例如：输入数据回车符为止。例如：输入数据 hello world C数组中内容为数组中内容为hello 3经过键盘输入的字符串不能运用转移字符。经过键盘输入的字符串不能运用转移字符。p四、字符数组

56、的输入和输出四、字符数组的输入和输出coutc;四、字符数组的输入和输出四、字符数组的输入和输出 3.字符数组输出 运用不仅可以直接输出字符数组中保管的字符串，而且可以直接输出一个字符串常量，即用双引号括起来的字符串。如：cout“x+y=“x+yendl;五、利用二维数组存储字符串 利用二维数组可以同时保管假设干个字符串，最多能保管的字符串个数等于该数组的行下标数。 例如：(1) char a74=“SUN,MON,TUE,WED,THU, FRI,SAT;(2) char b78=“well,good,middle,pass,bad; char b610=“int,double,char;

57、 Char d1020=;六、二维数组的输入输出 1、二维字符数组的输入、二维字符数组的输入 const int N=10; char wN30; for (int i=0;iwi; 2、二维字符数组的输出、二维字符数组的输出 for (i=N-1;i=0;i-) coutwiendl;七、字符串函数七、字符串函数否那么前往否那么前往NULL(即数值即数值0)#include #include void main()char st130,st240,st370;int l1,l2,a;cinst1st2; /*INPUT*/l1=strlen(st1); /*strlen*/l2=strlen

58、(st2);coutl1=l1tl2=l2n;a=strcmp(st1,st2);/*strcmp*/couta0)coutst1st2n;else if (a=0) coutst1=st2n;else coutst1st2n;cout(strcat(st1,st2)n; /*strcat*/coutst1n;coutstrcpy(st3,st2)n; /*strcpy*/coutst3n;例例5.6.1：字符串函数的运用：字符串函数的运用例例5.6.1：字符串函数的运用：字符串函数的运用八、字符数组程序运用八、字符数组程序运用v 字符串的长度字符串的长度v 逆序逆序v 字符串函数字符串函数_

59、例例5.6.2：求字符串长度：求字符串长度(选学选学扫描数组扫描数组,只需不是只需不是0,计数器就加计数器就加1源程序源程序:#includevoid main()int i;char s50;cins;for (i=0;i50& si!=0; i+) ;coutLength of s is in ;ac d0bifor (i=0; i50& si+ != 0 ;) ;ii=0#include#includevoid main() int i, j=0; char c10,t; cinc; int l=strlen(c); for(i=0, j=l-1;ij;i+, j-)t=

60、ci;ci=cj;cj=t; cout字符串长度字符串长度:l,逆序后的字符逆序后的字符串串:cs;for( i=0 ; i10&si!=0; i+) ;coutstrlen=in;for ( j=0;ji/2;j+) t=sj;sj=si-1-j;si-1-j=t;coutsn;源程序源程序2:(选学选学_字符串函数字符串函数/*例例5.6.4： STRCAT*/#includevoid main() int i,j; char s140,s250; cins1s2; for( i=0;i40&s1i!=0;i+); for( j=0;j50&s2j!=0;j+)s1i+=s2j; s1i=0;/*s1i=s2j;*/