了解数组的定义(精).ppt

《了解数组的定义(精).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组要求：了解数组的定义，数组的顺序表示；了解特殊矩阵的压缩存储表示和下标变换；了解稀疏矩阵的定义和表示：三元组表和十字链表。（实现和算法不要求）1第5章数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1数组的定义和特点定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()25.2数组的顺序存储结构次序约定以行序为主序以列序为主序a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n

2、+(j-1)]*l按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l35.3矩阵的压缩存储对称矩阵a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….a11a21a22a31a32an1an

3、n…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：存放位置下三角阵上三角阵4三角矩阵a1100……..0a21a220……..0an1an2an3……..ann………………….0Loc(aij)=Loc(a11)+[(+(j-1)]*li(i-1)2a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：5对角矩阵a11a120…………….0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00……an,n-1ann.0a32a33a340………0……………………

4、………Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11a12a21a22a23ann-1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：6M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩阵维数（6,7）唯一确定稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值7稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode{inti,j;

5、intv;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值8带辅助行向量的二元组表增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）显然有：NRA[1]=1NRA[i]=NRA[i-1]+第i-1行非零元个数(i2)0123456NRA133567678212391-36143242181154-7majv012345678

6、矩阵列数和非零元个数列下标和非零元值NRA[0]不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+19伪地址表示法伪地址：本元素在矩阵中（包括零元素再内）按行优先顺序的相对位置672123915-3201424243018361539-7maaddrv伪地址非零元值矩阵行列维数012345678伪地址表示法需存储单元个数为2(t+1)10求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col

7、mn)11678121213931-3361443245218611564-7ijv012345678maijv76813-3161521122518319342446-76314012345678mb?12解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以N的行(M的列)为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转