Data structure parts

DATA STRUCTURE :-

• BASIC CONCEPT : 

1. Introduction to Complexity.
2. Data Structure and Data Structure operations. 
3. Applications of Data Structure.
4. Basic data Structures.     

• ARRAYS :

1. Introduction.
2. Types of Array.
3. Memory representation.
4. Applications and operations.

• STACKS :

1. Introduction.
2. memory representation.
3. Applications and operations.

• LINKED LIST :

1. Operations:-traversing.
2. searching.
3. inserting.
4. deleting.
5. operations oh header linked list.
6. circular linked list.
7. doubly linked list.
8. memory representation.
9. Applications.
10. polynomial manipulation.

• QUEUE :

1. Introduction.
2. Types.
3. Memory Representation and Applications.

• TREES :

1. Definition and Basic concepts.
2. Representation in Contiguous Storage.
3. Binary Tree.
4. Binary Tree Traversal.
5. Searching.
6. Insertion and deletion in Binary trees.
7. Binary Search tree.

• GRAPHS :

1. Introduction.
2. Memory Representation.
3. Graph Traversal (DFS and BFS).

• SEARCHING :

1. Binary search.
2. Linear search.

• SORTING :

1. Bubble Sort.
2. Insertion Sort.
3. Selection Sort.
4. Merge Sort.
5. Quick Sort.
6. Comparison of various Searching and Sorting algorithms.

Basic operation performed in graph

/*Basic operation performed in graph*/

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

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
    struct AdjListNode *head;
};

// A structure to represent a graph. A graph
// is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
    struct AdjListNode* newNode =
     (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph =
        (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists.  Size of
    // array will be V
    graph->array =
      (struct AdjList*) malloc(V * sizeof(struct AdjList));

    // Initialize each adjacency list as empty by
    // making head as NULL
    int i;
    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{

    // Add an edge from src to dest.  A new node is  
        // added to the adjacency list of src.  The node
    // is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from
    // dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// A utility function to print the adjacency list
// representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

// Driver program to test above functions
int main()
{
    // create the graph given in above fugure
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // print the adjacency list representation of the above graph
    printGraph(graph);

    return 0;
}

----------------------------------------------------------
OUTPUT:-
   

sk.

Depth First Search (DFS) Program in C

/*Depth First Search (DFS) Program in C */

#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]
void main()
{
    int i,j;
    printf("Enter number of vertices:");
scanf("%d",&n);
    //read the adjecency matrix
printf("\nEnter adjecency matrix of the graph:");
for(i=0;i<n;i++)
       for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
    //visited is initialized to zero
   for(i=0;i<n;i++)
        visited[i]=0;
    DFS(0);
}
void DFS(int i)
{
    int j;
printf("\n%d",i);
    visited[i]=1;

for(j=0;j<n;j++)
       if(!visited[j]&&G[i][j]==1)
            DFS(j);

}

----------------------------------------------------------
OUTPUT:-

sk.

C programming code for binary search

/*C programming code for binary search*/

#include <stdio.h>

 

int main()

{

   int c, first, last, middle, n, search, array[100];

 

   printf("Enter number of elements\n");

   scanf("%d",&n);

 

   printf("Enter %d integers\n", n);

 

   for (c = 0; c < n; c++)

      scanf("%d",&array[c]);

 

   printf("Enter value to find\n");

   scanf("%d", &search);

 

   first = 0;

   last = n - 1;

   middle = (first+last)/2;

 

   while (first <= last) {

      if (array[middle] < search)

         first = middle + 1;    

      else if (array[middle] == search) {

         printf("%d found at location    %d.\n", search, middle+1);

         break;

      }

      else

         last = middle - 1;

 

      middle = (first + last)/2;

   }

   if (first > last)

      printf("Not found! %d isn't present in the list.\n", search);

 

   return 0;  

}

----------------------------------------------------------

OUTPUT:-

sk.

Binary search tree

/*Binary search tree*/    


#include<stdio.h>
#include<stdlib.h> 
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
} 
struct node* insert(struct node* root, int data)
{
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left  = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data); 
    return root;

}
void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}
int main(){
    struct node *root = NULL;
    root = insert(root, 8);
    insert(root, 3);
    insert(root, 1);
    insert(root, 6);
    insert(root, 7);
    insert(root, 10);
    insert(root, 14);
    insert(root, 4);
    inorder(root);
}

----------------------------------------------------------
OUTPUT:-

sk.

Insertion sort algorithm implementation in C

/*Insertion sort algorithm implementation in C*/

/* Insertion sort ascending order */

 

#include <stdio.h>

 

int main()

{

  int n, array[1000], c, d, t;

 

  printf("Enter number of elements\n");

  scanf("%d", &n);

 

  printf("Enter %d integers\n", n);

 

  for (c = 0; c < n; c++)

    scanf("%d", &array[c]);

 

  for (c = 1 ; c <= n - 1; c++) {

    d = c;

 

    while ( d > 0 && array[d-1] > array[d]) {

      t          = array[d];

      array[d]   = array[d-1];

      array[d-1] = t;

 

      d--;

    }

  }

 

  printf("Sorted list in ascending order:\n");

 

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

 

  return 0;

}

----------------------------------------------------------

OUTPUT:-

sk.

Merge Sort Program in C

/*Merge Sort Program in C*/

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)   
      b[i++] = a[l1++];
   while(l2 <= high) 
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
void sort(int low, int high) {
   int mid;
 
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else {
      return;
   } 
}

int main()
{
     int i;
   printf("List before sorting\n");
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
   sort(0, max);
   printf("\nList after sorting\n");
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}

----------------------------------------------------------
OUTPUT:-

sk.

Selection sort algorithm implementation in C

/*Selection sort algorithm implementation in C*/

#include <stdio.h>

 

int main()

{

  int array[100], n, c, d, position, swap;

 

  printf("Enter number of elements\n");

  scanf("%d", &n);

 

  printf("Enter %d integers\n", n);

 

  for (c = 0; c < n; c++)

    scanf("%d", &array[c]);

 

  for (c = 0; c < (n - 1); c++)

  {

    position = c;

   

    for (d = c + 1; d < n; d++)

    {

      if (array[position] > array[d])

        position = d;

    }

    if (position != c)

    {

      swap = array[c];

      array[c] = array[position];

      array[position] = swap;

    }

  }

 

  printf("Sorted list in ascending order:\n");

 

  for (c = 0; c < n; c++)

    printf("%d\n", array[c]);

 

  return 0;

}

----------------------------------------------------------

OUTPUT:-

sk.

Program in C to implement all the operations of doubly linked list

/*Program in C to implement all the operations of doubly linked list*/

#include<stdio.h>  

#include<stdlib.h>  

struct node  

{  

    struct node *prev;  

    struct node *next;  

    int data;  

};  

struct node *head;  

void insertion_beginning();  

void insertion_last();  

void insertion_specified();  

void deletion_beginning();  

void deletion_last();  

void deletion_specified();  

void display();  

void search();  

void main ()  

{  

int choice =0;  

    while(choice != 9)  

    {  

        printf("\n*********Main Menu*********\n");  

        printf("\nChoose one option from the following list ...\n");  

        printf("\n===============================================\n");  

        printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n  

        5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");  

        printf("\nEnter your choice?\n");  

        scanf("\n%d",&choice);  

        switch(choice)  

        {  

            case 1:  

            insertion_beginning();  

            break;  

            case 2:  

                    insertion_last();  

            break;  

            case 3:  

            insertion_specified();  

            break;  

            case 4:  

            deletion_beginning();  

            break;  

            case 5:  

            deletion_last();  

            break;  

            case 6:  

            deletion_specified();  

            break;  

            case 7:  

            search();  

            break;  

            case 8:  

            display();  

            break;  

            case 9:  

            exit(0);  

            break;  

            default:  

            printf("Please enter valid choice..");  

        }  

    }  

}  

void insertion_beginning()  

{  

   struct node *ptr;   

   int item;  

   ptr = (struct node *)malloc(sizeof(struct node));  

   if(ptr == NULL)  

   {  

       printf("\nOVERFLOW");  

   }  

   else  

   {  

    printf("\nEnter Item value");  

    scanf("%d",&item);  

      

   if(head==NULL)  

   {  

       ptr->next = NULL;  

       ptr->prev=NULL;  

       ptr->data=item;  

       head=ptr;  

   }  

   else   

    {  

       ptr->data=item;  

       ptr->prev=NULL;  

       ptr->next = head;  

       head->prev=ptr;  

       head=ptr;  

   }  

   printf("\nNode inserted\n");  

}  

     

}  

void insertion_last()  

{  

   struct node *ptr,*temp;  

   int item;  

   ptr = (struct node *) malloc(sizeof(struct node));  

   if(ptr == NULL)  

   {  

       printf("\nOVERFLOW");  

   }  

   else  

   {  

       printf("\nEnter value");  

       scanf("%d",&item);  

        ptr->data=item;  

       if(head == NULL)  

       {  

           ptr->next = NULL;  

           ptr->prev = NULL;  

           head = ptr;  

       }  

       else  

       {  

          temp = head;  

          while(temp->next!=NULL)  

          {  

              temp = temp->next;  

          }  

          temp->next = ptr;  

          ptr ->prev=temp;  

          ptr->next = NULL;  

          }  

             

       }  

     printf("\nnode inserted\n");  

    }  

void insertion_specified()  

{  

   struct node *ptr,*temp;  

   int item,loc,i;  

   ptr = (struct node *)malloc(sizeof(struct node));  

   if(ptr == NULL)  

   {  

       printf("\n OVERFLOW");  

   }  

   else  

   {  

       temp=head;  

       printf("Enter the location");  

       scanf("%d",&loc);  

       for(i=0;i<loc;i++)  

       {  

           temp = temp->next;  

           if(temp == NULL)  

           {  

               printf("\n There are less than %d elements", loc);  

               return;  

           }  

       }  

       printf("Enter value");  

       scanf("%d",&item);  

       ptr->data = item;  

       ptr->next = temp->next;  

       ptr -> prev = temp;  

       temp->next = ptr;  

       temp->next->prev=ptr;  

       printf("\nnode inserted\n");  

   }  

}  

void deletion_beginning()  

{  

    struct node *ptr;  

    if(head == NULL)  

    {  

        printf("\n UNDERFLOW");  

    }  

    else if(head->next == NULL)  

    {  

       head = NULL;   

        free(head);  

        printf("\nnode deleted\n");  

    }  

    else  

    {  

        ptr = head;  

        head = head -> next;  

        head -> prev = NULL;  

        free(ptr);  

        printf("\nnode deleted\n");  

    }  

  

}  

void deletion_last()  

{  

    struct node *ptr;  

    if(head == NULL)  

    {  

        printf("\n UNDERFLOW");  

    }  

    else if(head->next == NULL)  

    {  

        head = NULL;   

        free(head);   

        printf("\nnode deleted\n");  

    }  

    else   

    {  

        ptr = head;   

        if(ptr->next != NULL)  

        {  

            ptr = ptr -> next;   

        }  

        ptr -> prev -> next = NULL;   

        free(ptr);  

        printf("\nnode deleted\n");  

    }  

}  

void deletion_specified()  

{  

    struct node *ptr, *temp;  

    int val;  

    printf("\n Enter the data after which the node is to be deleted : ");  

    scanf("%d", &val);  

    ptr = head;  

    while(ptr -> data != val)  

    ptr = ptr -> next;  

    if(ptr -> next == NULL)  

    {  

        printf("\nCan't delete\n");  

    }  

    else if(ptr -> next -> next == NULL)  

    {  

        ptr ->next = NULL;  

    }  

    else  

    {   

        temp = ptr -> next;  

        ptr -> next = temp -> next;  

        temp -> next -> prev = ptr;  

        free(temp);  

        printf("\nnode deleted\n");  

    }     

}  

void display()  

{  

    struct node *ptr;  

    printf("\n printing values...\n");  

    ptr = head;  

    while(ptr != NULL)  

    {  

        printf("%d\n",ptr->data);  

        ptr=ptr->next;  

    }  

}   

void search()  

{  

    struct node *ptr;  

    int item,i=0,flag;  

    ptr = head;   

    if(ptr == NULL)  

    {  

        printf("\nEmpty List\n");  

    }  

    else  

    {   

        printf("\nEnter item which you want to search?\n");   

   scanf("%d",&item);  

        while (ptr!=NULL)  

        {  

            if(ptr->data == item)  

            {  

                printf("\nitem found at location %d ",i+1);  

                flag=0;  

                break;  

            }   

            else  

            {  

                flag=1;  

            }  

            i++;  

            ptr = ptr -> next;  

        }  

        if(flag==1)  

        {  

            printf("\nItem not found\n");  

        }  

    }     

          

}  

----------------------------------------------------------

OUTPUT:-

sk.

Program to delete node of Linked List

/*Program to delete node of Linked List*/

/**
 * C program to delete first node from Singly Linked List
 */

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


/* Structure of a node */
struct node {
    int data;          // Data
    struct node *next; // Address
}*head;


void createList(int n);
void deleteFirstNode();
void displayList();



int main()
{
    int n, choice;

    /*
     * Create a singly linked list of n nodes
     */
    printf("Enter the total number of nodes: ");
    scanf("%d", &n);

    createList(n);
    printf("\nData in the list \n");
    displayList();

    printf("\nPress 1 to delete first node: ");
    scanf("%d", &choice);

    /* Delete first node from list */
    if(choice == 1)
        deleteFirstNode();

    printf("\nData in the list \n");
    displayList();

    return 0;
}


/*
 * Create a list of n nodes
 */
void createList(int n)
{
    struct node *newNode, *temp;
    int data, i;

    head = (struct node *)malloc(sizeof(struct node));

    /*
     * If unable to allocate memory for head node
     */
    if(head == NULL)
    {
      printf("Unable to allocate memory.");
    }
    else
    {
        /*
         * In data of node from the user
         */
        printf("Enter the data of node 1: ");
        scanf("%d", &data);

        head->data = data; // Link the data field with data
        head->next = NULL; // Link the address field to NULL

        temp = head;

        /*
         * Create n nodes and adds to linked list
         */
        for(i=2; i<=n; i++)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            /* If memory is not allocated for newNode */
            if(newNode == NULL)
            {
                printf("Unable to allocate memory.");
                break;
            }
            else
            {
                printf("Enter the data of node %d: ", i);
                scanf("%d", &data);
               newNode->data = data; // Link the data field of newNode with data
                newNode->next = NULL; // Link the address field of newNode with NULL

                temp->next = newNode; // Link previous node i.e. temp to the newNode
                temp = temp->next;
            }
        }

        printf("SINGLY LINKED LIST CREATED SUCCESSFULLY\n");
    }
}


/*
 * Deletes the first node of the linked list
 */
void deleteFirstNode()
{
    struct node *toDelete;

    if(head == NULL)
    {
        printf("List is already empty.");
    }
    else
    {
        toDelete = head;
        head = head->next;

        printf("\nData deleted = %d\n", toDelete->data);

        /* Clears the memory occupied by first node*/
        free(toDelete);
       printf("SUCCESSFULLY DELETED FIRST NODE FROM LIST\n");
    }
}


/*
 * Displays the entire list
 */
void displayList()
{
    struct node *temp;

    /*
     * If the list is empty i.e. head = NULL
     */
    if(head == NULL)
    {
        printf("List is empty.");
    }
    else
    {
        temp = head;
        while(temp != NULL)
        {
            printf("Data = %d\n", temp->data); // Print data of current node
            temp = temp->next;                 // Move to next node
        }
    }
}

----------------------------------------------------------OUTPUT:-

sk.