先說說什么叫稀疏矩陣。你說，這個問題很簡單嗎，那你一定不知道中國學術界的嘴皮子仗，對一個字眼的“摳”將會導致兩種相反的結論。這是清華2000年的一道考研題：“表示一個有1000個頂點，1000條邊的有向圖的鄰接矩陣有多少個矩陣元素？是否稀疏矩陣？”如果你是個喜歡研究出題者心理活動的人，你可以看出這里有兩個陷阱，就是讓明明會的人答錯，我不想說出是什么，留給讀者思考。姑且不論清華給的標準答案是什么，那年的參考書是嚴蔚敏的《數據結構（C語言版）》，書上對于稀疏矩陣的定義是這樣的：“非零元較零元少（注：原書下文給出了大致的程度），且分布沒有一定規律”，照這個說法，那題的答案應該是不一定是稀疏矩陣，因為可能是特殊矩陣（非零元分布有規律）。自從2002年換參考書后，很多概念都發生了變化，最明顯的是從多少開始計數（0還是1），從而導致的是空樹的高度變成了－1，只有一個根節點的樹高度是0。很不幸的是樹高的問題幾乎年年都考，在你下筆的時候，總是犯點嘀咕，總不是一朝天子一朝臣吧，會不會答案是個兼容版本？然后，新參考書帶的習題集里引用了那道考研題，答案是是稀疏矩陣。你也許會驚訝這年頭咸魚都會游泳了，但這個答案和書并不矛盾，因為在這本黃皮書里，根本就沒有什么特殊矩陣，自然就一定是稀疏矩陣了。其實，這兩本書在這個問題上也沒什么原則上的問題，C版的是從數據結構實現區分出特殊矩陣和稀疏矩陣，畢竟他們實現起來很不相同；新書一股腦把非零元少的矩陣都當成稀疏矩陣，當你按照這種思路做的時候就會發現，各種結構特殊的非零元很少的矩陣，如果用十字鏈表來儲存的話，比考慮到它的特殊結構得出的特有儲存方法，僅僅是浪費了幾個表頭節點和一些指針域，再有就是一些運算效率的降低。從我個人角度講，我更喜歡多一些統一，少一些特別，即使犧牲一點效率；所以在這一點上我贊同新參考書的做法。而在計數起點上，我更喜歡原來的做法；畢竟，研究數據結構要考慮人的思考習慣，而不是計算機喜歡什么；你非得說表中的第一個元素是第0個，空樹的高是－1，怎么不讓人心里起疙瘩。數據結構是人們構造算法時思維和計算機實現的橋梁、中介，它應該符合人的思考習慣，即使在它實現的時候內部做了某些轉換。開始廢話了這么多，希望沒打消了你往下看的心情，好，言歸正傳。
這里的十字鏈表是這樣構成的：用鏈表模擬矩陣的行（或者列，這可以根據個人喜好來定），然后，再構造代表列的鏈表，將每一行中的元素節點插入到對應的列中去。書中為了少存幾個表頭節點，將行和列的表頭節點合并到了一起——實際只是省了幾個指針域，如果行和列數不等，多余的數據域就把這點省出的空間又給用了。這點小動作讓我著實廢了半天勁，個人感覺，優點不大，缺點不少，不如老老實實寫得象個十字鏈表，讓人也好看一些，這是教科書，目的是教學。實在看得暈的人，參閱C版的這部分內容，很清晰。我也不會畫圖，打個比方吧：這個十字鏈表的邏輯結構就像是一個圍棋盤（沒見過，你就想一下蒼蠅拍，這個總見過吧），而非零元就好像是在棋盤上放的棋子，總共占的空間就是，確定那些線的表頭節點和那些棋子代表的非零元節點。最后，我們用一個指針指向這個棋盤，這個指針就代表了這個稀疏矩陣。
現在，讓我們看看非零元節點最少需要哪幾個域，data必須的，down、right把線畫下去，好像不需要別的了。再看看表頭節點，由于是鏈表的表頭節點，所以就和后邊的節點一樣了。然后，行鏈表和列鏈表的表頭節點實際上也各構成了一個鏈表，我們給他們添加一個公有的表頭節點。最后，通過指向這個行列鏈表表頭構成的鏈表的公有的表頭節點的指針，我們就可以訪問稀疏矩陣了。
好像和書上的不一樣——非零元節點沒了指示位置的I、j，實際上，對于確定非零元在矩陣中的位置，I、j不是必須的，看著圍棋盤你就會很清楚。但是很不幸，不是把他們存起來就萬事大吉了，最起碼，必須考慮加法和乘法的效率，請你想想如果用上面的那種結構，如何完成。考慮到到這里已經寫了不少字，我將實現部分放在下篇，今天該休息了。
據結構學習（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->dat