Well, my best friend was shortlisted for Microsoft Recruitment Test via Amcat. He is very good in academics and is currently dwelling deep into android world. Well, we are still expecting a positive result. In the test, he was given two programs, one of which was a pattern, and, other was to insert an element into an sorted circular list. Well, For many days, it was in my mind to make this program, so I finally set out to make it. Here it is. In the program I have assumed that the list may or may not be sorted, so I had to sort the list by my own in the first place.

I am using eclipse Juno and MinGW compiler at the core, and I do not know why it is facing some problem in executing printf and scanf statements in the sequential order. The assumed soltuion is to add a “fflush(stdout);” statement next to printf statement. The statement does what it looks to do, it flushes the output stream buffer. If you are going to use some other compiler/IDE, I think you wont be needing that statement. Well, here is the program.

/*
 * file.c
 *
 * Created on: Dec 11, 2012
 * Author: Gaurav
 */
# include <stdio.h>
# include <stdlib.h>
struct node
{
     int data;
     struct node* next;
}; 

typedef struct node Node; Node* sort(Node*);

void display(Node*);
Node* insert(Node*);

int main()
{
     int data,i,num; printf("Enter the number of nodes ");
     fflush(stdout); 
     scanf("%d", &num); 
     Node *n, *head, 
     *sec; 
     if(num>0)
     { 
          head = (Node*)malloc(sizeof(Node)); printf("Enter the value of the node ");
          fflush(stdout); 
          scanf("%d", &data); 
          head->data = data;
          head->next = NULL; 
          sec = head; 
          for(i=1;i<=num-1;i++)
          {
               printf("Enter the value of data ");
               fflush(stdout); 
               scanf("%d", &data); 
               n = (Node*)malloc(sizeof(Node)); 
               n->data = data;
               n->next = head; sec->next = n;
               sec = n; 
          }
     }
     n=head;
     if(num>0)
     {
           printf("\nNow Displaying the Nodes\n"); 
           display(head);
      }
      head = sort(head); 
      printf("\nSorted List is\n");
      display(head); 
      head = insert(head);
      display(head);
      return 0;
}

void display(Node *head)
{
      Node * n;
      n=head; while(1)
      {
           printf("%d\n", n->data);
           fflush(stdout);
           n = n->next; 
           if(n->next==head)
           {
                printf("%d\n", n->data);
                fflush(stdout); break;
           }
      }
}
Node* sort(Node* head)
{
      int num=0, temp, i=0,j, count=0;
      Node *n, *p; n= head; while(1)
      {
           num++;
           n = n->next; 
           if(n->next==head)
           {
                num++;
                break;
           }
      }
      n=head;
      for(i=1;i<=num;i++)
      {
           for(j=1;j<=num-1;j++)
           {
                p=n->next; 
                if(n->data > p->data)
                {
                     temp=n->data;
                     n->data = p->data;
                     p->data = temp;
                     count++;
                }
           n=n->next;
           p=p->next;
       }
       if(count==0)
       {
           break;
       }
       else
       {
           count=0;
            n=head;
        }
    }
    return head;
} 
Node* insert(Node *head)
{
    int data, loc=0,it=0, cor=0; Node *p,*n,*old; printf("Enter the value of the node to be added ");
    fflush(stdout); 
    scanf("%d", &data); //Case 1 when the List is empty
    if(head==NULL)
    {
         p = (Node*)malloc(sizeof(Node*));
         p->data=data;
         p->next=p;
     }
     else
     {
         //It is the case when the list is not empty
         //We are here supposed to first search the correct location to be entered
         n=head; 
         while(1)
         {
             if((data<= n->data)||(n->next==head))
             {
                 loc=it;
                 break;
             }
             else
             {
                 it++;
                 n=n->next;
             }
         }
         n= head;
         it=0;
         while(1)
         {
              it++;
              n=n->next;
              if(n->next==head)
              {
                  break;
              }
          }
          if(loc==0) //Node would be inserted at the head
          {
              n=head;
              while(n->next!=head)
              n=n->next; 
              p = (Node*)malloc(sizeof(Node));
              p->data = data;
              p->next = head;
              head = p;
              n->next = p;
          }
          else
              if(loc<it)
              {
                  n=head;
                  while(cor<loc)
                  {
                     old=n;
                     n=n->next;
                     cor++;
                  } 
                  p=(Node*)malloc(sizeof(Node));
                  p->data = data;
                  p->next = n;
                  old->next =p;
              }
              else
              {
                  n=head;
                  while(n->next!=head)
                  {
                      n=n->next;
                  }
                  p=(Node*)malloc(sizeof(Node));
                  p->data = data;
                  p->next = head;
                  n->next = p;
              }
        }
     return head;
}
Advertisements