Multiplying polynomials maintained as Linked List in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
/* structure representing a node of a linked list. The node can store a term of
    a polynomial */
struct polynode
{
 float coeff ;
 int exp ;
 struct polynode *link ;
} ;
void poly_append ( struct polynode **, float, int ) ;
void display_poly ( struct polynode * ) ;
void poly_multiply ( struct polynode *, struct polynode *, struct polynode ** ) ;
void padd ( float, int, struct polynode ** ) ;
int main( )
{
 struct polynode *first, *second, *mult ;
 int i = 1 ;
 first = second = mult = NULL ;  /* empty linked lists */
 poly_append ( &first, 3, 5 ) ;
 poly_append ( &first, 2, 4 ) ;
 poly_append ( &first, 1, 2 ) ;
 system ( "cls" ) ;
 display_poly ( first ) ;
 poly_append ( &second, 1, 6 ) ;
 poly_append ( &second, 2, 5 ) ;
 poly_append ( &second, 3, 4 ) ;
 printf ( "\n\n" ) ;
 display_poly ( second ) ;
 printf ( "\n" ) ;
 while ( i++ < 79 )
  printf ( "-" ) ;
 poly_multiply ( first, second, &mult ) ;
 printf ( "\n\n" ) ;
 display_poly ( mult ) ;
 return 0 ;
}
/* adds a term to a polynomial */
void poly_append ( struct polynode **q, float x, int y )
{
 struct polynode *temp ;
 temp = *q ;
 /* create a new node if the list is empty */
 if ( *q == NULL )
 {
  *q = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
  temp = *q ;
 }
 else
 {
  /* traverse the entire linked list */
  while ( temp -> link != NULL )
   temp = temp -> link ;
  /* create new nodes at intermediate stages */
  temp -> link = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
  temp = temp -> link ;
 }
 /* assign coefficient and exponent */
 temp -> coeff = x ;
 temp -> exp = y ;
 temp -> link = NULL ;
}
/* displays the contents of linked list representing a polynomial */
void display_poly ( struct polynode *q )
{
 /* traverse till the end of the linked list */
 while ( q != NULL )
 {
  printf ( "%.1f x^%d  :  ", q -> coeff, q -> exp ) ;
  q = q -> link ;
 }
 printf ( "\b\b\b " ) ;  /* erases the last colon(:) */
}
/* multiplies the two polynomials */
void poly_multiply ( struct polynode *x, struct polynode *y,
       struct polynode **m )
{
 struct polynode *y1 ;
 float coeff1 ;
 int exp1 ;
 y1 = y ;  /* point to the starting of the second linked list */
 if ( x == NULL && y == NULL )
  return ;
 /* if one of the list is empty */
 if ( x == NULL )
  *m = y ;
 else
 {
  if ( y == NULL )
   *m = x ;
  else  /* if both linked lists exist */
  {
   /* for each term of the first list */
   while ( x != NULL )
   {
    /* multiply each term of the second linked list with a
        term of the first linked list */
    while ( y != NULL )
    {
     coeff1 = x -> coeff * y -> coeff ;
     exp1 = x -> exp + y -> exp ;
     y = y -> link ;
     /* add the new term to the resultant polynomial */
     padd ( coeff1, exp1, m ) ;
    }
    y = y1 ;  /* reposition the pointer to the starting of
       the second linked list */
    x = x -> link ;  /* go to the next node */
   }
  }
 }
}
/* adds a term to the polynomial in the descending order of the exponent */
void padd ( float c, int e, struct polynode **s )
{
 struct polynode *r = NULL, *temp = *s ;
 /* if list is empty or if the node is to be inserted before the first node */
 if ( *s == NULL || e > ( *s ) -> exp )
 {
  *s = r = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
  ( *s ) -> coeff = c ;
  ( *s ) -> exp = e ;
  ( *s ) -> link = temp ;
 }
 else
 {
  /* traverse the entire linked list to search the position to insert a new
   node */
  while ( temp != NULL )
  {
   if ( temp -> exp == e )
   {
    temp -> coeff += c ;
    return ;
   }
   if ( temp -> exp > e && ( temp -> link == NULL ||
         temp -> link -> exp < e ) )
   {
    r = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
    r -> coeff = c ;
    r -> exp = e ;
    r -> link = temp -> link ;
    temp -> link = r ;
    return ;
   }
   temp = temp -> link ;  /* go to next node */
  }
  r -> link = NULL ;
  temp -> link = r ;
 }
}

Adding polynomials maintained as Linked List in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
/* structure representing a node of a linked list. The node can store term of a polynomial */
struct polynode
{
 float coeff ;
 int exp ;
 struct polynode *link ;
} ;
void poly_append ( struct polynode **, float, int ) ;
void display_poly ( struct polynode * ) ;
void poly_add ( struct polynode *, struct polynode *, struct polynode ** ) ;
int main( )
{
 struct polynode *first, *second, *total ;
 int i = 0 ;
 first = second = total = NULL ;  /* empty linked lists */
 poly_append ( &first, 1.4f, 5 ) ;
 poly_append ( &first, 1.5f, 4 ) ;
 poly_append ( &first, 1.7f, 2 ) ;
 poly_append ( &first, 1.8f, 1 ) ;
 poly_append ( &first, 1.9f, 0 ) ;
 system ( "cls" ) ;
 display_poly ( first ) ;
 poly_append ( &second, 1.5f, 6 ) ;
 poly_append ( &second, 2.5f, 5 ) ;
 poly_append ( &second, -3.5f, 4 ) ;
 poly_append ( &second, 4.5f, 3 ) ;
 poly_append ( &second, 6.5f, 1 ) ;
 printf ( "\n\n" ) ;
 display_poly ( second ) ;
 /* draws a dashed horizontal line */
 printf ( "\n" ) ;
 while ( i++ < 79 )
  printf ( "-" ) ;
 printf ( "\n\n" ) ;
 poly_add ( first, second, &total ) ;
 display_poly ( total ) ;  /* displays the resultant polynomial */
 return 0 ;
}
/* adds a term to a polynomial */
void poly_append ( struct polynode **q, float x, int y )
{
 struct polynode *temp ;
 temp = *q ;
 /* creates a new node if the list is empty */
 if ( *q == NULL )
 {
  *q = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
  temp = *q ;
 }
 else
 {
  /* traverse the entire linked list */
  while ( temp -> link != NULL )
   temp = temp -> link ;
   /* create new nodes at intermediate stages */
   temp -> link = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   temp = temp -> link ;
 }
 /* assign coefficient and exponent */
 temp -> coeff = x ;
 temp -> exp = y ;
 temp -> link = NULL ;
}
/* displays the contents of linked list representing a polynomial */
void display_poly ( struct polynode *q )
{
 /* traverse till the end of the linked list */
 while ( q != NULL )
 {
  printf ( "%.1f x^%d  :  ", q -> coeff, q -> exp ) ;
  q = q -> link ;
 }
 printf ( "\b\b\b " ) ;  /* erases the last colon */
}
/* adds two polynomials */
void poly_add ( struct polynode *x, struct polynode *y, struct  polynode **s )
{
 struct polynode *z ;
 /* if both linked lists are empty */
 if ( x == NULL && y == NULL )
  return ;
 /* traverse till one of the list ends */
 while ( x != NULL && y != NULL )
 {
  /* create a new node if the list is empty */
  if ( *s == NULL )
  {
   *s = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   z = *s ;
  }
  /* create new nodes at intermediate stages */
  else
  {
   z -> link = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   z = z -> link ;
  }
  /* store a term of the larger degree polynomial */
  if ( x -> exp < y -> exp )
  {
   z -> coeff = y -> coeff ;
   z -> exp = y -> exp ;
   y = y -> link ;  /* go to the next node */
  }
  else
  {
   if ( x -> exp > y -> exp )
   {
    z -> coeff = x -> coeff ;
    z -> exp = x -> exp ;
    x = x -> link ;  /* go to the next node */
   }
   else
   {
    /* add the coefficients, when exponents are equal */
    if ( x -> exp == y -> exp )
    {
     /* assigning the added coefficient */
     z -> coeff = x -> coeff + y -> coeff ;
     z -> exp = x -> exp ;
     /* go to the next node */
     x = x -> link ;
     y = y -> link ;
    }
   }
  }
 }
 /* assign remaining terms of the first polynomial to the result */
 while ( x != NULL )
 {
  if ( *s == NULL )
  {
   *s = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   z = *s ;
  }
  else
  {
   z -> link = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   z = z -> link ;
  }
  /* assign coefficient and exponent */
  z -> coeff = x -> coeff ;
  z -> exp = x -> exp ;
  x = x -> link ;  /* go to the next node */
 }
 /* assign remaining terms of the second polynomial to the result */
 while ( y != NULL )
 {
  if ( *s == NULL )
  {
   *s = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   z = *s ;
  }
  else
  {
   z -> link = ( struct polynode * ) malloc ( sizeof ( struct polynode ) ) ;
   z = z -> link ;
  }
  /* assign coefficient and exponent */
  z -> coeff = y -> coeff ;
  z -> exp = y -> exp ;
  y = y -> link ;  /* go to the next node */
 }
 z -> link = NULL ;  /* assign NULL at end of resulting linked list */
}

Doubly Linked List in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
/* structure representing a node of the doubly linked list */
struct dnode
{
 struct dnode *prev ;
 int data ;
 struct dnode * next ;
} ;
void d_append ( struct dnode **, int ) ;
void d_addatbeg ( struct dnode **, int ) ;
void d_addafter ( struct dnode *, int , int ) ;
void d_display ( struct dnode * ) ;
int d_count ( struct dnode *  ) ;
void d_delete ( struct dnode **, int ) ;
int main( )
{
 struct dnode *p ;
 p = NULL ;  /* empty doubly linked list */
 d_append ( &p , 11 ) ;
 d_append ( &p , 2 ) ;
 d_append ( &p , 14 ) ;
 d_append ( &p , 17 ) ;
 d_append ( &p , 99 ) ;
 system ( "cls" ) ;
 d_display ( p ) ;
 printf ( "No. of elements in the DLL = %d\n\n", d_count ( p ) ) ;
 d_addatbeg ( &p, 33 ) ;
 d_addatbeg ( &p, 55 ) ;
 d_display ( p ) ;
 printf ( "No. of elements in the DLL = %d\n\n", d_count ( p ) ) ;
 d_addafter ( p, 4, 66 ) ;
 d_addafter ( p, 2, 96 ) ;
 d_display ( p ) ;
 printf ( "No. of elements in the DLL = %d\n\n", d_count ( p ) ) ;
 d_delete ( &p, 55 ) ;
 d_delete ( &p, 2 ) ;
 d_delete ( &p, 99 ) ;
 d_display ( p ) ;
 printf ( "No. of elements in the DLL = %d\n\n", d_count ( p ) ) ;
 return 0 ;
}
/* adds a new node at the end of the doubly linked list */
void d_append ( struct dnode **s, int num )
{
 struct dnode *r, *q = *s ;
 /* if the linked list is empty */
 if ( *s == NULL )
 {
  /*create a new node */
  *s = ( struct dnode * ) malloc ( sizeof ( struct dnode ) ) ;
  ( *s ) -> prev = NULL ;
  ( *s ) -> data = num ;
  ( *s ) -> next = NULL ;
 }
 else
 {
  /* traverse the linked list till the last node is reached */
  while ( q -> next != NULL )
   q = q -> next ;
  /* add a new node at the end */
  r = ( struct dnode * ) malloc ( sizeof ( struct dnode ) ) ;
  r -> data = num ;
  r -> next = NULL ;
  r -> prev = q ;
  q -> next = r ;
 }
}
/* adds a new node at the begining of the linked list */
void d_addatbeg ( struct dnode **s, int num )
{
 struct dnode *q ;
 /* create a new node */
 q = ( struct dnode * ) malloc ( sizeof ( struct dnode ) ) ;
 /* assign data and pointer to the new node */
 q -> prev = NULL ;
 q -> data = num ;
 q -> next = *s ;
 /* make new node the head node */
 ( *s ) -> prev = q ;
 *s = q ;
}
/* adds a new node after the specified number of nodes */
void d_addafter ( struct dnode *q, int loc, int num )
{
 struct dnode *temp ;
 int i ;
 /* skip to desired portion */
 for ( i = 0 ; i < loc ; i++ )
 {
  q = q -> next ;
  /* if end of linked list is encountered */
  if ( q == NULL )
  {
   printf ( "There are less than %d elements\n", loc );
   return ;
  }
 }
 /* insert new node */
 q = q -> prev ;
 temp = ( struct dnode * ) malloc ( sizeof ( struct dnode ) ) ;
 temp -> data = num ;
 temp -> prev = q ;
 temp -> next = q -> next ;
 temp -> next -> prev = temp ;
 q -> next = temp ;
}
/* displays the contents of the linked list */
void d_display ( struct dnode *q )
{
 /* traverse the entire linked list */
 while ( q != NULL )
 {
  printf ( "%2d\t", q -> data ) ;
  q = q -> next ;
 }
 printf ( "\n" ) ;
}
/* counts the number of nodes present in the linked list */
int d_count ( struct dnode * q )
{
 int c = 0 ;
 /* traverse the entire linked list */
 while ( q != NULL )
 {
  q = q -> next ;
  c++ ;
 }
 return c ;
}
/* deletes the specified node from the doubly linked list */
void d_delete ( struct dnode **s, int num )
{
 struct dnode *q = *s ;
 /* traverse the entire linked list */
 while ( q != NULL )
 {
  /* if node to be deleted is found */
  if ( q -> data == num )
  {
   /* if node to be deleted is the first node */
   if ( q == *s )
   {
    *s = ( *s ) -> next ;
    ( *s ) -> prev = NULL ;
   }
   else
   {
    /* if node to be deleted is the last node */
    if ( q -> next == NULL )
     q -> prev -> next = NULL ;
    else
    /* if node to be deleted is any intermediate node */
    {
     q -> prev -> next = q -> next ;
     q -> next -> prev = q -> prev ;
    }
    free ( q ) ;
   }
   return ;  /* return back after deletion */
  }
  q = q -> next ; /* go to next node */
 }
 printf ( "%d not found.\n", num ) ;
}

Copying one Linked LIst into another through Recursion in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
/* structure containing a data part and link part */
struct node
{
 int data ;
 struct node *link ;
} ;
void append ( struct node **, int ) ;
void copy ( struct node *, struct node ** ) ;
void display ( struct node * ) ;
int main( )
{
 struct node *first, *second ;
 first = second = NULL ;  /* empty linked lists */
 append ( &first, 1 ) ;
 append ( &first, 2 ) ;
 append ( &first, 3 ) ;
 append ( &first, 4 ) ;
 append ( &first, 5 ) ;
 append ( &first, 6 ) ;
 append ( &first, 7 ) ;
 system ( "cls" ) ;
 display ( first ) ;
 copy ( first, &second ) ;
 display ( second ) ;
 return 0 ;
}
/* adds a node at the end of the linked list */
void append ( struct node **q, int num )
{
 struct node *temp ;
 temp = *q ;
 if ( *q == NULL )  /* if the list is empty, create first node */
 {
  *q = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = *q ;
 }
 else
 {
  /* go to last node */
  while ( temp -> link != NULL )
   temp = temp -> link ;
  /* add node at the end */
  temp -> link = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = temp -> link ;
 }
 /* assign data to the last node */
 temp -> data = num ;
 temp -> link = NULL ;
}
/* copies a linked list into another */
void copy ( struct node *q, struct node **s )
{
 if ( q != NULL )
 {
  *s = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  ( *s ) -> data = q -> data ;
  ( *s ) -> link = NULL ;
  copy ( q -> link, &( ( *s ) -> link ) ) ;
 }
}
/* displays the contents of the linked list */
void display ( struct node *q )
{
 /* traverse the entire linked list */
 while ( q != NULL )
 {
  printf ( "%d ", q -> data ) ;
  q = q -> link ;
 }
 printf ( "\n" ) ;
}

Comparing 2 Linked Lists through Recursion in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
struct node
{
 int data ;
 struct node *link ;
} ;
void append ( struct node **, int ) ;
int compare ( struct node *, struct node * ) ;
int main( )
{
 struct node *first, *second ;
 first = second = NULL ;  /* empty linked lists */
 append ( &first, 1 ) ;
 append ( &first, 2 ) ;
 append ( &first, 3 ) ;
 append ( &second, 1 ) ;
 append ( &second, 2 ) ;
 append ( &second, 3 ) ;
 system ( "cls" ) ;
 if ( compare ( first, second ) )
  printf ( "Both linked lists are EQUAL\n" ) ;
 else
  printf ( "Linked lists are DIFFERENT\n" ) ;
 return 0 ;
}
/* adds a node at the end of a linked list */
void append ( struct node **q, int num )
{
 struct node *temp ;
 temp = *q ;
 if ( *q == NULL )  /* if the list is empty, create first node */
 {
  *q = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = *q ;
 }
 else
 {
  /* go to last node */
  while ( temp -> link != NULL )
   temp = temp -> link ;
  /* add node at the end */
  temp -> link = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = temp -> link ;
 }
 /* assign data to the last node */
 temp -> data = num ;
 temp -> link = NULL ;
}
/* compares 2 linked lists and returns 1 if linked lists are equal and 0 if
 unequal */
int compare ( struct node *q, struct node *r )
{
 static int flag ;
 if ( ( q == NULL ) && ( r == NULL ) )
  flag = 1 ;
 else
 {
  if ( q == NULL || r == NULL )
   flag = 0 ;
  if ( q -> data != r -> data )
   flag = 0 ;
  else
   compare ( q -> link, r -> link ) ;
 }
 return ( flag ) ;
}

Counting number of nodes in a Linked List through Recursion in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
/* structure containing a data part and link part */
struct node
{
 int data ;
 struct node *link ;
} ;
void append ( struct node **, int ) ;
int length ( struct node * ) ;
int main( )
{
 struct node *p ;
 p = NULL ;  /* empty linked list */
 append ( &p, 1 ) ;
 append ( &p, 2 ) ;
 append ( &p, 3 ) ;
 append ( &p, 4 ) ;
 append ( &p, 5 ) ;
 system ( "cls" ) ;
 printf ( "Length of linked list = %d\n", length ( p ) ) ;
 return 0 ;
}
/* adds a node at the end of a linked list */
void append ( struct node **q, int num )
{
 struct node *temp ;
 temp = *q ;
 if ( *q == NULL )  /* if the list is empty, create first node */
 {
  *q = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = *q ;
 }
 else
 {
  /* go to last node */
  while ( temp -> link != NULL )
   temp = temp -> link ;
  /* add node at the end */
  temp -> link = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = temp -> link ;
 }
 /* assign data to the last node */
 temp -> data = num ;
 temp -> link = NULL ;
}
/* counts the number of nodes in a linked list */
int length ( struct node *q )
{
 static int l ;
 /* if list is empty or if NULL is encountered */
 if ( q == NULL )
  return ( 0 ) ;
 else
 {
  /* go to next node */
  l = 1 + length ( q -> link ) ;
  return ( l ) ;
 }
}

Concatenating 2 Linked Lists end to end in C

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <windows.h>
struct node
{
 int data ;
 struct node *link ;
} ;
void append ( struct node **, int ) ;
void concat ( struct node **, struct node ** ) ;
void display ( struct node * ) ;
int count ( struct node * ) ;
struct node * erase ( struct node * ) ;
int main( )
{
 struct node *first, *second ;
 first = second = NULL ;  /* empty linked lists */
 append ( &first, 1 ) ;
 append ( &first, 2 ) ;
 append ( &first, 3 ) ;
 append ( &first, 4 ) ;
 system ( "cls" ) ;
 printf ( "First List:\n" ) ;
 display ( first ) ;
 printf ( "No. of elements in the first Linked List = %d\n", count ( first ) ) ;
 append ( &second, 5 ) ;
 append ( &second, 6 ) ;
 append ( &second, 7 ) ;
 append ( &second, 8 ) ;
 printf ( "Second List:\n" ) ;
 display ( second ) ;
 printf ( "No. of elements in the second Linked List = %d\n",
   count ( second ) ) ;
 /* the result obtained after concatenation is in the first list */
 concat ( &first, &second ) ;
 printf ( "Concatenated List:\n" ) ;
 display ( first ) ;
 printf ( "No. of elements in Linked List before erasing = %d\n",
   count ( first ) ) ;
 first = erase ( first ) ;
 printf ( "No. of elements in Linked List after erasing = %d\n",
   count ( first ) ) ;
 return 0 ;
}
/* adds a node at the end of a linked list */
void append ( struct node **q, int num )
{
 struct node *temp ;
 temp = *q ;
 if ( *q == NULL )  /* if the list is empty, create first node */
 {
  *q = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = *q ;
 }
 else
 {
  /* go to last node */
  while ( temp -> link != NULL )
   temp = temp -> link ;
  /* add node at the end */
  temp -> link = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  temp = temp -> link ;
 }
 /* assign data to the last node */
 temp -> data = num ;
 temp -> link = NULL ;
}
/* concatenates two linked lists */
void concat ( struct node **p, struct node **q )
{
 struct node *temp ;
 /* if the first linked list is empty */
 if ( *p == NULL )
  *p = *q ;
 else
 {
  /* if both linked lists are non-empty */
  if ( *q != NULL )
  {
   temp = *p ;  /* points to the starting of the first list */
   /* traverse the entire first linked list */
   while ( temp -> link != NULL )
    temp = temp -> link ;
   temp -> link = *q ;  /* concatenate the second list after the
         first */
  }
 }
}
/* displays the contents of the linked list */
void display ( struct node *q )
{
 /* traverse the entire linked list */
 while ( q != NULL )
 {
  printf ( "%d ", q -> data ) ;
  q = q -> link ;
 }
 printf ( "\n\n" ) ;
}
/* counts the number of nodes present in the linked list */
int count ( struct node *q )
{
 int c = 0 ;
 /* traverse the entire linked list */
 while ( q != NULL )
 {
  q = q -> link ;
  c++ ;
 }
 return c ;
}
/* erases all the nodes from a linked list */
struct node * erase ( struct node *q )
{
 struct node *temp ;
 /* traverse till the end erasing each node */
 while ( q != NULL )
 {
  temp = q ;
  q = q -> link ;
  free ( temp ) ;  /* free the memory occupied by the node */
 }
 return NULL ;
}