www.pudn.com > datastructor.rar > SparseMatrix.c

#include  
#include  
 
#define MAXSIZE     125 
typedef enum {ERROR = -2,OVERLOW,FALSE, TRUE, OK} Status; 
typedef int ElemType; 
typedef struct{ 
    int     i, j; //该非零元的行下标和列下标  
    ElemType   e; 
}Triple; 
 
typedef struct{ 
    Triple data[MAXSIZE+1];//非零元三元组表,data[0]未用  
    int    mu, nu, tu;     //矩阵的行数、列数和非零个数  
}TSMatrix; 
 
/****************Member function*****************/ 
Status CreateSMatrix(TSMatrix* M, int (*arr)[], int row, int col){ 
    //postcondition: 创建稀疏矩阵M  
    int m, n, k = 1;  
    M->mu = row; M->nu = col; 
    for(m = 0; m < row; ++m){ 
        for(n = 0; n < col; ++n){ 
            if((*arr)[m*col+n] != 0){ 
                M->data[k].i = m; 
                M->data[k].j = n; 
                M->data[k].e = (*arr)[m*col+n]; 
                ++M->tu; 
                ++k; 
            } 
        } 
    } 
    return OK;            
} 
 
Status DestroySMatrix(TSMatrix* M){ 
    //precondition: 稀疏矩阵M存在 
    //postcondition: 销毁稀疏矩阵M   
} 
 
Status PrintSMatrix(const TSMatrix* M){ 
    //precondition: 稀疏矩阵M存在 
    //postcondition: 输出稀疏矩阵M 
    int m, n, k = 1; 
    for(m = 0; m < M->mu; ++m){ 
        for(n = 0; n < M->nu; ++n){ 
            if(M->data[k].i == m && M->data[k].j == n){ 
                printf("%3d", M->data[k].e); 
                ++k; 
            } 
            else printf("%3d", 0); 
        } 
        printf("\n");     
    } 
    return OK;             
} 
 
Status CopySMatrix(const TSMatrix* M, TSMatrix* T){ 
    //precondition: 稀疏矩阵M存在 
    //postcondition: 由稀疏矩阵M复制得到T 
    T->mu = M->mu; T->nu = M->nu; T->tu = M->tu; 
    int n; 
    for(n = 0; n <= MAXSIZE; ++n) 
        T->data[n] = M->data[n]; 
    return OK;     
} 
 
Status AddSMatrix(const TSMatrix* M, const TSMatrix* N, TSMatrix* Q){ 
    //precondition: 稀疏矩阵M与N的行数和列数对应相等 
    //postcondition: 求稀疏矩阵的和Q=M+N 
} 
     
Status SubtMatrix(const TSMatrix* M, const TSMatrix* N, TSMatrix* Q){ 
    //precondition: 稀疏矩阵M与N的行数和列数对应相等 
    //postcondition: 求稀疏矩阵的差Q=M-N  
} 
 
Status MultSMatrix(const TSMatrix* M, const TSMatrix* N, TSMatrix* Q){ 
    //precondition: 稀疏矩阵M的列数等于N的行数 
    //postcondition: 求稀疏矩阵乘积Q=M*N 
} 
 
Status TransposeSMatrix(const TSMatrix* M, TSMatrix* T){ 
    //precondition: 稀疏矩阵M存在 
    //postcondition: 求稀疏矩阵M的转置矩阵T 
    T->mu = M->nu; T->nu = M->mu; T->tu = M->tu; 
    if(T->tu){ 
        int col, p, q = 1; 
        for(col = 0; col <= M->nu; ++col) 
            for(p = 0; p <= M->tu; ++p) 
                if(M->data[p].j == col) { 
                    T->data[q].i = M->data[p].j; 
                    T->data[q].j = M->data[p].i; 
                    T->data[q].e = M->data[p].e; 
                    ++q; 
                } 
            } 
    return OK;          
}  
 
Status FastTransposeSMatrix(const TSMatrix* M, TSMatrix* T){ 
    T->mu = M->nu; T->nu = M->mu; T->tu = M->tu; 
    if(T->tu){ 
        int col, num[20] = {0}, cpot[20] = {0}; 
        //for(col = 1; col <= M->tu; ++col) num[col] = 0; 
         
        int t; 
        for(t = 1; t <= M->tu; ++t) ++num[M->data[t].j];num[t+1] = 1; 
        for(t =0; t<7; ++t)  printf("%3d",num[t]);printf("%3d",num[t]); 
        cpot[1] = 1; 
        for(col = 2; col <= M->nu; ++col){  
            cpot[col] = cpot[col-1] + num[col-1]; 
            //printf("%3d", cpot[col]); 
        } 
             
        int p, q;   printf("Here is OK!\n");  
        for(p = 1; p <= M->tu; ++p){ 
            col = M->data[p].j; q = cpot[col]; 
            T->data[q].i = M->data[p].j; 
            T->data[q].j = M->data[p].i; 
            T->data[q].e = M->data[p].e; 
            ++cpot[col]; 
        } 
    } 
    return OK; 
} 
    
/****************************main()**************************/ 
int main() 
{ 
    int array[6][7] = {  
                        {0, 12,9, 0, 0, 0, 0}, 
                        {0, 0, 0, 0, 0, 0, 0}, 
                        {-3,0, 0, 0, 0, 14,0}, 
                        {0, 0, 24,0, 0, 0, 0}, 
                        {0, 18,0, 0, 0, 0, 0}, 
                        {15,0, 0,-7, 0, 0, 0} 
                      }; 
    TSMatrix array1, array2; 
     
    CreateSMatrix(&array1, array, 6, 7); 
    printf("The matrix:\n"); 
    PrintSMatrix(&array1);     
    /* 
    int ss; 
    for(ss = 1; ss <= array1.tu; ++ss) 
        printf("(%d, %d, %d)\n", array1.data[ss].i, 
                 array1.data[ss].j, array1.data[ss].e); 
    */ 
 
    TransposeSMatrix(&array1, &array2); 
    printf("\nTranspose matrix:\n"); 
    PrintSMatrix(&array2); 
    /*     
    for(ss = 1; ss <= array2.tu; ++ss) 
        printf("(%d, %d, %d)\n", array2.data[ss].i, 
                 array2.data[ss].j, array2.data[ss].e); 
    */ 
    printf("Copy matrix:\n"); 
    CopySMatrix(&array1, &array2); 
    PrintSMatrix(&array2); 
   
    TSMatrix array3; 
    printf("Fast Transpose matrix:\n"); 
    FastTransposeSMatrix(&array1, &array3); 
    PrintSMatrix(&array3);     
    //printf("%d  %d  %d\n", array1.mu, array1.nu, array1.tu); 
    //printf("%d  %d  %d\n", array2.mu, array2.nu, array2.tu); 
  
int nm; 
for(nm = 1; nm <= array1.tu; ++nm) 
printf("(%d, %2d, %2d)\n", array1.data[nm].i, array1.data[nm].j, array1.data[nm].e);   
    system("pause"); 
    return 0; 
}