数组是我们比较常接触的一种数据结构了,就我们所了解的,数组从一维到多维不等,由数组演变出来的另一概念,被称之为矩阵,但是其实质还是一种有序的序列。
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 特殊矩阵
如果采用矩阵存储数据时,可能会出现部分位置空闲,元素重复等情况,会造成大量的空间浪费,如此一来便出现了一些特殊矩阵:
- 对角矩阵
在数学中规定,一个n x n维方阵,其非对角线上的元素均为0,就称这种矩阵为对角矩阵。
通过定义,我们便可发现,一个n x n维对角矩阵,至多有n个非零元素,也即只需存储n个对角元素的信息。
这种情况,我们可以通过一维数组进行存储,通过相应的运算,决定对角元素所在位置。
但这相应的运算其实可以是A[i]存储矩阵A[i][i]的元素。
-
三角矩阵
三角矩阵又可细分为上三角矩阵和下三角矩阵。
在数学中规定,一个n x n维方阵,其中对于任意i<j的元素,都有M(i,j)=0,即可称为下三角矩阵,反之则为下三角矩阵。
对于三角矩阵的存储,也是通过相应的运算,将矩阵中的元素映射到一维数组中。 -
对称矩阵
规定,n x n维方阵中任意i ≠ j,均有M(i, j) = M(j, i),就称该矩阵为对称矩阵。
由定义可以看出,这种矩阵对称,则意味着左右对称,上下对称,如此,我们可以将其转化成一个三角矩阵进行存储,而由于在对称矩阵中,上三角和下三角的内容均相同,故而只需存储上三角或下三角的内容即可。
至于关系映射,则与所选的三角位置有关。 -
稀疏矩阵
规定,在一个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 十字链表
稀疏矩阵的另一种实现是十字链表,这种十字链表是由结点构成,结点中的内容为,左邻非零元素指针,上邻非零元素的指针,以及行列值的信息。
十字链表的结点
听起来这种存储方式要比三元组表麻烦,实际上也确实如此,不过这种存储方式奉行的是牺牲空间换时间原则,因此查找起来速度还是很快的。
这里说说三元组表的缺点,三元组表无论是添加或是删除矩阵中的非零元素,又或是说对矩阵实施一些操作(如运算),都会引起矩阵中非零元素的个数和位置变化,这种变化会使三元组表大量的结点进行移动,效率较低,使用链接存储则避免了这些问题。
网友评论