6二维数组(精品).ppt

《6二维数组(精品).ppt》由会员分享，可在线阅读，更多相关《6二维数组(精品).ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、版权所有,1997(c)Dale Carnegie&Associates,Inc.数组、矩阵与集合朱振元1数组的相关概念数组的相关概念数数组组是是n(n1)n(n1)个个具具有有相相同同数数据据类类型型的的数数据据元元素素a a0 0,a a1 1,a a2 2,a an-n-1 1构成的占用构成的占用连续连续存存储单储单元的有限序列。元的有限序列。操作操作:主要是存取数据元素。主要是存取数据元素。特点：采用特点：采用顺顺序的存序的存储结储结构，且不构，且不进进行插入、行插入、删删除等操作。除等操作。地址地址计计算：算：假假设设数数组组A A的的首首地地址址为为l l0 0 ，每每个个元元素素

2、占占k k个个存存储储单单元元，则则数数组组第第i i个元素的存个元素的存储储位置位置pos(Ai)pos(Ai)可由下式确定：可由下式确定：pos(Ai)pos(Ai)pos(A0)pos(A0)i i k kl l0 0i i k k(0=in)(0=in)特特别别地，当地，当k=1k=1时时，有：，有：pos(Ai)pos(Ai)l l0 0i;i;2数组抽象数据类型数组抽象数据类型 数数据据元元素素：数数组组的的数数据据元元素素集集合合可可表表示示为为a a0 0,a a1 1,a a2 2,a an-1n-1，其其中中每每个个数数据元素具有相同数据据元素具有相同数据类类型。型。结结构

3、构关关系系：数数组组元元素素呈呈线线性性结结构构，且且限限定定数数组组元元素素必必须须存存储储在在地地址址连连续续的内存的内存单单元中。元中。基本操作：基本操作：对对数数组组可可执执行以下的基本操作。行以下的基本操作。Initiate(A)Initiate(A)构造数构造数组组A A。Size(A)Size(A)求求长长度。函数度。函数值为给值为给定数定数组组A A中数据元素的个数。中数据元素的个数。Set(A,i,x)Set(A,i,x)存存数数组组元元素素。把把数数据据x x存存入入数数组组A A的的下下标标为为i i的的数数组组元元素素中中，其其约约束条件束条件为为0=0=i=lengt

4、h(A)-1i=length(A)-1。Get(A,i Get(A,i)取取数数组组元元素素。取取出出数数组组A A中中下下标标为为i i的的数数组组元元素素，其其约约束束条条件件为为0=0=i=length(A)-1i=length(A)-1。3数组类定义及实现数组类定义及实现 template template class Arrayclass Array private:private:T *a;T *a;intint size;size;public:public:Array(Array(int szint sz=100);=100);Array(const Array&Array(c

5、onst Array&arrarr););Array()delete a;Array()delete a;int getsizeint getsize()return size;()return size;T&operator(T&operator(intint i);i);Array&operator=(const Array&Array&operator=(const Array&arrarr););void resize(void resize(int szint sz=100);=100);void void prntprnt()()for(for(intint i=0;isize;i

6、+)i=0;isize;i+)coutcout ai;ai;coutcoutendlendl;4数组类构造函数与赋值函数数组类构造函数与赋值函数 Array(Array(int szint sz=100)=100)if(if(szsz=0)=0)coutcout数组长度无效数组长度无效endlendl;exit(0);exit(0);size=size=szsz;a=new Tsize;a=new Tsize;Array(const Array&Array(const Array&arrarr)size=arr.size;size=arr.size;a=new Tsize;a=new Tsiz

7、e;for(for(intint i=0;isize;i+)ai=arr.ai;i=0;isize;i+)ai=arr.ai;Array&operator=(const Array&Array&operator=(const Array&arrarr)delete a;delete a;size=arr.size;size=arr.size;a=new Tsize;a=new Tsize;for(for(intint i=0;isize;i+)ai=arr.ai;i=0;isize;i+)ai=arr.ai;return*this;return*this;5数组类重置函数数组类重置函数 /重新

8、分配空间重新分配空间void resize(void resize(int szint sz=100)=100)if(if(szsz=0)=0)coutcout数组长度无效数组长度无效endlendl;exit(0);exit(0);if(if(szsz=size)return;=size)return;T*T*newanewa=new T=new Tszsz;intint n=(n=(szsz=size)?=size)?szsz:size;:size;for(for(intint i=0;in;i+)i=0;in;i+)newanewai=ai;i=ai;delete a;delete a;

9、a=a=newanewa;size=size=szsz;6二维数组的初步认识二维数组的初步认识二二维维数数组组可可看看作作线线性性表表的的一一种种扩扩展展,在在逻逻辑辑上上可可看看成成由由若若干干行行、列列组组成成的的表表格格或或矩矩阵阵，例例如如以以下下的的m m行行n n列的矩阵列的矩阵:a a11 11 a a12 12 a a13 13 a a1n1n a a21 21 a a22 22 a a23 23 a a2n2n a am1 m1 a am2 m2 a am3 m3 a amnmn可表示成二维数组可表示成二维数组 intint Amn;Amn;7二维数组的初步认识二维数组的初步

10、认识将将二二维维数数组组看看作作是是线线性性表表的的扩扩展展,例例如如，如如果果将将每每一一列列看看作作为为一一个个元元素素，则则以以上上m m行行n n列列矩矩阵阵所所对对应应的的二二维维数数组组a a可看成如下线性表：可看成如下线性表：a a(1 1,2 2,n n)其中每一个数据元素其中每一个数据元素j j是一个列向量是一个列向量j j(a a1j,1j,a a2j,2j,a a3j,3j,a amjmj)类类似似地地，如如果果将将每每一一行行看看作作为为一一个个元元素素，则则a a可可看看成成如如下下线性表：线性表：a a(1 1,2 2,m m)其中每一个数据元素其中每一个数据元素i

11、 i是一个行向量是一个行向量i i(a ai1,i1,a ai2,i2,a ai3,i3,a ainin,)8二维数组的初步认识二维数组的初步认识一般地，二维数组的逻辑结构可表示为：一般地，二维数组的逻辑结构可表示为：Array_2=(D,R)Array_2=(D,R)其中，其中，D=D=a aij ij|i=c|i=c1 1,c,c1 1+1,+1,d,d1 1;j=c;j=c2 2,c,c2 2+1,+1,d,d2 2；a aijijData ObjectData ObjectR=ROW,COLR=ROW,COLROW=ROW=|c|c1 1i idd1 1;c;c2 2jdjd2 2-1

12、-1 ;a aijij,a ai i,j+1,j+1DDCOL=COL=|c|c1 1i idd1 1-1;c-1;c2 2jdjd2 2;a ai i+1,j+1,j,a aijijDD其其中中：(c c1 1,d d1 1)和和(c c2 2,d d2 2)分分别别为为数数组组下下标标i,i,j j的的一一对对界界界界偶偶偶偶（即即满足条件满足条件c c1 1i idd1 1，c c2 2jdjd2 2）。）。称称C C1 1,c,c2 2为下界为下界,通常取通常取c1=c2=1;c1=c2=1;称称d1,d2d1,d2为上界为上界,通常取通常取d1=md1=m，d2=nd2=n 9二维数

13、组的存储结构二维数组的存储结构按行排列按行排列排列方式排列方式a a11 11 a a12 12 a a1n1n a a21 21 a a22 22 a a2n2n a am1 m1 a am2 m2 a am3 m3 a amnmn地址计算地址计算pos(Ai,j)pos(Ai,j)l l0 0i i n n k kj j k k l l0 0 (i(i n nj j)k (0=in,0=jm)k (0=in,0=jm)特特别别地，地，当当k=1k=1时时，有：，有：pos(Ai,j)pos(Ai,j)l l0 0 i i n nj j10二维数组的存储结构二维数组的存储结构按列排列按列排列

14、排列方式排列方式a a1111 a a2121 a am1m1 a a1212 a a2222 a am2m2 a a1n1n a a2n2n a a3n3n a amnmn地址计算地址计算pos(Ai,j)pos(Ai,j)l l0 0j j m m k ki i k k l l0 0(j(j m mi i)k (0=in,0=jm)k (0=in,0=jm)特特别别地，地，当当k=1k=1时时，有：，有：pos(Ai,j)pos(Ai,j)l l0 0 j j m mi i 11矩阵的类定义矩阵的类定义class Matrixclass Matrix private:private:flo

15、at *item;float *item;intint m,n;m,n;public:public:Matrix()item=NULL;m=0;n=0;Matrix()item=NULL;m=0;n=0;Matrix(float a,Matrix(float a,intint row,row,int colint col););Matrix(Matrix&b);Matrix(Matrix&b);Matrix&operator=(Matrix&b);Matrix&operator=(Matrix&b);Matrix&Matrix&trantran();();Matrix&plus(Matrix&

16、b);Matrix&plus(Matrix&b);Matrix&Matrix&multmult(Matrix&b);(Matrix&b);void void prntprnt();();将将itemitem设设计计成成一一维维排排列列是是为为了了使使矩矩阵阵中中的的行行数数和和列列数数在在存存储储量量容许的情形下可以进行变化；容许的情形下可以进行变化；定定义义成成指指针针类类型型以以便便在在实实例例生生成成时按指定的长度动态分配存储时按指定的长度动态分配存储 12矩阵类的构造函数矩阵类的构造函数Matrix:Matrix(float a,Matrix:Matrix(float a,intint

17、 row,row,int colint col)intint j;j;m=row;n=m=row;n=colcol;item=new float m*n;item=new float m*n;for(j=0;jm*n;j+)itemj=aj;for(j=0;jm*n;j+)itemj=aj;Matrix:Matrix(Matrix&b)Matrix:Matrix(Matrix&b)intint j;j;m=b.m;n=b.n;m=b.m;n=b.n;item=new float m*n;item=new float m*n;for(j=0;jm*n;j+)itemj=b.itemj;for(j

18、=0;jm*n;j+)itemj=b.itemj;13矩阵转置矩阵转置Matrix&Matrix&trantran()()功能功能:返回当前矩返回当前矩阵阵的的转转置矩置矩阵阵但当前矩但当前矩阵阵没有改没有改变变。其。其处处理理过过程程为为：(1)(1)创创建建一一个个矩矩阵阵类类对对象象x x并并按按当当前前矩矩阵阵的的转转置置设设置置其其行行数数与与列列数数并并分分配配存存储储空空间间。(2)(2)将当前矩将当前矩阵阵中的元素中的元素转转置存放到矩置存放到矩阵阵x x中并返回中并返回x x。Matrix&Matrix:Matrix&Matrix:trantran()()Matrix&x=*

19、new Matrix;Matrix&x=*new Matrix;intint i,j;i,j;x.m=n;x.n=m;x.m=n;x.n=m;x.item=new float m*n;x.item=new float m*n;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)x.itemj*m+i=itemi*n+j;for(j=0;jn;j+)x.itemj*m+i=itemi*n+j;return x;return x;要要注注意意的的是是由由于于函函数数的的返返回回类类型型是是对对象象的的引引用用，所所以以不不能能返返回回局局部部对对象象或或无名无名对对

20、象，而只能是当前象，而只能是当前对对象或象或newnew创创建的建的对对象。象。14矩阵相加矩阵相加Matrix&plus(Matrix&b)Matrix&plus(Matrix&b)其功能其功能为为返回当前矩返回当前矩阵阵与与b b相加后的矩相加后的矩阵阵，其，其处处理理过过程程为为：(1)(1)若二矩若二矩阵阵的行、列数不等，的行、列数不等，则显则显示出示出错错信息；否信息；否则则(2)(2)创创建建一一个个矩矩阵阵类类的的对对象象x x并并按按当当前前矩矩阵阵设设置置其其行行数数与与列列数数；将将二二矩矩阵阵对对应应的元素相加后存入的元素相加后存入x x并返回并返回x x。Matrix&

21、Matrix:plus(Matrix&b)Matrix&Matrix:plus(Matrix&b)Matrix&x=*new Matrix;Matrix&x=*new Matrix;intint i,j;i,j;if(b.m!=m)|(b.n!=n)if(b.m!=m)|(b.n!=n)coutcout参数错参数错;exit(0);exit(0);else x.m=m;x.n=n;else x.m=m;x.n=n;x.item=new float m*n;x.item=new float m*n;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)for(j=0

22、;jn;j+)x.itemi*n+j=b.itemi*n+j+itemi*n+j;x.itemi*n+j=b.itemi*n+j+itemi*n+j;return x;return x;15矩阵相乘矩阵相乘设设两两个个行行列列数数分分别别为为m m l l和和l l n n的的矩矩阵阵A A、B B，则则乘积矩阵乘积矩阵C C中的元素中的元素CCi i,j j 满足以下等式：满足以下等式：例如：例如：16矩阵相乘矩阵相乘Matrix&mult(Matrix&b)其功能为返回当前矩阵与b相乘后的矩阵。处理过程为：(1)若当前矩阵的列数不等于矩阵b的行数，则显示出错信息，否则：(2)创建一个矩阵对

23、象x并按结果矩阵设置行数与列数，按公式求出其中的每一个元素并返回该矩阵。17矩阵相乘矩阵相乘Matrix&Matrix:Matrix&Matrix:multmult(Matrix&b)(Matrix&b)Matrix&x=*new Matrix;Matrix&x=*new Matrix;intint i,j,k;i,j,k;if(b.m!=n)if(b.m!=n)coutcout参数错参数错;exit(0);exit(0);else x.m=m;x.n=b.n;else x.m=m;x.n=b.n;x.item=new float x.m*x.n;x.item=new float x.m*x.

24、n;for(i=0;ix.m;i+)for(i=0;ix.m;i+)for(j=0;jx.n;j+)for(j=0;jx.n;j+)x.itemi*x.n+j=0;x.itemi*x.n+j=0;for(k=0;kn;k+)for(k=0;kn;k+)x.itemi*x.n+j=x.itemi*x.n+j=x.itemi*x.n+j+itemi*n+k*b.itemk*b.n+j;x.itemi*x.n+j+itemi*n+k*b.itemk*b.n+j;return x;return x;18互动环节：互动环节：MatrixMatrix类赋值操作的实现类赋值操作的实现 问题说问题说明：要明：

25、要实现实现MatrixMatrix类对类对象的象的赋值赋值操作。操作。float a=5,7,3,9,0,4,2,8,1,0,4,3;float a=5,7,3,9,0,4,2,8,1,0,4,3;Matrix jz1(a,4,3),jz2;Matrix jz1(a,4,3),jz2;可可设设置以下的代置以下的代码对码对其其进进行行赋值赋值的操作：的操作：jz2=jz1;jz2=jz1;赋赋值值函函数数Matrix&Matrix&operator=(operator=(Matrix&Matrix&b)b)的的功功能能是是将将矩矩阵阵对对象象b b的信息的信息设设置到当前置到当前对对象中去，并返

26、回当前象中去，并返回当前对对象。象。为为了了调调试试程程序序的的方方便便，再再增增设设一一个个成成员员函函数数prntprnt()()用用于于显显示示对对象中的矩象中的矩阵阵元素。元素。19互动环节：互动环节：MatrixMatrix类赋值操作的实现类赋值操作的实现 void Matrix:void Matrix:prntprnt()()intint i,j;i,j;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)for(j=0;jn;j+)coutcoutsetwsetw(5)itemi*n+j;(5)itemi*n+j;coutcoutendlendl;

27、coutcout-endlendl;Matrix&Matrix:operator=(Matrix&b)Matrix&Matrix:operator=(Matrix&b)intint j;j;m=b.m;n=b.n;m=b.m;n=b.n;if(item!=NULL)delete item;if(item!=NULL)delete item;item=new float m*n;item=new float m*n;for(j=0;jm*n;j+)itemj=b.itemj;for(j=0;jm*n;j+)itemj=b.itemj;return*this;return*this;20互动环节：

28、互动环节：MatrixMatrix类赋值操作测试程序类赋值操作测试程序 void main()void main()float a=5,7,3,9,0,4,2,8,1,0,4,3;float a=5,7,3,9,0,4,2,8,1,0,4,3;Matrix jz1(a,4,3),jz2(jz1),jz3,jz4,jz5;Matrix jz1(a,4,3),jz2(jz1),jz3,jz4,jz5;jz3=jz1.jz3=jz1.trantran();jz3.();jz3.prntprnt();();jz4=jz1.plus(jz2);jz4.jz4=jz1.plus(jz2);jz4.prnt

29、prnt();();jz5=jz1.jz5=jz1.multmult(jz3);jz5.(jz3);jz5.prntprnt();();程序的运行程序的运行结结果如下：果如下：5 9 2 05 9 2 07 0 8 47 0 8 43 4 1 33 4 1 3-10 14 6 10 14 6 18 0 8 18 0 8 4 16 2 4 16 2 0 8 6 0 8 6 -83 57 69 3783 57 69 3757 97 22 1257 97 22 1269 22 69 3569 22 69 3537 12 35 2537 12 35 25-21矩阵的压缩存储矩阵的压缩存储对称矩阵对称矩

30、阵 若若一一个个n n阶阶方方阵阵A A的的元元素素满满足足性性质质AAi i,j j=A=Aj j,i i，则则称称该该矩矩阵为阵为n n阶对称矩阵。阶对称矩阵。对角矩阵对角矩阵 所谓对角矩阵是指矩阵的所有非零元素都集中在以主对角所谓对角矩阵是指矩阵的所有非零元素都集中在以主对角线为中心的带状区域中。线为中心的带状区域中。稀疏矩阵稀疏矩阵 若在一个矩阵中，零元素的个数相对于整个矩阵元素总个若在一个矩阵中，零元素的个数相对于整个矩阵元素总个数所占比例较大，则可认为该矩阵是稀疏矩阵。数所占比例较大，则可认为该矩阵是稀疏矩阵。22对称矩阵的压缩存储对称矩阵的压缩存储仅存放对称矩阵的下三角元素仅存放

31、对称矩阵的下三角元素 A00A00A10 A11A10 A11An-10 An-11An-10 An-11 An-1n-1 An-1n-1由由于于下下标标序序号号从从0 0开开始始，AAi ij j 处处于于第第i+1i+1行行，其其前前i i行行元元素素的的个个数数为为i*(i+1)/2i*(i+1)/2，所所以以AAi ij j 在在一一维维数数组组排排列列中中的的序序号号为为i*(i+1)/2 i*(i+1)/2+j j。A A的任意一个元素的任意一个元素aai i,j j 在一维数组中的序号为在一维数组中的序号为k k，其中其中 23对角矩阵的压缩存储对角矩阵的压缩存储在在三三对对角角

32、矩矩阵阵B B中中，除除第第一一行行和和最最后后一一行行只只有有两两个个非非零零元元素素外外，其其它它每每行行中中各各有有三三个个非非零零元元素素；而而且且第第i i行行(0(0 i in)n)的的前前i i1 1个个元元素素为为零零。由由于于第第0 0行行有有2 2个个元元素素，第第1 1行行到到第第i-1i-1行行的的元元素素个个数数为为(i i1)1)3 3，而而BBi ij j 在在第第i i行行中中的的序序号号为为j j(i(i1)1)，因因此此，B B中中非非零零元元素素BBi ij j 在在该该一一维维数数组组中中的的位位置置k k可可计计算如下算如下(1(1i in)n)：k

33、k2 2(i(i1)1)3 3j j(i(i1)1)2 2 i ij j24稀疏矩阵的压缩存稀疏矩阵的压缩存储储只存储非零元素只存储非零元素三元组三元组(rowrow，colcol，value)value)例如对于非零元素例如对于非零元素2 2，其三元组表示为（，其三元组表示为（0 0，0 0，2 2）25稀疏矩阵的压缩存储如果以顺序存储结构来表示三元组线性表，如果以顺序存储结构来表示三元组线性表，则可得到稀疏矩阵的三元组表压缩存储方则可得到稀疏矩阵的三元组表压缩存储方式。式。例如，三元组表例如，三元组表 rowrowcolcolvaluevalue0 00 02 20 06 66 61 13

34、 34 42 22 27 74 40 012124 44 49 95 57 75 526const const maxlenmaxlen=三元组表允许的最大长度；三元组表允许的最大长度；typedef structtypedef struct intint row,row,colcol;float value;float value;RCV;RCV;typedef structtypedef struct intint r,c,num;r,c,num;RCV item RCV itemmaxlenmaxlen;SMatrixSMatrix;其其中中r,r,c,c,numnum分分别别表表示示稀

35、稀疏疏矩矩阵阵的的行行数数、列列数数和和非非零零元元个数个数itemitem域中表示的非零元的三元组是以行序为主序排列的。域中表示的非零元的三元组是以行序为主序排列的。三三元元组组表表数数据据类类型型定定义义27struct struct RCV RCV intint row,row,colcol;float value;float value;class class SMatrixSMatrix RCV *item;RCV *item;intint r,c,num;r,c,num;public:public:SMatrixSMatrix()item=NULL;r=0;c=0;num=0;()

36、item=NULL;r=0;c=0;num=0;SMatrixSMatrix(RCV a,(RCV a,intint n,n,intint row,row,int colint col););SMatrixSMatrix&trantran();();SMatrixSMatrix&tran1();&tran1();SMatrixSMatrix&plus(&plus(SMatrixSMatrix&b);&b);SMatrixSMatrix&multmult(SMatrixSMatrix&b);&b);void void prntprnt();();稀稀疏疏矩矩阵阵类类定定义义 28第一种形第一种形

37、态态无参数，无参数，仅创仅创建一个空的三元建一个空的三元组组表。表。第第二二种种形形态态设设置置三三元元组组表表a a，长长度度n n及及行行数数rowrow、列列数数colcol四四个个参参数数，创创建建的的三三元元组组表表由由参参数数a a、n n确确定定，而而行行数数、列列数数分分别别由由参参数数rowrow、colcol确定。确定。功能功能:按指定的参数分配存按指定的参数分配存储储空空间间并并设设置数据成置数据成员员的初的初值值。SMatrixSMatrix:SMatrixSMatrix(RCV a,(RCV a,intint n,n,intint row,row,int colint

38、 col)intint i;i;r=row;c=r=row;c=colcol;num=n;num=n;item=new RCV num;item=new RCV num;for(i=0;inum;i+)itemi=ai;for(i=0;i0)if(num0)k=0;k=0;for(i=0;ic;i+)for(i=0;ic;i+)for(j=0;jnum;j+)for(j=0;jnum;j+)if(itemj.if(itemj.colcol=i)=i)x.itemk.row=itemj.x.itemk.row=itemj.colcol;x.itemk.x.itemk.colcol=itemj.r

39、ow;=itemj.row;x.itemk.value=itemj.value;x.itemk.value=itemj.value;k+;k+;return(x);return(x);32稀疏矩阵快速转置稀疏矩阵快速转置在上述算法中要进行二重循环，算法的效率比较低，在上述算法中要进行二重循环，算法的效率比较低，如如果果能能确确定定所所求求转转置置矩矩阵阵B B中中每每一一行行的的第第一一个个非非零零元元素素在在对对应应的的三三元元组组表表中中的的位位置置 ，那那么么只只要要对对三三元元组组a a进进行行一一次次扫扫描描就就可可以以了了。为为此此，设设置置rnumrnum和和rstartrsta

40、rt两两个个数组。数组。rnumrnum k k 表示原矩阵表示原矩阵a a的第的第k k列中非零元的个数，列中非零元的个数，rstartrstart k k 则指示则指示a a中第中第k k列的第一个非零元在列的第一个非零元在B B的三元组表中的恰当位置。的三元组表中的恰当位置。不难看出，不难看出，rnumrnum和和rstartrstart间存在如下关系：间存在如下关系：rstartrstart k k r numr numk k-1-1rstartrstart k k-1-1 k k0 01 12 23 34 45 56 67 7rnumrnum k k 2 20 01 11 11 10

41、 01 11 1rstartrstart k k 0 02 22 23 34 45 55 56 633稀疏矩阵快速转置稀疏矩阵快速转置SMatrixSMatrix&tran1()&tran1()功能功能:使用快速使用快速转转置法置法计计算并返回当前矩算并返回当前矩阵阵的的转转置矩置矩阵阵，其，其处处理理过过程程为为：(1)(1)创创建一个稀疏矩建一个稀疏矩阵阵x x，形成形成x x的的r,c,numr,c,num，并按指定的并按指定的长长度分配存度分配存储储空空间间。(2)(2)求当前矩求当前矩阵阵中各列非零元的个数，将中各列非零元的个数，将结结果存入数果存入数组组rnumrnum。(3)(3

42、)求求结结果矩果矩阵阵中各行起始位置，将中各行起始位置，将结结果存入数果存入数组组rstartrstart。(4)(4)依依次次扫扫描描当当前前矩矩阵阵中中的的三三元元组组表表，对对每每一一个个三三元元组组行行列列置置换换后后按按原原列列号号colcol存入存入x x中由中由rstartrstart colcol 指示的位置，并使其位置加指示的位置，并使其位置加1 1。(5)(5)返回结果矩阵返回结果矩阵x x。34稀疏矩阵快速转置稀疏矩阵快速转置形成数组形成数组rnumrnum；for(i=0;ic;i+)for(i=0;ic;i+)rnumrnumi=0;i=0;for(i=0;inum;

43、i+)for(i=0;inum;i+)rnumrnumitemi.itemi.colcol+;+;形成数组形成数组rstartrstart；rstartrstart0=0;0=0;for(i=1;ic;i+)for(i=1;ic;i+)rstartrstarti=i=rnumrnumi-1+i-1+rstartrstarti-1;i-1;35稀疏矩阵快速转置稀疏矩阵快速转置SMatrixSMatrix&SMatrixSMatrix:tran1():tran1()SMatrixSMatrix&x=*new&x=*new SMatrixSMatrix;intint i,j;i,j;int rnum

44、int rnum100,100,rstartrstart100;100;x.r=c;x.c=r;x.num=num;x.r=c;x.c=r;x.num=num;x.item=new RCVnum;x.item=new RCVnum;for(i=0;ic;i+)for(i=0;ic;i+)rnumrnumi=0;i=0;for(i=0;inum;i+)for(i=0;inum;i+)rnumrnumitemi.itemi.colcol+;+;rstartrstart0=0;0=0;for(i=1;ic;i+)for(i=1;ic;i+)rstartrstarti=i=rnumrnumi-1+i-

45、1+rstartrstarti-1;i-1;for(i=0;inum;i+)for(i=0;i=0&x=0&xsize;void clear()for(void clear()for(intint i=0;isize;i+)seti=0;i=0;isize;i+)seti=0;public:public:TintsetTintset(intint s=100);s=100);TintsetTintset(const(const TintsetTintset&);&);void add(void add(intint););void remove(void remove(intint););bo

46、olbool contain(contain(intint););boolbool include(const include(const TintsetTintset&);&);boolbool equals(const equals(const TintsetTintset&);&);TintsetTintset&unionsetunionset(const(const TintsetTintset&);&);TintsetTintset&intersection(const&intersection(const TintsetTintset&);&);boolbool empty()em

47、pty()for(for(intint i=0;isize;i+)if(seti=1)return false;i=0;isize;i+)if(seti=1)return false;return true;return true;39整数集合类整数集合类 1 1 构造函数。按指定的构造函数。按指定的长长度构造一个度构造一个TintsetTintset类类的的对对象。象。TintsetTintset:TintsetTintset(intint s)s)size=s;size=s;set=new set=new intint size;clear();size;clear();2 2 拷拷贝贝构

48、造函数。按指定的构造函数。按指定的长长度度TintsetTintset类对类对象构造一个新的象构造一个新的对对象。象。TintsetTintset:TintsetTintset(const(const TintsetTintset&r)&r)size=r.size;size=r.size;set=new set=new intint size;clear();size;clear();for(for(intint i=0;isize;i+)i=0;isize;i+)seti=r.seti;seti=r.seti;40整数集合类整数集合类 3 3 增增加加删删除除一一个个元元素素。若若指指定定的

49、的元元素素k k合合法法，则则将将其其加加入入删删除除到到集集合中否合中否则显则显示出示出错错信息。信息。void void TintsetTintset:add(:add(intint k)k)if(valid(k)setk=1;if(valid(k)setk=1;else else coutcoutinvalid insertn;invalid insertn;void void TintsetTintset:remove(:remove(intint k)k)if(valid(k)setk=0;if(valid(k)setk=0;else else coutcoutinvalid del

50、eten;invalid deleten;4 4 判判指指定定的的元元素素k k是是否否属属于于当当前前集集合合。若若指指定定的的元元素素k k属属于于当当前前集集合合则则返返回回truetrue否否则则返回返回falsefalse。bool Tintsetbool Tintset:contain(:contain(intint k)k)if(setk=1)return true;else return false;if(setk=1)return true;else return false;41整数集合类整数集合类 5 5判判指指定定的的集集合合是是否否包包含含在在当当前前集集合合中中。若