C 语言稀疏矩阵

2025年8月19日 | 阅读 6 分钟

在 C 编程语言中，稀疏矩阵是指其大多数元素值为零，只有少数非零位置的矩阵。稀疏矩阵不存储所有值，而只存储非零值，包括行和列索引，这样可以减少内存空间，并加快计算速度。

它们在图论（邻接矩阵）、机器学习（大型数据集的表示）、网络分析、科学模拟等领域有许多应用。一些最常见的数据格式是坐标列表 (COO)、压缩行存储 (CSR) 和压缩列存储 (CSC) 数据格式，每种格式都经过优化，可以执行特定的操作。这种表示法不仅可以使用更少的存储空间，而且在矩阵乘法和求解线性系统等运算中，当零元素不对解产生影响时，还可以提高性能。

形式化定义

如果矩阵满足以下条件，则认为它是稀疏矩阵：

例如

它是一个 4x4 的矩阵，有 14 个零值和只有 2 个非零值，使其成为一个稀疏矩阵。

为什么我们要使用稀疏矩阵？

在 C 语言中，有几种场景可以使用稀疏矩阵。

存储：稀疏矩阵的非零元素数量少于零，因此可以用更少的内存来存储元素。它只评估非零元素。
计算时间：在稀疏矩阵中搜索时，我们只需要遍历非零元素，而不是遍历所有稀疏矩阵元素。它通过逻辑设计数据结构来遍历非零元素，从而节省计算时间。
速度：通过零元素进行乘法、加法或搜索可以更快地完成，而无需考虑零元素。

稀疏矩阵内存表示

在 C 语言中，稀疏矩阵是指其大多数元素等于零的矩阵。我们不存储所有元素（包括零），以节省内存并通过仅存储非零元素来提高计算性能。

在 C 语言编程中有两种流行的方法来存储稀疏矩阵。

1) 数组表示 (坐标列表/3 元组形式)

我们将稀疏矩阵表示为三元组的二维数组，其中数组的每一行包含

非零元素的行索引
该非零元素的列位置
非零元素值
整体行数、列数和非零元素的元数据通常放在第一行。

矩阵

0 5
8 0
0 0

数组表示

[3, 3, 3]    // rows, columns, non-zero count
[0, 2, 5]
[1, 1, 8]
[2, 0, 3]

C 语言中的数组表示示例

让我们通过一个稀疏数组的例子来演示 C 语言中的数组表示。

示例

#include <stdio.h>
#define MAX 100 // Maximum non-zero elements
// using 3-tuple form
struct SparseMat {
    int row;    //defining row
    int col;    //defining col
    int val;   //defining val
};
int main() {   //main function
    int x, y;
    int matrix[8][8];
    struct SparseMat sparse[MAX];
    int k = 0; // Index for sparse array
   
    printf("Enter number of rows and columns: ");
    scanf("%d %d", &x, &y);
    
    printf("Enter the elements of the matrix:\n");
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            scanf("%d", &matrix[i][j]);
            if (matrix[i][j] != 0) {
                sparse[k].row = i;
                sparse[k].col = j;
                sparse[k].val = matrix[i][j];
                k++;
            }
        }
    }
    // Print Sparse Matrix
    printf("\nSparse Matrix Representation (row, col, value):\n");
    for (int i = 0; i < k; i++) {
        printf("%d\t%d\t%d\n", sparse[i].row, sparse[i].col, sparse[i].val);
    }
    return 0;
}

编译并运行

输出

Enter number of rows and columns: 3 4
Enter the elements of the matrix:
0 0 3 0
22 0 0 0
0 0 0 4

Sparse Matrix Representation (row, col, value):
0   2   3
1   0   22
2   3   4

说明

在此示例中，我们使用一个三元组结构打印稀疏矩阵，该结构仅存储非零元素及其行和列索引。它不存储所有元素，而是通过存储重要的值来节省内存。最后，它以行、列和值的形式打印稀疏矩阵。

2) 链表表示

每个非零元素存储在一个节点中，该节点包含

行索引
列索引
值
指向下一个节点的指针（按行主序或列主序）。
有时会使用多个链表来实现更快的访问（每个行或列一个）。

C 语言中的示例节点结构

struct Node {
    int row, col, value;
    struct Node* next;
}; 

相同矩阵的可视化示例

C 语言中的链表表示示例

让我们通过一个使用 C 语言中的稀疏数组的链表表示的例子来说明。

示例

#include <stdio.h>
#include <stdlib.h>
// Node structure for linked list representation
struct Node {
    int row, col, val;
    struct Node *next;
};
// Function to create a new node
struct Node* createNode(int row, int col, int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->row = row;
    newNode->col = col;
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}
// Function to insert a node at the end of the list
void insertNode(struct Node** head, int row, int col, int val) {
    struct Node* newNode = createNode(row, col, val);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}
// Function to display the sparse matrix linked list
void display(struct Node* head) {
    printf("\nSparse Matrix Representation (row, col, value):\n");
    while (head != NULL) {
        printf("%d\t%d\t%d\n", head->row, head->col, head->val);
        head = head->next;
    }
}
int main() {   //main function
    int m, n, val;
    struct Node* head = NULL;
    printf("Enter number of rows and columns: ");
    scanf("%d %d", &m, &n);
    printf("Enter the elements of the matrix:\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &val);
            if (val != 0) {
                insertNode(&head, i, j, val);
            }
        }
    }
    display(head);
    return 0;
}

编译并运行

输出

Enter the elements of the matrix:
0 0 7 0
18 0 0 0
0 5 0 0

Sparse Matrix Representation (row, col, value):
0       2       7
1       0       18
2       1       5

说明

在此示例中，我们使用链表表示稀疏矩阵，其中仅存储非零元素及其行、列和值。稀疏矩阵通过避免存储零值来减少内存使用。最后，它以行、列和值的形式高效地打印矩阵。

稀疏矩阵的属性

C 语言中的稀疏矩阵有几个属性。其中一些如下：

高零密度：与非零元素相比，零元素的数量非常多。
高效的存储格式：特定用例使用不同的存储格式来存储稀疏矩阵（例如 COO、CSR 和 CSC）。
性能优化：在加法、乘法和遍历等多种运算中跳过零元素，可以提高计算速度。
位置-值映射：我们需要存储每个非零元素的行号、列号和值来重建矩阵。

结论

总之，C 语言中的稀疏矩阵用于仅存储非零元素，这可以节省内存并提高大型数据集的性能。在 C 语言编程中，基于数组的表示紧凑且便于快速访问，但对更新的灵活性较低。链表表示支持动态修改，但会为指针使用额外的内存。稀疏矩阵在图像处理、图形、机器学习等许多领域都非常有用。

稀疏矩阵常见问题解答

1) 稀疏矩阵是什么意思？

稀疏矩阵是一种矩阵，其中大多数元素为零，只有少数非零元素被存储以节省内存。

2) 为什么我们在 C 语言编程中使用稀疏矩阵？

稀疏矩阵主要用于减少存储使用，并有助于提高涉及大量零的巨大矩阵的运算效率。

3) 基于数组和链表的动态重塑有什么区别？

基于数组的存储在大小增长时需要不断分配新内存和复制数据，这对于频繁的修改来说成本很高。链表无需完全重新分配即可实现增长，但代价是增加了内存开销（指针）。

4) 稀疏矩阵在 C 语言中用在哪里？

稀疏矩阵可用于多个领域，例如：

图像处理
科学计数法
机器学习
图算法，以及更多

5) C 语言中稀疏矩阵的 3 元组形式是什么意思？

在 C 语言编程中，3 元组类型是一种紧凑的数组形式，其中每个非零元素都被定义为行、列和值。

下一主题C 语言编程测试

C 语言稀疏矩阵

为什么我们要使用稀疏矩阵？

稀疏矩阵内存表示

1) 数组表示 (坐标列表/3 元组形式)

C 语言中的数组表示示例

示例

2) 链表表示

C 语言中的链表表示示例

示例

稀疏矩阵的属性

结论

稀疏矩阵常见问题解答

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言稀疏矩阵

为什么我们要使用稀疏矩阵？

稀疏矩阵内存表示

1) 数组表示 (坐标列表/3 元组形式)

C 语言中的数组表示示例

示例

2) 链表表示

C 语言中的链表表示示例

示例

稀疏矩阵的属性

结论

稀疏矩阵常见问题解答

相关帖子

C 语言 Plus Minus HackerRank 解决方案

C 语言选择排序

C 语言 typedef vs define

C 语言锯齿数组或数组的数组

C 语言龙格-库塔法

C 语言 %u

C 语言 complex.h 头文件

C 语言 fsetpos() (设置文件位置)

C 语言计算矩形周长和面积的程序

C 语言 Char_bit

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器