第七章數組與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)<<