数据结构(考纲总结):三、数组

三、数组

1.一维数组和二维数组的存储;

1.1 数组的定义

数组是下标与值组成的偶对的有穷集合。

1.2 数组的基本操作

  1. 给定一组下标,存取或修改相应元素的值。
  2. 给定一组下标,检索相应的数组元素。
  3. 对数组元素进行排序。

1.3 一维数组 A[1:n]

1.3.1 一维数组的定义:

$ A[1:n] = ( a_1, a_2, a_3, … , a_{n-1}, a_n ) $

1.3.2 一维数组的存储:

若已知每个元素占k个存储单元,并且第一个元素的存储地址为 $ LOC( a_1 ) $,则

$ LOC( a_i ) = LOC(a_1) + (i-1) * k $

1.3.3 一维数组的特点:

  1. 除了第一个元素外,其他每个元素有且 仅有一个直接前驱元素;
  2. 除了最后那个元素外,其他每个元素有 且仅有一个直接后继元素。

1.4 二维数组 A[1:m, 1:n]

1.4.1 二维数组的定义:

$ A[1:m, 1:n] = \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{pmatrix} $

1.4.2 二维数组的存储:

1.4.2.1 二维数组行序为主序分配方式

若已知每个元素占k个存储单元,并且第一个元素的存储地址 $ LOC(a_{11}) $,则

$ \begin{align} LOC(a_{ij}) & = LOC(a_{11}) + (i−1)*n*k + (j−1)*k \\ & = LOC(a_{11}) + [ (i−1)*n+(j−1) ]*k \end{align} $
1.4.2.2 二维数组列序为主序分配方式

若已知每个元素占k个存储单元,并且第一个元素的存储地址 $ LOC(a_{11}) $,则

$ \begin{align} LOC(a_{ij}) & = LOC(a_{11}) + (j−1)*m*k + (i−1)*k \\ & = LOC(a_{11}) + [ (j−1)*m+(i−1) ]*k \end{align} $

2.矩阵的压缩存储的基本概念;

所谓 压缩存储 是指为多个值相同的元素,或者位置分布有规律的元素分配尽可能少的存储空间,而对 0 元素一般情况下不分配存储空间。

3.对称矩阵、对角矩阵以及三角矩阵的压缩存储。

3.1 对称矩阵的压缩存储

3.1.1 对称矩阵的定义

一个 n 阶矩阵 A 的元素满足性质 $ a_{ij} = a_{ji} ,1 \le i,j \le n $ 则称矩阵 A 为 n 阶对称矩阵。

3.1.2 对称矩阵的压缩存储做法:

只需为每一对位置对称的元素分配一个单元即可。从而将 $ n^2 $ 个元素压缩到 $ n(n+1)/2 $ 个元素的存储空间中。
建立一维数组 $ LTA[0:n*(n+1)/2] $,其中任意元素 $ a_{ij} $ 与 $ LTA[k] $ 之间存在以下关系:

$ k = \begin{cases} {i*(i-1) \over 2} + j - 1, & { i \ge j } \\ {j*(j-1) \over 2} + i - 1, & { i \lt j }\end{cases} $

时,则有 $ a_{ij} = LTA[k] $。也就是说,对于任意一组下标值 $ ( i , j ) $ 均可以在 LTA 中找到矩阵 A 的元素 $ a_{ij} $;反之,对于所有的 $ k = 0, 1, 2, …, n*(n+1)/2-1 $,都能确定 $ LTA[k] $ 在矩阵 A 中的位置 $ ( i , j ) $。

3.2 对角矩阵的压缩存储

3.2.1 对角矩阵的定义

若一个矩阵中,值非 0 的元素对称地集中在主对角线两旁的一个带状区域中(该区域之外的元素都为0元素),称这样的矩阵为 对角矩阵 。

3.2.2 对角矩阵的压缩存储做法

对称矩阵的压缩存储方法同样也适用于对角矩阵。

以三对角矩阵为例。三对角矩阵一共有 $ 3n-2 $ 个非零元素。建立一维数组 $ LTB[0:3*n-3] $,其中任意元素 $ b_{ij} $ 与 $LTB[k] $ 之间存在以下关系:

$ k = 2*i*j - 3 $

时,则有 $ b_{ij} = LTB[k] $。反过来,对于所有的 $ k = 0, 1, 2, …, 3*n-3 $,都能确定 $LTB[k] $ 在矩阵 B 中的位置 $ ( i , j ) $。

3.3 三角矩阵的压缩存储

对称矩阵的压缩存储方式同样可以用于三角矩阵。

$ k = \begin{cases} {i*(i-1) \over 2} + j - 1, & { i \ge j ,下三角矩阵} \\ {j*(j-1) \over 2} + i - 1, & { i \le j,上三角矩阵}\end{cases} $
原创不易,随意打赏!
0%