第8章数组.ppt

《第8章数组.ppt》由会员分享，可在线阅读，更多相关《第8章数组.ppt（58页珍藏版）》请在三一办公上搜索。

1、第8章 数组,8.1 一维数组的定义、初始化和使用8.2 多维数组的定义、初始化和使用8.3 数组作为函数参数8.4 字符数组8.5 字符串处理函数8.6 数组应用举例作业：3，4，6，12，15,2,8.1 一维数组的定义、初始化和使用,什么是数组？数目固定、类型相同的若干个变量的有序的集合。为什么引入数组？通过数组，可以方便地存储和处理许多同类型数据。,3,1.一维数组的定义,格式：,数据类型 数组名常量表达式;,值必须为正整数,例：int score100;float salary3;bool married2;char name4;,表示元素个数,4,1.一维数组的定义（续）,数组的存

2、储特点：在内存中占据一组连续的存储单元。,.,a0,a1,a2,a9,例：int a10;,.,下标的取值范围：0 数组元素个数-1,5,1.一维数组的定义（续）,注意点：,用常量：const int num=20;int scorenum;,能否用变量？int num=20;int scorenum;,！数组的大小在编译时必须确定，在程序执行过程中不能改变。,6,2.一维数组的初始化,定义数组时，可以给其中的元素赋初值，称为数组的初始化。,例：int arr5=9,8,7,6,5;,数据类型 数组名个数=元素1初值,元素2初值,;,初始化方法,7,2.一维数组的初始化（续）,形式1：对所有元

3、素赋初值。,例如：int a10=0,1,2,3,4,5,6,7,8,9;,8,2.一维数组的初始化（续）,形式1：对所有元素赋初值。,例如：int a10=0,1,2,3,4,5,6,7,8,9;,int a=0,1,2,3,4,5,6,7,8,9;,可省略大小,编译器根据初值表中元素的个数自动确定数组的大小,9,2.一维数组的初始化（续）,形式2：对部分元素赋初值。,例如：int b8=1,2,3,4,5;,只给前面部分元素赋初值时，后面其余元素的初值自动赋为0,10,3.一维数组的使用,使用数组中某一个元素的格式：数组名下标表达式,例如：int a10;a0=1，a9=2;,11,3.一

4、维数组的使用（续）,越界问题若一个数组含有n个元素，访问元素时，必须保证下标表达式的值是从0到n-1之间的整数。如果表达式的值超出该范围，这种现象称为越界。,例如：int a5;a5=3;,数组存储空间之外的内存单元,错误！,12,3.一维数组的使用（续）,两个数组的相互赋值,int a5=1,2,3,4,5,b5;b=a;,for(int i=0;i5;i+)bi=ai;,/错：数组之间不能直接相互赋值。,13,3.一维数组的使用（续）,如何输入数组?,int score5;cin score;,int score5;for(int i=0;i scorei;,14,3.一维数组的使用（续）

5、,如何输出数组?,int a5=1,2,3,4,5;couta;,int a5=1,2,3,4,5;for(int i=0;i5;i+)coutai;,15,4.一维数组的应用举例,例8.1 用一维数组存放前20个斐波那契(Fibonacci)数并输出。斐波那契数的第一和第二个数分别为0和1，从第三个开始，每个斐波那契数是前两个斐波那契数的和。,#includevoid main()int fib20=0,1;/定义数组,并初始化 for(int i=2;i20;i+)/通过循环依次访问数组元素 fibi=fibi-1+fibi-2;/置当前元素为前两元素之和 for(i=0;i20;i+)/

6、输出前20个斐波那契数 coutfibi;,16,例8.2 某学校有若干名学生参加了100米短跑测试，成绩分别为13.6、14.8、12.0、12.7、15.6、13.4、14.9、12.6秒,求出其中最快和最慢的成绩。,#includevoid main()double score=13.6,14.8,12.0,/100米短跑成绩 12.7,15.6,13.4,14.9,12.6,max=score0,/记录当前最慢成绩 min=score0;/记录当前最快成绩 int len=sizeof(score)/sizeof(double);/计算数组大小 for(int i=1;imax)max

7、=scorei;else if(scoreimin)min=scorei;cout最快成绩:min秒,最慢成绩:max秒n;,17,8.2 多维数组的定义、初始化和使用,1二维数组的定义 数据类型 数组名常量表达式1常量表达式2 例:int a34;float data44;,18,理解二维数组,二维数组可以看作一种特殊的一维数组，它的每个元素又是一个一维数组。二维数组在内存中的存储：按行存放。,19,2.二维数组的使用,引用数组元素的一般形式：数组名行标列标访问二维数组的每个元素，一般通过二重循环。例如：int x23;for(int i=0;i2;i+)for(int j=0;j3;j+)

8、xij=i*3+j+1;,20,3.二维数组的初始化,分行给二维数组赋值。int a23=1,2,3,4,5,6;去掉行的界限赋初值。int a23=1,2,3,4,5,6;如果对数组的全部元素都赋初值可以省略第一维的大小。int a3=1,2,3,4,5,6;也可只对部分元素赋初值而省略第一维大小，但应分行赋初值。int b4=3,3,3,1,3;,21,4.二维数组应用举例,例8.3 某超市有4个连锁店，定义二维数组存放各店2006年各个季度的销售额，计算各店一年的销售总额。#include void main()double sales45=0;,22,for(int i=0;isale

9、sij;salesi4+=salesij;cout一季度t二季度t三季度t四季度t总额n;for(i=0;i4;i+,coutendl)for(int j=0;j5;j+)coutsalesijt;,23,8.3 数组作为函数参数,1数组元素作为函数的实参 若函数的形参是普通变量，则调用该函数时可以用数组元素做实参，参数的结合属于按值传递。例8.5 数组元素作为函数的实参。#includeinline int square(int x)return x*x;,24,void main()int a52,i;for(i=0;i5;i+)ai0=i+1;ai1=square(ai0);/数组元素做

10、square函数的实参 for(i=0;i5;i+)coutai0tai1n;,25,2一维数组作为函数的参数,数组名代表该数组所占内存的起始位置值。若一维数组做函数的形参，则调用该函数时，相应的实参用数组名。用数组名作函数实参时，传递给形参的是实参数组所占内存的起始位置值，这样两个数组就合用实参数组的内存单元。,mul函数中,main函数中,合用内存,26,例8.6 设计一个函数，完成数与向量的乘法运算。,#includevoid mul(int a,int size,int n)for(int i=0;isize;i+)ai*=n;void main()int i,x8=1,2,3,4,5

11、,6,7,8;for(i=0;i8;i+)coutxit;coutendl;mul(x,8,2);for(i=0;i8;i+)coutxit;,27,例8.7 设计一个函数，计算一维整型数组元素总和。,#includeint sum(int a，int size)/size为形参数组大小 int total=0;/存放总和，置初值0 for(int i=0;isize;i+)/逐个访问元素 total+=ai;/累加 return total;void main(void)int a=1,2,3,4,5,6,7,8,9,10,b=78,90,98,76,82;cout数组a的元素之和:sum(

12、a,sizeof(a)/4)endl;cout数组b的元素之和:sum(b,sizeof(b)/4)endl;,28,3二维数组作为函数的参数,void Transpose(int a4,int n)for(int i=0;in;i+)for(int j=i;j4;j+)int t=aij;aij=aji;aji=t;,例8.8 设计程序，将一个4行4列的二维数组a中行和列元素互换。,应明确指明列数,此处指定行数无效,需另设参数指定行数,29,8.4 字符数组,字符数组：元素是字符的数组。字符数组初始化：char s13=c,a,r;char s24=c,a,r,0;char s2=“car”

13、;/字符串后自动加0 char s2=“car”;/字符串后自动加00：字符串字符串结束标志。主要用于字符串的处理和输出。,30,字符数组的输入和输出：可整体进行。char s420;cins4;/输入一个字符串存入s4数组 couts4;/输出s4数组中存放的字符串运行时若输入：Jiangsu China 则输出为：Jiangsu 而不是 Jiangsu China注意：cin输入时，若遇空白符，则认为字符串结束。输出时，若遇字符0，则认为字符串结束。,31,函数cin.getline()：用于输入包含空白符的字符串。第一个参数：字符数组名；第二个参数：允许输入的最多字符个数。例8.9 使用

14、函数cin.getline()实现字符串的输入。#include void main(void)char str51;cout输入一行字符串：;cin.getline(str,50);coutstr=strn;,32,8.5 字符串处理函数,字符串的比较、赋值等操作只能用字符串处理函数。字符串处理函数：在头文件string.h中声明。strlen(字符串)：求字符串中第一个 0前的字符个数，不含0。例如：coutstrlen(abcd);/结果为4 coutstrlen(“tv0willn0”);/结果为3 调用该函数时也可用字符数组名做实参。例如：char s1=today;coutstrl

15、en(s1);,33,字符串复制函数 strcpy(字符数组名1，字符数组名2)功能：将字符数组2中第一个0前的字符(包括结束标志）复制到字符数组1中去。例：char a=flower;char b=red0white;strcpy(a,b);coutaendl;/输出结果为red,34,字符串连接函数 strcat(字符数组名1,字符数组名2)功能：将字符数组名2中的第一个0前的字符连接到字符数组名1的第一个0开始的单元中。例如：char s120=note0this,s210=book0s;strcat(s1,s2);couts1endl;/输出结果为notebook,35,字符串比较函数

16、 strcmp(字符串1,字符串2)功能：比较两个字符串，并返回一个int型值。比较的规则从第一个字符开始，依次对字符串1和字符串2对应位置上的字符按ASCII代码的大小进行比较，直至出现一对不同的字符或遇到字符串的结束符0为止。若两个字符串中的字符都相同，则认为两个字符串相等；当两个字符串不等时，以最先出现的两个不同字符的比较结果作为字符串的比较结果。例如：strcmp(“cap”,“cap”)/相等为0 strcmp(“pen”,“pencil”)/小于0 strcmp(“chinese”,“china”)/大于0,36,例8.11 输入三个字符串，按升序排序后输出。#include#in

17、clude void strswap(char a,char b)/交换两个字符串 char t20;strcpy(t,a);strcpy(a,b);strcpy(b,t);void main(void)char s320;couts0s1s2;/输入三个字符串 if(strcmp(s0,s1)0)strswap(s0,s1);if(strcmp(s0,s2)0)strswap(s0,s2);if(strcmp(s1,s2)0)strswap(s1,s2);cout排序后的结果为：n;for(int i=0;i3;i+)coutsin;,37,8.6 数组应用举例,8.6.1 排序 排序：将一

18、个序列，按元素值的大小重新排列成一个有序序列。数据处理的基本操作。升序：元素从小到大降序：元素从大到小常用排序方法：选择排序冒泡排序插入排序,38,1.选择排序法,基本思想(以升序为例)：首先从所有元素中找出最小元素，并将其与序列中的第一个元素交换。此时第一个元素作为新序列的第一个元素，不再参与后续排序。第二次从剩下的元素中找出最小元素，将其与序列中第二个元素进行交换。依次类推，直到待排序序列中只剩下一个元素。,39,图8-6 选择排序过程示意图,40,例8.12 输入10个整数,用选择排序法进行排序(升序)。,void SelectSort(int a,int size)int minInd

19、ex,t;for(int i=0;isize;i+)/i为排序趟数 minIndex=i;/设本趟最小元素的下标初值 for(int j=i+1;jsize;j+)if(ajaminIndex)minIndex=j;/发现更小元素，记录其下标 if(minIndex!=i)/把本趟的最小元素交换至前面 t=ai,ai=aminIndex,aminIndex=t;,每趟最多交换一次,41,#includevoid SelectSort(int a,int size);void main()int a10,i;coutai;SelectSort(a,10);/排序 for(i=0;i10;i+)/

20、输出排序后的数组 coutai;,42,2.冒泡排序法,基本思想(以升序为例)：首先比较序列中第一个元素与第二个元素，若为逆序，则交换两元素，然后比较第二、第三个元素，依次进行下去，直到对最后两个元素进行了比较和交换。这是第一趟排序过程，结果把最大元素交换到最后位置。最后一个元素不再参加排序。然后再从前往后访问剩余元素组成的序列，比较相邻元素，把其中最大元素交换到最后位置。如此继续，直到某一趟未发生任何交换或新序列中只剩下一个元素，排序结束。,43,图8-7 冒泡排序过程示意图,44,例8.13 输入10个整数,用冒泡排序法进行排序(升序)。,void BubbleSort(int a,int

21、 size)int i,j,t,flag;for(i=1;iaj+1)/相邻元素比较和交换 t=aj,aj=aj+1,aj+1=t,flag=1;if(!flag)break;/本趟无交换，说明序列已有序，不必再排序。,45,#includevoid BubbleSort(int a,int size);void main(void)int a10,i;coutai;BubbleSort(a,10);/冒泡排序 for(i=0;i10;i+)/输出排序后的数组 coutai;,46,8.6.2 查找,查找：在序列中寻找某个或某些数据的过程。查找的方法:顺序查找法二分查找法,47,1顺序查找法,

22、顺序查找法的思想：按照从前到后的顺序依次访问序列中的元素，并将其与待查值进行比较，直到找到与待查值相等的元素或序列结束。如果查找至序列结束时，仍未发现与待查值相等的元素，则查找不成功。,48,例8.14 用顺序查找法在输入的10个整数中查找指定值。,#includeint SeqSearch(int a,int size,int key)for(int i=0;isize;i+)if(ai=key)/若找与待查值相等的元素 return i;/则返回其元素的下标 return-1;/查找不成功,返回-1void main()int a=45,89,87,12,34,22,90,77,53,10

23、;if(SeqSearch(a,10,26)!=-1)coutFound!n;else coutNot found!n;,49,2二分查找法,适用条件：有序序列。基本思路：首先比较待查值与序列中中间元素值的大小，如果相等，则查找成功；否则在序列的前半部分和后半部分二者中，选择可能包含待查值的那半部分继续查找。重复上述过程直至找到与待查值相等的元素，或者查找范围的长度小于零表示查找不成功。,50,51,例8.15 用二分查找法在元素呈升序排列的数组中查找指定值。,int HalfSearch(int a,int size,int key)int start=0,end=size-1,mid;/设

24、首、末元素下标 while(startamid)/若待查值大于中间元素，start=mid+1;/取后半部分继续查找 else end=mid-1;/否则取前半部分继续查找 return 1;/未找到,返回-1,52,#includeint HalfSearch(int a,int size,int key);void main(void)int a10,value,n,i;coutai;coutvalue;if(n=HalfSearch(a,10,value)!=-1)cout数组中找到value,是第n+1个元素!n;else cout数组中没有要找的值!n;,53,8.6.3 统计,统计

25、：对序列中的数据进行分析计算，得出一些汇总数据。例如，获得：总和平均值最大值最小值均方差分布在特定范围的数据个数,54,例8.16 一个班级有20名学生，编写程序，从键盘输入所有学生的英语考试成绩，求出全班该门课程的平均成绩。并统计考试成绩优秀（90分以上，包括90分）的学生人数和不及格（60分以下）的学生人数。#includeconst int num=20;void main()int scorenum,/存放20名学生成绩 sum=0,/累计总成绩 HighScoreCount=0,/记录优秀的人数 UnPassedCount=0;/记录不及格的人数,55,for(int i=0;isc

26、orei;/输入一个成绩 sum+=scorei;/累加一个成绩 if(scorei=90)/大于90分 HighScoreCount+;/优秀人数增1 else if(scorei60)/小于60分 UnPassedCount+;/不及格人数增1 cout”平均成绩：”(sum/num)”，优秀人数：”HighScoreCount”,不及格人数：”UnPassedCountendl;,56,8.6.4 字符处理,例8.17 有一封待发的电文，请按以下规律译成密码：AZ az BY by CX cx 即第一个字母变成第26个字母，第i个字母变成第（26-i+1）个字母。非字母字符不变。要求编程

27、实现上述加密功能，输入原文，输出密文，然后解密并显示解密后的效果。,57,#include#includevoid encrypt(char,int);void main(void)char text1024;/定义字符数组，存放字符串 cout输入明文：;cin.getline(text,1024);/输入字符串 int len=strlen(text);/计算字符串长度 encrypt(text,len);/加密 cout密文为：textendl;encrypt(text,len);/解密与加密方法相同 cout解密后为：textendl;,58,/加密函数void encrypt(char str,int size)for(int i=0;i=A/替换成密码字符,