矩陣之間能夠進行加法運算的前提條件是：各矩陣的行數和列數必須相等。

在行數和列數都相等的情況下，矩陣相加的結果就是矩陣中對應位置的值相加所組成的矩陣，例如：

采用鏈式存儲結構存儲稀疏矩陣三元組的方法，稱為“十字。

十字鏈表法表示矩陣

例如，用十字鏈表法表示矩陣 A ，為：

圖2 矩陣用十字鏈表法表示

由此可見，采用十字鏈表表示矩陣時，矩陣的每一行和每一個列都可以看作是一個單獨的鏈表，而之所以能夠表示矩陣，是因為行鏈表和列鏈表都分別存儲在各自的

圖 2 中：存儲行鏈表的數組稱為?rhead 數組；存儲列鏈表的數組稱為?chead 數組。

十字鏈表中的結點

從圖2中的十字鏈表表示矩陣的例子可以看到，十字鏈表中的結點由 5 部分組成：

圖3 十字鏈表中的結點

指針域A存儲的是矩陣中結點所在列的下一個結點的地址(稱為?“down域”)；

指針域B存儲的是矩陣中該結點所在行的下一個結點的地址(稱為?“right域”)；

用結構體自定義表示為：

typedef struct OLNode

{

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

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

}OLNode,*OLink;

十字鏈表的結構

使用十字鏈表表示一個完整的矩陣，在了解矩陣中各結點的結構外，還需要存儲矩陣的行數、列數以及非 0 元素的個數，另外，還需要將各結點鏈接成的鏈表存儲在數組中。

所以，采用結構體自定義十字鏈表的結構，為：

typedef struct

{

OLink *rhead,*chead; //存放各行和列鏈表頭指針的數組

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

}CrossList;

十字鏈表存儲矩陣三元組

由于三元組存儲的是該數據元素的行標、列標和數值，所以，通過行標和列標，就能在十字鏈表中唯一確定一個位置。

判斷方法為：在同一行中通過列標來判斷位置；在同一列中通過行標來判斷位置。

首先判斷該數據元素 A(例如三元組為：(i，j，k))所在行的具體位置：

如果 A 的列標 j 值比該行第一個非 0 元素 B 的 j 值小，說明該數據元素在元素 B 的左側，這時 A 就成為了該行第一個非0元素(也適用于當該行沒有非 0 元素的情況，可以一并討論)

如果 A 的列標 j 比該行第一個非 0 元素 B 的 j 值大，說明 A 在 B 的右側，這時，就需要遍歷該行鏈表，找到插入位置的前一個結點，進行插入。

對應行鏈表的位置確定之后，判斷數據元素 A 在對應列的位置：

如果 A 的行標比該列第一個非 0 元素 B 的行標 i 值還小，說明 A 在 B 的上邊，這時 A 就成了該列第一個非 0 元素。(也適用于該列沒有非 0 元素的情況)

反之，說明 A 在 B 的下邊，這時就需要遍歷該列鏈表，找到要插入位置的上一個數據元素，進行插入。

實現代碼：

//創建系數矩陣M,采用十字鏈表存儲表示

CrossList CreateMatrix_OL(CrossList M)

{

int m,n,t;

int i,j,e;

OLNode *p,*q;//定義輔助變量

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)) //輸入三元組 直到行為0結束

{

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

{

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

exit(0); //動態生成p

}

p->i=i;

p->j=j;

p->e=e; //初始化p

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->jright);

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->idown);

p->down=q->down;

q->down=p;

}

}

return M;

}

十字鏈表解決矩陣相加問題

在解決 “將矩陣 B 加到矩陣 A ” 的問題時，由于采用的是十字鏈表法存儲矩陣的三元組，所以在相加的過程中，針對矩陣 B 中每一個非 0 元素，需要判斷在矩陣 A 中相對應的位置，有三種情況：

提取到的 B 中的三元組在 A 相應位置上沒有非 0 元素，此時直接加到矩陣 A 該行鏈表的對應位置上；

提取到的 B 中三元組在 A 相應位置上有非 0 元素，且相加不為 0 ，此時只需要更改 A 中對應位置上的三元組的值即可；

提取到的 B 中三元組在 A 響應位置上有非 0 元素，但相加為 0 ，此時需要刪除矩陣 A 中對應結點。

提示：算法中，只需要逐個提取矩陣 B 中的非 0 元素，然后判斷矩陣 A 中對應位置上是否有非 0 元素，根據不同的情況，相應作出處理。

設指針 pa 和 pb 分別表示矩陣 A 和矩陣 B 中同一行中的結點( pb 和 pa 都是從兩矩陣的第一行的第一個非0元素開始遍歷)，針對上面的三種情況，細分為 4 種處理過程(第一種情況下有兩種不同情況)：

當 pa 結點的列值 j > pb 結點的列值 j 或者 pa == NULL (說明矩陣 A 該行沒有非 0 元素)，兩種情況下是一個結果，就是將 pb 結點插入到矩陣 A 中。

當 pa 結點的列值 j < pb 結點的列值 j ，說明此時 pb 指向的結點位置比較靠后，此時需要移動 pa 的位置，找到離 pb 位置最近的非 0 元素，然后在新的 pa 結點的位置后邊插入；

當 pa 的列值 j == pb 的列值 j， 且兩結點的值相加結果不為 0 ，只需要更改 pa 指向的結點的值即可；

當 pa 的列值 j == pb 的列值 j ，但是兩結點的值相加結果為 0 ，就需要從矩陣 A 的十字鏈表中刪除 pa 指向的結點。

實現代碼：

CrossList AddSMatrix(CrossList M,CrossList N){

OLNode * pa,*pb;//新增的兩個用于遍歷兩個矩陣的結點

OLink * hl=(OLink*)malloc(M.nu*sizeof(OLink));//用于存儲當前遍歷的行為止以上的區域每一個列的最后一個非0元素的位置。

OLNode * pre=NULL;//用于指向pa指針所在位置的此行的前一個結點

//遍歷初期，首先要對hl數組進行初始化，指向每一列的第一個非0元素

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

hl[j]=M.chead[j];

}

//按照行進行遍歷

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

//遍歷每一行以前，都要pa指向矩陣M當前行的第一個非0元素；指針pb也是如此，只不過遍歷對象為矩陣N

pa=M.rhead[i];

pb=N.rhead[i];

//當pb為NULL時，說明矩陣N的當前行的非0元素已經遍歷完。

while (pb!=NULL) {

//創建一個新的結點，每次都要復制一個pb結點，但是兩個指針域除外。(復制的目的就是排除指針域的干擾)

OLNode * p=(OLNode*)malloc(sizeof(OLNode));

p->i=pb->i;

p->j=pb->j;

p->e=pb->e;

p->down=NULL;

p->right=NULL;

//第一種情況

if (pa==NULL||pa->j>pb->j) {

//如果pre為NULL，說明矩陣M此行沒有非0元素

if (pre==NULL) {

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

}else{//由于程序開始時pre肯定為NULL，所以，pre指向的是第一個p的位置，在后面的遍歷過程中，p指向的位置是逐漸向后移動的，所有，pre肯定會在p的前邊

pre->right=p;

}

p->right=pa;

pre=p;

//在鏈接好行鏈表之后，鏈接到對應列的列鏈表中的相應位置

if (!M.chead[p->j]||M.chead[p->j]->i>p->i) {

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

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

}else{

p->down=hl[p->j]->down;

hl[p->j]->down=p;

}

//更新hl中的數據

hl[p->j]=p;

}else{

//第二種情況，只需要移動pa的位置，繼續判斷pa和pb的位置，一定要有continue

if (pa->jj) {

pre=pa;

pa=pa->right;

continue;

}

//第三、四種情況，當行標和列標都想等的情況下，需要討論兩者相加的值的問題

if (pa->j==pb->j) {

pa->e+=pb->e;

//如果為0，摘除當前結點，并釋放所占的空間

if (pa->e==0) {

if (pre==NULL) {

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

}else{

pre->right=pa->right;

}

p=pa;

pa=pa->right;

if (M.chead[p->j]==p) {

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

}else{

hl[p->j]->down=p->down;

}

free(p);

}

}

}

pb=pb->right;

}

}

//用于輸出矩陣三元組的功能函數

display(M);

return M;

}

完整代碼演示

#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);

CrossList AddSMatrix(CrossList M,CrossList N);

void display(CrossList M);

void main()

{

CrossList M,N;

printf("輸入測試矩陣M:\n");

M=CreateMatrix_OL(M);

printf("輸入測試矩陣N:\n");

N=CreateMatrix_OL(N);

M=AddSMatrix(M,N);

printf("矩陣相加的結果為:\n");

display(M);

}

CrossList CreateMatrix_OL(CrossList M)

{

int m,n,t;

int i,j,e;

OLNode *p,*q;

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->jright);

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->idown);

p->down=q->down;

q->down=p;

}

}

return M;

}

CrossList AddSMatrix(CrossList M,CrossList N){

OLNode * pa,*pb;

OLink * hl=(OLink*)malloc(M.nu*sizeof(OLink));

OLNode * pre=NULL;

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

hl[j]=M.chead[j];

}

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

pa=M.rhead[i];

pb=N.rhead[i];

while (pb!=NULL) {

OLNode * p=(OLNode*)malloc(sizeof(OLNode));

p->i=pb->i;

p->j=pb->j;

p->e=pb->e;

p->down=NULL;

p->right=NULL;

if (pa==NULL||pa->j>pb->j) {

if (pre==NULL) {

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

}else{

pre->right=p;

}

p->right=pa;

pre=p;

if (!M.chead[p->j]||M.chead[p->j]->i>p->i) {

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

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

}else{

p->down=hl[p->j]->down;

hl[p->j]->down=p;

}

hl[p->j]=p;

}else{

if (pa->jj) {

pre=pa;

pa=pa->right;

continue;

}

if (pa->j==pb->j) {

pa->e+=pb->e;

if (pa->e==0) {

if (pre==NULL) {

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

}else{

pre->right=pa->right;

}

p=pa;

pa=pa->right;

if (M.chead[p->j]==p) {

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

}else{

hl[p->j]->down=p->down;

}

free(p);

}

}

}

pb=pb->right;

}

}

display(M);

return M;

}

void display(CrossList M){

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

printf("M:\n---------------------\ni\tj\te\n---------------------\n");

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;

}

}

}

}

運行結果：

輸入測試矩陣M:

3 3 3

1 2 1

2 1 1

3 3 1

0 0 0

輸入測試矩陣N:

3 3 4

1 2 -1

1 3 1

2 3 1

3 1 1

0 0 0

矩陣相加的結果為:

輸出測試矩陣:

M:

---------------------

i j e

---------------------

2 1 1

3 1 1

1 3 1

2 3 1

3 3 1

總結

使用十字鏈表法解決稀疏矩陣的壓縮存儲的同時，在解決矩陣相加的問題中，對于某個單獨的結點來說，算法的

總結

以上是生活随笔為你收集整理的十字链表c语言实验报告,矩阵加法（基于十字链表）及C语言代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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