数据结构第四章数组和字符串--课本代码

1.稀疏矩阵的快速转置法
我们知道简单的稀疏矩阵的转置，可以直接交换矩阵的行和列就可以。这样需要遍历每一个元素，时间复杂度是o(m*n)。
我们通过快速转置法，可以将时间复杂度降到o(n+t).其中m,n,t分别是矩阵的行数，列数，和非零元素的个数。
快速转置法的核心在于利用两个数组num和k，num用来记录原三元组表中a.table[i].col中不同的列的号码j1,j2,j3,j4的数目。数组k遍历num数组，累计相加，于是index=k[a.table[i].col],index可以准确的表示出当前从原三元表读到的数据应该放在新三元表的哪一个位置。

#include<stdio.h>
#define maxn 100
typedef int ElemType;

typedef struct term{
int row,col;    //存储行和列
    ElemType value; //存储元素的值
}Term;

typedef struct sparsematrix{ //稀疏矩阵
int m,n,t; //m矩阵行数，n矩阵列数，t非零元素的个数
    Term table[maxn];  //存储非零元素的三元组表
}SparseMatrix;
SparseMatrix sp,sq;

void init(){
for(int i=0;i<sp.t;i++){
scanf("%d%d%d",&sp.table[i].row,&sp.table[i].col,&sp.table[i].value);
    }
}
void print(){
printf("\n");
for(int i=0;i<sp.t;i++){
printf("%d %d %d\n",sq.table[i].row,sq.table[i].col,sq.table[i].value);
    }
}

int main(){
scanf("%d%d%d",&sp.m,&sp.n,&sp.t);
int num[maxn];      //num存储列下标j的非零元素个数
int k[maxn];  //k存储下一个的开始位置
    init();
for(int j=0;j<sp.n;j++){
        num[j]=0;
    }
for(int i=0;i<sp.t;i++){
        num[sp.table[i].col]++;
    }

for(int j=0;j<sp.n;j++){
        k[j]=0;
    }
for(int j=1;j<sp.t;j++){
        k[j]=k[j-1]+num[j-1];
    }

for(int i=0;i<sp.t;i++){
int index=k[sp.table[i].col]++;
        sq.table[index].col=sp.table[i].row;
        sq.table[index].row=sp.table[i].col;
        sq.table[index].value=sp.table[i].value;
    }
    print();
return 0;
}