5.2.2 稀疏矩阵的压缩存储方法

　二、行逻辑链接的顺序表

　　假设以行序为主序的次序（每一行按列序有序）输入稀疏矩阵的非零元（行下标、列下标、非零元的值），则建立该稀疏矩阵的行逻辑链接的顺序表的算法如下。

算法 5.2
　　void Create_SM(RLSMatrix& M)
　{
　　// 以行序为主序的次序逐个输入非零元，
　　// 建立稀疏矩阵的行逻辑链接顺序表
　　cin >> M.rows>>M.cols>>M.terms;
　　k = 1; curRow = 0;
　　for (i=1; i<= M.terms; i++) {
　　　cin>>M.data[k].i >> M.data[k].j >> M.data[k].e;
　　　while (curRow < M.data[k].i)
　　　　M.rpos[++curRow]=k;
　　　++k;
　　} // for
　　while (curRow < M.rows+1) 　　　　　　　　// 剩余的没有非零元的行
　　　M.rpos[++curRow]=k;
　}

　　上述算法的控制结构只有一个for循环，显然它的时间复杂度为O(M.terms)。		  
　　如何建立稀疏矩阵的行逻辑链接的顺序表？

　　首先应该输入该矩阵的行数、列数以及非零元的个数，然后依次输入各个非零元的行号、列号和它的值，并在输入每一行的第一个非零元的同时为 rpos 中相应分量赋值。显然，对于顺序结构应尽少进行 "移动元素"的操作，因此非零元的输入次序应对行有序，且同一行的非零元按列有序。

　　算法中需要注意的是，可能存在某一行或连续几行都没有非零元的情况，则这些行的"第一个非零元在顺序表中的位置"应该和当前输入的那个非零元所在行相同。

　　虽然，表面上 rpos 中各分量的值只是指示每一行的第一个非零元在 data 中的位置，实际上它还隐含着一个信息，即
　"第 k 行的非零元的个数=rpos[k+1]-rpos[k]"。
　 为了使这个公式也适用于最后一行，在 rpos 中增添一个下标为(行数+1)的分量。

　　例如，按此算法得到的前面所举矩阵 M 的 rpos 值如下所示：
行号
1
2
3
4
5
6
M.rpos
1
3
3
4
6
7

　　显然如果非零元不是按它们所在行列有序的次序输入的话，算法5.2 的时间复杂度将是"平方级别" 的。