矩阵应用系列
矩阵是很多科学与工程计算问题中研究的数学对象。我这里主要是提供一些矩阵的计算方法和用不同方式存储矩阵元进行计算时算法的比较。
矩阵的存储方式很多，最为常见的是用二维数组来存储矩阵元；但是在处理稀疏矩阵时，这种存储方法会浪费大量的时间和空间，一般采用三员组和十字链表的方法来存储。我将依次讲解这三种方法的不同特点。
首先是最为常见的二维数组存储法。这种存储方法形式简单明了，进行各种计算时算法也很容易理解。矩阵的常见计算有求转置矩阵，求逆矩阵，矩阵的加法和乘法。
void CreateArray(int H[][N], int m, int n) //构造一个二维数组存储矩阵
{
int i, j;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
H[i][j] = rand()%4;
}
void PrintArray(const int H[][N], int m, int n) //输出二维数组存储矩阵
{
int i, j;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
printf("%6d ", H[i][j]);
printf("\n");
}
}
1。转置矩阵
转置是一种最简单的矩阵运算，对于一个m*n的矩阵Amn，其转置矩阵是一个n*m的矩阵Bnm，
且B[j][i] = A[i][j]，0<=i<m, 0<=j<n，其函数如下；
void trsmat(const int A[][N], int B[][N], int m, int n)
{
int i, j;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
B[j][i] = A[i][j];
}
2。矩阵相加
两个大小均为m*n的矩阵的元素相加后得到一个m*n的矩阵C，其运算是把A与B的相同位置的元素相加得到C，即Cij=Aij+Bij，0<=i<m, 0<=j<n，其函数如下；
void addsmat(const int A[][N], const int B[][N], int C[][N], int m, int n)
{
int i, j;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
C[i][j] = A[i][j] + B[i][j];
}
3。矩阵相乘
两个矩阵相乘，第一个矩阵的列数要与第二个矩阵的行数相等，即若C = A * B，则A是m*n矩阵，B是n*l矩阵，C是m*l矩阵，其函数如下；
void mulsmat(const int A[][N], const int B[][N], int C[][N], int m, int n, int l)
{
int i, j, k;
for(i=0; i<m; i++)
for(j=0; j<l; j++)
{
C[i][j] = 0;
for(k=0; k<n; k++)
C[i][j] += A[i][k] * B[k][j];
}
}
4.求逆矩阵
求逆矩阵的公式为A(逆) = A* /|A|，其中A*为矩阵A的伴随矩阵，|A|为矩阵A的行列式的值，算法较为复杂，必须先求出A*和|A|。其函数如下；
/*创建方形矩阵的行列式（人工输入数据），输出该矩阵的逆矩阵*/
/*2006-1-10 梁见斌*/
#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef struct node
{
int data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
int sum; //全局变量，存储行列式的值
void CreateArray(int H[][N], int m, int n); //构造一个二维数组存储矩阵
void PrintArray(const int H[][N], int m, int n) ; //输出二维数组存储矩阵
void SolveH(const int H[][N], array S[], int len, int i, int NiXu);//采用递归方式求行列式的值
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
void trsmat(const int A[][N], int B[][N], int m, int n) ; //二维数组存储转置矩阵
int main(void)
{
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int H[N][N], YH[N][N]; //存储原矩阵的行列式和代数余子式
int Y[N][N], YZ[N][N];//Y[N][N]存储代数余子式的值，其转置矩阵YZ[N][N]即原矩阵的伴随矩阵
int D; // 存储原矩阵的行列式的值
int x, y, row, col;
int i, j, k;
int m;//存储原矩阵的行列式的阶次
m = 3;
CreateArray(H, m, m); //构造一个矩阵行列式
PrintArray(H, m, m); //输出矩阵行列式
sum = 0; //设原矩阵的行列式的初值为0
SolveH(H, SL, m, 0, 0); //采用递归方式求矩阵行列式的值
D = sum;
// printf("D = %d\n", D); //输出原矩阵的行列式的值
for(x=0; x<m; x++)//构造各元素的代数余子式
for(y=0; y<m; y++)
{
for(row=0, i=0; i<m; i++) //构造代数余子式
{
if(i!=x)
{
for(col=0, j=0; j<m; j++)
if(j!=y)
YH[row][col++] = H[i][j];
row++;
}
}
//PrintYH(YH); //输出代数余子式
sum = 0; //设代数余子式的初值为0
SolveH(YH, SL, m-1, 0, 0);//采用递归方式求代数余子式的值
if((x+1+y+1)%2==0)
Y[x][y] = sum;
else
Y[x][y] = sum*(-1);
}
trsmat(Y, YZ, m, m);//求转置矩阵
//PrintArray(YZ, m, m); //输出伴随矩阵
puts("逆矩阵:");
printf("(1/%d)*\n", D);
PrintArray(YZ, m, m); //输出伴随矩阵
system("pause");
return 0;
}
void CreateArray(int H[][N], int m, int n) //构造一个二维数组存储矩阵
{
int i, j;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
scanf("%d", &H[i][j]);
fflush(stdin);
}
}
void PrintArray(const int H[][N], int m, int n) //输出二维数组存储矩阵
{
int i, j;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
printf("%4d ", H[i][j]);
printf("\n");
}
}
void trsmat(const int A[][N], int B[][N], int m, int n) //二维数组存储转置矩阵
{
int i, j;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
B[j][i] = A[i][j];
}
void SolveH(const int H[][N], array S[], int len, int i, int NiXu)//采用递归方式求行列式的值
{
array CS[N]; //栈，存储S[]的拷贝
int j, k, top = i;
int mul; //存储每一个乘积项的值
int CNiXu; //累积每一个乘积项的逆序数
for(j=0; j<len; j++)
{
if(Judge(S, j, top))//如果当前元素的纵坐标不与栈中存储的元素重复，将其入栈
{
S[top].x = i;
S[top].y = j;
S[top].data = H[i][j];
CNiXu = NiXu; //把逆序数复制到CNiXu
for(k=0; k<top; k++)
{
if(j < S[k].y) //累积逆序数
CNiXu++;
}
for(k=0; k<=top; k++) //复制栈
CS[k] = S[k];
if(i<len-1) //如果未分析到该乘积项的最后一个元素，递归继续分析
SolveH(H, CS, len, i+1, CNiXu);
else //否则计算该乘积项的值，并存储到栈中
{
for(mul=1, k=0; k<=top; k++)
mul *= S[k].data;
if(CNiXu%2==0) //如果逆序数为偶数，该乘积项为正
sum += mul;
else //否则为负
sum -= mul;
}
}
}
}
//判断当前元素的纵坐标是否与栈中存储的元素重复
bool Judge(const array S[], int line, int len)
{
int i;
for(i=0; i<len; i++)
if(line == S[i].y)
return 0;
return 1;
}
评论