数据结构：矩阵-编程实验室

数据结构：矩阵

矩阵是由m 行 n 列元素排列成的二维矩形数组，是线性代数和计算机科学中基础的数据结构。在编程中，矩阵通常用于表示二维数据（如图像像素、邻接矩阵）、线性变换、方程组等场景。
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、矩阵的定义与表示

1. 数学定义

一个m×n 矩阵（m 行 n 列）可表示为：
A=[a11a12…a1na21a22…a2n⋮⋮⋱⋮am1am2…amn] A = \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix}A=a11a21⋮am1a12a22⋮am2……⋱…a1na2n⋮amn
其中aija_{ij}aij表示矩阵第iii行第jjj列的元素，矩阵的维度记为m×n。

2. 编程中的存储方式

在计算机中，矩阵的存储主要有两种方式：

二维数组（行优先存储）：最常用的方式，如 Python 的list[list]、Java 的int[][]，按行顺序存储元素，访问a[i][j]的时间复杂度为O(1)O(1)O(1)。
一维数组映射：将二维矩阵映射到一维数组，通过公式index = i * n + j（行优先）或index = j * m + i（列优先）计算元素位置，适合底层内存优化。

二、矩阵的核心分类

根据元素分布和维度特征，矩阵可分为以下常见类型：

方阵：行数和列数相等（m=n）的矩阵，如 3×3 矩阵。方阵可定义对角线元素（aiia_{ii}aii）、上三角矩阵（对角线下方元素全为 0）、下三角矩阵（对角线上方元素全为 0）。
单位矩阵：一种特殊的方阵，对角线元素全为 1，其余元素全为 0，记为III。例如 3×3 单位矩阵：
I3=[100010001] I_3 = \begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}I3=100010001
零矩阵：所有元素均为 0 的矩阵，记为OOO。
对称矩阵：满足aij=ajia_{ij}=a_{ji}aij=aji的方阵，其转置等于自身（AT=AA^T=AAT=A）。
稀疏矩阵：大部分元素为 0 的矩阵，通常用三元组（行号, 列号, 值）或十字链表存储，节省空间。

三、矩阵的核心操作

1. 基础操作

操作	描述	时间复杂度
访问元素	获取第 i 行第 j 列的元素	O(1)O(1)O(1)
矩阵转置	将矩阵的行和列互换，得到ATA^TAT，满足AT[i][j]=A[j][i]A^T[i][j] = A[j][i]AT[i][j]=A[j][i]	O(m×n)O(m×n)O(m×n)
矩阵加法	两个同维度矩阵对应位置元素相加，要求AAA和BBB均为 m×n 矩阵	O(m×n)O(m×n)O(m×n)
标量乘法	矩阵中所有元素乘以一个常数 k	O(m×n)O(m×n)O(m×n)

2. 矩阵乘法

矩阵乘法是矩阵的核心操作，仅当第一个矩阵的列数等于第二个矩阵的行数时可乘。

若AAA是m×pm×pm×p矩阵，BBB是p×np×np×n矩阵，则乘积C=A×BC=A×BC=A×B是m×nm×nm×n矩阵，其中：
C[i][j]=∑k=0p−1A[i][k]×B[k][j] C[i][j] = \sum_{k=0}^{p-1} A[i][k] × B[k][j]C[i][j]=k=0∑p−1A[i][k]×B[k][j]
时间复杂度：O(m×p×n)O(m×p×n)O(m×p×n)，是算法优化的重点（如 Strassen 算法可优化至O(n2.81)O(n^{2.81})O(n2.81)）。

3. 特殊操作

矩阵求逆：仅方阵可逆时存在逆矩阵A−1A^{-1}A−1，满足A×A−1=IA×A^{-1}=IA×A−1=I，常用于解线性方程组。
行列式计算：仅适用于方阵，是衡量矩阵是否可逆的重要指标，记为det(A)det(A)det(A)。

四、矩阵的实现示例（Python）

classMatrix:def__init__(self,data):"""初始化矩阵，data为二维列表"""self.data=data self.rows=len(data)self.cols=len(data[0])ifself.rows>0else0def__str__(self):"""矩阵的字符串表示"""return'\n'.join([' '.join(map(str,row))forrowinself.data])deftranspose(self):"""矩阵转置"""transposed=[[self.data[j][i]forjinrange(self.rows)]foriinrange(self.cols)]returnMatrix(transposed)defadd(self,other):"""矩阵加法，要求维度相同"""ifself.rows!=other.rowsorself.cols!=other.cols:raiseValueError("矩阵维度不匹配，无法相加")result=[]foriinrange(self.rows):row=[self.data[i][j]+other.data[i][j]forjinrange(self.cols)]result.append(row)returnMatrix(result)defmultiply(self,other):"""矩阵乘法，要求self.cols == other.rows"""ifself.cols!=other.rows:raiseValueError("矩阵维度不匹配，无法相乘")result=[]foriinrange(self.rows):row=[]forjinrange(other.cols):# 计算C[i][j] = sum(A[i][k] * B[k][j])val=sum(self.data[i][k]*other.data[k][j]forkinrange(self.cols))row.append(val)result.append(row)returnMatrix(result)# 使用示例if__name__=="__main__":# 初始化两个矩阵A=Matrix([[1,2,3],[4,5,6]])# 2×3矩阵B=Matrix([[7,8],[9,10],[11,12]])# 3×2矩阵C=Matrix([[1,2],[3,4]])# 2×2矩阵print("矩阵A:")print(A)print("\n矩阵A的转置:")print(A.transpose())print("\n矩阵C + C:")print(C.add(C))print("\n矩阵A × B:")print(A.multiply(B))