十字链表实现两个稀疏矩阵相加的C语言代码

下面是十字链表实现两个稀疏矩阵相加的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;
}