C++大學(xué)教程-數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板課件

第七章數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板數(shù)組數(shù)組聲明,初始化,引用字符數(shù)組數(shù)組傳遞給函數(shù)數(shù)組存儲(chǔ),排序,查找多維數(shù)組C++標(biāo)準(zhǔn)庫(kù)-vector類模板總結(jié)1數(shù)組的用途程序設(shè)計(jì)要處理的數(shù)據(jù)往往是許多數(shù)據(jù)而非簡(jiǎn)單的幾個(gè)數(shù)據(jù),對(duì)單個(gè)數(shù)據(jù)分別聲明變量顯露其局限性例如，如果要處理3個(gè)學(xué)生考試成績(jī)，我們可以聲明:intgrade0，grade1，grade2；

但如果有很多成績(jī)(例100個(gè))，該怎么辦？對(duì)一組由相同類型數(shù)據(jù)組成的數(shù)據(jù)集合使用數(shù)組2數(shù)組的特征有序性：數(shù)組中的所有元素都有自身的序號(hào)0，1，2…相同類型：全部是整數(shù)、浮點(diǎn)數(shù)、字符型，也可以數(shù)組的數(shù)組（一維數(shù)組、二維數(shù)組、多維數(shù)組）,后面所說(shuō)數(shù)組是特指一維數(shù)組。3一維數(shù)組的聲明inta[5]

;

數(shù)據(jù)類型數(shù)組名數(shù)組元素的個(gè)數(shù):必須是正值常量表達(dá)式,編譯時(shí)就知值見(jiàn)到數(shù)組聲明后,編譯器保留恰當(dāng)容量?jī)?nèi)存,可以存儲(chǔ)5個(gè)整型變量,每個(gè)變量有自己的表示方式:a[0],a[1],a[2],a[3],a[4]5內(nèi)存空間占用情況

inta[5];1、設(shè)一個(gè)int需要占用4個(gè)字節(jié)的空間2、存放a[0]的地址為1000，此時(shí)1000被成為數(shù)組a的基地址a[0]a[1]a[2]a[3]a[4]值78111623地址100010041008101210166初始化聲明數(shù)組時(shí)可以對(duì)數(shù)組初始化floatx[5]={-1.1,0.2,33.0,4.4,5.05};初始化表的長(zhǎng)度短于要被初始化的數(shù)組元素?cái)?shù)目，那么剩余元素被初始化為0。取巧inta[10]={0}.外部或靜態(tài)數(shù)組沒(méi)有被初始化，系統(tǒng)自動(dòng)把所有元素初始化為0。沒(méi)有被初始化的自動(dòng)或常量數(shù)組含有的值是無(wú)用的。數(shù)組的存儲(chǔ)類型不能是寄存器類型。初始化表7使用一維數(shù)組例：對(duì)數(shù)組賦值(也達(dá)到初始化目的)#include<iostream>constintN=5intmain(void){ inta[N]; inti,sum=0; for(i=0;i<N;++i) a[i]=7+i*i;

return0;}數(shù)組有效的下標(biāo)為：0,1,2,3,40,1，…，(N-1)常量聲明數(shù)組大小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應(yīng)用范例片段聲明一個(gè)數(shù)組,用一個(gè)循環(huán)初始化數(shù)組 intn[10]; for(inti=0;i<10;i++) n[i]=0;13應(yīng)用范例片段求數(shù)組元素之和

intn[10]={32,27,64,18,95,14,90,70,60,37}; total=0;for(inti=0;i<10;i++) total+=n[i];14應(yīng)用范例使用不同計(jì)數(shù)器跟蹤一個(gè)篩子各個(gè)面出現(xiàn)的次數(shù)

分析:篩子有6個(gè)面,需要6個(gè)計(jì)數(shù)器,這里可以用一個(gè)含有6個(gè)分量的數(shù)組,為了和篩子上的數(shù)字對(duì)應(yīng),浪費(fèi)一個(gè)分量:0下標(biāo)分量,聲明數(shù)組含7個(gè)分量.intfrequency[7]如當(dāng)前擲出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第七章數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板數(shù)組數(shù)組聲明,初始化,引用字符數(shù)組數(shù)組傳遞給函數(shù)數(shù)組存儲(chǔ),排序,查找多維數(shù)組C++標(biāo)準(zhǔn)庫(kù)-vector類模板總結(jié)18字符數(shù)組字符串的處理可以使用string對(duì)象,但字符串存儲(chǔ)實(shí)際上是利用了一個(gè)字符數(shù)組,因此在性能上來(lái)說(shuō),有時(shí)直接使用字符數(shù)組更優(yōu)更方便.字符數(shù)組:數(shù)組中存儲(chǔ)了一系列字符,特殊地當(dāng)最后一個(gè)字符為空字符時(shí),代表了一個(gè)字符串.前者的處理同整數(shù)數(shù)組.

19串的結(jié)束符\0

inta[3]={1,2,3}chars[3]={‘a(chǎn)’,’b’,’\0’}s的實(shí)際長(zhǎng)度為2，但必須分配2+1個(gè)空間，多余一個(gè)空間用來(lái)存放’\0’

串是以’\0’為結(jié)束符的一維字符數(shù)組21空字符串沒(méi)有任何字符，只有\(zhòng)022‘a(chǎn)’與”a”‘a(chǎn)’字符常量，只需要1個(gè)字節(jié)存放“a”串常量，需要2個(gè)字節(jié)存放

aa\023串的輸入輸出輸入:charstring2[20];cin>>string2;輸入時(shí)以空格為終止,并在數(shù)組后自動(dòng)加空字符’\0’;注意輸入時(shí)長(zhǎng)度不要超過(guò)數(shù)組聲明時(shí)的大小,這里為19.否則系統(tǒng)并不會(huì)檢查.輸出:cout<<string2;25例子:

用字符串文字初始化一個(gè)字符數(shù)組,讀入一個(gè)字符串到一個(gè)字符數(shù)組,將字符數(shù)組作為一個(gè)字符串打印//Treatingcharacterarraysasstrings.#include<iostream>usingstd::cout;usingstd::cin;usingstd::endl;

26Static局部數(shù)組像其他局部變量一樣,數(shù)組也可以聲稱為static,函數(shù)中定義的static數(shù)組在程序運(yùn)行其間一直存在,但只在該函數(shù)體內(nèi)可見(jiàn).當(dāng)?shù)谝淮斡鲆?jiàn)static數(shù)組的聲明時(shí),程序就初始化它們,非第一次則不再執(zhí)行初始化.當(dāng)?shù)谝淮斡鲆?jiàn)static數(shù)組的聲明時(shí),程序如果沒(méi)有顯式地初始化,編譯器自動(dòng)將其初始化為0.29第七章數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板數(shù)組數(shù)組聲明,初始化,引用字符數(shù)組數(shù)組傳遞給函數(shù)數(shù)組存儲(chǔ),排序,查找多維數(shù)組C++標(biāo)準(zhǔn)庫(kù)-vector類模板總結(jié)30數(shù)組傳遞給函數(shù)要給一個(gè)函數(shù)傳遞一個(gè)數(shù)組實(shí)參,需指定數(shù)組名,且不帶方括號(hào),并將數(shù)組的大小也傳遞給函數(shù).如intdata[24]sum(data,24)數(shù)組名實(shí)際上是數(shù)組在內(nèi)存中的起始地址,函數(shù)由第一個(gè)參數(shù)獲得了數(shù)組在內(nèi)存中的地址.函數(shù)的第一個(gè)參數(shù)傳遞是按引用傳遞函數(shù)在函數(shù)體中修改數(shù)組元素時(shí),實(shí)際是在數(shù)組的原始內(nèi)存位置上修改其值31數(shù)組作為函數(shù)參數(shù)intsum(inta[],intn){ inti,s=0;for(i=0;i<n;++i) s+=a[i];returns;}數(shù)組a作為參數(shù)

標(biāo)示數(shù)組的大小

32數(shù)組作為函數(shù)參數(shù)conctintN=5;intmain(void){inti,total;intvalues[N];for(i=0;i<N;++i)values[i]=i;

total=sum(values,

N);return0;}數(shù)組values傳遞給函數(shù)01234ivaluesmaintotal33數(shù)組傳遞的是地址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數(shù)組傳遞的是地址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數(shù)組元素傳遞的是值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在函數(shù)中修改數(shù)組原有的值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如何在函數(shù)中保護(hù)數(shù)組原有的值?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實(shí)例:用數(shù)組改造后的GradeBook類GradeBook類表示一個(gè)教授使用的成績(jī)薄,用來(lái)存儲(chǔ)和分析學(xué)生的成績(jī)現(xiàn)在改造原有的GradeBook類,改變方法為:在類的數(shù)據(jù)成員中使用一個(gè)數(shù)組存儲(chǔ)所有學(xué)生的成績(jī)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參見(jiàn)Fig.7.16-18,要求學(xué)生課后運(yùn)行并分析該程序中數(shù)組用法42注釋:static成員表示是一個(gè)類變量,即只有在類這一級(jí)上有空間分配,該類的每個(gè)對(duì)象并沒(méi)有該成員副本.staticconst成員表示是一個(gè)類常量,在整個(gè)類包括各個(gè)對(duì)象都不能修改其值有關(guān)static數(shù)據(jù)成員詳細(xì)介紹見(jiàn)第十章43第七章數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板數(shù)組數(shù)組聲明,初始化,引用數(shù)組傳遞給函數(shù)數(shù)組存儲(chǔ),排序,查找多維數(shù)組C++標(biāo)準(zhǔn)庫(kù)-vector類模板總結(jié)44查找在數(shù)組存放的大量數(shù)據(jù)中,常遇到需要判斷這組數(shù)據(jù)中是否與某個(gè)關(guān)鍵字相匹配,即試圖在數(shù)組中發(fā)現(xiàn)一個(gè)特定的元素.此過(guò)程稱為查找查找的方法有很多,這里基于數(shù)組是否有序介紹兩種查找方法:無(wú)序時(shí)采用線性查找法有序時(shí)采用二分法查找45查找線性查找法將待查找的關(guān)鍵字和數(shù)組中的每個(gè)元素進(jìn)行比較,找到時(shí)返回其下標(biāo),否則宣布未找到查找次數(shù):平均必須比較一半元素.時(shí)間復(fù)雜程度O(n)線性查找法適用于小型數(shù)組或未排序數(shù)組46查找線性查找法:intlinearSearch(constintarray[],intkey,intsizeOfArray){for(intj=0;j<sizeOfArray;j++)if(array[j]==key)//iffound,returnj;//returnlocationofkeyreturn-1;//keynotfound}47查找二分法查找:對(duì)一個(gè)有序數(shù)組首先匹配中間位置的元素,如匹配成功終止,否則如待查關(guān)鍵字大于中間元素,拋開(kāi)前面的元素,從中間元素的下一元素到數(shù)組尾部范圍重復(fù)以上匹配.二查找法最壞比較次數(shù)log2n,遠(yuǎn)遠(yuǎn)小于n48排序比較線性查找法和二分法查找發(fā)現(xiàn):對(duì)一組有序的數(shù)據(jù),查找要快的多.因此應(yīng)用中常常先進(jìn)行排序.排序:按照某種特定的次序(升序或降序)排列數(shù)據(jù)插入排序是眾多排序算法中的一種,其簡(jiǎn)單但相對(duì)效率較低49排序插入排序思想:

算法核心思想是將一個(gè)元素插入到一個(gè)有序的數(shù)據(jù)序列中具體做法:首先將數(shù)組中的0下標(biāo)元素看作只有一個(gè)元素組成的有序序列,將1下標(biāo)元素插入到該序列中,形成含有二個(gè)元素的有序序列.如此方法處理下標(biāo)為3,4,…,n個(gè)元素,至此全部有序50排序例如:有一組含有5個(gè)元素的數(shù)據(jù)待排序 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和前面的有序序列從后到前逐個(gè)比較直到前者比其小或到達(dá)序列前端,將1放入此位置分析:下標(biāo)為i的元素前有i個(gè)元素,平均比較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;}比較移動(dòng)52第七章數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板數(shù)組數(shù)組聲明,初始化,引用數(shù)組傳遞給函數(shù)數(shù)組存儲(chǔ),排序,查找多維數(shù)組C++標(biāo)準(zhǔn)庫(kù)-vector類模板總結(jié)53二維數(shù)組聲明：數(shù)據(jù)類型數(shù)組名[M][N];M，N為常量表達(dá)式inta[3][4]；編譯器分配3*4*2個(gè)int型的連續(xù)存儲(chǔ)空間第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二維數(shù)組使用方法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]是錯(cuò)誤的寫(xiě)法55二維數(shù)組作為函數(shù)參數(shù)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;}第一個(gè)尺寸不需要給出其他的尺寸必須給出

56二維數(shù)組初始化以下三個(gè)初始化是等價(jià)的：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多維數(shù)組聲明：數(shù)據(jù)類型數(shù)組名[M]…[N];M，N，為常量表達(dá)式三維數(shù)組inta[3][4][2]；編譯器分配3*4*2個(gè)int型的連續(xù)存儲(chǔ)空間58實(shí)例:用二維數(shù)組改造后的GradeBook類GradeBook類表示一個(gè)教授使用的成績(jī)薄,用來(lái)存儲(chǔ)和分析學(xué)生的多次成績(jī)現(xiàn)在改造原有的GradeBook類,改變方法為:在類的數(shù)據(jù)成員中使用一個(gè)數(shù)組存儲(chǔ)所有學(xué)生的成績(jī)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參見(jiàn)Fig.7.22,要求學(xué)生課后運(yùn)行并分析該程序中數(shù)組用法62第七章數(shù)組與C++標(biāo)準(zhǔn)庫(kù)類模板數(shù)組數(shù)組聲明,初始化,引用數(shù)組傳遞給函數(shù)數(shù)組存儲(chǔ),排序,查找多維數(shù)組C++標(biāo)準(zhǔn)庫(kù)-vector類模板總結(jié)63C++標(biāo)準(zhǔn)庫(kù)-vector類模板vector類模板是一種更加健壯,且有許多附加功能的數(shù)組附加功能例如:提供下標(biāo)越界檢查; 提供數(shù)組用相等運(yùn)算和大小比較提供數(shù)組間賦值等運(yùn)算下面例子給出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使用前需要的預(yù)處理語(yǔ)句65Fig.7.26voidoutputVector(constvector<int>&);//displaythevectorvoidinputVector(vector<int>&);//inputvaluesintothevectorintmain(){

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

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

對(duì)象聲明Vector類參數(shù)說(shuō)明66Fig.7.26//printintegers1sizeandcontentscout<<"Sizeofvectorintegers1is"<<integers1.size()<<"\nvectorafterinitialization:"<<endl;outputVector(integers1);//printintegers2sizeandcontentscout<<"\nSizeofvectorintegers2is"<<integers2.size()<<"\nvectorafterinitialization:"<<endl;outputVector(integers2);調(diào)用其成員函數(shù)67Fig.7.26//inputandprintintegers1andintegers2cout<<"\nEnter17integers:"<<endl;

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

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

outputVector(integers2);調(diào)用函數(shù)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];調(diào)用==運(yùn)算調(diào)用[]運(yùn)算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[]和賦值運(yùn)算,[]不進(jìn)行越界檢查at函數(shù)和賦值運(yùn)算,此at函數(shù)進(jìn)行越界檢查72Fig.7.26//outputvectorcontentsvoidoutputVector(constvector<int>&array){size_ti;//declarecontrolvariablefor(i=0;i<array.size();i++){cout<<setw(12)<<