# 矩阵的压缩存储原理

当一个矩阵中有许多`值相同的元素`或是`零元素`,为了`节省`矩阵的存储空间,
可以对此类矩阵进行压缩存储,
而压缩存储的值是:为多个`相同的元素`只分配一个存储空间;对`零元素`不分配空间。
此处为对稀疏矩阵的压缩存储的介绍,
此外,因为稀疏矩阵是一个`不确定`的概念,
通常利用假设`稀疏因子`来定义一个矩阵是否为稀疏矩阵,
`稀疏因子`是通过`Row x Col`矩阵中不为零的元素 ÷ 矩阵总元素的个数来求得,
`稀疏因子`小于或等于0.05时称为稀疏矩阵。
当存储稀疏矩阵时,只需存储不为零的元素,
因此当存储时只需记录`不为零元素的行与列`的位置,
也就是存储在一个三元组`(Row,col,data)`中即可。

# 稀疏矩阵的压缩存储的基本实现

Matrix.txt
6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
Sparse_Matrix_.h(头文件)
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
#include<assert.h>
#define MAX_SPACE 40
typedef int DataType;
struct Triple
{
	DataType data;
	int row;
	int col;
};
struct Matrix_Pointer
{
	struct Triple List[MAX_SPACE];
	int All_row;
	int All_col;
	int All_R_data;
};
void CreateMatrix(struct Matrix_Pointer* M_P);
void Show_Menu();
void PrintMatrix(const struct Matrix_Pointer* M_P);
void CopyMatrix(const struct Matrix_Pointer* M_P, struct Matrix_Pointer* C_M_P);
void AddMatrix(struct Matrix_Pointer* M_P, const struct Matrix_Pointer* M_P1, const struct Matrix_Pointer* M_P2);
void SubMatrix(struct Matrix_Pointer* M_P, const struct Matrix_Pointer* M_P1, const struct Matrix_Pointer* M_P2);
void MulMatrix(struct Matrix_Pointer* M_P, const struct Matrix_Pointer* M_P1, const struct Matrix_Pointer* M_P2);
void TransposeMatrix(const struct Matrix_Pointer* M_P, struct Matrix_Pointer* M_P1);
void Fast_TransposeMatrix(const struct Matrix_Pointer* M_P,struct Matrix_Pointer* M_P1);
Sparse_Matrix_fuctions.c
#include"Sparse_Matrix_.h"
void Show_Menu()
{
	printf("\n**************************************************\n");
	printf(" [1]  CreateMatrix     [2]  PrintMatrix          *\n");
	printf(" [3]  CopyMatrix       [4]  AddMatrix            *\n");
	printf(" [5]  SubMatrix        [6]  MulMatrix            *\n");
	printf(" [7]  TransposeMatrix  [8]  Fast_TransposeMatrix *\n");
	printf(" [0]  SystemExit                                 *\n");
	printf("**************************************************\n");
}
void CreateMatrix(struct Matrix_Pointer* M_P)
{
	assert(NULL != M_P);
	FILE* fp = fopen("Matrix.txt", "r");
	
	if (NULL == fp)
		exit(1);
	else
	{
		int i = 0;
		int j = 0;
		int k = 0;
		fscanf(fp, "%d %d", &M_P->All_row, &M_P->All_col);
		for (i = 0; i < M_P->All_row; ++i)
		{
			for (j = 0; j < M_P->All_col; ++j)
			{
				fscanf(fp, "%d", &M_P->List[k].data);
				if (!(M_P->List[k].data))
					continue;
				M_P->List[k].row = i;
				M_P->List[k].col = j;
				++k;
			}
		}
		M_P->All_R_data = k;
	}
	fclose(fp);
}
void PrintMatrix(const struct Matrix_Pointer* M_P)
{
	assert(NULL != M_P);
	if (!(M_P->All_R_data))
		return;
	else
	{
		int i = 0;
		printf("Row:%d,Col:%d\n", M_P->All_row, M_P->All_col);
		for (i = 0; i < M_P->All_R_data; ++i)
			printf("(%d,%d,%d)\n", M_P->List[i].row, M_P->List[i].col, M_P->List[i].data);
	}
}
void CopyMatrix(const struct Matrix_Pointer* M_P, struct Matrix_Pointer* C_M_P)
{
	assert(NULL != M_P && NULL != C_M_P);
	if (!(M_P->All_R_data) || !(C_M_P->All_R_data))
		return;
	else
	{
		int i = 0;
		C_M_P->All_row = M_P->All_row;
		C_M_P->All_col = M_P->All_col;
		C_M_P->All_R_data = M_P->All_R_data;
		for (i = 0; i < C_M_P->All_R_data; ++i)
		{
			C_M_P->List[i].row = M_P->List[i].row;
			C_M_P->List[i].col = M_P->List[i].col;
			C_M_P->List[i].data = M_P->List[i].data;
		}
		PrintMatrix(C_M_P);
	}
}
void AddMatrix(struct Matrix_Pointer* M_P, const struct Matrix_Pointer* M_P1, const struct Matrix_Pointer* M_P2)
{
	assert(NULL != M_P && NULL != M_P1 && NULL != M_P2);
	if (!(M_P1->All_R_data) || !(M_P2->All_R_data))
		return;
	else if (M_P1->All_row != M_P2->All_row || M_P1->All_col != M_P2->All_col)
		return;
	else
	{
		int i = 0;
		M_P->All_row = M_P1->All_row;
		M_P->All_col = M_P1->All_col;
		M_P->All_R_data = M_P1->All_R_data;
		for (i = 0; i < M_P->All_R_data; ++i)
		{
			M_P->List[i].row = M_P1->List[i].row;
			M_P->List[i].col = M_P1->List[i].col;
			M_P->List[i].data = M_P1->List[i].data + M_P2->List[i].data;
		}
	}
	PrintMatrix(M_P);
}
void SubMatrix(struct Matrix_Pointer* M_P, const struct Matrix_Pointer* M_P1, const struct Matrix_Pointer* M_P2)
{
	assert(NULL != M_P && NULL != M_P1 && NULL != M_P2);
	if (!(M_P1->All_R_data) || !(M_P2->All_R_data))
		return;
	else if (M_P1->All_row != M_P2->All_row || M_P1->All_col != M_P2->All_col)
		return;
	else
	{
		int i = 0;
		M_P->All_row = M_P1->All_row;
		M_P->All_col = M_P1->All_col;
		M_P->All_R_data = M_P1->All_R_data;
		for (i = 0; i < M_P->All_R_data; ++i)
		{
			M_P->List[i].row = M_P1->List[i].row;
			M_P->List[i].col = M_P1->List[i].col;
			M_P->List[i].data = M_P1->List[i].data - M_P2->List[i].data;
		}
	}
	PrintMatrix(M_P);
}
void MulMatrix(struct Matrix_Pointer* M_P, const struct Matrix_Pointer* M_P1, const struct Matrix_Pointer* M_P2)
{
	assert(NULL != M_P && NULL != M_P1 && NULL != M_P2);
	int Pointer = 0;
	int i = 0;
	int j = 0;
	int n = 0;
	if (!(M_P1->All_R_data) || !(M_P2->All_R_data))
		return;
	else if (M_P1->All_col == M_P1->All_row && M_P2->All_col == M_P2->All_row)
	{
		M_P->All_row = M_P->All_row;
		M_P->All_col = M_P->All_col;
	}
	else if (M_P1->All_col == M_P2->All_col)
	{
		M_P->All_row = M_P1->All_row;
		M_P->All_col = M_P2->All_row;
	}
	else
	{
		M_P->All_row = M_P1->All_row;
		M_P->All_col = M_P2->All_col;
	}
	
	for (i = 0; i < M_P1->All_R_data; ++i)
	{
		for (j = 0; j < M_P2->All_R_data; ++j)
		{
			if (M_P1->List[i].col == M_P2->List[j].row)
			{
				int flag = 1;
				for (n = 0; n < Pointer; ++n)
				{
					if (M_P->List[n].row == M_P1->List[i].row && M_P->List[n].col == M_P2->List[j].col)
					{
						M_P->List[n].data += M_P1->List[i].data * M_P2->List[j].data;
						flag = 0;
						break;
					}
				}
				if (!(flag))
					continue;
				M_P->List[Pointer].row = M_P1->List[i].row;
				M_P->List[Pointer].col = M_P2->List[j].col;
				M_P->List[Pointer].data = M_P1->List[i].data * M_P2->List[j].data;
				++Pointer;
			}
		}
	}
	PrintMatrix(M_P);
}
void TransposeMatrix(const struct Matrix_Pointer* M_P, struct Matrix_Pointer* M_P1)
{
	assert(NULL != M_P && NULL != M_P1);
	if (!(M_P->All_R_data))
		return;
	else
	{
		int i = 0;
		int col = 0;
		int N = 0;
		M_P1->All_col = M_P->All_row;
		M_P1->All_row = M_P->All_col;
		M_P1->All_R_data = M_P->All_R_data;
		for (col = 0; col < M_P->All_col; ++col)
		{
			for (i = 0; i < M_P->All_R_data; ++i)
			{
				if (col == M_P->List[i].col)
				{
					M_P1->List[N].row = M_P->List[i].col;
					M_P1->List[N].col = M_P->List[i].row;
					M_P1->List[N].data = M_P->List[i].data;
					++N;
				}
			}
		}
		PrintMatrix(M_P1);
	}
	
}
void Fast_TransposeMatrix(const struct Matrix_Pointer* M_P, struct Matrix_Pointer* M_P1)
{
	assert(NULL != M_P && NULL != M_P1);
	if (!(M_P->All_R_data) || !(M_P1->All_R_data))
		return;
	else
	{
		int i = 0;
		int Pointer = 0;
		int col = 0;
		int* Per_N = (int*)calloc(M_P->All_col, sizeof(int));
		int* Head_N = (int*)calloc(M_P->All_col, sizeof(int));
		M_P1->All_col = M_P->All_row;
		M_P1->All_row = M_P->All_col;
		M_P1->All_R_data = M_P->All_R_data;
		for (i = 0; i < M_P->All_R_data; ++i)
			++Per_N[M_P->List[i].col];
		Head_N[0] = 0;
		for (i = 1; i < M_P->All_col; ++i)
			Head_N[i] = Head_N[i - 1] + Per_N[i - 1];
		for (i = 0; i < M_P->All_R_data; ++i)
		{
			col = M_P->List[i].col;
			Pointer = Head_N[col];
			M_P1->List[Pointer].col = M_P->List[i].row;
			M_P1->List[Pointer].row = M_P->List[i].col;
			M_P1->List[Pointer].data = M_P->List[i].data;
			++Head_N[col];
		}
		free(Per_N);
		free(Head_N);
		PrintMatrix(M_P1);
	}
}
Sparse_Matrix_main.c
#include"Sparse_Matrix_.h"
int main()
{
	struct Matrix_Pointer M_P,C_M_P;
	struct Matrix_Pointer M_P1, M_P2;
	int option = 0;
	memset(&M_P, 0, sizeof(struct Matrix_Pointer));
	Show_Menu();
	while (printf("\n选择为> "), scanf("%d", &option), option)
	{
		getchar();// 截断字符缓冲区的换行符
		switch (option)
		{
		case 1:
			CreateMatrix(&M_P);
			break;
		case 2:
			PrintMatrix(&M_P);
			break;
		case 3:
			CopyMatrix(&M_P, &C_M_P);
			break;
		case 4:
			CreateMatrix(&M_P1);
			CreateMatrix(&M_P2);
			AddMatrix(&M_P, &M_P1, &M_P2);
			break;
		case 5:
			CreateMatrix(&M_P1);
			CreateMatrix(&M_P2);
			SubMatrix(&M_P, &M_P1, &M_P2);
			break;
		case 6:
			CreateMatrix(&M_P1);
			CreateMatrix(&M_P2);
			MulMatrix(&M_P, &M_P1, &M_P2);
			break;
		case 7:
			TransposeMatrix(&M_P,&M_P1);
			break;
		case 8:
			Fast_TransposeMatrix(&M_P, &M_P1);
			break;
		default:printf("不在选择的范围内\n");
		}
		Show_Menu();
	}
	printf("已退出\n");
	return 0;
}