复合数据类型.ppt

单击此处编辑母版标题样式,第,4,章,数组,4.1,一维数组,4.2,指针数组,4.3,二维数组,4.4,数组作函数参数,4.5,动态存储,4.6,字符数组与字符串,小结,4.7,结构,(,放在第,5,章,),4.,8 string,类,(,略,),4.1,一维数组,若干类型相同的相关数据凑到一起，就是数组,;,用途,:,如矩阵运算，表格数据等,说明格式为：,类型,标识符,表达式,;,4.1.1,一维数组定义与初始化,4.1.1,一维数组与初始化,数组元素类型,数组名,存储地址,表示数组大小的常量或者常量表达式,表示数组大小的表达式中可以包括常量、常变量和符号常量，但不能包含变量。也就是说数组的大小不依赖于程序运行过程中变量的值,数组大小最好用宏来定义，以适应未来可能的变化,#define,SIZE 10,int,aSIZE,;,int n;,cin,n;/,输入,a,数组的长度,int a n;/,企图根据,n,的值决定数组的长度,4.1.1,一维数组定义与初始化,例如,const,int,N=20;,const,int,M=40;,const,int,MaxStringSize,=80;,const,int,MaxListSize,=1000;,int,A,10,;,char,B,MaxStringSize,;,float,C,M*N,;,int,Values,MaxListSize,;,A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,数组,A,C0,C1,C2,C3,C4,：,数组,C,B0,B1,B2,:,:,B11,B12,B13,:,:,数组,B,4.1.1,一维数组与初始化,int,a10;,定义了一个有,10,个,int,类型元素的数组,a,的类型可以看作,int,10,（只是看作，语法并不允许这么定义：,int,10 a,）,int,a2010;,定义了一个有,20,个,int,10,类型元素数组,a0,、,a1,a9,的类型是,int,10,，所以,a00,、,a01,a199,的类型是,int,int,a302010;,这个呢？,这种特性决定了数组元素在内存的分布规律，也解释了数组的很多语法现象,从,“,类型的角度,”,理解数组,4.1.1,一维数组定义与初始化,与普通变量一样，数组定义后的初值仍然是随机数，一般需要我们来初始化,例,：,int,a 5 =1,3,5,7,9;,int,b1 5 =0 ;,int,b2 5 =1,2,3,;,int,c =1,2,3,4,5,6,7 ;,int,d 5 =1,2,3,4,5,6,7 ;,/,各元素分别赋初始值,/,全部元素初始化为,0,/b23,b24,自动赋 0,/,自动定义数组长度为,7,/,错误，初始化数据过多,/,例,4-1,数组测试,#include,void main(),int,a 5 =1,3,5,7,9 ;,for(,int,i=0;i 5;i+),cout,a i ends;,cout,endl,;,static,int,b 5 =1,2,3;,for(i=0;i 5;i+),cout,b i ends;,cout,endl,;,int,c =1,2,3,4,5,6,7 ;,for(i=0;i,sizeof,(c)/,sizeof,(,int,);i+),cout,c i ends;,cout,endl,;,/,声明数组,a,并初始化,/,输出数组,a,的全部元素值,/,声明静态数组,b,并初始化,/,输出数组,b,的全部元素值,/,声明数组,c,，,初始化，默认长度,7,计算数组长度的方法,访问格式：,数组名,表达式,4.1.2,一维数组访问,1,以下标方式访问数组,4.1.2,一维数组访问,数组的地址,下标,表示访问数组的第几个元素,数组的下标都是从,0,开始,范围是,0N-1,其中,N,为数组大小，,C,并不提供,下标有效性检查,下标越界是大忌！,使用大于最大下标的下标，将访问数组以外的空间。那里的数据不是我们所想定的情况，可能带来严重后果,对于不知道大小的数组，可以用,sizeof,(,数组,)/,sizeof,（数组类型）,的方法来计算数组的大小,数组中的元素存放在内存里，你想读的是某个元素，结果却读过头,(,数组元素在内存中的存储位置,),了，很可能读到了另一个变量的头上。这就造成了越界。,数组就像一排的宿舍吗？假设有,5,间，你住在第,2,间；如果你晚上喝多了，回来时竟然一头撞入第,6,间,这第,6,间会是什么？,.,数组下标越界的问题,存储器在保存数据时并不关心数据的类型,完全以二进制方式工作,我们向计算机发出的指令说明了某块内存里数据的类型,一块内存内保存着,(61 62 63 64),16,以,char,类型看待每个字节：,abcd,以,double,类型看待每个字节：,16777999408082104000000.000000,以,int,类型看待每个字节：,1684234849,“类型”本不存在,.,#include,void main(),const,int,N=5;,const,int,M=10;,char B M;,int,A N;,for(,int,i=0;i,N;i,+),Ai,=i;,for(,int,j=0;j,M;j,+),Bj,=65+j;,for(,int,k=0;k=,N;k,+),cout,Ak,endl,;,数组下标越界的问题,cout,hex0 x44434241,endl,;,4.1.2,一维数组访问,2,以指针方式访问数组,a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a 0 x0012FF58,0 x0012FF64,/,例,4-3,#include,void main(),int,a 10 =1,3,5,7,9 ;,cout,Address of array a:a,endl,;,cout,Address of element a0:&a0,endl,;,4.1.2,一维数组访问,数组名,是存储空间首地址,4.1.2,一维数组访问,指针和数组的关系,数组名就是指针,(,常指针,),，其类型是数组元素的类型,指针指向一个数组后，指针就是数组。若指针,ptr,已指向数组中的一个元素,，则,ptr+n,指向同一数组中的下,n,个元素；,ptr-n,指向同一数组中的后,n,个元素,4.1.2,一维数组访问,讨论指针运算,int,*,p;,int,n;,p,=,p,+,n,;,表达式根据运算相容规则，,依,int,*,对,n,作,类型转换：,n*,sizeof(int,),字节,只能进行加减和关系运算,(2),只能,同类型,指针之间或指针与整数之间运算,4.1.2,一维数组访问,(1),数组就是指针,a =&a 0,a+1=&a 1,a+i =&a i,*a =a 0,*(a+1)=a 1,*(a+i)=a i,a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,0 x0065FDF0,1,3,5,7,9,0,0,0,0,0,int,a 10 =1,3,5,7,9 ;,则：,4.1.2,一维数组访问,a+1 0 x0065FDE8,1,a 0 x0065FDE4,数组元素的,指针访问方式,/,例,4-2,计算数组元素之和,#include,void main(),int,total=0;,int,intary,10;,for(,int,i=0;i 10;i+),*(,intary,+i)=i;,cout,*(,intary,+i)ends;,cout,endl,;,for(i=0;i 10;i+),total+=*(,intary,+i);,cout,total=total,endl,;,4.1.2,一维数组访问,数组元素的,指针表示方式,4.1.2,一维数组访问,(2),指针指向数组后,就是数组,int,a 10=0,1,2,3,4,5,6,7,8,9;,int,*p;,p=a;,for(int,i=0;i10;i+),cout,pi,endl,;,4.1.2,一维数组访问,/p,的值是,a0,的地址,/,指针作为数组使用,(2),指针指向数组后,就是数组,#include,void main(),int,a 10 =0,1,2,3,4,5,6,7,8,9;,int,*p;/p,是指针变量,p=a;/p,的值是,a0,的地址,cout,*p,endl,;/,输出,a0,的值,p+;/p,指向,a1,cout,*(p+),endl,;,p+=3;/p,指向,a2+3=a5,cout,*p,endl,;,/,p=a;/p,的值是,a0,的地址,for(int,i=0;i10;i+),cout,pi,endl,;/,指针作为数组使用,元素类型是指针的数组,;,数组的元素存储另外一个对象,(,可以是基本数据类型，也可以是另外一个数组,),的地址,4.2,指针数组,语法：,类型,*,标识符,表达式,;,数组名,数组长度,数组元素类型,4.2,指针数组,例如：,int,*pi 3 ;,float*pf 5 ;,char*,ps,10 ;,/,数组元素是关联类型为整型的指针,/,数组元素是关联类型为浮点型的指针,/,数组元素是关联类型为字符型的指针,例,4-4,#include,void main(),int,a=11,b=22,c=33,*pi 3 ;,pi 0 =,pi 1 =,pi 2 =,for(,int,i=0;i 3;i+),cout,*pi i ;,4.2.1,指向基本数据类型的指针数组,数组中存放的是指向基本类型的指针,pi0,pi1,pi2,33,22,11,a,b,c,4.2,指针数组,4.2.1,指向基本数据类型的指针数组,#include,void main(),int,a=11,b=22,c=33,*pi 3 ;,pi 0 =,pi 1 =,pi 2 =,for(,int,i=0;i 3;i+),cout,*pi i ;,pi0,pi1,pi2,&a,&b,&c,*pi0,*pi1,*pi2,33,22,11,a,b,c,4.2.1,指向基本数据类型的指针数组,#include,void main(),int,a=11,b=22,c=33,*pi 3 ;,pi 0 =,pi 1 =,pi 2 =,for(,int,i=0;i 3;i+),cout,*pi i ;,pi0,pi1,pi2,&a,&b,&c,*pi0,*pi1,*pi2,33,22,11,a,b,c,11 22 33,4.2.1,指向基本数据类型的指针数组,#include,void main(),int,a=11,b=22,c=33,*pi 3 ;,pi 0 =,pi 1 =,pi 2 =,for(,int,i=0;i 3;i+),cout,*pi i ;,4.2.2,指向数组的指针数组,数组中存放的是指向其他数组的指针,语法：,类型,(*,标识符,),;,指针数组长度,指针数组名称,指针的关联类型是 类型,如,double2,解读一下,:double(*,pf,3)2,/,例,4-5,#include,void main(),double,aa,2=1.1,2.2 ;,double bb 2=3.3,4.4 ;,double cc 2=5.5,6.6 ;,double(*pf 3)2;,pf 0=&,aa,;,pf 1=,pf 2=,for(,int,i=0;i 3;i+),for(,int,j=0;j 2;j+),cout,*(*pf i +j );,cout,endl,;,pf0,pf1,pf2,&,aa,&bb,&cc,aa0 aa1,bb0 bb1,cc0 cc1,5.5 6.6,3.3 4.4,1.1 2.2,aa,bb,cc,pf,4.2.2,指向数组的指针数组,/,例,4-7,#include,void main(),double,aa,2=1.1,2.2 ;,double bb 2=3.3,4.4 ;,double cc 2=5.5,6.6 ;,double(*pf 3)2,;,pf 0=&,aa,;,pf 1=,pf 2=,for(,int,i=0;i 3;i+),for(,int,j=0;j 2;j+),cout,*(*pf i +j );,cout,endl,;,4.2,指针数组,pf,是长度为,3,的数组,数组元素是指针,pf0,pf1,pf2,&,aa,&bb,&cc,aa0 aa1,bb0 bb1,cc0 cc1,5.5 6.6,3.3 4.4,1.1 2.2,aa,bb,cc,pf,4.2.2,指向数组的指针数组,指针的关联类型,是长度为,2,的浮点数组,double 2,取,对象地址,pf0,pf1,pf2,&,aa,&bb,&cc,aa0 aa1,bb0 bb1,cc0 cc1,5.5 6.6,3.3 4.4,1.1 2.2,aa,bb,cc,pf,4.2,指针数组,4.2.2,指向数组的指针数组,/,例,4-7,#include,void main(),double,aa,2=1.1,2.2 ;,double bb 2=3.3,4.4 ;,double cc 2=5.5,6.6 ;,double(*pf 3)2;,pf 0=&,aa,;,pf 1=,pf 2=,for(,int,i=0;i 3;i+),for(,int,j=0;j 2;j+),cout,*(*pf i +j );,cout,endl,;,访问数组元素,我们军训时站队列，排成,8,行,10,列。如果有同学姿势不标准，这时教官不管同学的名字,(,也不认识,),了，这样喊：“第,2,排第,4,个同学，就说你啦！踢错脚了！”。,老师在上课的经常这样说，请同学们把书翻到*页*行,.,这里的第,2,排第,4,个同学、*页*行均表示二维数组中的元素,同样的情况可以推广到多维数组，但是,3,维以上的数组比较少用到,4.3,二维数组,4.3,二维数组,二维数组,元素是类型相同、长度相同的一维数组,n,维数组,每一个元素是类型相同、长度相等的,n-1,维数组,4.3,二维数组,a00,a01,a02,a03,a10,a11,a12,a13,a20,a21,a22,a23,二维数组,a 0,a 1,a 2,4.3,二维数组,17 19 10 18,23 26 22 29,25 23 28 21,37 39 30 38,43 46 42 49,55 43 36 31,b 0,b 1,b 2,三维数组,4.3.1,二维数组定义与初始化,语法,:,类型 数组名,长度,1 ,长度,2,;,int,a 3 4 ;,/,二维,数组，,3,行,4,列,4.3.1,二维数组定义与初始化,第二维大小,(,行,),第一维大小,(,列,),注意事项,:,定义数组时长度必须是常量或者常量表达式,(1),定义时按维给出初值,4.3.1,二维数组定义与初始化,一维数组可以这样初始化：,int,arr4=0,1,2,3,4;,二维数组也可以：,int,arr23=0,1,2,10,11,12;,int,arr23=0,10;,(2),定义时直接给出初始值列表,4.3.1,二维数组定义与初始化,一维数组可以这样初始化：,int,arr,=0,1,2,3,4;,二维数组是不是也可以,?,：,int,arr,=0,1,2,10,11,12;,二维数组在定义时必须指定第一维大小，第二维大小可以利用初始化列表中的数据个数计算；,N,维数组必须指定第,N-1,维的大小,int,arr23=0,1,2,10,11,12;,或,int,arr3=0,1,2,10,11,12;,3,二维数组在内存中的存储方式,从逻辑上讲，一维数组像一个队列，二维数组像一个方阵，或平面,0,1,2,3,4.3.1,二维数组定义与初始化,00,01,02,03,10,11,12,13,20,21,22,23,30,31,32,03,内存是线性结构，二维数组的成员是连续存储的,存储时按照,”,高维优先存放,”,的原则,。,a 0 0,a 0 1,a 0 2,a 0 3,a 1 0,a 1 1,a 1 2,a 1 3,a 2 0,a 2 1,a 2 2,a 2 3,4.3.1,二维数组定义与初始化,4.3.1,二维数组定义与初始化,a 3 0,a 3 1,a 3 2,a 3 3,二维数组的元素是类型相同、长度相同的一维数组,1.,以下标方式访问二维数组,数组名,表达式,1,表达式,2,4.3.2,二维数组访问,4.3.2,二,维数,组访问,指定二维数组的行下标和列下标，可以访问数组中的任何一个元素,注意：,行下标和列下标不能越界,(0-N-1),/,例,4-7,访问二维数组,#include,#include,void main(),int,a 3 4 ;,int,i,j;,for(i=0;i 3;i+),for(j=0;j a i j ;,for(i=0;i 3;i+),for(j=0;j 4;j+),cout,setw,(5)a i j ;,cout,endl,;,4.3.2,二维数组访问,2,4,6,8,1,3,5,7,9,10,11,12,2.,以指针方式访问二维数组,从一维数组元素的地址关系可知：,数组名代表数组的首地址,任一数组元素的地址，可以用数组名加偏移量表示,。,地址值,元素值,a,&a 0 a 0 *a,a+1&a 1 a 1 *(a+1),a+2&a 2 a 2 *(a+2),:,a+i&a i a i *(a+i),以上结论可以推广到二维数组，二维数组的每一个元素是同构的一维数组,4.3.2,二维数组访问,float a 35,a 0,a 1,a 2,a 0 0,a 0 1,:,:,a 1 0,a 1 1,:,:,a 2 0,a 2 1,:,:,1000,1004,1020,1024,1030,1034,a 0 +1,*a+1,a 1 +1,*(a+1)+1,a 2 +1,*(a+2)+1,a,a+1,a+2,*a,*(a+1),*(a+2),*a0,*(*a+1),*a1,*(*(a+1)+1),4.3.2,二维数组访问,2.,以指针方式访问二维数组,二维数组名,a,表示数组的内存首地址,，这里是,&a0,0,二维数组名,a,是,逻辑上的,一个二级指针,a i,是一级指针,使用时不能直接讲二维数组名赋给一个二级指针变量,例：,int,a 3 5 ,*p2,*p1;,p1=*a;,/OK,p1=a 0 ;,/OK,p2=a;,/Error,p1=a;,/Error,4.3.2,二维数组访问,2.,以指针方式访问二维数组,a 0 0,a 0 1,:,:,a 1 0,a 1 1,:,:,a 2 0,a 2 1,:,:,1000,1004,1020,1024,1030,1034,第,0,行第,1,列元素,地址,a 0+1 *a+1&a0 1,第,1,行第,2,列元素,地址,a 1+2 *(a+1)+2&a1 2,第,i,行第,j,列元素,地址,a i+j *(a+i)+j&ai j,第,1,行第,2,列元素的值,*,(a 1+2)*(*(a+1)+2)a1 2,第,i,行第,j,列元素的值,*,(a i+j)*(*(a+i)+j)ai j,int,a 3 5,的表示形式,:,4.3.2,二维数组访问,2.,以指针方式访问二维数组,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(p=a 0 ;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(p=*a;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(,p=a 0,;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(,p=*a,;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,2.,以指针方式访问二维数组,取第,0,行元素的首地址,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(p=a 0 ;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(p=*a;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j),;,cout,endl,;,2.,以指针方式访问二维数组,第,i,行第,j,个元素,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(,p=a 0,;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(,p=*a,;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,2.,以指针方式访问二维数组,可以改为,p=a,吗？,No!,a,是逻辑上的二级指针，,不能把,a,赋给一级指针变量,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(,p=a 0,;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(,p=*a,;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,2.,以指针方式访问二维数组,可以改为,p=a00,吗？,No!,a00,是数组元素值,不能赋给指针变量,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(,p=a 0,;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(,p=*a,;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,2.,以指针方式访问二维数组,可以改为,p=&a00,吗？,OK!,4.3.2,二维数组访问,2.,以指针方式访问二维数组,注意,对二维数组不同的处理方式,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(p=a 0 ;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(p=*a;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,2.,以指针方式访问二维数组,4.3.2,二维数组访问,/,例,4-9,#include,void main(),int,a3 5=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ;,int,*p;,for(p=a 0 ;p a 0 +15;p+),cout,*p ;,cout,endl,;,for(p=*a;p *a+15;p+),cout,*p ;,cout,endl,;,for(,int,i=0;i 3;i+),for(,int,j=0;j 5;j+),cout,*(a i +j);,cout,endl,;,数组元素作参数的性质与简单变量相同,数组名作参数传递时，固定为指针传递方式，传递的是数组的地址,4.4,数组作函数参数,/,例,4-11,#include,#include,void fun(,int,int,int,);,void main(),int,i,a3=1,2,3 ;,fun(,a0,a1,a2,);,for(i=0;i 3;i+),cout,setw,(4)a i ;,cout,endl,;,void fun(,int,a,int,b,int,c,),a+;b+;c+;,cout,setw,(4)a,setw,(4)b,setw,(4)c,endl,;,return;,传值参数,4.4.1,向函数传送数组元素,当数组作为函数参数时,该参数实际上是一个指针,(,一维数组情况,),或者指针数组,(,多维,),在函数中使用形参数组时，实际是通过指针,(,指针数组,),来访问数组的；无法知道该形参数组的大小,4.4.2,数组名作函数参数,Sizeof(ap)/sizeof(int,),来计算数组大小行不行呢,?,int,sum(,int,*,ap,int,n),int,sum(,int,ap,int,n),int,sum(,int,(*ap)2,int,n),int,sum(,int,ap,2,int,n),数组作为函数参数的使用注意事项,(1),如果在函数中需要知道形参数组的大小，必须数组大小作为另外一个参数传递,.,(2),一维数组作为形参时，可以不指定数组的大小,(,指定了也没有用,);,二维数组作为形参时,需要执行最高维以后的各维大小,4.4.2,数组名作函数参数,int,a10;,sum(a,10);,函数能否正确执行,?,int,sum(,int,ap5,int,n),/,例,4-12,数组元素求和,(,跟踪一下看看,sum,函数中,AP,究竟是数组还是指针,),#include,int,sum(,int,ap,int,n),int,m=0;,for(,int,i=0;i n;i+),m+=,api,;,return m;,void main(),int,a 10 =1,2,3,4,5,6,7,8,9,10 ;,cout,sum=sum(a,10),endl,;,4.4.2,数组名作函数参数,/,例,4-12,数组元素求和,#include,int,sum(,int,ap,int,n),int,m=0;,for(,int,i=0;i n;i+),m+=*,ap,;,ap,+,;,return m;,void main(),int,a 10 =1,2,3,4,5,6,7,8,9,10 ;,cout,sum=sum(a,10),endl,;,4.4.2,数组名作函数参数,/,例,4-12-1,二维,数组元素求和,跟踪一下看看,ap,究竟是什么,?,数组,/,指针,/,指针数组,#include,int,sum(,int,ap,2,int,row,int,row),int,m=0;,for(,int,i=0;i row;i+),for(,int,j=0;j row;j+),m+=,apij,;,return m;,void main(),int,a 34=1,2,3,4,5,6,7,8,9,10,11,12 ;,cout,sum=sum(a,3,4),endl,;,4.4.2,数组名作函数参数,数据排序,选择排序法 冒泡排序法 快速排序,矩阵相乘,4.4.3,应用举例,4.4.3,应用举例,将被排序的数组,R1.n,垂直排列，排序原则是小数据不能在大数据之下。根据该原则，从下往上扫描数组,R,：凡扫描到该原则的数字，就使其向上,“,飘浮,”,。如此反复进行，直到最后任何两个数字都是小者在上，大者在下为止。,(1),初始,R1.n,为无序区。,(2),第一趟扫描,从无序区底部向上依次比较相邻的两个数字，若发现小在下、大者在上，则交换二者的位置。即依次比较,(,Rn,，,Rn-1),，,(Rn-1,，,Rn-2),，,，,(R2,，,R1),；,第一趟扫描完毕时，,“,最小,”,的数字就飘浮到该区间的顶部。,(3),第二趟扫描,扫描,R2.n,。扫描完毕时，,“,次小,”,的数字飘浮到,R2,的位置上,最后，经过,n-1,趟扫描可得到有序区,R1.n,【,动画演示,】,1.,冒泡排序法,1.,冒泡排序法,(P156),/bubble,void bubble(,int,a,int,size),int,i,temp,work;,for(,int,pass=1;pass size;pass+),/,对数组排序,work=1;,for(i=0;i a i+1 ),/,相邻元素比较,temp=a i ;,a i =a i+1 ;,a i+1 =temp;,work=0;,if(work)break ;,4.4.3,应用举例,1.,冒泡排序法,(P156),2,，,5,，,1,，,4,，,3,第一遍：,比较第一对相邻元素：,2,，,5,，序列保持不变,比较后两对元素：,5,，,1,，对调二者。序列变为：,2,，,1,，,5,，,4,，,3,继续比较后两对元素：,5,，,4,对调，于是：,2,，,1,，,4,，,5,，,3,继续比较后两对元素：,5,，,3,对调，于是：,2,，,1,，,4,，,3,，,5,第二遍：,比较第一对相邻元素：,2,，,1,，对调：,1,2,4,3,5,比较后两对元素：,2,，,4,，序列保持不变：,1,2,4,3,5,继续,4,，,3,，对调：,1,2,3,4,5,。,第三编：,.,如果在某次循环中没有发生过一次数据的交换，那就说明后面的元素必然是已经完全有序了，排序过程结束,可以让冒泡排序的效率提高一点点,1.,冒泡排序法,(P156),2.,选择排序法,选择排序的过程分析,(,降序排列,),：,若一组整数放在数组,a0,a 1,an-1,中，,第一趟在,a0,an-1,找出最大值，放在,a0;,第二趟在,a1,an-1,找出最大值，放在,a1;,依此类推，直到从,an-2,和,an-1,之中找最大值,4.4.3,应用举例,想像一下打扑克时检查扑克是否齐的过程,先检查黑桃,先是挑出黑桃,A,、然后是黑桃,K,黑桃,2,，完成后手中的黑桃,13,张已经排好次序了,.,2.,选择排序法,算法描述,：,for(i=0;in-1;i+),*,从,ai,到,an-1,中找最大元素,at,;,把,a t,与,a i,交换,*,细化寻找最大元素算法,:,每一趟寻找中，设变量,t,，,记录当前最大元素下标：,for(j=i+1;j,at,),t=j;,4.4.3,应用举例,/,例,4-15,#include,#include,#include,void sort(,int,int,);,void main(),int,a 10;,srand,(time(0);,/,调用种子函数,for(,int,i=0;i 10;i+)ai=rand()%100;,/,用随机函数初始化数组,for(i=0;i 10;i+),cout,a i ;,/,输出原始序列,cout,endl,;,sort(a,10);,/,调用排序函数,cout,Order1:,endl,;,for(i=0;i 10;i+),cout,a i ;,/,输出排序后序列,cout,endl,;,2.,选择排序法,4.4.3,应用举例,设置随机数函数的种子,随机函数,调用函数进行排序,/sort,void sort(,int,x,int,n),int,max,t;,for(,int,i=0;i n-1;i+),/,对数组排序,t=i;,for(,int,j=i+1;j x t )t=j;,if(t!=i),max=x i ;,/,交换数组元素,x i =x t ;,x t =max;,return;,2.,选择排序法,升序用,比较,4.4.3,应用举例,3.,矩阵相乘,则,C,阵为,m l,的矩阵,设,A,为,m n,的矩阵，,B,为,n l,的矩阵，求矩阵相乘,C=A B,4.4.3,应用举例,=,C,for(,int,i=0;i cm;i+),for(,int,j=0;j,cl,;j+),for(,int,k=0;k,cn,;k+),c i j +=a i k *b k j,cm=3,cl,=3,cn,=2,5,7,8,3,7,4,A,12,3,4,2,6,7,B,5,12,4.4.3,应用举例,#include,/,例,4-17,#include,const,int,m=4,p=3,n=2;,int,amp,bpn,cmn;,int,multimatrix,(const,int,amp,int,arow,int,acol,const,int,bpn,int,brow,int,bcol,int,cmn,int,crow,int,ccol,);,void main(),int,i,j;,cout,Please input A:n;,/,输入矩阵,A,元素,for(i=0;i m;i+),for(j=0;j aij;,cout,nPlease,input B:n;,/,输入矩阵,B,元素,for(i=0;i p;i+),for(j=0;j bij;,if(,multimatrix,(a,m,p,b,p,n,c,m,n),/,调用函数计算矩阵乘积,cout,illegal matrix multiply.n;,return;,for(i=0;i m;i+),/,输出结果矩阵,C,for(j=0;j n;j+),cout,setw,(5)cij;,cout,endl,;,4.4.3,应用举例,int,multimatrix,(const,int,amp,int,arow,int,acol,const,int,bpn,int,brow,int,bcol,int,cmn,int,crow,int,ccol,),if(,acol,!=brow)return 1;,if(crow!=,arow,)return 1;,if(,ccol,!=,bcol,)return 1;,for(,int,i=0;i crow;i+),for(,int,j=0;j,ccol,;j+),for(,int,n=0;n,acol,;n+),c i j +=a i n *b n j,;,return 0;,4.4.3,应用举例,a,b,c,实际上三个指针数组,4.5,动态存储,程序的内存区域,代码区,(code area),全局数据区,(data area),堆区,(heap area),栈区,(stack area),存放程序代码,存放程序的全局数据和静态数据,存放程序的动态数据,(,手工分配和释放空间,),存放程序的局部数据,(,自动分配和释放空间,),栈区的大小在,window,中是固定,如果申请的大小超过栈区的剩余空间，将提示,over