数组与广义表——稀疏矩阵的十字链表存储

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
    int row;                // 行索引
    int col;                // 列索引
    int value;             // 值
    struct Node *right;    // 指向同一行下一个节点
    struct Node *down;     // 指向同一列下一个节点
} Node;

typedef struct {
    Node **rowHead;        // 行头指针数组
    Node **colHead;        // 列头指针数组
    int rows;              // 矩阵行数
    int cols;              // 矩阵列数
} SparseMatrix;

// 创建稀疏矩阵
SparseMatrix* InitSparseMatrix(int rows, int cols) 
{
    SparseMatrix *matrix = (SparseMatrix *)malloc(sizeof(SparseMatrix));
    matrix->rows = rows;
    matrix->cols = cols;
    matrix->rowHead = (Node **)calloc(rows, sizeof(Node *));
    matrix->colHead = (Node **)calloc(cols, sizeof(Node *));
    return matrix;
}

// 插入元素
void insertElement(SparseMatrix *matrix, int row, int col, int value) 
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 插入到行链表
    if (matrix->rowHead[row] == NULL) 
	{
        matrix->rowHead[row] = newNode;
    } 
	else 
	{
        Node *current = matrix->rowHead[row];
        Node *prev = NULL;
        while (current && current->col < col) 
		{
            prev = current;
            current = current->right;
        }
        if (prev == NULL) 
		{
            newNode->right = matrix->rowHead[row];
            matrix->rowHead[row] = newNode;
        } 
		else 
		{
            newNode->right = current;
            prev->right = newNode;
        }
    }

    // 插入到列链表
    if (matrix->colHead[col] == NULL) 
	{
        matrix->colHead[col] = newNode;
    } 
	else 
	{
        Node *current = matrix->colHead[col];
        Node *prev = NULL;
        while (current && current->row < row) 
		{
            prev = current;
            current = current->down;
        }
        if (prev == NULL) 
		{
            newNode->down = matrix->colHead[col];
            matrix->colHead[col] = newNode;
        } 
		else 
		{
            newNode->down = current;
            prev->down = newNode;
        }
    }
}

// 打印稀疏矩阵
void printSparseMatrix(SparseMatrix *matrix) 
{
    printf("Sparse Matrix:\n");
    for (int i = 0; i < matrix->rows; i++)
	{
        Node *current = matrix->rowHead[i];
        while (current) 
		{
            printf("Value at (%d, %d): %d\n", current->row, current->col, current->value);
            current = current->right;
        }
    }
}

// 释放稀疏矩阵
void freeSparseMatrix(SparseMatrix *matrix) 
{
    for (int i = 0; i < matrix->rows; i++) 
	{
        Node *current = matrix->rowHead[i];
        while (current) 
		{
            Node *toDelete = current;
            current = current->right;
            free(toDelete);
        }
    }
    free(matrix->rowHead);
    free(matrix->colHead);
    free(matrix);
}

// 随机生成稀疏矩阵
SparseMatrix* CreateRandomSparseMatrix(int rows, int cols, float sparsity) 
{
    SparseMatrix *matrix = InitSparseMatrix(rows, cols);
    int m = rows * cols;
    int n = (int)(m * (1 - sparsity));

    srand((unsigned)time(NULL)); // 设置随机种子
    for (int i = 0; i < n; i++) 
	{
        int row = rand() % rows;
        int col = rand() % cols;
        int value = rand() % 100 + 1; // 随机值在 1 到 100 之间

        // 确保不重复插入相同位置的元素
        Node *current = matrix->rowHead[row];
        int exists = 0;
        while (current)
		{
            if (current->col == col) 
			{
                exists = 1; // 已存在
                break;
            }
            current = current->right;
        }
        if (!exists) 
		{
            insertElement(matrix, row, col, value);
        } 
		else 
		{
            i--; // 重复位置，重新生成
        }
    }
    return matrix;
}

int main() 
{
    int rows = 10;
    int cols = 10;
    float sparsity = 0.8; // 80% 的稀疏度

    SparseMatrix *matrix = CreateRandomSparseMatrix(rows, cols, sparsity);
    printSparseMatrix(matrix);
    freeSparseMatrix(matrix);

    return 0;
}