Python描述数据结构之数组和特殊矩阵篇

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

前言

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

1. 基本概念

  数组是由

n(n1)n(n \geq 1)

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

nn

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

方法 功能

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

xx

x

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

copy()
返回列表的副本

count(x)
返回列表中元素

xx

x的个数

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

index(x)
返回元素

xx

x的第一个索引

insert(index, x)
在指定位置

indexindex

index添加元素

xx

x

pop(index)
删除指定位置

indexindex

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

remove(x)
删除指定元素

xx

x

reverse()
反转列表

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

keykey

key指定排序标准的函数

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

2. 存储方式

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

M=[a11a12a13a21a22a23]M=\begin{bmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23}
\end{bmatrix}

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

MM

M,按行优先方式在内存中的存储形式为:

Python描述数据结构之数组和特殊矩阵篇
  对于上述矩阵

MM

M,按列优先方式在内存中的存储形式为:

Python描述数据结构之数组和特殊矩阵篇

3. 特殊矩阵

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

3.1 对称矩阵

M=[a11a12a1na21a22a2nan1an2ann]M=\begin{bmatrix}
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​​⎦⎥⎥⎥⎤​  

nn

n阶矩阵

MM

M中的任意一个元素

aija_{ij}

aij​都有

aij=aji(1i,jn)a_{ij}=a_{ji}(1\leq i,j\leq n)

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

nn

n阶矩阵

MM

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

(i<j)(i<j)

(i<j)、主对角线

(i=j)(i=j)

(i=j)和下三角区

(i>j)(i>j)

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

n2n^2

n2个元素压缩存储到

n(n+1)2\frac {n(n+1)} {2}

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

AA

A来压缩存储矩阵

MM

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

A[k]A[k]

A[k]与矩阵

MM

M中的元素

aija_{ij}

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

k={i(i1)2+j1,ij,线j(j1)2+i1,i<j,k=\begin{cases}
\frac {i(i-1)} {2} +j-1, & i \geq j,即下三角区和主对角线\\
\\
\frac {j(j-1)} {2} +i-1, & i < j,即上三角区
\end{cases}

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

(i,j)(i,j)

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

AA

A中找到矩阵

MM

M的元素

aija_{ij}

aij​,同理,对所有的

k=0,1,2,,n(n+1)21k=0,1,2,\dots,\frac {n(n+1)} {2}-1

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

AA

A中的元素在矩阵

MM

M中的位置

(i,j)(i,j)

(i,j)。

kk

k 0 1 2 3 \dots

n(n+1)21\frac {n(n+1)} {2}-1

2n(n+1)​−1 aija_{ij}

aij​

a11a_{11}

a11​

a21a_{21}

a21​

a22a_{22}

a22​

a31a_{31}

a31​

\dots

anna_{nn}

ann​

  上面的

kk

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

\dots

…,第

i1i-1

i−1行有

i1i-1

i−1个元素,第

ii

i行有

j1j-1

j−1个元素

(ai1,ai2,,aij1)(a_{i1},a_{i2},\dots,a_{ij-1})

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

k=1+2+3++(i1)+(j1)=i(i1)2+j1k=1+2+3+\dots+(i-1)+(j-1)=\frac {i(i-1)} {2} +j-1

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

3.2 三角矩阵

M=[a11a21a22an1an2ann]M=[a11a12a1na22a2nann]M=\begin{bmatrix}
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​​⎦⎥⎥⎥⎤​  下三角矩阵中,上三角区的所有元素均为同一常量;上三角矩阵中,下三角区的所有元素均为同一常量。它们的压缩存储方式同对称矩阵是一样的,不同之处在于存储完下三角区和主对角线上的元素之后,紧接着要存储对角线上方的常量,所以需要

n(n+1)2+1\frac {n(n+1)} {2}+1

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

k={i(i1)2+j1,ij,线n(n+1)2,i<j,k=\begin{cases}
\frac {i(i-1)} {2} +j-1, & i \geq j,即下三角区和主对角线\\
\\
\frac {n(n+1)} {2}, & i < j,即上三角区
\end{cases}

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

kk

k 0 1 2 3 \dots

n(n+1)21\frac {n(n+1)} {2}-1

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

2n(n+1)​ aija_{ij}

aij​

a11a_{11}

a11​

a21a_{21}

a21​

a22a_{22}

a22​

a31a_{31}

a31​

\dots

anna_{nn}

ann​

cc

c

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

kk

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

nn

n个元素,第2行有

n1n-1

n−1个元素,第3行有

n2n-2

n−2个元素,

\dots

…,第

i1i-1

i−1行有

ni+2n-i+2

n−i+2个元素,第

ii

i行有

jij-i

j−i个元素,所以

k=n+(n1)+(n1)++(ni+2)+(ji)=(i1)(2ni+2)2+jik=n+(n-1)+(n-1)+\dots+(n-i+2)+(j-i)=\frac {(i-1)(2n-i+2)} {2}+j-i

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

3.3 三对角矩阵

M=[a11a12a21a22a23a32a33a34an1n2an1n1an1nann1ann]M=\begin{bmatrix}
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​​⎦⎥⎥⎥⎥⎥⎥⎤​  对角矩阵也称带状矩阵,对于

nn

n阶方阵

MM

M中的任一元素

aija_{ij}

aij​,当

ij>1|i-j|>1

∣i−j∣>1时,有

aij=0(1i,jn)a_{ij}=0(1\leq i,j\leq n)

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

a11a_{11}

a11​存放在

A[0]A[0]

A[0]中。矩阵

MM

M中3条对角线上的元素

aija_{ij}

aij​与一维数组

BB

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

k=2i+j3k=2i+j-3

k=2i+j−3  其中,

1i,jn,ij11\leq i,j\leq n,|i-j|\leq1

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

a11a_{11}

a11​ a12a_{12}

a12​ a21a_{21}

a21​ a22a_{22}

a22​ a23a_{23}

a23​ \dots

an1na_{n-1n}

an−1n​ ann1a_{nn-1}

ann−1​ anna_{nn}

ann​

  如果知道三对角矩阵

MM

M中的某个元素

aija_{ij}

aij​存放于一维数组

AA

A的第

kk

k个位置,则可得

i=k+13+1,j=k2i+3i=\lfloor \frac {k+1} {3} + 1\rfloor,j=k-2i+3

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

3.4 稀疏矩阵

M=[0000030000000000004000000000000000000000000110]M=\begin{bmatrix}
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×nm\times n

m×n的矩阵

MM

M中,有

tt

t个元素不为0,令

δ=tm×n\delta =\frac {t} {m\times n}

δ=m×nt​,通常认为

δ0.05\delta \leq0.05

δ≤0.05,我们就称矩阵

MM

M为稀疏矩阵,

δ\delta

δ称为矩阵

MM

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

(i,j,aij)(i,j,a_{ij})

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

MM

M以行优先的方式存储:

ii

i jj

j aija_{ij}

aij​

0
5
3

2
0
4

4
7
11

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

m×nm\times n

m×n的矩阵

MM

M,其转置矩阵

TT

T是一个

n×mn\times m

n×m的矩阵,且

T(i,j)=M(j,i)T(i,j)=M(j,i)

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

T=[0040000000000000000000000300000000000001100000]T=\begin{bmatrix}
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 \\
3 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 11 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}

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

TT

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

ii

i jj

j aija_{ij}

aij​

0
2
4

5
0
3

7
4
11

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

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

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

Python描述数据结构之数组和特殊矩阵篇

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » Python描述数据结构之数组和特殊矩阵篇
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏