12_11.cpp

用正交表实现了稀疏矩阵

#include<iostream>
using namespace std;
class element
{
public:
	int value;
	int colnum;
	int rownum;
	element*front;
	element*behind;
	element*above;
	element*below;
	element()
	{
		colnum=-1;
		rownum=-1;
		front=behind=above=below=NULL;
	}

	element(int it,int r,int c)
	{
		value=it;
		colnum=c;
		rownum=r;
		front=behind=above=below=NULL;
	}
};

class head
{
public:
	int num;
	element*thisline;
	head*next;
	head()
	{
		num=-1;
		thisline=new element;
		next=NULL;
	}
	head(int n,head*h)
	{
		num=n;
		thisline=new element;
		next=h;
	}
};

class matrix
{
private:
	head*col;
	head*row;
public:
	matrix()
	{
		col=row=new head;
	}
	void insert(int it,int r,int c)
	{
		head*tempc=col;
		while(tempc->next!=NULL&&tempc->next->num<c)
			tempc=tempc->next;
		if(tempc->next!=NULL)
		{
			if(tempc->next->num!=c)
			{
			    head*newc=new head(c,tempc->next);
			    tempc->next=newc;
			}
		}
		else
		{
			head*newc2=new head(c,NULL);
			tempc->next=newc2;
		}
		
		head*tempr=row;
		while(tempr->next!=NULL&&tempr->next->num<r)
			tempr=tempr->next;
		if(tempr->next!=NULL)
		{
			if(tempr->next->num!=r)
			{
			   head*newr=new head(r,tempr->next);
			   tempr->next=newr;
			}
		}	
		else
		{
			head*newr2=new head(r,NULL);
			tempr->next=newr2;
		}
		tempc=tempc->next;
		tempr=tempr->next;
		
		element* nodetempr=tempc->thisline;//cout<<nodetempc->below->colnum;
		while(nodetempr->below!=NULL&&nodetempr->below->rownum<r)
			nodetempr=nodetempr->below;
		element* nodetempc=tempr->thisline;
		while(nodetempc->behind!=NULL&&nodetempc->behind->colnum<c)
			nodetempc=nodetempc->behind;
		
		element*newnode=new element(it,r,c);//cout<<newnode->colnum;
		newnode->below=nodetempr->below;
		if(nodetempr->below!=NULL)
			nodetempr->below->above=newnode;//cout<<'Y';}
		nodetempr->below=newnode;//cout<<nodetempc->below->colnum;
		newnode->above=nodetempr;//cout<<newnode->above->colnum;

		newnode->behind=nodetempc->behind;
		if(nodetempc->behind!=NULL)
			nodetempc->behind->front=newnode;
		nodetempc->behind=newnode;//cout<<nodetempc->behind->rownum;
		newnode->front=nodetempc;//cout<<newnode->front->rownum;
	}
	void print()
	{
		head*temph=row->next;
		while(temph!=NULL)
		{
			element* temp=temph->thisline->behind;
		    while(temp!=NULL)
			{
				 for(int i=temp->front->colnum;i<temp->colnum-1;i++)
					 cout<<"        ";
			     cout<<'A'<<temp->rownum<<','<<temp->colnum<<'='<<temp->value<<"  ";
			     temp=temp->behind;
			}
			cout<<endl;
			temph=temph->next;
		}

	}
	int getval(int r,int c)
	{
	
		head*tempc=col;
		while(tempc->next!=NULL&&tempc->next->num<=c)
			tempc=tempc->next;
		if(tempc->num!=c)
			return 0;
		
		/*head*tempr=row;
		while(tempr->next!=NULL&&tempr->next->num<=r)
			tempr=tempr->next;
		if(tempr->num!=r)
			return 0;*/

		element*noder=tempc->thisline;
		//element*nodec=tempr->thisline;-+
		while(noder->below!=NULL&&noder->rownum<r)//&&nodec->colnum!=c)
		{
			noder=noder->below;
			//nodec=nodec->behind;
		}
		if(noder->rownum==r&&noder->colnum==c)
		   return noder->value;
		else
		    return 0;
		
	}
	head*getcol()
	{
		return col;
	}
	head*getrow()
	{
		return row;
	}
};

matrix *add(matrix *m1,matrix *m2)
{
	matrix*result=new matrix;
	head*tempr1=m1->getrow();
	head* tempc2=m2->getcol();
	head*tempr2=m2->getrow();
	head*tempc1=m1->getcol();
	int row1=-1,row2=-1,col1=-1,col2=-1;
	while(tempc1!=NULL)
	{
		col1=tempc1->num;
		tempc1=tempc1->next;
	}
	while(tempr1!=NULL)
	{
		row1=tempr1->num;
		tempr1=tempr1->next;
	}
	while(tempc2!=NULL)
	{
		col2=tempc2->num;
		tempc2=tempc2->next;
	}
	while(tempr2!=NULL)
	{
		row2=tempr2->num;
		tempr2=tempr2->next;
	}
	int rowmax=row1;
	if(row2>row1)
		rowmax=row2;
	int colmax=col1;
	if(col2>col1)
		colmax=col2;
	int i,j;
	for(i=0;i<=rowmax;i++)
		for(j=0;j<=colmax;j++)
		{
		   int val1=m1->getval(i,j);
		   int val2=m2->getval(i,j);
		   if(val1!=0||val2!=0)
			   result->insert(val1+val2,i,j);
		}
	return result;
}

int main()
{
	matrix *m=new matrix;
	matrix *m1=new matrix;
	matrix*m2=new matrix;
	m1->insert(3,0,0);m1->insert(7,0,2);m1->insert(2,2,2);m1->insert(9,3,3);
	m2->insert(2,0,0);m2->insert(3,3,1);m2->insert(5,2,1);m2->insert(7,4,4);
	m=add(m1,m2);
	m1->print();
	
	cout<<'+'<<endl;
	m2->print();
	cout<<'='<<endl;
	m->print();
	return 0;
}