十字链表实现两个稀疏矩阵相加的C语言代码
时间: 2024-05-08 17:18:36 浏览: 110
十字链表-稀疏矩阵 C++ 代码
5星 · 资源好评率100%
下面是十字链表实现两个稀疏矩阵相加的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000
typedef int Status;
typedef struct OLNode
{
int i, j; //非零元素的行列下标
int e; //非零元素的值
struct OLNode *right, *down; //右指针和下指针
} OLNode, *OLink;
typedef struct
{
OLink *rhead, *chead; //行指针和列指针
int m, n, len; //稀疏矩阵的行数、列数和非零元素个数
} CrossList;
//十字链表按行插入新节点
Status InsertOLNodeByRow(OLink *rhead, OLink *chead, int i, int j, int e)
{
OLink p = *rhead, pre = NULL, q = NULL;
q = (OLink)malloc(sizeof(OLNode));
q->i = i;
q->j = j;
q->e = e;
while (p && p->i < i)
{
pre = p;
p = p->down;
}
if (p && p->i == i && p->j < j)
{
while (p && p->j < j && p->i == i)
{
pre = p;
p = p->right;
}
}
if (p && p->i==i && p->j==j)
{
p->e += e;
free(q);
return OK;
}
q->down = p;
if (pre) pre->down = q; else *rhead = q;
p = chead[j];
pre = NULL;
while (p && p->j<j)
{
pre = p;
p = p->right;
}
q->right = p;
if (pre) pre->right = q; else chead[j] = q;
return OK;
}
//创建稀疏矩阵
Status CreateSMatrix(CrossList *M)
{
int i, j, k, e;
printf("请输入稀疏矩阵的行数、列数和非零元素个数:");
scanf("%d %d %d", &M->m, &M->n, &M->len);
M->rhead = (OLink*)malloc((M->m+1)*sizeof(OLink));
M->chead = (OLink*)malloc((M->n+1)*sizeof(OLink));
for (i=0; i<=M->m; i++) M->rhead[i] = NULL;
for (i=0; i<=M->n; i++) M->chead[i] = NULL;
printf("请依次输入%d个非零元素及其行列下标:\n", M->len);
for (k=1; k<=M->len; k++)
{
printf("第%d个:", k);
scanf("%d %d %d",&i,&j,&e);
if (InsertOLNodeByRow(&(M->rhead[i]), M->chead, i, j, e) != OK)
{
printf("插入结点失败!\n");
return ERROR;
}
}
return OK;
}
//按十字链表格式输出稀疏矩阵
void PrintSMatrix(CrossList M)
{
int i, j;
OLink p = NULL;
printf("稀疏矩阵的行数、列数和非零元素个数分别为:%d %d %d\n", M.m, M.n, M.len);
for (i=1; i<=M.m; i++)
{
p = M.rhead[i];
for (j=1; j<=M.n; j++)
{
if (p && p->j == j)
{
printf("%d\t", p->e);
p = p->right;
}
else
{
printf("0\t");
}
}
printf("\n");
}
}
//稀疏矩阵相加,结果存储在M3中
Status AddSMatrix(CrossList M1, CrossList M2, CrossList *M3)
{
if (M1.m != M2.m || M1.n != M2.n)
{
printf("两个矩阵的行数或列数不等,无法相加!\n");
return ERROR;
}
int i, j;
int e;
*M3 = M1;
M3->rhead = (OLink*)malloc((M1.m+1)*sizeof(OLink));
M3->chead = (OLink*)malloc((M1.n+1)*sizeof(OLink));
for (i=0; i<=M1.m; i++) M3->rhead[i] = NULL;
for (i=0; i<=M1.n; i++) M3->chead[i] = NULL;
OLink p = NULL, q = NULL;
for (i=1; i<=M1.m; i++)
{
p = M1.rhead[i];
q = M2.rhead[i];
while (p && q)
{
if (p->j < q->j)
{
if (InsertOLNodeByRow(&(M3->rhead[i]), M3->chead, p->i, p->j, p->e) != OK)
{
printf("插入结点失败!\n");
return ERROR;
}
p = p->right;
}
else if (p->j > q->j)
{
if (InsertOLNodeByRow(&(M3->rhead[i]), M3->chead, q->i, q->j, q->e) != OK)
{
printf("插入结点失败!\n");
return ERROR;
}
q = q->right;
}
else
{
e = p->e + q->e;
if (InsertOLNodeByRow(&(M3->rhead[i]), M3->chead, p->i, p->j, e) != OK)
{
printf("插入结点失败!\n");
return ERROR;
}
p = p->right;
q = q->right;
}
}
while (p)
{
if (InsertOLNodeByRow(&(M3->rhead[i]), M3->chead, p->i, p->j, p->e) != OK)
{
printf("插入结点失败!\n");
return ERROR;
}
p = p->right;
}
while (q)
{
if (InsertOLNodeByRow(&(M3->rhead[i]), M3->chead, q->i, q->j, q->e) != OK)
{
printf("插入结点失败!\n");
return ERROR;
}
q = q->right;
}
}
return OK;
}
int main()
{
CrossList M1, M2, M3;
CreateSMatrix(&M1);
CreateSMatrix(&M2);
printf("第一个稀疏矩阵:\n");
PrintSMatrix(M1);
printf("第二个稀疏矩阵:\n");
PrintSMatrix(M2);
AddSMatrix(M1, M2, &M3);
printf("相加后的稀疏矩阵:\n");
PrintSMatrix(M3);
return 0;
}
```
阅读全文