當(dāng)矩陣的非零元個(gè)數(shù)和位置在操作過(guò)程中變化較大時(shí)，就不宜采用順序存儲(chǔ)的結(jié)構(gòu)來(lái)表示三元組的線性表了。因此，在這種情況下，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組更為恰當(dāng)。十字鏈表就是能夠?qū)崿F(xiàn)這樣功能的一種數(shù)據(jù)結(jié)構(gòu)。

在十字鏈表中，每個(gè)非零元可以用一個(gè)包含5個(gè)域的結(jié)點(diǎn)表示。其中i、j和e這3個(gè)域分別表示該非零元所在的行、列和非零元的值，向右域right用來(lái)鏈接同一行中下一個(gè)非零元，而向下域down用來(lái)鏈接同一列中下一個(gè)非零元。同一行的非零元通過(guò)right域鏈接成一個(gè)線性鏈表，同一列的非零元通過(guò)down域鏈接成一個(gè)線性鏈表。每個(gè)非零元既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)，整個(gè)矩陣通過(guò)這樣的結(jié)構(gòu)形成了一個(gè)十字交叉的鏈表。

稀疏矩陣的十字鏈表類型可以描述如下：

下面是建立稀疏矩陣十字鏈表的算法描述：

給出一個(gè)稀疏矩陣，請(qǐng)將其存儲(chǔ)到一個(gè)十字鏈表中，并將存儲(chǔ)完畢的矩陣輸出。

輸入的第一行是兩個(gè)整數(shù)r和c（r<200, c<200, r*c <= 12500），分別表示一個(gè)包含很多0的稀疏矩陣的行數(shù)和列數(shù)。接下來(lái)有r行，每行有c個(gè)整數(shù)，用空格隔開(kāi)，表示稀疏矩陣的各個(gè)元素。

輸出讀入的矩陣。輸出共有r行，每行有c個(gè)整數(shù)，每個(gè)整數(shù)后輸出一個(gè)空格。請(qǐng)注意行尾輸出換行。