資料結構實機實驗報告2——稀疏矩陣乘法

2023-12-12 2023-12-12

問題分析

本實驗的主要目標是開發一個稀疏矩陣乘法演算法，該演算法能夠將兩個稀疏矩陣 A 和 B 相乘，然後輸出結果矩陣 C。在這個演算法中，稀疏矩陣使用三元組表示，並且使用者可以多次輸入不同的矩陣數據，計算它們的乘積。

演算法設計

稀疏矩陣乘法演算法的設計如下：

使用 struct 結構體來表示矩陣，其中包括矩陣的行數、列數、稀疏矩陣元素的個數，以及一個陣列用於儲存節點的資訊。
輸入函數 input 用於獲取矩陣的三元組表示，檢查輸入的合法性，然後儲存在記憶體中的結構體中。
輸出函數 output 將稀疏矩陣以標準矩陣的形式打印出來，便於使用者查看。
矩陣乘法函數 multiplier 接受兩個輸入矩陣 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

使用者可以輸入兩個矩陣 A 和 B，然後程式會計算它們的乘積並輸出結果矩陣 C。使用者可以選擇繼續進行稀疏矩陣乘法計算，也可以選擇退出程式。程式會一直運行，直到使用者選擇退出。

總結

總體而言，該實驗成功實現了稀疏矩陣的乘法操作，提供了友好的使用者介面和錯誤處理機制，以確保輸入的矩陣數據是有效的。然後，它正確計算了兩個稀疏矩陣的乘積並將結果以標準矩陣的形式輸出。

原始碼

#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矩陣三元組長度,矩陣行數,矩陣列數:"<<endl;
    cin>>A->L>>A->m>>A->n;
    cout<<"請輸入A矩陣:"<<endl;
    if(input(A)){
        cout<<"出現錯誤,請重新輸入!"<<endl;
        goto start;
    }
    output(A,"A");
    cout<<"請輸入B矩陣三元組長度,矩陣行數,矩陣列數:"<<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;
}

發現新版本