匿名使用者 2013-09-13

十字連結串列的構成用連結串列模擬矩陣的行（或者列，這可以根據個人喜好來定），然後，再構造代表列的連結串列，將每一行中的元素節點插入到對應的列中去。十字連結串列的邏輯結構就像是一個圍棋盤（沒見過，你就想一下蒼蠅拍，這個總見過吧），而非零元就好像是在棋盤上放的棋子，總共佔的空間就是，確定那些線的表頭節點和那些棋子代表的非零元節點。最後，我們用一個指標指向這個棋盤，這個指標就代表了這個稀疏矩陣。 十字連結串列十字連結串列（Orthogonal List）是有向圖的另一種鏈式儲存結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種連結串列。在十字連結串列中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。

十字連結串列之於有向圖，類似於鄰接表之於無向圖。 舉例#include

#include

/*十字連結串列的結構型別定義如下：*/

typedef struct OLNode

{

int row，col； /*非零元素的行和列下標*/

int value；

struct OLNode *right； /*非零元素所在行表、列表的後繼鏈域*/

struct OLNode *down；

}OLNode， *OLink；

typedef struct

{

OLink *row_head； /*行、列連結串列的頭指標向量*/

OLink *col_head；

int m，n，len； /*稀疏矩陣的行數、列數、非零元素的個數*/

}CrossList；

/*建立稀疏矩陣的十字連結串列的演算法*/

void CreateCrossList（CrossList *M）

{

int m， n， t， i， j， e；

OLNode* p；

OLNode* q；

/*採用十字連結串列儲存結構，建立稀疏矩陣M*/

scanf（“%d%d%d”， &m，&n，&t）； /*輸入M的行數，列數和非零元素的個數*/

M->m=m；

M->n=n；

M->len=t；

if（！（M->row_head=（OLink *）malloc（（m+1）*sizeof（OLink））））

exit（OVERFLOW）；

if（！（M->col_head=（OLink * ）malloc（（n+1）*sizeof（OLink））））

exit（OVERFLOW）；

/*初始化行、列頭指標向量，各行、列連結串列為空的連結串列*/

for（int h=0； h

{

M->row_head［h］ = NULL；

}

for（int t=0； t

{

M->col_head［t］ = NULL；

}

for（scanf（“%d%d%d”， &i，&j，&e）；i！=0；scanf（“%d%d%d”， &i，&j，&e））

{

if（！（p=（OLNode *）malloc（sizeof（OLNode））））

exit（OVERFLOW）；

p->row=i；

p->col=j；

p->value=e； /*生成結點*/

if（M->row_head［i］==NULL）

M->row_head［i］=p；

else

{

/*尋找行表中的插入位置*/

for（q=M->row_head［i］；q->right&&q->right->colright）； /*空迴圈體*/

p->right=q->right；

q->right=p； /*完成插入*/

}

if（M->col_head［j］==NULL）

M->col_head［j］=p；

else

{

/*尋找列表中的插入位置*/

for（q=M->col_head［j］；q->down&&q->down->rowdown）； /*空迴圈體*/

p->down=q->down；

q->down=p； /*完成插入*/

}

}

}