第2章数组 素。试问: (1)该带状矩阵中有多少个非零元素? (2)若用一个一维数组B按行顺序存放各行的非零元素,且设a1存放在B[0中,请给出一个公式, 计算任一非零元素a在一维数组B中的存放位置。 【解答】 (1)主对角线包含n个非零元素,其上下各有一条包含n-1个非零元素的次对角线,再向外,由 各有一条包含n-2个非零元素的次对角线,……,最外层上下各有一条包含n-b个非零元素的次对角 线。则总共的非零元素个数有 =n+2 (n-1)+(n-b)b =n+b2n-b-1)=(2b+1)n-b-b2 2 n+2(n-1)+2(n-2)+…+2(n-b)=n+2(n-1)+(n-2)+…+(n-b)) (2)在用一个一维数组B按行顺序存放各行的非零元素时,若设b≤n/2,则可按各行非零元素个 数变化情况,分3种情况讨论 ①当1≤I≤b+1时,矩阵第1行有b+1个元素,第2行有b+2个元素,第3行有b+3个元素,…… 第i行存有bi个元素,因此,数组元素A[在B[]中位置分析如下: 第i行(i≥1)前面有i-1行,元素个数为(b+1)+(b+2)+…+(b+i-1)=(i-1)*bi*(i-1)2,在第i行第j 列(≥1)前面有j1个元素,则数组元素A[[在B[]中位置为 (-1)*b i*(1-1) 2 ②当b+1<i≤nb+1时,各行都有2b+1个元素。因为数组A[J]前b行共有b*b+(b+1)*b/2= b(3*b+1)2个元素,所以数组元素A[[在B[]中位置为 b*(3*b+1) (i-b-1)*(2*b b ③当nb+l<i≤n时,各行元素个数逐步减少。当i=nb+1时有2b个非零元素,当i=n-b+2时有 2b-1个非零元素,当i=nb+3时有2b-2个非零元素,…,当in时有b+1个非零元素。因为前面nb 行总共有b*(3*b+1)2+(n-2+b)+(2*b+1)个非零元素,所以在最后各行数组元素A[订在B[j中位置为 b*(3*b+1 (1-n+b-1)*(4*b-i+n-b+2) 2(-2*b)*(2*b+1)+ -+1-1+b 2 2-13稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。 1201100130 稀疏矩阵有多少行,在行指针数组中就有多少个元素:第i个元 素的数组下标i代表矩阵的第i行,元素的内容即为稀疏矩阵第i 0-400030 行的第一个非零元素在二元组表中的存放位置。二元组表中每个 0008000 二元组只记录非零元素的列号和元素值,且各二元组按行号递增 0000000 的顺序排列。试对右图所示的稀疏矩阵,分别建立它的三元组表0-900200 和带行指针数组的二元组表 【解答】 行指针数组 二元组表data 0 1 3第 2 章 数组 18       − − 0 9 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 4 0 0 0 3 0 0 0 0 0 0 0 14 12 0 11 0 0 13 0 素。试问： (1) 该带状矩阵中有多少个非零元素？ (2) 若用一个一维数组 B 按行顺序存放各行的非零元素，且设 a11 存放在 B[0]中，请给出一个公式， 计算任一非零元素 aij 在一维数组 B 中的存放位置。 【解答】 (1) 主对角线包含 n 个非零元素，其上下各有一条包含 n-1 个非零元素的次对角线，再向外，由 各有一条包含 n-2 个非零元素的次对角线，……，最外层上下各有一条包含 n-b 个非零元素的次对角 线。则总共的非零元素个数有 n + 2(n-1) + 2(n-2) + … + 2(n-b) = n + 2( (n-1) + (n-2 ) + … + (n-b) ) (2) 在用一个一维数组 B 按行顺序存放各行的非零元素时，若设 b≤n/2，则可按各行非零元素个 数变化情况，分 3 种情况讨论。 ① 当 1≤i≤b+1 时，矩阵第 1 行有 b+1 个元素，第 2 行有 b+2 个元素，第 3 行有 b+3 个元素，……， 第 i 行存有 b+i 个元素，因此，数组元素 A[i][j]在 B[ ]中位置分析如下： 第 i 行(i≥1)前面有 i-1 行，元素个数为 (b+1)+(b+2)+…+(b+i-1) = (i-1)*b+i*(i-1)/2，在第 i 行第 j 列(j≥1)前面有 j-1 个元素，则数组元素 A[i][j]在 B[ ]中位置为 ② 当 b+1<i≤n-b+1 时，各行都有 2b+1 个元素。因为数组 A[ ][ ]前 b 行共有 b*b+(b+1)*b/2 = b*(3*b+1)/2 个元素，所以数组元素 A[i][j]在 B[ ]中位置为 ③ 当 n-b+1<i≤n 时，各行元素个数逐步减少。当 i=n-b+1 时有 2b 个非零元素，当 i=n-b+2 时有 2b-1 个非零元素，当 i=n-b+3 时有 2b-2 个非零元素，…，当 i=n 时有 b+1 个非零元素。因为前面 n-b 行总共有 b*(3*b+1)/2+(n-2*b)*(2*b+1)个非零元素，所以在最后各行数组元素 A[i][j]在 B[ ]中位置为 2-13 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。 稀疏矩阵有多少行，在行指针数组中就有多少个元素：第 i 个元 素的数组下标 i 代表矩阵的第 i 行，元素的内容即为稀疏矩阵第 i 行的第一个非零元素在二元组表中的存放位置。二元组表中每个 二元组只记录非零元素的列号和元素值，且各二元组按行号递增 的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表 和带行指针数组的二元组表。 【解答】 2 n b(2n b 1) (2b 1)n - b - b 2 ((n 1) (n b))b n 2* = + − − = + − + − = + ( ) j 1 2 i * (i 1) i 1 * b + − − − + (i b 1)*(2*b 1) j i b 2 b*(3*b 1) + − − + + − + + j i b 2 (i n b 1)*(4*b i n b 2) (n 2*b)*(2*b 1) 2 b*(3*b 1) + − + − + − − + − + + − + + + 行指针数组 row 0 0 1 3 2 4 3 6 4 7 5 7 二元组表 data col value 0 0 12 1 2 11 2 5 13 3 6 14 4 1 -4 5 5 3 6 3 8