5-数组

数组其实是比较熟悉的一种数据类型，但其实数组本身也是一种数据结构。

前面 讨论的线性表结构的顺序存储结构都是借用一维数组来实现的，

一维数组是一种顺序表结构，多维数组是一种特殊的线性结构，是线性表的推广。

数组是用于储存多个相同类型数据的集合。

1.数组的顺序存储结构

由于数组可以是多维的，而顺序存储结构是一维的，因此数组中数据的存储要制定一个先后次序。

通常，数组中数据的存储有两种先后存储方式：

①以行序为主（先行后序）：按照列号从小到大的顺序，依次存储每一行的元素。

②以列序为主（先列后行）：按照行号从小到大的顺序，依次存储每一列的元素

假设有一个 m 行 n 列 的二维数组，每个元素占S个存储单元

按行优先存储的查找方法：

Loc(i,j) = Loc(1,1) + [ (i-1) *n + (j-1) ]*S

按列优先存储的查找方法：

Loc(i,j) = Loc(1,1) + [ (j-1) *m + (i-1) ]*S

2.特殊矩阵的压缩

这里所说的特殊矩阵，主要分为以下两类：

含有大量相同数据元素的矩阵，比如对称矩阵；

含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

我们可以使用一维数组存储对称矩阵。

由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据，

每一对对称元素共享一个存储空间。

则对于原来就在下三角区域的元素，(i>=j), 看成按行存储，第 i 行上 有 i个元素

Loc(i,j) = Loc(1,1) + i*(i-1)/2 + (j-1)

则令 k= i*(i-1)/2 + (j-1) ，这就是存储下三角元素的一维数组的索引

对原来就在上三角区域的元素( i< j)， 看成按列存储， 第 j 列 上有 j 个元素

Loc(i,j) = Loc(1,1) + j *(j-1)/2 + (i-1)

则令 k=j *(j-1)/2 + (i-1)，这就是存储上三角元素的一维数组的索引

上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

3、稀疏矩阵

稀疏矩阵是指其中有大量 0 元素，可以只保存这些非零元素以节省存储空间。

①采用三元组存储法：

保存非零元素的 行值，列值， 和元素本身值。

例如有一个4 x 5的矩阵A 则对应的压缩矩阵为：

1 0 0 0 0 4，5， 6， //第一行一定为 m ， n ， 非零元素个数

0 0 12 0 0 0，0 ， 1

0 3 0 0 0 -----》 1， 2 ，12

2 0 0 0 0 2 ，1 ，3

3 ，0 ，2

如此一来原本要20个元素，现在只需要存储15个元素，我这里只举了个简单的例子，当稀疏矩阵规模更大时，节约内存更明显。每行一定是3个元素，这可以当成一个结点保存下来，每个结点 当成一个元素存在顺序表里，所以称为三元组法，相应的顺序表称为三元组顺序表。

②行逻辑链接的顺序表

三元组顺序表每次提取指定元素都需要遍历整个数组，运行效率很低。

另一种存储矩阵的方法——行逻辑链接的顺序表。它可以看作是三元组顺序表的升级版，

即在三元组顺序表的基础上改善了提取数据的效率。

它比三元组多了一个 用于记录矩阵中每行第一个非 0 元素在三元组中的存储位置的一维数组 rpos， 以上例举例

rops [1, 2, 3, 4] 这就是每行第一个非零元素，在三元组中出现在第几个结点，

我这里例子里，由于原矩阵每行只有一个非零元素，所以没有太大的感觉。

此时，如果想从行逻辑链接的顺序表（三元组）中提取元素，则可以借助 rpos 数组提高遍历数组的效率，

③十字链表法

对于压缩存储稀疏矩阵，无论是使用三元组顺序表，还是使用行逻辑链接的顺序表，归根结底是使用数组存储稀疏矩阵。介于数组 "不利于插入和删除数据" 的特点，以上两种压缩存储方式都不适合解决类似 "向矩阵中添加或删除非 0 元素" 的问题。

使用十字链表压缩存储稀疏矩阵时，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组（rhead），所有列链表的表头存储到另一个数组（chead）中。

各个链表中节点的结构应如图：

结点的C语言代码

typedef struct OLNode{

int i, j; //元素的行标和列标

int data; //元素的值

struct OLNode * row ,*column;//两个指针域

}OLNode;

十字链表结构的 C 语言代码

typedef struct

{

OLink *rhead, *chead; //行和列链表头指针

int m , n , t; //矩阵的行数,列数和非零元的个数

}CrossList;