当前位置：首页 > news >正文

数据结构之多项式相加的链表实现

news 来源：原创 2025/7/15 23:35:03

在计算机科学中，多项式的表示和运算经常会用到。使用链表来表示多项式是一种常见且有效的方法，它可以方便地处理多项式的各项，并且在进行多项式相加等运算时具有较好的灵活性。

多项式通常由一系列的项组成，每一项包含一个系数和一个指数。在链表中，我们可以将每一项表示为一个节点，节点包含系数、指数和指向下一个节点的指针。通过这种方式，我们可以将多项式的各项连接起来，形成一个链表。

代码实现：

#include <stdio.h>
#include <stdlib.h>// 定义多项式节点结构体
typedef struct node {float coef;  // 系数int expn;    // 指数struct node *next;  // 指向下一个节点的指针
} node, *polynomial;// 创建多项式链表，按照指数升序插入节点
polynomial createPolyn(int n) {polynomial L = (polynomial)malloc(sizeof(node));  // 分配头节点内存if (L == NULL) {fprintf(stderr, "内存分配失败\n");  // 检查内存分配是否成功exit(EXIT_FAILURE);}L->next = NULL;  // 初始化头节点的 next 指针为 NULLnode *p = L;  // 用于遍历链表的指针printf("\n请输入多项式的系数和指数（格式：系数,指数）:\n");for (int i = 1; i <= n; i++) {node *s = (node *)malloc(sizeof(node));  // 为新节点分配内存if (s == NULL) {fprintf(stderr, "内存分配失败\n");  // 检查内存分配是否成功exit(EXIT_FAILURE);}if (scanf("%f,%d", &s->coef, &s->expn) != 2) {  // 读取用户输入fprintf(stderr, "输入格式错误，请输入正确的格式（系数,指数）\n");exit(EXIT_FAILURE);}node *pre = p;  // 用于记录当前节点的前一个节点node *q = pre->next;  // 用于遍历链表的指针// 找到合适的插入位置，保证链表按指数升序排列while (q && q->expn < s->expn) {pre = q;q = q->next;}s->next = q;  // 插入新节点pre->next = s;}return L;
}// 多项式相加函数
void addPolyn(polynomial L1, polynomial L2) {node *p1 = L1->next;  // 指向第一个多项式的第一个节点node *p2 = L2->next;  // 指向第二个多项式的第一个节点node *p3 = L1;  // 用于构建结果多项式的指针float sum;while (p1 && p2) {if (p1->expn == p2->expn) {sum = p1->coef + p2->coef;  // 系数相加if (sum != 0) {p1->coef = sum;  // 更新系数p3->next = p1;p3 = p1;p1 = p1->next;node *r = p2;p2 = p2->next;free(r);  // 释放 p2 节点的内存} else {node *r = p1;p1 = p1->next;free(r);  // 释放 p1 节点的内存r = p2;p2 = p2->next;free(r);  // 释放 p2 节点的内存}} else if (p1->expn < p2->expn) {p3->next = p1;p3 = p1;p1 = p1->next;} else {p3->next = p2;p3 = p2;p2 = p2->next;}}p3->next = p1 ? p1 : p2;  // 连接剩余的节点// 释放 L2 的头节点free(L2);node *p4 = L1->next;printf("\n两多项式之和: ");while (p4) {printf("%.2f,%d  ", p4->coef, p4->expn);p4 = p4->next;}printf("\n");
}int main() {int n1, n2;printf("请输入第一个多项式的项数: ");scanf("%d", &n1);polynomial L1 = createPolyn(n1);  // 创建第一个多项式printf("请输入第二个多项式的项数: ");scanf("%d", &n2);polynomial L2 = createPolyn(n2);  // 创建第二个多项式addPolyn(L1, L2);  // 多项式相加// 释放 L1 的头节点free(L1);return 0;
}

代码结构分析：

1、结构体定义了多项式节点的基本结构，包含系数、指数和指向下一个节点的指针。使用 typedef 关键字可以方便地定义指向节点的指针类型 polynomial。

2、在创建多项式链表时，我们首先分配一个头节点，并将其 next 指针初始化为 NULL。然后，通过循环读取用户输入的系数和指数，为每一项创建一个新节点，并将其插入到链表中合适的位置，保证链表按指数升序排列。在插入节点时，我们使用两个指针 pre 和 q 来找到合适的插入位置。

3、在多项式相加的过程中，我们使用三个指针 p1、p2 和 p3 分别指向第一个多项式、第二个多项式和结果多项式。通过比较 p1 和 p2 所指向节点的指数，我们可以将它们合并到结果多项式中。如果指数相等，则将系数相加；如果相加结果不为零，则更新系数；如果相加结果为零，则删除这两个节点。最后，将剩余的节点连接到结果多项式中，并释放 L2 的头节点。

4、主函数中，我们首先读取用户输入的两个多项式的项数，然后分别创建这两个多项式。接着调用 addPolyn 函数进行多项式相加，并输出结果。最后，释放 L1 的头节点，避免内存泄漏。

总结：通过使用链表来表示多项式，并实现多项式相加的功能，我们可以更好地理解链表的操作和应用。

运行：

相关文章：