稀疏矩阵的压缩存储

目录

稀疏矩阵

    ●定义

    ● 例:

    ●压缩策略:

    ● 约束:

    ● 方案:

● 定义存储结构

从二维矩阵创建其三元组表示

三元组元素赋值 : 执行A[i][j] = x 运算

输出三元组

复杂度分析:

---

稀疏矩阵

    ●定义

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

    ● 例:

        •一个100*100的矩阵,其中只有100个非零元素

    ●压缩策略:

        • 只存储非零元素,然后存放在表里

    ● 约束:

        • 稀疏矩阵中非零元素的分布没有任何规律,只是顺序遍历矩阵,然后存储

    ● 方案:

        •存储非零元素
        • 同时存储该非零元素所对应的行下标和列下标
        • 稀疏矩阵中的每一个非零元素由一个三元组(i,j,aij)唯一确定,稀疏矩阵中的
          所有非零元素构成三元组线性表
        • 说白了,就是矩阵里面元素太少,然后为了压缩存储空间,然后把矩阵里面的元素存放在        表里了
        • 查找的时候,遍历表即可

● 定义存储结构

//定义一个表的最大长度,视情况而定

#define MaxSize 100

//定义每个节点的数据结构
 

typedef struct
{
    int r;    //行号
    int c;    //列号
    ElemType d; //元素值
}TupNode;        //三元组定义

//定义存储节点的表的数据结构

typedef struct
{
	int rows;	//行数值
	int cols;	//列数值
	int nums;	//非零元素个数
	TupNode data[MaxSize];	//存储节点的数组
}TSMatrix;		//三元组顺序表的定义

    ● 约定 :data 域中表示的非零元素通常以行序为主序顺序排列----下标按行有序的存储结构
    ● 目标 : 简化运算,按顺序的话,容易找到元素的位置,方便插入和删除,寻找
 

从二维矩阵创建其三元组表示

    ● 算法: 以行序方式扫描二维矩阵 A,将其非零元素加入到三元组t

// 传入矩阵,传入三元组顺序表	
void CreateMat(TSMatrix &t, ElemType A[M][N])
{
	//接下来就是按顺序赋值罢了
	int i,j;
	t.rows = M;
	t.cols = N;
	//先定义成0,然后遍历到非零元素的话,数值加一
	t.nums = 0;
	//开始按行遍历
	for(i = 0;i
	{
		for(j = 0; j
		{
			if(A[i][j] != 0)	//只存储非零值
			{
				t.data[t.nums].r = i;
				t.data[t.nums].c = j;
				t.data[t.nums].d = A[i][j];
				t.nums++;
			}
		}
	}
}

---

将指定位置的元素赋值给变量: 执行 x = A[i][j]

//把矩阵执行位置的元素传出,指定的位置合法的话,如果不在表里,就是0,在表里,我们就开始遍历传出即可

//传入表,存储传出元素的x,坐标
bool Assign(TSMatrix t,ElemType &x,int i,int j)
{
	int k = 0;
	//验证坐标合法性
	if(i>=t.rows || j>=t.cols)
	{
		return false; //失败返回false
	}
	//合法则开启遍历模式
	//先遍历行,表数组位序增加,然后对比行,接着对比列即可
	while(kt.data[k].r)
	{
		k++;	//查找行
	}
	//如果我们找到行,接着找列
	//分开寻找,可以减少对比同一行的列
	while(kt.data[k].c)
	{
		k++;
	}
	//跳出时,如果符合,则返回值即可
	if(t.data[k].r == i && t.data[k].c == j)
	{
		x = t.data[k].d;	//传入对应的值
	}
	else
	{
		x = 0;	//没找到,说明是零元素
	}
	return true;
}

三元组元素赋值 : 执行A[i][j] = x 运算

所谓赋值, 就是给矩阵里面的元素赋值,如果是对非零元素赋值,我们就修改列表里面的元素,如果是0元素赋值,我们就需要把
零元素修改,然后加入列表

 ● 三元素元素赋值算法

//传入列表,要赋值的值,要赋值的坐标
bool Value(TSMatrix &t,ElemType x,int i,int j)
{
	int k = 0,k1;
	//判断输入的合法性
	if(i>=t.rows || j>=t.cols)
	{
		return false;	//失败时返回false
	}
	while(kt.data[k].r)
	{
		k++;	//查找行
	}
	while(kt.data[k].c)
	{
		k++;	//查找列
	}
	if(t.data[k].r == i && t.data[k].c==j)
	{
		t.data[k].d=x;
	}
	else{
	// 不存在时要插入
	//同时完成移动操作
	//即完成顺序表的插入操作
	    for(k1=t.nums-1;k1>k;k1--)
		{
			 t.data[k1+1].r=t.data[k1].r;
			 t.data[k1+1].c=t.data[k1].c;
			 t.data[k1+1].d=t.data[k1].d;
		 }
         t.data[k].r=i;
		 t.data[k].c=j;
		 t.data[k].d=x;
		 t.nums++;
	}//不存在时要插
	   return true;//成功时返回true
}

输出三元组

    ● 从头到尾扫描三元组t,依次输出元素值

	//传入列表
void DispMat(TSMatrix t)
{
	int i;
	if(t.numsl<= 0)
	{
		return;
	} 
	printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
	printf("--------------\n");
	//遍历输出
	for(i=0;i
	{
	printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);
	}
}
 

矩阵转置
    ● 对于一个m * n 的矩阵A m*n,其转置矩阵是一个n * m的矩阵 B n*m,满足 bij = bji,其中 (0<= i <=m-1,0<= j <= n-1)
  

  void TranTat(TSMatrix t,TSMatrix &tb)
    {
        int p = 0;
        int q = 0;
        int v;
        tb.rows = t.cols;
        tb.cols = t.rows;
        tb.nums = t.nums;
        if(t.nums != 0)    //当存在非零元素时
        {
            //先遍历t的列,因为我们要对转置的行进行部署
            for(v=0; v
            {
                for(p=0; p
                {
                    if(t.data[p].c == v)
                    {
                        tb.data[q].r = t.data[p].c;
                        tb.data[q].c = t.data[p].r;
                        tb.data[q].d = t.data[p].d;
                        q++;
                    }
                }
            }
        }
    }

复杂度分析:

 占用时间复杂度过大, 我们要衡量空间和时间之间的关系, 这是一个永恒的话题,我们一般采用折中的算法.