数据结构C语言兑现稀疏矩阵的压缩和运算的三元组顺序表表示法
总结：三元组顺序表示法表示稀疏矩阵有一定的局限性 ， 特别是在矩阵的乘法的时候，非常复杂。
头文件
#ifndef SYZHEAD_H_INCLUDED
#define SYZHEAD_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType ;
typedef struct
{
int row ;
int col ;
ElemType elem ;
} Triple ;
typedef struct
{
Triple* pdata ;
int rnum ;
int cnum ;
int tnum ;
} TSMatrix ;
int CreateMatrix( TSMatrix* M ) ;
int DestroyMatrix( TSMatrix* M ) ;
int PrintMatrix( TSMatrix* M ) ;
int PrintTriple( TSMatrix* M ) ;
int CopyMatrix( TSMatrix* Dest , TSMatrix Source ) ;
int TransposeMatrix( TSMatrix* Dest , TSMatrix Source ) ;
int AddMatrix( TSMatrix* Q , TSMatrix M , TSMatrix N ) ;
int SubMatrix( TSMatrix* Q , TSMatrix M , TSMatrix N ) ;
int MultMatrix( TSMatrix* Q , TSMatrix M , TSMatrix N ) ;
#endif // SYZHEAD_H_INCLUDED
函数的实现
#include "syzhead.h"
int CreateMatrix( TSMatrix* M )
{
printf( "please input the rnum , cnum , tnum of M\n" ) ;
scanf( "%d%d%d" , &M->rnum , &M->cnum , &M->tnum ) ;
M->pdata = ( Triple* )malloc( ( M->tnum + 1 )* sizeof( Triple ) ) ;
if( !M->pdata )
{
exit( 1 ) ;
}
int count = 1 ;
while( count <= M->tnum )
{
scanf( "%d%d%d" , &M->pdata[count].row , &M->pdata[count].col , &M->pdata[count].elem ) ;
if( M->pdata[count].row > M->rnum || M->pdata[count].col > M->cnum )
{
printf( "Index ERROR!\n" ) ;
exit( 1 ) ;
}
count++ ;
}
return 0 ;
}
int DestroyMatrix( TSMatrix* M )
{
if( !M->pdata )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
free( M->pdata ) ;
M->pdata = NULL ;
M->cnum = 0 ;
M->rnum = 0 ;
M->tnum = 0 ;
return 0 ;
}
int PrintMatrix( TSMatrix* M )
{
int i , j ;
int count = 1 ;
for( i = 1 ; i <= M->rnum ; i++ )
{
for( j = 1 ; j <= M->cnum ; j++ )
{
if( ( M->pdata[count].row == i ) && ( M->pdata[count].col == j ) )
{
printf( "%d\t" , M->pdata[count].elem ) ;
count++ ;
}
else
{
printf( "0\t" ) ;
}
}
printf( "\n" ) ;
}
return 0 ;
}
int PrintTriple( TSMatrix* M )
{
int i ;
for( i = 1 ; i <= M->tnum ; i++ )
{
printf( "%d\t%d\t%d\n" , M->pdata[i].row , M->pdata[i].col , M->pdata[i].elem ) ;
}
return 0 ;
}
int CopyMatrix( TSMatrix* Dest , TSMatrix Source )
{
Dest->cnum = Source.cnum ;
Dest->rnum = Source.rnum ;
Dest->tnum = Source.tnum ;
Dest->pdata = ( Triple* )malloc( (Dest->tnum + 1 ) * sizeof( Triple ) ) ;
int i = 1 ;
while( i <= Dest->tnum )
{
Dest->pdata[i].row = Source.pdata[i].row ;
Dest->pdata[i].col = Source.pdata[i].col ;
Dest->pdata[i].elem = Source.pdata[i].elem ;
i++ ;
}
return 0 ;
}
int TransposeMatrix( TSMatrix* Dest , TSMatrix Source )
{
Dest->rnum = Source.cnum ;
Dest->cnum = Source.rnum ;
Dest->tnum = Source.tnum ;
Dest->pdata = ( Triple* )malloc( (Dest->tnum + 1 ) * sizeof( Triple ) ) ;
int i ;
int col ;
int count = 1 ;
for( col = 1 ; col <= Source.cnum ; col++ )
{
for( i = 1 ; i <= Source.tnum ; i++ )
{
if( Source.pdata[i].col == col )
{
Dest->pdata[count].row = Source.pdata[i].col ;
Dest->pdata[count].col = Source.pdata[i].row ;
Dest->pdata[count].elem = Source.pdata[i].elem ;
count++ ;
}
}
}
return 0 ;
}
int AddMatrix( TSMatrix* Q , TSMatrix M , TSMatrix N )
{
if( M.rnum != N.rnum || M.cnum != N.cnum )
{
printf( "can't add!\n" ) ;
exit( 1 ) ;
}
Q->cnum = M.cnum ;
Q->rnum = M.rnum ;
int memsize = M.tnum + N.tnum + 1 ;
Q->pdata = ( Triple* )malloc( memsize * sizeof( Triple ) ) ;
if( !Q->pdata )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
int i ;
int j ;
int count = 1 ;
int countm = 1 ;
int countn = 1 ;
int temp = 0 ;
for( i = 1 ; i <= Q->rnum ; i++ )
{
for( j = 1 ; j <= Q->cnum ; j++ )
{
if( ( M.pdata[countm].row == i ) && ( M.pdata[countm].col == j ) && ( N.pdata[countn].row == i ) &&( N.pdata[countn].col == j ) )
{
temp = M.pdata[countm].elem + N.pdata[countn].elem ;
countm++ ;
countn++ ;
}
else if( ( M.pdata[countm].row == i ) && ( M.pdata[countm].col == j ) )
{
temp = M.pdata[countm].elem ;
countm++ ;
}
else if( ( N.pdata[countn].row == i ) &&( N.pdata[countn].col == j ) )
{
temp = N.pdata[countn].elem ;
countn++ ;
}
if( temp )
{
if( count > memsize )
{
Q->pdata = ( Triple* )realloc( Q->pdata , ( memsize + 1) * sizeof( Triple ) ) ;
memsize += 1 ;
}
Q->pdata[count].row = i ;
Q->pdata[count].col = j ;
Q->pdata[count].elem = temp ;
count++ ;
temp = 0 ;
}
}
}
Q->tnum = count - 1 ;
return 0 ;
}
int SubMatrix( TSMatrix* Q , TSMatrix M , TSMatrix N )
{
if( M.rnum != N.rnum || M.cnum != N.cnum )
{
printf( "can't sub!\n" ) ;
exit( 1 ) ;
}
Q->cnum = M.cnum ;
Q->rnum = M.rnum ;
int memsize = M.tnum + N.tnum + 1 ;
Q->pdata = ( Triple* )malloc( memsize * sizeof( Triple ) ) ;
if( !Q->pdata )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
int i ;
int j ;
int count = 1 ;
int countm = 1 ;
int countn = 1 ;
int temp = 0 ;
for( i = 1 ; i <= Q->rnum ; i++ )
{
for( j = 1 ; j <= Q->cnum ; j++ )
{
if( ( M.pdata[countm].row == i ) && ( M.pdata[countm].col == j ) && ( N.pdata[countn].row == i ) &&( N.pdata[countn].col == j ) )
{
temp = M.pdata[countm].elem - N.pdata[countn].elem ;
countm++ ;
countn++ ;
}
else if( ( M.pdata[countm].row == i ) && ( M.pdata[countm].col == j ) )
{
temp = M.pdata[countm].elem ;
countm++ ;
}
else if( ( N.pdata[countn].row == i ) &&( N.pdata[countn].col == j ) )
{
temp = -1 * N.pdata[countn].elem ;
countn++ ;
}
if( temp )
{
if( count > memsize )
{
Q->pdata = ( Triple* )realloc( Q->pdata , ( memsize + 1) * sizeof( Triple ) ) ;
memsize += 1 ;
}
Q->pdata[count].row = i ;
Q->pdata[count].col = j ;
Q->pdata[count].elem = temp ;
count++ ;
temp = 0 ;
}
}
}
Q->tnum = count - 1 ;
return 0 ;
}
int MultMatrix( TSMatrix* Q , TSMatrix M , TSMatrix N )
{
if( M.cnum != N.rnum )
{
printf( "can't mult!\n" ) ;
exit( 1 ) ;
}
Q->rnum = M.rnum ;
Q->cnum = N.cnum ;
int memsize = M.tnum + N.tnum + 1 ;
Q->pdata = ( Triple* )malloc( memsize * sizeof( Triple ) ) ;
if( !Q->pdata )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
int i ;
int j ;
int k ;
int count = 1 ;
int countm = 1 ;
int countn = 1 ;
int temp = 0 ;
TSMatrix TN ;
TransposeMatrix( &TN , N ) ;
for( i = 1 ; i <= M.rnum ; i++ )
{
for( j = 1 ; j <= TN.rnum ; j++ )
{
while( M.pdata[countm].row < i )
{
countm++ ;
}
while( TN.pdata[countn].row < j )
{
countn++ ;
}
for( k = 1 ; k <= M.cnum ; k++ )
{
if( M.pdata[countm].col < k && countm < M.tnum )
{
countm++ ;
}
if( TN.pdata[countn].col < k && countn < N.tnum )
{
countn++ ;
}
if( M.pdata[countm].row == i && TN.pdata[countn].row == j &&
M.pdata[countm].col == k && TN.pdata[countn].col == k )
{
temp = temp + M.pdata[countm].elem * TN.pdata[countn].elem ;
countm++ ;
countn++ ;
}
}
if( temp != 0 )
{
if( count > memsize )
{
Q->pdata = ( Triple* )realloc( Q->pdata , ( memsize + 1) * sizeof( Triple ) ) ;
memsize += 1 ;
}
Q->pdata[count].row = i ;
Q->pdata[count].col = j ;
Q->pdata[count].elem = temp ;
temp = 0 ;
count++ ;
}
countm = 1 ;
}
countn = 1 ;
}
Q->tnum = count - 1 ;
return 0 ;
}
主函数测试
#include "syzhead.h"
int main()
{
/*TSMatrix M ;
CreateMatrix( &M ) ;
PrintTriple( &M ) ;
PrintMatrix( &M ) ;
printf( "\n\n" ) ;
TSMatrix T ;
CopyMatrix( &T , M ) ;
PrintTriple( &T ) ;
PrintMatrix( &T ) ;
printf( "\n\n" ) ;
printf( "ADD\n" ) ;
TSMatrix Q ;
AddMatrix( &Q , M , T ) ;
PrintTriple( &Q ) ;
PrintMatrix( &Q ) ;
printf( "SUB\n" ) ;
SubMatrix( &Q , M , T ) ;
PrintTriple( &Q ) ;
PrintMatrix( &Q ) ;
TransposeMatrix( &T , M ) ;
PrintTriple( &T ) ;
PrintMatrix( &T ) ;*/
TSMatrix M ;
TSMatrix N ;
TSMatrix Res ;
CreateMatrix( &M ) ;
CreateMatrix( &N ) ;
printf( "ADD\n" ) ;
AddMatrix( &Res , M , N ) ;
PrintMatrix( &Res ) ;
printf( "SUB\n" ) ;
SubMatrix( &Res , M , N ) ;
PrintMatrix( &Res ) ;
/*TSMatrix M ;//chengfu
TSMatrix N ;
TSMatrix Res ;
CreateMatrix( &M ) ;
CreateMatrix( &N ) ;
printf( "matrix M is as follow:\n" ) ;
PrintMatrix( &M ) ;
printf( "matrix N is as follow:\n" ) ;
PrintMatrix( &N ) ;
MultMatrix( &Res , M , N ) ;
printf( "Triple Res is as follow:\n" ) ;
PrintTriple( &Res ) ;
printf( "matrix RES is as follow:\n" ) ;
PrintMatrix( &Res ) ;*/
return 0;
}