strassen矩阵乘法.cpp

递归和分治法解一系列经典算法

//Strassen矩阵乘法

#include<iostream.h> 

struct node
{
	int data;
	node *next;
};

class Vector
{
public:
	node * list;
	int n; 
public:
	void init();
	void show();
	void ch(Vector v1,Vector v2);
}; 

void Vector::init()
{
	node *p1, *p2, *head;
	int a;
	head=0;
	for(int i=0;i<n*n;i++)
	{
		cin>>a;
		p1=new node;
		p1->data=a;
		if(head==0)
		{
			head=p1;
			p2=p1;
		}
		else
		{
			p2->next=p1;
			p2=p1;
		}
	}
	list=head;
}

void Vector::ch(Vector v1,Vector v2)
{
	node *p1,*p2,*head;
	node *vp1=v1.list;
	node *vp2=v2.list;
	head=0;
	int m=0;
	for(int k=0; k<n*n; k++)
	{
		int ji=0;
		for(int j=0; j<n; j++)
		{
			ji+=(vp1->data)*(vp2->data);
			if(j<n-1)
			{
				vp1=vp1->next;
				for(int l=0; l<n; l++) vp2=vp2->next;
			}
			else break;
		}
		p1=new node;
		p1->data=ji;
		if(head==0)
		{
			head=p1;
			p2=p1;
		}
		else
		{
			p2->next=p1;
			p2=p1;
		} //将节点加入到链表中
		m++;
		vp1=v1.list;
		vp2=v2.list;
		for(j=0; j<m/n; j++)
			for(int e=0; e<n; e++) vp1=vp1->next;
			for(j=0; j<m%n; j++) vp2=vp2->next;
	}
	this->list=head;
}

void Vector::show()
{
	node *p1;
	int b;
	int c=0;
	p1=this->list;
	for(int i=0; i<n*n; i++)
	{
		b=p1->data;
		p1=p1->next;
		cout<<b<<'\t';
		c++;
		if(c%n==0) cout<<endl;
	}
	cout<<endl;
}

void main()
{
	Vector A,B,C,AB,BC,D,E;
	int jie;
	cout<<"请输入矩阵的阶数: "<<endl;
	cin>>jie;
	A.n=B.n=C.n=D.n=E.n=AB.n=BC.n=jie;
	cout<<"请输入矩阵A(两数之间用空格或回车隔开):"<<endl;
	A.init();
	cout<<"刚输入的矩阵A是:"<<endl;
	A.show();
	cout<<"请输入矩阵B(两数之间用空格或回车隔开):"<<endl;
	B.init();
	cout<<"刚输入的矩阵B是:"<<endl;
	B.show();
	cout<<"请输入矩阵C(两数之间用空格或回车隔开):"<<endl;
	C.init();
	cout<<"刚输入的矩阵C是:"<<endl;
	C.show();
	AB.ch(A,B);
	cout<<"AB相乘得到的矩阵是:"<<endl;
	AB.show();
	BC.ch(B,C);
	cout<<"BC相乘得到的矩阵是:"<<endl;
	BC.show();
	D.ch(A,BC);
	cout<<"A与BC相乘得到的矩阵是:"<<endl;
	D.show();
	E.ch(AB,C);
	cout<<"AB与C相乘得到的矩阵是:"<<endl;
	E.show();
}