C++大学教程-数组与C++标准库类模板课件

第七章数组与C++标准库类模板数组数组声明,初始化,引用字符数组数组传递给函数数组存储,排序,查找多维数组C++标准库-vector类模板总结1数组的用途程序设计要处理的数据往往是许多数据而非简单的几个数据,对单个数据分别声明变量显露其局限性例如，如果要处理3个学生考试成绩，我们可以声明:intgrade0，grade1，grade2；

但如果有很多成绩(例100个)，该怎么办？对一组由相同类型数据组成的数据集合使用数组2数组的特征有序性：数组中的所有元素都有自身的序号0，1，2…相同类型：全部是整数、浮点数、字符型，也可以数组的数组（一维数组、二维数组、多维数组）,后面所说数组是特指一维数组。3一维数组的声明inta[5]

;

数据类型数组名数组元素的个数:必须是正值常量表达式,编译时就知值见到数组声明后,编译器保留恰当容量内存,可以存储5个整型变量,每个变量有自己的表示方式:a[0],a[1],a[2],a[3],a[4]5内存空间占用情况

inta[5];1、设一个int需要占用4个字节的空间2、存放a[0]的地址为1000，此时1000被成为数组a的基地址a[0]a[1]a[2]a[3]a[4]值78111623地址100010041008101210166初始化声明数组时可以对数组初始化floatx[5]={-1.1,0.2,33.0,4.4,5.05};初始化表的长度短于要被初始化的数组元素数目，那么剩余元素被初始化为0。取巧inta[10]={0}.外部或静态数组没有被初始化，系统自动把所有元素初始化为0。没有被初始化的自动或常量数组含有的值是无用的。数组的存储类型不能是寄存器类型。初始化表7使用一维数组例：对数组赋值(也达到初始化目的)#include<iostream>constintN=5intmain(void){ inta[N]; inti,sum=0; for(i=0;i<N;++i) a[i]=7+i*i;

return0;}数组有效的下标为：0,1,2,3,40,1，…，(N-1)常量声明数组大小9//Fig.7.3:fig07_03.cpp//Initializinganarray.#include<iostream>usingstd::cout;usingstd::endl;#include<iomanip>usingstd::setw;intmain(){ intn[10];//nisanarrayof10integers //initializeelementsofarraynto0 for(inti=0;i<10;i++) n[i]=0;//setelementatlocationito010 cout<<"Element"<<setw(13)<<"Value"<<endl; //outputeacharrayelement'svalue for(intj=0;j<10;j++) cout<<setw(7)<<j<<setw(13)<<n[j]<<endl; return0;}11应用范例片段声明一个数组,用一个循环初始化数组 intn[10]; for(inti=0;i<10;i++) n[i]=0;13应用范例片段求数组元素之和

intn[10]={32,27,64,18,95,14,90,70,60,37}; total=0;for(inti=0;i<10;i++) total+=n[i];14应用范例使用不同计数器跟踪一个筛子各个面出现的次数

分析:筛子有6个面,需要6个计数器,这里可以用一个含有6个分量的数组,为了和筛子上的数字对应,浪费一个分量:0下标分量,声明数组含7个分量.intfrequency[7]如当前掷出5,则frequency[5]++;15intmain(){constintarraySize=7;//ignoreelementzerointfrequency[arraySize]={0};srand(time(0));//seedrandomnumbergenerator

//rolldie6,000,000times;usedievalueasfrequencyindexfor(introll=1;roll<=6000000;roll++)frequency[1+rand()%6]++;cout<<"Face"<<setw(13)<<"Frequency"<<endl;//outputeacharrayelement'svaluefor(intface=1;face<arraySize;face++)cout<<setw(4)<<face<<setw(13)<<frequency[face]<<endl;return0;//indicatessuccessfultermination}//endmain

17第七章数组与C++标准库类模板数组数组声明,初始化,引用字符数组数组传递给函数数组存储,排序,查找多维数组C++标准库-vector类模板总结18字符数组字符串的处理可以使用string对象,但字符串存储实际上是利用了一个字符数组,因此在性能上来说,有时直接使用字符数组更优更方便.字符数组:数组中存储了一系列字符,特殊地当最后一个字符为空字符时,代表了一个字符串.前者的处理同整数数组.

19串的结束符\0

inta[3]={1,2,3}chars[3]={‘a’,’b’,’\0’}s的实际长度为2，但必须分配2+1个空间，多余一个空间用来存放’\0’

串是以’\0’为结束符的一维字符数组21空字符串没有任何字符，只有\022‘a’与”a”‘a’字符常量，只需要1个字节存放“a”串常量，需要2个字节存放

aa\023串的输入输出输入:charstring2[20];cin>>string2;输入时以空格为终止,并在数组后自动加空字符’\0’;注意输入时长度不要超过数组声明时的大小,这里为19.否则系统并不会检查.输出:cout<<string2;25例子:

用字符串文字初始化一个字符数组,读入一个字符串到一个字符数组,将字符数组作为一个字符串打印//Treatingcharacterarraysasstrings.#include<iostream>usingstd::cout;usingstd::cin;usingstd::endl;

26Static局部数组像其他局部变量一样,数组也可以声称为static,函数中定义的static数组在程序运行其间一直存在,但只在该函数体内可见.当第一次遇见static数组的声明时,程序就初始化它们,非第一次则不再执行初始化.当第一次遇见static数组的声明时,程序如果没有显式地初始化,编译器自动将其初始化为0.29第七章数组与C++标准库类模板数组数组声明,初始化,引用字符数组数组传递给函数数组存储,排序,查找多维数组C++标准库-vector类模板总结30数组传递给函数要给一个函数传递一个数组实参,需指定数组名,且不带方括号,并将数组的大小也传递给函数.如intdata[24]sum(data,24)数组名实际上是数组在内存中的起始地址,函数由第一个参数获得了数组在内存中的地址.函数的第一个参数传递是按引用传递函数在函数体中修改数组元素时,实际是在数组的原始内存位置上修改其值31数组作为函数参数intsum(inta[],intn){ inti,s=0;for(i=0;i<n;++i) s+=a[i];returns;}数组a作为参数

标示数组的大小

32数组作为函数参数conctintN=5;intmain(void){inti,total;intvalues[N];for(i=0;i<N;++i)values[i]=i;

total=sum(values,

N);return0;}数组values传递给函数01234ivaluesmaintotal33数组传递的是地址conctintN=5;intmain(void){inti,total;intvalues[N];for(i=0;i<N;++i)values[i]=i;

total=sum(values,N);return0;}01234ivaluesintsum(inta[],intn){inti,s=0;for(i=0;i<n;++i)

s+=a[i];returns;}nsa5itotaltotal=?

1034数组传递的是地址conctintN=5;intmain(void){inti,total;intvalues[N];for(i=0;i<N;++i)values[i]=i;

total=sum(&values[1],N-2);return0;}01234ivaluesintsum(inta[],intn){inti,s=0;for(i=0;i<n;++i) s+=a[i];returns;}nsa3itotaltotal=?

635数组元素传递的是值conctintN=5;intmain(void){inti,total;intvalues[N];for(i=0;i<N;++i)values[i]=i;

total=sum(values[2],

N-2);return0;}01234ivaluesintsum(inta,intn){inti,s=1;for(i=0;i<n;++i) s*=a;returns;}nsa3itotaltotal=?

8236在函数中修改数组原有的值conctintN=5;intmain(void){inti;intvalues[N];for(i=0;i<N;++i)values[i]=i;

setArray(values,N);return0;}99999ivaluesvoidsetArray(int

a[],int

n)

{inti;for(i=0;i<n;++i) a[i]=9;}na5itotal37如何在函数中保护数组原有的值?conctintN=5;intmain(void){inti,total;intvalues[N];for(i=0;i<N;++i)values[i]=i;

total=sum(values,

N);return0;}01234ivaluesintsum(constinta[],intn){inti,s=0;for(i=0;i<n;++i) s*=a;a[0]=9;Xreturns;}nsa5itotaltotal=?

1038实例:用数组改造后的GradeBook类GradeBook类表示一个教授使用的成绩薄,用来存储和分析学生的成绩现在改造原有的GradeBook类,改变方法为:在类的数据成员中使用一个数组存储所有学生的成绩GradeBook类声明如下:39#include<string>//programusesC++StandardLibrarystringclassusingstd::string;//GradeBookclassdefinitionclassGradeBook{public://constant--numberofstudentswhotookthetest

conststaticintstudents=10;//notepublicdata

40//constructorinitializescoursenameandarrayofgradesGradeBook(string,constint[]);

//functiontosetthecoursenamevoidsetCourseName(string);

//functiontoretrievethecoursenamestringgetCourseName();//displayawelcomemessagevoiddisplayMessage();//performvariousoperationsonthegradedatavoidprocessGrades();41intgetMinimum();//findtheminimumgradeforthetestintgetMaximum();//findthemaximumgradeforthetestdoublegetAverage();//determinetheaveragegradeforthetestvoidoutputBarChart();//outputbarchartofgradedistributionvoidoutputGrades();//outputthecontentsofthegradesarrayprivate:stringcourseName;//coursenameforthisgradebook

intgrades[students];//arrayofstudentgrades};//endclassGradeBook参见Fig.7.16-18,要求学生课后运行并分析该程序中数组用法42注释:static成员表示是一个类变量,即只有在类这一级上有空间分配,该类的每个对象并没有该成员副本.staticconst成员表示是一个类常量,在整个类包括各个对象都不能修改其值有关static数据成员详细介绍见第十章43第七章数组与C++标准库类模板数组数组声明,初始化,引用数组传递给函数数组存储,排序,查找多维数组C++标准库-vector类模板总结44查找在数组存放的大量数据中,常遇到需要判断这组数据中是否与某个关键字相匹配,即试图在数组中发现一个特定的元素.此过程称为查找查找的方法有很多,这里基于数组是否有序介绍两种查找方法:无序时采用线性查找法有序时采用二分法查找45查找线性查找法将待查找的关键字和数组中的每个元素进行比较,找到时返回其下标,否则宣布未找到查找次数:平均必须比较一半元素.时间复杂程度O(n)线性查找法适用于小型数组或未排序数组46查找线性查找法:intlinearSearch(constintarray[],intkey,intsizeOfArray){for(intj=0;j<sizeOfArray;j++)if(array[j]==key)//iffound,returnj;//returnlocationofkeyreturn-1;//keynotfound}47查找二分法查找:对一个有序数组首先匹配中间位置的元素,如匹配成功终止,否则如待查关键字大于中间元素,抛开前面的元素,从中间元素的下一元素到数组尾部范围重复以上匹配.二查找法最坏比较次数log2n,远远小于n48排序比较线性查找法和二分法查找发现:对一组有序的数据,查找要快的多.因此应用中常常先进行排序.排序:按照某种特定的次序(升序或降序)排列数据插入排序是众多排序算法中的一种,其简单但相对效率较低49排序插入排序思想:

算法核心思想是将一个元素插入到一个有序的数据序列中具体做法:首先将数组中的0下标元素看作只有一个元素组成的有序序列,将1下标元素插入到该序列中,形成含有二个元素的有序序列.如此方法处理下标为3,4,…,n个元素,至此全部有序50排序例如:有一组含有5个元素的数据待排序 3,2,5,1,4

3,2,5,1,4

2,3,5,1,4

2,3,5,1,4

1,2,3,5,41,2,3,4,51和前面的有序序列从后到前逐个比较直到前者比其小或到达序列前端,将1放入此位置分析:下标为i的元素前有i个元素,平均比较i/2次.所有元素排好序平均比较n(n-1)/4次51插入排序算法for(intnext=1;next<arraySize;next++){insert=data[next];intmoveItem=next;

while((moveItem>0)&&(data[moveItem-1]>insert)){data[moveItem]=data[moveItem-1];moveItem--;} data[moveItem]=insert;}比较移动52第七章数组与C++标准库类模板数组数组声明,初始化,引用数组传递给函数数组存储,排序,查找多维数组C++标准库-vector类模板总结53二维数组声明：数据类型数组名[M][N];M，N为常量表达式inta[3][4]；编译器分配3*4*2个int型的连续存储空间第0列第1列第2列第3列第0行a[0][0]a[0][1]a[0][2]a[0][3]第1行a[1][0]a[1][1]a[1][2]a[1][3]第2行a[2][0]a[2][1]a[2][2]a[2][3]54二维数组使用方法constintM=3;constintN=4intmain(){ inta[M][N],i,j,sum=0;

for(i=0;i<M;++i) for(j=0;i<N;++j)

a[i][j]=i+j;}第0列第1列第2列第3列第0行0123第1行1234第2行2345注意:

a[i,j]是错误的写法55二维数组作为函数参数intsum(inta[][5],intn){ inti,j,s=0;for(i=0;i<n;++i)for(j=0;j<5;++j) s+=a[i][j];returns;}第一个尺寸不需要给出其他的尺寸必须给出

56二维数组初始化以下三个初始化是等价的：inta[2][3]={1,2,3,4,5,6};inta[2][3]={{1,2,3},{4,5,6}};inta[][3]={{1,2,3},{4,5,6}};57多维数组声明：数据类型数组名[M]…[N];M，N，为常量表达式三维数组inta[3][4][2]；编译器分配3*4*2个int型的连续存储空间58实例:用二维数组改造后的GradeBook类GradeBook类表示一个教授使用的成绩薄,用来存储和分析学生的多次成绩现在改造原有的GradeBook类,改变方法为:在类的数据成员中使用一个数组存储所有学生的成绩GradeBook类声明如下:59#include<string>//programusesC++StandardLibrarystringclassusingstd::string;//GradeBookclassdefinitionclassGradeBook{public://constant--numberofstudentswhotookthetest

conststaticintstudents=10;//notepublicdata

conststaticinttests=3;

60//constructorinitializescoursenameandarrayofgrades

GradeBook(string,constint[][tests]);

//functiontosetthecoursenamevoidsetCourseName(string);

//functiontoretrievethecoursenamestringgetCourseName();//displayawelcomemessagevoiddisplayMessage();//performvariousoperationsonthegradedatavoidprocessGrades();61intgetMinimum();//findtheminimumgradeforthetestintgetMaximum();//findthemaximumgradeforthetest

doublegetAverage(constint[],constint);//determinetheaveragegradeforthetestvoidoutputBarChart();//outputbarchartofgradedistributionvoidoutputGrades();//outputthecontentsofthegradesarrayprivate:stringcourseName;//coursenameforthisgradebook

intgrades[students][tests];//two-dimensionalarray};//endclassGradeBook参见Fig.7.22,要求学生课后运行并分析该程序中数组用法62第七章数组与C++标准库类模板数组数组声明,初始化,引用数组传递给函数数组存储,排序,查找多维数组C++标准库-vector类模板总结63C++标准库-vector类模板vector类模板是一种更加健壮,且有许多附加功能的数组附加功能例如:提供下标越界检查; 提供数组用相等运算和大小比较提供数组间赋值等运算下面例子给出vector类模板用法一瞥,其全部功在第23章介绍64Fig.7.26//Fig.7.26:fig07_26.cpp//DemonstratingC++StandardLibraryclasstemplatevector.#include<iostream>usingstd::cout;usingstd::cin;usingstd::endl;#include<iomanip>usingstd::setw;#include<vector>usingstd::vector;vector使用前需要的预处理语句65Fig.7.26voidoutputVector(constvector<int>&);//displaythevectorvoidinputVector(vector<int>&);//inputvaluesintothevectorintmain(){

vector<int>integers1(7);//7-elementvector<int>

vector<int>integers2(10);//10-elementvector<int>

对象声明Vector类参数说明66Fig.7.26//printintegers1sizeandcontentscout<<"Sizeofvectorintegers1is"<<integers1.size()<<"\nvectorafterinitialization:"<<endl;outputVector(integers1);//printintegers2sizeandcontentscout<<"\nSizeofvectorintegers2is"<<integers2.size()<<"\nvectorafterinitialization:"<<endl;outputVector(integers2);调用其成员函数67Fig.7.26//inputandprintintegers1andintegers2cout<<"\nEnter17integers:"<<endl;

inputVector(integers1);inputVector(integers2);cout<<"\nAfterinput,thevectorscontain:\n"<<"integers1:"<<endl;

outputVector(integers1);cout<<"integers2:"<<endl;

outputVector(integers2);调用函数68Fig.7.26//useinequality(!=)operatorwithvectorobjectscout<<"\nEvaluating:integers1!=integers2"<<endl;if(integers1!=integers2)cout<<"integers1andintegers2arenotequal"<<endl;//createvectorintegers3usingintegers1asan//initializer;printsizeandcontents

vector<int>integers3(integers1);//copyconstructorcout<<"\nSizeofvectorintegers3is"<<integers3.size()<<"\nvectorafterinitialization:"<<endl;outputVector(integers3);69Fig.7.26//useassignment(=)operatorwithvectorobjectscout<<"\nAssigningintegers2tointegers1:"<<endl;//integers1islargerthanintegers2

integers1=integers2;

cout<<"integers1:"<<endl;outputVector(integers1);cout<<"integers2:"<<endl;outputVector(integers2);70Fig.7.26//useequality(==)operatorwithvectorobjectscout<<"\nEvaluating:integers1==integers2“<<endl;if(integers1==integers2)cout<<"integers1andintegers2areequal“<<endl;//usesquarebracketstocreatervaluecout<<"\nintegers1[5]is"<<integers1[5];调用==运算调用[]运算71Fig.7.26//usesquarebracketstocreatelvaluecout<<"\n\nAssigning1000tointegers1[5]"<<endl;

integers1[5]=1000;cout<<"integers1:"<<endl;outputVector(integers1);//attempttouseout-of-rangesubscriptcout<<"\nAttempttoassign1000tointegers1.at(15)"<<endl;

integers1.at(15)

=1000;//ERROR:outofrangereturn0;}//endmain[]和赋值运算,[]不进行越界检查at函数和赋值运算,此at函数进行越界检查72Fig.7.26//outputvectorcontentsvoidoutputVector(constvector<int>&array){size_ti;//declarecontrolvariablefor(i=0;i<array.size();i++){cout<<setw(12)<<