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

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

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

14
int main(void) {
15
    MatrixRep *matrixRepFrontA, *matrixRepFrontB, *matrixRepFrontC;
16

17
    //輸入兩組一般矩陣且直接轉表示式
18
    inputMatrixRep("A", &matrixRepFrontA);      //輸入矩陣A且直接轉表示式A
19
    printMatrixRep("A", &matrixRepFrontA);      //印出表示式A
20
    printf("====================\n");
21
    inputMatrixRep("B", &matrixRepFrontB);      //輸入矩陣B且直接轉表示式B
22
    printMatrixRep("B", &matrixRepFrontB);      //印出表示式B
23
    printf("====================\n");
24

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

35
    system("pause");
36
    return 0;
37
}
38

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

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

52
    printf("請輸入矩陣%s的大小（m*n請輸入 m n）:\n", matrixName);
53
  scanf("%d%d", &(current->row), &(current->col));            //存表示式第0列的row及col
54
    current->value = 0;                                         //將第0列的value設為0
55
    current->next = NULL;                                       //將第0列尾端設為空
56

57
  printf("請輸入矩陣%s的元素 :\n", matrixName);
58
  for (int i = 0; i next->row; i++)
59
    for (int j = 0; j next->col; j++){
60
      scanf("%d", &num);                                  //讀入矩陣元素
61
            if(num!=0){                                         //若元素非0，存入表示式新的一列
62
                ((*front)->next->value)++;
63
                current = current->next = new MatrixRep{i, j, num, NULL};
64
                /*等同C的
65
                  current = current->next = (MatrixRep *)malloc(sizeof(MatrixRep));
66
                  current->row=i; current->col=j; current->value=num; current->next=NULL;*/
67
            }
68
        }
69
}
70

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

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

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

113
/*-----印出表示式轉矩陣-----*/
114
void printMatrix(char *matrixName, MatrixRep **front){
115
    MatrixRep *cur=(*front)->next->next;
116
    printf("矩陣%s：\n", matrixName);
117
    for(int i = 0; i next->row; i++){
118
        for(int j = 0; j next->col; j++){
119
            if(cur != NULL && i == cur->row && j == cur->col){
120
                printf("%2d ", cur->value);
121
                cur = cur->next;
122
            }else{
123
                printf("%2d ", 0);
124
            }
125
        }
126
        putchar('\n');
127
    }
128
}
129

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