三元組順序表矩陣表示

1、數(shù)據(jù)結(jié)構(gòu)第5章 數(shù)組與廣義表1第5章 數(shù)組和廣義表 5.1 數(shù)組的定義 5.2 數(shù)組的順序表示和實(shí)現(xiàn) 5.3 矩陣的壓縮存儲(chǔ) 5.4 廣義表的定義 5.5 廣義表的存儲(chǔ)結(jié)構(gòu) 5.6 m元多項(xiàng)式的表示 5.7 廣義表的遞歸算法25.1 數(shù)組的定義ADT Array 數(shù)據(jù)對(duì)象：Daj1,j2,.,ji ,.jn |ji =0,.,bi-1, i=1,2,.,n, 稱 n(0) 為數(shù)組的維數(shù)， bi為數(shù)組第 i 維的長(zhǎng)度，ji為數(shù)組元素的第i維下標(biāo)，aj1,.,jn ElemSet 數(shù)據(jù)關(guān)系：RR1, R2, ., Rn,Ri | 0jkbk-1, 1kn 且k i, 0jibi-2, aj1 ,.

2、,ji ,.,jn , aj1 ,.ji+1,.,jn D, i=2,.,n 35.1 數(shù)組的定義基本操作：InitArray(&A, n, bound1, ., boundn)操作結(jié)果：若維數(shù) n 和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組 A。DestroyArray(&A)初始條件：數(shù)組 A 已經(jīng)存在。操作結(jié)果：銷毀數(shù)組 A。Value(A, &e, index1, ., indexn)初始條件：A 是 n 維數(shù)組，e 為元素變量，隨后是 n 個(gè)下標(biāo)值。操作結(jié)果：若各下標(biāo)不超界,則e賦值為所指定的A的元素值,并返回OK。Assign(&A, e, index1, ., indexn)初始條件：A

3、是 n 維數(shù)組，e 為元素變量，隨后是 n 個(gè)下標(biāo)值。操作結(jié)果：若下標(biāo)不超界，則將 e 的值賦給A中指定下標(biāo)的元素。 ADT Array45.2 數(shù)組的順序表示和實(shí)現(xiàn)由于數(shù)組類型不作插入和刪除的操作，因此只需要通過(guò)順序映象得到它的存儲(chǔ)結(jié)構(gòu)，即借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。通常有兩種映象方法：即“以行(序)為主(序)“row-major的映象方法和”以列(序)為主(序)“ column-major 的映象方法。將多維數(shù)組映射到一維數(shù)組的方法 representations of a multidimensional array55.2 數(shù)組的順序表示和實(shí)現(xiàn)以二維數(shù)

4、組 a m, n為例，其在內(nèi)存中的映像既可以如下排列（行優(yōu)先）：a00, a01, , a0,n-1,a10,a11,a1,n-1,am-1,0,am-1,n-1也可以如下排列（列優(yōu)先）：a00, a10, , am-1,0,a01,a11,am-1,1,a0,n-1,am-1,n-111121314151621222324252631323334353641424344454611121314151621222324252631323334353641424344454611213141122232421323334314243444152535451626364665.2 數(shù)組的順序表示和

5、實(shí)現(xiàn)假設(shè)二維數(shù)組 Rmn 中每個(gè)數(shù)據(jù)元素占L個(gè)存儲(chǔ)地址，并以 LOC(i,j) 表示下標(biāo)為 (i,j) 的數(shù)據(jù)元素的存儲(chǔ)地址，則該數(shù)組中任何一對(duì)下標(biāo) (i,j) 對(duì)應(yīng)的數(shù)據(jù)元素在以行為主的順序映象中的存儲(chǔ)地址為：LOC(i,j) = LOC(0,0) + (i*n+j)*L在以列為主的順序映象中的存儲(chǔ)地址為：LOC(i,j) = LOC(0,0) + (j*m+i)*L其中 LOC(0,0) 是二維數(shù)組中第一個(gè)數(shù)據(jù)元素（下標(biāo)為(0,0)）的存儲(chǔ)地址，稱為數(shù)組的 基地址 或基址。75.2 數(shù)組的順序表示和實(shí)現(xiàn)類似地，假設(shè)三維數(shù)組 Rpmn 中每個(gè)數(shù)據(jù)元素占 L 個(gè)存儲(chǔ)地址，并以 LOC(i,j,

6、k) 表示下標(biāo)為(i,j,k) 的數(shù)據(jù)元素的存儲(chǔ)地址，則該數(shù)組中任何一對(duì)下標(biāo)(i,j,k) 對(duì)應(yīng)的數(shù)據(jù)元素在以行為主的順序映象中的存儲(chǔ)地址為：LOC(i,j,k) = LOC(0,0,0) + (imn + jn+k)L85.2 數(shù)組的順序表示和實(shí)現(xiàn)templateclass Array1D friend ostream& operator (ostream&, const Array1D&); public: Array1D(int size = 0); Array1D(const Array1D& v); / copy constructor Array1D() delete elemen

7、t; T& operator(int i) const; int Size() return size; Array1D& operator=(const Array1D& v); Array1D operator+() const; / unary + Array1D operator+(const Array1D& v) const; Array1D operator-() const; / unary minus Array1D operator-(const Array1D& v) const; Array1D operator*(const Array1D& v) const; Ar

8、ray1D& operator+=(const T& x); Array1D& ReSize(int sz); private: int size; T *element; / 1D array;Sahniarray1d.hCode from the book:Sartaj Sahni, Data Structures, Algorithms, and Applications in C+后面有大字版本95.2 數(shù)組的順序表示和實(shí)現(xiàn)templateclass Array1D friend ostream& operator (ostream&, const Array1D&); public:

9、 Array1D(int size = 0); Array1D(const Array1D& v); / copy constructor Array1D() delete element; T& operator(int i) const; int Size() return size;Sahniarray1d.h105.2 數(shù)組的順序表示和實(shí)現(xiàn)templateclass Array1D . Array1D& operator=(const Array1D& v); Array1D operator+() const; / unary + Array1D operator+(const Ar

10、ray1D& v) const; Array1D operator-() const; / unary minus Array1D operator-(const Array1D& v) const; Array1D operator*(const Array1D& v) const; Array1D& operator+=(const T& x); Array1D& ReSize(int sz); private: int size; T *element; / 1D array;Sahniarray1d.h115.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D:Array1D(in

11、t sz)/ Constructor for one-dimensional arrays. if (sz 0) throw BadInitializers(); size = sz; element = new Tsz;Sahniarray1d.h構(gòu)造函數(shù)125.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D:Array1D(const Array1D& v)/ Copy constructor for one-dimensional arrays. size = v.size; element = new Tsize; / get space for (int i = 0; i s

12、ize; i+) / copy elements elementi = v.elementi;Sahniarray1d.h構(gòu)造函數(shù)135.2 數(shù)組的順序表示和實(shí)現(xiàn)重載 templateT& Array1D:operator(int i) const/ Return reference to element i. if (i = size) throw OutOfBounds(); return elementi;Sahniarray1d.h145.2 數(shù)組的順序表示和實(shí)現(xiàn)重載 賦值運(yùn)算templateArray1D& Array1D:operator=(const Array1D& v) /

13、Overload assignment operator. if (this != &v) / not self-assignment size = v.size; delete element; / free old space element = new Tsize; / get right amount for (int i = 0; i size; i+) / copy elements elementi = v.elementi; / if return *this;Sahniarray1d.h155.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D Array1D: oper

14、ator+(const Array1D& v) const/ Return w = (*this) + v. if (size != v.size) throw SizeMismatch(); / create result array w Array1D w(size); for (int i = 0; i size; i+) w.elementi = elementi + v.elementi; return w;Sahniarray1d.h165.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D Array1D: operator-(const Array1D& v) const/

15、 Return w = (*this) - v. if (size != v.size) throw SizeMismatch(); / create result array w Array1D w(size); for (int i = 0; i size; i+) w.elementi = elementi - v.elementi; return w;Sahniarray1d.h175.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D Array1D:operator-() const/ Return w = -(*this). / create result array w A

16、rray1D w(size); for (int i = 0; i size; i+) w.elementi = -elementi; return w;Sahniarray1d.h185.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D Array1D:operator*(const Array1D& v) const/ Return w = (*this) * v. Pairwise multiply. if (size != v.size) throw SizeMismatch(); / create result array w Array1D w(size); for (int

17、 i = 0; i size; i+) w.elementi = elementi * v.elementi; return w;Sahniarray1d.h195.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D& Array1D:operator+=(const T& x) / Add x to each element of (*this). for (int i = 0; i size; i+) elementi += x; return *this; Sahniarray1d.h205.2 數(shù)組的順序表示和實(shí)現(xiàn)templateostream& operator(ostream&

18、 out, const Array1D& x)/ Put the elements of x into the stream out. for (int i = 0; i x.size; i+) out x.elementi ; return out;Sahniarray1d.h215.2 數(shù)組的順序表示和實(shí)現(xiàn)templateArray1D& Array1D:ReSize(int sz)/ Change the size to sz. / Do not copy array elements to new space. if (sz 0) throw BadInitializers(); de

19、lete element; size = sz; element = new T size; return *this;Sahniarray1d.h225.2 數(shù)組的順序表示和實(shí)現(xiàn)#include #include array1d.hvoid main(void) try Array1D X(10), Y, Z; for (int i=0; i 10; i+) Xi = i; cout X3 = X3 endl; cout X is X endl; Y = X; cout Y is Y endl; X += 2; cout X incremented by 2 is X endl; Z = (

20、Y + X) * Y; cout (Y + X) * Y is Z endl; cout -(Y + X) * Y is -Z endl; catch (.) cerr An exception has occurred endl;Sahniarray1d.cpp235.2 數(shù)組的順序表示和實(shí)現(xiàn)Sahni書(shū)一維數(shù)組實(shí)現(xiàn)的代碼：code增加了C+一般數(shù)組中缺乏的數(shù)組下標(biāo)檢驗(yàn)，數(shù)組整體的輸出，賦值，算術(shù)運(yùn)算等功能。復(fù)雜性：構(gòu)造和析構(gòu) (1)，如果T是C+內(nèi)部數(shù)據(jù)類型 (size)，如果T是用戶定義的類下標(biāo) ， (1)其它，O( size)Sahni245.2 數(shù)組的順序表示和實(shí)現(xiàn)類似地，可以定義二

21、維數(shù)組。Sahni255.2 數(shù)組的順序表示和實(shí)現(xiàn)教材上有任意維數(shù)組實(shí)現(xiàn)的例子數(shù)組：A維數(shù)：dim各維長(zhǎng)度（界）：bounds則Ai0,i1,idim-1的地址為：A首地址 + idim-1+idim-2*boundsdim-1+i1*boundsdim-1*bounds2+i0*boundsdim-1*bounds2*bounds1265.2 數(shù)組的順序表示和實(shí)現(xiàn)一般性的問(wèn)題：二維數(shù)組A，每個(gè)元素占字節(jié)數(shù)b，元素Ai1j1 地址為a1， Ai2j2地址為a2，則Ai3j3的地址是？行優(yōu)先/列優(yōu)先？275.2 數(shù)組的順序表示和實(shí)現(xiàn)用vector表示矩陣vector vector matrix;

22、template class matrixpublic:matrix(int numRows = 1, int numCols = 1, const T& initVal = T();vector& operator (int i);const vector& operator(int i) const;int rows() const;int cols() const;void resize(int numRows, int numCols);private: int nRows, nCols;vectorvector mat;285.2 數(shù)組的順序表示和實(shí)現(xiàn)template matrix:

23、matrix(int numRows, int numCols, const T& initVal): nRows(numRows), nCols(numCols), mat(numRows, vector(numCols,initVal)295.2 數(shù)組的順序表示和實(shí)現(xiàn)template vector& matrix:operator (int i) if (i = nRows) throw indexRangeError( matrix: invalid row index, i, nRows); return mati;template const vector& matrix:opera

24、tor (int i) const if (i = nRows) throw indexRangeError(matrix: invalid row index, i, nRows); return mati;305.2 數(shù)組的順序表示和實(shí)現(xiàn)template int matrix:rows() const return nRows;template int matrix:cols() const return nCols;315.2 數(shù)組的順序表示和實(shí)現(xiàn)template void matrix:resize(int numRows, int numCols) int i; / handle c

25、ase of no size change with a return if (numRows = nRows & numCols = nCols) return; / assign the new matrix size nRows = numRows; nCols = numCols; / resize to nRows rows mat.resize(nRows); / resize each row to have nCols columns for (i=0; i nRows; i+) mati.resize(nCols);325.3 矩陣的壓縮存儲(chǔ)5.3.1 特殊矩陣的壓縮存儲(chǔ)方法

26、5.3.2 稀疏矩陣的壓縮存儲(chǔ)方法335.3.1 特殊矩陣的壓縮存儲(chǔ)方法1. 對(duì)稱矩陣ai,j = aj,i 1=i,j=jk =i(i-1)/2+j-1ijk = j(j-1)/2+i-1345.3.1 特殊矩陣的壓縮存儲(chǔ)方法2. 三角矩陣上三角矩陣中aij和sak之間的對(duì)應(yīng)關(guān)系K = ?355.3.1 特殊矩陣的壓縮存儲(chǔ)方法3. 對(duì)角矩陣:若n階方陣中的非零值元都集中在以主對(duì)角線為中心的(由k條對(duì)角線組成的)帶狀區(qū)域中，則稱為k對(duì)角矩陣。K = f(i,j), f=?365.3.1 特殊矩陣的壓縮存儲(chǔ)方法由于特殊矩陣中的非零值元素在矩陣中的分布有著一定的規(guī)律，則可將這些非零值元連續(xù)存儲(chǔ)在一

27、個(gè)一維數(shù)組中。即矩陣中的任何一個(gè)元和它們?cè)谝痪S數(shù)組中的位置之間存在著某種轉(zhuǎn)換關(guān)系，并且這種轉(zhuǎn)換關(guān)系可以用數(shù)學(xué)公式表示之。 375.3.2 稀疏矩陣的壓縮存儲(chǔ)方法如果矩陣中只有少量的非零值元，并且這些非零值元在矩陣中的分布沒(méi)有一定規(guī)律，則稱為隨機(jī)稀疏矩陣，簡(jiǎn)稱為稀疏矩陣(Sparse matrix)。至于矩陣中究竟含多少個(gè)零值元才被稱為是稀疏矩陣，一般沒(méi)有一個(gè)確切的定義。假設(shè)在 m*n 的矩陣中有 t 個(gè)非零值元，稱=t/(m*n)為矩陣的稀疏因子，通常認(rèn)定0.05的矩陣為稀疏矩陣。385.3.2 稀疏矩陣的壓縮存儲(chǔ)方法一、三元組順序表const MAXTERMS=12500; / 假設(shè)非零元個(gè)

28、數(shù)的最大值為12500typedef struct int i, j; / 該非零元的行號(hào)和列號(hào)ElemType e; / 該非零元的值 Triple; / 三元組typedef struct Triple dataMAXTERMS + 1; / 非零元三元組表，data0 未用int rows, cols, terms;/ 矩陣的行數(shù)、列數(shù)和非零元的個(gè)數(shù) TSMatrix;/ 三元組順序表在data域中表示非零元的三元組是以行序?yàn)橹餍蝽樞蚺帕械?，這將有利于進(jìn)行某些矩陣運(yùn)算。395.3.2 稀疏矩陣的壓縮存儲(chǔ)方法三元組順序表示例：轉(zhuǎn)置運(yùn)算b.dataije13-3161521122518319

29、342446-76314a.dataije121213931-3361443245218611564-7？405.3.2 稀疏矩陣的壓縮存儲(chǔ)方法Status TransposeSMatrix( const TSMatrix &M, TSMatrix &T) / 采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 T.terms) q = 1; for( col = 1; col = M.cols; col+) for( p=1; p=M.terms; p+) if(M.datap.

30、j = col) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; q+; return OK;/ TransposeSMtrix后面有大字版本415.3.2 稀疏矩陣的壓縮存儲(chǔ)方法Status TransposeSMatrix( TSMatrix M, TSMatrix &T) / 采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 T.terms) q = 1; for( col = 1;

31、col = M.cols; col+)/ code in next page return OK;/ TransposeSMtrix425.3.2 稀疏矩陣的壓縮存儲(chǔ)方法Status TransposeSMatrix( TSMatrix M, TSMatrix &T) / 采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T for( col = 1; col = M.cols; col+) for( p=1; p=M.terms; p+) if(M.datap.j = col) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.

32、datap.e; q+; / TransposeSMtrix其時(shí)間復(fù)雜度為O(cols * terms)當(dāng)稀疏因子接近1時(shí)，為O( rows * cols2)如何修改使其時(shí)間復(fù)雜度為O( rows * cols)教材P100，算法5.2435.3.2 稀疏矩陣的壓縮存儲(chǔ)方法快速轉(zhuǎn)置Status FastTransposeSMatrix(const TSMatrix &M, TSMatrix &T) T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 T.terms)for(col=1;col=M.cols;col+) numco

33、l=0;for(t=1;t=M.terms;t+) numM.datat.j+;cpot1=1;for(col=2;col=Mu.col;col+) cpotcol=cpotcol-1+numcol-1;/ q = 1;/ for( col = 1; col = M.cols; col+) for( p=1; p=M.terms; p+) col = M.datap.j; q=cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; cpotcol+; / for / if return OK;/

34、 TransposeSMtrix后面有大字版本445.3.2 稀疏矩陣的壓縮存儲(chǔ)方法快速轉(zhuǎn)置Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T) T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 T.terms)for(col=1;col=M.cols;col+) numcol=0;for(t=1;t=M.terms;t+) numM.datat.j+;cpot1=1;for(col=2;col=Mu.col;col+) cpotcol=cpotcol-1+numcol-1

35、;/ . See next page return OK;/ TransposeSMtrix455.3.2 稀疏矩陣的壓縮存儲(chǔ)方法快速轉(zhuǎn)置Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T)./ q = 1;/ for( col = 1; col = M.cols; col+) for( p=1; pi=i; p-j=j; p-e=e;if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;else for(q=M.rheadi;(q-right)&q-right-jright);p-right=q-right;q-right=p;51三、十字鏈表if(M.cheadj=NULL|M.c