数据结构基于压缩存储的半三角矩阵乘法运算的实现

43次阅读

共计 2407 个字符,预计需要花费 7 分钟才能阅读完成。

题目要求

已知两个 n×n 阶方阵 A 和 B 的上半三角(不含主对角线上元素)元素全为 0,计算并输出这两个矩阵的乘积 C =A×B。根据矩阵乘法性质可知,C 矩阵的上半角三角元素(不含主对角线上元素)必然全为 0。
要求 A、B、C 三个矩阵均采用行序为主序顺序存储其下半三角元素 (含主对角线上元素)。程序先从键盘(或字符文件) 输入 n 值,建立三个矩阵的一维数组动态存储结构,然后从键盘 (或字符文件) 输入两个半三角矩阵,最后输出计算结果到屏幕上(或另一个字符文件中)。

例如:键盘 (或字符文件) 输入为:
3
1
2 3
4 5 6
-1
-2 -3
-4 -5 -6
则屏幕 (或字符文件) 输出为:
-1
-8 -9
-38 -45 -36

数据结构设计

用一维数组,定义三个矩阵:a、b、c。矩阵 a 和矩阵 b 通过文件读入,相乘结果保存在矩阵 c 中,并输出到文件中保存。

算法设计简要描述

下三角矩阵的特点是:i≤j,C 语言数组按行序为主序,在元素 a(i,j)之前需存储 i 行元素(行下标 0~i-1),在第 i 行上,a(i,j)之前存储有 j 个元素(行下标 0~j-1),故

程序代码

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
void Read(int *a, char *filename, int n)// 读取文件,a 为矩阵名,filename 为文件名,n 为矩阵阶数
{
    int i = 0, c;
    ifstream infile(filename);
    if (!infile)                        // 打开文件失败输出提示信息
    {
        cout << "file open error!" << endl;
        exit(0);
    }
    while (1)                               
    {
        infile >> c;
        if (infile.eof())
            break;
        a[i] = c;
        if (i + 1 == n*(n + 1) / 2)   // 读取元素个数达到最大,跳出循环
            break;
        i++;
    }
    infile.close();}
void Write(int *a, char *filename,int n)// 写入文件,a 为矩阵名,filename 为文件名,n 为矩阵阶数
{
    int i = 0, j = 0;
    ofstream outfile(filename);
    if (!outfile)                     // 打开文件失败输出提示信息
    {
        cout << "file open error!" << endl;
        exit(0);
    }
    else
        cout << "存储成功!" << endl;
    for (i = 0, j = 1; i < n*(n + 1) / 2; i++)    // 将元素按矩阵形式存到文件中
    {outfile << setw(5) << a[i];
        if ((i + 1) == j*(j + 1) / 2)
        {
            j++;
            outfile << endl;           // 每行元素达到最大,输出换行
        }
    }
    outfile.close();}
void Mutiply(int *a, int *b, int *c, int n)// 两个矩阵相乘, 矩阵 c = 矩阵 a * 矩阵 b,n 为矩阵阶数
{
    int i, j, k, m = 0, sum = 0;    // m 记录数组 c 的下标,sum 为矩阵 c 每个位置元素的计算结果
    for (i = 0; i < n; i++)         // 从 0 到 n 按行扫描
    {for (j = 0; j <= i; j++)    // 从 0 到 i 按列扫描
        {for (k = j; k <= i; k++)// 从 j 到 i 将矩阵 a 与矩阵 b 相乘
            {sum += a[i*(i + 1) / 2 + k] * b[k*(k + 1) / 2 + j];
                c[m] = sum;
            }
            sum = 0;
            m++;
        }
    }
}
void Print(int *a,int n)            // 输出函数,a 为矩阵名,n 为矩阵阶数
{
    int i, j;
    for (i = 0, j = 1; i < n*(n + 1) / 2; i++)
    {cout << setw(5) << a[i];
        if ((i + 1) == j*(j + 1) / 2)      // 将元素按矩阵形式输出
        {
            j++;
            cout << endl;
        }
    }
}
int main()
{
    int *a, *b, *c, n, m = 0, j = 0;
    char filename1[20], filename2[20], filename3[20];/*filename1 记录保存矩阵 a 的文件名,filename2 记录保存
                                                矩阵 b 的文件名,filename3 记录保存矩阵 c 的文件名 */
    cout << "请输入 n 的值:";               // 输入矩阵阶数
    cin >> n;
    a = new int[n * (n + 1) / 2];          // 分别建立三个数组,n * (n + 1) / 2 为数组中的元素个数
    b = new int[n * (n + 1) / 2];
    c = new int[n * (n + 1) / 2];
    a[n * (n + 1) / 2] = b[n * (n + 1) / 2] = c[n * (n + 1) / 2] = {0};// 初始化所有元素为 0
    cout << "请输入保存矩阵 A 的文件名:";     // 输入保存矩阵 a 的文件名
    cin >> filename1;
    Read(a, filename1, n);                  // 读取矩阵 a
    cout << "请输入保存矩阵 B 的文件名:";     // 输入保存矩阵 b 的文件名
    cin >> filename2;
    Read(b, filename2, n);                 // 读取矩阵 b
    cout << "矩阵 A 为:" << endl;
    Print(a, n);                           // 打印矩阵 a
    cout << "矩阵 B 为:" << endl;
    Print(b, n);                           // 打印矩阵 b
    Mutiply(a, b, c, n);                   // 将矩阵 a 与矩阵 b 相乘,结果保存在矩阵 c 中
    cout << "矩阵 C 为:" << endl;
    Print(c, n);                           // 打印矩阵 c
    cout << "请输入要存储矩阵 C 的文件名:";
    cin >> filename3;
    Write(c, filename3, n);                // 将矩阵 c 保存在文件中
    return 0;
}

示例

(1)程序输入
n = 3
矩阵 A:
1
2 3
4 5 6
矩阵 B:
-1
-2 -3
-4 -5 -6

程序输出
矩阵 C:
-1
-8 -9
-38 -45 -36

(2)程序输入
n = 5
矩阵 A:
10
-6 5
8 -9 4
2 3 9 10
1 -5 -4 2 7
矩阵 B:
5
10 12
-6 -3 -2
1 5 -9 8
-4 -6 2 1 3

程序输出
矩阵 C:
50
20 60
-74 -120 -8
-4 59 -108 80
-47 -80 4 23 21

正文完
 0