Category Archives: Data Structures

C++ program to find Factorial of a number.

 

Example of Factorial:
*************************************
Factorial of 1: 1
Factorial of 2: 2 x 1 = 2
Factorial of 3: 3 x 2 x 1 = 6
Factorial of 4: 4 x 3 x 2 x 1 = 24
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Iterative Factorial of n: n x (n-1) x (n-2) x . . . . .1
Recursive Factorial of n: n x Factorial of n-1
*************************************
Iterative program for factorial:

#include<iostream.h>
#include<conio.h>

void main()
{
	clrscr();

	int num, i, fact=1;

	cout<<"Enter an integer greater than or equal to 1: ";
	cin>>num;

	for(i=num; i>=1; i--)
	{
		fact = fact*i;
	}

	cout<<"Factorial of "<<num<<" is: "<<fact;

	getch();
}

Recursive program for factorial:

#include<iostream.h>
#include<conio.h>

int factorial(int n);

void main()
{
	clrscr();

	int num, fact;

	cout<<"Enter an integer greater than or equal to 1: ";
	cin>>num;

	fact = factorial(num);

	cout<<"Factorial of "<<num<<" is: "<<fact;

	getch();
}

int factorial(int n)
{
	int answer;

	if(n==1)
	{
		answer = 1;
	}
	else
	{
		answer = n * factorial(n-1);
	}

	return(answer);
}

C program to insert a node at front, at end, and at any position in a Single Linked List.

sll-insert.c

#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
	int data;
	struct node *link;
};

//Initialize 3 pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *temp;

//Prototypes for various user defined functions.
void insert_front();
void insert_end();
void insert_any();
void display();

void main()
{
	int choice;
	int cont = 1;

	//Allocate memory for header node.
	header = (struct node *) malloc(sizeof(struct node));

	clrscr();

	//Set the content of header node
	header->data = NULL;
	header->link = NULL;

	while(cont == 1)
	{
		//Display menu to the user
		printf("\n1. Insert at front\n");
		printf("\n2. Insert at end\n");
		printf("\n3. Insert at any position\n");
		printf("\n4. Display linked list\n");
		printf("\nEnter your choice: ");
		scanf("%d", &choice);

		switch(choice)
		{
			case 1:
				insert_front();
				break;
			case 2:
				insert_end();
				break;
			case 3:
				insert_any();
				break;
			case 4:
				display();
				break;
		}

		printf("\n\nDo you want to continue? (1 / 0): ");
		scanf("%d", &cont);
	}

	getch();
}

//Function to insert a node at the front of a single linked list.
void insert_front()
{
	int data_value;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);

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

	temp->data = data_value;
	temp->link = header->link;
	header->link = temp;
}

//Function to insert a node at the end of a single linked list.
void insert_end()
{
	int data_value;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);

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

	//Traverse to the end of the linked list.
	ptr = header;
	while(ptr->link != NULL)
	{
		ptr = ptr->link;
	}

	temp->data = data_value;
	temp->link = ptr->link;
	ptr->link = temp;
}

//Function to insert a node at any position after a particular node.
void insert_any()
{
	int data_value, key;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);
	printf("\nEnter data of the node after which new node is to be inserted: ");
	scanf("%d", &key);

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

	//Traverse till key is found or end of the linked list is reached.
	ptr = header;
	while(ptr->link != NULL && ptr->data != key)
	{
		ptr = ptr->link;
	}
	if(ptr->data == key)
	{
		temp->data = data_value;
		temp->link = ptr->link;
		ptr->link = temp;
	}
	else
	{
		printf("\nValue %d not found\n",key);
	}
}

//Function to display the contents of the linked list.
void display()
{
	printf("\nContents of the linked list are: \n");
	//Print the contents of the linked list starting from header
	ptr = header;
	while(ptr->link != NULL)
	{
		ptr = ptr->link;
		printf("%d ", ptr->data);
	}
}

C program to delete a node from front, from end, and from any position in a Single Linked List.

sll-delete.c

#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
	int data;
	struct node *link;
};

//Initialize pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *ptr1, *temp;

//Prototypes for various user defined functions.
void insert_end();
void delete_front();
void delete_end();
void delete_any();
void display();

void main()
{
	int choice;
	int cont = 1;

	//Allocate memory for header node.
	header = (struct node *) malloc(sizeof(struct node));

	clrscr();

	//Set the content of header node
	header->data = NULL;
	header->link = NULL;

	while(cont == 1)
	{
		//Display menu to the user
		printf("\n1. Insert at end\n");
		printf("\n2. Delete from front\n");
		printf("\n3. Delete from end\n");
		printf("\n4. Delete from anywhere\n");
		printf("\n5. Display linked list\n");
		printf("\nEnter your choice: ");
		scanf("%d", &choice);

		switch(choice)
		{
			case 1:
				insert_end();
				break;
			case 2:
				delete_front();
				break;
			case 3:
				delete_end();
				break;
			case 4:
				delete_any();
				break;
			case 5:
				display();
				break;
		}

		printf("\n\nDo you want to continue? (1 / 0): ");
		scanf("%d", &cont);
	}

	getch();
}

//Function to insert a node at the end of a single linked list.
void insert_end()
{
	int data_value;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);

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

	//Traverse to the end of the linked list.
	ptr = header;
	while(ptr->link != NULL)
	{
		ptr = ptr->link;
	}

	temp->data = data_value;
	temp->link = ptr->link;
	ptr->link = temp;
}

//Function to delete a node from the front of a linked list.
void delete_front()
{
	//If the list is already empty
	if(header->link == NULL)
	{
		printf("\nEmpty Linked List. Deletion not possible.\n");
	}
	else
	{
		ptr = header->link;
		header->link= ptr->link;
		free(ptr);
		printf("\nNode deleted from the front.\n");
	}	
}

//Function to delete a node from the end of a linked list.
void delete_end()
{
	if(header->link == NULL)
	{
		printf("\nEmpty Linked List. Deletion not possible.\n");
	}
	else
	{
		//Traverse to the end of the list.
		ptr = header;
		while(ptr->link != NULL)
		{
			ptr1 = ptr;
			ptr = ptr->link;
		}
		ptr1->link = ptr->link;
		free(ptr);
		printf("\nNode deleted from the end.\n");
	}
}

//Function to delete any node from linked list.
void delete_any()
{
	int key;

	if(header->link == NULL)
	{
		printf("\nEmpty Linked List. Deletion not possible.\n");
	}
	else
	{
		printf("\nEnter the data of the node to be deleted: ");
		scanf("%d", &key);

		ptr = header;
		while((ptr->link != NULL) && (ptr->data != key))
		{
			ptr1 = ptr;
			ptr = ptr->link;
		}
		if(ptr->data == key)
		{
			ptr1->link = ptr->link;
			free(ptr);
			printf("\nNode with data %d deleted.\n", key);
		}
		else
		{
			printf("\nValue %d not found. Deletion not possible.\n", key);
		}		
	}
}

//Function to display the contents of the linked list.
void display()
{
	printf("\nContents of the linked list are: \n");
	//Print the contents of the linked list starting from header
	ptr = header;
	while(ptr->link != NULL)
	{
		ptr = ptr->link;
		printf("%d ", ptr->data);
	}
}

C program for push, pop and peep operations in a stack using array.

stack.c

C program to implement push, pop and peep operations in a stack using an array is as follows:

#include<stdio.h>
#include<conio.h>

#define SIZE 5
int top = -1;
int stack[SIZE];

//Function prototypes
void push(int item);
int pop();
int peep();

void main()
{
	int item, choice, cont = 1;
	clrscr();

	while(cont == 1)
	{
		printf("\n1.Push onto stack.\n");
		printf("\n2.Pop from stack.\n");
		printf("\n3.Peep into stack.\n");

		printf("\nEnter your choice: ");
		scanf("%d",&choice);

		switch(choice)
		{
			case 1:
				printf("\nEnter the value of item: ");
				scanf("%d",&item);
				push(item);
				break;

			case 2:
				item = pop();
				if(item != NULL)
				{
					printf("\nItem popped out: %d\n",item);
				}				
				break;

			case 3:
				item = peep();
				if(item != NULL)
				{
					printf("\nItem at top of stack: %d\n",item);
				}				
				break;

			default:
				printf("\nInvalid choice.\n");
				break;
		}

		printf("\nDo you want to continue (1/0): ");
		scanf("%d",&cont);
	}

	getch();
}

//Function for push operation
void push(int item)
{
	if(top >= SIZE-1)
	{
		printf("\nStack Overflow. Push not possible.\n");
	}
	else
	{
		top = top+1;
		stack[top] = item;
	}
}

//Function for pop operation
int pop()
{
	int item = NULL;

	if(top <= -1)
	{
		printf("\nStack Underflow. Pop not possible.\n");
	}
	else
	{
		item = stack[top];
		stack[top] = NULL;
		top = top-1;
	}
	return(item);
}

//Function for peep operation
int peep()
{
	int item = NULL;

	if(top <= -1)
	{
		printf("\nStack Underflow. No element in stack.\n");
	}
	else
	{
		item = stack[top];
	}
	return(item);
}

C program to insert a node at front, at end, and at any position in a Circular Linked List.

cll-insert.c

C program to insert a node at front, at end, and at any position in a Circular Linked List is as follows:

#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
	int data;
	struct node *link;
};

//Initialize 3 pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *temp;

//Prototypes for various user defined functions.
void insert_front();
void insert_end();
void insert_any();
void display();

void main()
{
	int choice;
	int cont = 1;

	//Allocate memory for header node.
	header = (struct node *) malloc(sizeof(struct node));

	clrscr();

	//Set the content of header node
	header->data = NULL;
	header->link = header;

	while(cont == 1)
	{
		//Display menu to the user
		printf("\n1. Insert at front\n");
		printf("\n2. Insert at end\n");
		printf("\n3. Insert at any position\n");
		printf("\n4. Display linked list\n");
		printf("\nEnter your choice: ");
		scanf("%d", &choice);

		switch(choice)
		{
			case 1:
				insert_front();
				break;
			case 2:
				insert_end();
				break;
			case 3:
				insert_any();
				break;
			case 4:
				display();
				break;
		}

		printf("\n\nDo you want to continue? (1 / 0): ");
		scanf("%d", &cont);
	}

	getch();
}

//Function to insert a node at the front of a circular linked list.
void insert_front()
{
	int data_value;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);

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

	temp->data = data_value;
	temp->link = header->link;
	header->link = temp;
}

//Function to insert a node at the end of a circular linked list.
void insert_end()
{
	int data_value;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);

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

	//Traverse to the end of the linked list.
	ptr = header;
	while(ptr->link != header)
	{
		ptr = ptr->link;
	}

	temp->data = data_value;
	temp->link = ptr->link;
	ptr->link = temp;
}

//Function to insert a node at any position after a particular node.
void insert_any()
{
	int data_value, key;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);
	printf("\nEnter data of the node after which new node is to be inserted: ");
	scanf("%d", &key);

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

	//Traverse till key is found or end of the linked list is reached.
	ptr = header;
	while(ptr->link != header && ptr->data != key)
	{
		ptr = ptr->link;
	}
	if(ptr->data == key)
	{
		temp->data = data_value;
		temp->link = ptr->link;
		ptr->link = temp;
	}
	else
	{
		printf("\nValue %d not found\n",key);
	}
}

//Function to display the contents of the linked list.
void display()
{
	printf("\nContents of the linked list are: \n");
	//Print the contents of the linked list starting from header
	ptr = header;
	while(ptr->link != header)
	{
		ptr = ptr->link;
		printf("%d ", ptr->data);
	}
}

C program to delete a node from front, from end, and from any position in a Circular Linked List.

cll-delete.c

C program to delete a node from front, from end, and from any position in a Circular Linked List is as follows:

#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
	int data;
	struct node *link;
};

//Initialize pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *ptr1, *temp;

//Prototypes for various user defined functions.
void insert_end();
void delete_front();
void delete_end();
void delete_any();
void display();

void main()
{
	int choice;
	int cont = 1;

	//Allocate memory for header node.
	header = (struct node *) malloc(sizeof(struct node));

	clrscr();

	//Set the content of header node
	header->data = NULL;
	header->link = header;

	while(cont == 1)
	{
		//Display menu to the user
		printf("\n1. Insert at end\n");
		printf("\n2. Delete from front\n");
		printf("\n3. Delete from end\n");
		printf("\n4. Delete from anywhere\n");
		printf("\n5. Display linked list\n");
		printf("\nEnter your choice: ");
		scanf("%d", &choice);

		switch(choice)
		{
			case 1:
				insert_end();
				break;
			case 2:
				delete_front();
				break;
			case 3:
				delete_end();
				break;
			case 4:
				delete_any();
				break;
			case 5:
				display();
				break;
		}

		printf("\n\nDo you want to continue? (1 / 0): ");
		scanf("%d", &cont);
	}

	getch();
}

//Function to insert a node at the end of a circular linked list.
void insert_end()
{
	int data_value;

	printf("\nEnter data of the node: ");
	scanf("%d", &data_value);

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

	//Traverse to the end of the linked list.
	ptr = header;
	while(ptr->link != header)
	{
		ptr = ptr->link;
	}

	temp->data = data_value;
	temp->link = ptr->link;
	ptr->link = temp;
}

//Function to delete a node from the front of a linked list.
void delete_front()
{
	//If the list is already empty
	if(header->link == header)
	{
		printf("\nEmpty Linked List. Deletion not possible.\n");
	}
	else
	{
		ptr = header->link;
		header->link= ptr->link;
		free(ptr);
		printf("\nNode deleted from the front.\n");
	}	
}

//Function to delete a node from the end of a linked list.
void delete_end()
{
	if(header->link == header)
	{
		printf("\nEmpty Linked List. Deletion not possible.\n");
	}
	else
	{
		//Traverse to the end of the list.
		ptr = header;
		while(ptr->link != header)
		{
			ptr1 = ptr;
			ptr = ptr->link;
		}
		ptr1->link = ptr->link;
		free(ptr);
		printf("\nNode deleted from the end.\n");
	}
}

//Function to delete any node from linked list.
void delete_any()
{
	int key;

	if(header->link == header)
	{
		printf("\nEmpty Linked List. Deletion not possible.\n");
	}
	else
	{
		printf("\nEnter the data of the node to be deleted: ");
		scanf("%d", &key);

		ptr = header;
		while((ptr->link != header) && (ptr->data != key))
		{
			ptr1 = ptr;
			ptr = ptr->link;
		}
		if(ptr->data == key)
		{
			ptr1->link = ptr->link;
			free(ptr);
			printf("\nNode with data %d deleted.\n", key);
		}
		else
		{
			printf("\nValue %d not found. Deletion not possible.\n", key);
		}		
	}
}

//Function to display the contents of the linked list.
void display()
{
	printf("\nContents of the linked list are: \n");
	//Print the contents of the linked list starting from header
	ptr = header;
	while(ptr->link != header)
	{
		ptr = ptr->link;
		printf("%d ", ptr->data);
	}
}

C program to convert from Infix to Postfix.

infix-to-postfix.c

C program to convert an arithmetic expression given in Infix notation to Postfix notation is as follows:

#include<stdio.h>
#include<conio.h>

#define SIZE 100

int top = -1;
char stack[SIZE];

//Function prototypes
void push(char item);
char pop();
int is_operator(char symbol);
int precedence(char symbol);

void main()
{
	int i, j;
	char infix_exp[SIZE], postfix_exp[SIZE];
	char item, x;
	clrscr();

	printf("\nEnter the arithmetic expression in Infix notation enclosed in parentheses: \n");
	gets(infix_exp);

	i = 0;
	j = 0;
	item = infix_exp[i++];
	//Read symbol from Input string one at a time.
	while(item != '\0')
	{
		//If the symbol is left parenthesis
		if(item == '(')
		{
			push(item);
		}
		//If the symbol is an operand
		else if((item >= 'A'  && item <= 'Z') || (item >= 'a' && item <= 'z'))
		{
			postfix_exp[j++] = item;
		}
		//If the symbol is an operator
		else if(is_operator(item) == 1)
		{
			x = pop();
			while(is_operator(x) == 1 && precedence(x) >= precedence(item))
			{
				postfix_exp[j++] = x;
				x = pop();
			}
			push(x);
			push(item);			
		}
		//If the symbol is a right parenthesis
		else if(item == ')')
		{
			x = pop();
			while(x != '(')
			{
				postfix_exp[j++] = x;
				x = pop();
			}
		}
		//If the symbol is any other invalid character
		else
		{
			printf("\nInvalid Arithmetic Expression.\n");
			getch();
			exit(0);
		}

		item = infix_exp[i++];
	}

	postfix_exp[j++] = '\0';
	printf("\nArithmetic expression in Postfix notation: ");
	puts(postfix_exp);

	getch();
}

//Function for push operation
void push(char item)
{
	if(top >= SIZE-1)
	{
		printf("\nStack Overflow. Push not possible.\n");
	}
	else
	{
		top = top+1;
		stack[top] = item;
	}
}

//Function for pop operation
char pop()
{
	char item = NULL;

	if(top <= -1)
	{
		printf("\nStack Underflow. Pop not possible.\n");
	}
	else
	{
		item = stack[top];
		stack[top] = NULL;
		top = top-1;
	}
	return(item);
}

//Function to check whether the symbol is an operator.
int is_operator(char symbol)
{
	if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol == '-')
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//Function which returns the precedence of the operator.
int precedence(char symbol)
{
	if(symbol == '^')
	{
		return(3);
	}
	else if(symbol == '*' || symbol == '/')
	{
		return(2);
	}
	else if(symbol == '+' || symbol == '-')
	{
		return(1);
	}
	else
	{
		return(0);
	}
}

C program to insert and delete elements from a Queue.

queue.c

C program to insert (Enqueue) and delete (Dequeue) elements from a simple Queue which is implemented using an array is as follows:

#include<stdio.h>
#include<conio.h>

#define SIZE 5
int front = -1;
int rear = -1;
int queue[SIZE];

//Function prototypes
void enqueue(int item);
int dequeue();

void main()
{
	int item, choice, cont = 1;
	clrscr();

	while(cont == 1)
	{
		printf("\n1.Enqueue into queue.\n");
		printf("\n2.Dequeue from queue.\n");

		printf("\nEnter your choice: ");
		scanf("%d",&choice);

		switch(choice)
		{
			case 1:
				printf("\nEnter the value of item: ");
				scanf("%d",&item);
				enqueue(item);
				break;

			case 2:
				item = dequeue();
				if(item != NULL)
				{
					printf("\nItem dequeued: %d\n",item);
				}				
				break;

			default:
				printf("\nInvalid choice.\n");
				break;
		}

		printf("\nDo you want to continue (1/0): ");
		scanf("%d",&cont);
	}

	getch();
}

//Function for push operation
void enqueue(int item)
{
	if(rear >= SIZE-1)
	{
		printf("\nQueue is full. Enqueue not possible.\n");
	}
	else
	{
		if(front == -1 && rear == -1)
		{
			front = front + 1;
		}
		rear = rear + 1;
		queue[rear] = item;
		printf("\nItem enqueued: %d\n", item);
	}
}

//Function for pop operation
int dequeue()
{
	int item = NULL;

	if(front == -1 && rear == -1)
	{
		printf("\nQueue is empty. Dequeue not possible.\n");
	}
	else
	{
		item = queue[front];
		queue[front] = NULL;

		if(front == rear)
		{
			front = -1;
			rear = -1;
		}
		else
		{
			front = front + 1;
		}
	}
	return(item);
}

C program to insert and delete elements in a Circular Queue.

circular-queue.c

C program to insert (Enqueue) and delete (Dequeue) elements in a Circular Queue which is implemented using an array is as follows:

#include<stdio.h>
#include<conio.h>

#define SIZE 5
int front = -1;
int rear = -1;
int queue[SIZE];

//Function prototypes
void enqueue_cq(int item);
int dequeue_cq();

void main()
{
	int item, choice, cont = 1;
	clrscr();

	while(cont == 1)
	{
		printf("\n1.Enqueue into circular queue.\n");
		printf("\n2.Dequeue from circular queue.\n");

		printf("\nEnter your choice: ");
		scanf("%d",&choice);

		switch(choice)
		{
			case 1:
				printf("\nEnter the value of item: ");
				scanf("%d",&item);
				enqueue_cq(item);
				break;

			case 2:
				item = dequeue_cq();
				if(item != NULL)
				{
					printf("\nItem dequeued: %d\n",item);
				}				
				break;

			default:
				printf("\nInvalid choice.\n");
				break;
		}

		printf("\nDo you want to continue (1/0): ");
		scanf("%d",&cont);
	}

	getch();
}

//Function for push operation
void enqueue_cq(int item)
{
	int next;

	if(front == -1 && rear == -1)
	{
		front = front + 1;
		rear = rear + 1;
		queue[rear] = item;
		printf("\nItem enqueued: %d\n", item);
	}
	else
	{
		next = ((rear == (SIZE-1)) ? (rear % (SIZE-1)) : ((rear % (SIZE-1)) + 1));
		if(next == front)
		{
			printf("\nQueue is full. Enqueue not possible.\n");
		}
		else
		{
			rear = next;
			queue[rear] = item;
			printf("\nItem enqueued: %d\n", item);
		}
	}
}

//Function for pop operation
int dequeue_cq()
{
	int item = NULL;

	if(front == -1 && rear == -1)
	{
		printf("\nQueue is empty. Dequeue not possible.\n");
	}
	else
	{
		item = queue[front];
		queue[front] = NULL;

		if(front == rear)
		{
			front = -1;
			rear = -1;
		}
		else
		{
			front = ((front == (SIZE-1)) ? (front % (SIZE-1)) : ((front % (SIZE-1)) + 1));
		}
	}
	return(item);
}