数据结构——特殊矩阵的压缩存储

柔光的暖阳◎ 2022-06-17 09:37 250阅读 0赞

# 数据结构——特殊矩阵的压缩存储 #

**矩阵的压缩存储**：将矩阵的元素按照某种分布规律存储在较小的存储单元中。

## 1、对称矩阵的压缩存储 ##

**n阶对称矩阵**：一个n阶的矩阵A中的元素满足a(ij)=a(ji)(0<i,j<n-1)。由于矩阵中的元素是关于主对角线对称的，那么就可以只存储上三角或者下三角矩阵中的元素，这样就可以把原来需要存储n\*n个元素压缩至n\*(n-1)/2个元素了。使用一维数组s\[k\]以行为主存储对称矩阵A(i,j)的下三角元素，那么k和(i,j)之间的对应关系如下：

![20170423092615331][]

（使用等差数列公式就可以推导出来，下同）

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    /**对称矩阵压缩存储**/
    void PrintMatrix(double *s,int n);
    /**存储对称矩阵**/
    void storeMatrix(int n){
    	double *s = new double[n];
    	int len = n*(n+1)/2;
    	printf("Input the UP_Matrix's element by the order of row\n");
    	for(int i = 0;i<len;i++){
    		scanf("%d",&s[i]);
    	}
    	PrintMatrix(s,n);
    }
    /**打印矩阵**/
    void PrintMatrix(double *s,int n){
    	int k = 0;
    	for(int i =0;i<n;i++){
    		for(int j = 0;j<n;j++){
    			//以行为主存储下三角矩阵
    			if(i>=j)	k = i*(i+1)/2+j;
    			else	k = j*(j+1)/2+i;
    			printf("%d\t",s[k]);
    		}
    		printf("\n");
    	}
    	
    }
    void main(){
    	int n = 0 ;
    	printf("Input the order of the matrix:");
    	scanf("%d",&n);
    	storeMatrix(n);
    	system("pause");
    }

## 2、三角矩阵的压缩存储 ##

**上三角矩阵：**下三角元素均为常数的矩阵。

**下三角矩阵：**上三角元素均为常数的矩阵。

跟对称矩阵存储相似，只是一位数组s的最后一位用来存储常数项。而且这里的上三角矩阵的存储相当于对称矩阵的以列为主的压缩存储。

![SouthEast][]

## 3、对角矩阵的压缩存储 ##

**对角矩阵：**所有非零元素集中在主对角线两侧的带状区域内。m对角矩阵是指非零元素在每行中有m个，如下图为三对角矩阵。

![20170423103641350][]

特点：

>  *  第一行和最后一行有2个非零元素，第2-n-1行有3个非零元素
>  *  前i-1行有3\*(i-1)-1个非零元素，第i行的非零元素个数为j-i+1当j<i时，j-i = -1当j>i时j-i=1
>  *  使用一维数组存储，需要存储3\*n-2个元素
>  *  一维数组s\[k\]和A\[i\]\[j\]的对应关系为：k = 2\*i+j

## 4、稀疏矩阵的压缩存储 ##

**稀疏矩阵：**大多数元素均为零的矩阵。定义矩阵m\*n如果有t个非零元素，那么s = t/m\*n称为矩阵的稀疏因子，如果s<=0.05那么矩阵为稀疏矩阵。

**数据对象集合：**稀疏矩阵可以使用三元组顺序表表示，其中三元组格式为(i,j,e)记录了非零元素的行号、列号以及非零元素。

![20170511093421465][]

**基本操作集合：**

>  *  CreateMatrix(&M):创建稀疏矩阵
>  *  DestroyMatrix(&M):销毁稀疏矩阵
>  *  PrintMatrix(M):打印稀疏矩阵
>  *  CopyMatrix(M,&N):复制稀疏矩阵M到N
>  *  AddMatrix(M,N,&Q):矩阵加法
>  *  SubMatrix(M,N,&Q):矩阵减法
>  *  MultiMatrix(M,N,&Q):矩阵乘法
>  *  TransposeMatrix(M,&N):矩阵转置

代码实现：

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    /**稀疏矩阵压缩存储**/
    #define MAXSIZE 100
    typedef struct 
    {
    	int i;
    	int j;
    	int e;
    }Triple;
    typedef struct 
    {
    	Triple data[MAXSIZE];
    	int m,n,len;
    }Matrix;
    //函数声明
    int CreateMatrix(Matrix *M);
    void DestroyMatrix(Matrix *M);
    void PrintMatrix(Matrix M);
    void CopyMatrix(Matrix M,Matrix *N);
    int CompareNumber(int a,int b);
    int AddMatrix(Matrix M,Matrix N,Matrix *Q);
    int SubMatrix(Matrix M,Matrix N,Matrix *Q);
    void TransposeMatrix(Matrix M,Matrix *N);
    /**创建一个稀疏矩阵**/
    int CreateMatrix(Matrix *M){
    	//创建成功返回1
    	int i,m,n,len;
    	int e;
    	int flag;
    	printf("Input the Matrix's row,col and the number of non-zero element:");
    	scanf("%d%d%d",&m,&n,&len);
    	if(len>MAXSIZE)
    		return 0;
    	M->len = len;
    	M->m = m;
    	M->n = n;
    	//以行为主录入非零元素
    	for(i = 0;i<len;i++){
    		do{
    			printf("%d、Input the row(1-%d) and col(i-%d) of element by the order of row:",i,M->m,M->n);
    			scanf("%d%d%d",&m,&n,&e);
    			flag = 0;
    			if(m<0||n<0||m>M->m||n>M->n)
    				flag = 1;
    			if(i>0&&m<M->data[i-1].i||m==M->data[i-1].i&&n<M->data[i-1].j)
    				flag = 1;
    		}while(flag);
    		M->data[i].i = m;
    		M->data[i].j = n;
    		M->data[i].e = e;
    	}
    	return 1;
    }
    /**销毁一个稀疏矩阵**/
    void DestroyMatrix(Matrix *M){
    	M->len = 0;
    	M->m = 0;
    	M->n = 0;
    }
    /**打印矩阵**/
    void PrintMatrix(Matrix M){
    	int len  = M.len;
    	printf("k\ti\tj\te\n");
    	for(int i = 0;i<len;i++){
    		printf("%d\t%d\t%d\t%d\n",i,M.data[i].i,M.data[i].j,M.data[i].e);
    	}
    }
    /**矩阵复制**/
    void CopyMatrix(Matrix M,Matrix *N){
    	int len = M.len;
    	N->len = len;
    	N->m = M.m;
    	N->n = M.n;
    	for(int i =0 ;i<len;i++){
    		N->data[i].i = M.data[i].i;
    		N->data[i].j = M.data[i].j;
    		N->data[i].e = M.data[i].e;
    	}
    }
    int CompareNumber(int a,int b){
    	if(a<b)
    		return -1;
    	if(a==b)
    		return 0;
    	return 1;
    }
    /**矩阵加法**/
    int AddMatrix(Matrix M,Matrix N,Matrix *Q){
    	//相加成功返回1
    	if(M.m!=N.m||M.n!=N.n) return 0;
    	int m = 0,n = 0,k = -1;
    	Q->m = M.m;
    	Q->n = M.n;
    	while(m<M.len&&n<M.len){
    		switch (CompareNumber(M.data[m].i,N.data[n].i))
    		{
    		case -1:
    			Q->data[++k] = M.data[m++];
    			break;
    		case 0:
    			switch (CompareNumber(M.data[m].j,N.data[n].j))
    			{
    			case -1:
    				Q->data[++k] = M.data[m++];
    				break;
    			case 0:
    				Q->data[++k] = M.data[m++];
    				Q->data[k].e += N.data[n++].e;
    				if(Q->data[k].e==0){
    					k--;
    				}
    				break;
    			case 1:
    				Q->data[++k] = N.data[n++];
    				break;
    			}
    			break;
    		case 1:
    			Q->data[++k] = N.data[n++];
    			break;
    		}
    	}
    	while(m<M.len){
    		Q->data[++k] = M.data[m++];
    	}
    	while(n<N.len){
    		Q->data[++k] = N.data[n++];
    	}
    	Q->len = k+1;
    	if(k>MAXSIZE){
    		printf("ERROR!Out of bound!");
    		return 0;
    	}
    	return 1;
    }
    /**矩阵减法**/
    //只需要将第二个矩阵的每个元素取反然后进行加法即可
    int SubMatrix(Matrix M,Matrix N,Matrix *Q){
    	//相减成功返回1
    	int len = N.len;
    	for(int i=0;i<len;i++){
    		N.data[i].e = -N.data[i].e;
    	}
    	return AddMatrix(M,N,Q);
    }
    /**转置矩阵**/
    void TransposeMatrix(Matrix M,Matrix *N){
    	int i ,k,t,col,*num,*position;
    	num = (int *)malloc((M.n+1)*sizeof(int));
    	position = (int *)malloc((M.n+1)*sizeof(int));
    	N->m = M.m;
    	N->n = M.n;
    	N->len = M.len;
    	if(N->len){
    		for(col=0;col<M.n;++col){
    			num[col] = 0;
    		}
    		for(t = 0;t<M.len;t++){
    			num[M.data[t].j]++;
    		}
    		position[0] = 0;
    		for(col = 1;col<M.n;col++){
    			position[col] = position[col-1]+num[col-1];
    		}
    		for(i = 0;i<M.len;i++){
    			col = M.data[i].j;
    			k = position[col];
    			N->data[k].i =M.data[i].j;
    			N->data[k].j = M.data[i].i;
    			N->data[k].e = M.data[i].e;
    			position[col]++;
    		}
    	}
    	free(num);
    	free(position);
    }
    void main(){
    	Matrix m1,m2,m3,m4,m5;
    	CreateMatrix(&m1);
    		PrintMatrix(m1);
    		CopyMatrix(m1,&m2);
    		printf("--------------\n\n");
    		PrintMatrix(m2);
    		AddMatrix(m1,m2,&m3);
    		printf("--------------\n\n");
    		PrintMatrix(m3);
    		SubMatrix(m3,m2,&m4);
    		printf("--------------\n\n");
    		PrintMatrix(m4);
    		TransposeMatrix(m4,&m5);
    		printf("--------------\n\n");
    		PrintMatrix(m5);
    		DestroyMatrix(&m1);
    		printf("--------------\n\n");
    		PrintMatrix(m1);
    	system("pause");
    }

[20170423092615331]: /images/20220617/7788ca6c77e7486dbcd7d9683dc0a9bf.png
[SouthEast]: /images/20220617/5b0dfa9996814891b108825a8b08e828.png
[20170423103641350]: /images/20220617/fcc44793cbfb4daf8f50f38489447354.png
[20170511093421465]: /images/20220617/3dbae247cb0b4fdfb749276712d6a56d.png