C++數(shù)據(jù)結(jié)構(gòu)中，先說說什么叫稀疏矩陣。你說，這個問題很簡單嗎，那你一定不知道中國學(xué)術(shù)界的嘴皮子仗，對一個字眼的“摳”將會導(dǎo)致兩種相反的結(jié)論。這是清華2000年的一道考研題：“表示一個有1000個頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否稀疏矩陣?”如果你是個喜歡研究出題者心理活動的人，你可以看出這里有兩個陷阱，就是讓明明會的人答錯，我不想說出是什么，留給讀者思考。姑且不論清華給的標(biāo)準(zhǔn)答案是什么，那年的參考書是嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)(C語言版)》，書上對于稀疏矩陣的定義是這樣的：“非零元較零元少(注：原書下文給出了大致的程度)，且分布沒有一定規(guī)律”，照這個說法，那題的答案應(yīng)該是不一定是稀疏矩陣，因?yàn)榭赡苁翘厥饩仃?非零元分布有規(guī)律)。

　　自從2002年換參考書后，很多概念都發(fā)生了變化，最明顯的是從多少開始計數(shù)(0還是1)，從而導(dǎo)致的是空樹的高度變成了-1，只有一個根節(jié)點(diǎn)的樹高度是0。很不幸的是樹高的問題幾乎年年都考，在你下筆的時候，總是犯點(diǎn)嘀咕，總不是一朝天子一朝臣吧，會不會答案是個兼容版本?然后，新參考書帶的習(xí)題集里引用了那道考研題，答案是是稀疏矩陣。你也許會驚訝這年頭咸魚都會游泳了，但這個答案和書并不矛盾，因?yàn)樵谶@本黃皮書里，根本就沒有什么特殊矩陣，自然就一定是稀疏矩陣了。

　　其實(shí)，這兩本書在這個問題上也沒什么原則上的問題，C版的是從數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)區(qū)分出特殊矩陣和稀疏矩陣，畢竟他們實(shí)現(xiàn)起來很不相同;新書一股腦把非零元少的矩陣都當(dāng)成稀疏矩陣，當(dāng)你按照這種思路做的時候就會發(fā)現(xiàn)，各種結(jié)構(gòu)特殊的非零元很少的矩陣，如果用十字鏈表來儲存的話，比考慮到它的特殊結(jié)構(gòu)得出的特有儲存方法，僅僅是浪費(fèi)了幾個表頭節(jié)點(diǎn)和一些指針域，再有就是一些運(yùn)算效率的降低。從我個人角度講，我更喜歡多一些統(tǒng)一，少一些特別，即使?fàn)奚稽c(diǎn)效率;所以在這一點(diǎn)上我贊同新參考書的做法。而在計數(shù)起點(diǎn)上，我更喜歡原來的做法;畢竟，研究數(shù)據(jù)結(jié)構(gòu)要考慮人的思考習(xí)慣，而不是計算機(jī)喜歡什么;你非得說表中的***個元素是第0個，空樹的高是-1，怎么不讓人心里起疙瘩。數(shù)據(jù)結(jié)構(gòu)是人們構(gòu)造算法時思維和計算機(jī)實(shí)現(xiàn)的橋梁、中介，它應(yīng)該符合人的思考習(xí)慣，即使在它實(shí)現(xiàn)的時候內(nèi)部做了某些轉(zhuǎn)換。開始廢話了這么多，希望沒打消了你往下看的心情，好，言歸正傳。

　　這里的十字鏈表是這樣構(gòu)成的：用鏈表模擬矩陣的行(或者列，這可以根據(jù)個人喜好來定)，然后，再構(gòu)造代表列的鏈表，將每一行中的元素節(jié)點(diǎn)插入到對應(yīng)的列中去。書中為了少存幾個表頭節(jié)點(diǎn)，將行和列的表頭節(jié)點(diǎn)合并到了一起——實(shí)際只是省了幾個指針域，如果行和列數(shù)不等，多余的數(shù)據(jù)域就把這點(diǎn)省出的空間又給用了。這點(diǎn)小動作讓我著實(shí)廢了半天勁，個人感覺，優(yōu)點(diǎn)不大，缺點(diǎn)不少，不如老老實(shí)實(shí)寫得象個十字鏈表，讓人也好看一些，這是教科書，目的是教學(xué)。實(shí)在看得暈的人，參閱C版的這部分內(nèi)容，很清晰。我也不會畫圖，打個比方吧：這個十字鏈表的邏輯結(jié)構(gòu)就像是一個圍棋盤(沒見過，你就想一下蒼蠅拍，這個總見過吧)，而非零元就好像是在棋盤上放的棋子，總共占的空間就是，確定那些線的表頭節(jié)點(diǎn)和那些棋子代表的非零元節(jié)點(diǎn)。***，我們用一個指針指向這個棋盤，這個指針就代表了這個稀疏矩陣。

　　現(xiàn)在，讓我們看看非零元節(jié)點(diǎn)最少需要哪幾個域，data必須的，down、right把線畫下去，好像不需要別的了。再看看表頭節(jié)點(diǎn)，由于是鏈表的表頭節(jié)點(diǎn)，所以就和后邊的節(jié)點(diǎn)一樣了。然后，行鏈表和列鏈表的表頭節(jié)點(diǎn)實(shí)際上也各構(gòu)成了一個鏈表，我們給他們添加一個公有的表頭節(jié)點(diǎn)。***，通過指向這個行列鏈表表頭構(gòu)成的鏈表的公有的表頭節(jié)點(diǎn)的指針，我們就可以訪問稀疏矩陣了。

　　好像和書上的不一樣——非零元節(jié)點(diǎn)沒了指示位置的I、j，實(shí)際上，對于確定非零元在矩陣中的位置，I、j不是必須的，看著圍棋盤你就會很清楚。但是很不幸，不是把他們存起來就萬事大吉了，最起碼，必須考慮加法和乘法的效率，請你想想如果用上面的那種結(jié)構(gòu)，如何完成。

　　如果你細(xì)想想，就會發(fā)現(xiàn)，非零元節(jié)點(diǎn)如果沒有指示位置的域，那么做加法和乘法時，為了確定節(jié)點(diǎn)的位置，每次都要遍歷行和列的鏈表。因此，為了運(yùn)算效率，這個域是必須的。為了看出十字鏈表和單鏈表的差異，我從單鏈表派生出十字鏈表，這需要先定義一種新的結(jié)構(gòu)，如下：

class MatNode  
{  
public:  
int data;  
int row, col;  
union { Node<MatNode＞ *down; List<MatNode＞ *downrow; };  
}; 

　　另外，由于這樣的十字鏈表是由多條單鏈表拼起來的，為了訪問每條單鏈表的保護(hù)成員，要聲明十字鏈表類為單鏈表類的友元。即在class List的聲明中添加friend class Matrix;

#p#

　　稀疏矩陣的定義和實(shí)現(xiàn)

#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 << "輸入矩陣行數(shù)："; cin ＞＞ row; }  
if (!col) { cout << "輸入矩陣列數(shù)："; cin ＞＞ col; }  
if (!num) { cout << "輸入非零個數(shù)："; cin ＞＞ num; }  
if (!row || !col || !num) return;  
cout << endl << "請按順序輸入各個非零元素，以列序?yàn)橹鳎斎?表示本列結(jié)束" << endl;  
int i, j, k, v;//i行數(shù) j列數(shù) 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 << "行數(shù)："; 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 

　　【說明】對于十字鏈表來說，只要記住對每個節(jié)點(diǎn)的操作，要同時考慮它的兩個指針域，那么，各種算法的理解都不是很難。比如說矩陣加法，“兩個矩陣相加和兩個一元多項(xiàng)式相加極為相似，所不同的是一元多項(xiàng)式只有一個變元(指數(shù)項(xiàng))，而矩陣中每個非零元有兩個變元(行值和列值)，每個節(jié)點(diǎn)既在行表中又在列表中，致使插入和刪除節(jié)點(diǎn)時指針的修改稍為復(fù)雜，故需要更多的輔助指針。”(《數(shù)據(jù)結(jié)構(gòu)(C語言版)》)其實(shí)private的row等可以放在首行的頭節(jié)點(diǎn)里的，但為了清晰一點(diǎn)(本來就夠亂了)，我把他們單立出來了。另外，很多地方考慮不是很周全，要是不按照注明的要求使用，很容易就會出錯。

【編輯推薦】

1. 1.51 將稀疏矩陣表示為數(shù)組
2. 經(jīng)典四講貫通C++排序之一 插入排序
3. 1.51.1 如何把兩個稀疏矩陣相加
4. 給C++初學(xué)者的50個忠告
5. C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之棧和隊列
6. 程序員必看 c++筆試題匯總