C语言: 用单链表实现多项式加减法

这篇文章提供了一个完整的C语言代码示例，演示如何使用单链表来表示多项式，并进行多项式的加减法运算。

代码实现c#include <stdio.h>#include <stdlib.h>

// 结点定义typedef struct Node { int coeff; // 系数 int expo; // 指数 struct Node* next; // 下一个结点指针} Node;

// 创建新结点Node* createNode(int coeff, int expo) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->coeff = coeff; newNode->expo = expo; newNode->next = NULL; return newNode;}

// 按指数降序插入结点void insertNode(Node** poly, int coeff, int expo) { Node* newNode = createNode(coeff, expo);

// 如果链表为空，直接将新结点作为头结点    if (*poly == NULL) {        *poly = newNode;        return;    }

// 如果新结点指数大于头结点指数，将新结点作为头结点    if (expo > (*poly)->expo) {        newNode->next = *poly;        *poly = newNode;        return;    }

Node* curr = *poly;

// 在适当的位置插入新结点    while (curr->next != NULL && curr->next->expo > expo) {        curr = curr->next;    }

newNode->next = curr->next;    curr->next = newNode;}

// 输出多项式void printPolynomial(Node* poly) { Node* curr = poly; while (curr != NULL) { printf('%dx^%d ', curr->coeff, curr->expo); if (curr->next != NULL && curr->next->coeff >= 0) { printf('+ '); } curr = curr->next; } printf(' ');}

// 相加两个多项式Node* addPolynomials(Node* poly1, Node* poly2) { Node* result = NULL; Node* curr1 = poly1; Node* curr2 = poly2;

while (curr1 != NULL && curr2 != NULL) {        if (curr1->expo > curr2->expo) {            insertNode(&result, curr1->coeff, curr1->expo);            curr1 = curr1->next;        } else if (curr1->expo < curr2->expo) {            insertNode(&result, curr2->coeff, curr2->expo);            curr2 = curr2->next;        } else {            int sum = curr1->coeff + curr2->coeff;            if (sum != 0) {                insertNode(&result, sum, curr1->expo);            }            curr1 = curr1->next;            curr2 = curr2->next;        }    }

// 将剩余的结点插入结果链表    while (curr1 != NULL) {        insertNode(&result, curr1->coeff, curr1->expo);        curr1 = curr1->next;    }

while (curr2 != NULL) {        insertNode(&result, curr2->coeff, curr2->expo);        curr2 = curr2->next;    }

return result;}

// 相减两个多项式Node* subtractPolynomials(Node* poly1, Node* poly2) { Node* result = NULL; Node* curr1 = poly1; Node* curr2 = poly2;

while (curr1 != NULL && curr2 != NULL) {        if (curr1->expo > curr2->expo) {            insertNode(&result, curr1->coeff, curr1->expo);            curr1 = curr1->next;        } else if (curr1->expo < curr2->expo) {            insertNode(&result, -curr2->coeff, curr2->expo);            curr2 = curr2->next;        } else {            int diff = curr1->coeff - curr2->coeff;            if (diff != 0) {                insertNode(&result, diff, curr1->expo);            }            curr1 = curr1->next;            curr2 = curr2->next;        }    }

// 将剩余的结点插入结果链表    while (curr1 != NULL) {        insertNode(&result, curr1->coeff, curr1->expo);        curr1 = curr1->next;    }

while (curr2 != NULL) {        insertNode(&result, -curr2->coeff, curr2->expo);        curr2 = curr2->next;    }

return result;}

int main() { Node* poly1 = NULL; // 第一个多项式链表头指针 Node* poly2 = NULL; // 第二个多项式链表头指针

int coeff, expo;    int numTerms;

// 输入第一个多项式的项数    printf('输入第一个多项式的项数：');    scanf('%d', &numTerms);

// 输入第一个多项式的系数和指数    printf('输入第一个多项式的系数和指数：

'); for (int i = 0; i < numTerms; i++) { scanf('%d %d', &coeff, &expo); insertNode(&poly1, coeff, expo); }

// 输入第二个多项式的项数    printf('输入第二个多项式的项数：');    scanf('%d', &numTerms);

// 输入第二个多项式的系数和指数    printf('输入第二个多项式的系数和指数：

'); for (int i = 0; i < numTerms; i++) { scanf('%d %d', &coeff, &expo); insertNode(&poly2, coeff, expo); }

// 输出第一个多项式    printf('第一个多项式: ');    printPolynomial(poly1);

// 输出第二个多项式    printf('第二个多项式: ');    printPolynomial(poly2);

// 计算并输出两个多项式的和    Node* sum = addPolynomials(poly1, poly2);    printf('相加结果: ');    printPolynomial(sum);

// 计算并输出两个多项式的差    Node* diff = subtractPolynomials(poly1, poly2);    printf('相减结果: ');    printPolynomial(diff);

return 0;}

代码说明

• 数据结构: 使用单链表存储多项式，每个节点包含系数、指数和指向下一个节点的指针。

• 插入节点: insertNode 函数按指数降序将新的项插入到链表中，确保多项式按标准形式排序。

• 加法和减法: addPolynomials 和 subtractPolynomials 函数遍历两个链表，将对应项的系数相加或相减，并将结果存储在新链表中。

• 输出: printPolynomial 函数遍历链表并以标准的多项式形式打印每一项。

总结

这段代码提供了一种清晰、易懂的方式来使用C语言实现多项式的加减法。通过使用单链表，可以方便地存储和操作多项式，并进行各种运算。