三元组顺序表矩阵表示

1、数据结构第5章 数组与广义表1第5章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示 5.7 广义表的递归算法25.1 数组的定义ADT Array 数据对象：Daj1,j2,.,ji ,.jn |ji =0,.,bi-1, i=1,2,.,n, 称 n(0) 为数组的维数， bi为数组第 i 维的长度，ji为数组元素的第i维下标，aj1,.,jn ElemSet 数据关系：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 数组的定义基本操作：InitArray(&A, n, bound1, ., boundn)操作结果：若维数 n 和各维长度合法，则构造相应的数组 A。DestroyArray(&A)初始条件：数组 A 已经存在。操作结果：销毁数组 A。Value(A, &e, index1, ., indexn)初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。操作结果：若各下标不超界,则e赋值为所指定的A的元素值,并返回OK。Assign(&A, e, index1, ., indexn)初始条件：A

3、是 n 维数组，e 为元素变量，随后是 n 个下标值。操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。 ADT Array45.2 数组的顺序表示和实现由于数组类型不作插入和删除的操作，因此只需要通过顺序映象得到它的存储结构，即借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。通常有两种映象方法：即“以行(序)为主(序)“row-major的映象方法和”以列(序)为主(序)“ column-major 的映象方法。将多维数组映射到一维数组的方法 representations of a multidimensional array55.2 数组的顺序表示和实现以二维数

4、组 a m, n为例，其在内存中的映像既可以如下排列（行优先）：a00, a01, , a0,n-1,a10,a11,a1,n-1,am-1,0,am-1,n-1也可以如下排列（列优先）：a00, a10, , am-1,0,a01,a11,am-1,1,a0,n-1,am-1,n-111121314151621222324252631323334353641424344454611121314151621222324252631323334353641424344454611213141122232421323334314243444152535451626364665.2 数组的顺序表示和

5、实现假设二维数组 Rmn 中每个数据元素占L个存储地址，并以 LOC(i,j) 表示下标为 (i,j) 的数据元素的存储地址，则该数组中任何一对下标 (i,j) 对应的数据元素在以行为主的顺序映象中的存储地址为：LOC(i,j) = LOC(0,0) + (i*n+j)*L在以列为主的顺序映象中的存储地址为：LOC(i,j) = LOC(0,0) + (j*m+i)*L其中 LOC(0,0) 是二维数组中第一个数据元素（下标为(0,0)）的存储地址，称为数组的 基地址 或基址。75.2 数组的顺序表示和实现类似地，假设三维数组 Rpmn 中每个数据元素占 L 个存储地址，并以 LOC(i,j,

6、k) 表示下标为(i,j,k) 的数据元素的存储地址，则该数组中任何一对下标(i,j,k) 对应的数据元素在以行为主的顺序映象中的存储地址为：LOC(i,j,k) = LOC(0,0,0) + (imn + jn+k)L85.2 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现templateArray1D:Array1D(in

11、t sz)/ Constructor for one-dimensional arrays. if (sz 0) throw BadInitializers(); size = sz; element = new Tsz;Sahniarray1d.h构造函数125.2 数组的顺序表示和实现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构造函数135.2 数组的顺序表示和实现重载 templateT& Array1D:operator(int i) const/ Return reference to element i. if (i = size) throw OutOfBounds(); return elementi;Sahniarray1d.h145.2 数组的顺序表示和实现重载 赋值运算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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现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 数组的顺序表示和实现#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 数组的顺序表示和实现Sahni书一维数组实现的代码：code增加了C+一般数组中缺乏的数组下标检验，数组整体的输出，赋值，算术运算等功能。复杂性：构造和析构 (1)，如果T是C+内部数据类型 (size)，如果T是用户定义的类下标 ， (1)其它，O( size)Sahni245.2 数组的顺序表示和实现类似地，可以定义二

21、维数组。Sahni255.2 数组的顺序表示和实现教材上有任意维数组实现的例子数组：A维数：dim各维长度（界）：bounds则Ai0,i1,idim-1的地址为：A首地址 + idim-1+idim-2*boundsdim-1+i1*boundsdim-1*bounds2+i0*boundsdim-1*bounds2*bounds1265.2 数组的顺序表示和实现一般性的问题：二维数组A，每个元素占字节数b，元素Ai1j1 地址为a1， Ai2j2地址为a2，则Ai3j3的地址是？行优先/列优先？275.2 数组的顺序表示和实现用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 数组的顺序表示和实现template matrix:

23、matrix(int numRows, int numCols, const T& initVal): nRows(numRows), nCols(numCols), mat(numRows, vector(numCols,initVal)295.2 数组的顺序表示和实现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 数组的顺序表示和实现template int matrix:rows() const return nRows;template int matrix:cols() const return nCols;315.2 数组的顺序表示和实现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 矩阵的压缩存储5.3.1 特殊矩阵的压缩存储方法

26、5.3.2 稀疏矩阵的压缩存储方法335.3.1 特殊矩阵的压缩存储方法1. 对称矩阵ai,j = aj,i 1=i,j=jk =i(i-1)/2+j-1ijk = j(j-1)/2+i-1345.3.1 特殊矩阵的压缩存储方法2. 三角矩阵上三角矩阵中aij和sak之间的对应关系K = ?355.3.1 特殊矩阵的压缩存储方法3. 对角矩阵:若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵。K = f(i,j), f=?365.3.1 特殊矩阵的压缩存储方法由于特殊矩阵中的非零值元素在矩阵中的分布有着一定的规律，则可将这些非零值元连续存储在一

27、个一维数组中。即矩阵中的任何一个元和它们在一维数组中的位置之间存在着某种转换关系，并且这种转换关系可以用数学公式表示之。 375.3.2 稀疏矩阵的压缩存储方法如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵(Sparse matrix)。至于矩阵中究竟含多少个零值元才被称为是稀疏矩阵，一般没有一个确切的定义。假设在 m*n 的矩阵中有 t 个非零值元，称=t/(m*n)为矩阵的稀疏因子，通常认定0.05的矩阵为稀疏矩阵。385.3.2 稀疏矩阵的压缩存储方法一、三元组顺序表const MAXTERMS=12500; / 假设非零元个

28、数的最大值为12500typedef struct int i, j; / 该非零元的行号和列号ElemType e; / 该非零元的值 Triple; / 三元组typedef struct Triple dataMAXTERMS + 1; / 非零元三元组表，data0 未用int rows, cols, terms;/ 矩阵的行数、列数和非零元的个数 TSMatrix;/ 三元组顺序表在data域中表示非零元的三元组是以行序为主序顺序排列的，这将有利于进行某些矩阵运算。395.3.2 稀疏矩阵的压缩存储方法三元组顺序表示例：转置运算b.dataije13-3161521122518319

29、342446-76314a.dataije121213931-3361443245218611564-7？405.3.2 稀疏矩阵的压缩存储方法Status TransposeSMatrix( const TSMatrix &M, TSMatrix &T) / 采用三元组表存储表示，求稀疏矩阵M的转置矩阵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 稀疏矩阵的压缩存储方法Status TransposeSMatrix( TSMatrix M, TSMatrix &T) / 采用三元组表存储表示，求稀疏矩阵M的转置矩阵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 稀疏矩阵的压缩存储方法Status TransposeSMatrix( TSMatrix M, TSMatrix &T) / 采用三元组表存储表示，求稀疏矩阵M的转置矩阵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其时间复杂度为O(cols * terms)当稀疏因子接近1时，为O( rows * cols2)如何修改使其时间复杂度为O( rows * cols)教材P100，算法5.2435.3.2 稀疏矩阵的压缩存储方法快速转置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 稀疏矩阵的压缩存储方法快速转置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 稀疏矩阵的压缩存储方法快速转置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