iT邦幫忙

0

【資料結構】矩陣的相關處理筆記

矩陣的相關處理

目錄:

0.前言

1.矩陣設置

2.矩陣相乘

3.稀疏矩陣

4.稀疏矩陣的普通轉置

5.矩陣的轉置後相乘

6.快速稀疏矩陣轉置演算法

前言

期中快到ㄌ

最近打算把學到的觀念都弄成筆記整理,對內容也能更深的了解

小弟只是剛接觸程式半年的菜雞,若有觀念錯誤或不佳處還請見諒QQ

it邦連結,這邊排版比較好用

矩陣設置

主程式

int main()
{
    Data Matrix1;
    set_size(&Matrix1);
    set_content(&Matrix1);
    show_content(Matrix1);
}

GITHUB

相關函式

Data:矩陣結構
struct data
{
    int row;
    int col;
    int content[MAX][MAX];
};
typedef struct data Data;
set_size:設定陣列大小
void set_size(Data *Matrix)
{
    do
    {
        printf("輸入row:");
        scanf("%d", &Matrix->row);
        printf("輸入col:");
        scanf("%d", &Matrix->col);
    } while (Matrix->row <= 0 || Matrix->col <= 0);
}
set_content:設定矩陣內容
void set_content(Data *Matrix)
{
    for (int i = 0; i < Matrix->row; i++)
    {
        for (int j = 0; j < Matrix->col; j++)
        {
            scanf("%d", &(Matrix->content[i][j]));
        }
        printf("\n");
    }
}
show_content:印出矩陣
void show_content(Data Matrix)
{
    printf("距陣為:\n");
    for (int i = 0; i < Matrix.row; i++)
    {
        for (int j = 0; j < Matrix.col; j++)
        {
            printf("%d\t", Matrix.content[i][j]);
        }
        printf("\n");
    }
}

矩陣暴力相乘

主程式

int main()
{
    Data Matrix1, Matrix2, Matrix3;
    Sparse content1[MAX], content2[MAX], content3[MAX];
    set(&Matrix1, &Matrix2, &Matrix3);
    Mult(Matrix1, Matrix2, &Matrix3);
    show_content(Matrix3);
}

GITHUB

set:設定相乘的三個矩陣

void set(Data *M1, Data *M2, Data *M3)
{
    do
    {
        set_size(&*M1);
        set_content(&*M1);
        set_size(&*M2);
        set_content(&*M2);
    } while (M1->col != M2->row);
    show_content(*M1);
    show_content(*M2);
    M3->row = M1->row;
    M3->col = M2->col;
}

Mult:暴力相乘

void Mult(Data M1, Data M2, Data *M3)
{
    for (int i = 0; i < M1.row; i++)
    {
        for (int j = 0; j < M2.col; j++)
        {
            int all = 0;
            for (int k = 0; k < M2.row; k++)
            {
                all += M1.content[i][k] * M2.content[k][j];
            }
            M3->content[i][j] = all;
        }
    }
}

稀疏矩陣

主程式

int main(){
    Data Matrix1;
    Sparse content1[MAX];
    set_size(&Matrix1);
    set_content(&Matrix1);
    show_content(Matrix1);
    matrix_to_sparse(Matrix1, content1);
    show_sparse(content1);
}

GITHUB

Sparse:稀疏矩陣結構
struct sparse
{
    int row;
    int col;
    int content;
};
typedef struct sparse Sparse;
matrix_to_sparse:矩陣轉稀疏結構
void matrix_to_sparse(Data Matrix, Sparse sparse_Matrix[])
{
    int k = 1;
    for (int i = 0; i < Matrix.row; i++)
    {
        for (int j = 0; j < Matrix.col; j++)
        {
            if (Matrix.content[i][j] != 0)
            {
                sparse_Matrix[k].content = Matrix.content[i][j];
                sparse_Matrix[k].row = j;
                sparse_Matrix[k].col = i;
                k++;
            }
        }
    }
    k--;
    sparse_Matrix[0].content = k;
    sparse_Matrix[0].row = Matrix.row;
    sparse_Matrix[0].col = Matrix.col;
}

稀疏矩陣的普通轉置

主程式

int main(){
    Data Matrix1;
    Sparse content1[MAX];
    set_size(&Matrix1);
    set_content(&Matrix1);
    printf("轉置前:");
    show_content(Matrix1);
    turn(&Matrix1, content1);
    printf("轉置後:");
    show_content(Matrix1);
}

GITHUB

turn:矩陣轉置

void turn(Data *Matrix, Sparse content[])
{
    change_matrix_to_sparse(*Matrix, content);
    sparse_to_matrix(&*Matrix, content);
}

change_matrix_to_sparse:稀疏矩陣的轉置

void change_matrix_to_sparse(Data Matrix, Sparse sparse_Matrix[])
{
    int k = 0;
    for (int i = 0; i < Matrix.col; i++)
    {
        for (int j = 0; j < Matrix.row; j++)
        {
            if (Matrix.content[j][i] != 0)
            {
                k++;
                sparse_Matrix[k].content = Matrix.content[j][i];
                sparse_Matrix[k].row = i;
                sparse_Matrix[k].col = j;
            }
        }
        sparse_Matrix[0].content = k;
        sparse_Matrix[0].row = Matrix.row;
        sparse_Matrix[0].col = Matrix.col;
    }
}

sparse_to_matrix:稀疏矩陣轉矩陣

void sparse_to_matrix(Data *Matrix, Sparse sparse_Matrix[])
{
    Matrix->col = sparse_Matrix[0].row;
    Matrix->row = sparse_Matrix[0].col;
    for (int i = 0; i < Matrix->row; i++)
    {
        for (int j = 0; j < Matrix->col; j++)
        {
            Matrix->content[i][j] = 0;
        }
    }
    int num = sparse_Matrix[0].content;
    for (int i = 1; i <= num; i++)
    {
        Matrix->content[sparse_Matrix[i].row][sparse_Matrix[i].col] = sparse_Matrix[i].content;
    }
}

矩陣的轉置後相乘

以下待補

快速稀疏矩陣轉置演算法

以下待補


尚未有邦友留言

立即登入留言