sparsematrix.c

这是我的一些数据结构(C语言)源代码 比如LinkList

#include <stdio.h>
#include <stdlib.h>

#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;
}