稀疏距阵的链表实现.cpp

稀疏距阵的链表实现希望有所帮助

#include<iostream.h>

struct   node
{  
	int  row, col;
    struct node *down , *right;
    union  a_next
	{    
		float  a;
        struct node  *next;
	}x;
};


class xl
{
	private:
    node *head;
	int tu;//int mu,nu;
	public:
		xl()
		{
			node *p1,*p2;
			int mu,nu,k,max;
			tu=0;
			cout<<"键入距阵的行数:";
			cin>>mu;
            cout<<"键入距阵的列数:";
		    cin>>nu;
			cout<<endl;
			max=(mu>nu)?mu:nu;
			head=new node;
			head->col=nu;
			head->row=mu;
			head->x.next=NULL;
			p1=p2=head;
			for(k=1;k<=max;k++)
			{
				p2=new node;
				p2->row=k;
				p2->col=k;
				p2->right=p2;
				p2->down=p2;
				p1->x.next=p2;
				p1=p2;
			}
			p1->x.next=head;
		};


		void creat()
		{
			node *p,*p0,*p1;
            
			for(tu=0;;tu++)
			{
				p=new node;
				cout<<"键入该结点的行数:";
				cin>>p->row;
				while(p->row>head->row)
				{
					cout<<"你键入的行数有误，请重新输入!"<<endl;
                    cout<<"键入该结点的行数:";
				    cin>>p->row;
				}
				if(p->row==0)break;
				cout<<"键入该结点的列数:";
				cin>>p->col;
				while(p->col>head->col)
				{
					cout<<"你键入的行数有误，请重新输入!"<<endl;
                    cout<<"键入该结点的行数:";
				    cin>>p->col;
				}
				cout<<"键入该结点的数据:";
				cin>>p->x.a;
				p->down=NULL;p->right=NULL;
				cout<<endl;

				p0=head->x.next;
				while(p0->row!=p->row)p0=p0->x.next;
                p1=p0;
			    for(; p0->right!=p1 && p0->right->col < p->col ;p0=p0->right);
				p->right=p0->right;p0->right=p;
				

				p0=head->x.next;
				while(p0->col!=p->col)p0=p0->x.next;
				p1=p0;
				for(;p0->down!=p1 && p0->down->row < p->row;p0=p0->down);
				p->down=p0->down;p0->down=p;   
				
                
			}
             
		};
		void print()
		{
			node *p,*p1;
			int k=1,i=0;
			p=head->x.next;
			
			for(;p!=head;p=p->x.next)
			{
				p1=p->right;
				int j=1;

				if(p==p1 && k<=tu)
				{for(int j=0;j<head->col;j++)	cout<<"0"<<",";cout<<endl;i++;continue;}


				while(p1!=p)
				{
					
					while(p1->col-j>=1&&j<head->col)
					{
					   cout<<"0"<<",";
					   j++;
					   
					   
					}
					if(p1->col==j)
					{cout<<p1->x.a<<",";
					j++;k++;
					p1=p1->right;
					if(p1==p)
					{
						for(j;j<=head->col;j++)
						cout<<"0"<<",";
						cout<<endl;
						i++;
						//k++;
                    
					}
					continue;
					}
	
				}
				
				if(k>tu  && i<head->row)//输出数据全部完的时候以后剩下的0
				{for(int j=0;j<head->col;j++)cout<<"0"<<",";cout<<endl;i++;continue;}


               // if(k>tu && i<head->row)//输出数据全部完的时候以后剩下的0
				//{for(int j=0;j<head->col;j++)cout<<"1"<<",";cout<<endl;i++;continue;}
			
			
			}

		};



		//转置
		void derivation()
		{
			node *p,*p1,*p2;
			int k;

			k=head->row;
			head->row=head->col;
			head->col=k;

            p=head->x.next;
			while(p!=head)
			{
			
			   	p1=p;
			do
			{
				
                
				p2=p1->right;
				p1->right=p1->down;
				p1->down=p2;


				k=p1->col;
				p1->col=p1->row;
				p1->row=k;



				p1=p2;

				
				
			
			}
			while(p1!=p);
			
			
			

			p=p->x.next;
			}
		
			/*
			while(p!=head)
			{
				p1=p->right;
				p->right=p->down;
				p->down=p1;
				p=p->x.next;
				//cout<<":)"<<endl;
				
			
			}
			*/
		};


		void add(xl b, xl &c)//加法 
		{
			node *p,*p1,*p3,*p4,*p5,*p6,*p7;
			
			if(head->row!=b.head->row || head->col!=b.head->col )
			   cout<<"抱歉不能实现加法，原因可能是两个矩阵不是相同行数或列数"<<endl;

			else

			c.tu=tu+b.tu;


              
			p5=head->x.next;
			p6=b.head->x.next;
			p7=p3=c.head->x.next;
			while(p5!=head && p6!=b.head && p3!=c.head)
			{
			
				p=p5->right;
		        p1=p6->right;
				p3=p7;
		      
			while(p1!=p6 && p!=p5)
		   {
               
			   p4=p3;
			   p3=new node;
			   p4->right=p3;

			   if(p1->col<p->col){*p3=*p1;p1=p1->right;p3->right=p7;}
			   else if(p1->col>p->col){*p3=*p;p=p->right;p3->right=p7;}
			   else 
			   {p3->x.a=p1->x.a+p->x.a;p3->col=p->col;p3->row=p->row;p=p->right;p1=p1->right;p3->right=p7;}
               
			}
			while(p!=p5)
			{p4=p3;p3=new node;p4->right=p3;*p3=*p;p=p->right;p3->right=p7;}
			while(p1!=p6)
			{p4=p3;p3=new node;p4->right=p3;*p3=*p1;p1=p1->right;p3->right=p7;}


			p5=p5->x.next;
			p6=p6->x.next;
			p7=p7->x.next;

           
			}; 
			
		};
				
};
void main()
{
	xl a;
	a.creat();
	a.print();
	cout<<endl;
	cout<<":)"<<endl;
	cout<<endl;

	xl b;
	b.creat();
	b.print();

	cout<<endl;
	cout<<":)"<<endl;
	cout<<endl;

	xl c;
	a.add(b,c);
	c.print();
	cout<<"加法成功:)"<<endl;
	cout<<endl;


/*注:

    1两矩阵相加的前提：两矩阵的行数和列数分别对应相等； 

    2两矩阵相加的结果：行、列数不变； 

    3具有相同行号和列号的元素相加，如果相加结果为0，则不在结果矩阵中建立结点；

    4最后输入的参数是用于存储加法结果的距阵

*/

    cout<<"输入用于验证求导的参数:"<<endl;
	xl d;
	d.derivation();
	d.print();
	cout<<"求导成功:)"<<endl;
}