consider two matrices A & B
Its solution is based on transposing a matrix B, so that its solution can be
computed easily.
Here I gave the solution in which each node has three variables index i,j
and value.
#include<iostream>
using namespace std;
struct node
{
int val,i,j;
node *next;
};
node *mul(node *head1,node *head2,node *head3)
{
node *head=head1,*t1,*t2,*t3,*t4=head1;
for(t1=head1,t2=head2,t3=head3;t1!=NULL;)
{
t3->val=0;
while((t2->next!=0) && (t2->next->j>=t2->j))
{
t3->val+=t2->val * t1->val;
t1=t1->next;
t2=t2->next;
}
t3->val+=t1->val*t2->val;
cout<<t3->val<<"\n";
int ll=0;
if(t2->next==0)
{
t1=t1->next;
t4=t1;
ll=1;
}
else if(t2->next->j < t2->j)
t1=t4;
t3=t3->next;
if(t2->next!=0)
t2=t2->next;
else
t2=head2;
}
return head3; //output list
}
node *transpose(node *head) //transposing list B
{
int g;
node *head1=head,*temp,*head2;
head2=head1->next;
temp=head;
while((temp->next->j)!=(temp->j) || (temp->next->i)<=(temp->i))
{
cout<<temp->val<<"\n";
if(temp->next!=0)
{
if(temp->next->j < temp->j)
{
node *t,*t1;
t1=temp->next->next;
t=temp->next;
temp->next=t1;
t->next=head1->next;
head1->next=t;
head1=t;
head2=head1->next;
}
temp=temp->next;
if(temp==0 || temp->next==0)
{
head1=head1->next;
head2=head1->next;
temp=head2;
}
}
}
int i=0,j=0,o;
for(temp=head;temp!=NULL;temp=temp->next)
{
o=1;
if(temp->next!=0 && temp->j != temp->next->j)
{
o=0;
}
if(!o)
{
temp->i=i;
temp->j=j;
i++;j=0;
}
else
{
temp->i=i;
temp->j=j;
}
j++;
}
return head;
}
node *create_matrix_list(int n,int x)
{
node *head,*temp;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 && j==0)
{
head=new node();
if(x!=3)
cin>>head->val;
head->next=NULL;
head->i=i;
head->j=j;
temp=head;
}
else
{
temp->next=new node();
temp=temp->next;
if(x!=3)
cin>>temp->val;
temp->i=i;
temp->j=j;
temp->next=0;
}
}
}
return head;
}
int main()
{
node *h1=NULL,*h2=NULL,*h3=NULL;
cout<<"Enter the size of matrix :";
int m;
cin>>m;
cout<<"Enter values for matrix A :";
h1=create_matrix_list(m,1);
cout<<"Enter values for matrix B :";
h2=create_matrix_list(m,2);
h3=create_matrix_list(m,3);
h2=transpose(h2);
h3=mul(h1,h2,h3);
for(temp=h3;temp!=NULL;temp=temp->next)
cout<<"i :"<<temp->i<<"\tj :"<<temp->j<<"\tval
:"<<temp->val<<"\n";
return 0;
}
sample input:
A : 1->2->3->4->5->6->7->8->9
B : 5->6->2->1->3->7->8->2->1
C : 31->18->19->73->51->49->115->84->79
Cheers
~ Jeeva ~
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
