数据结构——二维数组.ppt

1 版权所有, 1997 (c) Dale Carnegie int size; public: Array(int sz=100) ; Array(const Array Array()deletea; int getsize()return size; T Array void resize(int sz=100) ; void prnt() ; 5 数组类构造函数与赋值函数 Array(int sz=100) if(sz a=new Tsize; for(int i=0;i size=arr.size; a=new Tsize; for(int i=0;i|c1id1;c2jd2-1;aij,ai,j+1D COL=|c1id1-1 ;c2jd2;ai+1,j,aijD 其中：(c1,d1)和(c2,d2)分别为数组下标i, j的一对界偶（即满 足条件c1id1，c2jd2）。 称c1,c2为下界,通常取c1=c2=1; 称d1,d2为上界,通常取d1=m，d2=n 11 二维数组的存储结构 按行排列 排列方式 a11 a12 a1n a21 a22 a2n am1 am2 am3 amn 地址计算 pos(Ai,j)L0inkjkL0(inj)k (00) k=0; for (i=0;ic;i+) for (j=0;jnum;j+) if (itemj.col=i) x.itemk.row=itemj.col; x.itemk.col=itemj.row; x.itemk.value=itemj.value; k+; return(x); 上述算法中要进行二重循环，算法的效率比较低 方法二：快速转置 即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定 M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M 的每一列中非零元个数 实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第col列第一个非零元在mb中位置 显然有： cpot1=1; cpotcol=cpotcol-1+numcol-1; (2col ma0.j) 1357889 col numcol cpotcol 1 2 2 2 3 2 4 1 5 0 6 1 7 0 37 稀疏矩阵快速转置 SMatrixic;i+ ) rnumi=0; for (i=0;inum;i+ ) rnumitemi.col+; 形成数组rstart； rstart0=0; for (i=1;ic;i+ ) rstarti=rnumi-1+rstarti-1; 39 稀疏矩阵快速转置 SMatrix int i,j; int rnum100,rstart100; x.r = c; x.c= r; x.num= num; x.item=new RCVnum; for (i=0;ic;i+ ) rnumi=0; for (i=0;inum;i+ ) rnumitemi.col+; rstart0=0; for (i=1;ic;i+ ) rstarti=rnumi-1+rstarti-1; for (i=0;inum;i+ ) j= itemi.col; x.itemrstartj.row=j; x.itemrstartj.col=itemi.row; x.itemrstartj.value=itemi.value; rstartj+; return(x); 6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v 0 1 2 3 4 5 6 7 8 ma i j v 0 1 2 3 4 5 6 7 8 mb col numcol cpotcol 1 1 2 2 3 2 3 5 2 4 7 1 5 8 0 6 8 1 7 9 0