数据结构ch数组和广义表.ppt

《数据结构ch数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章数组和广义表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1数组的定义和特点定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()5.2数组的顺序存储结构次序约定以行序为主序以列序为主序a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….

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

3、1按行序为主序：三角矩阵a1100……..0a21a220……..0an1an2an3……..ann………………….0a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：3．对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。例如，图5-3为77的三对角矩阵（即有三条对角线上元素非0）。3．对角矩阵我们仅讨论三对角矩阵的压缩存贮，五对角矩阵，七对角矩阵等读者可以作类似分析。在一个nn的

4、三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，则：s[k]与a[i][j]的对应关系为：3i-1当i=j+1k=3i当i=j3i+1当i=j-1M由{(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）唯一确定稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每

5、个非零元的行列下标及其值稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col

6、+)for(row=0;row

7、元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序Ch4_1.c678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2如何求转置矩阵？用“三元组”表示时如何实现？121415-522-731363428211451-522-713364328方法二：首先应该确定转置后每一行的第一个非零元在三元组中的位置。cpot[

8、1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+n