数据布局进修(C++)之稀疏矩阵
副标题#e#
先说说什么叫稀疏矩阵。你说，这个问题很简朴吗，那你必然不知道中国粹术界的嘴皮子仗，对一个字眼的“抠”将会导致两种相反的结论。这是清华2000年的一道考研题：“暗示一个有1000个极点，1000条边的有向图的连接矩阵有几多个矩阵元素？是否稀疏矩阵？”假如你是个喜欢研究出题者心理勾当的人，你可以看出这里有两个陷阱，就是让显着会的人答错，我不想说出是什么，留给读者思考。暂时岂论清华给的尺度谜底是什么，那年的参考书是严蔚敏的《数据布局（C语言版）》，书上对付稀疏矩阵的界说是这样的：“非零元较零元少（注：原书下文给出了大抵的水平），且漫衍没有必然纪律”，照这个说法，那题的谜底应该是不必然是稀疏矩阵，因为大概是非凡矩阵（非零元漫衍有纪律）。
自从2002年换参考书后，许多观念都产生了变革，最明明的是从几多开始计数（0照旧1），从而导致的是空树的高度酿成了－1，只有一个根节点的树高度是0。很不幸的是树高的问题险些年年都考，在你下笔的时候，老是犯点嘀咕，总不是一朝皇帝一朝臣吧，会不会谜底是个兼容版本？然后，新参考书带的习题集里引用了那道考研题，谜底是是稀疏矩阵。你也许会惊奇这年初咸鱼城市游泳了，但这个谜底和书并不抵牾，因为在这本黄皮书里，基础就没有什么非凡矩阵，自然就必然是稀疏矩阵了。
其实，这两本书在这个问题上也没什么原则上的问题，C版的是从数据布局实现区分出非凡矩阵和稀疏矩阵，究竟他们实现起来很不沟通；新书一股脑把非零元少的矩阵都当成稀疏矩阵，当你凭据这种思路做的时候就会发明，各类布局非凡的非零元很少的矩阵，假如用十字链表来储存的话，比思量到它的非凡布局得出的特有储存要领，仅仅是挥霍了几个表头节点和一些指针域，再有就是一些运算效率的低落。从我小我私家角度讲，我更喜欢多一些统一，少一些出格，纵然牺牲一点效率；所以在这一点上我附和新参考书的做法。而在计数起点上，我更喜欢本来的做法；究竟，研究数据布局要思量人的思考习惯，而不是计较机喜欢什么；你非得说表中的第一个元素是第0个，空树的高是－1，怎么不让人心里起疙瘩。数据布局是人们结构算法时思维和计较机实现的桥梁、中介，它应该切合人的思考习惯，纵然在它实现的时候内部做了某些转换。开始空话了这么多，但愿没撤销了你往下看的脸色，好，言归正传。
#p#副标题#e#
这里的十字链表是这样组成的：用链表模仿矩阵的行（可能列，这可以按照小我私家爱好来定），然后，再结构代表列的链表，将每一行中的元素节点插入到对应的列中去。书中为了少存几个表头节点，将行和列的表头节点归并到了一起——实际只是省了几个指针域，假如行和列数不等，多余的数据域就把这点省出的空间又给用了。这点小行动让我着实废了半天劲，小我私家感受，利益不大，缺点不少，不如老诚恳实写得象个十字链表，让人也悦目一些，这是教科书，目标是解说。实在看得晕的人，参阅C版的这部门内容，很清晰。我也不会绘图，打个例如吧：这个十字链表的逻辑布局就像是一个围棋盘（没见过，你就想一下苍蝇拍，这个总见过吧），而非零元就仿佛是在棋盘上放的棋子，总共占的空间就是，确定那些线的表头节点和那些棋子代表的非零元节点。最后，我们用一个指针指向这个棋盘，这个指针就代表了这个稀疏矩阵。
此刻，让我们看看非零元节点最少需要哪几个域，data必需的，down、right把线画下去，仿佛不需要此外了。再看看表头节点，由于是链表的表头节点，所以就和后边的节点一样了。然后，行链表和列链表的表头节点实际上也各组成了一个链表，我们给他们添加一个公有的表头节点。最后，通过指向这个队列链表表头组成的链表的公有的表头节点的指针，我们就可以会见稀疏矩阵了。
仿佛和书上的纷歧样——非零元节点没了指示位置的I、j，实际上，对付确定非零元在矩阵中的位置，I、j不是必需的，看着围棋盘你就会很清楚。可是很不幸，不是把他们存起来就万事大吉了，最起码，必需思量加法和乘法的效率，请你想想假如用上面的那种布局，如何完成。
假如你细想想，就会发明，非零元节点假如没有指示位置的域，那么做加法和乘法时，为了确定节点的位置，每次都要遍历行和列的链表。因此，为了运算效率，这个域是必需的。为了看出十字链表和单链表的差别，我从单链表派生出十字链表，这需要先界说一种新的布局，如下：
class MatNode
{
public:
int data;
int row, col;
union { Node<MatNode＞ *down; List<MatNode＞ *downrow; };
};#p#分页标题#e#
别的，由于这样的十字链表是由多条单链表拼起来的，为了会见每条单链表的掩护成员，要声明十字链表类为单链表类的友元。即在class List的声明中添加friend class Matrix;
稀疏矩阵的界说和实现
#ifndef Matrix_H
#define Matrix_H
#include "List.h"
class MatNode
{
public:
int data;
int row, col;
union { Node<MatNode＞ *down; List<MatNode＞ *downrow; };
MatNode(int value = 0, Node<MatNode＞ *p = NULL, int i = 0, int j = 0)
: data(value), down(p), row(i), col(j) {}
friend ostream & operator << (ostream & strm, MatNode &mtn)
{
strm << '(' << mtn.row << ',' << mtn.col << ')' << mtn.data;
return strm;
}
};
class Matrix : List<MatNode＞
{
public:
Matrix() : row(0), col(0), num(0) {}
Matrix(int row, int col, int num) : row(row), col(col), num(num) {}
~Matrix() { MakeEmpty(); }
void MakeEmpty()
{
List<MatNode＞ *q;
while (first-＞data.downrow != NULL)
{
q = first-＞data.downrow;
first-＞data.downrow = q-＞first-＞data.downrow;
delete q;
}
List<MatNode＞::MakeEmpty();
row = col = num = 0;
}
void Input()
{
if (!row) { cout << "输入矩阵行数："; cin ＞＞ row; }
if (!col) { cout << "输入矩阵列数："; cin ＞＞ col; }
if (!num) { cout << "输入非零个数："; cin ＞＞ num; }
if (!row || !col || !num) return;
cout << endl << "请按顺序输入各个非零元素，以列序为主，输入0暗示本列竣事" << endl;
int i, j, k, v;//i行数 j列数 k个非零元 v非零值
Node<MatNode＞ *p = first, *t;
List<MatNode＞ *q;
for (j = 1; j <= col; j++) LastInsert(MatNode(0, NULL, 0, j));
for (i = 1; i <= row; i++)
{
q = new List<MatNode＞;
q-＞first-＞data.row = i;
p-＞data.downrow = q;
p = q-＞first;
}
j = 1; q = first-＞data.downrow; First(); t = pNext();
for (k = 0; k < num; k++)
{
if (j ＞ col) break;
cout << endl << "输入第" << j << "列非零元素" << endl;
cout << "行数："; cin ＞＞ i;
if (i < 1 || i ＞ row) { j++; k--; q = first-＞data.downrow; t = pNext(); continue; }
cout << "非零元素值"; cin ＞＞ v;
if (!v) { k--; continue; }
MatNode matnode(v, NULL, i, j);
p = new Node<MatNode＞(matnode);
t-＞data.down = p; t = p;
while (q-＞first-＞data.row != i) q = q-＞first-＞data.downrow;
q-＞LastInsert(t);
}
}
void Print()
{
List<MatNode＞ *q = first-＞data.downrow;
cout << endl;
while (q != NULL)
{
cout << *q;
q = q-＞first-＞data.downrow;
}
}
Matrix & Add(Matrix &matB)
{
//初始化赋值帮助变量
if (row != matB.row || col != matB.col || matB.num == 0) return *this;
Node<MatNode＞ *pA, *pB;
Node<MatNode＞ **pAT = new Node<MatNode＞*[col + 1];
Node<MatNode＞ **pBT = new Node<MatNode＞*[matB.col + 1];
List<MatNode＞ *qA = pGetFirst()-＞data.downrow, *qB = matB.pGetFirst()-＞data.downrow;
First(); matB.First();
for (int j = 1; j <= col; j++)
{
pAT[j] = pNext();
pBT[j] = matB.pNext();
}
//开始
for (int i = 1; i <= row; i++)
{
qA-＞First(); qB-＞First();
pA = qA-＞pNext(); pB = qB-＞pNext();
while (pA != NULL && pB !=NULL)
{
if (pA-＞data.col == pB-＞data.col)
{
pA-＞data.data += pB-＞data.data;
pBT[pB-＞data.col]-＞data.down = pB-＞data.down; qB-＞Remove();
if (!pA-＞data.data)
{
pAT[pA-＞data.col]-＞data.down = pA-＞data.down;
qA-＞Remove();
}
else
{
pAT[pA-＞data.col] = pA;
qA-＞pNext();
}
}
else
{
if (pA-＞data.col ＞ pB-＞data.col)
{
pBT[pB-＞data.col]-＞data.down = pB-＞data.down;
qB-＞pRemove();
pB-＞data.down = pAT[pB-＞data.col]-＞data.down;
pAT[pB-＞data.col]-＞data.down = pB;
pAT[pB-＞data.col] = pB;
qA-＞InsertBefore(pB);
}
else if (pA-＞data.col < pB-＞data.col)
{
pAT[pA-＞data.col] = pA;
qA-＞pNext();
}
}
pA = qA-＞pGet();pB = qB-＞pGet();
}
if (pA == NULL && pB != NULL)
{
qA-＞pGetPrior()-＞link = pB;
qB-＞pGetPrior()-＞link = NULL;
while (pB != NULL)
{
pBT[pB-＞data.col]-＞data.down = pB-＞data.down;
pB-＞data.down = pAT[pB-＞data.col]-＞data.down;
pAT[pB-＞data.col]-＞data.down = pB;
pAT[pB-＞data.col] = pB;
pB = pB-＞link;
}
}
if (pA !=NULL)
{
while (qA-＞pGet() != NULL)
{
pAT[pA-＞data.col] = pA;
qA-＞pNext();
}
}
qA = qA-＞first-＞data.downrow; qB = qB-＞first-＞data.downrow;
}
delete []pAT; delete []pBT;
return *this;
}
private:
int row, col, num;
};
#endif
#p#分页标题#e#
【说明】对付十字链表来说，只要记着对每个节点的操纵，要同时思量它的两个指针域，那么，各类算法的领略都不是很难。好比说矩阵加法，“两个矩阵相加和两个一元多项式相加极为相似，所差异的是一元多项式只有一个变元（指数项），而矩阵中每个非零元有两个变元（行值和列值），每个节点既在行表中又在列表中，致使插入和删除节点时指针的修改稍为巨大，故需要更多的帮助指针。”（《数据布局（C语言版）》）其实private的row等可以放在首行的头节点里的，但为了清晰一点（原来就够乱了），我把他们单立出来了。别的，许多处所思量不是很周全，要是不凭据注明的要求利用，很容易就会堕落。
