数据结构串和数组(二)（数据结构串的概念）

数组的基本概念

数组是一个二元组（idx，value）的集合，对每个idx，都有一个value值与之对应。idx称为下标，可以由一个整数、两个整数或多个整数构成，下标含有d（d≥1）个整数称为维数是d。

数组按维数分为一维、二维和多维数组。

一维数组A是n（n>1）个相同类型元素a0，a1，…，an-1构成的有限序列，其逻辑表示为A=（a0，a1，…，an-1），其中，A是数组名，ai（0≤i≤n-1）是数组A中序号为i的元素。

一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。

以此类推

数组具有以下特点

（1）数组中各元素都具有统一的数据类型。

（2）d（d≥1）维数组中的非边界元素具有d个前驱元素和d个后继元素。

（3）数组维数确定后，数据元素个数和元素之间的关系不再发生改变，特别适合于顺序存储。

（4）每个有意义的下标都存在一个与其相对应的数组元素值。

d维数组抽象数据类型

数组的主要操作是存取元素值，没有插入和删除操作，所以数组通常采用顺序存储方式来实现。

一维数组

一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中。

其起始地址为第一个元素a0的地址即LOC(a0)。

假设每个数据元素占用k个存储单元。

则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出

d维数组

以m行n列的二维数组Am×n=(ai，j)为例讨论（二维数组也称为矩阵）。

按行优先存储

假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。对于元素ai，j：

ai,j前面有0～i-1共i行，每行n个元素，共有i×n个元素。

在第i行中前面有a[i,0..j-1]，共j个元素。

合起来，ai,j前面有i×n+j个元素。

按列优先存储

假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。对于元素ai，j：

ai,j前面有0～j-1共j列，每列m个元素，共有j×m个元素。

在第j列中前面有a[0..i-1,j]，共i个元素。

合起来，ai,j前面有j×m+i个元素。则：

例子：设有二维数组a[1..50，1..80]，其a[1][1]元素的地址为2000，每个元素占2个存储单元，若按行优先存储，则元素a[45][68]的存储地址为多少?若按列优先存储，则元素a[45][68]的存储地址为多少？

按行优先存储

元素a[45][68]前面有1～44行，每行80个元素，计44×80个元素。

在第45行中，元素a[45][68]前面有a[45][1..67]计67个元素，这样元素a[45][68]前面存储的元素个数=44×80+67。

LOC(a[45][68])=2000+(44×80+67)×2=9174。

例子：设有二维数组a[1..50，1..80]，其a[1][1]元素的地址为2000，每个元素占2个存储单元，若按行优先存储，则元素a[45][68]的存储地址为多少?若按列优先存储，则元素a[45][68]的存储地址为多少？

按列优先存储

元素a[45][68]前面有1～67列，每列50个元素，计67×50个元素。

在第68列中，元素a[45][68]前面有a[1..44][68]计44个元素，这样元素a[45][68]前面存储的元素个数=67×50+44。

LOC(a[45][68])=2000+(67×50+44)×2=8788。

特殊矩阵的压缩存储

对称矩阵的压缩存储

三角矩阵的压缩存储

对角矩阵的压缩存储

稀疏矩阵

一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即s<<t时，称该矩阵为稀疏矩阵。

例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。

稀疏矩阵和特殊矩阵的不同点：

特殊矩阵的特殊元素（值相同元素、常量元素）分布有规律。

稀疏矩阵的特殊元素（非0元素）分布没有规律。

稀疏矩阵的三元组表示

三元组表示中每个元素的类定义如下：

设计稀疏矩阵三元组存储结构类TupClass如下：

TupClass类中包含如下基本运算方法：

其中，data列表用于存放稀疏矩阵中所有非零元素，通常按行优先顺序排列。这种有序结构可简化大多数稀疏矩阵运算算法。

稀疏矩阵的十字链表表示

每个非零元素对应一个结点

每行的所有结点链起来构成一个带行头结点的循环单链表。以h[i]（0≤i≤m-1）作为第i行的头结点。

每列的所有结点链起来构成一个带列头结点的循环单链表。 以h[i]（0≤i≤m-1）作为第i列的头结点。

行、列头结点可以共享

增加一个总头结点，并把所有行、列头结点链起来构成一个循环单链表

为了统一，设计结点类型如下：