會(huì)計(jì)學(xué)1Chapter數(shù)組和矩陣實(shí)用本章教學(xué)內(nèi)容數(shù)組矩陣特殊矩陣稀疏矩陣第1頁(yè)/共49頁(yè)

4.1數(shù)組

從本質(zhì)上講，數(shù)組是一個(gè)<下標(biāo)，值>（<index,value>）偶對(duì)的集合，其中每個(gè)數(shù)據(jù)元素都由一個(gè)值和一個(gè)下標(biāo)組成。

一維數(shù)組是n（n≥0）個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0，a1，…，an-1構(gòu)成的有限線性序列，且該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中。其中，n叫做數(shù)組長(zhǎng)度或數(shù)組大?。蝗绻鹡=0，則是空數(shù)組。1、一維數(shù)組的定義第2頁(yè)/共49頁(yè)

數(shù)組中的每一個(gè)元素在數(shù)組中的位置由下標(biāo)唯一確定；數(shù)組中的各數(shù)據(jù)元素處于一個(gè)線性結(jié)構(gòu)中；一維數(shù)組也叫做向量。2、一維數(shù)組的特點(diǎn)3、二維數(shù)組當(dāng)每一個(gè)數(shù)組元素a[i]（0≤i≤n－1）本身又是一個(gè)一維數(shù)組時(shí)，一維數(shù)組擴(kuò)充為二維數(shù)組。二維數(shù)組也叫做矩陣，如a[n][m]可以看作是由n個(gè)行向量和m個(gè)列向量所組成的向量。第3頁(yè)/共49頁(yè)a[0][0]…a[0][k-1]a[0][k]a[0][k+1]…a[0][m-1]……a[j-1][0]…a[j-1][k-1]a[j-1][k]a[j-1][k+1]…a[j-1][m-1]a[j][0]…a[j][k-1]a[j][k]a[j][k+1]…a[j][m-1]a[j+1][0]…a[j+1][k-1]a[j+1][k]a[j+1][k+1]…a[j+1][m-1]……a[n-1][0]…a[n-1][k-1]a[n-1][k]a[n-1][k+1]…a[n-1][m-1]…………………………例如：二維數(shù)組a[n][m]總共有n×m個(gè)數(shù)組元素；每一個(gè)數(shù)組元素a[j][k]同時(shí)處于兩個(gè)向量之中；數(shù)組元素a[j][k]有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼；數(shù)組元素在數(shù)組中的位置由下標(biāo)的二元組[j][k]唯一確定。第4頁(yè)/共49頁(yè)4、在一個(gè)三維數(shù)組a[m1][m2][m3]中：總共有m1×m2×m3個(gè)數(shù)組元素；每一個(gè)數(shù)組元素a[i][j][k]同時(shí)處于三個(gè)向量之中；數(shù)組元素a[i][j][k]有三個(gè)直接前驅(qū)和三個(gè)直接后繼；數(shù)組元素在數(shù)組中的位置由下標(biāo)的三元組[i][j][k]唯一確定。5、在一個(gè)n維數(shù)組a[m1][m2]…[mn]中：總共有m1×m2×…×mn個(gè)數(shù)組元素；每一個(gè)數(shù)組元素a[i1][i2]…[in]同時(shí)處于n個(gè)向量之中；數(shù)組元素a[i1][i2]…[in]有n個(gè)直接前驅(qū)和n個(gè)直接后繼；數(shù)組元素在數(shù)組中的位置由下標(biāo)的n元組[i1][i2]…[in]唯一確定。高維數(shù)組第5頁(yè)/共49頁(yè)1、數(shù)組ADT抽象數(shù)據(jù)類型Array{實(shí)例形如(index,value)的數(shù)據(jù)對(duì)集合，其中任意兩對(duì)數(shù)據(jù)的index值都各不相同操作Create()：創(chuàng)建一個(gè)空的數(shù)組Store(index,value)：添加數(shù)據(jù)(index,value)，同時(shí)刪除具有相同index值的數(shù)據(jù)對(duì)（如果存在）Retrieve(index)：返回索引值為index的數(shù)據(jù)對(duì)}第6頁(yè)/共49頁(yè)設(shè)一維數(shù)組a[n]的第一個(gè)數(shù)組元素的存儲(chǔ)地址為a，每一個(gè)數(shù)組元素的存儲(chǔ)大小為l，則任一數(shù)組元素的存儲(chǔ)地址LOC(i)為：01…i…n-1alLOC(i)i×lLOC(i)＝a，i=0時(shí)LOC(i-1)+l，i>0時(shí)LOC(i)＝LOC(i-1)+l

＝a+i*lLOC(1)＝LOC(0)+l

＝a+lLOC(2)＝LOC(1)+l

＝a+2*l…，LOC(1)LOC(2)2、一維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)第7頁(yè)/共49頁(yè)用一組連續(xù)的存儲(chǔ)單元存放二維數(shù)組——將它的下標(biāo)映射到其相應(yīng)的一維數(shù)組的存儲(chǔ)位置。（1）行主映射：以行序?yàn)橹鞯拇鎯?chǔ)方式如C、C++和PASCAL等語(yǔ)言采用這種存儲(chǔ)方式。（2）列主映射：以列序?yàn)橹鞯拇鎯?chǔ)方式如FORTRAN語(yǔ)言采用這種存儲(chǔ)方式。3、二維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

——如何用一維的存儲(chǔ)地址來(lái)表示多維的關(guān)系第8頁(yè)/共49頁(yè)以行（列）序?yàn)橹鞯拇鎯?chǔ)方式：先存儲(chǔ)第0行（列），再存儲(chǔ)第1行（列），繼續(xù)下去，最后存儲(chǔ)第n-1行（m-1列）；第i+1行（j+1列）的第一個(gè)元素a[i+1][0]（a[0][j+1]）是緊接在第i行（第j列）的最后一個(gè)元素之后存放的。a[0][0]a[0][1]a[0][m-1]a[1][0]a[1][1]a[1][m-1]a[n-1][0]a[n-1][m-1]…………a[0][0]a[1][0]a[n-1][0]a[0][1]a[1][1]a[m-1][1]a[0][m-1]a[n-1][m-1]…………第0行第1行第n-1行第0列第1列第m-1列（a）以行序?yàn)橹鳎╞）以列序?yàn)橹鞯?頁(yè)/共49頁(yè)假設(shè)有二維數(shù)組a[n][m]，且下標(biāo)均從0開始，每個(gè)數(shù)據(jù)元素的存儲(chǔ)大小為l，那么，任一數(shù)組元素a[j][k]在相應(yīng)的一維數(shù)組中存放地址為：

LOC(j,k)=LOC(0,0)+(j*m+k)*l以行優(yōu)先的順序討論地址的映射方法第10頁(yè)/共49頁(yè)a[0][0]…a[0][k-1]a[0][k]a[0][k+1]…a[0][m-1]……a[j-1][0]…a[j-1][k-1]a[j-1][k]a[j-1][k+1]…a[j-1][m-1]a[j][0]…a[j][k-1]a[j][k]a[j][k+1]…a[j][m-1]a[j+1][0]…a[j+1][k-1]a[j+1][k]a[j+1][k+1]…a[j+1][m-1]……a[n-1][0]…a[n-1][k-1]a[n-1][k]a[n-1][k+1]…a[n-1][m-1]…………………………第11頁(yè)/共49頁(yè)LOC(i,j,k)=LOC(i,0,0)+(j*m3+k)*l=LOC(i-1,0,0)+(m2*m3+j*m3+k)*l=…=LOC(0,0,0)+(i*m2*m3+j*m3+k)*l假設(shè)有三維數(shù)組a[m1][m2][m3]，且下標(biāo)均從0開始，每個(gè)數(shù)據(jù)元素的存儲(chǔ)大小為l，那么，任一數(shù)組元素a[i][j][k]在相應(yīng)的一維數(shù)組中存放地址為：三維數(shù)組的地址映射函數(shù)第12頁(yè)/共49頁(yè)推廣到n維數(shù)組的映射函數(shù)行主次序列主次序

第13頁(yè)/共49頁(yè)設(shè)W為一個(gè)二維數(shù)組，其中每個(gè)數(shù)據(jù)元素W[i][j]占用6個(gè)字節(jié)，行下標(biāo)i從0到8，列下標(biāo)j從2到5，則二維數(shù)組W的數(shù)據(jù)元素共占用

A

個(gè)字節(jié)；W中第6行的元素和第4列的元素共占用

B

個(gè)字節(jié)；若按行順序存放二維數(shù)組W，其起始地址的字節(jié)號(hào)為100，則二維數(shù)組W的最后一個(gè)數(shù)據(jù)元素的起始地址的字節(jié)號(hào)為

C

，數(shù)據(jù)元素W[3][4]的起始地址號(hào)為

D

，而數(shù)據(jù)元素W[2][2]的起始地址號(hào)與當(dāng)按列優(yōu)先順序存放時(shí)數(shù)據(jù)元素

E

的起始地址相同。A（1）480 （2）192 （3）216 （4）144B（1）78 （2）72 （3）66 （4）84C（1）310 （2）311 （3）184 （4）185D（1）179 （2）178 （3）184 （4）185E（1）W[0][5] （2）W[2][8] （3）W[5][2] （4）W[8][2]√√√√√

【課堂練習(xí)】（軟考真題）第14頁(yè)/共49頁(yè)w02w03w04w05w12w13w14w15w22w23w24w25w32w33w34w35w42w43w44w45w52w53w54w55w62w63w64w65w72w73w74w75w82w83w84w85W=解：行下標(biāo)從0-8，共9行；列下標(biāo)從2-5，共4列?？偞鎯?chǔ)空間需9×4×6=216個(gè)字節(jié)第15頁(yè)/共49頁(yè)4、數(shù)組類的擴(kuò)展C++中的數(shù)組不能控制越界訪問(wèn)不能直接輸出不直接支持加、減、乘等運(yùn)算。inta[3]={1,4,2};cout<<a;inta[3]={1,4,2};a[-1]、a[4]第16頁(yè)/共49頁(yè)（1）一維數(shù)組類定義一系列運(yùn)算符第17頁(yè)/共49頁(yè)一維數(shù)組的構(gòu)造template<classT>Array1D<T>::Array1D(intsz){if(sz<0)cerr<<“BadInitializers！”<<endl;size=sz;element=newT[sz];}template<classT>Array1D<T>::Array1D(Array1D<T>&v){size=v.size;element=newT[size];for(inti=0;i<size;i++)element[i]=v.element[i];}構(gòu)造函數(shù)復(fù)制構(gòu)造函數(shù)第18頁(yè)/共49頁(yè)下標(biāo)操作符重載：[]template<classT>T&Array1D<T>::operator[](inti)const{if(i<0||i>=size)cerr<<“OutofBounds”<<endl;returnelement[i];}下標(biāo)操作符必須能夠出現(xiàn)在一個(gè)賦值操作符的左右兩邊，為了能在左邊出現(xiàn)它的返回值必須是一個(gè)左值，可以通過(guò)把返回類型指定為一個(gè)引用來(lái)實(shí)現(xiàn)。第19頁(yè)/共49頁(yè)賦值操作符重載：=template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&v){if(this!=&v){size=v.size;delete[]=element;element=newT[size];for(inti=0;i<size;i++)element[i]=v.element[i];}

return*this;

}

賦值操作符必須重載為成員函數(shù)；賦值運(yùn)算符必須傳回一個(gè)指向其左操作數(shù)的引用，即*this。第20頁(yè)/共49頁(yè)二元減法操作符重載：-template<classT>Array1D<T>Array1D<T>::operator-(Array1D<T>&v)const{//返回w=(*this)-vif(size!=v.size)throwSizeMismatch();Array1D<T>w(size);for(inti=0;i<size;i++)w.element[i]=element[i]-v.element[i];returnw;}第21頁(yè)/共49頁(yè)一元負(fù)號(hào)操作符重載：-template<classT>Array1D<T>Array1D<T>::operator-()const{//返回w=-(*this)Array1D<T>w(size);for(inti=0;i<size;i++)w.element[i]=-element[i];returnw;}第22頁(yè)/共49頁(yè)操作符重載：+=template<classT>Array1D<T>&Array1D<T>::operator+=(constT&x){for(inti=0;i<size;i++)element[i]+=x;return*this;

}第23頁(yè)/共49頁(yè)補(bǔ)充總結(jié)：操作符重載的規(guī)則操作符重載的規(guī)則（1）C++不允許用戶自己定義新的操作符，只能對(duì)已有的C++操作符進(jìn)行重載。（2）C++中絕大部分的操作符允許重載，不能重載的操作符只有5個(gè)：

.（成員訪問(wèn)操作符）*（成員指針訪問(wèn)操作符）∷（域操作符）

sizeof（長(zhǎng)度操作符）

?:（條件操作符）第24頁(yè)/共49頁(yè)（3）重載不能改變操作符操作對(duì)象（即操作數(shù)）的個(gè)數(shù)。（4）重載不能改變操作符的優(yōu)先級(jí)別。（5）重載不能改變操作符的結(jié)合性。（6）除了對(duì)operator()外對(duì)其他重載操作符提供缺省實(shí)參都是非法的。（7）重載的操作符必須和用戶定義的自定義類型的對(duì)象一起使用，其參數(shù)至少應(yīng)有一個(gè)是類對(duì)象（或類對(duì)象的引用）?！?/p>

參數(shù)不能全部是C++的標(biāo)準(zhǔn)類型，以防止用戶修改用于標(biāo)準(zhǔn)類型數(shù)據(jù)的操作符的性質(zhì)。操作符重載的規(guī)則（續(xù)）第25頁(yè)/共49頁(yè)（8）用于類對(duì)象的操作符一般必須重載，但有兩個(gè)例外，操作符"="和"&"不必用戶重載。①賦值操作符（=）可以用于每一個(gè)類對(duì)象，可以利用它在同類對(duì)象之間相互賦值。②地址操作符&也不必重載，它能返回類對(duì)象在內(nèi)存中的起始地址。（9）應(yīng)當(dāng)使重載操作符的功能類似于該操作符作用于標(biāo)準(zhǔn)類型數(shù)據(jù)時(shí)所實(shí)現(xiàn)的功能。（10）操作符重載函數(shù)可以是類的成員函數(shù)，也可以是類的友元函數(shù)，還可以是既非類的成員也不是友元函數(shù)的普通函數(shù)。操作符重載的規(guī)則（續(xù)）第26頁(yè)/共49頁(yè)重載為友元函數(shù)時(shí)，參數(shù)個(gè)數(shù)=原操作數(shù)個(gè)數(shù)，且至少應(yīng)該有一個(gè)自定義類型的形參。重載為類成員函數(shù)時(shí)，參數(shù)個(gè)數(shù)=原操作數(shù)個(gè)數(shù)-1（后置++、--除外），調(diào)用對(duì)象作為第一個(gè)參數(shù)使用。MoneyMoney::operator+(constMoney&amount2){ Moneytemp; temp.all_cents=all_cents+amount2.all_cents; returntemp;}total=cost+tax;操作符重載的使用第27頁(yè)/共49頁(yè)重載>>和<<輸出操作符是一個(gè)雙目操作符，它返回一個(gè)ostream引用。重載定義的通用框架如下//重載output操作符的通用框架ostream&operator<<(ostream&os,constClassType&object){

//準(zhǔn)備對(duì)象的特定邏輯//成員的實(shí)際輸出os<<//...

//返回ostream對(duì)象returnos;}它的第一個(gè)實(shí)參是一個(gè)ostream對(duì)象的引用，第二個(gè)一般是一個(gè)特定類類型的const引用；返同類型是一個(gè)ostream引用，且它的值總是該輸出操作符所應(yīng)用的ostream對(duì)象；因?yàn)榈谝粋€(gè)實(shí)參是一個(gè)ostream引用所以輸出操作符必須定義為非成員函數(shù)，當(dāng)輸出操作符要求訪問(wèn)非公有成員時(shí)必須將它聲明為該類的友元。第28頁(yè)/共49頁(yè)

<<（插入操作符）：二元操作符cout<<"Hello!\n";操作數(shù)1：輸出流操作數(shù)2：字符串Moneyamount(100);amount.output(cout);intamount(100);cout<<amount;cout<<amount;重載<<操作符重載>>和<<第29頁(yè)/共49頁(yè)課后練習(xí)（課下自行完成）Page136：練習(xí)1第30頁(yè)/共49頁(yè)（2）2維數(shù)組類第31頁(yè)/共49頁(yè)二維數(shù)組的構(gòu)造template<classT>Array2D<T>::Array2D(intr，intc){if(r<0||c<0)throwBadInitializers();

if((!r||!c)&&(r||c)throwBadInitializers();rows=r;cols=c;

row=newArray1D<T>[r];for(inti=0;i<r;i++) row[i].Resize(c);//調(diào)整每個(gè)元素的大小}template<classT>voidArray1D<T>::ReSize(intsz){delete[]element;size=sz;element=newT[size];}第32頁(yè)/共49頁(yè)二維數(shù)組的復(fù)制構(gòu)造template<classT>Array2D<T>::Array2D(constArray2D<T>&m){rows=m.rows;cols=m.cols;row=newArray1D<T>[rows];for(inti=0;i<rows;i++) row[i]=m.row[i];//逐行復(fù)制}第33頁(yè)/共49頁(yè)下標(biāo)操作符重載：[]template<classT>Array1D<T>&Array2D<T>::operator[](inti)const{if(i<0||i>=rows)throwOutOfBounds();

returnrow[i];}Array2D<T>X;

X[i][j]分解為：(X.operator[i]).operator[j]先調(diào)用Array2D<T>::operator[]，返回指向X.row[i]的引用，再調(diào)用Array1D::operator[]。第34頁(yè)/共49頁(yè)二元減法操作符重載：-template<classT>Array2D<T>Array2D<T>::operator-(Array2D<T>&m)const{//返回w=(*this)-mif(rows!=m.rows||cols!=m.cols)throwSizeMismatch();Array2D<T>w(rows,cols);for(inti=0;i<rows;i++)w.row[i]=row[i]-m.row[i];returnw;}第35頁(yè)/共49頁(yè)二元乘法操作符重載：*template<classT>Array2D<T>Array2D<T>::operator*(Array2D<T>&m)const{//返回w=(*this)*mif(cols!=m.rows)throwSizeMismatch();Array2D<T>w(rows,cols);for(inti=0;i<rows;i++){for(intj=0;j<m.cols;j++)Tsum=(*this)[i][0]*m[0][j];for(intk=1;k<cols;k++)sum+=(*this)[i][k]*m[k][j];w[i][j]=sum;}returnw;}第36頁(yè)/共49頁(yè)課后練習(xí)（課下自行完成）Page137：練習(xí)5第37頁(yè)/共49頁(yè)4.2矩陣矩陣是一個(gè)數(shù)值構(gòu)成的表，具有行、列二維結(jié)構(gòu)；矩陣的行、列編號(hào)從1開始，而不是從0開始；矩陣元素表達(dá)法是x(i,j),而非x[i][j]；可以用2維數(shù)組來(lái)描述矩陣。第38頁(yè)/共49頁(yè)矩陣示例5×4矩陣第39頁(yè)/共49頁(yè)矩陣運(yùn)算轉(zhuǎn)置加法乘法第40頁(yè)/共49頁(yè)使用二維數(shù)組表示矩陣的缺陷矩陣下標(biāo)從1開始C++數(shù)組不支持常規(guī)矩陣運(yùn)算 ——需要為矩陣開發(fā)一個(gè)封裝類！第41頁(yè)/共49頁(yè)矩陣類Matrix（自學(xué)）第42頁(yè)/共49頁(yè)類Matrix的構(gòu)造函數(shù)template<classT>Matrix<T>::Matrix(intr，intc){if(r<0||c<0)throwBadInitializers();

if((!r||!c)&&(r||c)throwBadInitializers();rows=r;cols=c;

element=newT[r*c];}第43頁(yè)/共49頁(yè)類Matrix操作符重載：()template<classT>T&Matrix<T>::operator()(inti,intj)const{if(i<1||i>rows||j<1||j>cols)throwOutOfBoun