C语言单链表实现多项式求和

摘要：#include #include typedefstruct Node {int coeff;int exp;struct Node* next;} Node;// 插入节点并保持降序排列，合并同类项void inser

talk is cheap show me code

#include #include typedefstruct Node {int coeff;int exp;struct Node* next;} Node;// 插入节点并保持降序排列，合并同类项void insertNode(Node** head, int coeff, int exp) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->coeff = coeff;newNode->exp = exp;newNode->next = NULL;if (*head == NULL) {*head = newNode;return;}Node* current = *head;Node* prev = NULL;// 查找插入位置while (current && current->exp > exp) {prev = current;current = current->next;}// 合并同类项if (current && current->exp == exp) {current->coeff += coeff;free(newNode);if (current->coeff == 0) { // 删除零系数项if (prev) {prev->next = current->next;} else {*head = current->next;}free(current);}return;}// 插入新节点if (prev) {prev->next = newNode;} else {newNode->next = *head;*head = newNode;}newNode->next = current;}// 多项式相加Node* addPolynomials(Node* poly1, Node* poly2) {Node* result = NULL;Node** tail = &result;while (poly1 && poly2) {Node* newNode = NULL;if (poly1->exp > poly2->exp) {newNode = (Node*)malloc(sizeof(Node));*newNode = (Node){poly1->coeff, poly1->exp, NULL};poly1 = poly1->next;} else if (poly2->exp > poly1->exp) {newNode = (Node*)malloc(sizeof(Node));*newNode = (Node){poly2->coeff, poly2->exp, NULL};poly2 = poly2->next;} else {int sum = poly1->coeff + poly2->coeff;if (sum != 0) {newNode = (Node*)malloc(sizeof(Node));*newNode = (Node){sum, poly1->exp, NULL};}poly1 = poly1->next;poly2 = poly2->next;}if (newNode) {*tail = newNode;tail = &(newNode->next);}}// 处理剩余节点Node* remaining = poly1 ? poly1 : poly2;while (remaining) {Node* newNode = (Node*)malloc(sizeof(Node));*newNode = (Node){remaining->coeff, remaining->exp, NULL};*tail = newNode;tail = &(newNode->next);remaining = remaining->next;}return result;}// 打印多项式void printPolynomial(Node* poly) {if (!poly) {printf("0\n");return;}while (poly) {printf("%dx^%d", poly->coeff, poly->exp);poly = poly->next;if (poly) printf(" + ");}printf("\n");}// 释放链表内存void freePolynomial(Node* poly) {while (poly) {Node* temp = poly;poly = poly->next;free(temp);}}int main {// 创建多项式 3x^5 + 4x^3 + 2xNode* poly1 = NULL;insertNode(&poly1, 3, 5);insertNode(&poly1, 4, 3);insertNode(&poly1, 2, 1);printf("Polynomial 1: ");printPolynomial(poly1);// 创建多项式 5x^4 + 4x^3 + 1Node* poly2 = NULL;insertNode(&poly2, 5, 4);insertNode(&poly2, 4, 3);insertNode(&poly2, 1, 0);printf("Polynomial 2: ");printPolynomial(poly2);// 多项式相加Node* sum = addPolynomials(poly1, poly2);printf("Sum: ");printPolynomial(sum);// 释放内存freePolynomial(poly1);freePolynomial(poly2);freePolynomial(sum);return 0;}

代码说明：

数据结构： 使用Node结构体表示多项式中的每一项，包含系数coeff、指数exp和指向下一项的指针next。插入节点：insertNode函数将新项插入到合适的位置以保持降序排列。如果遇到相同指数的项，则合并系数。如果合并后系数为零，则删除该节点。多项式相加：addPolynomials函数使用双指针法遍历两个多项式，按指数大小顺序合并生成新多项式。处理过程中始终维护结果的正确顺序。内存管理： 提供了freePolynomial函数来释放链表内存，避免内存泄漏。

执行结果：

该实现能够高效地处理多项式相加操作，时间复杂度为O(m+n)，其中m和n分别是两个多项式的项数。