對于壓縮存儲稀疏矩陣，無論是使用

圖 1 十字鏈表示意圖

可以看到，使用十字鏈表壓縮存儲稀疏矩陣時，矩陣中的各行各列都各用一各鏈表存儲，與此同時，所有行鏈表的表頭存儲到一個數組(rhead)，所有列鏈表的表頭存儲到另一個數組(chead)中。

因此，各個鏈表中節點的結構應如圖 2 所示:

圖 2 十字鏈表的節點結構

兩個指針域分別用于鏈接所在行的下一個元素以及所在列的下一個元素。

鏈表中節點的 C 語言代碼表示應為：

typedef struct OLNode{

int i,j;//元素的行標和列標

int data;//元素的值

struct OLNode * right,*down;//兩個指針域

}OLNode;

同時，表示十字鏈表結構的 C 語言代碼應為：

#include

#include

typedef struct OLNode

{

int i, j, e; //矩陣三元組i代表行 j代表列 e代表當前位置的數據

struct OLNode *right, *down; //指針域 右指針 下指針

}OLNode, *OLink;

typedef struct

{

OLink *rhead, *chead; //行和列鏈表頭指針

int mu, nu, tu; //矩陣的行數,列數和非零元的個數

}CrossList;

CrossList CreateMatrix_OL(CrossList M);

void display(CrossList M);

int main()

{

CrossList M;

M.rhead = NULL;

M.chead = NULL;

M = CreateMatrix_OL(M);

printf("輸出矩陣M:\n");

display(M);

return 0;

}

CrossList CreateMatrix_OL(CrossList M)

{

int m, n, t;

int i, j, e;

OLNode *p, *q;

printf("輸入矩陣的行數、列數和非0元素個數：");

scanf("%d%d%d", &m, &n, &t);

M.mu = m;

M.nu = n;

M.tu = t;

if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))

{

printf("初始化矩陣失敗");

exit(0);

}

for (i = 1; i <= m; i++)

{

M.rhead[i] = NULL;

}

for (j = 1; j <= n; j++)

{

M.chead[j] = NULL;

}

for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) {

if (!(p = (OLNode*)malloc(sizeof(OLNode))))

{

printf("初始化三元組失敗");

exit(0);

}

p->i = i;

p->j = j;

p->e = e;

//鏈接到行的指定位置

if (NULL == M.rhead[i] || M.rhead[i]->j > j)

{

p->right = M.rhead[i];

M.rhead[i] = p;

}

else

{

for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);

p->right = q->right;

q->right = p;

}

//鏈接到列的指定位置

if (NULL == M.chead[j] || M.chead[j]->i > i)

{

p->down = M.chead[j];

M.chead[j] = p;

}

else

{

for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);

p->down = q->down;

q->down = p;

}

}

return M;

}

void display(CrossList M) {

for (int i = 1; i <= M.nu; i++)

{

if (NULL != M.chead[i])

{

OLink p = M.chead[i];

while (NULL != p)

{

printf("%d\t%d\t%d\n", p->i, p->j, p->e);

p = p->down;

}

}

}

}

運行結果：

輸入矩陣的行數、列數和非0元素個數：3 3 3

2 2 3

2 3 4

3 2 5

0 0 0

輸出矩陣M:

2?????? 2?????? 3

3?????? 2?????? 5

2?????? 3?????? 4

總結

以上是生活随笔為你收集整理的十字链表表示矩阵c语言,十字链表法，十字链表压缩存储稀疏矩阵详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。