crosslink.cpp

本程序是用十字链表来存储矩阵并实现两个矩阵的相乘

# include<iostream.h>
# include<stdlib.h>
# include<fstream.h>
# include<iomanip.h>
struct crossnode									//存储三元组的大十字结点
{
		long row ,col;
		long val;
		crossnode *right,*down;
};

struct crosslink									//十字链表的定义
{
		crossnode *head;
		
		crosslink();
		void init(long i,long j);					//初始化，相当于构造函数
		void insert(long i,long j,long value);		//向矩阵中插入元素
		long get(long i,long j);					//取矩阵中的元素
		void disply();
		int row_num();
		int col_num();
		//void multiply(crosslink *a,crosslink *b);	//乘法运算
};
//构造函数
crosslink::crosslink()								
{}
//返回矩阵的行数
int crosslink::row_num()							
{
	if(head->down==head) return 0;
	return head->row;
}
//返回矩阵的列数
int crosslink::col_num()							
{
	if(head->right==head) return 0;
	return head->col;
}
//显示矩阵
void crosslink::disply()							
{
	long i,j;
	for(i=1;i<=row_num();i++)
	{
		for(j=1;j<=col_num();j++)
			cout<<get(i,j)<<setw(4);
		cout<<endl;
	}
}
//初始化矩阵，相当于构造函数
void crosslink::init(long i,long j)					
{
	int ai;
	head=new crossnode;
	head->row=i;
	head->col=j;
	head->right=head;
	head->down=head;

	crossnode *s;

	for(ai=0;ai<j;ai++)
	{
		s=new crossnode;
		s->col=j-ai;
		s->row=0;
		s->val=0;
		s->down=s;
		
		s->right=head->right;
		head->right=s;
	}
	
	for(ai=0;ai<i;ai++)
	{
		s=new crossnode;
		s->row=i-ai;
		s->col=0;
		s->val=0;
		s->right=s;

		s->down=head->down;
		head->down=s;
	}

}


//在i行j列插入值为value的数
void crosslink::insert(long i,long j,long value)
{
  if(value!=0)
  {
	crossnode *temp1,*temp2;
	crossnode *s=new crossnode;
	s->row=i;
	s->col=j;
	s->val=value;
	
	temp1=head->right;
	while(temp1->col!=j)	temp1=temp1->right;
	
	temp2=temp1;
	temp1=temp1->down;
	while(temp1->row<i&&temp1->row!=0)		
	{
		temp1=temp1->down;
		temp2=temp2->down;
	}
	s->down=temp2->down;
	temp2->down=s;
//------------------------------------------------------------
	temp1=head->down;
	while(temp1->row!=i)	temp1=temp1->down;
	
	temp2=temp1;
	temp1=temp1->right;
	while(temp1->col<j&&temp1->col!=0)		
	{
		temp1=temp1->right;
		temp2=temp2->right;
	}
	s->right=temp2->right;
	temp2->right=s;
  }
}

//取i行j列的元素，若没有返回零
long crosslink::get(long i,long j)					
{
	crossnode *temp1=head->right;
	while(temp1->col!=j)       temp1=temp1->right;
	
	temp1=temp1->down;
	while(temp1->row!=i&&temp1->row!=0)	temp1=temp1->down;
	if(temp1->row!=0) 
		return temp1->val;
	else
		return 0;
}

//实现矩阵相乘的算法
//a,b相乘，结果放到c中
void multiply(crosslink *&c,crosslink *a,crosslink *b)	
{														
	if(a->col_num()!=b->row_num())						//判断两个矩阵是否能够相乘
	
	{
		cout<<"a,b两矩阵不能相乘!!!!!"<<endl;
		cin.get();
		exit(0);
	}

	c->init(a->row_num(),b->col_num());

	int i,j,k;
	long temp=0;
	for(i=1;i<=a->row_num();i++)
		for(j=1;j<=b->col_num();j++)
		{	
			for(k=1;k<=a->col_num();k++)
			temp+=a->get(i,k)*b->get(k,j);
			c->insert(i,j,temp);
			temp=0;
		}
}

//从文件中读入数据
void read_data_file(char filename[],crosslink *&a,crosslink*&b)
{
	long row ,col ,data;
	long i=5,j=5;
	//filename="data.txt";
	fstream fp;
	fp.open(filename,ios::in);
	while(!fp)
	{
		cout<<"file open erorr!!!"<<endl;
		exit(0);
	}
	fp>>i;			//将值读入矩阵a
	fp>>j;
	a->init(i,j);
	while(!fp.eof())
	{
		fp>>row;
		fp>>col;
		fp>>data;
		if(row==0)
			break;
		a->insert(row,col,data);
	}
	cout<<endl;
	a->disply();

	fp>>i;				//将值读入矩阵b
	fp>>j;	
	b->init(i,j);
	while(!fp.eof())
	{
		fp>>row;
		fp>>col;
		fp>>data;
		if(row==0)
			break;
		b->insert(row,col,data);
	}
	cout<<endl;
	b->disply();
	cout<<endl;
	fp.close();
}

void main()
{
	crosslink *a=new crosslink,*b=new crosslink,*c=new crosslink;

    read_data_file("data.txt",a,b);
	multiply(c,a,b);

    c->disply();
		
			
}