[C/C++] 單向鏈結實作矩陣相乘轉矩陣表示式

//定義一個串列結構，用來存表示式的每一列
typedef struct MatrixRep {
    int row, col, value;
    struct MatrixRep *next;
} MatrixRep;

void createMatrixRepList(MatrixRep **front);                                            //建立表示式結構的Front
void inputMatrixRep(char *matrixName, MatrixRep **front);                               //輸入表示式
MatrixRep *indexOfRep(int r, int c, MatrixRep **rep);                                   //找某[i,j]是否位於某表示式中的一個節點
void multipliedMatrixRep(MatrixRep **frontA, MatrixRep **frontB, MatrixRep **frontC);   //表示式直接相乘
void printMatrix(char *matrixName, MatrixRep **front);                                  //印出表示式轉矩陣
void printMatrixRep(char *matrixName, MatrixRep **front);                               //印出表示式

int main(void) {
    MatrixRep *matrixRepFrontA, *matrixRepFrontB, *matrixRepFrontC;
    
    //輸入兩組一般矩陣且直接轉表示式
    inputMatrixRep("A", &matrixRepFrontA);      //輸入矩陣A且直接轉表示式A
    printMatrixRep("A", &matrixRepFrontA);      //印出表示式A
    printf("====================\n");
    inputMatrixRep("B", &matrixRepFrontB);      //輸入矩陣B且直接轉表示式B
    printMatrixRep("B", &matrixRepFrontB);      //印出表示式B
    printf("====================\n");

    //判斷能不能相乘
    if(matrixRepFrontA->next->col == matrixRepFrontB->next->row){
        multipliedMatrixRep(&matrixRepFrontA, &matrixRepFrontB, &matrixRepFrontC);  //兩組表示式直接相乘存入表示式C
        printMatrix("C", &matrixRepFrontC);                                         //印出矩陣C
        printMatrixRep("C", &matrixRepFrontC);                                      //印出表示式C
    }
    else{
        printf("兩個矩陣無法相乘\n");
    }

    system("pause");
    return 0; 
}

/*-----建立表示式結構的Front-----*/
void createMatrixRepList(MatrixRep **front){
    (*front) = new MatrixRep;  //等同C的 (**front) = (MatrixRep *)malloc(sizeof(MatrixRep));
    (*front)->next = NULL;
}

/*-----輸入表示式-----*/
void inputMatrixRep(char *matrixName, MatrixRep **front){
    int num;
    createMatrixRepList(front);                                 //建立表示式結構的Front【front為&(*front)的縮寫】
    MatrixRep *current = (*front)->next = new MatrixRep;
    //等同C的 MatrixRep *current = (*front)->next = (MatrixRep *)malloc(sizeof(MatrixRep));

    printf("請輸入矩陣%s的大小（m*n請輸入 m n）:\n", matrixName);
	scanf("%d%d", &(current->row), &(current->col));            //存表示式第0列的row及col
    current->value = 0;                                         //將第0列的value設為0
    current->next = NULL;                                       //將第0列尾端設為空
    
	printf("請輸入矩陣%s的元素 :\n", matrixName);               
	for (int i = 0; i < (*front)->next->row; i++)
		for (int j = 0; j < (*front)->next->col; j++){
			scanf("%d", &num);                                  //讀入矩陣元素
            if(num!=0){                                         //若元素非0，存入表示式新的一列
                ((*front)->next->value)++;
                current = current->next = new MatrixRep{i, j, num, NULL};
                /*等同C的
                  current = current->next = (MatrixRep *)malloc(sizeof(MatrixRep));
                  current->row=i; current->col=j; current->value=num; current->next=NULL;*/
            }
        }
}

/*-----找某[i,j]是否位於某表示式中的一個節點-----*/
MatrixRep *indexOfRep(int r, int c, MatrixRep **rep){
    for(MatrixRep *cur=(*rep)->next->next; cur!=NULL; cur=cur->next)
        if(cur->row == r && cur->col == c)
            return cur;
    return NULL;
}

/*-----表示式直接相乘-----*/
void multipliedMatrixRep(MatrixRep **frontA, MatrixRep **frontB, MatrixRep **frontC){
    createMatrixRepList(frontC);              //建立表示式結構的Front【frontC為&(*frontC)的縮寫】
    MatrixRep *currentA = (*frontA)->next;    //currentA指向表示式A的第0列
    MatrixRep *currentB = (*frontB)->next;    //currentB指向表示式B的第0列
    MatrixRep *currentC = (*frontC)->next = new MatrixRep{currentA->row, currentB->col, 0, NULL};
    /*等同C的
      MatrixRep *currentC = (*frontC)->next = (MatrixRep *)malloc(sizeof(MatrixRep));
      currentC->row=currentA->row; currentC->col=currentB->col;
      currentC->value=0; currentC->next=NULL;*/

    //相乘
    for(currentA = currentA->next; currentA!=NULL; currentA = currentA->next){
        for(currentB = (*frontB)->next->next; currentB!=NULL; currentB = currentB->next){
            //依數學定義，給定任兩數分別位於矩陣A[i,j]與矩陣B[s,t]，若且唯若j=s時，此兩數之乘積會累加於C[i,t]中
            //故遍歷表示式A，表示式A之每數再遍歷表示式B，當curA->col == curB->row時，即有非零乘積產生
            if(currentA->col == currentB->row){
                //若目前C[i,j]已存在於表示式C中，則累加進去，否則就宣告一個新的節點來放
                MatrixRep *findC = indexOfRep(currentA->row, currentB->col, frontC);   //找C[i,j]是否存在於表示式C中【frontC為&(*frontC)的縮寫】
                if((*frontC)->next->value>0 && findC!=NULL){
                    findC->value += currentA->value * currentB->value;
                }else{ 
                    ((*frontC)->next->value)++; //已紀錄的元素個數+1
                    currentC = currentC->next = new MatrixRep{currentA->row, currentB->col, currentA->value * currentB->value, NULL};
                    /*等同C的
                      currentC = currentC->next = (MatrixRep *)malloc(sizeof(MatrixRep));
                      currentC->row=currentA->row; currentC->col=currentB->col;
                      currentC->value=currentA->value*currentB->value; currentC->next=NULL;*/
                }
            }
        }
    }
}

/*-----印出表示式轉矩陣-----*/
void printMatrix(char *matrixName, MatrixRep **front){
    MatrixRep *cur=(*front)->next->next;
    printf("矩陣%s：\n", matrixName);
    for(int i = 0; i < (*front)->next->row; i++){
        for(int j = 0; j < (*front)->next->col; j++){
            if(cur != NULL && i == cur->row && j == cur->col){
                printf("%2d ", cur->value);
                cur = cur->next;
            }else{
                printf("%2d ", 0);
            }
        }   
        putchar('\n');
    }
}

/*-----印出表示式-----*/
void printMatrixRep(char *matrixName, MatrixRep **front){
	printf("矩陣%s的表示式:\n 列 行 元素\n", matrixName);
    for(MatrixRep *cur=(*front)->next; cur!=NULL; cur=cur->next)
        printf("%2d %2d %2d\n", cur->row, cur->col, cur->value);
}