数据结构——串和数组.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 三对角矩阵的存储方式： 设三对角矩阵为An×n，满足： 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 A= a11 a12 0 ? … … … … … … 0 a21 a22 a23 0 … … … … … 0 0 a32 a33 a34 0 … … … … 0 … … … … … … … … … … 0 0 … … … … … an-1,n-2 an-1,n-1 an-1,n 0 0 … … … … … 0 an,n-1 ann 若将其中的非零元素按行优先顺序存放，假设每个数据元素占用一个字节的存储单元，则三对角矩阵的地址公式为： 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 Loc(aij) = Loc(a11)+2(i?1)+(j?1) 其中：i=1, j=1, 2 或：i=n, j=n-1, n 或：1in, j=i-1, i, i+1 对称矩阵的存储方式： 解决方案类似于下三角矩阵的存储。 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 稀疏矩阵： 如果一个矩阵中大多数元素为零，非零元素较少且分布无一定规律，则称之为稀疏矩阵。 顺序存储： 三元组表：线性表中的每个结点由三个字段组成，分别是该非零元素的行下标、列下标和值。 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 稀疏矩阵的C语言表示： #define smax 16 /* 最大非零元素个数 */ typedef int datatype; typedef struct { int i, j; /* 行号，列号 */ datatype v; /* 元素值 */ } node; 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 稀疏矩阵的C语言表示： typedef struct { int m, n, t; /* 行数，列数，非零元素个数 */ node data[smax]; /* 三元组表 */ } spmatrix; /* 稀疏矩阵类型 */ 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 稀疏矩阵举例：非零元素按行优先顺序存储。 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 该稀疏矩阵共有20个元素，仅有6个非零元素。其三元组表如下图所示。 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 m=4 n=5 t=6 行号域 列号域 值域 1 0 1 5 2 0 4 8 3 1 0 1 4 1 2 3 5 2 1 -2 6 3 0 6 伪地址表示法： 伪地址是指本元素在矩阵中按行优先顺序的相对位置，上述稀疏矩阵A中非零元素为： {5，8，1，3，-2，6} 非零元素的伪地址=n*i+j，n为矩阵的列数。 因此，5的伪地址为1；1的伪地址为5；…。 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 稀疏矩阵的转置运算： 一般矩阵的转置算法为： for(col=0; coln; col++) for(row=0; rowm; row++) B[col][row]=A[row][col]; 由于稀疏矩阵含有大量的零元素，因此，其转置算法修改为如下所示： 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 spmatrix ?TRANSMAT(spmatrix ?a) /* 返回稀疏矩阵A的转置 */ { int ano, bno, col; /* ano和bno分别指示a-data 和b-data中结点序号； col指示*a的列号，即*b的行号 */ pmatrix *b; /* 存放转置后的矩阵 */ b=malloc(sizeof(spmatrix)); b-m=a-n; b-n=a-m; /*行列数交换*/ b-t=a-t; 3.6.3 二维数组的结构特点—特殊矩阵的存储方式 if (b-t0) /* 有非零元素，则转置 */ { bno=0; for(col=0; cola-n; col++) /*