重学数据结构——矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了重学数据结构——矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【矩阵】

下三角矩阵列优先,矩阵,线性代数,数据结构

~~梦回线代（滑稽）~~

将二维矩阵按行放到一个一维矩阵中，其中下标k和i，j的关系为：

K=n*(i-1)+j-1 例：A85=S7+j-1=n*7+5-1=7n+4

【矩阵-课堂习题】

例、数组A中，每个元素的长度为3字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[8][5]的起始地址为（ C ）

A.SA+141 B.SA+144 C.SA+222 D.SA+225

解析：7n+4=7*10+4=74，每个元素长度3字节首地址SA，则为74*3+SA，即SA+222

【对称矩阵】

下三角矩阵列优先,矩阵,线性代数,数据结构

下标k和i,j的关系：

K=Si-1+j-1=(1+i-1)(i-1)/2+j-1=i(i-1)/2+j-1（下三角公式推导，利用等差数列求和）

$下三角矩阵列优先,矩阵,线性代数,数据结构$ （下三角区和主对角线元素）

$下三角矩阵列优先,矩阵,线性代数,数据结构$ （上三角区元素aij=aji）

巧记：Aij，行左列右行列式，左边的下三角以i(行)为主，即等差数列公式以i为主，右等同

【对称矩阵-课堂习题】

例、设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储A11为第一个元素，其存储地址为1，每个元素占一个地址空间，则A85地址为（ B ）

A.23 B.33 C.18 D.40

解析：（1）由k与i,j的公式可知k=Si-1+j-1，但本题由题干可知A11为第一个元素，其存储地址为1，即储存在一维数组中第一个下标为0，所以此时k无需减1，即k=Si-1+j（2）题干：以行序为主序存储，即 $下三角矩阵列优先,矩阵,线性代数,数据结构$ ，得k=28+5=33

【三角矩阵】

三角矩阵分为：下三角矩阵和上三角矩阵

下三角矩阵：下三角为权值，上三角全相同（例如全为0或1）

上三角矩阵：上三角为权值，下三角全相同（例如全为0或1）

下三角矩阵列优先,矩阵,线性代数,数据结构

下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于储存完下三角区和主对角线上的所有元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵A[1...n][1...n]压缩存储在B[n(n+1)/2]中

下三角矩阵元素下标之间的对应关系为：

$下三角矩阵列优先,矩阵,线性代数,数据结构$

为下三角区和主对角线元素

为上三角区元素

上三角矩阵元素下标之间的对应关系为：

$下三角矩阵列优先,矩阵,线性代数,数据结构$

为上三角区和主对角线元素

为下三角区元素

【三角矩阵-课堂习题】

例、若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2+1]中，则存放到B[k]中的非零元素aij（）的下标i、j与k的对应关系是（ B ）

A. $下三角矩阵列优先,矩阵,线性代数,数据结构$ B. $下三角矩阵列优先,矩阵,线性代数,数据结构$

C. $下三角矩阵列优先,矩阵,线性代数,数据结构$ D. $下三角矩阵列优先,矩阵,线性代数,数据结构$

解析：由题知，按列压缩存储，则第一列有n个元素a1=n，第二列有n-1个元素，a2=n-1....，

aj-1=n-(j-1)+1=n-j+2，aj=n-j+1，Sj-1= $下三角矩阵列优先,矩阵,线性代数,数据结构$ 则此时求出前j-1列个数，我们需要求第i行第j列，则此时需考虑在第j列的第几个，我们可知例如A11,A22,A33都是位于主对角线上为第一个，则A43为第三列的第二个，由此可推出i和j的关系是i-j+1，综上则aij的下标i、j和k的对应关系为 $下三角矩阵列优先,矩阵,线性代数,数据结构$

【三对角矩阵】

下三角矩阵列优先,矩阵,线性代数,数据结构

元素下标之间的关系：

三对角矩阵是按行存放的，我们要求第i行第j列，首先要求前i-1的元素个数，即Si-1=3(i-1)-1,即Sn=3n-1即前三行有8个元素，前四行有11个元素，因为A21,A22,A23分别为1,2,3个元素，则我们可以推出i和j的关系，即为j-i+2，又因下标k从0开始所以最后还需减去一个1，综上我们要求第i行第j列所对应下标k之间的对应关系为：k=3(i-1)-1+j-i+2-1=3i-4+j-i+1=2i+j-3