《数据结构清华版》第四章串和数组

1、数据结构清华版第四章串和数组数据结构清华版第四章串和数组v4.2 数组的顺序存储结构次序约定v以行序为主序v以列序为主序 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放按行序为主序存放 amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n 按列序为主序存放按列序为主序存放01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21

2、a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 数据结构清华版第四章串和数组v4.3 矩阵的压缩存储对称矩阵jiijjjijiik, 12/ ) 1(12/ ) 1(， a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：数据结构清华版第四章串和数组三角矩阵 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0

3、Loc(aij)=Loc(a11)+( +(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：数据结构清华版第四章串和数组对角矩阵 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n

4、(n+1)/2-1 按行序为主序：数据结构清华版第四章串和数组7600070015000001800000240001400003000000000009120MM由(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）唯一确定稀疏矩阵v定义：非零元较零元少，且分布没有一定规律的矩阵v压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值数据结构清华版第四章串和数组v稀疏矩阵的压缩存储方法顺序存储结构v三元组表#define M 20typedef struct no

5、de int i,j; int v;JD;JD maM;三元组表所需存储单元个数为3(t+1)其中t为非零元个数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 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数行列下标非零元值7600070015000001800000240001400003000000000009120M数据结构清华版第四章串和数组v带辅助行向量的二元组表增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元在二元组表中的起始地址（

6、m为行数）显然有：NRA1=1NRAi=NRAi-1+第i-1行非零元个数(i2)0 1 2 3 4 5 6 NRA1335676 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 maj v0 1 2 3 4 5 6 7 8矩阵列数和非零元个数列下标和非零元值NRA0不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+17600070015000001800000240001400003000000000009120M数据结构清华版第四章串和数组v伪地址表示法伪地址：本元素在矩阵中（包括零元素再内） 按行优先顺序的相对位置 6 7 2 12 3 9

7、15 -3 20 14 24 24 30 18 36 15 39 -7 maaddr v伪地址非零元值矩阵行列维数0 1 2 3 4 5 6 7 8伪地址表示法需存储单元个数为2(t+1)7600070015000001800000240001400003000000000009120M数据结构清华版第四章串和数组v求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+) for(row=0;rowp-col时，p和q右移（2）插入：a、若p=NULL且q=NULL，即本行空，则rhr-1=s;b、若p=NULL,q!=NULL，即走到行末，则q-right=sc、若c=p-col，则修改