数据结构之数组、矩阵和广义表

  数据结构是程序设计的重要基础，它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。

  数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的
逻辑结构，数据元素及元素之间关系的存储称为
存储结构(或物理结构)。数据结构按照逻辑关系的不同分为
线性结构和
非线性结构两大类，其中，非线性结构又可分为树结构和图结构。

  线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”。

  数组与广义表可看作是线性表的推广，其特点是数据元素仍然是一个表。这里讨论多维数组的逻辑结构和存储结构，特殊矩阵和矩阵的压缩存储，广义表的逻辑结构、存储结构和基本运算。

1、数组

1.1、数组的定义及基本运算

  （1）数组的定义
  数组是定长线性表在维数上的扩展，即线性表中的元素又是一个线性表。n 维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。
  设有 n 维数组 A[b₁,b₂,…,b_n]，其每一维的下界都为 1，b_i是第 i 维的上界。从数据结构的逻辑关系角度来看，A 中的每个元素 A[j₁,j₂,…,j_n] (1≤j_i≤b_i) 都被 n 个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，它仍是线性的。
  以二维数组 4[m,n]为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。

  A 可看成一个行向量形式的线性表：

A

m

,

n

=

[

[

a

11

a

12

⋅

⋅

⋅

a

1

n

]

,

[

a

21

a

22

⋅

⋅

⋅

a

2

n

]

,

⋅

⋅

⋅

,

[

a

m

1

a

m

2

⋅

⋅

⋅

a

m

n

]

]

A_{m,n}=[ [a_{11} a_{12} ···a_{1n}],[a_{21} a_{22} ··· a_{2n}] ,···,[a_{m1}a_{m2}···a_{mn}]]

Am,n​=[[a11​a12​⋅⋅⋅a1n​],[a21​a22​⋅⋅⋅a2n​],⋅⋅⋅,[am1​am2​⋅⋅⋅amn​]]
  或列向量形式的线性表：

A

m

,

n

=

[

[

a

11

a

21

⋅

⋅

⋅

a

m

1

]

,

[

a

12

a

22

⋅

⋅

⋅

a

m

2

]

,

⋅

⋅

⋅

,

[

a

1

n

a

2

n

⋅

⋅

⋅

a

m

n

]

]

A_{m,n}=[ [a_{11} a_{21} ···a_{m1}],[a_{12} a_{22} ··· a_{m2}] ,···,[a_{1n}a_{2n}···a_{mn}]]

Am,n​=[[a11​a21​⋅⋅⋅am1​],[a12​a22​⋅⋅⋅am2​],⋅⋅⋅,[a1n​a2n​⋅⋅⋅amn​]]
  数组结构的特点如下。
  ① 数据元素数目固定，一旦定义了一个数组结构，就不再有元素个数的增减变化。
  ② 数据元素具有相同的类型。
  ③ 数据元素的下标关系具有上下界的约束且下标有序。
  （2）数组的两个基本运算
  ① 给定一组下标，存取相应的数据元素。
  ② 给定一组下标，修改相应的数据元素中某个数据项的值。
  所有的高级程序设计语言都提供了数组类型。实际上，在程序语言中把数组看成是具有共同名字的同一类型的多个变量的集合。

1.2、数组的顺序存储

  数组一般不做插入和删除运算，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
  二维数组的存储结构可分为以行为主序和以列为主序的两种方法，如下图所示

  设每个数据元素占用 L 个单元，m、n 为数组的行数和列数，Loc(a₁₁)表示元素a₁₁的地址，那么以行为主序优先存储的地址计算公式为

L

o

c

(

a

i

j

)

=

L

o

c

(

a

11

)

+

(

(

i

−

1

)

×

n

+

(

j

−

1

)

)

×

L

Loc(a_{ij})=Loc(a_{11})+((i-1)×n+(j-1))×L

Loc(aij​)=Loc(a11​)+((i−1)×n+(j−1))×L
  同理，以列为主序优先存储的地址计算公式为

L

o

c

(

a

i

j

)

=

L

o

c

(

a

11

)

+

(

(

j

−

1

)

×

n

+

(

i

−

1

)

)

×

L

Loc(a_{ij})=Loc(a_{11})+((j-1)×n+(i-1))×L

Loc(aij​)=Loc(a11​)+((j−1)×n+(i−1))×L
  推广至多维数组，在按下标顺序存储时，先排最右的下标，从右向左直到最左下标，而逆下标顺序则正好相反。

2、矩阵

  矩阵是很多科学与工程计算领域研究的数学对象。在数据结构中，主要讨论如何在节省存储空间的情况下使矩阵的各种运算能高效地进行。
  在一些矩阵中，存在很多值相同的元素或者是0元素。为了节省存储空间，可以对这类矩阵进行压缩存储，即为多个值相同的元素只分配一个存储单元，对0不分配存储单元。假如值相同的元素或0元素在矩阵中的分布有一定的规律，则称此类矩阵为特殊矩阵，否则称其为稀疏矩阵。

2.1、特殊矩阵

  若矩阵中元素(或非0元素)的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非0元素的分布有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非0元素在矩阵中的位置与其在一维数组中的位置之间的对应关系。
  若矩阵 A_n×n中的元素特点为 a_ij=a_ji(1≤i，j≤n)，则称之为n阶对称矩阵。
  若对称矩阵中的每一对元素仅占用一个存储单元，那么可将 n²个元素压缩存储到能存放n(n+1)/2 个元素的存储空间中。不失一般性，以行为主序存储下三角(包括对角线)中的元素。假设以一维数组 B[(n+1)/2]作为 n 阶对称矩阵 A 中元素的存储空间，则 B[k] (1≤k<n(n+1)/2)与矩阵元素 a_ij(a_ji) 之间存在着一一对应的关系，如下所示。

  对角矩阵是指矩阵中的非 0 元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为 0。一个 n 阶的三对角矩阵如下图 所示。

  若以行为主序将n阶三对角矩阵A_n×n的非0元素a_ij存储在一维数组 B[k] (1≤k≤3×n-2)中，则元素位置之间的对应关系为

k

=

3

×

(

i

−

1

)

−

1

+

j

−

i

+

1

+

1

=

2

i

+

j

−

2

(

1

≤

i

,

j

≤

n

)

k=3×(i-1)-1+j-i+1+1=2i+j-2 (1≤i, j≤n)

k=3×(i−1)−1+j−i+1+1=2i+j−2(1≤i,j≤n)
  其他特殊矩阵可做类似的推算，这里不再一一说明。

2.2、稀疏矩阵

  在一个矩阵中，若非 0 元素的个数远远少于 0 元素的个数，且非 0元素的分布没有规律，则称之为稀疏矩阵。对于稀疏矩阵，存储非 0 元素时必须同时存储其位置(即行号和列号)，所以三元组 (i，j，a_ij)可唯一确定矩阵 A 中的一个元素。由此，一个稀疏矩阵可由表示非 0 元素的三元组及其行、列数唯一确定。下图 所示的是一个 6 行 7 列的稀疏矩阵，其三元组表为((1,2,12),(1,3,9),(3,1,-3), (3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))。

  稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

3、广义表

  广义表是线性表的推广，是由 0 个或多个单元素或子表组成的有限序列。
  广义表与线性表的区别在于: 线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表。
  广义表一般记为

L

S

=

(

α

1

,

α

2

,

⋅

⋅

⋅

,

a

n

)

LS=(α_1,α_2,···,a_n)

LS=(α1​,α2​,⋅⋅⋅,an​)
  其中，α_j(1 ≤ i ≤ n)既可以是单个元素，又可以是广义表，分别称为原子和子表。
  广义表的长度是指广义表中元素的个数。广义表的深度是指广义表展开后所含的括号的最大层数。

3.1、广义表的基本操作

  与线性表类似，广义表也有查找、插入和删除等操作。由于广义表的结构较复杂，其各种运算的实现也不如线性表简单，这里只讨论两个重要的运算。
  （1）取表头 head(LS)。非空广义表 LS 的第一个元素称为表头，它可以是一个单元素，也可以是一个子表。
  （2） 取表尾 tail(LS)。在非空广义表中，除表头元素之外，由其余元素所构成的表称为表尾。非空广义表的表尾必定是一个表。

3.2、广义表的特点

  （1）广义表可以是多层次的结构，因为广义表的元素可以是子表，而子表的元素还可以是子表。
  （2）广义表中的元素可以是已经定义的广义表的名字，所以一个广义表可被其他广义表所共享。
  （3）广义表可以是一个递归的表，即广义表中的元素也可以是本广义表的名字。

3.3、广义表的存储结构

  由于广义表中的元素本身又可以具有结构，它是一种带有层次的非线性结构，因此难以用顺序存储结构表示，通常采用链式存储结构。由上面的讨论可知，若广义表不空，则可分解为表头和表尾两部分。反之，一对确定的表头和表尾可唯一确定一个广义表。针对原子和子表可分别设计不同的结点结构，如下图 所示。

  对于广义表 LS=(a,(b,c,d))，其链式存储结构如下图所示。