【数据结构之旅】稀疏矩阵的快速转置-白红宇

说明：

稀疏矩阵的快速转置算法的核心在于，用一个数组num记录原来矩阵中的每列非零元个数，用另一个数组cpos来记录原矩阵每列第一个非零元在新矩阵中的位置，以此来达到快速转置的目的。

用这样的方法，主要是希望，矩阵转置后，存储顺序依然是按照行来存储的。

1.实现及代码注释

根据上面的核心提示，可以有如下的代码，下面的代码中的注释已经非常详细，因此这里就不把每一部分实现的功能独立开来了：

                         
#
include
<stdio.h>
#
include
<stdlib.h>
#define OVERFLOW -
1
#define OK 
1
#define ERROR 
0
#define TRUE 
2
#define FALSE -
2
typedef 
int
ElemType;
typedef 
int
Status;
typedef struct{ 
//非零元三元组类型结构体 
    
int
i, j; 
//非零元的行和列 
    
ElemType e;    
//非零元的值 
} Triple;      
//非零元三元组类型结构体定义关键字
typedef struct{        
//矩阵类型结构体 
    
Triple *data;  
//data域，指向非零元三元组的结构体指针 
    
int
mu, nu, tu;  
//矩阵的行数、列数和非零元个数 
} TSMatrix;            
//矩阵类型结构体定义关键字
 
/*
   
0   14  0   0   -5
   
0   -7  0   0   0
   
36  0   0   28  0
   
   
mu = 3; nu = 5; tu = 5
*/
Status CreateSMatrix(TSMatrix &M){    
//创建一个稀疏矩阵 
    
M.tu = 
5
;
    
    
M.data = (Triple*)malloc(sizeof(Triple) * (M.tu + 
1
)); 
//data域存储元素的大小比稀疏矩阵的非零元个数大1，是因为data[0]不使用 
    
if
(NULL == M.data)
        
return
OVERFLOW;
    
M.data[
1
].i = 
1
;
    
M.data[
1
].j = 
2
;
    
M.data[
1
].e = 
14
;
    
    
M.data[
2
].i = 
1
;
    
M.data[
2
].j = 
5
;
    
M.data[
2
].e = -
5
;
    
    
M.data[
3
].i = 
2
;
    
M.data[
3
].j = 
2
;
    
M.data[
3
].e = -
7
;
    
    
M.data[
4
].i = 
3
;
    
M.data[
4
].j = 
1
;
    
M.data[
4
].e = 
36
;
    
    
M.data[
5
].i = 
3
;
    
M.data[
5
].j = 
4
;
    
M.data[
5
].e = 
28
;
    
    
M.mu = 
3
;
    
M.nu = 
5
;
    
    
return
OK;
}
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){ 
//采用顺序表存储表示，求稀疏矩阵M的转置矩阵T 
    
int
j, p, q, t;
    
/*j记录遍历时的当前列，cops[j]，则表示当前列第一个非零元的位置或者该列非零元位置的其它位置（cops[j]++），正式转置时用； 
    
p记录遍历时的非零元个数，正式转置时用； 
    
q记录cops[j]，简化代码的表示，正式转置时用 ；
    
t用在转置准备时。 
    
*/
    
int
*num;  
//保存每一列的非零元个数 
    
int
*cpos; 
//保存转置后每列第一个非零元在T中所处的序号
                
//cops[j]++则是该列的下一个非零元，如果存在的话 
    
    
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;  
//初始化矩阵T 
    
    
T.data = (Triple*)malloc(sizeof(Triple)*(T.nu + 
1
));
    
    
num = (
int
*)malloc((M.nu + 
1
)*sizeof(
int
)); 
//num和cpos开辟空间比非零元个数大1，是因为不使用0号位置 
    
cpos = (
int
*)malloc((M.nu + 
1
)*sizeof(
int
));
    
    
if
(num == NULL || cpos == NULL)
        
return
OVERFLOW;
    
    
if
(T.tu != 
0
){ 
        
for
(j = 
1
; j <= M.nu; j++) 
//初始化num向量 
            
num[j] = 
0
;
        
for
(t = 
1
;t <= M.tu; t++)   
//求M中每一列所含非零元的个数 
            
num[M.data[t].j]++;     
//这里要用到num[1]~num[5]，所以上面num要全部初始化为0 
        
        
cpos[
1
] = 
1
;  
//这里是一定的 
        
for
(j = 
2
;j <= M.nu; j++)   
//求每列的第一个非零元在T.data中的序号  
            
cpos[j] = cpos[j-
1
] + num[j-
1
]; 
//画表分析得出该公式并不难 
        
        
for
(p = 
1
; p <= M.tu; p++){        
//上面是准备工作，下面开始正式转置 
            
j = M.data[p].j;  
//j的作用是记录当前遍历的列，以让cops使用 
            
q = cpos[j];      
//是为了简化代码，因为下面都要用到cpos[j] 
            
T.data[q].i = M.data[p].j;    
//交换行 
            
T.data[q].j = M.data[p].i;    
//交换列 
            
T.data[q].e = M.data[p].e;    
//赋值 ，无论如何交换，储存顺序是已经定下来的了 
                                        
            
cpos[j]++;  
//cops[j]++则是该列的下一个非零元，如果存在的话，不存在的话也没有影响 
        
}               
//因为在这个for循环中，如果列变了，即j变化了，cpos[j]也不是原来的值了 
    
} 
    
free(num);
    
free(cpos);
    
return
OK;
}
int
main(
void
){ 
    
int
i,j;
    
    
TSMatrix M;
    
TSMatrix T;
    
CreateSMatrix(M);  
    
FastTransposeSMatrix(M, T);
    
    
printf(
"\n"
);
    
return
0
;
}
        
      

可以用C free等编译器进行编译运行，但由于时间关系，上面的代码中并没有给出转置后的矩阵打印的代码，可以自己加上去，当然也可以通过调试的方法监视新矩阵T中的data域的数值变化。

2.测试

测试就是按照上面的提示去做就可以了，时间关系，这里就先不做测试，改天有时间再补上吧。