Polynomial using LinkedList

Algorithm Pseudocode for solving polynomial using singly Linkedlist

INPUT: HEADER1 AND HEADER2 ARE POINTER TO THE HEADER NODE OF THE LINKEDLISTS
OUTPUT: MERGED LINKEDLIST POLYNOMIAL RESULT
DATA STRUCTURE: SINGLY LINKEDLIST

STEP 1: START
STEP 2: PTR1=HEADER1->LINK ,PTR2=HEADER2->LINK ,PTR3=HEADER3->LINK
STEP 3: WHILE(PTR1!=NULL&&PTR2!=NULL)
STEP 4: NEW=NEWNODE(NODE)
STEP 4: IF(PTR1->EXP<PTR2->EXP)
STEP 5: NEW->EXP=PTR1->EXP
STEP 6: NEW->COEFF=PTR1->COEFF+PTR2->COEFF
STEP 7: NEW->LINK=NULL
STEP 8: PTR3->LINK=NEW
STEP 9: PTR3=NEW
STEP 10: PTR1=PTR1->LINK
STEP 11: ELSE IF(PTR1->EXP==PTR2->EXP)
STEP 12: NEW->EXP=PTR2->EXP
STEP 13: NEW->COEFF=PTR2->COEFF
STEP 14: NEW->LINK=NULL;
STEP 15: PTR3->LINK=NEW
STEP 16: PTR3-NEW
STEP 17: PTR1=PTR1->LINK 
STEP 18: PTR2=PTR2->LINK
STEP 19: ELSE
STEP 20: NEW->EXP=PTR2->EXP
STEP 21: NEW->COEFF=PTR2->COEFF
STEP 22: NEW->LINK=NULL
STEP 23: PTR3->LINK=NEW
STEP 24: PTR3=NEW
STEP 25: PTR2=PTR2->LINK
STEP 26: ENDWHILE
STEP 27: WHILE(PTR1!=NULL)
STEP 28: NEW->DATA=PTR1->DATA
STEP 29: NEW->LINK=NULL
STEP 30: PTR3->LINK=NEW
STEP 31: PTR3=NEW
STEP 32: PTR1=PTR1->LINK
STEP 33: ENDWHILE
STEP 34: WHILE(PTR2!=NULL)
STEP 35: NEW->DATA=PTR2->DATA
STEP 36: NEW->LINK=NULL
STEP 37: PTR3->LINK=NEW
STEP 38: PTR3=NEW
STEP 39: PTR2=PTR2->LINK
STEP 40: ENDWHILE
STEP 41: END

This pseudocode represents the merging of two sorted singly linked lists into a third sorted linked list, commonly used for merging polynomial terms. Each node contains two fields: EXP (exponent) and COEFF (coefficient). Let’s break it down step by step:

STEP 1: START

  • Begin the algorithm.

STEP 2: Initialization

  • PTR1, PTR2, and PTR3 are pointers for traversing three linked lists.
    • PTR1 points to the first node of the first list (HEADER1->LINK).
    • PTR2 points to the first node of the second list (HEADER2->LINK).
    • PTR3 is used to construct the merged list, starting at the head of the third list (HEADER3->LINK).

STEP 3: WHILE (PTR1 != NULL && PTR2 != NULL)

  • Loop through both lists as long as neither is fully traversed.

Inside the WHILE loop: for merging polynomials represented as nodes in a linkedlist.

STEP 4: Allocate memory for a new node

  • Create a new node to add to the merged list.

STEP 4-25: Compare Exponents

  1. IF (PTR1->EXP < PTR2->EXP)
    • Copy the exponent and coefficient from PTR1 to the new node.
    • Add PTR1->COEFF and PTR2->COEFF to compute the coefficient.
    • Update the links and move PTR1 to the next node.
  2. ELSE IF (PTR1->EXP == PTR2->EXP)
    • Both nodes have the same exponent.
    • Copy the exponent and coefficient of either pointer (e.g., PTR2) to the new node.
    • Move both PTR1 and PTR2 to their respective next nodes.
  3. ELSE (PTR1->EXP > PTR2->EXP)
    • Copy the exponent and coefficient from PTR2 to the new node.
    • Update the links and move PTR2 to the next node.

STEP 26: ENDWHILE

  • Exit the loop when at least one of the lists has been fully traversed.

STEP 27-33: Add Remaining Nodes from List 1

  • If nodes remain in PTR1 (list 1), add them to the merged list by:
    • Copying the data from PTR1 to the new node.
    • Updating the links and moving PTR1 to the next node.

STEP 34-40: Add Remaining Nodes from List 2

  • If nodes remain in PTR2 (list 2), add them to the merged list in the same way as above.

STEP 41: END

  • End the algorithm.

Key Points

  • This algorithm assumes that both input lists are sorted by exponents (EXP).
  • The merged list will also be sorted.
  • The NEW->COEFF calculation in step 6 may require additional clarification depending on whether coefficients should be summed for duplicate exponents.

Code for solving polynomial using Singly Linkedlist

The provided C program is designed to merge two polynomials represented as linked lists.

#include <stdio.h>
 #include <stdlib.h>
 int getnode(int);void display();void merge();void newnode();
 int x, pos, n;
 struct node
 {
    int coeff;
    int exp;
    struct node *link;
 };
 struct node *prev, *head, *news, *p, *ptr,*ptr1,*ptr2,*ptr3;
 struct node *q1;
 struct node *header, *header1,*header3,*header2;
 struct node *q, *r, *s;
 int main()
 {
    printf("ENTER THE LIMIT OF POLYNOMIAL 1: ");
    scanf("%d", &n);
    getnode(n);
    header1=header;
    printf("ENTER THE LIMIT OF POLYNOMIAL 2 ");
    scanf("%d", &n);
    getnode(n);
    header2=header;
    merge();
    printf("THE MERGE LIST IS:");
    display(header3);
    return 0;
 }
 void display(struct node *head1)
 {
    struct node *ptr;
    ptr = head1->link;
    // ptr=header->link;
    while (ptr != NULL)
    {
        printf("%d ", ptr->coeff);
        printf("%d",ptr->exp);
        ptr = ptr->link;
    }
 }
 void newnode()
 {
    news=malloc(sizeof(struct node));
 }
 void merge()
 {   
    header3=malloc(sizeof(struct node));
    header3->link=news;
    ptr1=header1->link;
    ptr2=header2->link;
    ptr3=header3;
    while(ptr1!=NULL&&ptr2!=NULL)
    {
        if(ptr1->exp<ptr2->exp)
        {
            newnode();
            news->exp=ptr1->exp;
            news->coeff=ptr1->coeff+ptr2->coeff;
            news->link=NULL;
            ptr3->link=news;
            ptr3=news;
            ptr1=ptr1->link;
        }
        else if(ptr1->exp==ptr2->exp)
        {
             newnode();
            news->exp=ptr2->exp;
            news->coeff=ptr2->coeff;
            news->link=NULL;
            ptr3->link=news;
            ptr3=news;
            ptr1=ptr1->link;
            ptr2=ptr2->link;
           
        }
        else{
             newnode();
            news->exp=ptr2->exp;
            news->coeff=ptr2->coeff;
            news->link=NULL;
            ptr3->link=news;
            ptr3=news;
            ptr2=ptr2->link;  
        }     
    }
    while(ptr1!=NULL)
    { 
        newnode();
        news->exp=ptr1->exp;
        news->coeff=ptr1->coeff;
        news->link=NULL;
        ptr3->link=news;
        ptr3=news;
        ptr1=ptr1->link; 
    }
    while(ptr2!=NULL)
    {
        newnode();
        news->exp=ptr2->exp;
        news->coeff=ptr2->coeff;
        news->link=NULL;
        ptr3->link=news;
        ptr3=news;
        ptr2=ptr2->link;
    }
 }
 int getnode(int n)
 {
    header = malloc(sizeof(struct node));
    head = NULL;
    for (int i = 0; i < n; i++)
    {
        p = malloc(sizeof(struct node));
        q1 = malloc(sizeof(struct node));
        q = NULL;
        printf("enter the coefficient");
        scanf("%d", &p->coeff);
        printf("enter the degree");
        scanf("%d",&p->exp);
        p->link = NULL;
        if (head == NULL)
            head = p;
        else
            prev->link = p;
        prev = p;
    }
    header->link = head;
    display(header);
    return 0;
 }

Explanation of the above program

Key Components

  1. Data Structure:
    • Each polynomial is stored as a linked list where:
      • coeff stores the coefficient of a term.
      • exp stores the exponent.
      • link points to the next node.
  2. Functions:
    • getnode(int n):
      • Creates a linked list of n terms based on user input.
    • display(struct node *head):
      • Prints the terms of the polynomial from the given linked list.
    • merge():
      • Merges two sorted polynomial linked lists (header1 and header2) into a third sorted list (header3).
    • newnode():
      • Allocates memory for a new node.
  3. Global Variables:
    • header1, header2: Headers for the two polynomials.
    • header3: Header for the merged polynomial.

Program Flow

  1. Input Polynomials:
    • The program first asks for the number of terms in Polynomial 1, then collects the coefficients and exponents using getnode().
    • This process is repeated for Polynomial 2.
  2. Merging Polynomials:
    • The merge() function iterates over both linked lists simultaneously.
    • It compares the exponents of the terms in the two polynomials:
      • If the exponents are equal, the coefficients are added.
      • If one exponent is smaller, the corresponding term is added to the merged list.
    • Remaining terms from either polynomial are added at the end.
  3. Display the Result:
    • The merged polynomial is printed using display().

Output

user@computer$ : ENTER THE LIMIT OF POLYNOMIAL 1: 3 
 enter the coefficient1 
 enter the degree2 
 enter the coefficient3 
 enter the degree3 
 enter the coefficient4 
 enter the degree4 
 1 23 34 4ENTER THE LIMIT OF POLYNOMIAL 2 3 
 enter the coefficient5 
 enter the degree5 
 enter the coefficient6 
 enter the degree6 
 enter the coefficient7 
 enter the degree8 
 5 56 67 8THE MERGE LIST IS:6 28 39 45 56 67 8

Related Posts

Leave a Comment

Your email address will not be published. Required fields are marked *

Subscribe
Subscribe