一个组合应用，做了一个工程文件，大家可以去下载。
把基本函数写下来，其他的功能函数可以在文中找到.
#define N 100
#define MAXSIZE 1000 //假设非零元素的个数最多为1000个
#define MAXRC 100 //假设矩阵的行（列）数最多为100
typedef struct matnode
{
int row, col; //结点的行域和列域
struct matnode *right, *down;//结点的向下域（down）和向右域（right）
union //结点的数据域，若为表头结点则无数值，而用指向其后继的指针代替
{
int data;
struct matnode *next;
} tag;
} CrossNode, *CrossList;
typedef struct
{
int x, y; //该非零元素的行下标和列下标
int e; //该非零元素的值
} Triple;
typedef struct
{
Triple data[MAXSIZE+1];//非零元素三元组顺序表data[0]未用
int mu, nu, tu; //矩阵的行数，列数和非零元素的个数
} TSMatrix;
typedef struct node
{
int data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
int sum; //全局变量，存储行列式的值
void DoArray(void); // 二维数组存储矩阵演示
void CreateArray(int H[][N], int m, int n); //构造一个二维数组存储矩阵
void PrintArray(const int H[][N], int m, int n); //输出二维数组存储矩阵
void trsmat(const int A[][N], int B[][N], int m, int n) ; //二维数组存储转置矩阵
void addsmat(const int A[][N], const int B[][N], int C[][N], int m, int n); //二维数组存储矩阵矩阵相加
//二维数组存储矩阵矩阵相乘
void mulsmat(const int A[][N], const int B[][N], int C[][N], int m, int n, int l);
void DoTriple(void); //三元组顺序表存储矩阵 演示
TSMatrix ArrayToTriple(const int A[][N], int m, int n);//二维数组转换为三元组顺序表
void TripleToArray(TSMatrix T, int A[][N], int *m, int *n);//三元组顺序表转换为二维数组
void PrintTriple(TSMatrix M);//输出三元组顺序表存储矩阵
int TransposeSMatrix(TSMatrix M, TSMatrix *T);//三元组顺序表 转置矩阵
int FastTransposeSMatrix(TSMatrix M, TSMatrix *T); //三元组顺序表 快速转置矩阵
TSMatrix TripleAddSMatrix(TSMatrix A, TSMatrix B); //三元组顺序表 矩阵相加
int value(TSMatrix M, int i, int j);//计算出C的行号i和列号j处元素的值
int MultSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C); //三元组顺序表 矩阵相乘
void RPos(TSMatrix M, int rpos[]);//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
int FastMultSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C); //三元组顺序表 快速矩阵相乘
void DoCrossList(void); //十字链表存储矩阵 演示
void CreateHead(CrossList Head[], int len); //创建十字链表的表头结点
void Insert(CrossList Head[], int r, int c, int v); //插入新的结点
CrossList ArrayToCrossList(const int A[][N], int m, int n);//二维数组转换为十字链表
void CrossListToArray(CrossList T, int A[][N], int *m, int *n);//十字链表转换为二维数组
void PrintCrossList(CrossList T);//输出十字链表存储矩阵
CrossList CrossListAddSMatrix(const CrossList A, const CrossList B);//十字链表存储矩阵矩阵相加
int TransposeCrossList(const CrossList M, CrossList *T); //十字链表存储转置矩阵
int MultCrossList(const CrossList A, const CrossList B, CrossList *C);//十字链表存储矩阵矩阵相乘
void DoNJZ(void);//矩阵的逆矩阵 演示
int ByArray(const int H[][N], int Y[][N], int m); //二维数组存储矩阵 方式求逆矩阵
int ByTSMatrix(const int H[][N], int Y[][N], int m); //三元组顺序表存储矩阵 方式求逆矩阵
int ByCrossList(const int H[][N], int Y[][N], int m); //十字链表存储矩阵 方式求逆矩阵
//判断当前元素的纵坐标是否与栈中存储的元素重复
int Judge(const array S[], int line, int len);
void SolveHA(const int H[][N], array S[], int len, int i, int NiXu);//二维数组采用递归方式求行列式的值
TSMatrix CreateYHT(TSMatrix T, int x, int y); //三元组顺序表求代数余子式矩阵
void SolveHT(const TSMatrix A, array S[], int rpos[], int row, int top, int NiXu);//三元组顺序表采用递归方式求行列式的值
CrossList CreateYHC(const CrossList T, int s, int x, int y);//十字链表求代数余子式矩阵
void SolveHC(CrossList T, array S[], CrossList HeadRow, int top, int NiXu);//十字链表采用递归方式求行列式的值
extern sum;
int main(int argc, char *argv[])
{
// DoArray();
// DoTriple();
// DoCrossList();
DoNJZ() ;
system("PAUSE");
return 0;
}
void DoArray(void) // 二维数组存储矩阵演示
{
int Array1[N][N], Array2[N][N], Array3[N][N], Array4[N][N], Array5[N][N]; //二维数组存储矩阵
int m1, n1, m2, n2;
m1 = 3;
n1 = 4;
m2 = 3;
n2 = 4;
puts("第1个矩阵：");
CreateArray(Array1, m1, n1); //构造一个二维数组存储矩阵
PrintArray(Array1, m1, n1); //输出二维数组存储矩阵
puts("第1个矩阵的转置矩阵3：");
trsmat(Array1, Array2, m1, n1);
PrintArray(Array2, n1, m1); //输出二维数组存储矩阵
puts("第2个矩阵：");
CreateArray(Array3, m2, n2); //构造一个二维数组存储矩阵
PrintArray(Array3, m2, n2); //输出二维数组存储矩阵
puts("第1个矩阵和第2个矩阵相加：");
addsmat(Array1, Array3, Array4, m1, n1);
PrintArray(Array4, m1, n1); //输出二维数组存储矩阵
puts("第1个矩阵和第3个矩阵相乘：");
mulsmat(Array1, Array2, Array5, m1, n1, m1);
PrintArray(Array5, m1, m1); //输出二维数组存储矩阵
}
void DoTriple(void)//三元组顺序表存储矩阵 演示
{
int Array1[N][N], Array2[N][N], Array3[N][N], Array4[N][N], Array5[N][N]; //二维数组存储矩阵
TSMatrix Triple1, Triple2, Triple3, Triple4, Triple5;
int m1, n1, m2, n2;
int flag1, flag2;
m1 = 3;
n1 = 4;
m2 = 3;
n2 = 4;
puts("第1个矩阵：");
CreateArray(Array1, m1, n1); //构造一个二维数组存储矩阵
PrintArray(Array1, m1, n1); //输出二维数组存储矩阵
// puts("第1个矩阵转换为三元组顺序表：");
Triple1 = ArrayToTriple(Array1, m1, n1);//二维数组转换为三元组顺序表
// PrintTriple(Triple1);
puts("第2个矩阵：");
CreateArray(Array2, m2, n2); //构造一个二维数组存储矩阵
PrintArray(Array2, m2, n2); //输出二维数组存储矩阵
// puts("第2个矩阵转换为三元组顺序表：");
Triple2 = ArrayToTriple(Array2, m2, n2); //二维数组转换为三元组顺序表
// PrintTriple(Triple2);
puts("第1个矩阵与第2个矩阵相加：");
Triple4 = TripleAddSMatrix(Triple1, Triple2); //三元组顺序表 矩阵相加
TripleToArray(Triple4, Array3, &m2, &n2);//三元组顺序表转换为二维数组
PrintArray(Array3, m2, n2); //输出二维数组存储矩阵
flag1 = TransposeSMatrix(Triple1, &Triple3); //三元组顺序表 转置矩阵
// flag1 = FastTransposeSMatrix(Triple1, &Triple3);//三元组顺序表 快速转置矩阵
if(flag1)
{
puts("第1个矩阵的转置矩阵3：");
// PrintTriple(Triple3);
TripleToArray(Triple3, Array3, &m1, &n1);//三元组顺序表转换为二维数组
PrintArray(Array3, m1, n1); //输出二维数组存储矩阵
flag2 = MultSMatrix(Triple1, Triple3, &Triple5);//三元组顺序表 矩阵相乘
if(flag2)
{
TripleToArray(Triple5, Array3, &m1, &n1);//三元组顺序表转换为二维数组
puts("第1个矩阵与其转置矩阵相乘：");
PrintArray(Array3, m1, n1); //输出二维数组存储矩阵
}
}
}
void DoCrossList(void)
{
int Array1[N][N], Array2[N][N], Array3[N][N], Array4[N][N], Array5[N][N]; //二维数组存储矩阵
CrossList CrossList1=NULL, CrossList2=NULL, CrossList3=NULL, CrossList4=NULL;
int m1, n1, m2, n2;
int flag1, flag2;
m1 = 5;
n1 = 5;
puts("第1个矩阵：");
CreateArray(Array1, m1, n1); //构造一个二维数组存储矩阵
PrintArray(Array1, m1, n1); //输出二维数组存储矩阵
CrossList1 = ArrayToCrossList(Array1, m1, n1); //二维数组转换为十字链表
// PrintCrossList(CrossList1); //输出十字链表存储矩阵
puts("第2个矩阵：");
CreateArray(Array2, m1, n1); //构造一个二维数组存储矩阵
PrintArray(Array2, m1, n1); //输出二维数组存储矩阵
CrossList2 = ArrayToCrossList(Array2, m1, n1); //二维数组转换为十字链表
// PrintCrossList(CrossList2); //输出十字链表存储矩阵
puts("第1个矩阵和第2个矩阵相加：");
CrossList4 = CrossListAddSMatrix(CrossList1, CrossList2);//十字链表存储矩阵矩阵相加
// PrintCrossList(CrossList4); //输出十字链表存储矩阵
CrossListToArray(CrossList4, Array3, &m2, &n2); //十字链表转换为二维数组
PrintArray(Array3, m2, n2); //输出二维数组存储矩阵
flag1 = TransposeCrossList(CrossList1, &CrossList3); //十字链表存储转置矩阵
if(flag1)
{
puts("第1个矩阵的转置矩阵3：");
// PrintCrossList(CrossList3); //输出十字链表存储矩阵
CrossListToArray(CrossList3, Array3, &m2, &n2); //十字链表转换为二维数组
PrintArray(Array3, m2, n2); //输出二维数组存储矩阵
puts("第1个矩阵与其转置矩阵相乘：");
flag2 = MultCrossList(CrossList1, CrossList3, &CrossList4);
if(flag2)
{
// PrintCrossList(CrossList4); //输出十字链表存储矩阵
CrossListToArray(CrossList4, Array3, &m2, &n2); //十字链表转换为二维数组
PrintArray(Array3, m2, n2); //输出二维数组存储矩阵
}
}// if(flag1)
}
void DoNJZ(void)
{
int H[N][N]; //存储原矩阵的行列式和代数余子式
int Y[N][N], YZ[N][N];//Y[N][N]存储代数余子式的值，其转置矩阵YZ[N][N]即原矩阵的伴随矩阵
int D; // 存储原矩阵的行列式的值
int m;//存储原矩阵的行列式的阶次
int choice;
m = 8;
CreateArray(H, m, m); //构造一个矩阵行列式
PrintArray(H, m, m); //输出矩阵行列式
puts("请选择处理逆矩阵的方法：");
puts("输入1：二维数组存储矩阵方式求逆矩阵 ");
puts("输入2：三元组顺序表存储矩阵方式求逆矩阵 ");
puts("输入3：十字链表存储矩阵方式求逆矩阵");
scanf("%d", &choice);
switch(choice)
{
case 1: D = ByArray(H, Y, m); //二维数组存储矩阵 方式求逆矩阵
break;
case 2: D = ByTSMatrix(H, Y, m); //三元组顺序表存储矩阵 方式求逆矩阵
break;
case 3: D = ByCrossList(H, Y, m); //十字链表存储矩阵 方式求逆矩阵
break;
default: puts("");
break;
}
trsmat(Y, YZ, m, m);//求转置矩阵
//PrintArray(YZ, m, m); //输出伴随矩阵
puts("逆矩阵:");
printf("(1/%d)*\n", D);
PrintArray(YZ, m, m); //输出伴随矩阵
}
int ByArray(const int H[][N], int Y[][N], int m) //二维数组存储矩阵 方式求逆矩阵
{
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int YH[N][N]; //存储原矩阵的行列式和代数余子式
int D; // 存储原矩阵的行列式的值
int x, y, row, col;
int i, j;
sum = 0; //设原矩阵的行列式的初值为0
SolveHA(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
SolveHA(YH, SL, m-1, 0, 0);//采用递归方式求代数余子式的值
if((x+1+y+1)%2==0)
Y[x][y] = sum;
else
Y[x][y] = sum*(-1);
}
return D;
}
int ByTSMatrix(const int H[][N], int Y[][N], int m) //三元组顺序表存储矩阵 方式求逆矩阵
{
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int YH[N][N]; //存储原矩阵的行列式和代数余子式
TSMatrix Triple1, Triple2; //三元组顺序表
int Trpos[N] = {0};//存储矩阵T的每一行的第一个非零元素在三元组中的位置
int D; // 存储原矩阵的行列式的值
int x, y;
int ym; //分别存储原矩阵的行列式和代数余子式的阶次
Triple1 = ArrayToTriple(H, m, m); //二维数组转换为三元组顺序表
// PrintTriple(Triple1);
RPos(Triple1, Trpos);//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
sum = 0; //设原矩阵的行列式的初值为0
SolveHT(Triple1, SL, Trpos, 1, 0, 0); //采用递归方式求矩阵行列式的值
D = sum;
// printf("D = %d\n", D); //输出原矩阵的行列式的值
for(x=1; x<=m; x++) //构造各元素的代数余子式
for(y=1; y<=m; y++)
{
Triple2 = CreateYHT(Triple1, x, y); //求代数余子式矩阵
// PrintTriple(Triple2); //输出代数余子式
// TripleToArray(Triple2, YH, &ym, &ym);//三元组顺序表转换为二维数组
// PrintArray(YH, ym, ym); //输出行列式
RPos(Triple2, Trpos);//确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置
sum = 0; //设代数余子式的初值为0
SolveHT(Triple2, SL, Trpos, 1, 0, 0);//采用递归方式求代数余子式的值
if((x+y)%2==0)
Y[x-1][y-1] = sum;
else
Y[x-1][y-1] = sum*(-1);
}
return D;
}
int ByCrossList(const int H[][N], int Y[][N], int m) //十字链表存储矩阵 方式求逆矩阵
{
CrossList CrossList1=NULL, CrossList2=NULL; // 十字链表
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int YH[N][N]; //存储原矩阵的行列式和代数余子式
int YZ[N][N];//存储代数余子式的值，其转置矩阵即原矩阵的伴随矩阵
int D; // 存储原矩阵的行列式的值
int x, y;
int ym; //分别存储原矩阵的行列式和代数余子式的阶次
CrossList1 = ArrayToCrossList(H, m, m);//二维数组转换为十字链表
// PrintCrossList(CrossList1);//输出十字链表存储矩阵
sum = 0; //设原矩阵的行列式的初值为0
SolveHC(CrossList1, SL, CrossList1->tag.next, 0, 0); //采用递归方式求矩阵行列式的值
D = sum;
// printf("D = %d\n", D); //输出原矩阵的行列式的值
for(x=1; x<=m; x++) //构造各元素的代数余子式
for(y=1; y<=m; y++)
{
CrossList2 = CreateYHC(CrossList1, m-1, x, y); //求代数余子式矩阵
// PrintCrossList(CrossList2); //输出十字链表存储矩阵
// CrossListToArray(CrossList2, YH, &ym, &ym); //十字链表转换为二维数组
// PrintArray(YH, ym, ym); //输出二维数组存储矩阵
sum = 0; //设代数余子式的初值为0
SolveHC(CrossList2, SL, CrossList2->tag.next, 0, 0);//采用递归方式求代数余子式的值
if((x+y)%2==0)
Y[x-1][y-1] = sum;
else
Y[x-1][y-1] = sum*(-1);
}
return D;
}
//部分功能函数
//判断当前元素的纵坐标是否与栈中存储的元素重复
int 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;
}
void SolveHA(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) //如果未分析到该乘积项的最后一个元素，递归继续分析
SolveHA(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;
}
}
}
}
TSMatrix CreateYHT(TSMatrix T, int x, int y) //三元组顺序表求代数余子式矩阵
{
int i, k = 1;
TSMatrix TY;
for(i=1; i<=T.tu; i++) //构造代数余子式
{
if(x != T.data[i].x && y != T.data[i].y)
{
if(x > T.data[i].x) //若该非零元素的行号比x小，其代数余子式对应的元素行号不变
TY.data[k].x = T.data[i].x;
else //若该非零元素的行号比x大，其代数余子式对应的元素行号减1
TY.data[k].x = T.data[i].x-1;
if(y > T.data[i].y) //列号的处理方法与行号相同
TY.data[k].y = T.data[i].y;
else
TY.data[k].y = T.data[i].y-1;
TY.data[k].e = T.data[i].e;
k++;
}
} //for(i=1; i<=T.tu; i++)
TY.mu = T.mu-1;
TY.nu = T.nu-1;
TY.tu = k-1;
return TY;
}
void SolveHT(const TSMatrix A, array S[], int rpos[], int row, int top, int NiXu)//三元组顺序表采用递归方式求行列式的值
{
array CS[N]; //栈，存储S[]的拷贝
int ta, p, i, j, k, ctop;
int mul; //存储每一个乘积项的值
int CNiXu; //累积每一个乘积项的逆序数
if(row < A.mu) //处理A中第arow的每一个非零元素ta指示下一行第一个非零元素的位置
ta = rpos[row+1];
else //最后一行的 下一行第一个非零元素的位置 当然是 A.tu + 1
ta = A.tu + 1;
for(p=rpos[row]; p<ta; p++) //按行扫描
{
ctop = top;
if(Judge(S, A.data[p].y, ctop))//如果当前元素的纵坐标不与栈中存储的元素重复，将其入栈
{
S[ctop].x = A.data[p].x;
S[ctop].y = A.data[p].y;
S[ctop++].data = A.data[p].e;
CNiXu = NiXu; //把逆序数复制到CNiXu
for(k=0; k<ctop-1; k++)
{
if(S[ctop-1].y < S[k].y) //累积逆序数
CNiXu++;
}
for(k=0; k<ctop; k++) //复制栈
CS[k] = S[k];
if(row < A.mu) //如果未分析到该乘积项的最后一个元素，递归继续分析
SolveHT(A, CS, rpos, row+1, ctop, CNiXu);
else //否则计算该乘积项的值，并存储到栈中
{
if(ctop == row)
{
for(mul=1, k=0; k<ctop; k++)
mul *= S[k].data;
if(CNiXu%2==0) //如果逆序数为偶数，该乘积项为正
sum += mul;
else //否则为负
sum -= mul;
}
}
}
}
}
CrossList CreateYHC(const CrossList T, int s, int x, int y)//十字链表求代数余子式矩阵
{
CrossList Head[MAXRC], p, q;
int k, row, col;
CreateHead(Head, s);
k = 1;
p = T->tag.next;
while(p != T) //按行表顺序，把十字链表中的元素写入二维数组
{
q = p->right;
while(q != p)
{
if(x != q->row && y != q->col)
{
if(x > q->row) //若该非零元素的行号比x小，其代数余子式对应的元素行号不变
row = q->row;
else //若该非零元素的行号比x大，其代数余子式对应的元素行号减1
row = q->row-1;
if(y > q->col) //列号的处理方法与行号相同
col = q->col;
else
col = q->col-1;
Insert(Head, row, col, q->tag.data);
k++;
} //if
q = q->right;
} // while(q != p)
p = p->tag.next;
} //while(p != CrossList1)
Head[0]->row = s; //总表头Head[0]的行域存储矩阵的总行数
Head[0]->col = s; //总表头Head[0]的列域存储矩阵的总列数
Head[1]->row = k-1; //非零元素的个数存储在Head[1]的行域
return Head[0];
}
void SolveHC(CrossList T, array S[], CrossList HeadRow, int top, int NiXu)//十字链表采用递归方式求行列式的值
{
CrossList q;
array CS[N]; //栈，存储S[]的拷贝
int k, ctop;
int mul; //存储每一个乘积项的值
int CNiXu; //累积每一个乘积项的逆序数
q = HeadRow->right;
while(q != HeadRow)
{
ctop = top;
if(Judge(S, q->col, ctop))//如果当前元素的纵坐标不与栈中存储的元素重复，将其入栈
{
S[ctop].x = q->row;
S[ctop].y = q->col;
S[ctop++].data = q->tag.data;
CNiXu = NiXu; //把逆序数复制到CNiXu
for(k=0; k<ctop-1; k++)
{
if(S[ctop-1].y < S[k].y) //累积逆序数
CNiXu++;
}
for(k=0; k<ctop; k++) //复制栈
CS[k] = S[k];
if(HeadRow->right->row < T->row) //如果未分析到该乘积项的最后一个元素，递归继续分析
SolveHC(T, CS, HeadRow->tag.next, ctop, CNiXu);
else //否则计算该乘积项的值，并存储到栈中
{
if(ctop == T->row)
{
for(mul=1, k=0; k<ctop; k++)
mul *= S[k].data;
if(CNiXu%2==0) //如果逆序数为偶数，该乘积项为正
sum += mul;
else //否则为负
sum -= mul;
}
} //else
} //if(Judge(S, q->col, ctop))
q = q->right;
} //while(q != HeadRow)
}
评论