gc_842_2.c

gc:高级程序员考试用书的c程序源文件

#include <stdio.h>
#include <stdlib.h>

typedef struct ele {                 /*十字链表结点类型*/
	int row,col;
	double val;
	struct ele *right,*down;
}eleNode;



/*函数,建立一个元素全为零的稀疏矩阵的十字链表*/
eleNode *createNullMat(int m,int n)          /*m行n列*/
{
	eleNode *h,*p;
	int k;
	h = (eleNode*)malloc(sizeof(eleNode));        /*十字链表头结点*/
	h->row = m; h->col = n; h->val = 0;           /*稀疏矩阵的行数和列数*/
	h->right = (eleNode *)malloc(sizeof(eleNode)*n);
	h->down = (eleNode *)malloc(sizeof(eleNode)*m);
	for(p = h->down,k=0;k<m;k++,p++) {
		p->col = 1000;                        /*设矩阵不会超过1000列*/
		p->right = p;                        /*每个行链表是一个环*/
		p->down = k<m-1?p+1:h->down;        /*使全部行链表头结点构成环*/
	}
	for(p = h->right,k = 0; k<m;k++,p++){
		p->row = 1000;                      /*设矩阵不会超过1000行*/
		p->down = p;                       /*每个列链表是一个环*/
		p->right = k<m-1?p+1:h->right;         /*使全部列链表头结点构成环*/
	}
	return h;
}


/*函数,在十字链表中插入一个结点*/
int insertNode(eleNode *a,int row,int col,double val)
{
	eleNode *p,*q,*r,*u,*v;
	if (row >= a->row ||col>=a->col)return -2;        /*不合理的行列号*/
	r = (eleNode *)malloc(sizeof(eleNode));
	r->row=row; r->col=col; r->val=val;
	p = a->down+row; q = p->right;
	while(q->col<col) {
		p=q;q=q->right;
	}
	if(q->col==col) {
		free(r);return -3;
	}                       /*该行已经有col列元素*/
	u=a->right+col; v=u->down;
	while(v->row<row) {
		u=v; v=v->down;
	}
	if(v->row == row) {
		free(r);return -1;
	}                        /*该列 已有row行元素*/
	p->right=r; r->right =q;             /*插入到行链中*/
	u->down = r; r->down = v;              /*插入到列链中*/
	a->val += 1.0;
	return 0;                             /*插入成功*/
}



/*函数,输入数据建立十字链表*/
eleNode * readMat()
{
	eleNode *h;
	int i,j,m,n;
	int errorcode;        /*插入时返回的错误代码*/
	double v;
	printf("输入稀疏矩阵的行数和列数");
	scanf("%d%d",&m,&n);
	h = createNullMat(m,n);
	h->row = m; h->col=n;
	printf("输入有非零元素的行号  ");
	scanf("%d",&i);
	while(i >= 0) {                /*逐行输入非零元素*/
		printf("输入非零元素的列号");
		scanf("%d",&j);
		while(j >= 0) {             /*输入一列非零元素*/
			printf("输入非零元素的值  ");
			scanf("%lf",&v);
			errorcode =insertNode(h,i,j,v);
			if (errorcode == -2) printf("不合理的行列号!!!!!!\n");
			if (errorcode == -3) printf("该行已有col列元素!!!!\n");
			if (errorcode == -1) printf("该列已有row行元素!!!!\n");
			printf("输入当前行下一个非零元素的列号(-1表示当前行结束)");
			scanf("%d",&j);
		}
		printf("输入下一列有非零元素的行号(-1表示输入结束) ");
		scanf("%d",&i);
	}
	return h;
}


/*函数,输出十字链表*/
void printMat(eleNode *a)
{
	eleNode *p,*q;
	int k=0;
	p = a->down;    /*a->down指向第一个行链表头结点,头结点与所有结点构成一个环*/
	printf("第%d行: ",k++);   //输出第一行
	q=p->right;
	while (q!=p) {
			printf("[%d,%d,%lf]->",q->row,q->col,q->val);
			q=q->right;
		}
	p=p->down;
	printf("行头结点");
	printf("\n");
	while (p!= a->down) {
		printf("第%d行: ",k++);
		q=p->right;
		while (q!=p) {
			printf("[%d,%d,%lf]->",q->row,q->col,q->val);
			q=q->right;
		}
		printf("行头结点\n");
		p=p->down;
	}
}

/*函数,两个相同行数和列数的稀疏矩阵加法运算.*/
eleNode * matAdd(eleNode *a,eleNode *b)
{
	eleNode *r,*p,*q,*u,*v;;
	r = createNullMat(a->row,a->col);
	p = a->down; u = b->down;
	do  {                /*逐行相加*/
		q = p->right; v = u->right;
		while(q!=p ||v!=u)                 /*两矩阵有一个行未结束循环*/
			if(q->col == v->col) {         /*有相同列的元素*/
				if(q->val + v->val != 0.0)   /*和非零插入*/
					insertNode(r,q->row,q->col,q->val+v->val);
				q=q->right; v=v->right;
				}
			else if(q->col<v->col)  {           /*插入a的元素*/
				insertNode(r,q->row,q->col,q->val);
				q=q->right;
				}
			else {                                   /*插入b的元素*/
				insertNode(r,v->row,v->col,v->val);
				v= v->right;
				}
		p=p->down; u=u->down;              /*或p++,u++*/
	} while (p!=a->down);
	return r;
}



void main()
{

	eleNode *h,*h2,*r;
	h=readMat();

	printMat(h);
	printf("\n");
	printf("%lf",h->val);

	printf("\n\n演算两个相同行数和列数的矩阵相加\n");
	printf("请在下面的输入中,输入和你刚才生成的矩阵一样的行列值\n");
	h2=readMat();   //*为试验两个相同行数和烈属的稀疏矩阵加法运算,引入的一个矩阵*/
	printf("你所输入的第一个矩阵如下: \n");
	printMat(h);
	printf("\n你所输入的第二个矩阵如下: \n");
	printMat(h2);
	printf("%lf",h2->val);

	r=matAdd(h,h2);
	printf("\n\n运算成功,打印结果如下\n");
	printMat(r);
	printf("%lf",r->val);




}