Data Structures 05 - Polynomial Addition

Code

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

// Define a linked list node for representing a polynomial term, containing coefficient and exponent
typedef struct LinkNode {
    int coefficient; // Coefficient
    int exponent;    // Exponent
    struct LinkNode *next; // Pointer to the next node
} *LinkList, *NodePtr;

// Initialize a linked list with a head node; the head node's coefficient and exponent are both 0; return the head node pointer
LinkList initLinkList() {
    LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode));
    tempHeader->coefficient = 0;
    tempHeader->exponent = 0;
    tempHeader->next = NULL;
    return tempHeader;
}

// Print the linked list, traversing each node and printing its coefficient and exponent
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");
}

// Print information of a single node, used for testing
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);
    }
}

// Append a new node to the end of the linked list; the new node contains coefficient and exponent information
void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent) {
    NodePtr p, q;

    // Create a new node
    q = (NodePtr)malloc(sizeof(struct LinkNode));
    q->coefficient = paraCoefficient;
    q->exponent = paraExponent;
    q->next = NULL;

    // Find the end of the linked list
    p = paraHeader;
    while (p->next != NULL) {
        p = p->next;
    }

    // Append the new node to the end of the linked list
    p->next = q;
}

// Polynomial addition; stores the result of adding two polynomials into the first polynomial
void add(NodePtr paraList1, NodePtr paraList2) {
    NodePtr p, q, r, s;

    // Initialize pointers; p and q point to the first nodes of the two linked lists respectively
    p = paraList1->next;
    printNode(p, 'p');
    q = paraList2->next;
    printNode(q, 'q');
    r = paraList1; // r tracks the last node of the result linked list
    printNode(r, 'r');
    free(paraList2); // Free the head node of the second linked list

    // Merge the two linked lists
    while ((p != NULL) && (q != NULL)) {
        if (p->exponent < q->exponent) {
            // The current node of the first linked list has a smaller exponent, link directly to result
            r->next = p;
            r = p;
            p = p->next;
        } else if (p->exponent > q->exponent) {
            // The current node of the second linked list has a smaller exponent, link to result
            r->next = q;
            r = q;
            q = q->next;
        } else {
            // Both current nodes have the same exponent, merge nodes
            p->coefficient += q->coefficient;
            if (p->coefficient == 0) {
                // If the coefficient is 0 after merging, remove this node
                s = p;
                p = p->next;
            } else {
                // If the coefficient is not 0, link to the result
                r = p;
                p = p->next;
            }
            s = q;
            q = q->next;
            free(s);
        }
    }

    // Link remaining nodes to the result
    if (p == NULL) {
        r->next = q;
    } else {
        r->next = p;
    }
}

// Unit test 1: test polynomial addition functionality
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");
}

// Unit test 2: test polynomial addition functionality
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 function, program entry point
int main() {
    additionTest1();
    additionTest2();
    printf("Finish.\r\n");
    return 0;
}

Code Summary:

1. This code implements a linked list structure for representing polynomials. Each node contains a coefficient (coefficient), an exponent (exponent), and a pointer to the next node (next).
2. It provides functions for initializing a linked list, printing a linked list, appending elements to the end of a linked list, and polynomial addition.
3. The initLinkList function creates an empty linked list, i.e., a linked list with a head node.
4. The printList function traverses the linked list and prints the coefficient and exponent of each node.
5. The appendElement function appends a new node to the end of the linked list.
6. The add function adds two polynomials represented as linked lists and stores the result in the first linked list. If two polynomials have terms with the same exponent, their coefficients are added; if the sum is 0, that term is removed. The second linked list is destroyed during the addition process.
7. The additionTest1 and additionTest2 functions are unit tests for testing the polynomial addition functionality.
8. The main function serves as the program entry point, calling both test functions and printing "Finish." at the end to indicate program completion.

Running Result