【python数据结构】多维数组_python多维数组

在程序设计语言中大都提供了数组作为构造数据类型，本章重点讨论数组以及特殊矩阵的存储与寻址。

目录

数组

数组的定义

数组的特点

数组的基本操作

数组的存储结构与寻址

一维数组

 二维数组

按行优先存储的寻址

矩阵的压缩存储

特殊矩阵和稀疏矩阵

 压缩存储的基本思想

对称矩阵

三角矩阵

下三角矩阵：

 上三角矩阵：

对角矩阵

 稀疏矩阵

 转置操作：

十字链表

 本章总结

---

数组

数组的定义

数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为 n 维数组。

如上图表示的二维数组中，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。 

数组的特点

• 元素本身可以具有某种结构，属于同一数据类型；
• 数组是一个具有固定格式和数量的数据集合。

数组的基本操作

• 读操作：给定一组下标，读出对应的数组元素；

• 写操作：给定一组下标，存储或修改与其相对应的数组元素。

读操作和写操作本质上只对应一种操作——寻址

在数组上一般不能做插入和删除元素的操作，所以不用预留空间，适合采用顺序存储。

数组的存储结构与寻址

一维数组

设一维数组的下标的范围为闭区间［l，h］，每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定：

Loc(ai)＝Loc(al)＋(i－l)×c

 二维数组

常用的映射方法有两种：

• 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。
• 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

按行优先存储的寻址

 

aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数

=(i -l1)×(h2 -l2＋1)＋(j -l2)

矩阵的压缩存储

特殊矩阵和稀疏矩阵

 特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律：对称矩阵、三角矩阵、对角矩阵 …

 稀疏矩阵：矩阵中有很多零元素。

 压缩存储的基本思想

  ⑴ 为多个值相同的元素只分配一个存储空间；

  ⑵ 对零元素不分配存储空间。

对称矩阵

压缩存储：存储下三角部分的元素。由于下三角中共有n×(n+1)/2个元素，可将这些元素按行存储到一个数组SA[n×(n+1)/2]中。

 

aij在一维数组中的序号=阴影部分的面积=[(i-1)(i-1)+(i-1)]/2 + j  =  i×(i-1)/2+ j

∵一维数组下标从0开始  ∴aij在一维数组中的下标  k= i×(i-1)/2+ j-1

对于下三角中的元素aij（i≥j），在数组SA中的下标k与i、j的关系为：k＝i×(i-1)/2＋j -1。

上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j-1)/2＋i -1 

三角矩阵

压缩存储：只存储上三角（或下三角）部分的元素。

下三角矩阵：

矩阵中任一元素aij在数组中的下标k与i、j的对应关系：

 上三角矩阵：

矩阵中任一元素aij在数组中的下标k与i、j的对应关系：

对角矩阵

所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。  

 寻址计算方法：

元素aij在一维数组中的序号 =2 + 3(i－2)+( j－i + 2) =2i+ j -2         

∵一维数组下标从0开始    ∴元素aij在一维数组中的下标   k = 2i+ j -3

 

 

 稀疏矩阵

由于稀疏矩阵中的非零元素的分布没有规律，因此将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)——三元组

三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。

 转置操作：

 算法1：直接取，顺序存（时间复杂度较高）

在A的三元组顺序表中依次找第0列、第1列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。

伪代码：

1. 设置转置后矩阵B的行数、列数和非零元个数；

2. 在B中设置初始存储位置pb；

3. for (col=最小列号; col<=最大列号; col++)

    3.1 在A中查找列号为col的三元组；

    3.2 交换其行号和列号，存入B中pb位置；

    3.3 pb++；

  算法2：顺序取，直接存。即在A中依次取三元组，交换其行号和列号放到B 中适当位置。

引入两个数组作为辅助数据结构：

num[nu]：存储矩阵A中某列的非零元素的个数；

cpot[nu]：初值表示矩阵A中某列的第一个非零元素在B中的位置。

num与cpot存在如下递推关系：

cpot[0]=0；         cpot[col]=cpot[col-1]+num[col-1]；   1≤col＜nu

将矩阵A中col列元素存放在B中下标为cpot[col]的位置

伪代码：

1. 设置转置后矩阵B的行数、列数和非零元素的个数；

2. 计算A中每一列的非零元素个数；

3. 计算A中每一列的第一个非零元素在B中的下标；

4. 依次取A中的每一个非零元素对应的三元组；

    4.1 确定该元素在B中的下标pb；

    4.2 将该元素的行号列号交换后存入B中pb的位置；

    4.3 预置该元素所在列的下一个元素的存放位置；

十字链表

采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：

row：存储非零元素的行号

col：存储非零元素的列号

item：存储非零元素的值

right：指针域，指向同一行中的下一个三元组

down：指针域，指向同一列中的下一个三元组

 

稀疏矩阵的压缩存储——十字链表的具体存储方法 

（1） 每一行的非零元素按其列号由right域链成一个带头结点的循环链表。

（2）每一列的非零元素按其行号由down域链成一个带头结点的循环链表。

（3）由于各行列链表头结点row域、col域和item域均为空，行链表头结点只用right域，列链表头结点只用down域，故这两组链表头结点可以合用。

（4）为了实现对某一行（或某一列）头指针的快速查找，将指向这些头结点的头指针存在一个数组中。

 本章总结