1 #include<stdio.h>
 2 #define MAX_TERMS 101 //最大元素个数加1第一个用于存储数组 行数列数元素数 
 3 #define MAX_COL   50  //最大列加1 
 4 typedef struct  {
 5     int col;
 6     int row;
 7     int value; 
 8 } term;
 9 term   a[MAX_TERMS];
10 void transpose(term a[],term b[]);
11 void fast_transpose(term a[],term b[]);
12 
13 
14 void transpose(term a[],term b[])//时间是col*elements 
15 {
16     /*
17     思路:当矩阵不是非0矩阵时，求a矩阵的每一列的元素，转置为b的每一行的元素 
18     具体就是扫描a表max_col次，每次找出相同的列转置为行 
19     不按行转置是因为会打乱顺序，而按照列转置是有序的 
20     */ 
21     int n,i,j,bcurrent;
22     n=a[0].value;
23     b[0].row=a[0].col;
24     b[0].col=a[0].row;
25     b[0].value=http://www.mamicode.com/n;
26     if( n > 0 ){ 
27         //非0矩阵        
28         bcurrent=1;
29         for(i=0;i<a[0].col;i++){
30             //按a的列转置 
31             for(j = 1;j <n; j++){
32                 //找出当前列所有元素 
33                  if(a[j].col==i){
34                      //是当前列加入b 
35                      b[bcurrent].row=a[j].col;
36                      b[bcurrent].col=a[j].row;
37                      b[bcurrent].value=http://www.mamicode.com/a[j].value;
38                      bcurrent++;
39                  } 
40             }    
41         }
42     } 
43 } 
44 void fast_transpose(term a[],term b[])//时间复杂度:col+elements 
45 { 
46     /*
47     思路:   先确定a矩阵中每一列的元素个数
48             然后确定a矩阵转置为b矩阵之后的元素位置 
49             下一行元素位置=上一行元素位置+元素个数 
50             相当于先确定好每一个元素的位置后进行填充
51     */ 
52     int row_terms[MAX_COL],starting_pos[MAX_COL] 
53     //转置后矩阵的行数，矩阵转置后的每一行的开始位置
54     int i,j,num_cols=a[0].col,num_terms =a[0].values;//, , a阵的列数，a阵的最大元素数 
55     b[0].row=a[0].col;
56     b[0].col=a[0].row;
57     b[0].value=http://www.mamicode.com/num_terms;
58     if(num_terms > 0){
59         for(i=1;i<num_col;i++){
60             //初始a阵的每一列元素个数为0 
61             row_terms[i]=0;
62         }
63         for(i=1;i<num_terms;i++){
64             //a阵求每一列元素个数 
65             row_terms[a[i].col]++;
66         } 
67         starting_pos[0]=1;
68         //开始位置为1--去除第一行记录矩阵总信息的行 
69         for(i=1;i<num_col;i++){
70             //每一行的开始位置=上一行的位置+上一行的元素数目 
71             startint_pos[i]= startint_pos[i-1]+row_terms[i-1];
72         } 
73         for(i=1;i<num_terms;i++){
74             //每次用完开始位置后要加1--因为有一个元素已经占有了那个开始位置 
75             j=starting_pos[a[i].col]++; 
76             b[j].row=a[i].col;
77             b[j].col=a[i].row;
78             b[j].value=http://www.mamicode.com/a[i].value;    
79         }
80     } 
81      
82 }