數(shù)組和矩陣-1

1、2/25/20221數(shù)組和矩陣第四章2/25/20222數(shù)組矩陣特殊矩陣稀疏矩陣本章內(nèi)容2/25/20223矩陣ADT特殊矩陣稀疏矩陣本章重點(diǎn)44.1 數(shù)組4.1.1 抽象數(shù)據(jù)類型4.1.2 C+數(shù)組4.1.3 行主映射和列主映射4.1.4 類Array1D4.1.5 類 Array2D2/25/20225數(shù)組的抽象數(shù)據(jù)類型描述抽象數(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ì)（如果存在）

2、Retrieve(index)：返回索引值為index的數(shù)據(jù)對(duì)4.1.1 Arrays2/25/20226n數(shù)組的索引: ni1i2i3ikn k維數(shù)組：nint scoreu1u2u3uk. (ui-正的常量或有常量表示的表達(dá)式）n0ijuj 0 j k n數(shù)組元素的個(gè)數(shù): nn=u1u2u3uk n內(nèi)存空間: nn x sizeof(int) 字節(jié).nc+ 編譯器為數(shù)組預(yù)留空間: nstart -start + sizeof(score) -14.1.2 C+數(shù)組74.1.3 行主映射和列主映射l為了實(shí)現(xiàn)與數(shù)組相關(guān)的函數(shù)Store和Retrieve，必須確定索引值在start, start

3、+n*sizeof(score)-1中的相應(yīng)位置 :li1i2ik start + map(i1,i2,ik) * sizeof(int)lmap(i1,i2,ik): 0-n-1l對(duì)一維數(shù)組： lmap(i1) = i1l對(duì)二維數(shù)組2/25/20228行主映射和列主映射Row- and Column-Major Mappings9行主映射和列主映射行主映射Int su1u2映射函數(shù): map(i1,i2)= u2 * i1 + i2在行主映射模式中，在對(duì)索引i1i2進(jìn)行編號(hào)時(shí),第0，.i1-1行中的i1u2個(gè)元素以及第i1行中的前i2個(gè)元素都已經(jīng)被編號(hào)。0 s001s01. .U2-1s0u

4、2-1U2s10U2+1s11 .s1u2-1.map(i1,i2) si1i2.su1-10su1-11 .U2*(u1-1)+u2-1su1-1u2-110行主映射和列主映射列主映射映射函數(shù): map(i1,i2)= u1 * i2 + i1在列主映射模式中，在對(duì)索引i1i2進(jìn)行編號(hào)時(shí),第0，.i2-1列中的i2u1個(gè)元素以及第i2列中的前i1個(gè)元素都已經(jīng)被編號(hào)。在 C+ 使用的是哪一種?行主映射!0 s001s10 .u1-1su1-10s01s11 .su1-11.map(i1,i2) si1i2.s0u2-1s1u2-1 .u1 * (u2-1) + (u1-1)su1-1u2-1行

5、主映射與列主映射2/25/202211u1*u2u2u2*u1u12/25/202212n三維數(shù)組的行主映射函數(shù)為：map(i1,i2,i3)=i1u2u3+i2u3+i3三維數(shù)組行主映射u1*u2*u3u2*u3u313行主映射和列主映射對(duì)三維數(shù)組 (int scoreu1u2u3) 索引按行主次序排列 int score324：000,001,002,003,0l0,0ll,012,013,100,l0l,102,103,110,111,112,113,200,201,202,203,210,211,2l2,213首先列出所有第一個(gè)坐標(biāo)為0的索引，然后是第一個(gè)坐標(biāo)為1的索引， 。第一個(gè)坐標(biāo)

6、相同的所有索引按其第二個(gè)坐標(biāo)的遞增次序排列，前兩個(gè)坐標(biāo)相同的所有索引按其第三個(gè)坐標(biāo)的遞增次序排列。映射函數(shù):map(i1,i2,i3) = i1u2u3+i2u3+i3列主映射，映射函數(shù) ？14u盡管C+支持一維數(shù)組，但這種支持很不夠。u可以使用超出正常范圍之外的索引值來(lái)訪問(wèn)數(shù)組。u例如對(duì)int a9，C+可以訪問(wèn)數(shù)組元素a-3，a9和a90，盡管-3，9和90是非法的索引u也不能對(duì)一維數(shù)組進(jìn)行諸如加法和減法等操作。u為了克服這些不足，定義了類Array1D。u該類的每個(gè)實(shí)例X都是一個(gè)一維數(shù)組。uX的元素存儲(chǔ)在數(shù)組X.element之中，u第i個(gè)元素位于X.element i，0isize。2

7、/25/202215templateclass Array1D public:Array1D(int size = 0);Array1D(const Array1D& v); / 復(fù)制構(gòu)造函數(shù)Array1D() delete element;T& operator(int i) const;int Size() return size;Array1D& operator=(const Array1D& v);Array1D operator+() const; / 一元加法操作符Array1D operator+(const Array1D& v) co

8、nst;Array1D operator-() const; / 一元減法操作符Array1D operator-(const Array1D& v) const;Array1D operator*(const Array1D& v) const;Array1D& operator+=(const T& x);private:int size;T *element; /一維數(shù)組;4.1.4 一維數(shù)組的類定義16構(gòu)造函數(shù)和復(fù)制構(gòu)造函數(shù) templateArray1D:Array1D(int sz)/ 一維數(shù)組的構(gòu)造函數(shù) if (sz0) throw BadInit

9、ializers(); size=sz; element=new Tsz; templateArray1D:Array1D(const Array1D& v)/ 一維數(shù)組的復(fù)制構(gòu)造函數(shù) size=v.size; element=new Tsize; / 申請(qǐng)空間 for (int i=0; isize; i+) / 復(fù)制元素 elementi=v.elementi;17操作符 = templateT& Array1D:operator(int i) const/ 返回指向第i個(gè)元素的引用if (i = size) throw OutOfBounds();return eleme

10、nti; templateArray1D& Array1D:operator=(const Array1D& v)/ 重載賦值操作符= if (this != &v) / 不是自我賦值 size=v.size; delete element; / 釋放原空間 element = new Tsize; / 申請(qǐng)空間 for (int i = 0; i size; i+) /復(fù)制元素 elementi=v.elementi; return *this;18操作符 templateArray1D Array1D: operator-(const Array1D& v)

11、 const/ 返回w = (*this) - v if (size != v.size) throw SizeMismatch(); Array1D w(size); / 創(chuàng)建結(jié)果數(shù)組w for (int i = 0; i size; i+) w.elementi=elementi-v.elementi; return w; templateArray1D Array1D:operator-() const/ 返回w = -(*this)Array1D w(size); / 創(chuàng)建結(jié)果數(shù)組wfor (int i = 0; i size; i+) w.elementi = -elementi;r

12、eturn w;19操作符 += templateArray1D& Array1D:operator+=(const T& x) /把x 加到( * this )的每個(gè)元素上 for (int i = 0; i size; i+) elementi += x; return *this; 204.1.5 類 Array2Dtemplateclass Array2D public:Array2D(int r = 0, int c = 0);Array2D(const Array2D& m); / 復(fù)制構(gòu)造函數(shù)Array2D() delete row;int Rows()

13、const return rows;int Columns() 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;Array2

14、D operator*(const Array2D& m) const;Array2D& operator+=(const T& x);private:int rows, cols; / 數(shù)組維數(shù)Array1D *row; / rowi是類型為Array1D的一維數(shù)組，它代表二維數(shù)組的第i行。;21構(gòu)造函數(shù)templateArray2D:Array2DArray2D(int r, int c)/ 二維數(shù)組的構(gòu)造函數(shù)/ 合法的r 和c if (r 0 | c 0) throw BadInitializers(); if (!r | !c) & (r | c) th

15、row BadInitializers(); rows = r; cols = c; row = new Array1D r; / 分配r個(gè)具有缺省大小的一維數(shù)組 for (int i = 0; i r; i+) / 調(diào)整每個(gè)元素的大小 rowi.ReSize(c);Array1D Array1D : ReSizeReSize(int sz) delete element; size = sz; element = new T size; return *this;22復(fù)制構(gòu)造函數(shù)templateArray2D:Array2DArray2D(const Array2D& m)/ 二維數(shù)

16、組的復(fù)制構(gòu)造函數(shù) rows = m.rows; cols = m.cols; row = new Array1D rows;/分配指向一維數(shù)組的數(shù)組 for (int i = 0; i rows; i+) / 復(fù)制每一行 rowi = m.rowi; /ARRAY1D的 = 23 操作符 templateArray1D& Array2D:operator(int i) const /二維數(shù)組的第一個(gè)索引if (i = rows) throw OutOfBounds(); return rowi; Array2D x;Xij24操作符 -templateArray2D Array2D:

17、operator-operator-(const Array2D& m) const/返回w = (*this) - m. if (rows != m.rows | cols != m.cols) throw SizeMismatch(); Array2D w(rows,cols); /創(chuàng)建存放結(jié)果的數(shù)組w for (int i = 0; i rows; i+) w.rowi = rowi - m.rowi; return w;25操作符 *templateArray2D Array2D: operator*(const Array2D& m) const/ 矩陣乘，返回w =

18、 (*this) * m.if (cols != m.rows) throw SizeMismatch();/ 創(chuàng)建存放結(jié)果的數(shù)組wArray2D w(rows, m.cols);for (int i = 0; i rows; i+) for (int j = 0; j m.cols; j+) T sum = (*this)i0 * m0j; for (int k = 1; k cols; k+) sum += (*this)ik * mkj; wij = sum; return w;264.2 矩陣4.2.1 定義和操作4.2.2 類 Matrix274.2.1 定義和操作mxn 矩陣:m行

19、和n列的表.M(i,j):矩陣M 中第i 行、第j 列1im，1jn 的元素 .常用矩陣操作轉(zhuǎn)置矩陣加矩陣乘 28矩陣操作轉(zhuǎn)置：一個(gè)mn 矩陣的轉(zhuǎn)置矩陣是一個(gè)nm的矩陣MTMT(i,j)=M(j,i), 1in, 1jm矩陣加：僅當(dāng)兩個(gè)矩陣的維數(shù)相同時(shí)，才可對(duì)矩陣求和A , B : m x n 矩陣C=A+BC(i,j) = A(i,j) + B(i,j), 1im, 1jnn1kqj1 m,i1 j)B(k, * k)A(i, j)C(i,矩陣乘：僅當(dāng)一個(gè)矩陣A 列數(shù)與另一個(gè)矩陣B 的行數(shù)相同，才可執(zhí)行A*BnA : m x n 矩陣; B: n x q 矩陣. nC= A*B : m x

20、q 矩陣 294.2.2 類Matrixn矩陣描述.n 使用二維數(shù)組nT Mmnn M(i,j): Mi-1j-1nP46 程序2-19 矩陣加法nP49 程序2-22 矩陣轉(zhuǎn)置nP52 程序2-24 兩個(gè)n*n矩陣相乘nP53 程序2-25 一個(gè)m*n矩陣與一個(gè)n*p矩陣相乘n 使用類 Array2D nArray2D M(m,n)nM(i,j): Mi-1j-1 2/25/202230templateclass Matrix public:Matrix(int r = 0, int c = 0);Matrix(const Matrix& m); /復(fù)制構(gòu)造函數(shù)Matrix() de

21、lete 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; / 一元減法Matrix operator-(const Matrix& m)

22、 const;Matrix operator*(const Matrix& m) const;Matrix& operator+=(const T& x);private:int rows, cols; / 矩陣維數(shù)T *element; / 元素?cái)?shù)組;4.2.2 類matrix31Matrix 操作符（） templateT& Matrix:operator()(int i, int j) const/ 返回一個(gè)指向元素(i,j)的引用if (irows|jcols) throw OutOfBounds();return element(i-1)*cols +

23、j-1; 讀 P139 程序4-13 Matrix 構(gòu)造函數(shù)讀 P140 程序4-15 Matrix 減法操作符32Matrix 操作符*templateMatrix Matrix: operator*(const Matrix& m) const/ 矩陣乘法，返回w =(*this)*m. if (cols!=m.rows) throw SizeMismatch(); Matrix w(rows, m.cols); / 結(jié)果矩陣 / 為*this, m和w定義游標(biāo) / 并設(shè)定初始位置為(1,1) int ct=0, cm=0, cw=0;33Matrix 操作符 *for (int

24、i=1; i=rows; i+) / 對(duì)所有的i和j計(jì)算w(i,j)for (int j=1; j=m.cols; j+) / 計(jì)算出結(jié)果的第i行 T sum=elementct*m.elementcm; /計(jì)算w(i,j)的第一項(xiàng) for (int k=2; k1時(shí)，有M(i,j) = 0下三角矩陣下三角矩陣(lower triangular): 當(dāng)且僅當(dāng)ij時(shí)，有M(i,j) = 0對(duì)稱矩陣對(duì)稱矩陣(symmetric):當(dāng)且僅當(dāng)對(duì)于所有的i和j，有M(i,j) = M(j,i)2/25/2022372/25/202238n可以采用二維數(shù)組來(lái)描述一個(gè)元素類型為T的nn對(duì)角矩陣D：T dnn

25、n使用數(shù)組元素di-1j-1來(lái)表示矩陣元素D(i,j)，這種描述形式所需要的存儲(chǔ)空間n2*sizeof(T)。n思考：節(jié)省空間的存貯方式？4.3.2對(duì)角矩陣(diagonal)描述394.3.2 對(duì)角矩陣u 矩陣描述uT dnuD(i,j) di-1 i =juD(i,j) 0 iju需要 n x sizeof(T)字節(jié)空間2/25/202240templateclass DiagonalMatrixpublic:DiagonalMatrix(int size=10) n = size;d = new Tn;DiagonalMatrix()delete d;/析構(gòu)函數(shù)DiagonalMatri

26、x& Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩陣維數(shù)T *d;/存儲(chǔ)對(duì)角元素的一維數(shù)組;DiagonalMatrix類2/25/202241templateDiagonalMatrix &DiagonalMatrix:Store(const T&x,int i,int j)/把x存為D(i,j).if(i1|jn|jn)throw OutOfBounds();if(i!=j & x!=0) throw MustBeZero();if(i=j) d

27、i-1=x;return *this; 復(fù)雜性？DiagonalMatrix類-Store2/25/202242templateT DiagonalMatrix:Retrieve(inti,intj) const/返回D(i,j).if(i1|jn|jn)throw OutOfBounds();if(i=j) return di-1;else return 0; 復(fù)雜性？DiagonalMatrix類-Retrieve434.3.3 三對(duì)角矩陣三條非0元素對(duì)角線 :主對(duì)角線 : i = j主對(duì)角線之下的對(duì)角線（稱低對(duì)角線） : i = j+1主對(duì)角線之上的對(duì)角線（稱高對(duì)角線） : i = j-

28、1三條對(duì)角線上的3n-2個(gè)元素: T t3n-2映射 按行映射 2,1,3,1,3,5,2,7,9,0按列映射 2,3,1,1,5,3,2,9,7,0按對(duì)角線的次序映射：3,5,9,2,1,2,0,1,3,744三對(duì)角矩陣按照對(duì)角線的次序（從最下面的對(duì)角線開始）進(jìn)行映射D(2,1)- t0D(3,2)- t1D(n,n-1) - tn-2D(1,1)- tn-1D(2,2)- tn.D(n, n)- t(n-2)+n = t2n-2D(1,2)- t2n-1D(2,3)- t2nD(n-1,n) - t(2n-2)+(n-1) = t3n-3 ti-2 i=j+1D(i,j) tn+i-2 i

29、=j t2*n+i-2 i=j-1 0 |i-j|1讀程序4-182/25/202245templateclass TridiagonalMatrixpublic:TridiagonalMatrix(int size=10)n=size;t=new T3*n-2;TridiagonalMatrix()delete t;TridiagonalMatrix& Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩陣維數(shù)T *t;/存儲(chǔ)三對(duì)角矩陣的一維數(shù)組;TridiagonalMatri

30、x類46templateTridiagonalMatrix& TridiagonalMatrix: Store(const T& x, int i, int j)/ 把x存為D(i , j)if (i1|jn|jn) throw OutOfBounds();switch (i-j) case 1: / 低對(duì)角線 ti-2 = x; break; case 0: / 主對(duì)角線 tn+i-2 = x; break; case -1: / 高對(duì)角線 t2*n+i-2 = x; break; default: if(x!=0) throw MustBeZero(); return *t

31、his;template T TridiagonalMatrix: Retrieve(int i, int j) const/ 返回D (i, j)if (i1|jn|jn) throw OutOfBounds();switch (i-j) case 1: /低對(duì)角線 return ti-2; case 0: / 主對(duì)角線 return tn+i-2; case -1: / 高對(duì)角線 return t2*n+i-2; default: return 0; 2/25/202247n行映射描述map(i,j)=(i-1)*3-1+(j-i+1)=2i+j-34.3.2 三對(duì)角矩陣描述2/25/202248n在一個(gè)三角矩陣中，非0元素都位于所示的“非0”區(qū)域。對(duì)于這兩種情況，非0區(qū)域的元素總數(shù)均為：4.3.3 三角矩陣494.3.4 三角矩陣矩陣描述使