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

说明：

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

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

1.实现及代码注释

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

<code>#</code><code>include</code><code>&lt;stdio.h&gt;</code>

<code>#</code><code>include</code><code>&lt;stdlib.h&gt;</code>

<code>#define OVERFLOW -</code><code>1</code>

<code>#define OK </code><code>1</code>

<code>#define ERROR </code><code>0</code>

<code>#define TRUE </code><code>2</code>

<code>#define FALSE -</code><code>2</code>

<code>typedef </code><code>int</code> <code>ElemType;</code>

<code>typedef </code><code>int</code> <code>Status;</code>

<code>typedef struct{ </code><code>//非零元三元组类型结构体 </code>

<code>    </code><code>int</code> <code>i, j; </code><code>//非零元的行和列 </code>

<code>    </code><code>ElemType e;    </code><code>//非零元的值 </code>

<code>} Triple;      </code><code>//非零元三元组类型结构体定义关键字</code>

<code>typedef struct{        </code><code>//矩阵类型结构体 </code>

<code>    </code><code>Triple *data;  </code><code>//data域，指向非零元三元组的结构体指针 </code>

<code>    </code><code>int</code> <code>mu, nu, tu;  </code><code>//矩阵的行数、列数和非零元个数 </code>

<code>} TSMatrix;            </code><code>//矩阵类型结构体定义关键字</code>

<code> </code><code>/*</code>

<code>   </code><code>0   14  0   0   -5</code>

<code>   </code><code>0   -7  0   0   0</code>

<code>   </code><code>36  0   0   28  0</code>

<code>   </code> 

<code>   </code><code>mu = 3; nu = 5; tu = 5</code>

<code>*/</code>

<code>Status CreateSMatrix(TSMatrix &amp;M){    </code><code>//创建一个稀疏矩阵 </code>

<code>    </code><code>M.tu = </code><code>5</code><code>;</code>

<code>    </code> 

<code>    </code><code>M.data = (Triple*)malloc(sizeof(Triple) * (M.tu + </code><code>1</code><code>)); </code><code>//data域存储元素的大小比稀疏矩阵的非零元个数大1，是因为data[0]不使用 </code>

<code>    </code><code>if</code><code>(NULL == M.data)</code>

<code>        </code><code>return</code> <code>OVERFLOW;</code>

<code>    </code><code>M.data[</code><code>1</code><code>].i = </code><code>1</code><code>;</code>

<code>    </code><code>M.data[</code><code>1</code><code>].j = </code><code>2</code><code>;</code>

<code>    </code><code>M.data[</code><code>1</code><code>].e = </code><code>14</code><code>;</code>

<code>    </code><code>M.data[</code><code>2</code><code>].i = </code><code>1</code><code>;</code>

<code>    </code><code>M.data[</code><code>2</code><code>].j = </code><code>5</code><code>;</code>

<code>    </code><code>M.data[</code><code>2</code><code>].e = -</code><code>5</code><code>;</code>

<code>    </code><code>M.data[</code><code>3</code><code>].i = </code><code>2</code><code>;</code>

<code>    </code><code>M.data[</code><code>3</code><code>].j = </code><code>2</code><code>;</code>

<code>    </code><code>M.data[</code><code>3</code><code>].e = -</code><code>7</code><code>;</code>

<code>    </code><code>M.data[</code><code>4</code><code>].i = </code><code>3</code><code>;</code>

<code>    </code><code>M.data[</code><code>4</code><code>].j = </code><code>1</code><code>;</code>

<code>    </code><code>M.data[</code><code>4</code><code>].e = </code><code>36</code><code>;</code>

<code>    </code><code>M.data[</code><code>5</code><code>].i = </code><code>3</code><code>;</code>

<code>    </code><code>M.data[</code><code>5</code><code>].j = </code><code>4</code><code>;</code>

<code>    </code><code>M.data[</code><code>5</code><code>].e = </code><code>28</code><code>;</code>

<code>    </code><code>M.mu = </code><code>3</code><code>;</code>

<code>    </code><code>M.nu = </code><code>5</code><code>;</code>

<code>    </code><code>return</code> <code>OK;</code>

<code>}</code>

<code>Status FastTransposeSMatrix(TSMatrix M, TSMatrix &amp;T){ </code><code>//采用顺序表存储表示，求稀疏矩阵M的转置矩阵T </code>

<code>    </code><code>int</code> <code>j, p, q, t;</code>

<code>    </code><code>/*j记录遍历时的当前列，cops[j]，则表示当前列第一个非零元的位置或者该列非零元位置的其它位置（cops[j]++），正式转置时用； </code>

<code>    </code><code>p记录遍历时的非零元个数，正式转置时用； </code>

<code>    </code><code>q记录cops[j]，简化代码的表示，正式转置时用 ；</code>

<code>    </code><code>t用在转置准备时。 </code>

<code>    </code><code>*/</code>

<code>    </code><code>int</code> <code>*num;  </code><code>//保存每一列的非零元个数 </code>

<code>    </code><code>int</code> <code>*cpos; </code><code>//保存转置后每列第一个非零元在T中所处的序号</code>

<code>                </code><code>//cops[j]++则是该列的下一个非零元，如果存在的话 </code>

<code>    </code><code>T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;  </code><code>//初始化矩阵T </code>

<code>    </code><code>T.data = (Triple*)malloc(sizeof(Triple)*(T.nu + </code><code>1</code><code>));</code>

<code>    </code><code>num = (</code><code>int</code><code>*)malloc((M.nu + </code><code>1</code><code>)*sizeof(</code><code>int</code><code>)); </code><code>//num和cpos开辟空间比非零元个数大1，是因为不使用0号位置 </code>

<code>    </code><code>cpos = (</code><code>int</code><code>*)malloc((M.nu + </code><code>1</code><code>)*sizeof(</code><code>int</code><code>));</code>

<code>    </code><code>if</code><code>(num == NULL || cpos == NULL)</code>

<code>    </code><code>if</code><code>(T.tu != </code><code>0</code><code>){</code>

<code>        </code><code>for</code><code>(j = </code><code>1</code><code>; j &lt;= M.nu; j++) </code><code>//初始化num向量 </code>

<code>            </code><code>num[j] = </code><code>0</code><code>;</code>

<code>        </code><code>for</code><code>(t = </code><code>1</code><code>;t &lt;= M.tu; t++)   </code><code>//求M中每一列所含非零元的个数 </code>

<code>            </code><code>num[M.data[t].j]++;     </code><code>//这里要用到num[1]~num[5]，所以上面num要全部初始化为0 </code>

<code>        </code> 

<code>        </code><code>cpos[</code><code>1</code><code>] = </code><code>1</code><code>;  </code><code>//这里是一定的 </code>

<code>        </code><code>for</code><code>(j = </code><code>2</code><code>;j &lt;= M.nu; j++)   </code><code>//求每列的第一个非零元在T.data中的序号  </code>

<code>            </code><code>cpos[j] = cpos[j-</code><code>1</code><code>] + num[j-</code><code>1</code><code>]; </code><code>//画表分析得出该公式并不难 </code>

<code>        </code><code>for</code><code>(p = </code><code>1</code><code>; p &lt;= M.tu; p++){        </code><code>//上面是准备工作，下面开始正式转置 </code>

<code>            </code><code>j = M.data[p].j;  </code><code>//j的作用是记录当前遍历的列，以让cops使用 </code>

<code>            </code><code>q = cpos[j];      </code><code>//是为了简化代码，因为下面都要用到cpos[j] </code>

<code>            </code><code>T.data[q].i = M.data[p].j;    </code><code>//交换行 </code>

<code>            </code><code>T.data[q].j = M.data[p].i;    </code><code>//交换列 </code>

<code>            </code><code>T.data[q].e = M.data[p].e;    </code><code>//赋值 ，无论如何交换，储存顺序是已经定下来的了 </code>

<code>                                        </code> 

<code>            </code><code>cpos[j]++;  </code><code>//cops[j]++则是该列的下一个非零元，如果存在的话，不存在的话也没有影响 </code>

<code>        </code><code>}               </code><code>//因为在这个for循环中，如果列变了，即j变化了，cpos[j]也不是原来的值了 </code>

<code>    </code><code>} </code>

<code>    </code><code>free(num);</code>

<code>    </code><code>free(cpos);</code>

<code>int</code> <code>main(</code><code>void</code><code>){</code>

<code>    </code><code>int</code> <code>i,j;</code>

<code>    </code><code>TSMatrix M;</code>

<code>    </code><code>TSMatrix T;</code>

<code>    </code><code>CreateSMatrix(M);  </code>

<code>    </code><code>FastTransposeSMatrix(M, T);</code>

<code>    </code><code>printf(</code><code>"\n"</code><code>);</code>

<code>    </code><code>return</code> <code>0</code><code>;</code>

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

2.测试

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

本文转自 xpleaf 51CTO博客，原文链接：http://blog.51cto.com/xpleaf/1698590，如需转载请自行联系原作者