博客文章

Sparse Matrix Fast Transpose

作者: andy.      时间: 2016-03-08 09:41:53

        今天大清早起来继续看数据结构。稀疏矩阵的转置,蛮有意思的。用C实现一下~~~

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

typedef struct {
    int col;
    int row;
    int value;
} term;

void fastTranspose(term *a, term *b) {
    int i, j, numCols = (*a).col, numTerms = (*a).value;
    (*b).col = (*a).row;
    (*b).row = (*a).col;
    (*b).value = numTerms;
    //转置过去的行数
    int *rowTerms = (int *)malloc(numCols*sizeof(int));
    int *startPos = (int *)malloc((numCols + 1)*sizeof(int));

    if (numTerms == 0)
        return;
    //初始化每行的元素个数为0个
    for (i = 0; i < numCols; i++)
        *(rowTerms + i) = 0;

    //统计转置过后每行的元素个数
    for (i = 1; i <= numTerms; i++)
        (*(rowTerms + (*(a + i)).col))++;

    //转置后 每行元素在 一维数组 中初始的位置
    *startPos = 1;
    for (i = 1; i <= numCols; i++)
        *(startPos + i) = *(startPos + i - 1) + *(rowTerms + i - 1);


    for (i = 1; i <= numTerms; i++) {
        //通过col确定转置后的列找到其在新数组中的存储位置
        //因为row是有顺序的 转置过后的列也就有顺序
        j = (*(startPos + (*(a + i)).col))++;

        (*(b + j)).col = (*(a + i)).row;
        (*(b + j)).row = (*(a + i)).col;
        (*(b + j)).value = (*(a + i)).value;
    }

    free(rowTerms);
    free(startPos);
}

void printfMatrix(term *terms) {
    int i = 0;
    printf("Row Col Value\n");
    for (i = 0; i <= (*terms).value; i++)
        printf("%2d  %2d  %d\n", (*(terms + i)).row, (*(terms + i)).col, (*(terms + i)).value);
}

int main(void) {
    term a[] = { { 10,10,6 },{4,5,1},{ 1,4,1 },{ 7,4,1 },{ 2,9,1 },{ 3,5,1 },{ 2,5,1 } };
    term b[7];
    printfMatrix(a);
    fastTranspose(a, b);
    printf("-----------------------------------------------------------------\n");
    printfMatrix(b);
    getchar();
}

        运行结果如下:

PS D:\Visual Studio\Projects\C__> gcc .\fastTranspose.c
PS D:\Visual Studio\Projects\C__> .\a.exe
Row Col Value
10  10  6
 5   4  1
 4   1  1
 4   7  1
 9   2  1
 5   3  1
 5   2  1
-----------------------------------------------------------------
Row Col Value
10  10  6
 1   4  1
 2   9  1
 2   5  1
 3   5  1
 4   5  1
 7   4  1