如果你细想想，就会发现，非零元节点如果没有指示位置的域，那么做加法和乘法时，为了确定节点的位置，每次都要遍历行和列的链表。因此，为了运算效率，这个域是必须的。为了看出十字链表和单链表的差异，我从单链表派生出十字链表，这需要先定义一种新的结构，如下： 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等可以放在首行的头节点里的，但为了清晰一点（本来就够乱了），我把他们单立出来了。另外，很多地方考虑不是很周全，要是不按照注明的要求使用，很容易就会出错。 【后记】按理说，十字链表应该不算是线性链式结构，按照原书的安排，放在链表这章不是很合适；《数据结构（C语言版）》将它和广义表放在一章还是合理的。其实十字链表不是很难，就是很烦人；并且，如果不是数值运算，基本很少用到矩阵，就算是用到矩阵运算，在矩阵规模不大的时候，可以用二维数组代替十字链表。从历届考研题来看，这部分几乎没有题，原因就是麻烦（你写起来麻烦，他批起来也麻烦）、不常用、算法固定没新意。所以，你要是闹心，这部分跳过去也可以。

评论