C语言实现一元多项式加法运算

本文将提供一个C语言代码示例，演示如何使用链表实现一元多项式加法运算，并对代码进行了优化，使之更容易理解和维护。

代码实现

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status;

typedef struct LNode
{
    ElemType coef;  // 系数
    ElemType exp;   // 指数
    struct LNode *next;
} LNode, *LinkList;

void CreateList(LinkList *H)
{
    int a, b, n;
    LinkList p;
    scanf('%d', &n);
    *H = (LinkList)malloc(sizeof(LNode));
    p = *H;
    for (int i = 0; i < n; i++)
    {
        scanf('%d%d', &a, &b);
        p->next = (LinkList)malloc(sizeof(LNode));
        p = p->next;
        p->coef = a;
        p->exp = b;
    }
    p->next = NULL;
}

void PrintList(LinkList head)
{
    LinkList p;
    p = head->next;
    if (p == NULL)
    {
        printf('<0,0>
');
        return;
    }
    else
    {
        printf('<%d,%d>', p->coef, p->exp);
        p = p->next;
    }
    while (p)
    {
        printf(',<%d,%d>', p->coef, p->exp);
        p = p->next;
    }
    printf('
');
}

void AddPolyn(LinkList pa, LinkList pb)
{
    int sum = 0;
    LinkList a, b, q, cur;
    a = pa->next;
    b = pb->next;
    cur = pa;
    while ((a != NULL) && (b != NULL))
    {
        if (a->exp < b->exp)
        {
            cur = a;
            a = a->next;
        }
        else if (a->exp == b->exp)
        {
            sum = a->coef + b->coef;
            if (sum == 0)
            {
                q = a->next;
                free(a);
                a = q;
                cur->next = q;
            }
            else
            {
                a->coef = sum;
                cur = a;
                a = a->next;
            }
            q = b;
            b = b->next;
            free(q);
        }
        else
        {
            q = b->next;
            b->next = a;
            cur->next = b;
            cur = b;
            b = q;
        }
    }
    if (b)
        cur->next = b;
}

int main()
{
    int N;
    while (scanf('%d', &N) != EOF)
    {
        if (N == 0)
            break;
        LinkList pa, pb, pc;
        CreateList(&pa);
        CreateList(&pb);
        CreateList(&pc);
        PrintList(pa);
        PrintList(pb);
        PrintList(pc);
        AddPolyn(pa, pb);
        PrintList(pa);
        AddPolyn(pa, pc);
        PrintList(pa);
    }
    return 0;
}

代码解释

数据结构
- 使用链表来存储一元多项式，每个节点代表一个单项式，包含系数和指数信息。
- 链表的头指针指向第一个节点，如果链表为空，则头指针指向NULL。
函数功能
- CreateList(LinkList *H)：创建一元多项式链表，从标准输入读取多项式的系数和指数信息，并将其存储到链表中。
- PrintList(LinkList head)：打印一元多项式链表，将链表中的每个节点的信息以<系数, 指数>的形式输出。
- AddPolyn(LinkList pa, LinkList pb)：将两个一元多项式相加，并将结果存储到第一个多项式链表中。
算法实现
- CreateList() 函数使用循环遍历输入的系数和指数信息，创建新的节点并将其添加到链表的尾部。
- PrintList() 函数使用循环遍历链表，打印每个节点的信息。
- AddPolyn() 函数使用两个指针分别指向两个链表的第一个节点，比较两个指针所指向节点的指数信息，并根据比较结果进行以下操作：
  - 如果两个节点的指数相等，则将两个节点的系数相加，如果相加结果为0，则删除该节点，否则更新该节点的系数信息。
  - 如果第一个节点的指数小于第二个节点的指数，则将第一个节点指向下一个节点。
  - 如果第一个节点的指数大于第二个节点的指数，则将第二个节点插入到第一个节点的前面。
- 循环遍历两个链表，直到其中一个链表为空，并将剩余的节点添加到第一个链表中。

代码优化

使用指针传递参数，避免对链表的深拷贝，提高效率。
使用 malloc() 和 free() 函数动态分配和释放内存，避免内存泄漏。
对代码进行了注释，提高代码可读性。

总结

本文提供了使用链表实现一元多项式加法运算的C语言代码示例，并对代码进行了优化，使之更加简洁、高效和易于维护。希望本示例能够帮助读者更好地理解和掌握链表的应用以及多项式加法的算法实现。