Polynomial linked list C++

Add two polynomials using linked list in c

C program for Add two polynomials using linked list. Here more information.

// Include header file #include #include /* C program for Add two polynomials using linked list */ typedef struct Node { // Define useful field of Node int data; int power; struct Node * next; }Node; Node * getNode(int data, int power) { // Create dynamic memory of Node Node * ref = (Node * ) malloc(sizeof(Node)); if (ref == NULL) { // Failed to create memory return NULL; } ref->data = data; ref->power = power; ref->next = NULL; return ref; } // Update node value void updateRecord(Node * ref, int data, int power) { ref->data = data; ref->power = power; } typedef struct AddPolynomial { // Define useful field of AddPolynomial struct Node * head; }AddPolynomial; AddPolynomial * getAddPolynomial() { // Create dynamic memory of AddPolynomial AddPolynomial * ref = (AddPolynomial * ) malloc(sizeof(AddPolynomial)); if (ref == NULL) { // Failed to create memory return NULL; } ref->head = NULL; return ref; } // Display given polynomial nodes void display(AddPolynomial * ref) { if (ref->head == NULL) { printf("Empty Polynomial "); } printf(" "); Node * temp = ref->head; while (temp != NULL) { if (temp != ref->head) { printf(" + %d", temp->data); } else { printf("%d",temp->data); } if (temp->power != 0) { printf("x^%d", temp->power); } // Visit to next node temp = temp->next; } printf("\n"); } // Add node with given data and power void addNode(AddPolynomial * ref, int data, int power) { if (ref->head == NULL) { // Add first node ref->head = getNode(data, power); } else { Node * node = NULL; Node * temp = ref->head; Node * location = NULL; // Find the valid new node location while (temp != NULL && temp->power >= power) { location = temp; temp = temp->next; } if (location != NULL && location->power == power) { // When polynomial power already exists // Then add current add to previous data location->data = location->data + data; } else { node = getNode(data, power); if (location == NULL) { // When add node in begining node->next = ref->head; ref->head = node; } else { // When adding node in intermediate // location or end location node->next = location->next; location->next = node; } } } } // Add two polynomial Node * addTwoPolynomials(AddPolynomial * ref, AddPolynomial * other) { // Define some useful variable Node * result = NULL; Node * tail = NULL; Node * node = NULL; // Get first node of polynomial Node * first = ref->head; Node * second = other->head; // Execute loop until when polynomial are exist // And add two polynomial. // Process takes O(n) time. while (first != NULL || second != NULL) { // Create node with default value node = getNode(0, 0); if (result == NULL) { // When first resultant node result = node; } if (first != NULL && second != NULL) { if (first->power == second->power) { // When the polynomial node power are same updateRecord(node, first->data + second->data, first->power); first = first->next; second = second->next; } else if (first->power > second->power) { // When first polynomial power are larger updateRecord(node, first->data, first->power); first = first->next; } else { // When second polynomial power are larger updateRecord(node, second->data, second->power); second = second->next; } } else if (first != NULL) { // When first polynomial are not empty // Update the current node information updateRecord(node, first->data, first->power); first = first->next; } else { // When second polynomial are not empty updateRecord(node, second->data, second->power); second = second->next; } if (tail == NULL) { tail = node; } else { // Add new node at end of resultant polynomial tail->next = node; tail = node; } } // return first node return result; } int main() { AddPolynomial * poly1 = getAddPolynomial(); AddPolynomial * poly2 = getAddPolynomial(); AddPolynomial * result = getAddPolynomial(); // Add node in polynomial poly1 addNode(poly1, 9, 3); addNode(poly1, 4, 2); addNode(poly1, 3, 0); addNode(poly1, 7, 1); addNode(poly1, 3, 4); // Add node in polynomial poly2 addNode(poly2, 7, 3); addNode(poly2, 4, 0); addNode(poly2, 6, 1); addNode(poly2, 1, 2); // Display Polynomial nodes printf("\n Polynomial A\n"); display(poly1); printf(" Polynomial B\n"); display(poly2); result->head = addTwoPolynomials(poly1, poly2); // Display calculated result printf(" Result\n"); display(result); }

Output

Polynomial A 3x^4 + 9x^3 + 4x^2 + 7x^1 + 3 Polynomial B 7x^3 + 1x^2 + 6x^1 + 4 Result 3x^4 + 16x^3 + 5x^2 + 13x^1 + 7