数组和矩阵

作者: 贪婪的君子 | 来源:发表于2017-07-11 15:06 被阅读353次

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

    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]的元素。

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

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

    3. 稀疏矩阵
      规定,在一个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 十字链表

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


    十字链表的结点

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

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

    相关文章

      网友评论

        本文标题:数组和矩阵

        本文链接:https://www.haomeiwen.com/subject/gykmhxtx.html