【資料結構之旅】稀疏矩陣的快速轉置

說明：

    稀疏矩陣的快速轉置算法的核心在于，用一個數組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，如需轉載請自行聯系原作者