• 数据结构的一道上机题
• 主要实现快速转置算法
• 参考博客: 稀疏矩阵的压缩存储及其转置算法
• 参考博客把思路讲的很清晰了，但代码仍有错误，下面结合我的理解给出代码(难以理解的地方有注释)

代码

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

typedef struct {
    int row,col;
    int e;
}Triple;
typedef struct {
    Triple data[MAX+1];
    int m,n,len;        //len表示非零元素的个数
}TSMatrix;

void fastTransposeTSMatrix(TSMatrix *M,TSMatrix *T);

int main(int argc, const char * argv[]) {
    TSMatrix *ob = (TSMatrix *)malloc(sizeof(TSMatrix));
    printf("输入矩阵行数和列数：");
    scanf("%d%d",&ob->m,&ob->n);
    int i,j,k=0,e,index=1;
    printf("输入三元组:\n");
    while (scanf("%d%d%d",&i,&j,&e) != EOF) {
        ob->data[index].row = i;
        ob->data[index].col = j;
        ob->data[index].e = e;
        ob->len = ++k;
        index ++;
    }
    printf("\n打印原始三元组:\n");
    for (i=1; i<=ob->len; ++i) {
        printf("%d %d %d\n",ob->data[i].row,ob->data[i].col,ob->data[i].e);
    }
    printf("转置后的三元组:\n");
    TSMatrix *ob_T = (TSMatrix *)malloc(sizeof(TSMatrix));
    fastTransposeTSMatrix(ob, ob_T);
    for (i=1; i<=ob_T->len; ++i) {
        printf("%d %d %d\n",ob_T->data[i].row,ob_T->data[i].col,ob_T->data[i].e);
    }
    return 0;
}

void fastTransposeTSMatrix(TSMatrix *M,TSMatrix *T){
    T->m = M->n;
    T->n = M->m;
    T->len = M->len;
    /*num[]记录每一列有多少非0元素，cops[]记录求M中各列第一个非零元在T.data中的下标*/
    int num[MAX],cops[MAX],col,i;
    cops[1] = 1;
    for (col=1; col<=M->n; col++) {
        num[col] = 0;
    }
    for (i=1; i<=M->len; ++i) {
        num[M->data[i].col]++;
    }
    for (i=2; i<=M->n; ++i) {
        cops[i] = cops[i-1] + num[i-1];
    }
    for (i=1; i<=M->len; ++i) {
        int p;
        p = cops[M->data[i].col];
        T->data[p].col = M->data[i].row;
        T->data[p].row = M->data[i].col;
        T->data[p].e = M->data[i].e;
        /*cops[]只记载了M中各列第一个非零元在T.data中的下标，若该列有其他元素，则需要下标表示的位置需要+1*/
        ++cops[M->data[i].col];
    }
}