C语言单链表实现多项式加减法及排序

C语言单链表实现多项式加减法及排序

本文将介绍如何使用C语言的单链表来表示多项式，并实现多项式的加法、减法以及按指数降序排序。

1. 数据结构定义

首先，我们定义一个结构体来表示多项式的每个项，包括系数和指数：ctypedef struct Node { int coeff; // 系数 int expo; // 指数 struct Node* next; // 下一个结点指针} Node;

2. 创建新节点

接下来，我们创建一个函数来生成新的节点：cNode* createNode(int coeff, int expo) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->coeff = coeff; newNode->expo = expo; newNode->next = NULL; return newNode;}

3. 插入节点

为了方便后续操作，我们按照指数降序插入节点：cvoid 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;}

4. 输出多项式

为了直观地展示结果，我们编写一个函数来输出多项式：cvoid 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(' ');}

5. 多项式加法

实现多项式加法的函数：cNode* polyAdd(Node* poly1, Node* poly2) { Node* result = NULL; Node* temp1 = poly1; Node* temp2 = poly2;

while (temp1 != NULL && temp2 != NULL) {        if (temp1->expo > temp2->expo) {            insertNode(&result, temp1->coeff, temp1->expo);            temp1 = temp1->next;        } else if (temp1->expo < temp2->expo) {            insertNode(&result, temp2->coeff, temp2->expo);            temp2 = temp2->next;        } else {            insertNode(&result, temp1->coeff + temp2->coeff, temp1->expo);            temp1 = temp1->next;            temp2 = temp2->next;        }    }

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

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

return result;}

6. 多项式减法

实现多项式减法的函数，与加法类似，只需将系数相减即可：cNode* polySubtract(Node* poly1, Node* poly2) { Node* result = NULL; Node* temp1 = poly1; Node* temp2 = poly2;

while (temp1 != NULL && temp2 != NULL) {        if (temp1->expo > temp2->expo) {            insertNode(&result, temp1->coeff, temp1->expo);            temp1 = temp1->next;        } else if (temp1->expo < temp2->expo) {            insertNode(&result, -temp2->coeff, temp2->expo);            temp2 = temp2->next;        } else {            insertNode(&result, temp1->coeff - temp2->coeff, temp1->expo);            temp1 = temp1->next;            temp2 = temp2->next;        }    }

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

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

return result;}

7. 测试代码

最后，我们编写一个简单的测试程序：cint main() { Node* poly1 = NULL; Node* poly2 = NULL; Node* sum = NULL; Node* diff = NULL;

insertNode(&poly1, 3, 2);    insertNode(&poly1, 4, 1);    insertNode(&poly1, 2, 0);

insertNode(&poly2, 5, 3);    insertNode(&poly2, 2, 1);

printf('多项式1: ');    printPolynomial(poly1);    printf('多项式2: ');    printPolynomial(poly2);

sum = polyAdd(poly1, poly2);    printf('多项式相加: ');    printPolynomial(sum);

diff = polySubtract(poly1, poly2);    printf('多项式相减: ');    printPolynomial(diff);

return 0;}

总结

本文介绍了如何使用C语言的单链表实现多项式的表示、加法、减法以及按指数降序排序。通过本文的介绍，相信读者能够更加深入地理解数据结构和算法的相关知识。