C++课件(南航皮德常)4

1第4章数组皮德常[e-mail]2引言•构造数据类型：由基本数据类型和构造类型，按一定原则组合而成，亦称导出类型。主要包括：数组、指针、结构体、类等。•数组是由单一类型的数据元素组成的有序集合，每个元素采用数组名和下标来表示。•数组可分为一维数组和多维数组34.1一维数组•数组用来存储一组类型相同的值，并且值保存在连续的内存单元中；•4.1.1定义一维数组类型说明符数组名[常量表达式];例如：intdays[7];constintnumDays=5;#defineCOUNT5intworkDay[numDays];doublepay[COUNT];44.1.2引用一维数组元素•通过下标访问元素，例如：days[0]=10;注意：全局数组元素初值为0；局部数组初值不定。思考如下有什么错：intreadings[-1]floatmeasurements[4.5]intsize;cinsize;charname[size];54.1.3数组无越界检查•例如：shortvalues[3];for(intcount=0;count5;count++)values[count]=200;注意：权利与义务是相对的。C++是一个很灵活的语言，给程序员高度自由的同时，也要求你具有高度的责任感，否则系统崩溃的后果自负。64.1.4数组初始化•初始化：在定义数组的同时对元素赋值。(1)全部赋初值，例如：intdays[7]={0,1,2,3,4,5,6};(2)部分元素赋初值，例如：intdays[7]={0,1,2,3};(3)全部数组元素赋初值时，可以不指定长度：intdays[]={0,1,2,3,4};(4)全局/静态数组初值为0。局部动态数组初值不定。【例4.1】用数组求Fibonacci数列的前24项，以及它们的和。intmain(){inti,fib[24]={1,1},sum;sum=fib[0]+fib[1];for(i=2;i24;i++){fib[i]=fib[i-2]+fib[i-1];sum+=fib[i];}for(i=0;i24;i++){coutsetw(10)fib[i];if((i+1)%6==0)coutendl;}coutsetw(10)sum=sumendl;return0;}84.2多维数组•具有两个或两个以上下标的数组称为多维数组;•一维数组对应数学中的向量;•二维数组对应矩阵或一个二维表。二维数组的横向为行，纵向为列。第一个下标称为行下标，第二个下标称为列下标。94.2.1二维数组的定义•例如，定义一个3行4列的二维数组：intmatrix[3][4];104.2.2二维数组的初始化1.按行对二维数组初始化，例如：intmatrix[3][4]＝{{1,2,3,4},{5,6,7,8},{9,10,11,12}};2.将所有数据写在一个花括号内，按数组元素排列的顺序赋初值：intmatrix[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};114.2.2二维数组的初始化3.对部分元素赋初值，例如：intmatrix[3][4]={{1},{5，6},{9，10，11}};4.根据给定的初始化数据，自动确定数组的行数：intmatrix[][4]={1,2,3,4,5,6,7,8,9,10};5.定义数组时可省略行数，但不能省略列数：intmatrix[3][]={1,2,3,4,5,6,7,8,9,10};124.2.3引用二维数组元素•例如，有如下定义：intmatrix[3][4]；正确：matrix[0][0]=matrix[1][2]+matrix[2][3]；错误：matrix[3][4]=5;但不能混淆：intmatrix[3][4]={0};•数组不能整体赋值，例如：intmatrix_A[3][4]={0},matrix_B[3][4];matrix_B=matrix_A；//error134.3数组作函数参数•两种情况：数组元素作函数参数和数组名做参数。4.3.1数组元素作函数参数•数组元素作函数参数与普通变量做函数参数一样，属于单向传值。•【例4.2】采用函数输出一维数组的内容。voidshowValue(intnum);//函数原型intmain(){intset[]={2,8,15,29,45,38,35,90};for(inti=0;i8;i++)showValue(set[i]);return0;}voidshowValue(intnum){coutsetw(5)num;}154.3.2数组名作函数参数•数组名代表数组在内存中的首地址。•数组名做实参的传递方式称为地址传递，本质属于单向传递地址值。•采用数组名作实参和形参时，将实参数组的首地址传递给形参数组，它们将共享空间。•数组名做参数的传递方式，可节省内存空间，提高程序效率。•【例4.3】将set数组的值翻倍。voidshowValue(int[],int);voiddoubleValue(int[],int);intmain(){intset[]={2,8,15,29,45,38,35,90};doubleValue(set,8);showValue(set,8);return0;}voidshowValue(intnums[],intcount){for(intindex=0;indexcount;index++)coutsetw(5)nums[index];}voiddoubleValue(intnums[],intcount){for(intindex=0;indexcount;index++)nums[index]*=2;}174.4常用算法举例【例4.4】线性查找。在长度为n的一维数组中查找值为value的元素，即从数组的第一个元素开始，逐个与被查值value进行比较。若找到，返回数组元素的下标，否则返回-1。constintarrSize=5;intsearchList(intlist[],intnumElems,intvalue);intmain(){inttests[arrSize]={43,87,89,453,238};intresult,x=453;result=searchList(tests,arrSize,x);if(result==-1)cout没有找到:xendl;elsecoutx是第(result+1)个元素;return0;}intsearchList(intlist[],intnumElems,intvalue){for(inti=0;inumElems;i++)if(value==list[i])returni;return-1;}19【例4.5】冒泡排序（按从小到大的顺序对数组元素排序constintarrSize=8;voidgetArray(intarray[],intn);voidbubbleSort(intarray[],intn);voidshowArray(intarray[],intn);intmain(){intvalues[arrSize];getArray(values,arrSize);cout排序前:\n;showArray(values,arrSize);bubbleSort(values,arrSize);cout排序后:\n;showArray(values,arrSize);return0;}voidgetArray(intarray[],intn){srand(time(0));for(inti=0;in;i++)array[i]=rand()%100;}voidbubblesortArray(intarray[],intn){inti,j,t;for(i=0;in-1;i++)for(j=0;jn-1-i;j++)if(array[j]array[j+1]){t=array[j];array[j]=array[j+1];array[j+1]=t;}}voidshowArray(intarray[],intn){for(inti=0;in;i++)coutsetw(5)array[i];coutendl;}22【例4.6】选择排序(以升序为例):冒泡法的改进97652第4趟：79652第3趟：69752第2趟：69572第1趟：62579原数组a[4]a[3]a[2]a[1]a[0]voidselectionSort(intarray[],intn){inti,j,t,minIndex;for(i=0;in-1;i++){minIndex=i;for(j=i+1;jn;j++)if(array[j]array[minIndex])minIndex=j;if(minIndex!=i){t=array[minIndex];array[minIndex]=array[i];array[i]=t;}}}24【例4.7】插入排序（以升序为例）voidinsertSort(inta[],intn)//插入排序{inti,j,k,x;for(i=1;in;i++){x=a[i];for(j=0;ji&&x=a[j];j++)//找位置;for(k=i;kj;k--)//右移a[k]=a[k-1];a[j]=x;}}25【例4.8】利用筛选法求1~100之间的素数。voidprime(inta[],intn){inti,j;for(i=1;in;i++)for(j=i+1;jn;j++)if(a[i]!=0&&a[j]!=0&&a[j]%a[i]==0)a[j]=0;}constintarrSize=100;voidprime(inta[],intn);intmain(){inta[arrSize],i,count;for(i=0;iarrSize;i++)a[i]=i+1;prime(a,arrSize);for(i=1,count=0;iarrSize;i++){if(a[i]!=0){coutsetw(5)a[i];count++;if(count%10==0)coutendl;}}return0;}27【例4.9】二分查找，即折半查找。前提是数组已经排序（假定是非递减排序）。#includeiostream#includeiomanip#includectimeusingnamespacestd;constintarrSize=10;intbinarySearch(inta[],intnumElems,intvalue);voidgetArray(inta[],intn);//产生数组voidselectionSort(inta[],intn);//选择排序voidshowArray(inta[],intn);//输出数组元素intmain(){inta[arrSize],p,x;getArray(a,arrSize);cout排序前：;showArray(a,arrSize);selectionSort(a,arrSize);cout排序后：;showArray(a,arrSize);cout请输入要查找的数：;cinx;p=binarySearch(a,sizeof(a)/sizeof(a[0]),x);if(p=0)cout已找到，下标为:pendl;elsecout无此数xendl;return0;}voidgetArray(inta[],intn){srand(time(0));for(inti=0;in;i++)a[i]=rand()%100;}voidshowArray(inta[],intn){for(inti=0;in;i++)coutsetw(5)a[