《数据结构》读书笔记 第五章 行逻辑稀疏矩阵

写得好费劲啊。找了半天错,最后发现是rpos初始化出错了。

Matrix.h:行逻辑稀疏矩阵的基本操作

enum Statuses{WRONG=-1,OK=0};
enum Max{MAX_SIZE=100,MAX_RC=20};
typedef int Status;
typedef int Elem;
typedef struct
{
 int i,j;
 Elem e;
}Triple;

typedef struct
{
 int mu,nu,tu;
 int rpos[MAX_RC+1];
 Triple data[MAX_SIZE+1];
}Matrix;

Status CreateMatrix(Matrix &M)
{
 std::cout<<"请顺序输入矩阵的行数、列数、非零元素的数目:";
 std::cin>>M.mu>>M.nu>>M.tu;
 if(M.mu>MAX_RC||M.nu>MAX_RC||M.tu>MAX_SIZE)
  return WRONG;
 std::cout<<"请按顺序输入行、列、非零元素的值.\n";
 
 Triple T;
 Status k;
 
 M.data[0].i=0;
 memset(M.rpos,1,sizeof(int)*MAX_RC);
 for(int i=1;i<=M.tu;i++)
 {
  do
  {
   std::cout<<"请输入第"<<i<<"个非零元素所在的行、列、值:";
   std::cin>>T.i>>T.j>>T.e;
   if(T.i>MAX_RC||T.j>MAX_RC||T.i<1||T.j<1)
    k=WRONG;
   if(T.i<M.data[i-1].i||T.i==M.data[i-1].i&&T.j<=M.data[i-1].j)
    k=WRONG;
  }while(k==WRONG);
  M.data[i]=T;
  if(M.data[i].i>M.data[i-1].i)
   M.rpos[M.data[i].i]=i;
 }
 return OK;
}

void PrintMatrix(Matrix M)
{
 int i,j;
 Triple *p=&M.data[1];
 for(i=1;i<=M.mu;i++)
 {
  for(j=1;j<=M.nu;j++)
   if(p->i==i&&p->j==j)
    std::cout<<p++->e<<" ";
   else
    std::cout<<0<<" ";

  std::cout<<std::endl;
 }
}

Status AddMatrix(Matrix M,Matrix N,Matrix &Q)
{
 int i,m,n,q=1,bm,bn;
 if(M.mu!=N.mu||N.nu!=M.nu)
  return WRONG;
 Q.mu=M.mu;
 Q.nu=M.nu;
 for(i=1;i<=M.mu;i++)
 {
  Q.rpos[i]=q;
  m=M.rpos[i];
  n=N.rpos[i];
  bm=i<M.mu?M.rpos[i+1]:M.tu+1;
  bn=i<M.tu?N.rpos[i+1]:N.tu+1;
  while(m<bm&&n<bn)
  {
   if(M.data[m].j==N.data[n].j)
   {
    if(M.data[m].e+N.data[n].e!=0)
    {
     Q.data[q]=M.data[m];
     Q.data[q].e+=N.data[n].e;
     q++;
    }
    m++;
    n++;
   }
   else if(M.data[m].j<N.data[n].j)
   {
    Q.data[q]=M.data[m];
    q++;
    m++;
   }
   else if(M.data[m].j>N.data[n].j)
   {
    Q.data[q]=N.data[n];
    q++;
    n++;
   }
    
  }
  while(m<bm)
  {
   Q.data[q++]=M.data[m++];
  }
  while(n<bn)
  {
   Q.data[q++]=N.data[n++];
  }
 }
 Q.tu=q-1;
 if(Q.tu>MAX_SIZE)
  return WRONG;
 return OK;
}

void CopyMatrix(Matrix &M,Matrix N)
{
 M=N;
}

Status MultMatrix(Matrix M,Matrix N,Matrix &Q)
{
 int i,j,m,n,q,bm,bn,temp[MAX_RC+1];
 if(M.nu!=N.mu)
  return WRONG;
 Q.mu=M.mu;
 Q.nu=N.nu;
 Q.tu=0;
 if(M.tu*N.tu==0)
  return WRONG;
 for(i=1;i<=M.mu;i++)
 {
  Q.rpos[i]=Q.tu+1;
  memset(temp,0,sizeof(int)*(MAX_RC+1));
  bm=i<M.mu?M.rpos[i+1]:M.tu+1;
  for(m=M.rpos[i];m<bm;m++)
  {
   n=M.data[m].j;
   bn=i<N.nu?N.rpos[n+1]:N.tu+1;
   for(j=N.rpos[n];j<bn;j++)
   {
    temp[(N.data[j].j)]+=M.data[m].e*N.data[j].e;
   }
  }
  for(q=1;q<=Q.nu;q++)
   if(temp[q]!=0)
   {
    if(++Q.tu>MAX_SIZE)
     return WRONG; 
    Q.data[Q.tu].e=temp[q];
    Q.data[Q.tu].i=i;
    Q.data[Q.tu].j=q;
   }
 }
 return OK;
}
/*
Status MultMatrix(Matrix M,Matrix N,Matrix &Q)
{
 int mrow,m,bm,ncol,n,bn,temp[MAX_RC+1];
 if(M.nu!=N.mu)
  return WRONG;
 Q.mu=M.mu;
 Q.nu=N.nu;
 Q.tu=0;
 if(M.tu*N.tu==0)
  return WRONG;
 for(mrow=1;mrow<=M.mu;mrow++)
 {
  bm=mrow<M.mu?M.rpos[mrow+1]:(M.tu+1);
  memset(temp,0,sizeof(int)*(MAX_RC+1));
  Q.rpos[mrow]=Q.tu+1;
  for(m=M.rpos[mrow];m<bm;m++)
  {
   n=M.data[m].j;
   bn=n<N.mu?N.rpos[n+1]:(N.tu+1);
   for(ncol=N.rpos[n];ncol<bn;ncol++)
   {
    temp[N.data[ncol].j]+=M.data[m].e*N.data[ncol].e;
   }
  }
  for(ncol=1;ncol<=Q.nu;ncol++)
  {
   if(temp[ncol]!=0)
    if(++Q.tu>MAX_SIZE)
     return WRONG;
    else
    {
     Q.data[Q.tu].e=temp[ncol];
     Q.data[Q.tu].i=m;
     Q.data[Q.tu].j=ncol;
    }

  }
 }
 return OK;
}*/

 

main.cpp:主程序

#include <iostream>
#include "Matrix.h"

int main()
{
 Matrix M,N,S;
 std::cout<<"创建M:\n";
 CreateMatrix(M);
 std::cout<<"创建N:\n";
 CreateMatrix(N);
 MultMatrix(M,N,S);
 PrintMatrix(S);
 int i;
 for(i=1;i<S.tu;i++)
  std::cout<<S.data[i].e<<" ";
 return 0;
}

Leave a Reply

Your email address will not be published.