数据结构学习(C++)之稀疏矩阵

3/8/2008来源:C/C++教程人气:6873


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

  自从2002年换参考书后,很多概念都发生了变化,最明显的是从多少开始计数(0还是1),从而导致的是空树的高度变成了-1,只有一个根节点的树高度是0。很不幸的是树高的问题几乎年年都考,在你下笔的时候,总是犯点嘀咕,总不是一朝天子一朝臣吧,会不会答案是个兼容版本?然后,新参考书带的习题集里引用了那道考研题,答案是是稀疏矩阵。你也许会惊奇这年头咸鱼都会游泳了,但这个答案和书并不矛盾,因为在这本黄皮书里,根本就没有什么非凡矩阵,自然就一定是稀疏矩阵了。

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

  这里的十字链表是这样构成的:用链表模拟矩阵的行(或者列,这可以根据个人喜好来定),然后,再构造代表列的链表,将每一行中的元素节点插入到对应的列中去。书中为了少存几个表头节点,将行和列的表头节点合并到了一起——实际只是省了几个指针域,假如行和列数不等,多余的数据域就把这点省出的空间又给用了。这点小动作让我着实废了半天劲,个人感觉,优点不大,缺点不少,不如老老实实写得象个十字链表,让人也好看一些,这是教科书,目的是教学。实在看得晕的人,参阅C版的这部分内容,很清楚。我也不会画图,打个比方吧:这个十字链表的逻辑结构就像是一个围棋盘(没见过,你就想一下苍蝇拍,这个总见过吧),而非零元就似乎是在棋盘上放的棋子,总共占的空间就是,确定那些线的表头节点和那些棋子代表的非零元节点。最后,我们用一个指针指向这个棋盘,这个指针就代表了这个稀疏矩阵。

  现在,让我们看看非零元节点最少需要哪几个域,data必须的,down、right把线画下去,似乎不需要别的了。再看看表头节点,由于是链表的表头节点,所以就和后边的节点一样了。然后,行链表和列链表的表头节点实际上也各构成了一个链表,我们给他们添加一个公有的表头节点。最后,通过指向这个行列链表表头构成的链表的公有的表头节点的指针,我们就可以访问稀疏矩阵了。

  似乎和书上的不一样——非零元节点没了指示位置的I、j,实际上,对于确定非零元在矩阵中的位置,I、j不是必须的,看着围棋盘你就会很清楚。但是很不幸,不是把他们存起来就万事大吉了,最起码,必须考虑加法和乘法的效率,请你想想假如用上面的那种结构,如何完成。
  假如你细想想,就会发现,非零元节点假如没有指示位置的域,那么做加法和乘法时,为了确定节点的位置,每次都要遍历行和列的链表。因此,为了运算效率,这个域是必须的。为了看出十字链表和单链表的差异,我从单链表派生出十字链表,这需要先定义一种新的结构,如下:

class MatNode

{
public:
int data;
int row, col;
union { Node<MatNode> *down; List<MatNode> *downrow; };
};

  另外,由于这样的十字链表是由多条单链表拼起来的,为了访问每条单链表的保护成员,要声明十字链表类为单链表类的友元。即在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

  【说明】对于十字链表来说,只要记住对每个节点的操作,要同时考虑它的两个指针域,那么,各种算法的理解都不是很难。比如说矩阵加法,“两个矩阵相加和两个一元多项式相加极为相似,所不同的是一元多项式只有一个变元(指数项),而矩阵中每个非零元有两个变元(行值和列值),每个节点既在行表中又在列表中,致使插入和删除节点时指针的修改稍为复杂,故需要更多的辅助指针。”(《数据结构(C语言版)》)其实private的row等可以放在首行的头节点里的,但为了清楚一点(本来就够乱了),我把他们单立出来了。另外,很多地方考虑不是很周全,要是不按照注明的要求使用,很轻易就会出错。