數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)(C)稀疏矩陣(十字鏈表1)

1、數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（）一稀疏矩陣（十字鏈表【】）（原作）轉(zhuǎn)自D先說(shuō)說(shuō)什么叫稀疏矩陣。你說(shuō)，這個(gè)問(wèn)題很簡(jiǎn)單嗎，那你一定不知道中國(guó)學(xué)術(shù)界的嘴皮子仗，對(duì)一個(gè)字眼的“摳”將會(huì)導(dǎo)致兩種相反的結(jié)論。這是清華2000年的一道考研題：“表示一個(gè)有1000個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否稀疏矩陣？”如果你是個(gè)喜歡研究出題者心理活動(dòng)的人，你可以看出這里有兩個(gè)陷阱，就是讓明明會(huì)的人答錯(cuò)，我不想說(shuō)出是什么，留給讀者思考。姑且不論清華給的標(biāo)準(zhǔn)答案是什么，那年的參考書(shū)是嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），書(shū)上對(duì)于稀疏矩陣的定義是這樣的：“非零元較零元少（注：原書(shū)下文給出了大致的程度），且分布沒(méi)有一定規(guī)律”

2、，照這個(gè)說(shuō)法，那題的答案應(yīng)該是不一定是稀疏矩陣，因?yàn)榭赡苁翘厥饩仃嚕ǚ橇阍植加幸?guī)律）。自從2002年換參考書(shū)后，很多概念都發(fā)生了變化，最明顯的是從多少開(kāi)始計(jì)數(shù)（0還是1），從而導(dǎo)致的是空樹(shù)的高度變成了1，只有一個(gè)根節(jié)點(diǎn)的樹(shù)高度是0。很不幸的是樹(shù)高的問(wèn)題幾乎年年都考，在你下筆的時(shí)候，總是犯點(diǎn)嘀咕，總不是一朝天子一朝臣吧，會(huì)不會(huì)答案是個(gè)兼容版本？然后，新參考書(shū)帶的習(xí)題集里引用了那道考研題，答案是是稀疏矩陣。你也許會(huì)驚訝這年頭咸魚(yú)都會(huì)游泳了，但這個(gè)答案和書(shū)并不矛盾，因?yàn)樵谶@本黃皮書(shū)里，根本就沒(méi)有什么特殊矩陣，自然就一定是稀疏矩陣了。其實(shí)，這兩本書(shū)在這個(gè)問(wèn)題上也沒(méi)什么原則上的問(wèn)題，C版的是從數(shù)據(jù)結(jié)構(gòu)

3、實(shí)現(xiàn)區(qū)分出特殊矩陣和稀疏矩陣，畢竟他們實(shí)現(xiàn)起來(lái)很不相同；新書(shū)一股腦把非零元少的矩陣都當(dāng)成稀疏矩陣，當(dāng)你按照這種思路做的時(shí)候就會(huì)發(fā)現(xiàn)，各種結(jié)構(gòu)特殊的非零元很少的矩陣，如果用十字鏈表來(lái)儲(chǔ)存的話，比考慮到它的特殊結(jié)構(gòu)得出的特有儲(chǔ)存方法，僅僅是浪費(fèi)了幾個(gè)表頭節(jié)點(diǎn)和一些指針域，再有就是一些運(yùn)算效率的降低。從我個(gè)人角度講，我更喜歡多一些統(tǒng)一，少一些特別，即使?fàn)奚稽c(diǎn)效率；所以在這一點(diǎn)上我贊同新參考書(shū)的做法。而在計(jì)數(shù)起點(diǎn)上，我更喜歡原來(lái)的做法；畢竟，研究數(shù)據(jù)結(jié)構(gòu)要考慮人的思考習(xí)慣，而不是計(jì)算機(jī)喜歡什么；你非得說(shuō)表中的第一個(gè)元素是第0個(gè)，空樹(shù)的高是1，怎么不讓人心里起疙瘩。數(shù)據(jù)結(jié)構(gòu)是人們構(gòu)造算法時(shí)思維和計(jì)算機(jī)

4、實(shí)現(xiàn)的橋梁、中介，它應(yīng)該符合人的思考習(xí)慣，即使在它實(shí)現(xiàn)的時(shí)候內(nèi)部做了某些轉(zhuǎn)換。開(kāi)始廢話了這么多，希望沒(méi)打消了你往下看的心情，好，言歸正傳。這里的十字鏈表是這樣構(gòu)成的：用鏈表模擬矩陣的行（或者列，這可以根據(jù)個(gè)人喜好來(lái)定），然后，再構(gòu)造代表列的鏈表，將每一行中的元素節(jié)點(diǎn)插入到對(duì)應(yīng)的列中去。書(shū)中為了少存幾個(gè)表頭節(jié)點(diǎn)，將行和列的表頭節(jié)點(diǎn)合并到了一起實(shí)際只是省了幾個(gè)指針域，如果行和列數(shù)不等，多余的數(shù)據(jù)域就把這點(diǎn)省出的空間又給用了。這點(diǎn)小動(dòng)作讓我著實(shí)廢了半天勁，個(gè)人感覺(jué)，優(yōu)點(diǎn)不大，缺點(diǎn)不少，不如老老實(shí)實(shí)寫(xiě)得象個(gè)十字鏈表，讓人也好看一些，這是教科書(shū)，目的是教學(xué)。實(shí)在看得暈的人，參閱C版的這部分內(nèi)容，很清晰。

5、我也不會(huì)畫(huà)圖，打個(gè)比方吧：這個(gè)十字鏈表的邏輯結(jié)構(gòu)就像是一個(gè)圍棋盤(pán)（沒(méi)見(jiàn)過(guò)，你就想一下蒼蠅拍，這個(gè)總見(jiàn)過(guò)吧），而非零元就好像是在棋盤(pán)上放的棋子，總共占的空間就是，確定那些線的表頭節(jié)點(diǎn)和那些棋子代表的非零元節(jié)點(diǎn)。最后，我們用一個(gè)指針指向這個(gè)棋盤(pán)，這個(gè)指針就代表了這個(gè)稀疏矩陣。現(xiàn)在，讓我們看看非零元節(jié)點(diǎn)最少需要哪幾個(gè)域，data必須的，down、right把線畫(huà)下去，好像不需要?jiǎng)e的了。再看看表頭節(jié)點(diǎn)，由于是鏈表的表頭節(jié)點(diǎn)，所以就和后邊的節(jié)點(diǎn)一樣了。然后，行鏈表和列鏈表的表頭節(jié)點(diǎn)實(shí)際上也各構(gòu)成了一個(gè)鏈表，我們給他們添加一個(gè)公有的表頭節(jié)點(diǎn)。最后，通過(guò)指向這個(gè)行列鏈表表頭構(gòu)成的鏈表的公有的表頭節(jié)點(diǎn)的指針，

6、我們就可以訪問(wèn)稀疏矩陣了。好像和書(shū)上的不一樣一一非零元節(jié)點(diǎn)沒(méi)了指示位置的I、j，實(shí)際上，對(duì)于確定非零元在矩陣中的位置，I、j不是必須的，看著圍棋盤(pán)你就會(huì)很清楚。但是很不幸，不是把他們存起來(lái)就萬(wàn)事大吉了，最起碼，必須考慮加法和乘法的效率，請(qǐng)你想想如果用上面的那種結(jié)構(gòu)，如何完成。考慮到到這里已經(jīng)寫(xiě)了不少字，我將實(shí)現(xiàn)部分放在下篇，今天該休息了。據(jù)結(jié)構(gòu)學(xué)習(xí)()稀疏矩陣(十字鏈表【】)如果你細(xì)想想，就會(huì)發(fā)現(xiàn)，非零元節(jié)點(diǎn)如果沒(méi)有指示位置的域，那么做加法和乘法時(shí)，為了確定節(jié)點(diǎn)的位置，每次都要遍歷行和列的鏈表。因此，為了運(yùn)算效率，這個(gè)域是必須的。為了看出十字鏈表和單鏈表的差異，我從單鏈表派生出十字鏈表，這需要

7、先定義一種新的結(jié)構(gòu)，如下：classMatNodepublic:intdata;introw,col;unionNode*down;List*downrow;另外，由于這樣的十字鏈表是由多條單鏈表拼起來(lái)的，為了訪問(wèn)每條單鏈表的保護(hù)成員，要聲明十字鏈表類為單鏈表類的友元。即在classList的聲明中添加friendclassMatrix;稀疏矩陣的定義和實(shí)現(xiàn)#ifndefMatrix_H#defineMatrix_H#includeList.hclassMatNodepublic:intdata;introw,col;unionNode*down;List*downrow;MatNode(in

8、tvalue=0,Node*p=NULL,inti=0,intj=0):data(value),down(p),row(i),col(j)friendostream&operator(ostream&strm,MatNode&mtn)strm(mtn.row,mtn.col)mtn.data;returnstrm;classMatrix:Listpublic:Matrix():row(0),col(0),num(0)Matrix(introw,intcol,intnum):row(row),col(col),num(num)Matrix()MakeEmpty();voidMakeEmpty()

9、List*q;while(first-data.downrow!=NULL)q=first-data.downrow;first-data.downrow=q-first-data.downrow;deleteq;List:MakeEmpty();row=col=num=0;voidInput()if(!row)coutrow;if(!col)coutcol;if(!num)coutnum;if(!row|!col|!num)return;coutendl請(qǐng)按順序輸入各個(gè)非零元素，以列序?yàn)橹鳎斎?表示本列結(jié)束endl;inti,j,k,v;/i行數(shù)j列數(shù)k個(gè)非零元v非零值Node*p=fir

10、st,*t;List*q;for(j=1;j=col;j+)LastInsert(MatNode(0,NULL,0,j);for(i=1;i=row;i+)q=newList;q-first-data.row=i;p-data.downrow=q;p=q-first;j=1;q=first-data.downrow;First();t=pNext();for(k=0;kcol)break;coutendl輸入第j列非零元素endl;couti;if(irow)j+;k-;q=first-data.downrow;t=pNext();continue;coutv;if(!v)k-;continu

11、e;MatNodematnode(v,NULL,i,j);p=newNode(matnode);t-data.down=p;t=p;while(q-first-data.row!=i)q=q-first-data.downrow;q-LastInsert(t);voidPrint()List*q=first-data.downrow;coutendl;while(q!=NULL)coutfirst-data.downrow;Matrix&Add(Matrix&matB)/初始化賦值輔助變量if(row!=matB.row|col!=matB.col|matB.num=0)return*this;Node*pA,*pB;Node*pAT=newNode*col+1;*qBNode*pBT=newNode*matB.col+1;*qBList*qA=pGetFirst()-data.downrow,matB.pGetFirst()-data.downrow;First();matB.First();for(intj=1;j=col;j+)pATj=pNext();pBTj=matB.pNext();/開(kāi)始for(inti=1;iFirst();qB-First();pA=qA-pNext();pB=qB-pNext();while(pA!=N