十字链表实现2个矩阵的加法 求解法严维明数据结构p105

十字链表实现2个矩阵的加法 求解法严维明数据结构p105

#include <iostream>
#include <malloc.h>
using namespace std;

typedef int Status;
typedef int ElemType;

#define OK 1

typedef struct OLNode
{
int i,j;
ElemType e;
struct OLNode *right,*down;
} OLNode, *OLink;

typedef struct
{
OLink *rhead,*chead;
int mu,nu,tu;
} CrossList;

Status CreatSMatrix_OL(CrossList &M);
void PrintSMatrix(CrossList &M);
Status AddSMatrix(CrossList &M,CrossList &N);

int main()
{
CrossList M,N;
CreatSMatrix_OL(M);
PrintSMatrix(M);
CreatSMatrix_OL(N);
PrintSMatrix(N);
AddSMatrix(M,N);
PrintSMatrix(M);
return 0;
}

Status CreatSMatrix_OL(CrossList &M)
{
OLink temp,p1,p2;
int i,j;
ElemType e;
cout<<"M.mu=? M.nu=?"<<endl;
cin>>M.mu>>M.nu;
M.tu=0;
M.rhead=(OLink *)malloc(sizeof(OLink)*(M.mu+1));
M.chead=(OLink *)malloc(sizeof(OLink)*(M.nu+1));
for(i=0;i<=M.mu;i++)
M.rhead[i]=NULL;
for(i=0;i<=M.nu;i++)
M.chead[i]=NULL;
cin>>i>>j>>e;
while(i!=0)
{
temp=(OLNode *)malloc(sizeof(OLNode));
(*temp).i=i;
(*temp).j=j;
(*temp).e=e;
if(M.rhead[i]==NULL||M.rhead[i]->j>j)
{
temp->right=M.rhead[i];
M.rhead[i]=temp;
}
else
{
p1=M.rhead[i];
while(p1->right&&p1->right->j<j)
p1=p1->right;
temp->right=p1->right;
p1->right=temp;
}
if(M.chead[j]==NULL||M.chead[j]->i>i)
{
temp->down=M.chead[j];
M.chead[j]=temp;
}
else
{
p1=M.chead[j];
while(p1->down&&p1->down->i<i)
p1=p1->down;
temp->down=p1->down;
p1->down=temp;
}
M.tu++;
cin>>i>>j>>e;
}
return OK;
}

void PrintSMatrix(CrossList &M)
{
OLink temp;
int i;
cout<<"M.mu="<<M.mu<<" M.nu="<<M.nu<<" M.tu="<<M.tu<<endl;
for(i=1;i<=M.mu;i++)
{
temp=M.rhead[i];
while(temp)
{
cout<<"i="<<temp->i<<" j="<<temp->j<<" e="<<temp->e<<endl;
temp=temp->right;
}
}
}

Status AddSMatrix(CrossList &M,CrossList &N)
{
OLink *a,pa,pb,pre;
OLNode *temp;
a=(OLink *)malloc((M.nu+1)*sizeof(OLink));
int i;
for(i=1;i<=M.nu;i++)
a[i]=M.chead[i];
for(i=1;i<=M.mu;i++)
{
pa=M.rhead[i];
pb=N.rhead[i];
pre=NULL;
while(pb!=NULL)
{
if(pa==NULL||pa->j>pb->j)
{
temp=(OLNode *)malloc(sizeof(OLNode));
temp->i=pb->i;
temp->j=pb->j;
temp->e=pb->e;
//pb=pb->right;
if(pre==NULL)
M.rhead[i]=temp;
else pre->right=temp;
temp->right=pa;
pre=temp;
if(M.chead[pb->j]==NULL||M.chead[pb->j]->i>pb->i)
{
temp->down=M.chead[pb->j];
M.chead[pb->j]=temp;
}
else
{
while(a[pb->j]->down!=NULL&&a[pb->j]->down->i<pb->i)
a[pb->j]=a[pb->j]->down;
temp->down=a[pb->j]->down;
a[pb->j]->down=temp;
}
a[pb->j]=temp;
M.tu++;
pb=pb->right;
}
else if(pa!=NULL&&pa->j<pb->j)
{
pre=pa;
pa=pa->down;
}
else if(pa->j==pb->j)
{
pa->e+=pb->e;
if(pa->e==0)
{
if(pre==NULL)
M.rhead[i]=M.rhead[i]->right;
else
pre->right=pa->right;
temp=pa;
pa=pa->right;
while(a[pa->j]->down->i!=pa->i)
a[pa->j]=a[pa->j]->down;
if(M.chead[pa->j]==pa)
{
M.chead[pa->j]=pa->down;
a[pa->j]=pa->down;
}
else a[pa->j]->down=pa->down;
free(pa);
M.tu--;
}
}
pb=pb->right;
}
}
return OK;
}
按书写的。错了。求写过的人贴下代码对比一下

----------------解决方案--------------------------------------------------------

今天终于调好了
#include <iostream>
#include <malloc.h>
using namespace std;

typedef int Status;
typedef int ElemType;

#define OK 1

typedef struct OLNode
{
int i,j;
ElemType e;
struct OLNode *right,*down;
} OLNode, *OLink;

typedef struct
{
OLink *rhead,*chead;
int mu,nu,tu;
} CrossList;

Status CreatSMatrix_OL(CrossList &M);
void PrintSMatrix(CrossList &M);
Status AddSMatrix(CrossList &M,CrossList &N);

int main()
{
CrossList M,N;
CreatSMatrix_OL(M);
PrintSMatrix(M);
CreatSMatrix_OL(N);
PrintSMatrix(N);
AddSMatrix(M,N);
PrintSMatrix(M);
return 0;
}

Status CreatSMatrix_OL(CrossList &M)
{
OLink temp,p1,p2;
int i,j;
ElemType e;
cout<<"M.mu=? M.nu=?"<<endl;
cin>>M.mu>>M.nu;
M.tu=0;
M.rhead=(OLink *)malloc(sizeof(OLink)*(M.mu+1));
M.chead=(OLink *)malloc(sizeof(OLink)*(M.nu+1));
for(i=0;i<=M.mu;i++)
M.rhead[i]=NULL;
for(i=0;i<=M.nu;i++)
M.chead[i]=NULL;
cin>>i>>j>>e;
while(i!=0)
{
temp=(OLNode *)malloc(sizeof(OLNode));
(*temp).i=i;
(*temp).j=j;
(*temp).e=e;
if(M.rhead[i]==NULL||M.rhead[i]->j>j)
{
temp->right=M.rhead[i];
M.rhead[i]=temp;
}
else
{
p1=M.rhead[i];
while(p1->right&&p1->right->j<j)
p1=p1->right;
temp->right=p1->right;
p1->right=temp;
}
if(M.chead[j]==NULL||M.chead[j]->i>i)
{
temp->down=M.chead[j];
M.chead[j]=temp;
}
else
{
p1=M.chead[j];
while(p1->down&&p1->down->i<i)
p1=p1->down;
temp->down=p1->down;
p1->down=temp;
}
M.tu++;
cin>>i>>j>>e;
}
return OK;
}

void PrintSMatrix(CrossList &M)
{
OLink temp;
int i;
cout<<"M.mu="<<M.mu<<" M.nu="<<M.nu<<" M.tu="<<M.tu<<endl;
/*for(i=1;i<=M.mu;i++)
{
temp=M.rhead[i];
while(temp)
{
cout<<"i="<<temp->i<<" j="<<temp->j<<" e="<<temp->e<<endl;
temp=temp->right;
}
}*/
for(i=1;i<=M.nu;i++)
{
temp=M.chead[i];
while(temp)
{
cout<<"i="<<temp->i<<" j="<<temp->j<<" e="<<temp->e<<endl;
temp=temp->down;
}
}
}

Status AddSMatrix(CrossList &M,CrossList &N)
{
int k=0;
OLink *a,pa,pb,pre;
OLNode *temp;
a=(OLink *)malloc((M.nu+1)*sizeof(OLink));
int i;
for(i=1;i<=M.nu;i++)
a[i]=M.chead[i];
for(i=1;i<=M.mu&&i<=N.mu;i++)
{
pa=M.rhead[i];
pb=N.rhead[i];
pre=NULL;
while(pb!=NULL)
{
while(pa!=NULL&&pa->j<pb->j)
{
k++;
pre=pa;
pa=pa->right;
if(k==100)
break;
}
if(pa==NULL||pa->j>pb->j)
{
temp=(OLNode *)malloc(sizeof(OLNode));
temp->i=pb->i;
temp->j=pb->j;
temp->e=pb->e;
if(pre==NULL)
M.rhead[i]=temp;
else pre->right=temp;
temp->right=pa;
pre=temp;
if(M.chead[pb->j]==NULL||M.chead[pb->j]->i>pb->i)
{
temp->down=M.chead[pb->j];
M.chead[pb->j]=temp;
}
else
{
while(a[pb->j]->down!=NULL&&a[pb->j]->down->i<pb->i)
a[pb->j]=a[pb->j]->down;
temp->down=a[pb->j]->down;
a[pb->j]->down=temp;
}
a[pb->j]=temp;
M.tu++;
pb=pb->right;
}
else if(pa->j==pb->j)
{
pa->e+=pb->e;
if(pa->e==0)
{
if(pre==NULL)
M.rhead[i]=M.rhead[i]->right;
else
pre->right=pa->right;
temp=pa;
pa=pa->right;
cout<<a[temp->j]->i<<a[temp->j]->j<<a[temp->j]->e<<endl;
if(M.chead[temp->j]->i==temp->i)
{
M.chead[pb->j]=M.chead[pb->j]->down;
a[pb->j]=M.chead[pb->j];
}
else
{
while(a[pb->j]->down->i!=pb->i)
{
a[pb->j]=a[pb->j]->down;
cout<<a[pb->j]->i<<a[pb->j]->j<<a[pb->j]->e<<endl;
}
a[pb->j]->down=temp->down;
}
M.tu--;
}
pb=pb->right;
}
}
}
return OK;
}

----------------解决方案--------------------------------------------------------