matrix.c

这是一个数据结构中,对树遍历的程序,写得相当精炼,对数据结构初学者是个不错的参考程序!

/*==================================================================*
 *description  Initialize sparse matrix and create matrix a, b      *
 *             and store the result of matrix a plus b into         *
 *             a new matrix c                                       *
 *author David                                                      *
 *modified 2006-11-14                                               *
 *==================================================================*/

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
/*用户输入数字位数最大长度*/
#define STRLENGTH 5
/*最大矩阵的行列数*/
#define MATRIXSIZE 20
/*存放矩阵中一个非零元素的结点结构*/
typedef struct node{
	int row;
	int col;
	int data;
	struct node *next;
}node;
/*稀疏矩阵的链表存储结构*/
typedef struct matrix{
	node *data[MATRIXSIZE];
	int m;		/*行数*/
	int n;		/*列数*/
	int t;		/*非零元数个数*/
	int initialized; /*矩阵是否初始化*/
}matrix;

/*接受没有从标准输入设备读取完的输入字符*/
void FlushSTDIN();
/*获得字符串*/
int GetString(char *);
/*判断字符串是否为数字字符串*/
int IsDigtal(char *);
/*将数字字符串转换成十进制整数*/
int Str2Digtal(char *);
/*初始化一个矩阵*/
int InitMatrix(matrix *, int, int, int);
/*向矩阵中输入数据*/
int StorageMatrix(matrix *);
/*根据标签来创建矩阵*/
int CreateMatrixbyLabel(matrix *, char *);
/*矩阵相加*/
int MatrixAdd(matrix *, matrix *, matrix *);
/*矩阵相乘*/
int MatrixMultiply(matrix *, matrix *, matrix *);
/*回收结点内存区*/
int Cleanup(matrix *);
/*根据返回输出系统信息*/
void Message(int);

/*接受没有从标准输入设备读取完的输入字符*/
void FlushSTDIN(){
	char c;
	if((c=feof(stdin))==0){
		c=getchar();
		while((c!=10)&&(c!='\0')) c=getchar();
	}
}

/*判断字符串states是否为数字字符串,如果是返回0，否则返回-1*/
int IsDigital(char *states){
	char c;
	int rs=-1;
	if((!states)||(*states=='\0')) return (rs);
	c=*states;
	if(c=='-'){
		c=*(++states);
		if(c=='\0') return (rs);
	}
	for(;c!='\0';c=*(++states)){
		if((c>'9')||(c<'0'))
			return (rs);
	}
	rs=0;
	return (rs);
}

/*获得串str,返回0为数字字符串，否则为非数字字符串*/
int GetDigitalString(char *str){
	int strlen=0,rs=0;
	char tmp, *p=NULL;
	p=str;
	scanf("%c",&tmp);
	strlen++;
	while((tmp!=32)&&(tmp!=10)&&(tmp!='\n')&&(strlen<STRLENGTH)){
		*str++=tmp;
		strlen++;
		scanf("%c",&tmp);
	}
	*str='\0';
	if(strlen==STRLENGTH) FlushSTDIN();
	rs=IsDigital(p);
	if(rs==-1) return (-1);
	return (0);
}

/*将数字字符串states转换成十进制整数,如果成功返回0，否则返回-1*/
int Str2Digital(char *states){
	char c;
	int rs=0, sign=1;
	if(IsDigital(states)==-1) return (-1);
	c=*states;
	if(c=='-'){
		sign=-1;
		c=*(++states);
	}
	for(;c!='\0';c=*(++states))
		rs=rs*10+(c-'0');
	rs*=sign;
	return (rs);
}

/*初始化m行n列的矩阵mt，其中非零个数为t，如果成功返回0，否则返回-1*/
int InitMatrix(matrix *mt, int m, int n, int t){
	int i=0;
	/*确保m,n,t数据的范围正确*/
	if((m<=0)||(n<0)||(t<0)||(t>m*n)||(m>MATRIXSIZE)) return (-1);
	/*每行的指针域初始为NULL*/
	for(i=0;i<MATRIXSIZE;i++) mt->data[i]=NULL;
	mt->m=m;				/*该矩阵的行数*/
	mt->n=n;				/*该矩阵的列数*/
	mt->t=t;				/*该矩阵非零的数目*/
	mt->initialized=1;		/*该矩阵已经被初始化*/
	return (0);
}

/*确定在mt矩阵结构中是否已经记录了row行col列的数据，如果是返回-1，否则返回0*/
int LocateNode(matrix *mt, int row, int col){
	node *p=NULL;
	if((!mt)||(row>mt->m)||(col>mt->n)||(row<0)||(col<0)) return (-1);
	for(p=mt->data[row-1];p!=NULL;p=p->next)
		if(p->col==col) return (-1);
	return (0);
}

/*根据标签label来创建矩阵mt*/
int CreateMatrixbyLabel(matrix *mt, char *label){
	int rs=0,m=0,n=0,t=0;
	char str[STRLENGTH];
	printf("[ Please input parameters of matrix %s ]\n",label);
	do{
		printf("->Rows=",label);
		rs=GetDigitalString(str);
	}while(rs==-1);
	/*接收的矩阵行数赋给变量m*/
	m=Str2Digital(str);
	do{
		printf("->Columns=",label);
		rs=GetDigitalString(str);
	}while(rs==-1);
	/*接收的矩阵列数赋给变量n*/
	n=Str2Digital(str);
	do{
		printf("->Quantity of Nonzero node=",label);
		rs=GetDigitalString(str);
	}while(rs==-1);
	/*接收的稀疏矩阵非零元素个数赋给变量t*/
	t=Str2Digital(str);
	/*初始化矩阵a*/
	rs=InitMatrix(mt,m,n,t);
	return (rs);
}

/*向矩阵mt中输入数据,构建稀疏矩阵*/
int StorageMatrix(matrix *mt){
	node *q=NULL, *p=NULL, *s=NULL;
	char c[STRLENGTH];	/*接收用户从键盘输入的数字字符*/
	int i=0,row=0,col=0,data=0,rs=0,site=0;
	if((!mt)||(mt->initialized!=1)) return (-1);
	for(i=0;i<mt->t;i++){
		/*接受用户输入的整型数据，如果不是整型或者mt中已经有该位置的元素就重复接受*/
		do{
			do{
				printf("->Row NO. of the %d node=",i+1);
				while(GetDigitalString(c)==-1);	/*判断用户的输入是否为数字字符串*/
				row=Str2Digital(c);	/*将用户输入的数字字符串转为整型数据*/
			}while(row>mt->m);	/*判断用户输入非零元素所在行是否超出了矩阵最大行数*/
			do{
				printf("->Column NO. of the %d node=",i+1);
				while(GetDigitalString(c)==-1);
				col=Str2Digital(c);
			}while(col>mt->n);
			printf("->Value of the %d node(int)=",i+1);
			while(GetDigitalString(c)==-1);
			data=Str2Digital(c);
			rs=LocateNode(mt,row,col);
		}while(rs==-1);
		/*数据接受正确后创建新结点*/
		q=(node *)malloc(sizeof(node));
		if(!q) return (-1);		/*如果没有正确的申请到空间则返回*/
		q->row=row;
		q->col=col;
		q->data=data;
		q->next=NULL;
		/*将新结点插入到相应的行和列*/
		p=mt->data[row-1];
		if(p==NULL) mt->data[row-1]=q;
		else{
			site=0;
			for(s=p;(p!=NULL)&&(p->col<col);s=p,p=p->next) site++;
			q->next=p;
			if(site!=0) s->next=q;
			else mt->data[row-1]=q;
		}
	}
	return (0);
}

/*矩阵a相加b,得到矩阵c*/
int MatrixAdd(matrix *a, matrix *b, matrix *c){
	node *p=NULL, *q=NULL, *s=NULL, *cs=NULL, *cp=NULL;
	int rs=0,i=0,row=0,col=0,data=0, site=0;
	if((a->m!=b->m)||(a->n!=b->n))	return (-1);	/*如果a,b不是同行同列的矩阵则返回*/
	rs=InitMatrix(c,a->m,a->n,0);		/*以a的行列数来初始化矩阵c*/
	if(rs==-1)  return (-1);
	for(i=0;i<a->m;i++){
		p=a->data[i];
		q=b->data[i];
		while(p!=NULL){
			if(q!=NULL){
				if(p->col<q->col){
					row=p->row;
					col=p->col;
					data=p->data;
					p=p->next;
				}else if(p->col==q->col){
					row=p->row;
					col=p->col;
					data=p->data+q->data;
					p=p->next;
					q=q->next;
				}else{
					row=q->row;
					col=q->col;
					data=q->data;
					q=q->next;
				}
			}else{
				row=p->row;
				col=p->col;
				data=p->data;
				p=p->next;
			}
			s=(node *)malloc(sizeof(node));
			if(!s) return (-1);
			s->row=row;
			s->col=col;
			s->data=data;
			s->next=NULL;
			/*将生成的结点插入到矩阵c的恰当位置*/
			cp=c->data[row-1];
			if(cp==NULL) c->data[row-1]=s;
			else{
				site=0;
				for(cs=cp;(cp!=NULL)&&(cp->col<col);cs=cp,cp=cp->next) site++;
				s->next=cp;
				if(site!=0)	cs->next=s;
				else c->data[row-1]=s;
			}
		}
		while(q!=NULL){
			row=q->row;
			col=q->col;
			data=q->data;
			q=q->next;
			s=(node *)malloc(sizeof(node));
			if(!s) return (-1);
			s->row=row;
			s->col=col;
			s->data=data;
			s->next=NULL;
			cp=c->data[row-1];
			if(cp==NULL) c->data[row-1]=s;
			else{
				site=0;
				for(cs=cp;(cp!=NULL)&&(cp->col<col);cs=cp,cp=cp->next) site++;
				s->next=cp;
				if(site!=0)	cs->next=s;
				else c->data[row-1]=s;
			}
		}
	}
	return (0);
}

/*输出矩阵mt的内容*/
int OutMatrix(matrix *mt){
	node *p=NULL;
	int i=0,j=0;
	if(mt->initialized!=1) return (-1);
	for(i=0;i<mt->m;i++){
		p=mt->data[i];
		for(j=0;j<mt->n;j++){
			if((p!=NULL)&&(j==p->col-1)){
				printf("%d\t",p->data);
				p=p->next;
			}else printf("0\t");
		}
		printf("\n");
	}
	return (0);
}

/*回收malloc分配的结点内存区*/
int Cleanup(matrix *mt){
	node *p=NULL;
	int i=0;
	if(mt->initialized!=1) return (-1);
	for(i=0;i<mt->m;i++){
		p=mt->data[i];
		for(;mt->data[i]!=NULL;p=mt->data[i]){
			mt->data[i]=p->next;
			free(p);
		}
	}
	return (0);
}

/*打印字符菜单*/
void MenuList(){
	printf("***************************************************\n");
	printf("* 1.Create matrix a and b                         *\n");
	printf("* 2.Matrix a plus matrix b                        *\n");
	printf("* 3.Display matrix a, matrix b and the result     *\n");
	printf("* 4.Cleanup result                                *\n");
	printf("* 5.Exit                                          *\n");
	printf("***************************************************\n");
	printf("* 1-5 Choice to operate                           *\n");
	printf("***************************************************\n");
}

/*根据返回输出系统信息*/
void Message(int msg){
	if(msg==0){
		printf("\nNOTE: The operation was successful completion of your choice!\n");
	}else{
		printf("\nERROR: Implementation mistakes!\n");
	}
	printf("\nPress any key to continue...\n");
}
int main(void){
	matrix a, b, c;
	int rs=0;
	char select;
	do{
		/*如果你是使用tc3.0/2.0，使用这个函数来清屏*/
//		clrscr();
		/*如果你是使用VC++，使用这个函数来清屏*/
		system("cls");
		MenuList();
		scanf("%c",&select);
		FlushSTDIN();
		switch(select){
			case '1':
				if((a.initialized==1)&&(b.initialized==1)){
					Cleanup(&a);
					Cleanup(&b);
				}
				if(c.initialized==1) Cleanup(&c);
				rs=CreateMatrixbyLabel(&a,"a");
				if(rs==-1){
					printf("!! Initialize matrix a error !!\n");
					getch();
					return (-1);
				}
				rs=CreateMatrixbyLabel(&b,"b");
				if(rs==-1){
					printf("!! Initialize matrix b error !!\n");
					getch();
					return (-1);
				}
				printf("[ Please input Nonzero node value of matrix a ]\n");
				rs=StorageMatrix(&a);
				if(rs==-1){
					printf("!! Storage matrix a error !!\n");
					getch();
					return (-1);
				}
				printf("[ Please input Nonzero node value of matrix b ]:\n");
				rs=StorageMatrix(&b);
				if(rs==-1){
					printf("!! Storage matrix b error !!\n");
					getch();
					return (-1);
				}
				break;
			case '2':
				if(c.initialized==1)
					Cleanup(&c);
				rs=MatrixAdd(&a, &b, &c);
				Message(rs);
				getch();
				break;
			case '3':
				rs=0;
				if((a.initialized==1)&&(b.initialized==1)){
					printf("\n******************matrix a*****************\n");
					rs=OutMatrix(&a);
					printf("\n******************matrix b*****************\n");
					rs=OutMatrix(&b);
				}
				if(c.initialized==1){
					printf("\n******Result of matrix a plus matrix b*****\n");
					rs=OutMatrix(&c);
				}
				Message(rs);
				getch();
				break;
			case '4':
				rs=0;
				if(c.initialized==1) rs=Cleanup(&c);
				Message(rs);
				getch();
				break;
			case '5':
				rs=0;
				if((a.initialized==1)&&(b.initialized==1)){
					Cleanup(&a);
					Cleanup(&b);
				}
				if(c.initialized==1) Cleanup(&c);
				break;
			default:break;
		}
	}while(select!='5');
	return (0);
}