C语言实现单链表存储多项式相加算法

本文介绍了使用C语言实现单链表存储多项式并进行相加运算的算法。代码示例清晰易懂，并包含了创建节点、读入多项式、输出多项式、多项式相加等功能。

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

// 定义多项式节点结构体
typedef struct PolynomialNode {
    float coef; // 系数
    int exp; // 指数
    struct PolynomialNode *next; // 下一个节点指针
} PolynomialNode, *Polynomial;

// 创建多项式节点
PolynomialNode* createNode(float coef, int exp) {
    PolynomialNode *node = (PolynomialNode*)malloc(sizeof(PolynomialNode));
    node->coef = coef;
    node->exp = exp;
    node->next = NULL;
    return node;
}

// 释放多项式链表内存
void freePolynomial(Polynomial poly) {
    Polynomial p = poly;
    while (p) {
        Polynomial temp = p->next;
        free(p);
        p = temp;
    }
}

// 读入多项式
Polynomial readPolynomial() {
    int n;
    float coef;
    int exp;
    Polynomial head = createNode(0, 0); // 带头节点
    Polynomial tail = head; // 尾指针
    scanf('%d', &n);
    while (n--) {
        scanf('%f %d', &coef, &exp);
        PolynomialNode *node = createNode(coef, exp);
        tail->next = node;
        tail = node;
    }
    return head;
}

// 输出多项式
void printPolynomial(Polynomial poly) {
    Polynomial p = poly->next;
    while (p) {
        printf('%.1f %d ', p->coef, p->exp);
        p = p->next;
    }
    printf('\n');
}

// 多项式相加
Polynomial addPolynomial(Polynomial poly1, Polynomial poly2) {
    Polynomial head = createNode(0, 0); // 带头节点
    Polynomial tail = head; // 尾指针
    Polynomial p1 = poly1->next;
    Polynomial p2 = poly2->next;
    while (p1 && p2) {
        if (p1->exp > p2->exp) {
            tail->next = createNode(p1->coef, p1->exp);
            tail = tail->next;
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            tail->next = createNode(p2->coef, p2->exp);
            tail = tail->next;
            p2 = p2->next;
        } else {
            float coef = p1->coef + p2->coef;
            if (coef != 0) {
                tail->next = createNode(coef, p1->exp);
                tail = tail->next;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    while (p1) {
        tail->next = createNode(p1->coef, p1->exp);
        tail = tail->next;
        p1 = p1->next;
    }
    while (p2) {
        tail->next = createNode(p2->coef, p2->exp);
        tail = tail->next;
        p2 = p2->next;
    }
    return head;
}

int main() {
    Polynomial ha, hb, hc;
    ha = readPolynomial();
    hb = readPolynomial();
    hc = addPolynomial(ha, hb);
    printPolynomial(hc);
    freePolynomial(ha);
    freePolynomial(hb);
    freePolynomial(hc);
    return 0;
}

代码说明：

结构体定义: 定义了PolynomialNode结构体，用于存储多项式节点的信息，包括系数coef、指数exp以及指向下一个节点的指针next。
创建节点: createNode函数用于创建新的多项式节点，并初始化其系数、指数和下一个节点指针。
释放链表内存: freePolynomial函数用于释放多项式链表所占用的内存空间，防止内存泄漏。
读入多项式: readPolynomial函数从标准输入流中读入多项式，并将每个项存储在一个新的节点中。
输出多项式: printPolynomial函数将多项式以系数和指数的形式输出到标准输出流。
多项式相加: addPolynomial函数实现了两个多项式的相加操作。它根据两个多项式的指数进行比较，分别处理三种情况：
- 指数相等：将两个项的系数相加，如果结果不为零，则创建新的节点添加到结果链表中。
- 指数不相等：将指数较大的项添加到结果链表中。
主函数: main函数演示了如何使用以上函数进行多项式相加。

代码运行结果：

首先输入第一个多项式项数，然后输入每一项的系数和指数，用空格隔开，以回车结束。输入第二个多项式，方式与第一个相同。最后程序会输出两个多项式相加后的结果。

示例：

输入：

输出：

4.0 3 1.0 2 2.0 1 4.0 0

总结：

该算法使用单链表存储多项式，并实现了多项式相加的功能。该算法简洁高效，易于理解和实现。