稀疏矩阵的加，减，乘，转置

1　需求分析

稀疏矩阵是指哪些多元素为零的矩阵。利用“稀疏的特点”进行储存和计算可以打打节省储存空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

以“带行逻辑链接信息”的三元组标表示稀疏矩阵，实现矩阵的转置，实现两个矩阵相加，相减和相乘的运算。稀疏矩阵的输入形势采用三元组表示，而运算结果的矩阵则以通常的阵列形势列出。

演示程序以用户和计算机的对话法师执行，数组的建立方式为边输入边建立。

由题目要求可知：首先应该输入矩阵的行数和列数，并判别给出的两个矩阵的行数，列数对于所要求作的运算是否相互匹配。

程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时，不会产生错误。

程序在vc6.0环境下设计。程序执行命令为：1.稀疏矩阵的转置；2.稀疏矩阵的乘法；3.稀疏矩阵的加法；4.稀疏矩阵的减法；5.退出；的工作。

1.1　用户角度

（1）从界面选择一种算法并输入一个或两个稀疏矩阵，输出运算的正确结果。

（2）界面简洁，操作方便。

1.2　开发工具的特点

Visual C++  6.0版本：

（1）具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点。

（2）界面简洁，占用资源少，操作方便。

（3）拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。

2　概要设计

                           图2.1

 

 

1．  基本操作：

InputTSMatrix

操作结果：输入三元组矩阵

OutputSMatrix

初始条件：矩阵已经存在

操作结果：输出矩阵

TranSMatrix()

初始条件：矩阵已经存在

操作结果：转置输入的矩阵

FastTranMat()

初始条件：矩阵已经存在

操作结果：快速转置输入的矩阵

MultSMatrix()

初始条件：矩阵A和矩阵B已经存在

操作结果：求矩阵A和矩阵B的积

AddMatrix()

初始条件：矩阵A和矩阵B已经存在

操作结果：求矩阵A和矩阵B的和

SubMatrix()

初始条件：矩阵A和矩阵B已经存在

操作结果：求矩阵A和矩阵B的减

 

 

 

模块调运关系如下：

3　详细设计

3.1定义储存矩阵三元组结构

#include <stdio.h>

#include <iomanip>

 

const int MAXSIZE = 100;        //定义非零元素的最多个数

const int MAXROW = 10;            //定义数组行数的最大值

const int SIZENUM = 10;

 

typedef struct                    //定义三元组元素

{

  int r, c;                    //矩阵的行号和列号

  int v;                        //矩阵元素值

}Triple;

 

typedef struct                    //定义普通三元组对象

{

  Triple data[MAXSIZE+1];

  int rpos[MAXROW+1];

  int rows, cols, nzeroNums;    //行数、列数、非零元素个数

}TSMatrix;

稀疏矩阵的三元组顺序表：为了节省存储空间，同样对稀疏矩阵进行压缩存储，即只存储稀疏矩阵的非零元素。但是为了实现矩阵的各种运算，还要必须同时记下他的行号和列号。这样，一个三元组（i，j，Aij）便唯一的确定了矩阵中的非零元素，其中i，j分别表示非零元素的行号和列号，Aij则表示非零元素的值。

3.2主要模块的详细分析

3.2.1　矩阵的主程序模块

Main函数主控调用其他模块并描述了以下界面：

 

3.2.1　矩阵的构造模块

void InputTSMatrix(TSMatrix *M)

{

   printf("输入矩阵的行数、列数和非零元素个数: ");

   scanf("%d%d%d",&M->rows,&M->cols,&M->nzeroNums);

   printf("请输入非零元素对应的行号、列号和相应的元素值:\n ");

   for (int i = 1; i <= M->nzeroNums; i++)

   {

       scanf("%d%d%d",&M->data[i].r,&M->data[i].c,&M->data[i].v);

   }

}

3.2.1　矩阵的运算模块

1）矩阵的转置

void TranSMatrix()

{

   TSMatrix M, T;

   InputTSMatrix(&M);

   int col, p, q = 1;

   T.rows = M.cols;

   T.cols = M.rows;

   T.nzeroNums = M.nzeroNums;

   if (T.nzeroNums)

   {

       for (col = 1; col <= M.cols; col++)

       {

          for (p = 1; p <= M.nzeroNums; p++)

          {

              if (M.data[p].c == col)

              {

                 T.data[q].r = M.data[p].c;

                 T.data[q].c = M.data[p].r;

                 T.data[q].v = M.data[p].v;

                 ++q;

              }

          }

       }

   }

   printf("运用普通转置算法, 输入矩阵的转置矩阵为:\n ");

    OutputSMatrix(T);

稀疏矩阵的转置的实现规则：

1.将矩阵的行列值相互交换。2.每个三元组的i、j相互交换。3.重新排列三元组之间的次序便可实现转置

 

2）矩阵的快速转置

void FastTranMat()

{

   TSMatrix M, T;

   int num[MAXROW+1];        //表示矩阵M中第col列非零元素的个数

   int cpot[MAXROW+1];        //表示矩阵M中第col列第一个非0元素在b.data中的位置

   int p, q, col, t;

   InputTSMatrix(&M);        //输入稀疏矩阵

   T.rows = M.cols;

   T.cols = M.rows;

   T.nzeroNums = M.nzeroNums;

   if (T.nzeroNums)

   {

       for (col = 1; col <= M.cols; col++)//M中各列元素初始化

       {

          num[col] = 0;

       }

       for (t = 1; t <= M.nzeroNums; t++)

       {

          ++num[M.data[t].c];            //求M中每一列非零元个数

       }

       //求第col列第一个非零元在b.data中的序号

       cpot[1] = 1;

       for (col = 2; col <= M.cols; col++)

       {

          cpot[col] = cpot[col-1] + num[col-1];

       }

       for (p = 1; p <= M.nzeroNums; p++)

       {

          col = M.data[p].c;         //稀疏矩阵M中每个元素对应的列号

          q = cpot[col];             //稀疏矩阵M中第一个非零元素位置

          T.data[q].r = M.data[p].c;

          T.data[q].c = M.data[p].r;

          T.data[q].v = M.data[p].v;

          ++cpot[col];

       }//end_for

   }//end_if

   printf("运用快速算法，输入矩阵的转置为:\n ");

   OutputSMatrix(T);

}

快速转置的思想是开辟两个数组用来存放每一行有效值的个数，另一个用来存转置后顺序表vector的起始位置。使得数组可以快速找到有效顺序在转置后顺序表里的位置。也就是说快速转置与普通转置比较来说快速转置更为有效计算机运算相对比较简单。

4）矩阵的加法

//两个稀疏矩阵的加法

int AddMatrix()

{

   TSMatrix A, B, C;

   int i = 1, j = 1, k = 1;    //i, j, k分别用以保存A、B、C非零元素个数

   int value = 0;

   InputTSMatrix(&A);

   InputTSMatrix(&B);

   if (A.rows != B.rows || A.cols != B.cols)

   {

       printf("两个稀疏矩阵的大小不等,不能相加!\n" );

       return 0;

   }

   if (A.rows == B.rows && A.cols == B.cols)

   {

       while (i <= A.nzeroNums && j <= B.nzeroNums)

       {

          if (A.data[i].r == B.data[j].r)

          {

              if (A.data[i].c < B.data[j].c)

              {

                 C.data[k].r = A.data[i].r;

                 C.data[k].c = A.data[i].c;

                 C.data[k].v = A.data[i].v;

                 k++;

                 i++;

              }

              else if (A.data[i].c > B.data[j].c)

              {

                 C.data[k].r = B.data[j].r;

                 C.data[k].c = B.data[j].c;

                 C.data[k].v = B.data[j].v;

                 k++;

                 j++;

              }

              else

              {

                 value = A.data[i].v + B.data[j].v;

                 if (value != 0)

                 {

                     C.data[k].r = A.data[i].r;

                     C.data[k].c = A.data[i].c;

                     C.data[k].v = value;

                     k++;

                 }

                 i++;

                 j++;

              }

          }

          else if (A.data[i].r < B.data[j].r)

          {

              C.data[k].r = A.data[i].r;

              C.data[k].c = A.data[i].c;

              C.data[k].v = A.data[i].v;

              k++;

              i++;

          }

          else

          {

              C.data[k].r = B.data[j].r;

              C.data[k].c = B.data[j].c;

              C.data[k].v = B.data[j].v;

              k++;

              j++;

          }//把剩余部分元素存入C中

          if (i > A.nzeroNums && j <= B.nzeroNums)

          {

              for (; j <= B.nzeroNums; j++)

              {

                 C.data[k].r = B.data[j].r;

                 C.data[k].c = B.data[j].c;

                 C.data[k].v = B.data[j].v;

                 k++;

              }

          }

          if (i <= A.nzeroNums && j > B.nzeroNums)

          {

              for (; i <= A.nzeroNums; i++)

              {

                 C.data[k].r = A.data[i].r;

                 C.data[k].c = A.data[i].c;

                 C.data[k].v = A.data[i].v;

                 k++;

              }

          }

       }

       C.rows = A.rows;

       C.cols = A.cols;

       C.nzeroNums = k-1;

       printf("输出两个稀疏矩阵的和:\n ");

       OutputSMatrix(C);

       return 1;

   }

   else

   return 0;

}

稀疏矩阵的加法：稀疏矩阵的加法与普通矩阵的加法一样，遵循普通矩阵的加法运算规则，也就是当矩阵A和矩阵B行数和列数必须相同才可以进行计算。

5）矩阵的减法

//两个稀疏矩阵的减法

int SubMatrix()

{

   TSMatrix A, B, C;

   int m = 1, n = 1, k = 1, temp;

   InputTSMatrix(&A);

   InputTSMatrix(&B);

   C.rows = A.rows;

   C.cols = A.cols;

   C.nzeroNums = 0;

   if (A.rows == B.rows && A.cols == B.cols)

   {

       while (m <= A.nzeroNums && n <= B.nzeroNums)

       {

          if (A.data[m].r == B.data[n].r)

          {

              if (A.data[m].c == B.data[n].c)

              {

                 temp = A.data[m].v - B.data[n].v;

                 if (temp != 0)

                 {

                     C.data[k].r = A.data[m].r;

                     C.data[k].c = A.data[m].c;

                     C.data[k].v = temp;

                     k++;

                 }

                 m++;

                 n++;

              }

              else if (A.data[m].c < B.data[n].c)

              {

                 C.data[k].r = A.data[m].r;

                 C.data[k].c = A.data[m].c;

                 C.data[k].v = A.data[m].v;

                 k++;

                 m++;

              }

              else

              {

                 C.data[k].r = B.data[n].r;

                 C.data[k].c = B.data[n].c;

                  C.data[k].v = -B.data[n].v;

                 k++;

                 n++;

              }

          }

          else if (A.data[m].r < B.data[n].r)

          {

              C.data[k].r = A.data[m].r;

              C.data[k].c = A.data[m].c;;

              C.data[k].v = A.data[m].v;

              k++;

              m++;

          }

          else

          {

              C.data[k].r = B.data[n].r;

              C.data[k].c = B.data[n].c;

              C.data[k].v = -B.data[n].v;

              k++;

              n++;

          }

       }//end_while

       if (m <= A.nzeroNums)

       {

          for (; m <= A.nzeroNums; m++)

          {

              C.data[k].r = A.data[m].r;

              C.data[k].c = A.data[m].c;

              C.data[k].v = A.data[m].v;

              k++;

          }

       }

       if (n <= B.nzeroNums)

       {

          for (; n <= B.nzeroNums; n++)

          {

              C.data[k].r = B.data[n].r;

              C.data[k].c = B.data[n].c;

              C.data[k].v = -B.data[n].v;

              k++;

          }

       }

       C.nzeroNums = k-1;

       printf("两个稀疏矩阵的差为:\n");

       OutputSMatrix(C);

       return 1;

   } //end_if

   else

   {

       printf("两个稀疏矩阵的大小不同，不能相减!\n");

       return 0;

   }

}

 

//得到矩阵元素M[i][j]的值

int value(TSMatrix M, int i, int j)

{

   int k;

   for (k = 1; k <= M.nzeroNums; k++)

   {

       if (M.data[k].r == i && M.data[k].c == j)

       {

          return M.data[k].v;

       }

   }

   return 0;

}

稀疏矩阵的减法：规则同加法一样，矩阵A和矩阵B的行数和列数相等时才可以进行计算。

6）矩阵的乘法

//矩阵乘法的算法

int MultMat()

{

   TSMatrix A, B, C;

   InputTSMatrix(&A);

   InputTSMatrix(&B);

   int i, j, k, temp = 0, p = 1;

   if (A.cols != B.rows)

   {

       printf("矩阵A的列数不等于矩阵B的行数不能相乘!\n");

       return 0;

   }

   else

   {

       for (i = 1; i <= A.rows; i++)

       {

          for (j = 1; j <= B.cols; j++)

          {

              temp = 0;

              for (k = 1; k <= A.cols; k++)

              {

                 temp += value(A, i, k) * value(B, k, j);

              }

              if (temp != 0)

              {

                 C.data[p].r = i;

                 C.data[p].c = j;

                 C.data[p].v = temp;

                 p++;

              }

          }

       }

       C.rows = A.rows;

       C.cols = B.cols;

       C.nzeroNums = p-1;

       OutputSMatrix(C);

       return 1;

   }

}

稀疏矩阵的乘法：同样遵循普通矩阵的乘法运算，当矩阵A与矩阵B相乘时则只有前者的列数等于后者的行数时该运算才有意义。

 

（4）矩阵的输出模块

//输出矩阵，按标准格式输出

void OutputSMatrix(TSMatrix M)

{

   int i, j, k = 1;

   for (i = 0; i < M.rows; i++)

   {

       for (j = 0; j < M.cols; j++)

       {

          if ((M.data[k].r-1) == i && (M.data[k].c-1) == j)

          {

              printf("%4d",M.data[k].v);

              k++;

          }

          else

          printf("%4d",0);

       }//end_j

       printf("\n");

   }//end_i

}

 

 

 

 

Main（）

Input（）

Transpose（）

Add（）

Sub（）

Mul（）

Output（）

模块调用关系图 Â

3.3　主程序流程图

4　测试

稀疏矩阵的定义：矩阵中非零元素远远小于矩阵元素的个数，并且非零元素的分布没有一定的规律，则称该矩阵为稀疏矩阵。

该程序测试所使用的矩阵A、B和矩阵C分别如下：

5  0  0   12  0  0       0  0  0  0  15  3       1  0  4  0  0

0  0  16  0   0  0       4  0  0  0  0   0       0  1  0  0  0

   8  0  11  0  27  0       0  0  0  8  0   0       8  0  0  0  0

   0  0  0   0   0  0       1  13 0  0  0   0       0  0  7  0  0

        矩阵A                    矩阵B             5  1  0  0  0

0    0  0  0  3

矩阵C