String Data Structure

Videos Tutorials on all the topics of String Data Structures

Computer were first used for processing numerical data but now computers are also used for processing non-numerical data like strings.

String: String is a collection of alphabetic letters (A-Z) numeric digits (0-9) and special characters (#,$,/) etc. Total number of symbol in a string is called length of string. A string with no symbol in it is called null or empty string. We can represent the end of the string by null character. Null character is the combination of back-slash with 0 (\0).

Importance of String: String is an important data structure. All of our word processing document making tasks heavily depends on the string data structure. Therefor handling string in computer science paly an important role.

String representation in memory: String is also an array of characters or symbols. We store each element of string in one memory location.

There are three types of strings.

1. Fixed Length strings
2. Variable length strings
3. Linked Strings

Fixed Length Strings: for the fixed length strings memory for storing a string is fixed. We fixed it when we declare a string variable but this way of storing and processing string may cause wastage of memory. For Example: If I want to save name “Ali” and declare string variable with 10 characters, I am going to waste the rest of 7 characters.

#include<iostream>
using namespace std;
int main()
{
char name[100];
cout<<"Enter your name";
cin.get(name, 100);
cout<<"The Name is "<<name;
}

Variable length String: This is a dynamic kind of string and you don’t need to declare the size of the string. These kind of strings have the ability to change their size during the program execution or say these kind of string can change their size on runtime and these strings are helpful as well to avoid the wastage of storage.

#include<iostream>
#include<string>
using namespace std;
int main()
{
//Variable length
string name;
cout<<"Enter Your name";
getline(cin,name);
cout<<"Your name is "<<name;
}

Q : How variable length strings are handled 🖐 in memory ? There are two ways of handling the variable length strings.

1. Boundary Marker
2. String Descriptor

1.Boundary Marker: A boundary marker is symbol like “ ↑ ” which we store at the end of string. So using this method we can store all the string one after other separated by the boundary marker.

2.String Descriptor: This method use the pointer - array to save the data. We have not studied the concepts of pointer based data structures yet so it will be difficult to understand the whole concept of string descriptors so for now understand it as this method use two fields to store a string.

1. Pointer Field: It contains the address of the first character of the string in memory. 2. Length Field : It contains the length of the strings.

For Example :

3.Linked String: In the linked type of storage for the strings we have nodes, A node is actually a sequence of memory cells. One node contains a fixed number of characters of a string and the other thing which the node contains is the pointer which stores the address of the next node. Which also holds the fixed length of characters for the string i.e. The next part of the string.

• Linked string is a good way to avoid memory wastage.
• It is also a good way for memory utilization

For Example: Let say a user want to save a large string into memory and we don't have enough memory in a sequence to store that string but we have memory in the form of small chunks which are located at random locations in memory. Individually those small chunks will be not enough to store the string but collectively they can. So we will brake that string into small fixed length of characters set, Store those small set into memory chunks. These chunks will also hold the addresses of the next chunk into the pointers which store the next part of the string.

String Operations: To some extent string data structure is also like array data structure but few operations of string data structure are different from array data structure and the reason of this difference is array data structure stores the individual elements in the array chambers where as the string data structures save the group of characters which are relevant to each other, which combines to make a word or sentence. We will go through all the string operations practically using C++ Code

1. Insertion operation

#include<iostream>
using namespace std;
int main()
{
//Fixed length
//old style of string
// c style string
char name[100];
cout<<"Enter a name";
cin>>name;
cout<<"Your Name is "<<name;
}

2. Deletion of sub string operation

#include<iostream>
#include<string>
using namespace std;
int main()
{
string myStr = "This is a Data Structure using C++ with Software Engineering Channel";
cout<<"Before Deletion-> "+myStr+"\n";
myStr.erase(1,8);
cout<<"After Deletion -> "+myStr;
}

3. String Copy Operation

#include <iostream>
using namespace std;
int main() {
char str1[100] = "Doctor_of_Computers";
char str2[100];
int i;
for(i = 0; str1[i] != '\0'; i++)
{
str2[i] = str1[i];
}
str2[i+1] = '\0';
cout<<"The string is in str2 now -> "<<str2;
return 0;
}

4. String Concatenation Operation

#include<iostream>
#include<string>
using namespace std;
int main()
{
string strOne;
string strTwo;
strOne = "Hammad";
strTwo = "Maqbool";
cout<<"My Name is "+strOne+" "+strTwo;
}

5. String Search Operation :

#include<iostream>
#include<string>
using namespace std;
int main()
{
string strOne;
string strTwo;
cout<<"Enter your first string\n";
getline(cin,strOne);
cout<<"Enter string you want to search";
getline(cin,strTwo);
cout << "The string is starting from location " << strOne.find(strTwo) << endl;
}