Monday, July 11, 2011

Write a program to perform data structure operations on LInked list.


#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
main()
{
struct node *start,*loc;
int c,ch,f=0;
int n,item;
void create(struct node **, int);
void show(struct node *);

void insert_beg(struct node **);
void insert_end(struct node **);
void insert_after(struct node *);
void insert_before(struct node **);
void insert_sorted(struct node **);

void deletion_beg(struct node **);
void deletion_end(struct node **);
void deletion_after(struct node *);
void deletion_before(struct node **);
void deletion_given(struct node **);

extern struct node* search_unsorted(struct node *,int);
extern struct node* search_item(struct node *,int );
extern struct node* search_bitem(struct node *,int );
struct node* search_sorted(struct node *,int);
extern struct node* search_bi(struct node *,int );
start=NULL;

printf("main menu");
printf("\nPress 1 to create a linked list");
while(f!=6)
{
printf("\nPress 2 to display a linked list");
printf("\nPress 3 to insert a item linked list");
printf("\nPress 4 to search a item linked list");
printf("\nPress 5 to delete a item linked list");
printf("\npress 6 to exit");
printf("\nEnter your choice");
scanf("%d",&ch);
switch(ch)
{
   case 1:
        printf("Enter the elements you want in your linked list :");
        scanf("%d",&n);
        create(&start,n);
        break;
   case 2:
        show(start);
        break;
   case 3:
        printf("\ninsert Menu:");
        printf("\nPress 1 to insert item in the begining");
        printf("\nPress 2 to insert item in the last");
        printf("\nPress 3 to insert item after the given item");
        printf("\nPress 4 to insert item before the given item");
        printf("\nPress 5 to insert item in the sorted linked list");
        printf("\nEnter your choice");
        scanf("%d",&c);
        switch(c)
        {
       
             case 1:
                  insert_beg(&start);
                  break;
             case 2:
                  insert_end(&start);
                  break;
             case 3:
                  insert_after(start);
                  break;
             case 4:
                  insert_before(&start);
                  break;
             case 5:
                  insert_sorted(&start);
                  break;
             default:
                  printf("Invalid choice");
        }
        break;
   case 4:
        printf("\nEntered the item to be searched:");
        scanf("%d",&item);
        printf("\nsearching Menu:");
        printf("\nPress 1 to search item in the unsorted linked list");
        printf("\nPress 2 to search item in the sorted linked list");
        printf("\nEnter your choice");
        scanf("%d",&c);
        switch(c)
        {
             case 1:
                  loc=(struct node *)search_unsorted(start,item);
                  if(loc==NULL)
                   printf("\nItem is not in the list");
                  else
                   printf("\nitem is at %d location",loc);
                   break;
             case 2:
                    loc=(struct node *)search_sorted(start,item);
                  if(loc==NULL)
                   printf("\nItem is not in the list");
                  else
                   printf("\nitem is at %d location",loc);
                   break;
             default:
                  printf("Invalid choice");
        }
        break;
   case 5:      
        printf("\ndeletion Menu:");        
        printf("\nPress 1 to delete item in the begining");
        printf("\nPress 2 to delete item in the last");
        printf("\nPress 3 to delete item after the given item");
        printf("\nPress 4 to delete item before the given item");
        printf("\nPress 5 to delete given item ");
        printf("\nEnter your choice");
        scanf("%d",&c);
        switch(c)
        {
       
             case 1:
                  deletion_beg(&start);
                  break;
             case 2:
                  deletion_end(&start);
                  break;
             case 3:
                  deletion_after(start);
                  break;
             case 4:
                  deletion_before(&start);
                  break;
             case 5:
                  deletion_given(&start);
                  break;
             default:
                  printf("Invalid choice");
        }
        break;
        break;
   case 6:
        f=6;
        break;
   default:
        printf("Invalid choice");
}
}
}

void create(struct node **q,int n)
{
int i;
struct node *lst;
struct node *p;
lst=NULL;
for(i=1;i<=n;i++)
{
 p=(struct node *)malloc(sizeof(struct node));
 printf("Enter the %d element :",i);
 scanf("%d",&(p->data));
 p->next=NULL;
 if(*q==NULL)
    *q=p;
 else
   lst->next=p;
  lst=p;
}
}

void show(struct node *start)
{
printf("Entered linked list is :\n");
while(start!=NULL)
{
printf(" %d\n",start->data);
start=start->next;
}
}

void insert_beg(struct node **q)
{
 struct node *p;
 p=(struct node *)malloc(sizeof(struct node));
 printf("Enter the element to be inserted ");
 scanf("%d",&(p->data));
 p->next=*q;
 *q=p;
}

void insert_end(struct node **q)
{
 struct node *p,*ptr;
 p=(struct node *)malloc(sizeof(struct node));
 printf("Enter the element to be inserted ");
 scanf("%d",&(p->data));
 p->next=NULL;
 if(*q==NULL)
 {
   *q=p;
 }
 else
 {
  ptr=*q;
  while(ptr->next!=NULL)
  {
   ptr=ptr->next;
  }
  ptr->next=p;
}
}

void insert_after(struct node *q)
{
 struct node *p,*loc;
 int item;
 printf("Enter the item after which new element is to be inserted ");
 scanf("%d",&item);
 loc=(struct node *)search_unsorted(q,item);
  if(loc==NULL)
    printf("\nItem afer which element is to be inserted is not in the list");
  else
  {
    p=(struct node *)malloc(sizeof(struct node));
    printf("Enter the element to be inserted ");
    scanf("%d",&(p->data));
    p->next=loc->next;
    loc->next=p;
  }
}

void insert_before(struct node **q)
{
 struct node *p,*loc;
 int item;
 printf("Enter the item before which new element is to be inserted ");
 scanf("%d",&item);
 if(*q==NULL)
 {
  printf("\nItem before which element is to be inserted is not in the list");
  return;
 }

    p=(struct node *)malloc(sizeof(struct node));
    printf("Enter the element to be inserted ");
    scanf("%d",&(p->data));
   
 if(item==(*q)->data)
 {
      p->next=*q;
      *q=p;
 }
 else
 {
 loc=(struct node *)search_bitem(*q,item);
  if(loc==NULL)
    printf("\nItem before which element is to be inserted is not in the list");
  else
  {
      p->next=loc->next;
      loc->next=p;
  }
 }
}

struct node* search_bitem(struct node *start,int item)
{
       struct node *prev,*ptr;
       ptr=start;
        prev=ptr;
        ptr=ptr->next;
        while(ptr!=NULL)
        {
          if(item==(ptr->data))
           return prev;
          prev=ptr;
          ptr=ptr->next;
        }
        return NULL;
}

void insert_sorted(struct node **start)
{
 struct node *p,*loc;
 int item;
 p=(struct node *)malloc(sizeof(struct node));
 printf("Enter the element to be inserted ");
 scanf("%d",&item);  
 p->data=item;
 p->next=NULL;
 loc=(struct node *)search_item(*start,item);
 if(loc==NULL)
  {
   p->next=*start;
  *start=p;
  }
 else
 {
  p->next=loc->next;
  loc->next=p;
 }
}

struct node* search_item(struct node *ptr,int item)
{
       struct node *prev;
       if(ptr==NULL)
        return NULL;
       else if(item<(ptr->data))
        return NULL;
        prev=ptr;
        ptr=ptr->next;
        while(ptr!=NULL)
        {
          if(item<(ptr->data))
           return prev;
          prev=ptr;
          ptr=ptr->next;
        }
        return prev;
}

struct node* search_unsorted(struct node *ptr,int item)
{
    while(ptr!=NULL)
    {
       if(item==ptr->data)
       return ptr;
       else
       ptr=ptr->next;
    }
    return NULL;
}

struct node* search_sorted(struct node *ptr,int item)
{
    struct node* loc=NULL;
    while(ptr!=NULL)
    {
       if(item>ptr->data)
          ptr=ptr->next;
       else if(item==ptr->data)
        {  loc=ptr;
          break;}
       else
          break;
    }
    return loc;
}

void deletion_beg(struct node **start)
{
     struct node *temp;
     if(*start==NULL)
     {
       printf("\n list is already empty");
     }
     else
     {
         temp=*start;
         *start=(*start)->next;
         free(temp);
     }
}
void deletion_end(struct node **start)
{
     struct node *temp,*prev,*ptr;
     ptr=*start;
     if(ptr==NULL)
     {
       printf("\n list is already empty");
     }
     else if(ptr->next==NULL)
     {
         temp=ptr;
         ptr=ptr->next;
         *start=ptr;
         free(temp);
         return;
     }
     else
     {
         prev=ptr;
         ptr=ptr->next;
         while(ptr->next!=NULL)
         {
           prev=ptr;
           ptr=ptr->next;
         }
         temp=prev->next;
         prev->next=NULL;
         free(temp);        
     }
}
void deletion_after(struct node *start)
{
 struct node *temp,*loc;
 int item;
 printf("Enter the item after which new element is to be deleted ");
 scanf("%d",&item);
 loc=(struct node *)search_unsorted(start,item);
  if(loc==NULL)
   {
     printf("\nItem afer which element is to be deleted is not in the list");
     return;
   }
  if(loc->next==NULL)
  {
    printf("\nNo element exit after the given item");
    return;
  }
    temp=loc->next;
    loc->next=(loc->next)->next;
    free(temp);
}

void deletion_given(struct node **start)
{
struct node *temp,*loc;
 int item;
 printf("Enter the item to be deleted ");
 scanf("%d",&item);
 if(*start==NULL)
 {
  printf("\nlist is empty");
  return;
 }  
 if(item==(*start)->data)
 {
      temp=*start;
      *start=(*start)->next;
      free(temp);
 }
 else
 {
 loc=(struct node *)search_bitem(*start,item);
  if(loc==NULL)
    printf("\nItem  which is to be deleted is not in the list");
  else
  {
      temp=loc->next;
      loc->next=temp->next;
      free(temp);
  }
 }
}

void deletion_before(struct node **start)
{
 struct node *temp,*loc;
 int item;
 printf("Enter the item before which the element is to be deleted ");
 scanf("%d",&item);
 if(*start==NULL)
 {
  printf("\nlist is empty");
 }  
 else if(item==(*start)->data)
 {
  printf("\nNo element exits before given item");
 }
 else if(item==((*start)->next)->data)
 {
      temp=*start;
      *start=(*start)->next;
      free(temp);
 }
 else
 {
 loc=(struct node *)search_bi(*start,item);
  if(loc==NULL)
    printf("\nItem  before which element is to be deleted is not in the list");
  else
  {
      temp=loc->next;
      loc->next=temp->next;
      free(temp);
  }
 }
}

struct node* search_bi(struct node *start,int item)
{
struct node *p1,*p2,*c;
p1=start;
p2=p1->next;
c=p2->next;
while(c!=NULL)
{
  if(c->data==item)
   return p1;
  p1=p2;
  p2=c;
  c=c->next;
}
return NULL;
}

Previous Next Home
0 Comments
Comments

Leave a Comment

:)) ;)) ;;) :D ;) :p :(( :) :( :X =(( :-o :-/ :-* :| 8-} :)] ~x( :-t b-( :-L x( =))

Twitter Delicious Facebook Favorites More