ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——稀疏矩阵(十字链表【2】) (转)

数据结构学习(C++)——稀疏矩阵(十字链表【2】) (转)

原创 IT综合 作者:amyz 时间:2007-11-09 16:53:35 0 删除 编辑
数据结构学习(C++)——稀疏矩阵(十字链表【2】) (转)[@more@]

如果你细想想,就会发现,非零元节点如果没有指示位置的域,那么做加法和乘法时,为了确定节点的位置,每次都要遍历行和列的链表。因此,为了运算效率,这个域是必须的。为了看出十字链表和单链表的差异,我从单链表派生出十字链表,这需要先定义一种新的结构,如下:

class MatNodeXML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

{

public:

  int data;

  int row, col;

  union { Node *down; List *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 *down; List *downrow; };

  MatNode(int value = 0, Node *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

{

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 *q;

  while (first->data.downrow != NULL)

  {

  q = first->data.downrow;

    first->data.downrow = q->first->data.downrow;

    delete q;

  }

    List::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 *p = first, *t;

    List *q;

  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(matnode);

    t->data.down = p; t = p;

    while (q->first->data.row != i) q = q->first->data.downrow;

    q->LastInsert(t);

  }

  }

 

  void Print()

  {

    List *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 *pA, *pB;

  Node **pAT = new Node*[col + 1];

  Node **pbt = new Node*[matB.col + 1];

  List *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等可以放在首行的头节点里的,但为了清晰一点(本来就够乱了),我把他们单立出来了。另外,很多地方考虑不是很周全,要是不按照注明的要求使用,很容易就会出错。

【后记】按理说,十字链表应该不算是线性链式结构,按照原书的安排,放在链表这章不是很合适;《数据结构(C语言版)》将它和广义表放在一章还是合理的。其实十字链表不是很难,就是很烦人;并且,如果不是数值运算,基本很少用到矩阵,就算是用到矩阵运算,在矩阵规模不大的时候,可以用二维数组代替十字链表。从历届考研题来看,这部分几乎没有题,原因就是麻烦(你写起来麻烦,他批起来也麻烦)、不常用、算法固定没新意。所以,你要是闹心,这部分跳过去也可以。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-981481/,如需转载,请注明出处,否则将追究法律责任。

上一篇: Eclipse DIY (转)
请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7338940