Sunday 13 October 2013

Data Structures - C Programming

The Below Programs had written based upon my knowledge and not considered any rainy day scenarios(Negative/performance Issues). Please let me know if you find any discrepancy in the content. 


C Programs on Double Pointers
----------------------------- 

Double Pointer means it points the address of the pointer as shown below.

int **p; 
int *a;
int j=9;
 // Double Pointer points to the address of the pointer
p = &a  
// pointer holds the address of variable.
a = &j
      =  Gives the address of pointer (&a) = 500 
*p     =  Gives the value present in the address of 500 which is 399 (a or &j)
**p   =  Gives the value present in the address of 399 which is 4 (j).

 

#include<stdio.h>
#include<stdlib.h>
int main()
{
   int **i, *u, j=3;

   /* Double Pointer Points to address of the pointer */
   u = &j;

   /* Pointer Holds the address of the variable */
   i = &u;


  printf("The value of i:%u\n",  i);
  printf("The value of u:%u\n", &u);
  printf("The value of u:%u\n",  u);
  printf("The value of *i:%u\n", *i);
  printf("The value of &j:%u\n", &j);
  printf("The value of j:%u\n",   j);
}

output
====
[~]# gcc double_sample.c -o test.exe
[~]# ./test.exe
The value of i:3214414668
The value of u:3214414668
The value of u:3214414664
The value of *i:3214414664
The value of &j:3214414664
The value of j:3


Program for Double Pointers Memory Allocation
=============================================
#include<stdio.h>
#include<stdlib.h>
int main()
{
   int **p= NULL;
 
   /* Allocate the Memory for the Double Pointer */
   p = (int **)malloc(sizeof(int));

  /* Allocate the memory for the pointer which points by the 

   * Double pointer 
   */
  *p = (int *)malloc(sizeof(int));

 
  printf("The value of  p:%u\n",  p);
  printf("The value of *p:%u\n", *p);
  printf("The value of &p:%u\n", &p);
  
  /* Store the value in the Double Pointer */
  **p = 9;

  printf("The value of **p:%d\n", **p);
}


[~]# ./test.exe
The value of  p:134520840
The value of *p:134520856
The value of &p:3218864012
The value of **p:9


C Program for Double Link list 
-------------------------------

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

#define EXIT 10

typedef struct node
{
   int data;
   struct node *next;
   struct node *prev;
}NODE;

NODE *head, *tail;


/* 
 * Create Linklist
 */ 
NODE *createLinkList(int data)
{
   NODE *newNode = NULL;

   newNode = (NODE *)malloc(sizeof(NODE *));
   newNode->prev = NULL;
   newNode->next = NULL;
   newNode->data = data;

   return newNode;
}
/*
 * InsertLinkList()
 */
void insertLinkList()
{
  NODE *new, *temp;
  int k=1;

  int data, pos;

  printf(" Enter the Data to be inserted in Linklist\n");
  scanf("%d", &data);
           
  new = createLinkList(data);

  if(head == NULL)
  {
    head = new;
    return;
  }
  printf(" Enter the Position of Linklist\n");
  scanf("%d", &pos);
 

  /* Insert front of the Node */
  if(pos ==1)
  {
    new->next = head;
    head->prev = new;
    head = new;
    return;
  }
  temp = head;

  while ((k< pos-1) && (temp->next != NULL))
  {
    temp = temp->next;
    k++;
  }

  /* Insert Last of the Node */
  if(temp->next == NULL)
  {
    temp->next = new;
    new->prev = temp;
  }

  /* Insert Middle Of the Node */
  else      
  {
     new->prev = temp;
     new->next = temp->next;
     temp->next->prev = new; 
     temp->next = new;
  }
}
/*
 * Delete
 */
void deleteLinkList(void)
{
  NODE *temp, *temp2;

  int k=1;

  int pos;

  printf(" Enter the Position of Node to be Deleted\n");
  scanf("%d", &pos);

  if(head !=NULL)
  {

    /* Delete Start */
    if(pos == 1)
    {
      temp = head;
      head = head->next;
     
      if(head != NULL)
        head->prev = NULL;

      free(temp);
      return;
    }
    temp = head;
    while((k< pos) && (temp->next!= NULL))
    {
      temp = temp->next;
      k++;
    }

    /* Delete Last Node */
    if(temp->next == NULL)
    {
       temp2= temp;
       if(temp->prev != NULL)
          temp->prev->next = NULL;
       free(temp2);
    }

    /* Delete Middle */
    else
    {

       temp2= temp;
       temp->prev->next = temp->next;
       temp->next->prev = temp->prev;
       free(temp2);
    }
   }
   else
   {
     printf("Nodes Are Empty \n");
     return;
   }
}
/*
 * Display()
 */

void display()
{
  NODE *temp;

  temp = head;

  printf("The Data is \n");
  while(temp!= NULL)
  {
    printf("%d\n", temp->data);
    temp = temp->next;
  }
}
/*
 * Main()
 */
int main()
{
   int ch, data, pos;
   do
   {
     ch=0;
     printf("\n Enter the Choice \n");
     printf("1. Insert \n");
     printf("2. Delete \n");
     printf("3. Display \n");

     printf("Enter 10 for EXIT \n");
    
scanf("%d", &ch);
     switch(ch)
     {
        case 1:
             insertLinkList();
             break;
        case 2:
             deleteLinkList();
             break;
        case 3: display();
             break;
        default:
             printf("Invalid Choice \n");
             break;
      };
   }while(ch!=EXIT);
   return 0;
}


C Program for Circular Link list 
---------------------------------

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

#define EXIT 10

typedef struct node
{
   int data;
   struct node *next;
}NODE;

NODE *head, *last;

NODE *createLinkList(int data)
{
   NODE *newNode = NULL;

   newNode = (NODE *)malloc(sizeof(NODE *));
  
   newNode->next = NULL;
   newNode->data = data;

   return newNode;
}
/*
 * InsertLinkList()
 */
void insertLinkList()
{
  NODE *new, *temp;
  int k=1;

  int data, pos;

  printf(" Enter the Data to be inserted in Linklist\n");
  scanf("%d", &data);
            
  new = createLinkList(data);

  if(head == NULL)
  {
    head = new;
    head->next = head;
    last = head;
    return;
  }

  printf(" Enter the Position of Linklist\n");
  scanf("%d", &pos);

  if(pos ==1)
  {
    new->next = last->next;
    last->next = new;
    head = new;
    return;
  }
  temp = head;

  while ((k< pos-1) && (temp->next != head))
  {
    temp = temp->next;
    k++;

  }
  if(temp->next == head)
  {
    new->next = temp->next;
    temp->next = new;
    last = new;
  }
  else
  {
     new->next = temp->next;
     temp->next = new;
  }
}
/*
 * Delete
 */
void deleteLinkList(void)
{
  NODE *temp, *temp2;

  int k=1;

  int pos;

  printf(" Enter the Position of Node to be Deleted\n");
  scanf("%d", &pos);

  if(head !=NULL)
  {
    if(pos == 1)
    {
      if(head->next == head)
      {
         free(head);
         head= NULL;
      }
      else
      {
        temp2 = head;
        temp  = head->next;
        head->next = 0;
        head = temp;
        last->next = head;

        free(temp2);
        temp2= NULL;
      }
      return;
    }

    temp = head;
    while((k< pos-1) && (temp->next!= head))
    {
      temp = temp->next;
      k++;
    }
    if(temp->next == head)
    {
       temp2 = last->next;
       last->next = 0;
       temp->next = temp2;

       temp2 = last;
       last = temp;

       free(temp2);
       temp2 = NULL;
    }
    else
    {
       temp2= temp->next;
       temp->next = temp->next->next;
       free(temp2);
       temp2=NULL;
    }
   }
   else
   {
     printf("Nodes Are Empty \n");
     return;
   }
}
/*
 * Display()
 */
void display()
{
  NODE *temp;

  temp = head;
 
  printf("The Data is \n");
 
  if(temp != NULL)
  {
    if(temp == head)
      printf("%d\n", temp->data);

    temp = temp->next;

    while(temp!= head)
    {
      printf("%d\n", temp->data);
      temp = temp->next;
    }
  }
  else
  {
     printf(" Nodes are Empty \n");
  }
}

/*
 * Main()
 */
int main()
{
   int ch, data, pos;
   do
   {
     ch=0;
     printf("\n Enter the Choice \n");
     printf("1. Insert \n");
     printf("2. Delete \n");
     printf("3. Display \n");
     scanf("%d", &ch);
   
     switch(ch)
     {
        case 1:
              insertLinkList();
              break;
        case 2:
              deleteLinkList();
              break;
        case 3: display();
             break;

        default:
          printf("Invalid Choice \n");
          break;
      };
   }while(ch!=EXIT);
   return 0;
}