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

　　C++数据结构中，先说说什么叫稀疏矩阵。你说，这个问题很简单吗，那你一定不知道中国学术界的嘴皮子仗，对一个字眼的“抠”将会导致两种相反的结论。这是清华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
  
  
  
};

　　另外，由于这样的十字链表是由多条单链表拼起来的，为了访问每条单链表的保护成员，要声明十字链表类为单链表类的友元。即在class List的声明中添加friend class Matrix;

#p#

　　稀疏矩阵的定义和实现

 
 
 
  
  
  #ifndef Matrix_H  
  
  
  #define Matrix_H  
  
  
   
  
  
  #include "List.h"  
  
  
   
  
  
  class MatNode  
  
  
  {  
  
  
  public:  
  
  
  int data;  
  
  
  int row, col;  
  
  
  union { Node
  
  
  
MatNode(int value = 0, Node
  
  
  
: 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
  
  
  
{  
  
  
  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
  
  
  
while (first-＞data.downrow != NULL)  
  
  
  {  
  
  
  q = first-＞data.downrow;  
  
  
  first-＞data.downrow = q-＞first-＞data.downrow;  
  
  
  delete q;  
  
  
  }  
  
  
  List
  
  
  
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
  
  
  
List
  
  
  
for (j = 1; j <= col; j++) LastInsert(MatNode(0, NULL, 0, j));  
  
  
  for (i = 1; i <= row; i++)  
  
  
  {  
  
  
  q = new List
  
  
  
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
  
  
  
t-＞data.down = p; t = p;  
  
  
  while (q-＞first-＞data.row != i) q = q-＞first-＞data.downrow;  
  
  
  q-＞LastInsert(t);  
  
  
  }  
  
  
  }  
  
  
   
  
  
  void Print()  
  
  
  {  
  
  
  List
  
  
  
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
  
  
  
Node
  
  
  
Node
  
  
  
List
  
  
  
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等可以放在首行的头节点里的，但为了清晰一点(本来就够乱了)，我把他们单立出来了。另外，很多地方考虑不是很周全，要是不按照注明的要求使用，很容易就会出错。

【编辑推荐】

1.51 将稀疏矩阵表示为数组
经典四讲贯通C++排序之一插入排序
1.51.1 如何把两个稀疏矩阵相加
给C++初学者的50个忠告
C++数据结构学习之栈和队列
程序员必看 c++笔试题汇总

文章标题：C++数据结构学习之稀疏矩阵
文章URL：http://www.shufengxianlan.com/qtweb/news43/342193.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容