文章目录前言1. 基本概念2. 存储方式3. 特殊矩阵3.1 对称矩阵3.2 三角矩阵3.3 三对角矩阵3.4 稀疏矩阵

前言

  本篇章主要介绍数组及特殊矩阵，包括数组的基本概念、数组的存储、对称矩阵、三角矩阵、三对角矩阵及稀疏矩阵四种特殊矩阵的压缩。

1. 基本概念

  数组是由

n(n≥1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在

n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
  数组是线性表的推广，一维数组可以视为一个线性表，二维数组可以视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
  Python中内置的数组是array，但通常使用列表list代替。下面给出列表(没说是数组哦)的一些基本操作：

append(x)
在列表的末尾添加一个元素

x

clear()
删除列表中的所有元素

copy()
返回列表的副本

count(x)
返回列表中元素

x的个数

extend(iterable)
将列表元素(或任何可迭代的元素)添加到列表的末尾

index(x)
返回元素

x的第一个索引

insert(index, x)
在指定位置

index添加元素

x

pop(index)
删除指定位置

index的元素，默认删除最后一个并返回

remove(x)
删除指定元素

x

reverse()
反转列表

sort(reverse=False, key=myFunc)
对列表进行排序，默认升序，可以通过参数

key指定排序标准的函数

  在Python中最常用的数组运算函数库是numpy，它是一个扩展程序库，在机器学习中超级常用，这里不再叙述，感兴趣的话可以关注或订阅我的机器学习专栏。

2. 存储方式

  由于数组一般不进行插入或删除操作，所以一旦建立了数组，其结构中的数据元素个数和元素之间的关系就不再发生变动，所以数组常采用顺序存储结构来存储数据元素。
  一维就是一个线性表，就不多说了，就说一下子多维数组吧，它有按行优先和按列优先两种映射方式。以二维数组(矩阵)为例，按行优先存储的基本思想就是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。

M=[a11​a21​​a12​a22​​a13​a23​​]  对于上述矩阵

M，按行优先方式在内存中的存储形式为：

  对于上述矩阵

M，按列优先方式在内存中的存储形式为：

3. 特殊矩阵

  特殊矩阵是指具有许多相同元素或零元素，并且这些元素的分布有一定规律性的矩阵。
  压缩存储是指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是节省存储空间。
  特殊矩阵的压缩存储方法是指找出特殊矩阵中值相同的元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

3.1 对称矩阵

$M=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ \mathrm{⋮}& \mathrm{⋮}& \ddots & \mathrm{⋮}\\ a_{n1}& a_{n2}& \dots & a_{nn}\end{array}\right]$
a_{11} & a_{12} & \dots & a_{1n} \\
a_{21} & a_{22} & \dots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \dots & a_{nn}
\end{bmatrix}

M=⎣⎢⎢⎢⎡​a11​a21​⋮an1​​a12​a22​⋮an2​​……⋱…​a1n​a2n​⋮ann​​⎦⎥⎥⎥⎤​  

n阶矩阵

M中的任意一个元素

aij​都有

aij​=aji​(1≤i,j≤n)，则称

n阶矩阵

M为对称矩阵，其中的元素可以分为上三角区

(i<j)、主对角线

(i=j)和下三角区

(i>j)三个部分。
  对于对称矩阵，我们可以为每一对对称元素分配一个存储空间，则可以将

n2个元素压缩存储到

2n(n+1)​个存储空间中。这里用数组

A来压缩存储矩阵

M的下三角区的元素，当然，这里还包括对角线上的元素。数组

A[k]与矩阵

M中的元素

aij​存在着以下一一对应的关系：

k=⎩⎪⎨⎪⎧​2i(i−1)​+j−1,2j(j−1)​+i−1,​i≥j,即下三角区和主对角线i<j,即上三角区​  对于任意给定的一组下标

(i,j)，都可以在数组

A中找到矩阵

M的元素

aij​，同理，对所有的

k=0,1,2,…,2n(n+1)​−1，也都可以确定数组

A中的元素在矩阵

M中的位置

(i,j)。

k 0 1 2 3 $\dots$

… $\frac{n(n+1)}{2}-1$

2n(n+1)​−1 $a_{ij}$

aij​

a11​

a21​

a22​

a31​

…

ann​

  上面的

k是这样算的：第1行有1个元素，第2行有两个元素，第三行有三个元素，

…，第

i−1行有

i−1个元素，第

i行有

j−1个元素

(ai1​,ai2​,…,aij−1​)，所以

k=1+2+3+⋯+(i−1)+(j−1)=2i(i−1)​+j−1。

3.2 三角矩阵

$M=\left[\begin{array}{cccc}{a}_{11}& & & \\ a_{21}& a_{22}& & \\ \mathrm{⋮}& \mathrm{⋮}& \ddots & \\ a_{n1}& a_{n2}& \dots & a_{nn}\end{array}\right]M=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ & a_{22}& \dots & a_{2n}\\ & & \ddots & \mathrm{⋮}\\ & & & a_{nn}\end{array}\right]$
a_{11} & & & \\
a_{21} & a_{22} & & \\
\vdots & \vdots & \ddots & \\
a_{n1} & a_{n2} & \dots & a_{nn}
\end{bmatrix}
M=\begin{bmatrix}
a_{11} & a_{12} & \dots & a_{1n} \\
& a_{22} & \dots & a_{2n} \\
& & \ddots & \vdots \\
& & & a_{nn}
\end{bmatrix}

M=⎣⎢⎢⎢⎡​a11​a21​⋮an1​​a22​⋮an2​​⋱…​ann​​⎦⎥⎥⎥⎤​M=⎣⎢⎢⎢⎡​a11​​a12​a22​​……⋱​a1n​a2n​⋮ann​​⎦⎥⎥⎥⎤​  下三角矩阵中，上三角区的所有元素均为同一常量；上三角矩阵中，下三角区的所有元素均为同一常量。它们的压缩存储方式同对称矩阵是一样的，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着要存储对角线上方的常量，所以需要

2n(n+1)​+1个存储空间，多了一个常量的存储空间。还以下三角区为例：

k=⎩⎪⎨⎪⎧​2i(i−1)​+j−1,2n(n+1)​,​i≥j,即下三角区和主对角线i<j,即上三角区​

k 0 1 2 3 $\dots$

… $\frac{n(n+1)}{2}-1$

2n(n+1)​−1 $\frac{n(n+1)}{2}$

2n(n+1)​ $a_{ij}$

aij​

a11​

a21​

a22​

a31​

…

ann​

c

  如果是存储上三角区的元素，数组的下标

k可以这样计算：第1行有

n个元素，第2行有

n−1个元素，第3行有

n−2个元素，

…，第

i−1行有

n−i+2个元素，第

i行有

j−i个元素，所以

k=n+(n−1)+(n−1)+⋯+(n−i+2)+(j−i)=2(i−1)(2n−i+2)​+j−i。

3.3 三对角矩阵

$M=\left[\begin{array}{cccccc}{a}_{11}& a_{12}& & & & \\ a_{21}& a_{22}& a_{23}& & & \\ & a_{32}& a_{33}& a_{34}& & \\ & & \ddots & \ddots & \ddots \\ & & & a_{n-1n-2}& a_{n-1n-1}& a_{n-1n}\\ & & & & a_{nn-1}& a_{nn}\end{array}\right]$
a_{11} & a_{12} & & & & \\
a_{21} & a_{22} & a_{23} & & & \\
& a_{32} & a_{33} & a_{34} & & \\
& & \ddots & \ddots & \ddots \\
& & & a_{n-1n-2} & a_{n-1n-1} & a_{n-1n} \\
& & & & a_{nn-1} & a_{nn}
\end{bmatrix}

M=⎣⎢⎢⎢⎢⎢⎢⎡​a11​a21​​a12​a22​a32​​a23​a33​⋱​a34​⋱an−1n−2​​⋱an−1n−1​ann−1​​an−1n​ann​​⎦⎥⎥⎥⎥⎥⎥⎤​  对角矩阵也称带状矩阵，对于

n阶方阵

M中的任一元素

aij​，当

∣i−j∣>1时，有

aij​=0(1≤i,j≤n)，则称为三对角矩阵。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为0。
  三对角矩阵的压缩存储方式是将3条对角线上的元素按行优先的方式存放在一维数组中，且

a11​存放在

A[0]中。矩阵

M中3条对角线上的元素

aij​与一维数组

B中的下标对应关系如下：

k=2i+j−3  其中，

1≤i,j≤n,∣i−j∣≤1。

a11​ $a_{12}$

a12​ $a_{21}$

a21​ $a_{22}$

a22​ $a_{23}$

a23​ $\dots$

… $a_{n-1n}$

an−1n​ $a_{nn-1}$

ann−1​ $a_{nn}$

ann​

  如果知道三对角矩阵

M中的某个元素

aij​存放于一维数组

A的第

k个位置，则可得

i=⌊3k+1​+1⌋,j=k−2i+3。

3.4 稀疏矩阵

$M=\left[\begin{array}{ccccccccc}0& 0& 0& 0& 0& 3& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 4& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 11& 0\end{array}\right]$
0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 11 & 0 \\
\end{bmatrix}

M=⎣⎢⎢⎢⎢⎡​00400​00000​00000​00000​00000​30000​00000​000011​00000​⎦⎥⎥⎥⎥⎤​  在

m×n的矩阵

M中，有

t个元素不为0，令

δ=m×nt​，通常认为

δ≤0.05，我们就称矩阵

M为稀疏矩阵，

δ称为矩阵

M的稀疏因子。
  由于稀疏矩阵的零元素的分布没有规律，所以在压缩存储稀疏矩阵时，我们不仅要存储非零元素的值，还要存储其所在的行和列，即构成了一个三元组

(i,j,aij​)。将上述矩阵

M以行优先的方式存储：

i $j$

j $a_{ij}$

aij​

0
5
3

2
0
4

4
7
11

  矩阵的转置运算，即对于一个

m×n的矩阵

M，其转置矩阵

T是一个

n×m的矩阵，且

T(i,j)=M(j,i)，即行和列所在的位置进行互换。

T=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​000003000​000000000​400000000​000000000​0000000110​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​  转置矩阵

T也是个稀疏矩阵，其压缩存储方式为：

i $j$

j $a_{ij}$

aij​

0
2
4

5
0
3

7
4
11

  即行和列交换位置后，再按行优先的方式重新对三元组进行排序。除此之外，稀疏矩阵还可以用十字链表法进行存储，那什么是十字链表呢，这个等介绍到图的存储结构时再说。

原创：https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

关注我们小说电影免费看

关注我们，获取更多的全网素材资源，有趣有料！

120000+人已关注