/*按规则输入线性方程组的系数（每行N+1个数值，按顺序输入N个系数项，最后一项为常数项，用空格隔开）
，输出该方程组的系数行列式和它的值，最后输出方程组的解*/
/*处理实型数据,电脑随机输入数据*/
/*2006-1-11 梁见斌*/
#include <stdio.h>
#include <stdlib.h>
#define N 10 //行列式的行（列）数
#define MAXRC 100 //假设矩阵的行（列）数最多为100
typedef struct matnode
{
int row, col; //结点的行域和列域
struct matnode *right, *down;//结点的向下域（down）和向右域（right）
union //结点的数据域，若为表头结点则无数值，而用指向其后继的指针代替
{
float data;
struct matnode *next;
} tag;
} CrossNode, *CrossList;
typedef struct node
{
float data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
float sum; //全局变量，存储行列式的值
void Create(float H[][N], float X[]); //构造一个行列式
void PrintH(const float H[][N], const float X[]); //输出行列式
void CreateHead(CrossList Head[], int len); //创建十字链表的表头结点
void Insert(CrossList Head[], int r, int c, float v); //插入新的结点
CrossList ArrayToCrossList(const float A[][N], int m, int n);//二维数组转换为十字链表
void SolveHC(CrossList T, array S[], CrossList HeadRow, int top, int NiXu);//采用递归方式求行列式的值
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
int main(void)
{
CrossList CrossList1=NULL, CrossList2=NULL; // 十字链表
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
float H[N][N], CH[N][N];//存储系数行列式
float B[N]; //存储常数项
float D, X[N]; //分别存储系数行列式的值 和 方程组的解
int i, j, k;
int m; //十字链表转换为二维数组时返回的矩阵行数和列数，这里没有用处
Create(H,B); //构造一个行列式
PrintH(H,B); //输出行列式
CrossList1 = ArrayToCrossList(H, N, N);//二维数组转换为十字链表
sum = 0; //设原矩阵的行列式的初值为0
SolveHC(CrossList1, SL, CrossList1->tag.next, 0, 0); //采用递归方式求矩阵行列式的值
D = sum;
printf("D = %f\n", D); //输出原矩阵的行列式的值
for(k=0; k<N; k++)
{
for(i=0; i<N; i++) //复制行列式
{
for(j=0; j<N; j++)
CH[i][j] = H[i][j];
CH[i][k] = B[i]; //把系数行列式D中第k列的元素用方程组右端的常数项代替
}
CrossList1 = ArrayToCrossList(CH, N, N);//二维数组转换为十字链表
sum = 0; //设原矩阵的行列式的初值为0
SolveHC(CrossList1, SL, CrossList1->tag.next, 0, 0); //采用递归方式求矩阵行列式的值
printf("D%d = %f\n", k+1, sum); //输出该行列式的值
X[k] = sum / D;
}
for(i=0; i<N; i++)
printf("X%d = %f\n", i+1, X[i]); //输出该行列式的值
system("pause");
return 0;
}
void Create(float H[][N], float X[])
{
int i, j;
puts("请按标准格式输入行列式：每行N+1个数值，按顺序输入N个系数项，最后一项为常数项，用空格隔开");
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
H[i][j]=(rand()%5)*1.0; //输入系数项
X[i]=(rand()%5)*1.0; //输入常数项
// fflush(stdin);
}
}
void PrintH(const float H[][N], const float X[])
{
int i, j;
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
printf("%f ", H[i][j]);
printf("\t%f", X[i]);
printf("\n");
}
}
CrossList ArrayToCrossList(const float A[][N], int m, int n)//二维数组转换为十字链表
{
int s;
int i, j, k=0;
CrossList Head[MAXRC], p, q;
s = m>n ? m:n;//因为序号相同行头和列头共用一个结点，故只要分配s个表头结点就好了
CreateHead(Head, s);
for(i=0; i<m; i++)
for(j=0; j<n; j++)
if(A[i][j] != 0)
{
k++;
Insert(Head, i+1, j+1, A[i][j]);
}//if(A[i][j] != 0)
Head[0]->row = m; //总表头Head[0]的行域存储矩阵的总行数
Head[0]->col = n; //总表头Head[0]的列域存储矩阵的总列数
Head[1]->row = k; //非零元素的个数存储在Head[1]的行域
return Head[0]; //返回总表头结点
}
void CreateHead(CrossList Head[], int len) //创建十字链表的表头结点
{
CrossList p;
int i;
p = (CrossList)malloc(sizeof(CrossNode));
if(!p)
{
puts("Error");
exit(1);
}
p->row = p->col = 0; //表头结点的行域和列域设置为0
p->down = p->right = p;//先将表头结点的行域和列域指向自身，以构成循环链表
Head[0] = p; //生成总表头结点
for(i=1; i<=len; i++)//先初始化所有的行头（列头）
{
p = (CrossList)malloc(sizeof(CrossNode));
if(!p)
{
puts("Error");
exit(1);
}
p->row = p->col = 0; //表头结点的行域和列域设置为0
p->down = p->right = p;//先将表头结点的行域和列域指向自身，以构成循环链表
Head[i] = p;
Head[i-1]->tag.next = p;//把表头结点按顺序连接起来
} //for(i=1; i<=s; i++)
Head[len]->tag.next = Head[0];//最后一个表头结点的后继为总表头，即构成循环链表
}
void Insert(CrossList Head[], int r, int c, float v) //插入新的结点
{
CrossList p, q;
p = (CrossList)malloc(sizeof(CrossNode));
if(!p)
{
puts("Error");
exit(1);
}
p->row = r;
p->col = c;
p->tag.data = v;
q = Head[r]; //完成行插入
while(q->right != Head[r] && q->right->col < c)
q = q->right;
p->right = q->right;
q->right = p;
// printf("222r=%d,c=%d,v=%d",r,c,v); system("pause");
q = Head[c]; //完成列插入
while(q->down != Head[c] && q->down->row < r)
q = q->down;
p->down = q->down;
q->down = p;
}
void SolveHC(CrossList T, array S[], CrossList HeadRow, int top, int NiXu)//采用递归方式求行列式的值
{
CrossList q;
array CS[N]; //栈，存储S[]的拷贝
int k, ctop;
float 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)
}
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;
}
评论