用户登录
用户注册

分享至

行逻辑链接的顺序表实现矩阵乘法（附带C语言完整代码）

  • 作者: 黄山小妖是我老婆
  • 来源: 51数据库
  • 2022-09-29

解题思路:


    ① 只需要计算两矩阵非0元素间的乘法；

    ② 使用行逻辑链接可得到该行首个非0元位置，也可以间接得到该行非0元个数；

    ③ 在行逻辑链接的基础上，可以成行确定Q的元素，即需要M该行的遍历 + N全行的遍历。



参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<stdio.h>
#include<malloc.h>
#include<string.h>
 
typedef struct Triple {
    int i, j; // 所在行、列
    int data; // 数值
} Triple;
 
typedef struct RL**atrix {
    Triple *data;
    int *rpos; // 记录每行首个非0元的位置
    int mu, nu, tu; // 行、列、非0元个数
} RL**atrix;
 
// 创建行逻辑链接的顺序表
void CreateRL**atrix(RL**atrix *M);
// 矩阵乘法，在M中遍历非0元进行
void MultRL**atrix(RL**atrix *M, RL**atrix *N, RL**atrix *Q);
// 按行输出矩阵
void DisplayRL**atrix(RL**atrix *Q);
 
int main()
{
    RL**atrix M, N, Q;
    M.data = NULL; M.rpos = NULL;
    N.data = NULL; N.rpos = NULL;
    Q.data = NULL; Q.rpos = NULL;
    CreateRL**atrix(&M);
    CreateRL**atrix(&N);
    MultRL**atrix(&M, &N, &Q);
    DisplayRL**atrix(&Q);
    return 0;
}
 
void CreateRL**atrix(RL**atrix *M) {
    int i, j, data, size;
    M->tu = 1;
    scanf("%d%d", &M->mu, &M->nu);
    M->data = (Triple *)malloc(sizeof(Triple) * M->nu * 2);
    M->rpos = (int *)malloc(sizeof(int) * (M->mu + 1));
    size = M->nu * 2;
    for (i = 1; i <= M->mu; i++) {
        M->rpos[i] = M->tu; // 该行首个非0元位置在上一行输入完时确定
        for (j = 1; j <= M->nu; j++) {
            scanf("%d", &data);
            if (data) { // 存放非0元
                    // 注意这里第0个位置不存放非0元，从第1个开始，和行逻辑对应
                M->data[M->tu].i = i;
                M->data[M->tu].j = j;
                M->data[M->tu++].data = data;
            }
        }
        if (size - M->tu < M->nu) {
            M->data = (Triple *)realloc(M->data, sizeof(Triple) * (size + M->nu));
            size += M->nu;
        }
    }
    M->tu--; // 此前始终比非0元个数大1，此时减去
}
 
void MultRL**atrix(RL**atrix *M, RL**atrix *N, RL**atrix *Q) {
    int i, j, k1, k2, k3, k4, row, col, size, *temp;
    Q->mu = M->mu;
    Q->nu = N->nu;
    Q->tu = 0;
    Q->data = (Triple *)malloc(sizeof(Triple) * Q->nu * 2);
    size = Q->nu * 2;
    // temp暂时存放乘积结果，每次存放Q[i]行的结果，个数为N的列数
    temp = (int *)malloc(sizeof(int) * (Q->nu + 1));
    for (row = 1; row <= M->mu; row++) { // 遍历M每行的非0元
        memset(temp, 0, sizeof(int) * (Q->nu + 1)); // 每行都需要将temp重置
        k1 = M->rpos[row]; // 获取该行首个非0元
        if (row == M->mu) {
            k2 = M->tu + 1; // 若是最后一行，直接遍历完
        }
        else {
            k2 = M->rpos[row + 1]; // 否则，遍历完到下一行首个非0元之前
        }
        // M中从k1遍历到k2
        while (k1 < k2) {
            j = M->data[k1].j; // 获取非0元在M中的所在列
            k3 = N->rpos[j]; // 找到对应N的那行
            if (j == N->mu) {
                k4 = N->tu + 1;
            }
            else {
                k4 = N->rpos[j + 1];
            }
            // 对M中每个非0元取所在列，在N中找到对应行非0元，记录分积
            while (k3 < k4) {
                col = N->data[k3].j; // 获取N中该非0元所在列
                temp[col] += M->data[k1].data * N->data[k3].data;
                k3++;
            }
            k1++;
        }
        // 当M的该行遍历完成，Q的该行元素全部确定
        for (i = 1; i <= Q->nu; i++) {
            if (temp[i]) { // 只存放非0元
                Q->data[++Q->tu].i = row;
                Q->data[Q->tu].j = i;
                Q->data[Q->tu].data = temp[i];
            }
        } // 偷懒，没有进行Q的行逻辑链接。
        if (size - Q->tu < Q->nu) {
            Q->data = (Triple *)realloc(Q->data, sizeof(Triple) * (size + Q->nu));
            size += Q->nu;
        }
    }
}
 
void DisplayRL**atrix(RL**atrix *Q) {
    int i, j, k = 1;
    for (i = 1; i <= Q->mu; i++) {
        for (j = 1; j <= Q->nu; j++) {
            if (Q->data[k].i == i && Q->data[k].j == j) {
                printf("%d ", Q->data[k++].data);
            }
            else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}



推荐阅读
热点文章

Copyright 2018 51数据库(www.51sjk.com)

软件
前端设计
程序设计
Java相关