数据结构实践遇难题，求基于链表的稀疏矩阵代码指导

Hey Byungheon, looks like you're working on a sparse matrix implementation using linked lists and hit some tricky spots. Let's start by organizing your existing code clearly, then walk through common fixes and enhancements for this setup.

Your Existing Code (Cleaned Up) #

#include <stdio.h>
typedef struct {
    int row; // 행번호
    int col; // 열번호
    int value; // 값
}element;
typedef struct ListNode {
    element data;
    struct ListNode *link;
}ListNode;
typedef struct {
    int rows;// 행의 갯수
    int cols;// 열의 개수
    ListNode *head;// 연결리스트의 시작
    ListNode *tail;// 연결리스트의 끝. 문제에 따라 사용할 건지는 본인이 선택
}ListHeader;
void init(ListHeader *plist, int r, int c) {
    plist->rows = r;
    plist->cols = c;
    plist->head = NULL;
    plist->tail = NULL;
}
void print_matrix(ListHeader *plist) {
    ListNode *p = pli... // 看起来这里代码没写完！
}

Key Fixes & Implementations #

Let's tackle the incomplete parts and common pain points for this sparse matrix setup:

1. Complete the print_matrix Function

You have two options here: print the full matrix (including zeros) or only the non-zero elements (more efficient for sparse matrices). Here are both implementations:

Full Matrix Print (with zeros):

void print_matrix(ListHeader *plist) {
    ListNode *current = plist->head;
    // Iterate through every row and column
    for (int i = 0; i < plist->rows; i++) {
        for (int j = 0; j < plist->cols; j++) {
            // Check if current node matches the (i,j) position
            if (current != NULL && current->data.row == i && current->data.col == j) {
                printf("%d ", current->data.value);
                current = current->link;
            } else {
                printf("0 "); // Print zero for empty positions
            }
        }
        printf("\n");
    }
}

Non-Zero Elements Only Print:

void print_non_zero(ListHeader *plist) {
    ListNode *current = plist->head;
    printf("Row\tColumn\tValue\n");
    while (current != NULL) {
        printf("%d\t%d\t%d\n", current->data.row, current->data.col, current->data.value);
        current = current->link;
    }
}

2. Add an Element Insertion Function

A critical piece for sparse matrices is inserting non-zero elements in sorted order (row-major, usually) to keep the list organized. Here's a robust implementation:

#include <stdlib.h> // Don't forget this for malloc!

int insert_element(ListHeader *plist, int row, int col, int value) {
    // Validate indices
    if (row < 0 || row >= plist->rows || col < 0 || col >= plist->cols) {
        printf("Invalid row/column index!\n");
        return -1;
    }
    // Skip zero values (sparse matrix rule)
    if (value == 0) return 0;

    // Create new node
    ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
    if (new_node == NULL) {
        printf("Memory allocation failed!\n");
        return -1;
    }
    new_node->data.row = row;
    new_node->data.col = col;
    new_node->data.value = value;
    new_node->link = NULL;

    // Insert into empty list
    if (plist->head == NULL) {
        plist->head = new_node;
        plist->tail = new_node;
        return 0;
    }

    // Insert at the beginning
    if (row < plist->head->data.row || (row == plist->head->data.row && col < plist->head->data.col)) {
        new_node->link = plist->head;
        plist->head = new_node;
        return 0;
    }

    // Find insertion point in the middle
    ListNode *current = plist->head;
    while (current->link != NULL && 
           (current->link->data.row < row || 
            (current->link->data.row == row && current->link->data.col < col))) {
        current = current->link;
    }

    // Insert at the end or middle
    if (current->link == NULL) {
        plist->tail->link = new_node;
        plist->tail = new_node;
    } else {
        new_node->link = current->link;
        current->link = new_node;
    }
    return 0;
}

3. Avoid Memory Leaks with a Cleanup Function

Always free allocated memory when you're done with the matrix:

void free_matrix(ListHeader *plist) {
    ListNode *temp;
    while (plist->head != NULL) {
        temp = plist->head;
        plist->head = plist->head->link;
        free(temp);
    }
    plist->tail = NULL;
    plist->rows = 0;
    plist->cols = 0;
}

Common Pitfalls to Watch For #

• Duplicate entries: Before inserting, check if an element already exists at (row, col) — update its value instead of adding a new node.
• Off-by-one errors: Ensure row/column indices stay within 0 to rows-1/cols-1.
• Uninitialized pointers: Always initialize your list header with init() before using it.

If you can share more details about the specific issue you're facing (like crashes, incorrect output, or matrix operation bugs), we can dive deeper into those!

内容的提问来源于stack exchange，提问作者Byungheon Lee