2)从 Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点,然后再从该结点后的下一结 点开始寻找、输出和删除表中的第m个结点,重复此过程 35二维数组(矩阵) ■1.二维数组定义 ◆行关系,列关系均是线性关系 ■2.二维数组的顺序存放 (一)行优先存放:ana12..a1na12.aina12…,aim,am1am2…amn 计算a的存放位置:设每个元紊占据S个存储单元 Loc(aj)=Loc(an)+(i-1)*n+(-1)*S计算前面有多少个元素 (二)列优先存放 ala21…am1a2a2…am2aa2j…ai.alna2n…amn Loc(aij)=Loc(an)+((j-1)m+(i-1))"s ■3.规则矩阵的压缩存储 ◆(1)对称矩阵,三角矩阵的压缩 对称矩阵:ali,j=aj,i 三角矩阵:上三角为0,或下三角为0 只存储上或下三角内的元素,节约近一半的存储空间 (1)对称矩阵,三角矩阵的压缩 i>=j时,元素位于下三角 Loc(aij)=Loc(an)+(i(i-1)/2+(j-1))*S j时,元素位于上三角 Loc(ai)=loc(an)+(j(j-1)/2+(i-1))*S ■(2)稀疏矩阵 矩阵中的非零元素很少,分布没有规律 利用三元存储法(行值,列值,元素值 先形成三元矩阵 再按照行优先顺序方式存储 稀疏矩阵三元组定义 1)定义三元组元素 typedef struct tuple3tpl int row num;/行号 int col num:;/列号* elemtype value;/元素值* 3 tuple3tp 2)定义三元组 typedef struct tuple int row;/行数 int col;/列数* int num;/非零元素个数 tuple3 tp datal MAXNUMI;/三元组* ] tuple 1111 2）从 Josephus 表中的第 s 个结点开始寻找、输出和删除表中的第 m 个结点，然后再从该结点后的下一结 点开始寻找、输出和删除表中的第 m 个结点，重复此过程， 3.5 二维数组（矩阵） ◼ 1.二维数组定义 ◆ 行关系，列关系均是线性关系 ◼ 2. 二维数组的顺序存放 （一）行优先存放：a11 a12... a1na21 a22... ai1 ai2 ...ain... am1 am2 ... amn ◆ 计算 aij的存放位置：设每个元素占据 S 个存储单元 Loc(aij) = Loc(a11) + (( i - 1)*n + (j - 1))*S 计算前面有多少个元素 ◼ （二）列优先存放 a11 a21... am1a12 a22... am2a1j a2j ...aii... a1n a2n ... amn Loc(aij) = Loc(a11) + (( j - 1)*m + (i - 1))*S ◼ 3. 规则矩阵的压缩存储 ◆ (1)对称矩阵，三角矩阵的压缩  对称矩阵：a[ i , j ] = a[ j , i ]  三角矩阵：上三角为 0，或下三角为 0 只存储上或下三角内的元素，节约近一半的存储空间 (1)对称矩阵，三角矩阵的压缩 i >= j 时，元素位于下三角 Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1))*S i < j 时，元素位于上三角 Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1))*S ◼ (2)稀疏矩阵 ◆ 矩阵中的非零元素很少，分布没有规律 ◆ 利用三元存储法 （行值，列值，元素值）  先形成三元矩阵  再按照行优先顺序方式存储。 稀疏矩阵三元组定义 1)定义三元组元素 typedef struct tuple3tp{ int row_num; /*行号*/ int col_num; /*列号*/ elemtype value; /*元素值*/ } tuple3tp 2)定义三元组 typedef struct tuple3{ int row; /*行数*/ int col; /*列数*/ int num; /*非零元素个数*/ tuple3tp data[ MAXNUM];/* 三元组*/ }tuple3;