Implementation of Stacks using Linked Lists

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

typedef struct node
{
 int data;
 struct node *link;
}NODE,*NODEPTR;

NODEPTR insert(NODEPTR start)
{
 NODEPTR temp;
 temp=(NODEPTR)malloc(sizeof(NODE));
 if(temp==NULL)
 {
  printf("Unsuccessfull\n");
  return;
 }
 temp->link=NULL;
 printf("Enter the data to be pushed\n");
 scanf("%d",&temp->data);
 temp->link=start;
 start=temp;
 return start;
}

NODEPTR del(NODEPTR start)
{
 NODEPTR temp;
 if(start==NULL)
 {
  printf("Stack is empty\n");
  return;
 }
 temp=start;
 start=start->link;
 printf("The element popped is %d\n",temp->data);
 free(temp);
 return start;
}

void dis(NODEPTR start)
{
 NODEPTR temp;
 if(start==NULL)
 {
   printf("Stack is empty\n");
   return;
 }
 printf("The contents of the stack are:\n");
 for(temp=start;temp!=NULL;temp=temp->link)
  printf("%d\n",temp->data);
 }

main()
{
 int ch;
 NODEPTR start=NULL;
 while(1)
 {
  printf("1.Push\n2.Pop\n3.Display\n4.Exit\n");
  scanf("%d",&ch);
  switch(ch)
 {
  case 1 : start=insert(start);
           break;
  case 2 : start=del(start);
            break;
  case 3 : dis(start);
           break;
  default: return;
 }
}
}

Reversing of a linked list

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

typedef struct node
{
 int data;
 struct node *link;
}NODE,*NODEPTR;

NODEPTR insert(NODEPTR start)
{
 NODEPTR temp;
 temp=(NODEPTR)malloc(sizeof(NODE));
 if(temp==NULL)
 {
 printf("Unsuccessful\n");
 return start;
 }
 printf("Enter the data\n");
 scanf("%d",&temp->data);
 temp->link=start;
 start=temp;
 return start;
}

NODEPTR rev(NODEPTR start)
{
 NODEPTR cur=start;
 NODEPTR prev=NULL;
 NODEPTR next;
 while(cur!=NULL)
 {
  next=cur->link;
  cur->link=prev;
  prev=cur;
  cur=next;
 }
 return prev;
}

NODEPTR disb(NODEPTR start)
{
 NODEPTR temp;
 if(start==NULL)
 {
  printf("List is empty\n");
  return;
 }
 printf("The contents of the list before reversing\n");
 for(temp=start;temp!=NULL;temp=temp->link)
  printf("%d\n",temp->data);
 return start;
}
NODEPTR disa(NODEPTR prev)
{
 NODEPTR temp;
 if(prev==NULL)
 {
  printf("list is empty\n");
  return;
 }
 printf("The contents of the list after reversing\n");
 for(temp=prev;temp!=NULL;temp=temp->link)
  printf("%d\n",temp->data);
 return prev;
}

main()
{
 int ch;
 NODEPTR start=NULL;
 NODEPTR prev=NULL;
 while(1)
 {
  printf("1.Insert into the list\n2.List before reversing\n3.Reverse the list\n4.List after reversing\n");
 scanf("%d",&ch);
 switch(ch)
 {
  case 1 : start=insert(start);break;
  case 2 : start=disb(start);break;
  case 3 : prev=rev(start);break;
  case 4 : prev=disa(prev);break;
  default : return;
 }
 }
}

Implementation of Queues using Linked lists

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

typedef struct node
{
 int data;
 struct node *link;
}NODE,*NODEPTR;

NODEPTR insert(NODEPTR start)
{
 NODEPTR temp;
 NODEPTR cur=start;
 temp=(NODEPTR)malloc(sizeof(NODE));
 if(temp==NULL)
 {
  printf("Memory allocation not possible\n");
  return start;
 }
 printf("Enter the data\n");
 scanf("%d",&temp->data);
 temp->link=NULL;
 if(start==NULL)
  return temp;
 while(cur->link!=NULL)
  cur=cur->link;
 cur->link=temp;
 return start;
}

NODEPTR del(NODEPTR start)
{
 NODEPTR cur=start;
 if(start==NULL)
 {
 printf("Queue is empty\n");
  return NULL;
 }
 start=start->link;
 printf("Element deleted is %d\n",cur->data);
 free(cur);
 return start;
}

NODEPTR dis(NODEPTR start)
{
 NODEPTR cur=start;
 if(start==NULL)
 {
  printf("Queue is empty\n");
  return;
 }
 for(cur=start;cur!=NULL;cur=cur->link)
  printf("%d\n",cur->data);
}

main()
{
 int ch;
 NODEPTR start=NULL;
 while(1)
 {
  printf("1.Insert 2.Delete 3.Display\n");
  scanf("%d",&ch);
  switch(ch)
 {
  case 1 : start=insert(start);
           break;
  case 2 : start=del(start);
            break;
  case 3 : dis(start);
           break;
  default : return;
 }
}
}

Merging of 2 ordered Linked Lists without creating new nodes

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

typedef struct node
{
 int data;
 struct node *link;
}NODE,*NODEPTR;

NODEPTR insert(NODEPTR start)
{
 NODEPTR temp,cur=start;
 temp=(NODEPTR)malloc(sizeof(NODE));
 if(temp==NULL)
 {
  printf("Memory allocation not possible\n");
  return start;
 }
 printf("Enter the data\n");
 scanf("%d",&temp->data);
 temp->link=NULL;
 if(start==NULL)
  return temp;
 while(cur->link!=NULL)
  cur=cur->link;
 cur->link=temp;
 return start;
}

NODEPTR sl(NODEPTR start1,NODEPTR start2)
{
 NODEPTR start,p,q;
 if(start1==NULL)
  start=start2;
 else if(start2==NULL)
  start=start1;
 else if(start2->data >=start1->data)
  start=start1;
 else
  start=start2;
 p=start1;
 q=start2;
 while(start1!=NULL && start2!=NULL)
 {
  if(start2->data >= start1->data)
  {
   p=p->link;
   if(p!=NULL && p->data < start2->data)
   {
      start1=p;
      continue;
   }
   start1->link=start2;
   start1=p;
  }
  else
  {
   q=q->link;
   if(q!=NULL && q->data < start1->data)
   {
     start2=q;
     continue;
   }
   start2->link=start1;
   start2=q;
  }
 }
 return start;
}

void display(NODEPTR start)
{
 NODEPTR cur=start;
 if(start==NULL)
 {
   printf("List is empty\n");
   return;
 }
 printf("The merged list is \n");
 for(cur=start;cur!=NULL;cur=cur->link)
  printf("%d\t",cur->data);
}

main()
{
 int ch;
 NODEPTR start,start1,start2;
 start=NULL;
 start2=NULL;
 start1=NULL;
 while(1)
 {
  printf("1.Enter into list 1\n2.Enter into list 2\n3.Merge the 2 lists\n4.Display\n");
  scanf("%d",&ch);
  switch(ch)
 {
  case 1 : start1=insert(start1);break;
  case 2 : start2=insert(start2);break;
  case 3 : start=sl(start1,start2);break;
  case 4 : display(start);break;
  default: return;
 }
}
}

Binary Trees : Creating Tree using Iterative Technique with Inorder,Preorder and Postorder Traversals

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

typedef struct node
{
 int info;
 struct node *left,*right;
}NODE,*NODEPTR;

NODEPTR getnode()
{
 NODEPTR temp=(NODEPTR)malloc(sizeof(NODE));
 temp->left=temp->right=NULL;
 return temp;
}

NODEPTR create(NODEPTR root,int item)
{
 NODEPTR temp,cur,prev;
 temp=getnode();
 temp->info=item;
 if(root==NULL)
  return temp;
 cur=root;
 prev=NULL;
 while(cur!=NULL)
 {
  prev=cur;
  if(cur->info > item)
   cur=cur->left;
  else
   cur=cur->right;
 }
 if(item < prev->info)
  prev->left=temp;
 else
  prev->right=temp;
 return root;
}

void inorder(NODEPTR root)
{
 if(root!=NULL)
 {
  inorder(root->left);
  printf("%d\t",root->info);
  inorder(root->right);
 }
}

void preorder(NODEPTR root)
{
 if(root!=NULL)
 {
  printf("%d\t",root->info);
  preorder(root->left);
  preorder(root->right);
 }
}

void postorder(NODEPTR root)
{
 if(root!=NULL)
 {
  postorder(root->left);
  postorder(root->right);
  printf("%d\t",root->info);
 }
}

main()
{
NODEPTR root=NULL;
int item,ch,cont=1;
printf("Enter elements and -1 to terminate\n");
 while(1)
{
 scanf("%d",&item);
 if(item==-1)break;
 root=create(root,item);
}
 while(cont==1)
 {
 printf("1.Inorder 2.Preorder 3.Postorder \n");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1 : inorder(root);
            break;
   case 2 : preorder(root);break;
   case 3 : postorder(root);break;
   default : return;
}
 }
 }

Binary Trees : Creating, Deleting and Displaying

All thanks to my friends and Khanetkar Textbook, this code finally works somehow! :D




#include<stdio.h>
#include<malloc.h>

typedef struct node
{
int info;
struct node *left, *right;
}NODE,*NODEPTR;
int count=0;

insert(int x,NODEPTR *root)
{
if((*root)==NULL)
{
(*root)=malloc(sizeof(NODE));
(*root)->left=(*root)->right=NULL;
(*root)->info=x;
count++;
return;
}
if(x<(*root)->info)
insert(x,&((*root)->left));
else
insert(x,&((*root)->right));
}

void inorder(NODEPTR root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d ",root->info);
inorder(root->right);
}
}

NODEPTR search(NODEPTR root, int num, NODEPTR *parent,int *found)
{
NODEPTR q=root,x;
*found=0;
*parent=NULL;
if(count==0)return NULL;
while(q!=NULL)//binary searching
{
if(q->info==num)
{
*found=1;
printf("Search works\n");
return q;
}
if(q->info>num)
{
*parent=q;
q=q->left;
}
else
{
*parent=q;
q=q->right;
}
}
printf("Key not found\n");
return NULL;
}

delete(NODEPTR *root, int num)
{
int found;
NODEPTR parent, x,xsucc;
if(*root==NULL)
{
printf("Tree is empty\n");
return;
}
parent=NULL;
x=NULL;
x=search(*root,num,&parent,&found);
if(!found)
{
printf("Data not found\n");
return;
}
if(x==*root&&count==1)
{
*root=NULL;
count--;
return;
}
if(x==*root&&count==2)
{
if(x->left!=NULL)
*root=x->left;
else
*root=x->right;
count--;
return;
}
if(x!=*root&&count==2)
{
(*root)->left=NULL;
(*root)->right=NULL;
count--;
return;
}
if(x->left!=NULL&&x->right!=NULL)
{
printf("Reaches correct if\n");
parent=x;
xsucc=x->right;
printf("Finds correct xsucc\n");
while(xsucc->left!=NULL)
{
parent=xsucc;
xsucc=xsucc->left;
}
x->info=xsucc->info;
x=xsucc;
printf("Successful swap\n");
}
if(x->left==NULL&&x->right==NULL)
{
if(parent->right==x)
parent->right=NULL;
else
parent->left=NULL;
free(x);
count--;
return;
}
if(x->left==NULL&&x->right!=NULL)
{
if(x==*root)
{
*root=x->right;
free(x);
count--;
return;
}
if(parent->left==x)
parent->left=x->right;
else
parent->right=x->right;
printf("Enters correct sub if\n");
free(x);
count--;
return;
}
if(x->left!=NULL&&x->right==NULL)
{
if(x==*root)
{
*root=x->left;
free(x);
count--;
return;
}
parent->left=x->left;
free(x);
count--;
return;
}
}


int main()
{
NODEPTR root=NULL;
int elt=0,cont=1,num;
printf("Enter -1 to terminate\n");
while(elt!=-1)
{
scanf("%d",&elt);
if(elt!=-1)
insert(elt,&root);
}
printf("Before deletion\n");
inorder(root);
printf("\n");
while(cont==1)
{
printf("Enter element to be deleted\n");
scanf("%d",&num);
delete(&root,num);
printf("After deletion\n");
inorder(root);
printf("\nEnter 1 to keep deleting\n");
scanf("%d",&cont);
}
}

Insertion sort of strings in C

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

void insert(char a[][25],int n)
{
 int i,j,k;
 char key[25];
 for(i=1;i<n;i++)
 {
  strcpy(key,a[i]);
  for(j=i-1;j>=0;j--)
  {
    if(strcmp(key,a[j])>=0)break;
     strcpy(a[j+1],a[j]);
  }
  strcpy(a[j+1],key);
  printf("After pass %d:\n",i);
  for(k=0;k<n;k++)
   printf("%s\n",a[k]);
 }
}

int main()
{
  int n,i;
  char a[25][25];
  printf("Enter the  number of elements to sort\n");
  scanf("%d",&n);
  printf("Enter the strings to be sorted\n");
  for(i=0;i<n;i++)
   scanf("%s",a[i]);
  insert(a,n);
  printf("After sorting\n");
  for(i=0;i<n;i++)
   printf("%s\n",a[i]);
}


Thanks to the senior who gave us the permission to copy their code :P

Right Threaded Tree in C

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

typedef struct node
{
 int data;
 int rthread;
 struct node *left,*right;
}NODE,*NODEPTR;

NODEPTR getnode()
{
 NODEPTR temp;
 temp=(NODEPTR)malloc(sizeof(NODE));
 temp->left=NULL;
 temp->rthread=1;
 return temp;
}

NODEPTR insucc(NODEPTR s)//to find the inorder successor
{
  NODEPTR  p=s->right;
  if(s->rthread==0)
   while(p->left!=NULL)
    p=p->left;
  return p;
}

void inorder(NODEPTR h)//function to traverse in in-order
{
  NODEPTR t=h;
  while(1)
  {
    t=insucc(t);
     if(t==h)
            return;
     printf("%d\n",t->data);
   }
}

NODEPTR create(NODEPTR head)
{
 NODEPTR y,t,q[100];
 int f=0,r=0,v;
 y=getnode();
 q[r++]=y;
 printf("Enter the root:");
 scanf("%d",&y->data);
 y->right=head;
 head->right=y;
 head->rthread=0;
 while(f!=r)
 {
  t=q[f++];
  printf("\nEnter the left child(%d) :",t->data);
  do
  {
   printf("Left child should be smaller\n");
   scanf("%d",&v);
   if(v==-1)break;
  }while(v>t->data);
  if(v!=-1)
  {
   y=getnode();
   q[r++]=y;
   t->left=y;
   y->right=t;
   y->data=v;
  }
  printf("Enter the right child(%d) :",t->data);
  do
  {
   printf("Right child should be  greater\n");
   scanf("%d",&v);
   if(v==-1)break;
  }while(v<t->data);
  if(v!=-1)
  {
    y=getnode();
    y->right=t->right;
    t->right=y;
    y->data=v;
    t->rthread=0;
    q[r++]=y;
  }
 }
 return head;
}

int main()
{
 NODEPTR head;
 head=getnode();
 head=create(head);
 printf("Inorder traversal : \n");
 inorder(head);
}



PS : A very long, inefficient code.. Try to understand at your own risk!