用C试一下稀疏矩阵的快速转置

struct val3{
   int x, y, e; }; 
struct mat3{
    int row, col, count;
    val3 tab[MAXCOUNT]; };
/*x是列，y是行，从零开始计数，row是矩阵有几行，col是有几列，count是矩阵中非零元的个数*/

void init_mat31(mat3 *a){
    srand(time(NULL));
    a->row = rand() % (MAXROW - MINROW + 1) + MINROW;
    a->col = rand() % (MAXCOL - MINCOL + 1) + MINCOL;
    a->count = a->row * a->col * FACTOR; //FACTOR暂取0.05
    if(a->count < MINCOUNT) a->count = MINCOUNT;
    else if(a->count > MAXCOUNT) a->count = MAXCOUNT;
    for(int saved[MAXCOUNT+1],i,x,y, nsave=0,k=0; /*为矩阵生成数据*/
        k < a->count; nsave++, k++) {
again:  x = rand() % a->col, y = rand() % a->row; //生成行列位置
        saved[nsave] = (x << 16) | y; //行列不超过2^16
        for(i = 0; i < nsave; i++)
            if(saved[i] == saved[nsave])
                goto again; //如果位置重复那么重新生成
        a->tab[k].x = x, a->tab[k].y = y;
        a->tab[k].e = rand() % (a->row * a->col);
    }
}

int sort_mat3(mat3 *a){
    val3 *tab;
    int k, i, key, minpos, min;

    if(!(tab = (val3*)malloc(a->count*sizeof(val3))) return -1;
    memcpy(tab, a->tab, a->count * sizeof(val3));//一个副本
    k = 0;
    //使用选择排序，每次从tab选Key最小的三元组放入a->tab
again:
    // 找第一个没被选择过(*.x<0)的三元组
    for(minpos = 0;
minpos < a->count && tab[minpos].x < 0; minpos++);
    if(minpos == a->count) goto done;//找不到，结束排序
    min = (tab[minpos].y << 16) | tab[minpos].x;
    for(i = minpos + 1; i < a->count; i++) {
        if(tab[i].x == -1) // skip invalid items
            continue;
        key = (tab[i].y << 16) | tab[i].x; //使用(y<<16)|x做Key
        if(key < min) { min = key, minpos = i; }
    }
    a->tab[k++] = tab[minpos];
    tab[minpos].x = -1; // 标记使其不再被选择
    goto again;
done:
    free(tab); return 0;
}

int transpose(mat3 *a){
    val3* tab;
    int i, w[MAXCOL], pos;

    tab = (val3*) malloc(a->count * sizeof(val3));
    if(!tab) return -1;/*转置后的三元组先放在tab再复制到a->tab*/
    memset(w, 0, sizeof(int) * a->col);
    for(i = 0; i < a->count; i++)
        w[a->tab[i].x]++; //先统计各列非零元的个数存到 w
    for(pos=0, i=0; i < a->col; i++) {
        int nextpos = pos + w[i];
        w[i] = pos; //再计算转置后各列第一个非零元在a->tab的位置
        pos = nextpos;
    }
    for(i = 0; i < a->count; i++) { /*根据w表执行转置*/
        int icol = a->tab[i].x;
        pos = w[icol];
        tab[pos].x = a->tab[i].y; tab[pos].y = a->tab[i].x;
        tab[pos].e = a->tab[i].e;
        w[icol]++;
    }
    memcpy(a->tab, tab, a->count * sizeof(val3));
    i = a->row, a->row = a->col, a->col = i;
    free(tab); return 0;
}