Add two Polynomials maintained as Linked Lists

C Program to add two polynomials maintained as linked lists.

#include <>
#include <>
#include <>

/* 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 ** ) ;

void main( )
{
struct polynode *first, *second, *total ;
int i = 0 ;

first = second = total = NULL ; /* empty linked lists */

poly_append ( &first, 1.4, 5 ) ;
poly_append ( &first, 1.5, 4 ) ;
poly_append ( &first, 1.7, 2 ) ;
poly_append ( &first, 1.8, 1 ) ;
poly_append ( &first, 1.9, 0 ) ;

clrscr( ) ;
display_poly ( first ) ;

poly_append ( &second, 1.5, 6 ) ;
poly_append ( &second, 2.5, 5 ) ;
poly_append ( &second, -3.5, 4 ) ;
poly_append ( &second, 4.5, 3 ) ;
poly_append ( &second, 6.5, 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 */
}

/* 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 = 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 = 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 = malloc ( sizeof ( struct polynode ) ) ;
z = *s ;
}
/* create new nodes at intermediate stages */
else
{
z – > link = malloc ( sizeof ( struct polynode ) ) ;
z = z – > link ;
}

/* store a term of the larger degree polynomial */
if ( x – > exp <> 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 = malloc ( sizeof ( struct polynode ) ) ;
z = *s ;
}
else
{
z – > link = 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 = malloc ( sizeof ( struct polynode ) ) ;
z = *s ;
}
else
{
z – > link = 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 */
}

read more: http://www.c-cplusplus.com/add-two-polynomials-maintained-as-linked-lists

C program to implement Avl Tree

#include
#include
typedef int ElementType;
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty( AvlTree T );

AvlTree Insert( ElementType X, AvlTree T );

void display(AvlTree T);


#include


struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};

void display(AvlTree T)
{
if(T->Left!=NULL)
display(T->Left);
if(T->Right!=NULL)
display(T->Right);
printf("%d",T->Element);
}
AvlTree MakeEmpty( AvlTree T )
{
if( T != NULL )
{
MakeEmpty( T->Left );
MakeEmpty( T->Right );
free( T );
}
return NULL;
}



static int Height( Position P )
{
if( P == NULL )
return -1;
else
return P->Height;
}


static int Max( int Lhs, int Rhs )
{
return Lhs > Rhs ? Lhs : Rhs;
}


/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static Position SingleRotateWithLeft( Position K2 )
{
Position K1;

K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;

K2->Height = Max( Height( K2->Left ), Height( K2->Right ) ) + 1;
K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;

return K1; /* New root */
}


/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static Position SingleRotateWithRight( Position K1 )
{
Position K2;

K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;

K1->Height = Max( Height( K1->Left ), Height( K1->Right ) ) + 1;
K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;

return K2; /* New root */
}


/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */

static Position DoubleRotateWithLeft( Position K3 )
{
/* Rotate between K1 and K2 */
K3->Left = SingleRotateWithRight( K3->Left );

/* Rotate between K3 and K2 */
return SingleRotateWithLeft( K3 );
}


/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */

static Position DoubleRotateWithRight( Position K1 )
{
/* Rotate between K3 and K2 */
K1->Right = SingleRotateWithLeft( K1->Right );

/* Rotate between K1 and K2 */
return SingleRotateWithRight( K1 );
}



AvlTree Insert( ElementType X, AvlTree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T =(AvlTree) malloc( sizeof( struct AvlNode ) );
if( T == NULL )
printf( "Out of space!!!" );
else
{
T->Element = X; T->Height = 0;
T->Left = T->Right = NULL;
}
}
else
if( X <>Element )
{
T->Left = Insert( X, T->Left );
if( Height( T->Left ) - Height( T->Right ) == 2 )
if( X <>Left->Element )
T = SingleRotateWithLeft( T );
else
T = DoubleRotateWithLeft( T );
}
else
if( X > T->Element )
{
T->Right = Insert( X, T->Right );
if( Height( T->Right ) - Height( T->Left ) == 2 )
if( X > T->Right->Element )
T = SingleRotateWithRight( T );
else
T = DoubleRotateWithRight( T );
}
/* Else X is in the tree already; we'll do nothing */

T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
return T;
}





main()
{
AvlTree T;
Position P;


int i=0,a,ch;
T = MakeEmpty( NULL );
while(1)
{
printf("\nenter your choice 1.insert 2.display 3.exit");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the element");
scanf("%d",&a);
T = Insert( a, T );
break;
case 2:
printf("display by postorder traversal\n");
display(T);
break;
case 3:
exit(0);
break;
} }



}





OUTPUT:


enter your choice 1.insert 2.display 3.exit1
enter the element3

enter your choice 1.insert 2.display 3.exit1
enter the element2

enter your choice 1.insert 2.display 3.exit1
enter the element4

enter your choice 1.insert 2.display 3.exit
2
display by postorder traversal
243
enter your choice 1.insert 2.display 3.exit3

C program to implement expression tree

#include
#include
#include

typedef struct tree
{
char data;
struct tree *left;
struct tree *right;
}*pos;

pos stack[30];
int top=-1;
pos newnode(char b)
{
pos temp;
temp=(struct tree *)malloc (sizeof(struct tree));
temp->data=b;
temp->left=null;
temp->right=null;
return(temp);
}
void push(pos temp)
{
stack[++top]=temp;
}
pos pop()
{
pos p;
p=stack[top--];
return(p);
}

void inorder(pos t)
{
if(t!=NULL)
{
inorder(t->left);
printf(“%c”,t->data);
inorder(t->right);
}
}


void preorder(pos t)
{
if(t!=NULL)
{
printf(“%c”,t->data);
preorder(t->left);
preorder(t->right);
}
}
void postorder(pos t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf(“%c”,t->data);
}
}
void main()
{
char a[30];
pos temp, t;
int i ,j;
clrscr();
printf(“\t\t Expression tree”);
printf(“\nEnter the postfix expression:”);
gets(a);
for(i=0;a[i]!=NULL;i++)
{
if(a[i]==’*’ || a[i]==’/’ || a[i]==’+’ || a[i]==’-‘)
{
temp=newnode(a[i])
temp->right=pop();
temp->left=pop();
push(temp);
}
else
{
temp=newnode(a[i]);
push(temp);
}
}
printf(“\n Inorder Traversal”);
inorder(temp);
printf(“\n Preorder Traversal”);
preorder(temp);
printf(“\n postorder Traversal”);
postorder(temp);
getch();}


OUTPUT:


Enter the expression in postfix form : ab+c-

Inorder traversal : a+b-c

Preorder traversal : -+abc

Postorder traversal : ab+c-

C program to compute minimum cost spanning tree

#include
#include
#define SIZE 20
#define INFINITY 32767
void prim(int G[][SIZE],int nodes)
{
int select [SIZE],i,j,k;
int min_dist,v1,v2,total=0;
for(i=0;i
select[i]=0;
printf("\n\n The minimal spanning tree is:\n");
select[0]=1;
for(k=1;k
{
min_dist=INFINITY;
for(i=0;i
{
for(j=0;j
{
if(G[i][j] && ((select[i] && !select[j])||(!select[i] && select[j])))
{
if(G[i][j]
{
min_dist=G[i][j];
v1=i;
v2=j;
}
}
}
}
printf("\n Edge(%d%d) & wt=%d",v1,v2,min_dist);
select[v1]=select[v2]=1;
total=total+min_dist;
}
printf("\n\n\t Total path length is=%d",total);
}
void main()
{
int G[SIZE][SIZE],nodes;
int v1,v2,length,i,j,n;
clrscr();
printf("\n\t Prim's algorithm\n");
printf("\n Enter no. of nodes in the graph");
scanf("%d", &nodes);
printf("\n enter no. of edges in the graph");
scanf("%d",&n);
for(i=0;i
G[i][j]=0;
printf("\n Enter edges & wts\n");
for(i=0;i
{
printf("\n Enter Edge by v1&v2:");
scanf("%d%d", &v1,&v2);
printf("\n enter corresponding wt:");
scanf("%d",&length);
G[v1][v2]=G[v2][v1]=length;
}
getch();
printf("\n\t");
clrscr();
prim(G,nodes);
getch();
}


OUTPUT:

enter the no of nodes in graph:7
enter the no of edges in graph:12

enter edges and weights

enter edges by v1 and v2:0 1
enter the corresponding weight 2

enter edges by v1 and v2:0 2
enter the corresponding weight 4

enter edges by v1 and v2:0 3
enter the corresponding weight 1

enter edges by v1 and v2:1 3
enter the corresponding weight 3

enter edges by v1 and v2:1 4
enter the corresponding weight 10

enter edges by v1 and v2:2 3
enter the corresponding weight 2

enter edges by v1 and v2:3 4
enter the corresponding weight 7
enter edges by v1 and v2:2 5
enter the corresponding weight 5

enter edges by v1 and v2:5 6
enter the corresponding weight 1

enter edges by v1 and v2:4 6
enter the corresponding weight 6

enter edges by v1 and v2:3 5
enter the corresponding weight 8

enter edges by v1 and v2:3 6
enter the corresponding weight 4

The minimal spanning tree is:
edge(0,1)&weight=2
edge(0,3)&weight=1
edge(2,3)&weight=2
edge(3,6)&weight=4
edge(4,6)&weight=6
edge(5,6)&weight=1

total path length is=16

C Program to implement Binary Search Tree

#include
#include
#include
typedef int ElementType;
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
SearchTree MakeEmpty( SearchTree T );
Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Retrieve( Position P );
void display(SearchTree T);
struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
};
SearchTree MakeEmpty( SearchTree T )
{
if( T != NULL )
{
MakeEmpty( T->Left );
MakeEmpty( T->Right );
free( T );
}
return NULL;
}
Position Find( ElementType X, SearchTree T )
{
if( T == NULL )
return NULL;
if( X <>Element )
return Find( X, T->Left );
else
if( X > T->Element )
return Find( X, T->Right );
else
return T;
}
Position FindMin( SearchTree T )
{
if( T == NULL )
return NULL;
else
if( T->Left == NULL )
return T;
else
return FindMin( T->Left );
}
Position FindMax( SearchTree T )
{
if( T != NULL )
while( T->Right != NULL )
T = T->Right;

return T;
}


SearchTree Insert( ElementType X, SearchTree T )
{
/* 1*/ if( T == NULL )
{
/* Create and return a one-node tree */
/* 2*/ T =(struct TreeNode *) malloc( sizeof( struct TreeNode ) );
/* 3*/ if( T == NULL )
/* 4*/ printf( "Out of space!!!" );
else
{
/* 5*/ T->Element = X;
/* 6*/ T->Left = T->Right = NULL;
}
}
else
/* 7*/ if( X <>Element )
/* 8*/ T->Left = Insert( X, T->Left );
else
/* 9*/ if( X > T->Element )
/*10*/ T->Right = Insert( X, T->Right );
/* Else X is in the tree already; we'll do nothing */

/*11*/ return T; /* Do not forget this line!! */
}
SearchTree Delete( ElementType X, SearchTree T )
{
Position TmpCell;

if( T == NULL )
printf( "Element not found" );
else
if( X <>Element ) /* Go left */
T->Left = Delete( X, T->Left );
else
if( X > T->Element ) /* Go right */
T->Right = Delete( X, T->Right );
else /* Found element to be deleted */
if( T->Left && T->Right ) /* Two children */
{
/* Replace with smallest in right subtree */
TmpCell = FindMin( T->Right );
T->Element = TmpCell->Element;
T->Right = Delete( T->Element, T->Right );
}
else /* One or zero children */
{
TmpCell = T;
if( T->Left == NULL ) /* Also handles 0 children */
T = T->Right;
else if( T->Right == NULL )
T = T->Left;
free( TmpCell );
}

return T;
}

ElementType Retrieve( Position P)
{
return P->Element;
}
void display(SearchTree T)
{

printf("%d\t",T->Element);
if(T->Left!=NULL)
display(T->Left);
if(T->Right!=NULL)
display(T->Right);
}

#include

main( )
{
SearchTree T;
Position P;
int a; int f,b;
int n;
T = MakeEmpty( NULL );
while(1)
{
printf("\nenter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit\n");
scanf("%d",&n);
switch(n)
{
case 1:
printf("enter the element\n");
scanf("%d",&a);
T = Insert( a, T );
break;
case 2:
printf("enter the element to found\n");
scanf("%d",&f);
printf("the element is found it is%d",Retrieve(Find(f,T)));
break;
case 3:

printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
Retrieve( FindMax( T ) ) );
break;
case 4:

printf("to delete an element..enter the element");
scanf("%d",&b);
Delete(b,T);
break;
case 5:
display(T);
break;
case 6:
exit(0);
break;
default:
printf("invaid choice\n");
}
}
}

OUTPUT:


enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
1
enter the element
1

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
1
enter the element
2

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
1
enter the element
0

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
2
enter the element to found
0
the element is found it is0
enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
3
Min is 0, Max is 2

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
4
to delete an element..enter the element0

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
5
1 2
enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit

how to do a Binary search on a linked list?

Great C datastructure question!

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.