稀疏矩阵的两种转置算法

其中fasttranspos是优化的算法（详细说明见程序中说明），该算法描述如下：
1） 先确定原矩阵a中每列元素的个数，也就确定了转置矩阵b每行的个数；
2） 确定转置矩阵b每行元素的起始位置；
3） 确定a中元素在b中的正确位置。
程序执行结果：
before tranpose
0       3       22
0       5       -1
1       1       71
2       3       88
3       2       -9
5       5       7

after transpos
1       1       71
2       3       -9
3       0       22
3       2       88
5       0       -1
5       5       7
其中本例中：row_num[1-5]:1 1 2 0 2
          start_pos[1-5]:1 2 3 5 5(读者可以根据fasttranspose中给定的算法计算）

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

typedef struct{
        int row;
        int col;
        int data;
}xishu;//存储稀疏矩阵的结构(行， 列，值)


#define MAX_COL 10
//static void transpose(xishu a[], xishu b[]);//普通算法

static void fasttranspose(xishu a[], xishu b[]);//改进的算法

static void create(int a[][6], int m, int n, xishu b[], int* count);
static void print(int* count, xishu a[]);

int main(int argc, char** argv)
{
        int a[6][6] = { {0, 0, 0, 22, 0, -1}, {0, 71, 0, 0, 0, 0}, {0, 0, 0, 88, 0, 0},
                                                {0, 0, -9, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 7} };
        xishu b[10], c[10];
        int count = 0, i, k;

        for(i = 0; i < 10; i++){
                b[i].row = c[i].row = 0;
                b[i].col = c[i].col = 0;
                b[i].data = c[i].data = 0;
        }//初始化


        create(a, 6, 6, b, &count);//建立一个以xishu为元素的数组来表示一个稀疏矩阵

        printf("\nbefore tranpose\n");
        print(&count, b);//打印建立好的稀疏矩阵


        //transpose(b, c);

        fasttranspose(b, c);//建立转置矩阵

        printf("\nafter transpos\n");
        print(&count, c);//打印转置矩阵

        exit(0);
}

static void print(int* count, xishu a[])
{
        int k;

        for(k = 1; k <= *count; k++){
               printf("%d\t%d\t%d\n", a[k].row, a[k].col, a[k].data);
        }
}

static void create(int a[][6], int m, int n, xishu b[], int* count)
{
        int i, j;

        *count = 0;
        b[0].row = m;
        b[0].col = n;

        for(i = 0; i < m; i++){
                for(j = 0; j < n; j++){
                        if(a[i][j] != 0){
                                (*count)++;
                                b[*count].row = i;
                                b[*count].col = j;
                                b[*count].data = a[i][j];
                        }
                }
        }
        b[0].data = *count;
}

/***
static void transpose(xishu a[], xishu b[])
{
//该算法的时间代价为O(a[0].data*a[0].data)

        int count = 0;
        int i, col;

        b[0].row = a[0].col;
        b[0].col = a[0].row;
        b[0].data = a[0].data;
        printf("%d, %d, %d\n", b[0].row, b[0].col, b[0].data);
        printf("%d, %d, %d\n", a[0].row, a[0].col, a[0].data);

        for(col = 0; col < a[0].col; col++){
                for(i = 1; i <= a[0].data; i++){
                        if(a[i].col == col){
                                count++;
                                b[count].row = a[i].col;
                                b[count].col = a[i].row;
                                b[count].data = a[i].data;
                        }
                }
        }
}
***/
static void fasttranspose(xishu a[], xishu b[])
{
//改进的算法，该算法的时间代价为O(a[0].col+a[0].data)

        int i, pos;
        int row_num[MAX_COL];
        int start_pos[MAX_COL];

        b[0].row = a[0].col;
        b[0].col = a[0].row;
        b[0].data = a[0].data;

        for(i = 0; i < a[0].col; i++){
                row_num[i] = 0;
        }
        for(i = 1; i <= a[0].data; i++){
                row_num[a[i].col]++;
        }

        start_pos[0] = 1;
        for(i = 1; i < a[0].col; i++){
                start_pos[i] = start_pos[i-1] + row_num[i-1];
        }

        for(i = 1; i <= a[0].data; i++){
                pos = start_pos[a[i].col];
                while(b[pos].data != 0){
                        pos++;
                }
                b[pos].row = a[i].col;
                b[pos].col = a[i].row;
                b[pos].data = a[i].data;
        }
}