Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced

String Operations in Data Structures

Operations on Strings

  • Reversing the order of words in a sentence

Reversing a string is a technique that reverses or alters the order of a given string so that the last character becomes the first character, and so on. We may also test the Palindrome of a given string by reversing the original string.

For instance, we may type "JAVATPOINT" and then use the reverse procedure. The reverse algorithm returns "TNIOPTAVAJ," which is the inverse of the original string.

REVERSING A STRING

Operations on Strings

In C, there are several methods for finding the inverse of a string.

  1. The strrev() method is used to reverse a string.
  2. Without using the library function, reverse a string
  3. Using a for loop, reverse a string
  4. Using a while loop, reverse a string

1. The strrev() method is used to reverse a string.

#include <stdio.h>  
#include <string.h>  
int main()  
{  
    char reverse_string[40]; // declare the length of the character string
    printf (" \n Type a string to be reversed: ");  
    scanf ("%s", reverse_string);  
          
    // To reverse a string, use the strrev() method.
    printf (" \n Following is the string's reversal: %s ", strrev(reverse_string));  
    return 0;  
}  

The following output should be generated by this programme:

Output

Type a string to be reversed: JAVATPOINT
Following is the string's reversal: TNIOPTAVAJ

2. Without using the library function, reverse a string

#include <stdio.h>  
#include <string.h>  
      
// stringreverse() function definition
void stringreverse(char *reverse_string)  
{  
    // variable declaration
    int i, len, temp;  
    len = strlen(reverse_string); // To get the length of the reverse string string, use strlen().
          
    // To iterate the string, use a for loop.
    for (i = 0; i < len/2; i++)  
    {  
        // The temp variable is used to temporarily store the string.           	temp = reverse_string[i];  
        reverse_string [i] = reverse_string [len - i - 1];  
        reverse_string [len - i - 1] = temp;  
    }  
}  
          
int main()  
{  
    char reverse_string [50]; // char string length  
    printf (" Enter the following string: ");  
    gets(reverse_string); // To take a string, use the gets() method.
          
    printf (" \n Before you reverse the string:%s \n", reverse_string);  
              
    // use the stringreverse () function
    stringreverse (reverse_string);  
    printf (" After reversing the string: %s", reverse_string);  
}

The following output should be generated by this programme:

Output

Enter the following string: Welcome to JavaTPoint


Before you reverse the string: Welcome to JavaTPoint
After reversing the string: tnioPTavaJ ot emocleW

3. Using a for loop, reverse a string.

#include <stdio.h>  
#include <conio.h>  
#include <string.h>  
void main()  
{  
	char reverse_string[50], temp; // set the size of the reverse_string[] array	
	int i, left, right, len;  
	printf (" \n Show a reverse string in C:\n");  
	printf (" ----------------------- ");  
	printf (" \n Enter the following string to reverse the order:");  
	scanf( "%s", &reverse_string);  
	len = strlen(reverse_string); // get the string's length
	left = 0; // set the left index to 0
	right = len - 1; // set the correct index len - 1
	// To save the reverse string, use a for loop.  
	for (i = left; i <right; i++)  
	{  
		temp = reverse_string[i];  
		reverse_string[i] = reverse_string[right];  
		reverse_string[right] = temp;  
		right--;  
	}  
	printf ("The original string's inverse is: %s ", reverse_string);  
	getch();  
}

The following output should be generated by this programme:

Output

Show a reverse string in C:
 -----------------------
Enter the following string to reverse the order: JAVATPOINT
The original string's inverse is: TNIOPTAVAJ

4. Using a while loop, reverse a string.

#include <stdio.h>  
#include <string.h>  
int main()  
{  
	char reverse_string[50], temp; // declare and initialise the string array's size
	int i = 0, j =0;  
	printf ("Enter the following string to be reversed: ");  
	scanf( "%s", reverse_string);  
	j = strlen (reverse_string) - 1;  // get the string's length  


	// To specify the condition, use a while loop.	
	while ( i < j)   
	{  
		// use a temp variable to hold the reverse_string characters  
		temp = reverse_string[j];  
		reverse_string[j] = reverse_string[i];  
		reverse_string[i] = temp;  
		i++; // i increased by one
		j--; // j is reduced by one
	}  
	printf ("The string in reverse: %s", reverse_string);  
	return 0;  
}

The following output should be generated by this programme:

Output

Enter the following string to be reversed: JAVATPOINT
The string in reverse: TNIOPTAVAJ
  • To duplicate one string to another
#include <stdio.h>
#include <string.h>
#include <stdlib.h>




void main()
{
    char string_1[100], string_2[100];
    int  i;


       printf("\n\n Copy one string and paste it into another.:\n");
       printf("-----------------------------------------\n"); 	
       printf("Enter the string here.: ");
       fgets(string_1, sizeof(string_1), stdin);
	   
    /* string1 to string2 is copied character by character. */
    i=0;
    while(string_1[i]!='\0')
    {
        string_2[i] = string_1[i];
        i++;
    }


    // Ensures that the string is finished with a NULL.
    string_2[i] = '\0';


    printf("\nThe Initial string is : %s\n", string_1);
    printf("The Copied string is : %s\n", string_2);
    printf("Number of characters copied : %d\n\n", i);
}

The following output should be generated by this programme:

Output

Copy one string and paste it into another.:                                                                         
-----------------------------------------                                                                     
Enter the string here.: Greetings from JavaTPoint.                                                             
                                                                                                              
The Initial string is : Greetings from JavaTPoint.                                                          
                                                                                                              
The Copied string is : Greetings from JavaTPoint.                                                         
                                                                                                              
Number of characters copied : 26
  • Detecting a palindrome

A palindrome number is one that is the same after being reversed. Palindrome numbers include 171, 14641, 838, 9123219, and 48984.

Algorithm for palindrome numbers

  • Obtain the number from the user
  • Keep the value in a temporary variable.
  • Reverse the digits
  • Compare the temporary and reversed numbers.
  • If the numbers are the same, print a palindrome.
  • Otherwise, print a number that is not a palindrome.

C programme for palindromes

#include <stdio.h>  
#include <conio.h>  
#include <string.h>  
void main()  
{  
	char reverse_string[50], temp; // set the size of the reverse_string[] array	
	int i, left, right, len;  
	printf (" \n Show a reverse string in C:\n");  
	printf (" ----------------------- ");  
	printf (" \n Enter the following string to reverse the order:");  
	scanf( "%s", &reverse_string);  
	len = strlen(reverse_string); // get the string's length
	left = 0; // set the left index to 0
	right = len - 1; // set the correct index len - 1
	// To save the reverse string, use a for loop.  
	for (i = left; i <right; i++)  
	{  
		temp = reverse_string[i];  
		reverse_string[i] = reverse_string[right];  
		reverse_string[right] = temp;  
		right--;  
	}  
	printf ("The original string's inverse is: %s ", reverse_string);  
	getch();  
} 

The following output should be generated by this programme:

Output

Show a reverse string in C:
 -----------------------
Enter the following string to reverse the order: JAVATPOINT
The original string's inverse is: TNIOPTAVAJ
  • Counting the number of words in a string

In this programme, we must count the words in the string.

As an example:

Hello and welcome to JavaTpoint! We hope we were able to provide you with what you were searching for.

There are a total of 19 words in the string.

Counting the total amount of words in a string algorithm

  • Create a string.
  • We'll loop through the string and count the spaces to see how many words there are. Because each word is always followed by a space.
  • If a string begins with a space, the initial space should not be counted because it is not preceded by a word.
  • We'll add one to the total to count the last word.

C programme for Counting the total amount of words in a string

#include <stdio.h>  
#include <string.h>  
   
int main()  
{  
	char sentence_string[] = "Hello and welcome to JavaTpoint! We hope we were able to provide you with what you were searching for.";  
	int wordCount = 0;  
  
	for(int i = 0; i < strlen(sentence_string)-1; i++) {  
		// Counts the number of gaps in the string.  
		// It excludes the initial space since it is not considered a word.
		if(sentence_string[i] == ' ' && isalpha(sentence_string[i+1]) && (i > 0)) {  
			wordCount++;  
		}  
	}
	// Increase wordCount by 1 to count the last word in the string.	wordCount++;  
  
	// The total number of words in the provided string is shown.
	printf("The total number of words in the string is: %d", wordCount);  
   
	return 0;  
} 

The following output should be generated by this programme:

Output

The total number of words in the string is: 19
  • Determining the number of repeated words within a string

We need to locate and display the duplicate words in the string in this software.

big black bug bit a big black dog on his big black nose  

We initially break the string into words in order to locate the duplicate words. We count how many times each word appears in the string. If the count is larger than one, the string contains a duplicate word.

Algorithm for number of repeated words within a string

  • Create a string.
  • To make the comparison insensitive, convert the string to lowercase.
  • Make a word out of the string.
  • To discover duplicate words, two loops will be employed. The outer loop will choose a word and set the variable count to one. The word chosen by the outer loop will be compared against the remainder of the words in the inner loop.
  • If a match is detected, increase the count by one and make the duplicates of the word '0' to prevent counting it again.
  • If the count of a word is more than one after the inner loop, the word contains duplicates in the string.

C programme for Counting number of repeated words within a string

#include <stdio.h>  
#include <string.h>  
       
int main()  
{     
    char string_array[] = "big black bug bit a big black dog on his big black nose";  
    char words_array[100][100];  
    int i = 0, j = 0, k, length, count;  
          
    // Split the string_array into words, with each row of the words_array representing a single word.  
    for(k=0; string_array[k]!='\0'; k++){  
              
        // The two-dimensional array words_array is represented by the letters i and j.
        if(string_array[k] != ' ' && string_array[k] != '\0'){  
            // The string array is converted to lowercase and added to the words array array.  
            words_array[i][j++] = tolower(string_array[k]);  
        }  
        else{  
            words_array[i][j] = '\0';  
            // To store a new term, increase the row count.  
            i++;  
            //Set column count to 0  
            j = 0;  
        }  
    }  
          
    // Count the number of rows in a variable-length table.  
    length = i+1;  
          
    printf("In the provided string array, there are duplicate words:\n");  
    for(i = 0; i < length; i++){  
        count = 1;  
        for(j = i+1; j < length; j++){  
           if(strcmp(words_array[i], words_array[j]) == 0 && (strcmp(words_array[j],"0") != 0)){  
               count++;  
               // To prevent publishing the visited word, set words array[j] to 0.
               strcpy(words_array[j],"0");  
           }   
        }  
        // If the count is more than one, the duplicate word is shown.
        if(count > 1 )  
            printf("%s\n", words_array[i]);  
    }  
    
    return 0;  
} 

The following output should be generated by this programme:

Output

In the provided string array, there are duplicate words: 
big
black
  • Determine whether the first string is a subsequence of the second

Determine whether string_1 is a subsequence of string_2 given two strings, string_1 and string_2. A subsequence is a sequence that may be created by eliminating some components from another sequence without altering the order of the remaining elements. Time complexity is assumed to be linear. As an example:

  • Input: string_1 = "ABC", string_2 = "ABCXYZ"
  • Output: True (string_1 is a subsequence of string_2)
  • Input: string_1 = "APY", string_2 = "YADXCP"
  • Output: False (string_1 is not a subsequence of string_2)
  • Input: string_1 = "java", string_2 = "javatpoint"
  • Output: True (string_1 is a subsequence of string_2)

The goal here is to see if the length of the longest common subsequence is the same as string_1. If it's equal, it signifies that string_2 contains a subsequence. The implementation utilising the memoization approach is shown below.

C programme for checking whether the first string is a subsequence of the second

// Check if a string is a subsequence of another string with a C++ application.
#include <bits/stdc++.h>
using namespace std;


int arr[1001][1001];


// The length of the longest common subsequence is returned.
int isSubSequence(string& string_1, string& string_2, int i, int j)
{
	if (i == 0 || j == 0) {
		return 0;
	}
	if (arr[i][j] != -1) {
		return arr[i][j];
	}
	if (string_1[i - 1] == string_2[j - 1]) {
		return arr[i][j]
			= 1 + isSubSequence(string_1, string_2, i - 1, j - 1);
	}
	else {
		return arr[i][j] = isSubSequence(string_1, string_2, i, j - 1);
	}
}


/* To test the aforementioned function, using the driver program. */
int main()
{
	string str1 = "jvtont";
	string str2 = "javatpoint";
	int m = str1.size();
	int n = str2.size();
	if (m > n) {
		cout << "NO" << endl;
		return 0;
	}
	arr[m][n];
	memset(arr, -1, sizeof(arr));
	if (isSubSequence(str1, str2, m, n) == m) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

The following output should be generated by this programme:

Output

YES



ADVERTISEMENT
ADVERTISEMENT