/*按规则输入线性方程组的系数（每行N+1个数值，按顺序输入N个系数项，最后一项为常数项，用空格隔开），输出该方程组的系数行列式和它的值，最后输出方程组的解*//*处理实型数据,电脑随机输入数据*/ /*2006-1-11 梁见斌*/ #include <stdio.h>#include <stdlib.h> #define N 10  //行列式的行（列）数 #define MAXRC 100 //假设矩阵的行（列）数最多为100typedef 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;}

评论