数组是我们比较常接触的一种数据结构了，就我们所了解的，数组从一维到多维不等，由数组演变出来的另一概念，被称之为矩阵，但是其实质还是一种有序的序列。

1. 数组

---

数组的存储和寻址

数组可以是一维的，也可以是多维的，多维数组可以实现向一维数组的转换，根据不同的优先顺序，可以有不同的转换方案，但是为了方便，我们对数组的存储和寻址进行了相关的约定：

• 数组是以线性方式进行存储的。设有一个一维数组A[n]，其中每个数组元素的存储空间为C个字节，则数组第i个元素的首地址为A[0] + i x C，即Loc(A[i]) = Loc(A[0]) + i x C 其中Loc表示元素首地址。

• 多维数组按照行优先原则进行存储。即设有一个二维数组A[m][n]，其中每个数组元素占空间为C个字节，则数组元素A[i][j]的存储首地址为A[0][0] + i x n x C + j x C，即Loc(A[i][j]) = Loc(A[0][0] + (i x j x n) x C 。

一般所使用的C，C++，Java等语言均是按行优先原则，而MATLAB等语言则是按列优先存储。

接下来给出一维数组的实现。

class Array
{
    private:
        int size;  //数组大小
        int *list;  //指向数组第一个元素
    public:
        Array(int size = 0);
        Array(const Array &v);   //用于数组的复制
        ~Array() { delete[] list; }
        int ArraySize() { return size; }
        int & operator[] (int i)const;  //重载下标符
        Array & operator= (const Array &v)const;  //重载复制运算符
        Array & operator+ ()const;   //重载一元加法
        Array & operator+ (const Array &v)const;    //重载二元加法
        Array & operator- ()const;   //重载一元减法
        Array & operator- (const Array &v)const;   //重载二元减法
};

其中，数组的运算可以通过函数来实现，并不一定需要通过重载运算符来实现，这也说明，在编程时，方法不是主要的，只要知道最核心的思想，实现方法怎么顺手怎么来。

2. 矩阵

---

矩阵其实是一种比较特殊的二维数组，不过由于其特殊性，我们会单独为他做一些实现来简化工作。
矩阵在线性代数中会有专门的讲解，有很多的运算，很多的定义。矩阵的知识学着学着，就会让人怀疑人生，好在，不研究这东西，只需要会用就行。
普通矩阵的一种实现：

class Matrix
{
    private:
        int rows, cols;    //矩阵行和列
        int *element;    //矩阵中的元素
    public:
        Matrix(int r, int c);
        Matrix(const Matrix &m);    //用于复制的构造函数
        ~Matrix() { delete[] element; }
        int Rows()const { return rows; }
        int Columns()const { return cols; }
        int & operator() (int i, int j)const;    //重载下标操作符
        Matrix &operator+ ()const;
        Matrix &operator+ (const Matrix &m)const;
        Matrix &operator- ()const;
        Matrix &operator- (const Matrix &m)const;
        Matrix &operator* (const Matrix &m)const;
};

2.1 特殊矩阵

如果采用矩阵存储数据时，可能会出现部分位置空闲，元素重复等情况，会造成大量的空间浪费，如此一来便出现了一些特殊矩阵：

1. 对角矩阵
   在数学中规定，一个n x n维方阵，其非对角线上的元素均为0，就称这种矩阵为对角矩阵。
   通过定义，我们便可发现，一个n x n维对角矩阵，至多有n个非零元素，也即只需存储n个对角元素的信息。
   这种情况，我们可以通过一维数组进行存储，通过相应的运算，决定对角元素所在位置。

但这相应的运算其实可以是A[i]存储矩阵A[i][i]的元素。

2. 三角矩阵
   三角矩阵又可细分为上三角矩阵和下三角矩阵。
   在数学中规定，一个n x n维方阵，其中对于任意i<j的元素，都有M(i,j)=0，即可称为下三角矩阵，反之则为下三角矩阵。
   对于三角矩阵的存储，也是通过相应的运算，将矩阵中的元素映射到一维数组中。

3. 对称矩阵
   规定，n x n维方阵中任意i ≠ j，均有M(i, j) = M(j, i)，就称该矩阵为对称矩阵。
   由定义可以看出，这种矩阵对称，则意味着左右对称，上下对称，如此，我们可以将其转化成一个三角矩阵进行存储，而由于在对称矩阵中，上三角和下三角的内容均相同，故而只需存储上三角或下三角的内容即可。
   至于关系映射，则与所选的三角位置有关。

4. 稀疏矩阵
   规定，在一个m x n的矩阵中，其中非零元素的个数远小于零元素的个数，且其分布无规律，即称稀疏矩阵
   这种矩阵和之前三种不同，其中元素的分布是没有规律的，所以不可以用映射公式进行矩阵到一维数组的转换，但是由于其存储的有效信息（非零元素）较少，所以可以直接对有效信息进行存储，用到的方式，我们称之为三元组表，其后会介绍到。

2.2 三元组表

稀疏矩阵不能使用普通的矩阵进行存储，于是我们想到可以直接存储稀疏矩阵中的有效信息，进而诞生了三元组表。
三元组表是由结点构成，每一个结点又是由一个结构体构成，该结构体有row，col，value三个域，存储元素的行列值信息。

三元组表

上图为三元组表的内容。

三元组表的实现为：

struct Trituple
{
    int row, col;
    int value;
};

class SparseMatrix
{
    private:
        int rows, cols, count;   //稀疏矩阵的行列数，以及非零元素的个数
        Trituple *smArray;    //存储三元组表的数组
        int MaxTerm;  //数组的大小
    public:
        SparseMatrix(int Mrows, int Mcols);
        SparseMatrix Transpose();   //求转置矩阵
        /* 与普通矩阵的其他操作相同 */
};

2.3 十字链表

稀疏矩阵的另一种实现是十字链表，这种十字链表是由结点构成，结点中的内容为，左邻非零元素指针，上邻非零元素的指针，以及行列值的信息。

十字链表的结点

听起来这种存储方式要比三元组表麻烦，实际上也确实如此，不过这种存储方式奉行的是牺牲空间换时间原则，因此查找起来速度还是很快的。

这里说说三元组表的缺点，三元组表无论是添加或是删除矩阵中的非零元素，又或是说对矩阵实施一些操作（如运算），都会引起矩阵中非零元素的个数和位置变化，这种变化会使三元组表大量的结点进行移动，效率较低，使用链接存储则避免了这些问题。