EC8381 - Fundamentals of Data Structures in C Lab

1. Looping and Arrays

a) Multiplication Table Using for Loop

#include<stdio.h>

#include<conio.h>

void main()

{

 int n,i,mult;

 clrscr();

 printf("Enter a number:\n");

 scanf("%d",&n);

 for(i=1;i<=10;i++)

 {

  mult=n*i;

  printf("%d*%d=%d\n",n,i,mult);

 }

 getch();

}

b) Sum of Even Numbers Using while Loop

#include<stdio.h>

#include<conio.h>

void main()

{

 int n,i=0,sum=0;

 clrscr();

 printf("Enter the limit:\n");

 scanf("%d",&n);

 printf("Sum of Even Numbers from 0 to %d\n",n);

 while(i<=n)

 {

  sum=sum+i;

  i=i+2;

 }

 printf("%d",sum);

 getch();

}

c) Sum of Digits Using while Loop

#include<stdio.h>

#include<conio.h>

void main()

{

 int n,sum=0,rem;

 clrscr();

 printf("Enter a Number:\n");

 scanf("%d",&n);

 while(n!=0)

 {

  rem=n%10;

  sum=sum+rem;

  n=n/10;

 }

 printf("Sum Of Digit=%d",sum);

 getch();

}

d) Determine Whether the Number is Palindrome or not

#include<stdio.h>

#include<conio.h>

void main()

{   

 int n1,n2,digit,rev=0;

 clrscr();

 printf("Enter a number:\n");

 scanf("%d",&n1);

 n2=n1;

 while(n2!=0)

 {

  digit=n2%10;

  rev=(rev*10)+digit;

  n2=n2/10;

 }

 if(n1==rev)

 {

  printf("The number is a palindrome");

 }

 else

 {

  printf("The number is not a palindrome");

 }

 getch();

}

e) Determine Whether the Number is Armstrong or not

#include<stdio.h>

#include<conio.h>

void main()

{

 int n1,n2,rem,sum=0;

 clrscr();

 printf("\nEnter a Number:\n");

 scanf("%d",&n1);

 n2=n1;

 while(n2!=0)

 {

  rem=n2%10;

  sum=sum+(rem*rem*rem);

  n2=n2/10;

 }

 if(sum==n1)

 {

  printf("Armstrong Number");

 }

 else

 {

  printf("Not an Armstrong Number ");

 }

 getch();

}

f) Generating Prime Numbers

#include<stdio.h>

#include<conio.h>

void main()

{

 int no,i,count,remainder;

 clrscr();

 for(no=2;no<=50;no++)

 {

  i=1,count=0;

  while(i<=no)

  {

   remainder=no%i;

   if(remainder==0)

   {

    count=count+1;

   }

   i++;

  }

  if(count==2)

  {

   printf("%d\n",no);

  }

 }

 getch();

}

g) Array Sorting

#include<stdio.h>

#include<conio.h>

void main()

{

 int n,i,j,a[30],temp;

 clrscr();

 printf("Enter the limit:\n");

 scanf("%d",&n);

 printf("Enter the array elements:\n");

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

 {

  scanf("%d",&a[i]);

 }

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

 {

  for(j=i+1;j<n;j++)

  {

   if(a[i]>a[j])

   {

    temp=a[i];

    a[i]=a[j];

    a[j]=temp;

   }

  }

 }

 printf("Array Elements in Ascending Order:\n");

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

 {

  printf("%d\n",a[i]);

 }

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

 {

  for(j=i+1;j<n;j++)

  {

   if(a[i]<a[j])

   {

    temp=a[i];

    a[i]=a[j];

    a[j]=temp;

   }

  }

 }

 printf("Array Elements in Descending Order:\n");

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

 {

  printf("%d\n",a[i]);

 }

 getch();

}

2. String Operations

#include<stdio.h>

#include<conio.h>

void main()

{

 char str1[30],str2[30];

 clrscr();

 printf("Enter string1:");

 gets(str1);

 printf("Enter string2:");

 gets(str2);

 printf("\nLength of string1:%d",strlen(str1));

 printf("\nLength of string2:%d",strlen(str2));

 strcat(str1,str2);

 printf("\nConcatenated String:");

 puts(str1);

 getch();

}

3. Structures and Pointers

a) Student Details Using Structure

#include<stdio.h>

#include<conio.h>

struct stud

{

 char name[25];

 int rno;

 int m1;

 int m2;

 int m3;

 int total;

 float avg;

};

struct stud s[10];

void main()

{

 int n,i;

 clrscr();

 printf("Enter the limit:");

 scanf("%d",&n);

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

 {

  printf("Enter the name,rollno,and marks:\n");

  scanf("%s",&s[i].name);

  scanf("%d",&s[i].rno);

  scanf("%d",&s[i].m1);

  scanf("%d",&s[i].m2);

  scanf("%d",&s[i].m3);

  s[i].total=s[i].m1+s[i].m2+s[i].m3;

  s[i].avg=s[i].total/3;

 }

 printf("\nSTUDENT DETAILS\n\n");

 printf("Name\tRollNo\tMark1\tMark2\tMark3\tTotal\tAverage\n");

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

 {

 printf("%s\t%d\t%d\t%d\t%d\t%d\t%f\n",s[i].name,s[i].rno,s[i].m1,s[i].m2,s[i].m3,s[i].total,s[i].avg);

 }

 getch();

}

b) Simple Program Using Pointer

#include <stdio.h>

void main()

{

 int *ptr;

 int c = 33;

 ptr= &c;

 printf("Value of variable c is: %d", c);

 printf("\nValue of variable c is: %d", *ptr);

 printf("\nAddress of variable c is: %p", &c);

 printf("\nAddress of variable c is: %p", ptr);

 printf("\nAddress of pointer ptr is: %p", &ptr);

}

c) Swapping Using Pointer

#include <stdio.h>
void main()
{
 int x, y, *a, *b, temp;
 printf("Enter the value of x and y\n");
 scanf("%d%d", &x, &y);
 printf("Before Swapping x = %d, y = %d\n", x, y);
 a = &x;
 b = &y;
 temp = *b;
 *b = *a;
 *a = temp;
 printf("After Swapping x = %d, y = %d\n", x, y);
}

4. Dynamic Memory Allocations

a) Sum of n Numbers Using malloc() Function

#include <stdio.h>
#include <stdlib.h>
void main()
{
 int num, i, *ptr, sum = 0;
 printf("Enter number of elements: ");
 scanf("%d", &num);
 ptr = (int*) malloc(num * sizeof(int));
 if(ptr == NULL)                   
 {
  printf("Error! memory not allocated.");
  exit(0);
 }
 printf("Enter the elements ");
 for(i = 0; i < num; i++)
 {
  scanf("%d", ptr + i);
  sum = sum + *(ptr + i);
 }
 printf("Sum = %d", sum);
 free(ptr);
}

b) Sum of n Numbers Using calloc() Function

#include <stdio.h>
#include <stdlib.h>
void main()
{
 int num, i, *ptr, sum = 0;
 printf("Enter number of elements: ");
 scanf("%d", &num);
 ptr = (int*) calloc(num, sizeof(int));
 if(ptr == NULL)
 {
  printf("Error! memory not allocated.");
  exit(0);
 }
 printf("Enter elements of array: ");
 for(i = 0; i < num; i++)
 {
  scanf("%d", ptr + i);
  sum = sum + *(ptr + i);
 }
 printf("Sum = %d", sum);
 free(ptr);
}

c) Reallocation of Memory Using realloc() Function

#include <stdio.h>
#include <stdlib.h>
void main()
{
 int *ptr, i , n1, n2;
 printf("Enter size of array:");
 scanf("%d", &n1);
 ptr = (int*) malloc(n1 * sizeof(int));
 printf("Address of previously allocated memory: ");
 for(i = 0; i < n1; ++i)
 printf("%u\t",ptr + i);
 printf("\nEnter new size of array: ");
 scanf("%d", &n2);
 ptr = realloc(ptr, n2);
 printf("Address of Reallocated memory: ");
 for(i = 0; i < n2; ++i)
 printf("%u\t", ptr + i);
}

5. Stack

a) Array Implementation of Stack

#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
void main()
{
 top=-1;
 printf("ARRAY IMPLEMENTATION OF STACK\n");
 printf("Enter the size of Stack [MAX=100]:");
 scanf("%d",&n);
 printf("1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT");
 do
 {
  printf("\nEnter the Choice:");
  scanf("%d",&choice);
  switch(choice)
  {
   case 1:
   push();
   break;
   case 2:
   pop();
   break;
   case 3:
   display();
   break;
   case 4:
   break;
   default:
   printf ("Please Enter a Valid Choice(1/2/3/4)");   
  }
 }
 while(choice!=4);
}
void push()
{
 if(top>=n-1)
 {
  printf("Stack is over flow"); 
 }
 else
 {
  printf("Enter a value to be inserted:");
  scanf("%d",&x);
  top++;
  stack[top]=x;
 }
}
void pop()
{
 if(top<=-1)
 {
  printf("Stack is under flow");
 }
 else
 {
  printf("The popped elements is %d",stack[top]);
  top--;
 }
}
void display()
{
 if(top>=0)
 {
  printf("The elements in Stack");
  for(i=top; i>=0; i--)
  printf("\n%d",stack[i]);
 }
 else
 {
  printf("The Stack is empty");
 }
}

b) Linked List Implementation of Stack

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct Node
{
 int data;
 struct Node *next;
}
*top = NULL;
int choice, value;
void push();
void pop();
void display();
void main()
{
 printf("LINKED LIST IMPLEMENTATION OF STACK\n");
 printf("1.Push\n2.Pop\n3.Display\n4.Exit");
 while(choice!=4)
 {
  printf("Enter your choice: ");
  scanf("%d",&choice);
  switch(choice)
  {
   case 1:
   push();
   break;
   case 2:
   pop();
   break;
   case 3:
   display();
   break;
   case 4:
   exit(0);
   default:
   printf("Wrong Choice!! Please Enter a Valid Choice(1/2/3/4)\n");
  }
 }
}
void push()
{
 printf("Enter the value to be inserted: ");
 scanf("%d", &value);
 struct Node *newNode;
 newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = value;
 if(top == NULL)
 {
  newNode->next = NULL;
 }
 else
 {
  newNode->next = top;
 }
 top = newNode;
 printf("Insertion is Success!!!\n");
}
void pop()
{
 if(top == NULL)
 {
  printf("Stack is Empty!!!\n");
 }
 else
 {
  struct Node *temp = top;
  printf("Deleted element: %d\n", temp->data);
  top = temp->next;
  free(temp);
 }
}
void display()
{
 if(top == NULL)
 {
  printf("Stack is Empty!!!\n");
 }
 else
 {
  struct Node *temp = top;
  while(temp->next != NULL)
  {
   printf("%d--->",temp->data);
   temp = temp -> next;
  }
  printf("%d--->NULL\n",temp->data);
 }
}

6. Queue

a) Array Implementation of Queue

#include<stdio.h>
#include<conio.h>
#define n 100
int queue[n],ch,front=0,rear=0,i,j=1,x=n;
void enqueue(void);
void dequeue(void);
void display(void);
void main()
{
 printf("ARRAY IMPLEMENTATION OF QUEUE");
 printf("\n1.Enqueue \n2.Dequeue \n3.Display \n4.Exit\n");
 do
 {
  printf("Enter the Choice:");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
   enqueue();
   break;
   case 2:
   dequeue();
   break;
   case 3:
   display();
   break;
   case 4:
   break;
   default:
   printf("Wrong Choice!! Please Enter a Valid Choice(1/2/3/4)\n");
  }
 }
 while(ch!=4);
}
void enqueue()
{
 if(rear==x)
 {
  printf("Queue is Full\n");
 }
 else
 {
  printf("Enter the value to be inserted:");
  scanf("%d",&queue[rear++]);
 }
}
void dequeue()
{
 if(front==rear)
 {
  printf("Queue is empty\n");
 }
 else
 {
  printf("Deleted Element is %d\n",queue[front++]);
  x++;
 }
}
void display()
{
 if(front==rear)
 {
  printf("Queue is Empty\n");
 }
 else
 {
  printf("Queue Elements are:\n");
  for(i=front; i<rear; i++)
  {
   printf("%d\n",queue[i]);
  }
 }
}

b) Linked List Implementation of Queue

#include<stdio.h>
#include<conio.h>
struct Node
{
 int data;
 struct Node *next;
}*front = NULL,*rear = NULL;
void enqueue(void);
void dequeue(void);
void display(void);
int choice, value;
void main()
{
 printf("Linked List Implementation of Queue\n");
 printf("\n1.Enqueue \n2.Dequeue \n3.Display \n4.Exit\n");
 do
 {
  printf("Enter your choice: ");
  scanf("%d",&choice);
  switch(choice)
  {
   case 1:
   enqueue();
   break;
   case 2:
   dequeue();
   break;
   case 3:
   display();
   break;
   case 4:
   break;
   default: printf("Please Enter a Valid Choice(1/2/3/4\n");
  }
 }
 while(choice!=4);
}
void enqueue()
{
 printf("Enter the value to be insert: ");
 scanf("%d", &value);
 struct Node *newNode;
 newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = value;
 newNode -> next = NULL;
 if(front == NULL)
 front = rear = newNode;
 else
 {
  rear -> next = newNode;
  rear = newNode;
 }
 printf("Insertion is Success!\n");
}
void dequeue()
{
 if(front == NULL)
 printf("Queue is Empty\n");
 else
 {
  struct Node *temp = front;
  front = front -> next;
  printf("Deleted element: %d\n", temp->data);
  free(temp);
 }
}
void display()
{
 if(front == NULL)
 printf("Queue is Empty!\n");
 else
 {
  struct Node *temp = front;
  while(temp->next != NULL)
  {
   printf("%d--->",temp->data);
   temp = temp -> next;
  }
  printf("%d--->NULL\n",temp->data);
 }
}

7. Application of Stack (Reverse a String)

#include <stdio.h>
#include <string.h>
#define max 100
int top,stack[max];
void push(char);
void pop();
void main()
{
 char str[]="INDIA";
 int len = strlen(str);
 int i;
 for(i=0;i<len;i++)
 {
  push(str[i]);
 }
 for(i=0;i<len;i++)
 {
  pop();
 }
}
void push(char x)
{
 if(top == max-1)
 {
  printf("stack overflow");
 }
 else
 {
  stack[++top]=x;
 }
} 
void pop()
{
 printf("%c",stack[top--]);
}

8. Implementation of Tree Traversals

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* newNode(int data)
{
 struct node* node = (struct node*)malloc(sizeof(struct node));
 node->data = data;
 node->left = NULL;
 node->right = NULL;
 return(node);
}
void printPostorder(struct node* node)
{
 if (node == NULL)
 return;
 printPostorder(node->left);
 printPostorder(node->right);
 printf("%d ", node->data);
}
void printInorder(struct node* node)
{
 if (node == NULL)
 return;
 printInorder(node->left);
 printf("%d ", node->data);
 printInorder(node->right);
}
void printPreorder(struct node* node)
{
 if (node == NULL)
 return;
 printf("%d ", node->data);
 printPreorder(node->left);
 printPreorder(node->right);
} 
void main()
{
 struct node *root = newNode(1);
 root->left = newNode(2);
 root->right = newNode(3);
 root->left->left = newNode(4);
 root->left->right = newNode(5);
 printf("Preorder traversal of binary tree is: ");
 printPreorder(root);
 printf("\nInorder traversal of binary tree is: ");
 printInorder(root);
 printf("\nPostorder traversal of binary tree is: ");
 printPostorder(root);
}

9. Implementation Binary Search Tree

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int key;
 struct node *left, *right;
};
struct node *newNode(int item)
{
 struct node *temp =  (struct node *)malloc(sizeof(struct node));
 temp->key = item;
 temp->left = temp->right = NULL;
 return temp;
}
void inorder(struct node *root)
{
 if (root != NULL)
 {
  inorder(root->left);
  printf("%d \n", root->key);
  inorder(root->right);
 }
}
struct node* insert(struct node* node, int key)
{
 if (node == NULL)
 {
  return newNode(key);
 }
 if (key < node->key)
 {
  node->left  = insert(node->left, key);
 }
 else if (key > node->key)
 {
  node->right = insert(node->right, key);
 } 
 return node;
}
void main()
{
 struct node *root = NULL;
 root = insert(root, 50);
 insert(root, 30);
 insert(root, 20);
 insert(root, 40);
 insert(root, 70);
 insert(root, 60);
 insert(root, 80);
 inorder(root);
}

10. Searching

a) Implementation of Linear Search

#include<stdio.h>
void main()
{
  int a[100], search, i, n;
  printf("Enter the number of elements: ");
  scanf("%d", &n);
  printf("Enter %d elements\n", n);
  for (i = 0; i < n; i++)
  scanf("%d", &a[i]);
  printf("Enter a number to search\n");
  scanf("%d", &search);
  for (i = 0; i < n; i++)
  {
   if (a[i] == search)
   {
    printf("%d is present at location %d\n", search, i+1);
    break;
   }
  }
  if (i == n)
  printf("%d is not present in the array\n", search);
}

b) Implementation of Binary Search

#include<stdio.h>
#include<conio.h>
void main()
{
 int n, i, j, a[50], temp, search, first, last, middle;
 printf("Enter total number of elements :");
 scanf("%d",&n);
 printf("Enter %d elements in ascending order:\n", n);
 for (i=0; i<n; i++)
 {
  scanf("%d",&a[i]);
 }
 printf("Enter a number to find :");
 scanf("%d", &search);
 first = 0;
 last = n-1;
 middle = (first+last)/2;
 while (first <= last)
 {
  if(a[middle] < search)
  {
   first = middle + 1;
  }
  else if(a[middle] == search)
  {
   printf("%d is found at location %d\n", search, middle+1);
   break;
  }
  else
  {
   last = middle - 1;
  }
  middle = (first + last)/2;
 }
 if(first > last)
 {
  printf("%d is not present in the list",search);
 }
}

11. Sorting

a) Implementation of Insertion Sort

#include<stdio.h>
void main()
{
 int i,j,n,temp,a[30];
 printf("Enter the number of elements:");
 scanf("%d",&n);
 printf("Enter the elements\n");
 for(i=0;i<n;i++)
 {
  scanf("%d",&a[i]);
 }
 for(i=1;i<=n-1;i++)
 {
  temp=a[i];
  j=i-1;
  while((temp<a[j])&&(j>=0))
  {
   a[j+1]=a[j];
   j=j-1;
  }
  a[j+1]=temp;
 }
 printf("Elements after sorting\n");
 for(i=0;i<n;i++)
 {
  printf("%d\n",a[i]);
 }
}

b) Implementation of Bubble Sort

#include<stdio.h>
void main()
{
 int a[50],n,i,j,temp;
 printf("Enter the number of elements: ");
 scanf("%d",&n);
 printf("Enter the elements:\n");
 for(i=0;i<n;++i)
 {
  scanf("%d",&a[i]);
 }
 for(i=1;i<n;++i)
 {
  for(j=0;j<(n-i);++j)
  {
   if(a[j]>a[j+1])
   {
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
   }
  }
 }
 printf("Elements after sorting:\n");
 for(i=0;i<n;++i)
 {
  printf("%d\n",a[i]);
 }
}

c) Implementation of Quick Sort

#include<stdio.h>
void quick_sort(int a[20],int,int);
void main()
{
 int a[20],n,i;
 printf("Enter the number of elements: ");
 scanf("%d",&n);
 printf("Enter %d elements:\n",n);
 for(i=0 ; i<n ; i++)
 {
  scanf("%d",&a[i]);
 }
 quick_sort(a,0,n-1);
 printf("Elements after sorting:\n");
 for(i=0 ; i<n ; i++)
 {
  printf("%d\n",a[i]);
 }
}
void quick_sort(int a[20],int low,int high)
{
 int pivot,j,temp,i;
 if(low<high)
 {
  pivot = low;
  i = low;
  j = high;
  while(i<j)
  {
   while((a[i]<=a[pivot])&&(i<high))
   {
    i++;
   }
   while(a[j]>a[pivot])
   {
    j--;
   }
   if(i<j)
   {
     temp=a[i];
     a[i]=a[j];
     a[j]=temp;
   }
  }
  temp=a[pivot];
  a[pivot]=a[j];
  a[j]=temp;
  quick_sort(a,low,j-1);
  quick_sort(a,j+1,high);
 }
}

d) Implementation of Merge Sort

#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
void main()
{
 int a[30],n,i;
 printf("Enter the number of elements:");
 scanf("%d",&n);
 printf("Enter the elements:\n");
 for(i=0;i<n;i++)
 {
  scanf("%d",&a[i]);
 }
 mergesort(a,0,n-1);
 printf("Elements after sorting:\n");
 for(i=0;i<n;i++)
 {
  printf("%d\n",a[i]);
 }
}
void mergesort(int a[],int i,int j)
{
 int mid;
 if(i<j)
 {
  mid=(i+j)/2;
  mergesort(a,i,mid);
  mergesort(a,mid+1,j);
  merge(a,i,mid,mid+1,j);
 }
}
void merge(int a[],int i1,int j1,int i2,int j2)
{
 int temp[50];
 int i,j,k;
 i=i1;
 j=i2;
 k=0;
 while(i<=j1 && j<=j2)
 {
  if(a[i]<a[j])
  temp[k++]=a[i++];
  else
  temp[k++]=a[j++];
 }
 while(i<=j1)
 {
  temp[k++]=a[i++];
 }
 while(j<=j2)
 {
  temp[k++]=a[j++];
 }
 for(i=i1,j=0;i<=j2;i++,j++)
 {
  a[i]=temp[j];
 }
}