<b>数据构造学习(C++)之稀疏矩阵</b>[VC/C++编程]

先说说什么叫稀疏矩阵.你说,这个问题很简单吗,那你一定不知道中国学术界的嘴皮子仗,对一个字眼的“抠”将会招致两种相反的结论.这是清华2000年的一道考研题:“表示一个有1000个顶点,1000条边的有向图的毗邻矩阵有多少个矩阵元素?能否稀疏矩阵?”假如你是个喜好研究出题者心理活动的人,你可以看出这里有两个陷阱,就是让明显会的人答错,我不想说出是什么,留给读者考虑.姑且不管清华给的尺度答案是什么,那年的参考书是严蔚敏的《数据构造（C语言版）》,书上关于稀疏矩阵的定义是这样的:“非零元较零元少（注:原书下文给出了大致的程度）,且分布没有一定规律”,照这个说法,那题的答案应当是不一定是稀疏矩阵,因为大概是特别矩阵（非零元分布有规律）.

自从2002年换参考书后,很多概念都发生了改变,最明显的是从多少开始计数（0还是1）,从而招致的是空树的高度变成了－1,只有一个根节点的树高度是0.很不幸的是树高的问题几近些年年都考,在你下笔的时刻,老是犯点嘀咕,总不是一朝天子一朝臣吧,会不会答案是个兼容版本?然后,新参考书带的习题集里引用了那道考研题,答案是是稀疏矩阵.你大概会惊奇这年初咸鱼城市游泳了,但这个答案和书并不冲突,因为在这本黄皮书里,根本就没有什么特别矩阵,自然就一定是稀疏矩阵了.

其实,这两本书在这个问题上也没什么原则上的问题,C版的是从数据构造实现辨别出特别矩阵和稀疏矩阵,毕竟他们实现起来很不相同;新书一股脑把非零元少的矩阵都当作稀疏矩阵,当你按照这种思绪做的时刻就会发现,各种构造特别的非零元很少的矩阵,假如用十字链表来储存的话,比考虑到它的特别构造得出的特有储存办法,仅仅是浪费了几个表头节点和一些指针域,再有就是一些运算效率的降低.从我个人角度讲,我更喜好多一些统一,少一些分外,即便牺牲一点效率;所以在这一点上我赞成新参考书的做法.而在计数起点上,我更喜好本来的做法;毕竟,研究数据构造要考虑人的考虑习惯,而不是计算机喜好什么;你非得说表中的第一个元素是第0个,空树的高是－1,怎么不让人心里起疙瘩.数据构造是人们构造算法时思维和计算机实现的桥梁、中介,它应当符合人的考虑习惯,即便在它实现的时刻内部做了某些转换.开始废话了这么多,但愿没撤销了你往下看的心情,好,言归正传.