C++大學教程-數(shù)組與C++標準庫類模板課件

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

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

;

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

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

return0;}數(shù)組有效的下標為：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應用范例片段聲明一個數(shù)組,用一個循環(huán)初始化數(shù)組 intn[10]; for(inti=0;i<10;i++) n[i]=0;13應用范例片段求數(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應用范例使用不同計數(shù)器跟蹤一個篩子各個面出現(xiàn)的次數(shù)

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

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

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

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

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

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

26Static局部數(shù)組像其他局部變量一樣,數(shù)組也可以聲稱為static,函數(shù)中定義的static數(shù)組在程序運行其間一直存在,但只在該函數(shù)體內(nèi)可見.當?shù)谝淮斡鲆妔tatic數(shù)組的聲明時,程序就初始化它們,非第一次則不再執(zhí)行初始化.當?shù)谝淮斡鲆妔tatic數(shù)組的聲明時,程序如果沒有顯式地初始化,編譯器自動將其初始化為0.29第七章數(shù)組與C++標準庫類模板數(shù)組數(shù)組聲明,初始化,引用字符數(shù)組數(shù)組傳遞給函數(shù)數(shù)組存儲,排序,查找多維數(shù)組C++標準庫-vector類模板總結(jié)30數(shù)組傳遞給函數(shù)要給一個函數(shù)傳遞一個數(shù)組實參,需指定數(shù)組名,且不帶方括號,并將數(shù)組的大小也傳遞給函數(shù).如intdata[24]sum(data,24)數(shù)組名實際上是數(shù)組在內(nèi)存中的起始地址,函數(shù)由第一個參數(shù)獲得了數(shù)組在內(nèi)存中的地址.函數(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ù)

標示數(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ù)中保護數(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ù)組改造后的GradeBook類GradeBook類表示一個教授使用的成績薄,用來存儲和分析學生的成績現(xiàn)在改造原有的GradeBook類,改變方法為:在類的數(shù)據(jù)成員中使用一個數(shù)組存儲所有學生的成績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,要求學生課后運行并分析該程序中數(shù)組用法42注釋:static成員表示是一個類變量,即只有在類這一級上有空間分配,該類的每個對象并沒有該成員副本.staticconst成員表示是一個類常量,在整個類包括各個對象都不能修改其值有關static數(shù)據(jù)成員詳細介紹見第十章43第七章數(shù)組與C++標準庫類模板數(shù)組數(shù)組聲明,初始化,引用數(shù)組傳遞給函數(shù)數(shù)組存儲,排序,查找多維數(shù)組C++標準庫-vector類模板總結(jié)44查找在數(shù)組存放的大量數(shù)據(jù)中,常遇到需要判斷這組數(shù)據(jù)中是否與某個關鍵字相匹配,即試圖在數(shù)組中發(fā)現(xiàn)一個特定的元素.此過程稱為查找查找的方法有很多,這里基于數(shù)組是否有序介紹兩種查找方法:無序時采用線性查找法有序時采用二分法查找45查找線性查找法將待查找的關鍵字和數(shù)組中的每個元素進行比較,找到時返回其下標,否則宣布未找到查找次數(shù):平均必須比較一半元素.時間復雜程度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查找二分法查找:對一個有序數(shù)組首先匹配中間位置的元素,如匹配成功終止,否則如待查關鍵字大于中間元素,拋開前面的元素,從中間元素的下一元素到數(shù)組尾部范圍重復以上匹配.二查找法最壞比較次數(shù)log2n,遠遠小于n48排序比較線性查找法和二分法查找發(fā)現(xiàn):對一組有序的數(shù)據(jù),查找要快的多.因此應用中常常先進行排序.排序:按照某種特定的次序(升序或降序)排列數(shù)據(jù)插入排序是眾多排序算法中的一種,其簡單但相對效率較低49排序插入排序思想:

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

56二維數(shù)組初始化以下三個初始化是等價的：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，為常量表達式三維數(shù)組inta[3][4][2]；編譯器分配3*4*2個int型的連續(xù)存儲空間58實例:用二維數(shù)組改造后的GradeBook類GradeBook類表示一個教授使用的成績薄,用來存儲和分析學生的多次成績現(xiàn)在改造原有的GradeBook類,改變方法為:在類的數(shù)據(jù)成員中使用一個數(shù)組存儲所有學生的成績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,要求學生課后運行并分析該程序中數(shù)組用法62第七章數(shù)組與C++標準庫類模板數(shù)組數(shù)組聲明,初始化,引用數(shù)組傳遞給函數(shù)數(shù)組存儲,排序,查找多維數(shù)組C++標準庫-vector類模板總結(jié)63C++標準庫-vector類模板vector類模板是一種更加健壯,且有許多附加功能的數(shù)組附加功能例如:提供下標越界檢查; 提供數(shù)組用相等運算和大小比較提供數(shù)組間賦值等運算下面例子給出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類參數(shù)說明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)用==運算調(diào)用[]運算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函數(shù)和賦值運算,此at函數(shù)進行越界檢查72Fig.7.26//outputvectorcontentsvoidoutputVector(constvector<int>&array){size_ti;//declarecontrolvariablefor(i=0;i<array.size();i++){cout<<setw(12)<<