c语言稀疏矩阵_C中的稀疏矩阵

爱被打了一巴掌 2022-12-07 12:53 173阅读 0赞

![36820264dce8df0bda78970e8ccb4bd4.png][]

c语言稀疏矩阵

In this tutorial, we are going to learn about the sparse matrix in C.

在本教程中，我们将学习C语言中的稀疏矩阵。

Before we start let us first discuss what a little bit about two-dimensional arrays. A matrix is represented by 2D arrays where the first index represents the number of rows and the second index represents the number of columns in the matrix. An m\*n matrix is represented by a [2D array][].

在开始之前，让我们先讨论一下二维数组的内容。 矩阵由2D数组表示，其中第一个索引表示行数，第二个索引表示矩阵中的列数。 m \* n矩阵由[2D数组][2D array]表示。

arr[m][n]

**Sparsity**: A matrix is said to be sparse matrix if most of the elements (More than half) elements in the matrix are zero and the number of elements divided by the total number of elements present in the array is called the sparsity of the matrix.

**稀疏性** ：如果矩阵中的大多数元素(大于一半)元素为零，并且元素数除以数组中存在的元素总数，则称矩阵为稀疏矩阵。

Sparsity = Number of non-zero elements/ Total number of elements

稀疏度=非零元素数/元素总数

Matrix is sparse if sparsity is less than 0.5 and dense otherwise.

如果稀疏度小于0.5，则矩阵稀疏，否则稀疏。

When storing data in the array the zero does not actually represent any information but they are taking space in memory so instead of storing this type of data in the 2D arrays we can store that data in some other format and reduce the overall space required by the program.

当将数据存储在数组中时，零实际上并不代表任何信息，但是它们在内存中占用空间，因此，除了将这种类型的数据存储在2D数组中之外，我们还可以以其他格式存储该数据并减少存储空间所需的总空间。程序。

Creating table from the sparse matrix :

从稀疏矩阵创建表：

Instead of having an array containing zeroes we can actually remove all those zeroes from the array and to can store indices of the elements in the array separately.

我们实际上可以从数组中删除所有这些零，而不必将数组包含零，并且可以将元素的索引分别存储在数组中。

The above array can be converted to a sparse matrix using the following code:

可以使用以下代码将上述数组转换为稀疏矩阵：

#include <stdio.h>
     
    int nonZeroElements(int m,int n,int arr[][n])
    {
    	int i,j;
    	int counter = 0;
    	for(i=0;i<m;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			if(arr[i][j]!=0)
    				counter++;
    		}
    	}
    	
    	return counter;
    }
     
    void convertIntoSparse(int m,int n,int arr[][n])
    {
    	int nonZero = nonZeroElements(m,n,arr);
    	
    	double sparsity = nonZero/16.0;
    	int applicable = sparsity <= 0.5;
    	
    	if(applicable)
    	{
    		int sparseMatrix[3][nonZero];
    		int i,j,counter = 0;
    		
    		for(i=0;i<m;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				if(arr[i][j]!=0)
    				{
    					sparseMatrix[0][counter] = i;
    					sparseMatrix[1][counter] = j;
    					sparseMatrix[2][counter] = arr[i][j];
    					counter++;
    				}
    			}
    		}
    		
    		printf("The final Sparse Matrix is : \n");
    		
    		for(i=0;i<nonZero;i++)
    		{
    			printf("At (%d, %d) value is : %d\n",sparseMatrix[0][i],sparseMatrix[1][i],sparseMatrix[2][i]);
    		}
    		
    	}
    	else
    	{
    		printf("Matrix is not a sparse matrix !!");
    	}
    	
    }
     
    int main(void) {
    	
    	
    	/* 
    	int m,n,i,j;
    	scannf("%d%d",&m,&n);
    	
    	for(i=0;i<m;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			scanf("%d",&arr[i][j]);
    		}
    	}
    	
    	*/
    	
    	int m = 4, n = 4;
    	int arr[4][4] = { 
    		{4, 0, 1, 0},
    		{0, 0, 2, 3},
    		{0, 0, 0, 5}
    	};
    	
    	convertIntoSparse(m,n,arr);
    	
    	return 0;
    }

Using a linked list:

使用链表：

We can also use a linked list for the same purpose. The structure of the linked list will look as below :

我们也可以出于相同目的使用链表。 链接列表的结构如下所示：

struct node{
    	int rows;
    	int cols;
    	int val;
    	struct node* next;
    }

All the other operations can be performed similary on the linked list and space can be saved.

所有其他操作都可以在链表上类似地执行，并且可以节省空间。

Most of the languages nowadays use vector of pairs/structures or list of pairs/structures to store the sparse matrix.

如今，大多数语言都使用成对/结构的向量或成对/结构的列表来存储稀疏矩阵。

> 翻译自: [https://www.thecrazyprogrammer.com/2020/03/sparse-matrix-in-c.html][https_www.thecrazyprogrammer.com_2020_03_sparse-matrix-in-c.html]

c语言稀疏矩阵

[36820264dce8df0bda78970e8ccb4bd4.png]: /images/20221123/23fb4911578c4b53880ce883f9a2476b.png
[2D array]: https://www.thecrazyprogrammer.com/2015/01/arrays-in-c-2d-array-part-5.html
[https_www.thecrazyprogrammer.com_2020_03_sparse-matrix-in-c.html]: https://www.thecrazyprogrammer.com/2020/03/sparse-matrix-in-c.html