(5.2.1)--5.2特殊矩阵数据结构与算法.ppt

特殊矩阵特殊矩阵1 5.2.1 特殊矩阵 对称矩阵 三角矩阵 矩阵：矩阵：由 m n 个数aij排成的m行n列的数表称为m行n列的矩阵，简称m n矩阵。记作：()()()()()()()()()1.将一个矩阵存储为一个二维数组，可以对其元素进行随机存取，各种矩阵运算也非常简单。2.在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，采用二维数组会占用许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的空间浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5 a11 0 8 0 0 a21 a 22 8 9 2 6 a31 a32 a33 0 2 5 1 .0 6 1 3 an1 an2 an3 ann 对称矩阵对称矩阵 在这个下三角矩阵中，第在这个下三角矩阵中，第i行恰有行恰有i个元素个元素，元素总数为：，元素总数为：n(n+1)/2a11a21a22a31a32a33ai1ai2ai31+2+3+(n-1)+n1 5 1 3 71 5 1 3 7 k=i*(i-1)/2+(j-1)ij k=j*(j-1)/2+(i-1)ij6对称矩阵下三角压缩存储的地址映射公式a11a21 a 22a31 a32 a33.an1 an2 an3 ann a11a21a22a31a32a33ai1ai2ai3aijaijk?三角矩阵三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。三角矩阵常数为零。a11 a12 a 1 n-1 a11 c c c a21 a 2 n-1 a21 a22 c .c c a n n an1 an2 an n (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵 课程作业：1 1、已知对称矩阵、已知对称矩阵intint a1010,a1010,下三角压缩存储时计算下三角压缩存储时计算a74a74的相对地址是多少？的相对地址是多少？9 下下下下 节节节节 课课课课 见见见见！