データ構造実機実験レポート2——疎行列乗算

2023-12-12 2023-12-12

問題分析

本実験の主な目標は、2つの疎行列AとBを乗算し、結果行列Cを出力する疎行列乗算アルゴリズムを開発することです。このアルゴリズムでは、疎行列は3項組で表現され、ユーザーは異なる行列データを複数回入力し、それらの積を計算できます。

アルゴリズム設計

疎行列乗算アルゴリズムの設計は以下の通りです：

行列を表現するためにstruct構造体を使用し、行列の行数、列数、疎行列要素の数、およびノード情報を格納する配列を含みます。
入力関数inputは行列の3項組表現を取得し、入力の合法性をチェックしてからメモリ内の構造体に格納します。
出力関数outputは疎行列を標準的な行列形式で表示し、ユーザーが確認できるようにします。
行列乗算関数multiplierは2つの入力行列AとBを受け取り、それらの積を計算して結果を行列Cに格納します。

データ構造設計

matrix構造体には、行数m、列数n、疎行列要素の数L、およびノード情報を格納するMa配列が含まれます。
node構造体は疎行列の各非ゼロ要素を表し、行インデックスi、列インデックスj、および要素の値dataを含みます。

デバッグ過程

コードには、入力が合法かどうかのチェック、メモリ割り当てが成功したかどうかのチェック、行列乗算が合法かどうかのチェックなど、いくつかのエラー処理メカニズムがあります。
疎行列データを入力する際、ユーザーはエラーメッセージを受け取り、行列のサイズに合致するデータを再入力するよう求められます。
疎行列乗算アルゴリズムでは、行列の列と行が一致するかどうかがチェックされ、乗算可能かどうかが確認されます。

出力結果

Pasted image 20231020161652.png Matlab検証結果： Pasted image 20231020161908.png Pasted image 20231020161929.png

ユーザーは2つの行列AとBを入力でき、プログラムはそれらの積を計算して結果行列Cを出力します。ユーザーは疎行列乗算計算を続けるか、プログラムを終了するかを選択できます。プログラムはユーザーが終了を選択するまで実行され続けます。

まとめ

全体として、この実験は疎行列の乗算操作を成功裏に実装し、入力行列データが有効であることを保証するためのユーザーフレンドリーなインターフェースとエラー処理メカニズムを提供しました。そして、2つの疎行列の積を正しく計算し、結果を標準的な行列形式で出力しました。

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000

struct node{
    int i;
    int j;
    int data;
};
struct matrix{
    int m;
    int n;
    int L;
    node* Ma[MAX];
};

int input(matrix* A){
    int m,n,data;
    for(int i=0;i<A->L;i++){
        cin>>m>>n>>data;
        if(m<0||m>=A->m||n<0||n>=A->n){
            cout<<"入力エラー,行/列が行列サイズを超えています!"<<endl;
            return 1;
        }
        A->Ma[i]=(node*)malloc(sizeof(node));
        if(!A->Ma[i]){
            cout<<"メモリ割り当て失敗!"<<endl;
            return 2;
        }else{
            A->Ma[i]->i=m;
            A->Ma[i]->j=n;
            A->Ma[i]->data=data;
        }
    }
    return 0;
}

void output(matrix* A,string name){
    cout<<"行列"<<name<<"は:"<<endl;
    int nums[A->m][A->n];

    memset(nums,0,sizeof(nums));
    for(int i=0;i<A->L;i++){
        nums[A->Ma[i]->i][A->Ma[i]->j]=A->Ma[i]->data;
    }
    for(int i=0;i<A->m;i++){
        for(int j=0;j<A->n;j++){
            cout<<nums[i][j]<<'\t';
        }
        cout<<endl;
    }
}

void multiplier(matrix* A,matrix* B,matrix* C){
    C->m=A->m;
    C->n=B->n;
    C->L=0;
    int x,y,z;
    bool sert=false;
    for(int i=0;i<A->L;i++){
        for(int j=0;j<B->L;j++){
            if(A->Ma[i]->j==B->Ma[j]->i){//Aの列番号==Bの行番号
                x=A->Ma[i]->i;
                y=B->Ma[j]->j;
                z=A->Ma[i]->data*B->Ma[j]->data;
                sert=false;
                for(int k=0;k<C->L;k++){
                    if(x==C->Ma[k]->i&&y==C->Ma[k]->j){
                        C->Ma[k]->data+=z;
                        sert=true;
                        break;
                    }
                }
                if(!sert){
                    C->L++;
                    C->Ma[C->L-1]=(node*)malloc(sizeof(node));
                    C->Ma[C->L-1]->i=x;
                    C->Ma[C->L-1]->j=y;
                    C->Ma[C->L-1]->data=z;
                }
            }
        }
    }
}

int main(){
start:
    matrix* A=(matrix*)malloc(sizeof(matrix));
    matrix* B=(matrix*)malloc(sizeof(matrix));
    matrix* C=(matrix*)malloc(sizeof(matrix));
    cout<<"行列Aの3項組の長さ、行数、列数を入力してください:"<<endl;
    cin>>A->L>>A->m>>A->n;
    cout<<"行列Aを入力してください:"<<endl;
    if(input(A)){
        cout<<"エラーが発生しました、再入力してください!"<<endl;
        goto start;
    }
    output(A,"A");
    cout<<"行列Bの3項組の長さ、行数、列数を入力してください:"<<endl;
    cin>>B->L>>B->m>>B->n;
    cout<<"行列Bを入力してください:"<<endl;
    if(input(B)){
        cout<<"エラーが発生しました、再入力してください!"<<endl;
        goto start;
    }
    output(B,"B");
    multiplier(A,B,C);
    output(C,"C");

    cout<<"疎行列乗算計算を続けますか(y/n):";
    char choice;
choise:
    cin>>choice;
    if(choice=='y'||choice=='Y'){
        goto start;
    }else if(choice=='n'||choice=='N'){
        return 0;
    }else{
        cout<<"入力エラー、再入力してください:";
        goto choise;
    }
    return 0;
}

新しいバージョンが見つかりました