终于回来了。粗略地看了下小施与有容的代码，简单点评一下，说的不对的地方两位见谅呵呵。


小施的代码利用链表实现矩阵的压缩存储，矩阵的尺寸可根据需要在机器资源允许的范围内任意伸缩。达到了我开贴的要求。再确认一下有没有什么BUG就准备领奖吧。

美中不足是效率偏低，对数据的检索在行列两个方向上都是顺序检索。这样虽然可以最大限度地降低空间的消耗，但代价是时间。

一个折衷的方案是对于矩阵的其中一维使用数组（这样可以直接检索以提高检索效率），另一维使用链表以降低空间消耗。一般行的头指针用数组，每行元素用链表。


有容的代码是用一个固定尺寸的一维数组来存储稀疏矩阵的有效元素。这种做法在小范围内可以实现矩阵操作的要求，但毕竟是受限的。固定的空间操作小规模的矩阵存在空间浪费，而对于大规模的矩阵可能又会因为空间不足而操作失败。而且这种结构的矩阵操作算法效率更低，元素的插入删除需要做大量的数据移动。

呵呵，建议有容重新设计矩阵结构，再接再厉。

关于稀疏矩阵的判定标准是个很模糊的概念，小施提到的那个判定公式也不过是个经验公式。所以，我们建立的稀疏矩阵理论上要完全能够操作一个普通矩阵才行（因为空间不足导致操作失败的因素不予考虑）。

呵呵，有容继续努力。再等两天，看看还有没有人想拿这分。

你俩后天晚上7点左右记得来领分，过期作废哦！

这个论坛的分有三种。可用分、专家分、积分。

可用分只能靠自己发贴获取（还有参与投票）。

专家分靠回答坛友问题由坛友赠予。

积分，网友请帖赠予。

如果你你俩想要积分我倒是现在就可以给你们，专家分如果你俩想平分这贴的100分也可以，但想得到我承诺的每人百分只能由我开新贴你们来领。

正在细看你们的代码，刚看到小施的matrix_set函数即发现问题。回答以下问题

1.当参数line或row为负值应该怎么处理。
2.当参数value为0应该怎么处理。

0的问题是我看错了，你确实释放了该结点。呵呵，被你的变量名row给搞混了。

继续阅读中......

致小施
matrix_set中value为0还是有问题。因为你行首也是用的链表，当该行仅包含一个元素时，删除该元素后应该将这个行结点也删除掉，对吧？你的代码中好像没有处理这种情况。

致小施
之后的运算函数逻辑上倒没什么问题，只是运算效率太低了。
虽然调用已有的get和set函数可以简化代码，但每操作一个元素都要重新定位一次。
设矩阵尺寸为n行m列，则每次定位的时间复杂度中O(n+m)。以加法运算为例，每一次矩阵加法运算的时间复杂度是O(n*m*(n+m))。如果认为n接近于m，则可以表达成O(n^3)。
事实利用稀疏的特点，设矩阵中有效元素的数量为c，则两个矩阵相加的时间复杂度可以达到O(c)的程度。相差3个数量级，这一定要引起重视。
这有多大差别？如果O(c)的算法需要计算1秒钟的话，O(n^3)很可能1天也算不完。

这不影响我给你的送分承诺（承诺中没有要求效率），只是我很重视程序的执行效率，希望这次论剑不光是展示各位的能力，也希望各位能有所收获。

小施的代码就看到这里，该阅读有容的代码了


[ 本帖最后由 beyondyf 于 2012-8-11 16:20 编辑 ]

致有容
Matrix_set没有对0值的处理，这将使你固定的矩阵空间很快被本不该出现的0消耗掉。
矩阵的存储方式实在不是三元组行链的实现方式，这点我很报歉，要尽快修改。你这种方式受限太多，几乎不实用，而且操作复杂度更高。

看来再等也不会有惊喜了。就到这儿了。

有容的新代码有所改进，不过行还是用的固定数组，呵呵，而且既然已经有了这个数组为什么还要再动态申请一个空的头结点呢？get函数也没有做合法性判断。

不足之处就说到这里了，还是要鼓励一下，毕竟在这么繁荣的C论坛能参与这次论剑的也只有小施和有容了。

两位来领奖励吧，关注我发的奖励贴。

呵呵，只要你们兴趣看我可以写一个。想看行链表的呢，还是来个十字链表的？

[ 本帖最后由 beyondyf 于 2012-8-12 21:09 编辑 ]

好的，近期奉上。