Basic Stack Operations in C

Basic stack operations in C

"A stack is a basic computer science data structure and can be defined in an abstract, implementation-free manner, or it can be generally defined as a linear list of items in which all additions and deletion are restricted to one end that is Top." - Wikipedia

	/**
	* A Stack is a last in, first out (LIFO) abstract data type and data
	* structure.It is characterized by three fundamental operations: push,
	* pop and stack top.
	* PUSH : The push operation adds a new item to the top of the stack, or
	* initializes the stack if it is empty, but if the stack is full and
	* does not contain more space to accept the given item it is considered
	* as an Overflow state (It means that the stack is overloaded or no more
	* space for new item).
	* POP : The pop operation removes an item from the top of the stack,
	* but if the stack is empty then it goes into underflow state (It means
	* no items are present in the stack to be removed).
	* STACK TOP : The stack top operation gets the data from the top-most
	* position and returns it to the user without deleting it. The same
	* underflow state can also occur in stack top operation if stack is empty.
	**/
	#include<stdio.h>
	#define MAX 50
	int main()
	{
	int stack[MAX], top = -1, e;
	int choice;
	void PUSH(int *, int, int *);
	void POP(int *, int *);
	void DISPLAY_TOP(int *, int *);
	while(1) {
	printf("\nMenu\n1.PUSH\n2.POP\n3.DISPLAY STACK TOP\n4.EXIT\n");
	printf("Type 1 to Push, 2 to Pop, 3 to display and 4 to Exit : \n");
	scanf("%d", &choice);
	switch(choice) {
	case 1:
	printf("Enter element to be pushed : \n");
	scanf("%d", &e);
	PUSH(stack, e, &top);
	break;
	case 2:
	POP(stack, &top);
	break;
	case 3:
	DISPLAY_TOP(stack, &top);
	break;
	case 4:
	exit(0);
	default:
	printf("Invalid entry!!\n");
	}
	}
	return 0;
	}
	void PUSH(int *stack, int item, int *top)
	{
	if((*top) == MAX - 1) {
	printf("Stack Overflow!\n");
	return;
	} else {
	stack[++(*top)] = item;
	printf("%d inserted\n", item);
	}
	}
	void POP(int *stack, int *top)
	{
	int item;
	if((*top) == -1) {
	printf("Stack underflow\n");
	} else {
	item = stack[(*top)];
	printf("Popped item : %d\n", item);
	(*top)--;
	}
	}
	void DISPLAY_TOP(int *stack, int *top)
	{
	int i;
	if(*top == -1)
	printf("Stack underflow\n");
	else {
	printf("The stack contents are :\n");
	for(i = 0; i <= (*top); i++)
	printf("%d ",stack[i]);
	printf("\nThe top of the stack : %d\n", stack[(*top)]);
	printf("\n");
	}
	}

view raw stack.c hosted with ❤ by GitHub

Written by Munia Balayil

Program to delete an element from an array in C

To delete an element from an array (in C)

	/**
	* Program to delete an element from an array
	**/
	#include<stdio.h>
	#include<stdlib.h>
	int main(void)
	{
	int *array, size;
	int e, i, pos;
	printf("\nEnter the size of the array : ");
	scanf("%d", &size);
	array = malloc(size * sizeof(int));
	printf("\nEnter the elements of the array : ");
	for(i = 0; i < size; i++)
	scanf("%d",&array[i]);
	printf("\nEnter the element to be deleted : ");
	scanf("%d", &e);
	printf("\n\nOriginal array size : %d", size);
	printf("\nOriginal array :\n");
	for(i = 0; i < size; i++)
	printf("%d ",array[i]);
	/* Find out position of 'e' in the array */
	for(pos = 0; pos < size; pos++)
	if(array[pos] == e)
	break;
	/* Shift the array elements backwards from 'pos' */
	for(i = pos; i < (size - 1); i++)
	array[i] = array[i + 1];
	array = realloc(array, (size - 1) * sizeof(int));
	/* Print updated array */
	printf("\n\nThe updated array size : %d", (size - 1));
	printf("\nThe updated array :\n");
	for(i = 0; i < (size - 1); i++)
	printf("%d ", array[i]);
	return 0;
	}

view raw del_array_element.c hosted with ❤ by GitHub

Written by Munia Balayil

Check the occurrence of a pattern in a string/text

	/**
	* Program to check the occurrences of a pattern in a text/string
	* This program checks whether the pattern occur in the string
	* or not, if yes at what positions and also print the text/string
	* highlighting the occurrences
	**/
	#include <stdio.h>
	#include<string.h>
	void check_substring(char *, char *);
	int main()
	{
	char str[500], substr[50];
	printf("\nEnter any string(Max length = 500 char):");
	fgets(str, 500, stdin);
	printf("\nEnter the pattern to be checked:");
	fgets(substr, 50, stdin);
	printf("\nstring = %s", str);
	printf("substring to be checked = %s", substr);
	check_substring(str, substr);
	return 0;
	}
	void check_substring(char *s, char *subs)
	{
	int i, j, k, no_of_occurence = 0;
	int l1, l2, f, pos;
	int position[100]; /* Keeps all positions where the
	substring occurs */
	l1 = strlen(s);
	printf("\n\nlength of string = %d", l1);
	l2 = strlen(subs);
	printf("\nlength of substring pattern being checked = %d", l2);
	k = 0;
	/* Traversing through the string */
	for(i = 0; i < l1; i++) {
	f = i;
	pos = i; /* Note the starting position */
	for(j = 0; j < l2; j++) {
	if(s[i] == subs[j])
	i++;
	else {
	i = f + 1;
	break;
	}
	}
	i--;
	/* On finding an occurrence */
	if(j >= l2) {
	/* Place start position in the position array */
	position[k++] = pos;
	no_of_occurence++;
	}
	}
	/* If the pattern occurs in the string/text */
	if(no_of_occurence > 0) {
	printf("\n\nThe substring occurs %d times at", no_of_occurence);
	/* Print all positions */
	for(i = 0; i < k; i++)
	printf("\nposition %d", position[i]);
	/* The string/text is printed with all occurrences enclosed
	between ^ and ^ */
	printf("\n\nThe text highlighting the occurrences of the substring\n ");
	k = 0;
	for(j = 0; j < l1; j++) {
	if(j == position[k])
	printf("^");
	printf("%c", s[j]);
	if(j == position[k] + l2 - 1) {
	printf("^");
	k++;
	}
	}
	}
	/* If the pattern does not occur in the string/text */
	else
	printf("\n\nThe substring does not occur in the string\n");
	}

view raw substring.c hosted with ❤ by GitHub

Written by Munia Balayil

Check if a String is Palindrome in C

"A palindrome is a word, phrase, number, or other sequence of units that may be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers." - Wikipedia

This is a C program to check if a given string is a palindrome or not.

	/**
	* A palindrome is a word, phrase, number or other sequence
	* of units that can be read the same way in either direction
	**/
	#include<stdio.h>
	#include<stdlib.h>
	#include<string.h>
	int main(void)
	{
	int i, j, l;
	char str1[20], str2[20];
	printf("Enter any word:");
	scanf("%s", str1);
	/* Find the length of the string */
	l = strlen(str1);
	j = 0;
	/* Store the reversed string in another string str2 */
	for(i = l - 1; i >= 0; i-- )
	str2[j++] = str1[i];
	str2[j] = '\0';
	/* Compare str1 and str2 */
	/* strcmp returns 0 when the strings are equal, */
	/* a negative integer when s1 is less than s2, */
	/* or a positive integer if s1 is greater than s2, */
	/* according to the lexicographical order. */
	if(strcmp(str1, str2) == 0)
	printf("The word is a palindrome\n");
	else
	printf("The word is not a palindrome\n");
	return 0;
	}

view raw palindrome.c hosted with ❤ by GitHub

Written by Munia Balayil

Factorial of a number in C - Iterative algorithm

	/**
	* To find the factorial of a number
	**/
	#include<stdio.h>
	#include<stdlib.h>
	int main(void)
	{
	int n, i, f;
	printf("Enter any number:");
	scanf("%d", &n);
	if(n < 0) {
	printf("\nFactorial does not exist for negative numbers\n");
	exit(0);
	}
	for(f = 1, i = n; i > 0; i--)
	f = f * i;
	printf("\nFactorial of %d is %d\n", n, f);
	return 0;
	}

view raw factorial.c hosted with ❤ by GitHub

Written by Munia Balayil

Check if a number is prime or not

	/**
	* To check whether a number is prime or not
	**/
	#include<stdio.h>
	#include<stdlib.h>
	int main(void)
	{
	int n, i, p = 1;
	printf("Enter any number:");
	scanf("%d", &n);
	/* 0 and 1 are neither a prime nor a composite number */
	if((n == 0) || (n == 1)) {
	printf("The number is neither prime nor composite\n");
	exit(0);
	}
	/* 2 is a prime number */
	if(n == 2) {
	printf("The number is prime\n");
	exit(0);
	}
	/* Check for all numbers other than 0, 1 and 2 */
	for(i = 2; i < n/2; i++)
	if(n % i == 0) {
	printf("Number is a composite number\n");
	p = 0;
	}
	if(p == 1)
	printf("The number is prime\n");
	return 0;
	}

view raw check_prime.c hosted with ❤ by GitHub

Written by Munia Balayil

Swapping without using temporary variable in C - XOR

	/**
	* Swapping without using a temporary variable in C
	* (XOR)
	**/
	#include<stdio.h>
	int main(void)
	{
	int a = 5; /* a = 0101 */
	int b = 10; /* b = 1010 */
	printf("Initially, a = %d and b = %d\n", a, b);
	a = a ^ b; /* a = 0101 XOR 1010 = 1111 */
	b = a ^ b; /* b = 1111 XOR 1010 = 0101 */
	a = a ^ b; /* a = 1111 XOR 0101 = 1010 */
	printf("After swapping, a = %d and b = %d\n", a, b);
	return 0;
	}

view raw swap_xor.c hosted with ❤ by GitHub

Written by Munia Balayil

Swapping without using temporary variable in C - Multiplication & Division

	/**
	* Swapping without using a temporary variable in C
	* (Multiplication & Division)
	**/
	#include<stdio.h>
	int main(void)
	{
	int a = 5, b = 10;
	printf("Initially, a = %d and b = %d\n", a, b);
	a = a * b; /* a = 5 * 10 = 50 */
	b = a / b; /* b = 50 / 10 = 5 */
	a = a / b; /* a = 50 / 5 = 10 */
	printf("After swapping, a = %d and b = %d\n", a, b);
	return 0;
	}

view raw swap_mul_div.c hosted with ❤ by GitHub

Written by Munia Balayil

Binary Search in C

"In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.[1][2] In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned." - Wikipedia

	/** Binary Search locates the position of an item in a sorted list.
	*
	* Divide : It works by dividing the list into two halves and
	* comparing the input value to be searched with the
	* middle element of the list.
	*
	* Conquer : If the input value is equal to the mid value, search
	* is successful. If greater, call binary search only
	* on the greater sub-array of the sorted list and if
	* lesser, call binary search on the lesser sub-array.
	* Continue this until you find the input value or you
	* reach a scenario where no match is found even after
	* the sub-array reduces to a size of 1.
	**/
	#include<stdio.h>
	int main(void)
	{
	int list[20], n, i, search_num, result;
	printf("Enter the size of the array:");
	scanf("%d", &n);
	printf("Enter the elements in the list in ascending order\n");
	for(i = 0; i < n; i++)
	scanf("%d", &list[i]);
	printf("Enter element to be searched:");
	scanf("%d", &search_num);
	result = binary_search(list, n, search_num);
	// binary_search returns -1 if search_num not found
	if(result == -1) {
	printf("No such element in the list.\n");
	printf("Search unsuccessful :-(\n");
	}
	// binary_search returns the position of the search_num
	// if element found in the list
	else {
	printf("Element found at location %d", result);
	printf("of the list(starting from zero)\n");
	}
	return 0;
	}
	int binary_search(int arr[], int size, int search_val)
	{
	int low, high, mid;
	low = 0;
	high = size - 1;
	while(low <= high) {
	mid = (low + high)/2;
	// if search_val = middle element return mid
	if(search_val == arr[mid])
	return mid;
	// if search_val < middle element search lower/lesser
	// half of the sorted list
	else if(search_val < arr[mid])
	high = mid - 1;
	// if search_val > middle element search higher/greater
	// half of the sorted list
	else if(search_val > arr[mid])
	low = mid + 1;
	}
	return -1;
	}

view raw binary_search.c hosted with ❤ by GitHub

Written by Munia Balayil

Swapping without using temporary variable in C - Addition & Subtraction

	/**
	* Swapping without using a temporary variable in C
	* (Addition & Subtraction)
	**/
	#include<stdio.h>
	int main(void)
	{
	int a = 5, b = 10;
	printf("Initially, a = %d and b = %d\n", a, b);
	a = a + b;
	b = a - b;
	a = a - b;
	printf("After swapping, a = %d and b = %d\n", a, b);
	return 0;
	}

view raw swap_add_mul.c hosted with ❤ by GitHub

Written by Munia Balayil

Quick Sort Using Recursion in C

"Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space." - Wikipedia

	/** Divide : Partition the array A[low....high] into two sub-arrays
	* A[low....j-1] and A[j+1...high] such that each element
	* of A[low....j-1] is less than or equal to A[j], which
	* in turn is is less than or equal to A[j+1...high]. Compute
	* the index j as part of this partitioning procedure.
	* Conquer : Sort the two sub-arrays A[low....j-1] and A[j+1....high]
	* by recursive calls to quicksort
	**/
	#include<stdio.h>
	int main()
	{
	int arr[20], n, i;
	printf("Enter the size of the array\n");
	scanf("%d", &n);
	printf("Enter the elements to be sorted\n");
	for(i = 0; i < n; i++)
	scanf("%d", &arr[i]);
	quicksort(arr, 0, n-1);
	printf("Sorted array\n");
	for(i = 0; i < n; i++)
	printf("%d ", arr[i]);
	return 0;
	}
	void quicksort(int *arr, int low, int high)
	{
	int pivot, i, j, temp;
	if(low < high) {
	pivot = low; // select a pivot element
	i = low;
	j = high;
	while(i < j) {
	// increment i till you get a number greater than the pivot element
	while(arr[i] <= arr[pivot] && i <= high)
	i++;
	// decrement j till you get a number less than the pivot element
	while(arr[j] > arr[pivot] && j >= low)
	j--;
	// if i < j swap the elements in locations i and j
	if(i < j) {
	temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	}
	}
	// when i >= j it means the j-th position is the correct position
	// of the pivot element, hence swap the pivot element with the
	// element in the j-th position
	temp = arr[j];
	arr[j] = arr[pivot];
	arr[pivot] = temp;
	// Repeat quicksort for the two sub-arrays, one to the left of j
	// and one to the right of j
	quicksort(arr, low, j-1);
	quicksort(arr, j+1, high);
	}
	}

view raw quick_sort.c hosted with ❤ by GitHub

Written by Munia Balayil