연결 리스트로 작성하는 희소행렬

이전 프로그램에서는 희소행렬을 단순 배열로 작성해보았습니다.
이번에는 연결 리스트를 활용하여 작성해보겠습니다.

일단 첫번째로 row, col, value의 데이터가 들어간 Node를 뒤의 Node로 link시켜서 만드는..
연결 리스트가 생각납니다.
그러나 더 효과적인 방법은 없을까요?

2차원 형식으로 작성하는 건 어떨까요?
코드의 기본 틀을 작성하면 이렇게 됩니다.

typedef enum {head, entry} tagfield;

// 데이터를 저장하는 노드 구조체
struct entry_node {
    int row;
    int col;
    int value;
};

// 매트릭스의 노드를 나타내는 구조체
struct matrix_node {
    struct matrix_node *down;  // 아래쪽 노드를 가리키는 포인터
    struct matrix_node *right; // 오른쪽 노드를 가리키는 포인터
    tagfield tag;              // 노드의 유형 (head 또는 entry)
    union {
        struct entry_node entry; // 데이터를 저장하는 노드
        struct matrix_node *next; // 다음 헤드 노드를 가리키는 포인터
    } u;
};

matrix 형태의 데이터를 2차원으로 해석하는 것입니다.

위의 코드에서 확인할 수 있듯이, 노드는 head와 entry로 구분됩니다. head에는 null값이 들어가고 다음에 들어갈 entry를 가리킵니다.
그리고 union을 통해 데이터를 저장, 다음 헤드 노드로를 처리시킵니다.

행에서의 head 노드는 right 노드로 연결됩니다.
열에서의 head 노드는 down 노드로 연결됩니다.
비제로 요소가 있으면 노드에 연결합니다.

typedef struct matrix_node *matrix_pointer;

matrix_pointer hdnode[MAX_SIZE];

// 새로운 노드를 동적으로 생성하는 함수
matrix_pointer new_node() {
    matrix_pointer temp = (matrix_pointer)malloc(sizeof(struct matrix_node));
    if (!temp) {
        printf("Memory allocation error\n");
        exit(1);
    }
    return temp;
}

// 매트릭스를 읽어들이는 함수
matrix_pointer mread() {
    int num_rows, num_cols, num_nonzeros, num_heads;
    int row, col, value, current_row;
    matrix_pointer temp, last, node;

    // 행, 열, 0이 아닌 값의 개수를 입력받음
    printf("Enter the number of rows, columns, and nonzeros: ");
    scanf("%d %d %d", &num_rows, &num_cols, &num_nonzeros);

    num_heads = (num_rows > num_cols) ? num_rows : num_cols;

    // 헤드 노드를 생성
    node = new_node();
    node->tag = entry;
    node->u.entry.row = row;
    node->u.entry.col = col;

    if (!num_heads) {
        node->right = node;
    } else {
        // 헤드 노드들을 초기화
        for (int i = 0; i < num_heads; i++) {
            temp = new_node();
            hdnode[i] = temp;
            hdnode[i]->tag = head;
            hdnode[i]->right = temp;
            hdnode[i]->u.next = temp;
        }
    }

    current_row = 0;
    last = hdnode[0];

    // 각 비제로 요소를 읽어들이고 노드로 변환하여 연결
    for (int i = 0; i < num_nonzeros; i++) {
        printf("Enter the row, column, and value: ");
        scanf("%d %d %d", &row, &col, &value);

        if (row > current_row) {
            last->right = hdnode[current_row];
            current_row = row;
            last = hdnode[row];
        }

        temp = new_node();
        temp->tag = entry;
        temp->u.entry.row = row;
        temp->u.entry.col = col;
        temp->u.entry.value = value;

        last->right = temp;
        last = temp;
        hdnode[col]->u.next->down = temp;
        hdnode[col]->u.next = temp;
    }

    last->right = hdnode[current_row];

    // 각 헤드 노드들을 연결
    for (int i = 0; i < num_heads - 1; i++) {
        hdnode[i]->u.next->down = hdnode[i + 1];
    }

    hdnode[num_heads - 1]->u.next->down = hdnode[0];

    return node;
}

// 매트릭스를 출력하는 함수
void mwrite(matrix_pointer node, int num_rows, int num_cols) {
    matrix_pointer temp, head = node->right;

    printf("Sparse Matrix:\n");
    for (int i = 0; i < num_rows; i++) {
        temp = head->right;
        for (int j = 0; j < num_cols; j++) {
            if (temp != head && temp->u.entry.col == j) {
                printf("%d ", temp->u.entry.value);
                temp = temp->right;
            } else {
                printf("0 ");
            }
        }
        head = head->u.next;
        printf("\n");
    }
}

int main() {
    int num_rows, num_cols, num_nonzeros;

    // 매트릭스 읽기
    matrix_pointer matrix = mread();


    // 매트릭스 출력
    mwrite(matrix, num_rows, num_cols);

    return 0;
}

뒤의 코드를 전부 해체분석 해보겠습니다.
먼저 행의 head = 열의 head는 동일하게 취급합니다.
어차피 사용법은 똑같기 때문이죠. 그러나 어떤 한 쪽이 더 길 수도 있으므로 그 긴 쪽으로 맞춰줍니다.

그리고 행렬의 길의를 받아오고 희소행렬을 받아옵니다.

먼저 비제로 요소들을 초기화 시킨뒤, 비제로 요소들을 right, down으로 서로 link시킵니다.
또한 head node를 서로 원형 리스트로 연결시켜 순환, 탐색할 수 있습니다