跳到主要内容

数据结构05-多项式相加

代码​

#include <stdio.h>
#include <stdlib.h>

// 定义一个链表节点，用于表示多项式的单项式，包含系数和指数
typedef struct LinkNode {
    int coefficient; // 系数
    int exponent;    // 指数
    struct LinkNode *next; // 指向下一个节点的指针
} *LinkList, *NodePtr;

// 初始化一个带头节点的链表，头节点的系数和指数都是0，返回链表头节点指针
LinkList initLinkList() {
    LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode));
    tempHeader->coefficient = 0;
    tempHeader->exponent = 0;
    tempHeader->next = NULL;
    return tempHeader;
}

// 打印链表，遍历链表每个节点，打印节点中的系数和指数
void printList(LinkList paraHeader) {
    NodePtr p = paraHeader->next;
    while (p != NULL) {
        printf("%d * x^%d + ", p->coefficient, p->exponent);
        p = p->next;
    }
    printf("\r\n");
}

// 打印单个节点的信息，用于测试
void printNode(NodePtr paraPtr, char paraChar) {
    if (paraPtr == NULL) {
        printf("NULL\r\n");
    } else {
        printf("The element of %c is (%d * x^%d)\r\n", paraChar, paraPtr->coefficient, paraPtr->exponent);
    }
}

// 在链表尾部添加一个新的节点，新节点包含系数和指数信息
void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent) {
    NodePtr p, q;

    // 创建一个新节点
    q = (NodePtr)malloc(sizeof(struct LinkNode));
    q->coefficient = paraCoefficient;
    q->exponent = paraExponent;
    q->next = NULL;

    // 找到链表的尾部
    p = paraHeader;
    while (p->next != NULL) {
        p = p->next;
    }

    // 将新节点添加到链表尾部
    p->next = q;
}

// 多项式相加，将两个多项式相加的结果存储在第一个多项式中
void add(NodePtr paraList1, NodePtr paraList2) {
    NodePtr p, q, r, s;

    // 初始化指针，p和q分别指向两个链表的第一个节点
    p = paraList1->next;
    printNode(p, 'p');
    q = paraList2->next;
    printNode(q, 'q');
    r = paraList1; // r用于追踪结果链表的最后一个节点
    printNode(r, 'r');
    free(paraList2); // 释放第二个链表的头节点

    // 合并两个链表
    while ((p != NULL) && (q != NULL)) {
        if (p->exponent < q->exponent) {
            // 第一个链表的当前节点的指数更小，直接链接到结果链表
            r->next = p;
            r = p;
            p = p->next;
        } else if (p->exponent > q->exponent) {
            // 第二个链表的当前节点的指数更小，链接到结果链表
            r->next = q;
            r = q;
            q = q->next;
        } else {
            // 两个链表的当前节点指数相同，合并节点
            p->coefficient += q->coefficient;
            if (p->coefficient == 0) {
                // 如果合并后系数为0，移除这个节点
                s = p;
                p = p->next;
            } else {
                // 如果系数不为0，链接到结果链表
                r = p;
                p = p->next;
            }
            s = q;
            q = q->next;
            free(s);
        }
    }

    // 将剩余的节点链接到结果链表
    if (p == NULL) {
        r->next = q;
    } else {
        r->next = p;
    }
}

// 单元测试1：测试多项式相加的功能
void additionTest1() {
    LinkList tempList1 = initLinkList();
    appendElement(tempList1, 7, 0);
    appendElement(tempList1, 3, 1);
    appendElement(tempList1, 9, 8);
    appendElement(tempList1, 5, 17);
    printList(tempList1);

    LinkList tempList2 = initLinkList();
    appendElement(tempList2, 8, 1);
    appendElement(tempList2, 22, 7);
    appendElement(tempList2, -9, 8);
    printList(tempList2);

    add(tempList1, tempList2);
    printf("The result is: ");
    printList(tempList1);
    printf("\r\n");
}

// 单元测试2：测试多项式相加的功能
void additionTest2() {
    LinkList tempList1 = initLinkList();
    appendElement(tempList1, 7, 0);
    appendElement(tempList1, 3, 1);
    appendElement(tempList1, 9, 8);
    appendElement(tempList1, 5, 17);
    printList(tempList1);

    LinkList tempList2 = initLinkList();
    appendElement(tempList2, 8, 1);
    appendElement(tempList2, 22, 7);
    appendElement(tempList2, -9, 10);
    printList(tempList2);

    add(tempList1, tempList2);
    printf("The result is: ");
    printList(tempList1);
    printf("\r\n");
}

// main函数，程序入口
int main() {
    additionTest1();
    additionTest2();
    printf("Finish.\r\n");
    return 0;
}

代码总结：

  1. 这段代码实现了一个链表结构，用来表示多项式。每个节点包含一个系数（coefficient）和一个指数（exponent），以及一个指向下一个节点的指针（next）。
  2. 提供了初始化链表、打印链表、在链表末尾添加元素和多项式相加的功能。
  3. initLinkList 函数创建一个空的链表，即带有一个头节点的链表。
  4. printList 函数遍历链表并打印每个节点的系数和指数。
  5. appendElement 函数在链表的末尾添加一个新的节点。
  6. add 函数将两个链表表示的多项式相加，并将结果存储在第一个链表中。如果两个多项式中有相同指数的项，则将这些项的系数相加；如果相加后系数为0，则该项被移除。第二个链表在相加过程中被销毁。
  7. additionTest1 和 additionTest2 两个函数是单元测试，用于测试多项式相加的功能。
  8. main 函数作为程序的入口，调用了两个测试函数，并在最后打印了“Finish.”表示程序结束。

运行结果​