資料結構學習（C++）——稀疏矩陣（十字連結清單【2】）

如果你細想想，就會發現，非零元節點如果沒有訓示位置的域，那麼做加法和乘法時，為了确定節點的位置，每次都要周遊行和列的連結清單。是以，為了運算效率，這個域是必須的。為了看出十字連結清單和單連結清單的差異，我從單連結清單派生出十字連結清單，這需要先定義一種新的結構，如下：

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語言版）》将它和廣義表放在一章還是合理的。其實十字連結清單不是很難，就是很煩人；并且，如果不是數值運算，基本很少用到矩陣，就算是用到矩陣運算，在矩陣規模不大的時候，可以用二維數組代替十字連結清單。從曆屆考研題來看，這部分幾乎沒有題，原因就是麻煩（你寫起來麻煩，他批起來也麻煩）、不常用、算法固定沒新意。是以，你要是鬧心，這部分跳過去也可以。