山大數據結構_4

1、3/15/202211.Arrays2.Matrices3.Special Matrices4.Sparse MatricesChapter4 Arrays and Matrices3/15/202221.矩陣ADT2.特殊矩陣3.稀疏矩陣本章重點3/15/20223數組的抽象數據類型描述抽象數據類型Array實例形如(index,value)的數據對集合，其中任意兩對數據的index值都各不相同操作Create()：創(chuàng)建一個空的數組Store(index,value)：添加數據(index,value)，同時刪除具有相同index值的數據對（如果存在）Retrieve(index)：返回索引

2、值為index的數據對4.1 Arrays3/15/20224n在C+中，值為整數類型的k維數組score可用如下語句來創(chuàng)建： int scoreu1u2u3.ukn為實現與數組相關的函數Store和Retrieve，必須把數組索引i1i2i3.ik映射到0,n-1中的某個數map(i1,i2,i3,.,ik)，使得該索引所對應的元素值存儲在以下位置：start+map(i1,i2,i3,.,ik)*sizeof(int)C+數組3/15/20225n當數組維數為1時（即k=1），使用以下函數：map(i1)=i1一維數組3/15/20226行主映射和列主映射Row- and Column-M

3、ajor Mappings3/15/20227n行主次序所對應的映射函數為：map(i1,i2)=i1u2+i2n其中u2是數組的列數。n在行主映射模式中，在對索引i1i2進行編號時,第0，.i1-1行中的i1u2個元素以及第i1行中的前i2個元素都已經被編號。二維數組行主映射3/15/20228n三維數組的行主映射函數為：map(i1,i2,i3)=i1u2u3+i2u3+i3三維數組行主映射3/15/20229templateclass Array1D public:Array1D(int size = 0);Array1D(const Array1D& v); / 復制構造函數A

4、rray1D() delete element;T& operator(int i) const;int Size() return size;Array1D& operator=(const Array1D& v);Array1D operator+() const; / 一元加法操作符Array1D operator+(const Array1D& v) const;Array1D operator-() const; / 一元減法操作符Array1D operator-(const Array1D& v) const;Array1D operato

5、r*(const Array1D& v) const;Array1D& operator+=(const T& x);一維數組的類定義3/15/202210private:int size;T *element; /一維數組;一維數組的類定義3/15/202211templateclass Array2D public:Array2D(int r = 0, int c = 0);Array2D(const Array2D& m); / 復制構造函數Array2D() delete row;int Rows() const return rows;int Colu

6、mns() const return cols;Array1D& operator(int i) const;Array2D& operator=(const Array2D& m);Array2D operator+() const; / 一元加法操作符Array2D operator+(const Array2D& m) const;Array2D operator-() const; / 一元減法操作符Array2D operator-(const Array2D& m) const;Array2D operator*(const Array2D&

7、amp; m) const;Array2D& operator+=(const T& x);二維數組的類定義3/15/202212private:int rows, cols; / 數組維數Array1D *row; / 一維數組的數組;二維數組的類定義3/15/202213n一個mn 的矩陣是一個m行、n 列的表，其中m 和n 是矩陣的維數。n矩陣通常被用來組織數據。4.2 Metrices3/15/202214矩陣3/15/202215n對于矩陣來說，最常見的操作就是矩陣轉置、矩陣加、矩陣乘。n一個mn 矩陣的轉置矩陣是一個nm的矩陣MT，它與M之間存在以下關系：nMT (

8、i,j) = M(j,i ), 1in，1jmn僅當兩個矩陣的維數相同時（即具有相同的行數和列數），才可以對兩個矩陣求和。兩個mn 矩陣A 和B 相加所得到的mn 矩陣C 如下：nC(i,j ) = A(i,j )+B(i,j)，1in，1jm矩陣的操作3/15/202216矩陣的操作n僅當一個mn 矩陣A 的列數與另一個qp 矩陣B 的行數相同時（即n = q），才可以執(zhí)行矩陣乘法A*B。A*B 所得到的mp 矩陣C 滿足以下關系：3/15/202217templateclass Matrix public:Matrix(int r = 0, int c = 0);Matrix(const

9、Matrix& m); /復制構造函數Matrix() delete element;int Rows() const return rows;int Columns() const return cols;T& operator()(int i, int j) const;Matrix& operator=(const Matrix& m);Matrix operator+() const; / 一元加法Matrix operator+(const Matrix& m) const;Matrix operator-() const; / 一元減法Mat

10、rix operator-(const Matrix& m) const;Matrix operator*(const Matrix& m) const;Matrix& operator+=(const T& x);類matrix3/15/202218private:int rows, cols; / 矩陣維數T *element; / 元素數組;類matrix3/15/202219 特殊方陣n對角矩陣(Diagonal Matrices )n三 對 角 矩 陣 ( T r i d i a g o n a l Matrix )n三角矩陣(Triangular M

11、atrices)n對稱矩陣(Symmetric Matrices )4.3 Special Matrices3/15/202220nM是一個對角矩陣當且僅當ij時有M(i,j)=0。對角矩陣(diagonal)3/15/202221nM是一個三對角矩陣當且僅當|i-j|1時有M(i,j)=0。三對角矩陣(tridiagonal)3/15/202222nM是一個下三角矩陣當且僅當ij時有M(i,j)=0。上三角矩陣(uppertriangular)3/15/202224nM是一個對稱矩陣當且僅當對于所有的i和j有M(i,j)=M(j,i)。對稱矩陣(symmetric)3/15/2022253/

12、15/202226n可以采用二維數組來描述一個元素類型為T的nn對角矩陣D：T dnnn使用數組元素di-1j-1來表示矩陣元素D(i,j)，這種描述形式所需要的存儲空間n2*sizeof(T)。n思考：節(jié)省空間的存貯方式？對角矩陣(diagonal)描述3/15/202227n一個對角矩陣最多包含n個非0元素，所以可以采用如下所示的一維數組來描述對角矩陣：Tdnn使用數組元素di-1來表示矩陣元素Di,i。根據對角矩陣的定義，所有未在一維數組中出現的矩陣元素均為0。對角矩陣描述方案3/15/202228templateclass DiagonalMatrixpublic:DiagonalMa

13、trix(int size=10) n = size;d = new Tn;DiagonalMatrix()delete d;/析構函數DiagonalMatrix& Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩陣維數T *d;/存儲對角元素的一維數組;DiagonalMatrix類3/15/202229templateDiagonalMatrix &DiagonalMatrix:Store(const T&x,int i,int j)/把x存為D(i,j)

14、.if(i1|jn|jn)throw OutOfBounds();if(i!=j & x!=0) throw MustBeZero();if(i=j) di-1=x;return *this; 復雜性？DiagonalMatrix類3/15/202230templateT DiagonalMatrix:Retrieve(inti,intj) const/返回D(i,j).if(i1|jn|jn)throw OutOfBounds();if(i=j) return di-1;else return 0; 復雜性？DiagonalMatrix類3/15/202231n在一個nn三對角矩陣T

15、中，非0元素排列在如下的三條對角線上：n1)主對角線i=j。n2)主對角線之下的對角線(稱低對角線)i=j+1。n3)主對角線之上的對角線(稱高對角線)i=j-1。三對角矩陣(tridiagonal)3/15/202232n這三條對角線上的元素總數為? 。n行映射？n列映射？n對角線映射？三對角矩陣描述3/15/202233templateclass TridiagonalMatrixpublic:TridiagonalMatrix(int size=10)n=size;t=new T3*n-2;TridiagonalMatrix()delete t;TridiagonalMatrix&

16、; Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩陣維數T *t;/存儲三對角矩陣的一維數組;TridiagonalMatrix類3/15/202234templateTridiagonalMatrix& TridiagonalMatrix:Store(const T& x,int i,int j)/把x存為T(i,j)if(i1|jn|jn) throw OutOfBounds();switch(i-j)case1:/低對角線ti-2=x;break;case0:/

17、主對角線tn+i-2=x; break;case-1:/高對角線t2*n+i-2=x;break;default:if(x!=0)throw MustBeZero(); return *this; 復雜性？TridiagonalMatrix類3/15/202235templateTTridiagonalMatrix:Retrieve(int i,int j)const/返回T(i,j)if(i1|jn|jn) throw OutOfBounds();switch(i-j)case1:/低對角線return ti-2;case0:/主對角線return tn+i-2;case-1:/高對角線re

18、turn t2*n+i-2;default:return 0; 復雜性？TridiagonalMatrix類3/15/202236n行映射描述map(i,j)=(i-1)*3-1+(j-i+1)=2i+j-3三對角矩陣描述3/15/202237n在一個三角矩陣中，非0元素都位于所示的“非0”區(qū)域。對于這兩種情況，非0區(qū)域的元素總數均為：三角矩陣3/15/202238n兩種三角矩陣都可以用一個大小為n(n+1)/2的一維數組來進行描述。n按行映射?(在元素L(i, j)之前共有 ? 個元素位于非0區(qū)域?)n按列映射?三角矩陣3/15/202239templateclass LowerMatrix

19、public:LowerMatrix(int size=10)n=size;t=new Tn*(n+1)/2;LowerMatrix()delete t;LowerMatrix&Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩陣維數T *t;/存儲下三角矩陣的一維數組;LowerMatrix類3/15/202240n一個nn的對稱矩陣可以用一個大小為n(n+1)/2的一維數組來描述，可參考三角矩陣的存儲模式來存儲矩陣的上三角或下三角。n可以根據已存儲的元素來推算出未存儲的元素。

20、對稱矩陣(symmetric)3/15/2022411.如果一個mn 矩陣中有“許多”元素為0，則稱該矩陣為稀疏矩陣。2.不是稀疏的矩陣被稱為稠密矩陣(den se)。3.在稀疏矩陣和稠密矩陣之間并沒有一個精確的界限。4.本節(jié)中我們規(guī)定若一個矩陣是稀疏矩陣,則其非0元素的數目應小于n2/3。4.4 Sparse Matrices3/15/202242n某超級市場正在開展一項關于顧客購物品種的研究。為了完成這項研究，收集了10 00個顧客的購物數據，這些數據被組織成一個矩陣purchases，其中purchases (i, j) 表示顧客j 所購買的商品i 的數量。n假定該超級市場有10 000

21、種不同的商品，那么purchases 將是一個10 0001 0 0 0的矩陣。如果每個顧客平均購買了20種不同商品，那么在10 000 000個矩陣元素將大約只有20 000個元素為非0，并且非0元素的分布沒有很明確的規(guī)律。稀疏矩陣例子3/15/202243template class Term private:int row, col;T value;；類Term3/15/202244稀疏矩陣數組描述3/15/202245n存儲圖4-10a 中的九個非0元素所需要的存儲器字節(jié)數為21*sizeof(int)+ 9*sizeof(T)。n如果用一個48的數組來描述這個矩陣，則需要的字節(jié)數為3

22、2*sizeof(T)。n假定T是int 類型且sizeof(T) = 2，那么圖4-10b 中的描述需60個字節(jié)，而采用48的數組則需要64個字節(jié)。存貯空間3/15/202246n對例4-5中的矩陣purchase，其一維數組描述需60000*sizeof(int)個字節(jié)，n而二維數組描述則需10 000 000* sizeof(int)個字節(jié)。n如果一個整數占2個字節(jié)，則節(jié)省的空間為19 880 000字節(jié)。存貯空間3/15/202247templateclass SparseMatrixfriend ostream& operator (ostream&, const S

23、parseMatrix&);friend istream& operator (istream&, SparseMatrix&);public :SparseMatrix(int maxTerms = 10);SparseMatrix() delete a;void Transpose(SparseMatrix &b) const;void Add(const SparseMatrix &b, SparseMatrix &c) const;類SparseMatrix3/15/202248private:void Append(const

24、Term& t);int rows, cols; /矩陣維數int terms; / 非0元素數目Term *a; / 存儲非0元素的數組int MaxTerms; / 數組a的大小; ;類SparseMatrix3/15/202249templatevoid SparseMatrix: Transpose(SparseMatrix &b) const/把*this 的轉置結果送入b if (terms b.MaxTerms) throw NoMem(); /b有足夠空間?/設置轉置特征b.cols = rows;b.rows = cols;b.terms = terms;/初

25、始化int *ColSize, *RowNext;ColSize = new intcols+1;/ColSizei表示矩陣第i列中的非0元素數RowNext = new introws+1;/RowNexti表示矩陣第i行的下一個非0元素在b中的位置轉置一個稀疏矩陣3/15/202250/計算*this每一列的非0元素數for (int i = 1; i = cols; i+) /初始化ColSizei = 0;for (int = 0; i terms; i+)ColSizeai.col+;/給出b中每一行的起始點RowNext1 = 0;for (int i = 2; i = cols;

26、 i+)RowNexti = RowNexti - 1+ColSizei - 1;轉置一個稀疏矩陣3/15/202251/執(zhí)行轉置操作for (int i = 0; i terms; i+) int j = RowNextai.col+; /在b中的位置b.aj.row = ai.col;b.aj.col = ai.row;b.aj.value = ai.value; 復雜性？轉置一個稀疏矩陣3/15/202252templatevoid SparseMatrix:Append(const Term& t)/把一個非0元素t添加到*this之中if (terms = MaxTerms)

27、 throw NoMem();aterms = t;terms+ ;添加一個非0元素3/15/202253templatevoid SparseMatrix:Add(const SparseMatrix &b, SparseMatrix &c) const/計算c = (*this)+b./驗證可行性if (rows != b.rows | cols != b.cols)throw SizeMismatch(); /不能相加/設置結果矩陣c的特征c.rows = rows;c.cols = cols;c.terms = 0; /初值/定義*this 和b的游標int ct =

28、0, cb = 0;兩個稀疏矩陣相加3/15/202254/在*this 和b 中遍歷while (ct terms & cb b.terms) /每一個元素的行主索引int indt = act.row*cols+act.col;int indb = b.acb.row*cols+b.acb.col;if (indt indb) /b 的元素在后c.Append(act) ;ct+; /*this的下一個元素兩個稀疏矩陣相加3/15/202255else if (indt = indb) /位置相同/僅當和不為0時才添加到c中if (act.value+b.acb.value) Term t;t.row = act.row;t.col = act.col;t.value = act.value+b.acb.value;c.Append(t) ; ct+; cb+; /*this 和b的下一個元素else c.Append(b.acb); cb+; /b的下一個元素兩個稀疏矩陣相加3/15/202256/復制剩余元素for (; ct terms; ct+)c.Append(act)