三元组表spma.cpp

数据结构经典课件(附带各章的经典算法) 具体代码是使用C语言编写的

#include "stdlib.h"
#define MAXSIZE 12
#define MAXCOL  8
typedef int ElemType;
typedef struct
{
  int r,c;
  ElemType d;
}TupNode;
typedef struct
{ 
  TupNode data[MAXSIZE];
  int rows,cols,nums;
}TSMatrix;

bool access(TSMatrix M,int i,int j,ElemType &e)
{   if(i>M.rows || j>M.cols)
      return false; 
	int t=1;
	while(t<=M.nums && M.data[t].r<i)
		t++;
    if(t>M.nums) {e=0;return true;}
    while(t<=M.nums && M.data[t].r==i && M.data[t].c<j)
		t++;
	if(M.data[t].r==i && M.data[t].c==j)
	{e=M.data[t].d;return true;}
	else
	{e=0;return true;}
}

void TransposeSMatrix(TSMatrix M,TSMatrix &T)
{  
   T.rows=M.cols;T.cols=M.rows;T.nums=M.nums;
   int q=1;
   for(int col=1;col<=M.cols;col++)
    for(int p=1;p<=M.nums;p++)
      if(M.data[p].c==col)
	  { T.data[q].r=M.data[p].c;
	    T.data[q].c=M.data[p].r;
	    T.data[q].d=M.data[p].d;
	    q++;
	  }
      
}
void FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{  int num[MAXCOL],cpot[MAXCOL];
   T.rows=M.cols;T.cols=M.rows;T.nums=M.nums;
   for(int col=1;col<=M.cols;col++)
	   num[col]=0;
   for(int t=1;t<=M.nums;t++)
	   ++num[M.data[t].c];
   cpot[1]=1;
   for( col=2;col<=M.cols;col++)
	   cpot[col]=cpot[col-1]+num[col-1];
   int q;
   for(int p=1;p<=M.nums;p++)
	  { col=M.data[p].c;
	    q=cpot[col];
	    T.data[q].r=M.data[p].c;
	    T.data[q].c=M.data[p].r;
	    T.data[q].d=M.data[p].d;
	    ++cpot[col];
	  }
}
void main()
{ TSMatrix M,T;
  ElemType e;
  TupNode a[]={{1,2,12},{1,3,9},{3,1,-3},{3,6,14},{4,3,24},
  {5,2,18},{6,1,15},{6,4,-7}};
  int i;
  M.rows =6;M.cols=7;M.nums=8;
  for(i=1;i<=M.nums ;i++)
    {M.data[i].r=a[i-1].r;
     M.data[i].c=a[i-1].c;
     M.data[i].d=a[i-1].d;
    }
  bool b=access(M,3,6,e);
  TransposeSMatrix(M,T);
  FastTransposeSMatrix(M,T);
  
}