#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];
}
}
