C语言链表多项式详解（手把手教你用链表实现多项式加法与存储）

第一步：定义链表节点结构

每个节点代表多项式的一项，包含系数（coef）、指数（exp）和指向下一个节点的指针（next）。

struct PolyNode {    int coef;           // 系数    int exp;            // 指数    struct PolyNode* next;};typedef struct PolyNode PolyNode;  

第二步：创建多项式（尾插法）

我们写一个函数，通过输入系数和指数，逐步构建多项式链表。为了保持指数从高到低排序，我们采用有序插入的方式。

PolyNode* createPolynomial() {    PolyNode* head = NULL;    PolyNode* tail = NULL;    int coef, exp;    printf("请输入多项式的项（系数 指数），输入 0 0 结束：\n");    while (1) {        scanf("%d %d", &coef, &exp);        if (coef == 0 && exp == 0) break;        PolyNode* newNode = (PolyNode*)malloc(sizeof(PolyNode));        newNode->coef = coef;        newNode->exp = exp;        newNode->next = NULL;        if (head == NULL || head->exp < exp) {            // 插入到头部            newNode->next = head;            head = newNode;        } else {            // 找到合适位置插入            PolyNode* curr = head;            while (curr->next != NULL && curr->next->exp > exp) {                curr = curr->next;            }            if (curr->next != NULL && curr->next->exp == exp) {                // 合并同类项                curr->next->coef += coef;                if (curr->next->coef == 0) {                    // 系数为0，删除该项                    PolyNode* temp = curr->next;                    curr->next = temp->next;                    free(temp);                }                free(newNode); // 不需要新节点            } else {                // 插入新节点                newNode->next = curr->next;                curr->next = newNode;            }        }    }    return head;}  

第三步：实现两个多项式相加

多项式加法的核心思想是：指数相同则系数相加，不同则保留原项。我们可以用两个指针分别遍历两个链表，按指数大小合并。

PolyNode* addPolynomials(PolyNode* p1, PolyNode* p2) {    PolyNode* result = NULL;    PolyNode* tail = NULL;    while (p1 != NULL && p2 != NULL) {        PolyNode* newNode = (PolyNode*)malloc(sizeof(PolyNode));        if (p1->exp > p2->exp) {            newNode->coef = p1->coef;            newNode->exp = p1->exp;            p1 = p1->next;        } else if (p1->exp < p2->exp) {            newNode->coef = p2->coef;            newNode->exp = p2->exp;            p2 = p2->next;        } else {            newNode->coef = p1->coef + p2->coef;            newNode->exp = p1->exp;            p1 = p1->next;            p2 = p2->next;            if (newNode->coef == 0) {                free(newNode);                continue;            }        }        newNode->next = NULL;        if (result == NULL) {            result = tail = newNode;        } else {            tail->next = newNode;            tail = newNode;        }    }    // 处理剩余项    while (p1 != NULL) {        PolyNode* newNode = (PolyNode*)malloc(sizeof(PolyNode));        newNode->coef = p1->coef;        newNode->exp = p1->exp;        newNode->next = NULL;        if (tail == NULL) result = newNode;        else tail->next = newNode;        tail = newNode;        p1 = p1->next;    }    while (p2 != NULL) {        PolyNode* newNode = (PolyNode*)malloc(sizeof(PolyNode));        newNode->coef = p2->coef;        newNode->exp = p2->exp;        newNode->next = NULL;        if (tail == NULL) result = newNode;        else tail->next = newNode;        tail = newNode;        p2 = p2->next;    }    return result;}  

第四步：打印多项式

为了验证我们的结果，写一个打印函数：

void printPolynomial(PolyNode* head) {    if (head == NULL) {        printf("0\n");        return;    }    PolyNode* curr = head;    while (curr != NULL) {        if (curr != head && curr->coef > 0) printf("+");        if (curr->exp == 0) {            printf("%d", curr->coef);        } else if (curr->exp == 1) {            if (curr->coef == 1) printf("x");            else if (curr->coef == -1) printf("-x");            else printf("%dx", curr->coef);        } else {            if (curr->coef == 1) printf("x^%d", curr->exp);            else if (curr->coef == -1) printf("-x^%d", curr->exp);            else printf("%dx^%d", curr->coef, curr->exp);        }        curr = curr->next;    }    printf("\n");}  

完整示例与运行效果

将上述函数整合到 main() 中：

#include <stdio.h>#include <stdlib.h>// 此处插入上面定义的所有函数...int main() {    printf("=== C语言链表多项式加法演示 ===\n");    printf("输入第一个多项式：\n");    PolyNode* p1 = createPolynomial();    printf("输入第二个多项式：\n");    PolyNode* p2 = createPolynomial();    printf("\n多项式1: ");    printPolynomial(p1);    printf("多项式2: ");    printPolynomial(p2);    PolyNode* sum = addPolynomials(p1, p2);    printf("相加结果: ");    printPolynomial(sum);    // 注意：实际项目中应释放链表内存（略）    return 0;}  

总结

通过本教程，你已经掌握了如何使用C语言链表多项式来动态存储和运算多项式。这种链表实现多项式的方法不仅节省内存，还能高效处理任意长度的多项式。

这是数据结构链表教程中的经典案例，建议你动手敲一遍代码，加深理解。掌握它，你就离精通C语言多项式运算更近了一步！

关键词回顾：C语言链表多项式、链表实现多项式、C语言多项式运算、数据结构链表教程