ccrosslist.cpp

一个用十字链表实现的稀疏矩阵类

#include "StdAfx.h"
#include "CCrossList.h"
Element::Element()
{
	i = 0;
	j = 0;
	value = 0;
	left	=	NULL;
	right	=	NULL;
	up		=	NULL;
	down	=	NULL;
	
}

Element::Element(int r, int c, double v)
{
	i = r;
	j = c;
	value = v;
	left	=	NULL;
	right	=	NULL;
	up		=	NULL;
	down	=	NULL;
	
	
}

CrossList::CrossList()
{

	m_elements = NULL;
	m_r = 0;
	m_c = 0;
	m_elements_counter = 0;
	m_elements_MaxNum	=	4750474;//3246290;//4750474;//2973696;///5;
	
	CHeaders = NULL;
	Rheaders = NULL;
}

CrossList::CrossList(int para_r, int para_c)
{
	m_r = para_r;
	m_c = para_c;
	m_elements_counter = 0;
	m_elements_MaxNum	=	4750474;//3246290;////m_r*m_c/1000;///5;
	m_elements = new Element[m_elements_MaxNum];
	CHeaders = new Element*[m_c];
	Rheaders = new Element*[m_r];
	for(int i=0; i<m_r; i++)
	{
		Rheaders[i]=NULL;
	}
	for(i=0; i<m_c; i++)
	{
		CHeaders[i]=NULL;
	}
}

CrossList::CrossList(const CrossList& motherboard)
{
	int i=0;
/*	if(m_elements)
	{
		for(i=0; i<m_c; i++)
		{
			delete CHeaders[i];
			CHeaders[i] = NULL;
		}
		delete CHeaders;
		CHeaders = NULL;
		for(i=0; i<m_r; i++)
		{
			delete Rheaders[i];
			Rheaders[i] = NULL;
		}
		delete Rheaders;
		Rheaders=NULL;
		delete[] m_elements;
		m_elements = NULL;
	}*/
	m_r = motherboard.m_r;
	m_c = motherboard.m_c;
	m_elements_counter = 0;
	m_elements_MaxNum	=	motherboard.m_elements_MaxNum;//m_r*m_c/1000;///5;
	m_elements = new Element[m_elements_MaxNum];
	CHeaders = new Element*[m_c];
	Rheaders = new Element*[m_r];
	for(i=0; i<m_r; i++)
	{
		Rheaders[i]=NULL;
	}
	for(i=0; i<m_c; i++)
	{
		CHeaders[i]=NULL;
	}
	Element *t;
	for(i=0; i<m_r; i++)
	{
		t = motherboard.Rheaders[i];
		while(t)
		{
			InsertElement(t->i, t->j, t->value);
			t=t->right;
		}
			
	}
}
CrossList::~CrossList()
{

	delete []CHeaders;
	delete []Rheaders;
	delete []m_elements;
//	for(int i=0; i<m_r; i++)
//	{
//		delete Rheaders[i];
// 	}
//	for( i=0; i<m_c; i++)
//	{
//		delete CHeaders[i];
//	}
}

void CrossList::InsertElement(int i, int j, double v)
{
	
//	if(m_elements_counter+1 > m_elements_MaxNum)
//	{
//		AfxMessageBox("Error...");
//	}
	m_elements[m_elements_counter].i=i;
	m_elements[m_elements_counter].j=j;
	m_elements[m_elements_counter].value=v;
	//修改行方向的链表
	//原来行i没有非零元素
	if(Rheaders[i]==NULL)
	{
		Rheaders[i] = &(m_elements[m_elements_counter]);                  //让对应的头链表元素指向该十字链表元素
		m_elements[m_elements_counter].left = NULL;
		m_elements[m_elements_counter].right= NULL;
	}
	//原来行i有非零元素
	else 
	{
		Element* temp;
		temp = Rheaders[i];
		while (temp->right) 
		{
			if(temp->right)
			{
				if(temp->j > j)
					break;
				
			}
			temp = temp->right;
		}
		if(temp->j > j)   //中间插入
		{
			if(temp->left) //temp不是第一个
			{
				m_elements[m_elements_counter].left = temp->left;
				m_elements[m_elements_counter].right = temp;
				temp->left->right = &(m_elements[m_elements_counter]);
				temp->left  =  &(m_elements[m_elements_counter]);

			}
			else			//temp原来是第一个,插入之后变成第二个
			{
				m_elements[m_elements_counter].left = NULL;
				m_elements[m_elements_counter].right = temp;
				Rheaders[i]	=	&(m_elements[m_elements_counter]);	
				temp->left  =  &(m_elements[m_elements_counter]);
			}
			
		}
		else              //末尾插入
		{
			if(temp->right==NULL)
			{
				temp->right = &(m_elements[m_elements_counter]);
				m_elements[m_elements_counter].left = temp;
				m_elements[m_elements_counter].right = NULL;
			}
		}
	}
	

	//修改列方向的链表
	//原来列i没有非零元素
	if(CHeaders[j]==NULL)
	{
		CHeaders[j] = &(m_elements[m_elements_counter]);                  //让对应的头链表元素指向该十字链表元素
		m_elements[m_elements_counter].up = NULL;
		m_elements[m_elements_counter].down= NULL;
	}
	//原来列i有非零元素C
	else 
	{
		Element* temp;
		temp = CHeaders[j];
		while (temp->down) 
		{
			if(temp)
			{
				if(temp->i > i)
					break;
				
			}
			temp = temp->down;
		}
		if(temp->i > i)   //中间插入
		{
			if(temp->up) //temp不是第一个
			{
				m_elements[m_elements_counter].up = temp->up;
				m_elements[m_elements_counter].down = temp;
				temp->up->down = &(m_elements[m_elements_counter]);
				temp->up  =  &(m_elements[m_elements_counter]);

			}
			else			//temp原来是第一个,插入之后变成第二个
			{
				m_elements[m_elements_counter].up = NULL;
				m_elements[m_elements_counter].down = temp;
				CHeaders[j]	=	&(m_elements[m_elements_counter]);	
				temp->up  =  &(m_elements[m_elements_counter]);
			}			
		}
		else              //末尾插入
		{
			if(temp->down==NULL)
			{
				temp->down = &(m_elements[m_elements_counter]);
				m_elements[m_elements_counter].up = temp;
				m_elements[m_elements_counter].down = NULL;
			}
		}
	}
	m_elements_counter++;
}

void CrossList::Print()
{
	for (int i=0; i<m_r; i++)   //按行
	{
		Element *e = Rheaders[i]; 
		while(e)
		{
			cout<<"X["<<e->i<<"]["<<e->j<<"] = "<<e->value<<"  ";
			e=e->right;
		}
		cout<<endl;
	}
/*	for (i=0; i<m_c; i++)		//按列
	{
		Element *e = CHeaders[i]; 
		while(e)
		{
			cout<<"X["<<e->i<<"]["<<e->j<<"] = "<<e->value<<"  ";
			e=e->down;
		}
		cout<<endl;
	}*/
}

void CrossList::PrintAll()
{
	double *cdata = new double[m_r];
	double *rdata = new double[m_c];
	
	for (int i=0; i<m_r; i++)
	{
		memset(rdata, 0, sizeof(double)*m_c);
		Element *e = Rheaders[i]; 
		while(e)
		{
			rdata[e->j]=e->value;
			e=e->right;
		}
		for(int j=0; j<m_c; j++)
		{
			cout<<setw(10)<<rdata[j];
		}
		cout<<endl;
	}
	cout<<endl;
	
/*	for ( i=0; i<m_c; i++)
	{
		memset(cdata, 0, sizeof(double)*m_r);
		Element *e = CHeaders[i]; 
		while(e)
		{
			cdata[e->i]=e->value;
			e=e->down;
		}
		for(int j=0; j<m_r; j++)
		{
			cout<<setw(10)<<cdata[j];
		}
		cout<<endl;
	}
	cout<<endl;cout<<endl;*/
//
	delete rdata;
	delete cdata;
}

//void CrossList::SaveAll(CString path)
//{
//	double *rdata = new double[m_c];
//	ofstream ofile(path, ios::out | ios::ate);
//	for (int i=0; i<m_r; i++)
//	{
//		memset(rdata, 0, sizeof(double)*m_c);
//		Element *e = Rheaders[i]; 
//		while(e)
//		{
//			rdata[e->j]=e->value;
//			e=e->right;
//		}
//		for(int j=0; j<m_c; j++)
//		{
//			ofile<<rdata[j]<<"  ";
//		}
//		ofile<<endl;
//	}
//	ofile<<endl;
//	delete rdata;
//
//}
CrossList CrossList::operator + (const CrossList & mx)
{
	CrossList result(m_r, m_c);
	if(m_r!=mx.m_r || m_c!=mx.m_c)
	{
		return result;
	}
	Element *e,*e1;
	for(int i=0; i<result.m_r; i++)
	{
		if(!(Rheaders[i]||mx.Rheaders[i]))    //都没有非零元素的情况
		{   
			continue;
		}
		else if(Rheaders[i] && !mx.Rheaders[i])   //当前对象行有非零元，mx没有
		{
			e=Rheaders[i];
			while(e)
			{
				result.InsertElement(e->i, e->j, e->value);
				e=e->right;
			}
		}
		else if(!Rheaders[i] && mx.Rheaders[i])    //相反
		{
			e=mx.Rheaders[i];
			while(e)
			{
				result.InsertElement(e->i, e->j, e->value);
				e=e->right;
			}
		} 
		else                                     //比较麻烦的情况，两个都含有非零元
		{
			e	=	Rheaders[i];
			e1	=	mx.Rheaders[i];
			while(e||e1)
			{
				if(e&&e1)
				{
					if(e->j==e1->j)
					{
						result.InsertElement(i,e->j,e->value+e1->value);
						e=e->right;
						e1=e1->right;
					}
					if(e&&e1&&(e->j > e1->j))
					{
						result.InsertElement(i,e1->j,e1->value);
						e1=e1->right;
					}
					if(e&&e1&&(e->j < e1->j))
					{
						result.InsertElement(i,e->j,e->value);
						e=e->right;
					}
				}
				if(!e&&e1)
				{
					result.InsertElement(i,e1->j,e1->value);
					e1=e1->right;
				}
				if(e&&!e1)
				{
					result.InsertElement(i,e->j,e->value);
					e=e->right;
				}
			}
		}
	}
	return result;
}
CrossList CrossList::operator - (const CrossList & mx)
{
	CrossList result(m_r, m_c);
	if(m_r!=mx.m_r || m_c!=mx.m_c)
	{
		return result;
	}
	Element *e,*e1;
	for(int i=0; i<result.m_r; i++)
	{
		if(!(Rheaders[i]||mx.Rheaders[i]))    //都没有非零元素的情况
		{   
			continue;
		}
		else if(Rheaders[i] && !mx.Rheaders[i])   //当前对象行有非零元，mx没有
		{
			e=Rheaders[i];
			while(e)
			{
				result.InsertElement(e->i, e->j, e->value);
				e=e->right;
			}
		}
		else if(!Rheaders[i] && mx.Rheaders[i])    //相反
		{
			e=mx.Rheaders[i];
			while(e)
			{
				result.InsertElement(e->i, e->j, -e->value);
				e=e->right;
			}
		} 
		else                                     //比较麻烦的情况，两个都含有非零元
		{
			e	=	Rheaders[i];
			e1	=	mx.Rheaders[i];
			while(e||e1)
			{
				if(e&&e1)
				{
					if(e->j==e1->j)
					{
						result.InsertElement(i,e->j,e->value-e1->value);
						e=e->right;
						e1=e1->right;
					}
					if(e&&e1&&(e->j > e1->j))
					{
						result.InsertElement(i,e1->j,-e1->value);
						e1=e1->right;
					}
					if(e&&e1&&(e->j < e1->j))
					{
						result.InsertElement(i,e->j,e->value);
						e=e->right;
					}
				}
				if(!e&&e1)
				{
					result.InsertElement(i,e1->j,-e1->value);
					e1=e1->right;
				}
				if(e&&!e1)
				{
					result.InsertElement(i,e->j,e->value);
					e=e->right;
				}
			}
		}
	}
	return result;
}
CrossList CrossList::operator *(const CrossList &mx)
{
	double temp = 0;
	CrossList result(m_r, mx.m_c);
	if(m_c!=mx.m_r)
	{
		return result;
	}
	for(int i=0; i<result.m_r; i++)
		for(int j=0; j<result.m_c; j++)
		{
			if(!Rheaders[i] || !mx.CHeaders[j])     //有一个无非零元就拉到
			{
				continue;
			}
			else
			{