《C课件第六章数组》由会员分享,可在线阅读,更多相关《C课件第六章数组(57页珍藏版)》请在金锄头文库上搜索。
1、C-C-课件课件- -第六章第六章- -数组数组记数器 i=1、总分zf=0i=10?读入一个分数到变量fs中zf=zf+fsavg=zf/10结束开始YN打印zf、avg问题的引入问题的引入 例:输入10个学生某门学科的成绩,求平均成绩。1、当读入下一分数时,前一分数值是否还能找到?2、如何将低于平均成绩的分数打印出来? 在程序设计中存储单个数据时,需要根据数据的类型定义相应的变量来保存。如存储一个整数时需要定义一个整数变量来保存,存储一个实数时需要定义一个单精度或双精度变量来保存,存储含有多个成分的一个记录数据时,需要定义该类型的一个结构变量来保存。 若在程序设计中需要存储同一数据类型的、
2、彼此相关的多个数据时,如存储数学上使用的一个数列或一个矩阵中的全部数据时,显然采用定义简单变量的方法是不行的,这就要求定义出能够同时存储多个值的变量,这种变量在程序设计中称为数组数组(相同类型的若干个元素所组成的有序集合)。 在实际应用中,一组相关的数据之间可能存在着一维关系,也可能存在着二维关系,等等。如下表: 张三70李四80王五90一维数组模型 学科姓名英语计算机张三7090李四8080王五9070二维数组模型概述概述 C+C+数据类型数据类型: 基本类(简单类)字符型/整型/实型/枚举型 构造类(组合类)数组/结构体/共用体 指针类 空类型(void) 基本类型单个出现的变量,每个变量
3、可以代表一个确定的数据(变量值),且具有一定属性。如 static int x,y;但变量间不存在确定的相互关系。 构造类型由基本类型按一定规则组成。其中数组 :由一组有序数据(数组元素)组成,这些数据保存在连续的内存空间,每个元素具有相同类型,因此占有相同大小的存储单元,具有统一数组名,用下标确定其顺序,但可以取各自值。 如 static int a5;其中: 1. 表示a是个数组,而不是一个简单变量a 2. 5表示该数组共有5个元素 3. 元素编号即下标从0开始,a0表示第一个元素,a4表示第5个元素(最后一个) 一般化:假设m和n是常量,则数组am的第一个元素是a0,最后一个元素是am-
4、1;数组amn的第一个元素是a00,最后一个元素是am-1n-1,以此类推。 数组的用处很多。简单例子:要读入某班全体50位同学某科学习成绩,然后进行简单处理(求平均成绩、最高分、最低分) 分析:若用简单变量,需50个不同变量名,如stu1,stu2,stu50,要用很多个cin命令。而用数组,可共用一个cin命令,并利用循环结构读取。同变量一样,数组也必须先定义,后使用。定义内容: 数组名 :必须是合法标示符 类型(存储属性/数据类型) 大小(维数/元素个数) 定义的一般形式: 存储属性 数据类型 数组名常量表达式常量表达式 常量表达式:常量或符号常量,其值必须为正,不能为变量 !如:int
5、 n=5;int an;这样定义是错误的,如下为正确的:int a10,b54; char name8, ch23; static float x8*2+1, table234; #define NUM 40 int aNUM,bNUM+2;数组定义数组定义 数组的初始化数组的初始化 可以在定义数组的同时赋初值,如:int a5=1,2,3,4,5;12345int b23=1,2,3,4,5,6;123456也可写成:int b23=1,2,3,4,5,6; 可以省略第一维数组大小,如: int a =, b3=;省略元素值,如:int x6=1,2,3,4; (x4、x5自动用0补足) 0
6、04321int a5=0; int b32=0;(全部元素初始化为0 )int a3=1,2,3,4,5,6,0;000300520641int a 3=1,2,3,4,5,6,7 ; (思考第一维的大小?)静态/外部数组未初始化,默认初值是0(数值)或0(字符). auto数组未初始化,初值为不可预料的数。只能逐个引用数组元素,不能一次引用整个数组 .引用数组元素要注意下标不要越界(编译程序不检查是否“越界”).引用示例 : a23 a2-12*3-1 ax(x为整型表达式或变量) int a5; for (i=0;i5;i+) (注意下标不要越界) coutai; 数组元素的引用数组元素
7、的引用 用一维数组来处理Fibonicci数列的前20项。f1 = 1 n = 1f2 = 1 n = 2fn = fn-1 + fn-2 n 3voidmain()inti;intf20=1,1;/*f1、f2已知*/for(i=2;i20;i+)fi=fi-1+fi-2;for(i=0;i20;i+)if(i%5=0)coutendl;coutsetw(12)fi;#include#include【例】以下程序的运行结果是什么?#includevoidmain()inta3=1,2,3,4,5,6,0;couta11a21a31;结果:5001 2 31 2 34 5 04 5 06 0
8、06 0 00 0 00 0 0 【例】显示如下图形:1 0 0 0 0 2 1 0 0 0 3 2 1 0 0 4 3 2 1 0 5 4 3 2 1 a55分析:a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24a30 a31 a32 a33 a34a40 a41 a42 a43 a44void main()int a55=1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,i,j; for(i=0;i=4;i+) for(j=0;j=4;j+) coutaij; coutn; 例:读入某班全体50位同学某科学习成绩,
9、然后进行简单处理(求平均成绩、最高分、最低分) 例:找出一个二维数组的鞍点,即该位置上的元素在该行上最大,在该列上最小,也可能没有鞍点.【例】有一34矩阵,编程求其元素最大值并输出其行、列号。 voidvoid main()inti,j,x,y,max;inta4=3,5,8,1,6,9,7,12,-6;max=a00;for(i=0;i3;i+)for(j=0;jmax)max=aij;x=i;y=j;coutmaxisaxy=maxn;358169712-6000 结果:maxisa13=12 用数组元素作函数实参此时可把数组元素看作普通变量(单向值传递).特点:主调函数中的实参数组元素(
10、带下标) 被调函数中的形参普通变量 调用结果:形参值的变化对实参值无影响(二者分占不同内存)数组作为函数参数数组作为函数参数 【例】voidmain()inta=1,2,3,4,5,6;staticintb6=2,3,0,4;inti;sum(int,int,int);for(i=0;i6;i+)sum(ai,bi,i);couta=ai,b=bi;voidsum(intx,inty,intz)x=z;y=z;结果: a=1,b=2 a=2,b=3 a=3,b=0 a=4,b=4 a=5,b=0 a=6,b=0 用数组名作函数实参若int a6;则数组名a表示数组的起始地址.此时,是把实参数组
11、的起始地址起始地址“传给”形参数组 .本质:对应的数组元素(不是形参与实参)共享同一内存单元(所谓“双向的地址传送”).特点:主调函数中的实参数组名(不带下标) 被调函数中的形参数组名或数组定义式 调用结果:两数组同下标者为同值 . 数组作为函数参数数组作为函数参数 【例】voidmain()inta=1,2,3,4,5,6;staticintb6=2,3,0,4;inti;sum(int,int,int);for(i=0;i6;i+)sum(a,b,i);couta=ai,b=bi;voidsum(intx,inty,intz)xz=z+2;yz=z;传址传址abyxxyab结果: a=2,
12、b=0 a=3,b=1 a=4,b=2 a=5,b=3 a=6,b=4 a=7,b=5 例:下面的程序定义了一个3x4的数组,表示3个学生,每个学生有4门成绩,求所有学生中的最好成绩。 int maximum(int4,int,int); void main()int sg34=68,77,73,86,87,96,78,86,90,70, 81,86; cout“the max grade is”maximum(sg,3,4)endl; int maximun(int grade4,int pupils,int tests) int max=0; for(int i=0;ipupils;i+)
13、 for(int j=0;jmax) max=gradeij; return max;字符数组的初始化 char c5=a,b,c; c3和c4自动定为0字符串在内存中以字符数组存放,因此可以用字符串直接初始化字符数组. char c5=“abc”;思考:char c =“abc”; 数组c的数组长度?字符串以字符串结束标志0(即空字符)结束(可以思考A和“A”在内存中存放的区别),因此 char c =“abc”;等价于 char c =a,b,c,0);既数组c的数组长度为4,当然char c5=“abc”;的数组长度仍为5.字符数组和字符串字符数组和字符串 字符数组char c5;的输入
14、法一(逐字符输入):int i; for(i=0;ici;法二(字符串输入):cinc; 注意:此法输入的字符串以空格或回车结束,即输入的字符串不可能包括空格!如输入:abc def回车后,c对应的字符串为“abc”,而不是“abc def”.另外此法输入的字符串串长有可能比数组长度要长,应引起注意!要想输入带空格的字符串,可使用函数cin.get或者cin.getline. 此例对应cin.get(c,6,n) 或者cin.getline(c,6,n)字符数组char c5;的输出法一:int i; for(i=0;i5;i+) coutci;法二:coutc; 输出一个字符串,直到遇到0为
15、止,因此输出的字符串有可能和数组不一样。【例】比较以下字符数组长度是否相同:chara=”ABCD”;charb=“ABCD”;charc=A,B,C,D;(5)(5)(4)【例】下列程序段的运行结果是:chara5=a,b,0,d,0;couta; (ab) 二维数组可以看成特殊的一维数组,这个特殊的一维数组的元素又是一个一维数组。即a34可看成数组长度为3的一维数组,而此一维数组的每个元素又是一个数组长度为4的一维数组。如下图所示:aa0a1a2a00,a01,a02,a03 所以a0对二维数组a来说是元素名,但对一维数组a00,a01,a02,a03来说却是数组名.【例】分析以下程序的运
16、行结果:voidmain()charword310;inti;for(i=0;iwordi;coutwordi-2;运行时,输入:12345(回车)abcdef(回车)ABCDEFG(回车)word0 1 2 3 4 5 0word1 a b c d e f 0word2 A B C D E F G 0结果:abcdef 将一个字符串直接给一个字符数组只能够出现在初始化中,不能够出现在赋值语句中!也不能把一个字符数组直接赋值给另一个字符数组,如:char c5,d5;c=“abc”;d=c;是错误的! 要使用string.h的函数strcpy(to字符数组1,from字符数组2)如:strcp
17、y(c,”abc”); strcpy(d,c);字符串处理函数【例】以下程序的输出结果是 。#include“string.h”voidmain()chars10,sp=”HELLO”;strcpy(s,sp);s0=h;s6=!;couts;H ELL O 0 0 0 0 0hELL O 0 0 0 0 0hELL O 0!0 0 0hELLOhELLO strcat( ) 字符串连接函数形式:strcat(目的字符数组,源字符串);作用:将源字符串连接到目的字符数组后面。函数返回值:目的字符数组的地址。注意:目的字符数组要定义得足够大。 【例】以下程序的输出结果是 _。#includest
18、ring.hvoidmain()chara=abcde;charb=12345;strcat(b,a);couta,b;abcde,12345abcde 【例】以下程序的输出结果是 _。#includestring.hvoidmain()chara80=”AB”,b80=”LMNP”;inti=0;strcat(a,b);while(ai+!=0)bi=ai;cout = 0时,字符串1字符串2;strcmp函数返回值0时,字符串1字符串2; 思考:如何判断str1是否等于str2?要写成 if(strcmp(str1,str2)=0) .不可写成 if(str1=str2) .#includ
19、e“string.h”voidmain()inti;charstr10,temp10=”Control”;for(i=0;istr;if(strcmp(temp,str)0)strcpy(temp,str);couttemp;【例】运行以下程序时,从键盘输入:BOOKCUTGAMEPAGE(表示回车),则运行结果是什么?变量跟踪:tempstr比较i=0ControlBOOK0i=1ControlCUT0i=2ControlGAME0GAMEi=3GAMEPAGE0PAGE 求字符串实际长度可使用string.h的函数strlen(字符数组),它不包括字符串的结束符0.如: char a10=
20、“abcde”; 则strlen(a)=5 ,sizeof(a)=10【例】以下程序段的运行结果是什么?chara=”tr0willn”;coutsizeof(a)tstrlen(a);结果:10 3 数组元素的排序一 输入10个数,用“冒泡法”对10个数排序(由小到大)。“冒泡法”算法:以六个数9、8、5、4、2、0为例。第1趟比较第一次:8、9、5、4、2、0第二次:8、5、9、4、2、0第三次:8、5、4、9、2、0第四次:8、5、4、2、9、0第五次:8、5、4、2、0、9第1趟比较产生第一个最大数:9对剩下的五个数: 8、5、4、2、0进行第2趟比较第一次:5、8、4、2、0第二次:
21、5、4、8、2、0第三次:5、4、2、8、0第四次:5、4、2、0、8第2趟比较产生第二个最大数:8依此类推,便可实现排序。第1趟比较后,剩5个数未排好序;两两比较5次第2趟比较后,剩4个数未排好序;两两比较4次第3趟比较后,剩3个数未排好序;两两比较3次第4趟比较后,剩2个数未排好序;两两比较2次第5趟比较后,全部排好序; 两两比较1次 算法结论:对于n个数的排序,需进行n-1趟比较,第i趟比较需进行n-i次两两比较。for(i=1;in;i+)for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;改进后的算法for(i=1;in;i+)flag=0;for(j=0;jaj+1
22、)t=aj;aj=aj+1;aj+1=t;flag=1;if(flag=0)break;二 输入10个数,用“选择法”对10个数排序(由小到大)。“选择法”算法:以六个数9、8、5、4、2、0为例。第1趟比较第一次:8、9、5、4、2、0第二次:5、9、8、4、2、0第三次:4、9、8、5、2、0第四次:2、9、8、5、4、0第五次:0、9、8、5、4、2第1趟比较产生第一个最小数:0对剩下的五个数: 9、8、5、4、2进行第2趟比较第一次:8、9、5、4、2第二次:5、9、8、4、2第三次:4、9、8、5、2第四次:2、9、8、5、4第2趟比较产生第二个最小数:2依此类推,便可实现排序。算法
23、总结:对于n个数的排序,需进行n-1趟比较,第i趟比较时要将第i+1个开始的元素依次与第i个元素进行两两比较,后者小于前者就进行交换。for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ajai)t=ai;ai=aj;aj=t;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(ajak)k=j;if(k!=i)t=ai;ai=ak;ak=t;改进后的选择排序算法三 插入排序基本思想:(假定从小到大排序)依次从后面拿一个数和前面已经排好序的数进行比较,比较的过程是从已经排好序的数中最后一个数开始比较,如果比这个数,继续往前面比较,直到找到比它大的数,
24、然后就放在它的后面,如果一直没有找到,肯定这个数已经比较到了第一个数,那就放到第一个数的前面。 那么一般情况下,对于采用插入排序法去排序的一组数,可以先选 取第一个数做为已经排好序的一组数。然后把第二个放到正确位置voidmain()inti,j,t,a=12,11,2,3,6,67,89,0,1,3;for(i=1;i=0;j-)if(taj)aj+1=aj;elsebreak;aj+1=t;for(i=0;i10;i+)coutait;四 合并排序基本思想: 将a、b两个数组看成两个队列,比较队首的两个元素,将较小者放入c队列尾部,如果队首的两个元素相等,则先选择a队列首部元素加入c队列尾
25、部。循环执行以上过程,直到a或b队列之一为空,然后将另一个非空队列拷贝到c队列尾部。 inti=0,j=0;while(im&jn)if(ai=bj)ck+=ai+;elseck+=bj+;/注意:因为while循环条件为逻辑表达式,退出循环有多种可能,退出循环后一定要分情况讨论!while(im)ck+=ai+;/如果a队列非空,将a队列剩余元素拷贝至c队列尾部。while(ja(mid)keya(mid)intbinsearch(inta,intn,intkey)intlow=0,high=n-1,mid=(low+high)/2;while(low=high)if(key=amid)returnmid;if(keyamid)low=mid+1;mid=(low+high)/2;return-1;课后练习:试卷汇编 P5T23、26 P15T24、25 P23T24,P24T1,P25T9 P27T12(涉及到指针部分) P32T24 P33T1、3 P41T3 P42T6、7 P51T22,P52T25 P53T3、7结束!结束!