Data Structures Using C++

 

Introduction to Data Structures

• Definition: A data structure is a way of organizing and storing data so that it can be accessed and used efficiently.
• Importance: Data structures are crucial for solving problems efficiently, optimizing memory usage, and improving algorithm performance.
• Applications: Data structures are used in databases, file systems, operating systems, and many algorithms.

Classification of Data Structures

• Linear Data Structures: Data elements are stored in a sequence, where each element has a predecessor and successor. Examples include arrays, linked lists, stacks, and queues.
• Non-linear Data Structures: Data elements are arranged in a hierarchical or graph-like structure, where elements are connected in multiple ways. Examples include trees and graphs.

Review of C++ Basics

• Syntax: The set of rules that defines the structure of valid C++ code.
• Variables: Containers that hold data values, like integers, floats, and characters.
• Control Structures: Statements that control the flow of execution in a program, such as loops (for, while) and conditionals (if, else).
• Functions: Blocks of code that perform specific tasks and can be reused throughout the program.

Arrays

• Introduction: An array is a collection of elements of the same type, stored in contiguous memory locations. It allows for efficient access to data using an index.
• Declaration: To create an array, you specify the data type, array name, and size. For example:
  int arr[5]; (declares an array of 5 integers).
• Initialization: Arrays can be initialized at the time of declaration. Example:
  int arr[] = {1, 2, 3, 4, 5};
• Basic Operations:
  • Accessing Elements: You can access array elements using an index, e.g., arr[0] for the first element.
  • Updating Elements: You can modify an array element using its index, e.g., arr[2] = 10;
  • Traversing Arrays: To access or modify all elements, use a loop. Example:

    
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    

Multidimensional Arrays and their Applications

• Introduction: Multidimensional arrays are arrays of arrays. A two-dimensional array can be thought of as a table with rows and columns.
• Declaration: Example for a 2D array: int arr[3][4]; (declares a 2D array with 3 rows and 4 columns).
• Initialization: You can initialize a 2D array with values:

  
  int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
  

• Accessing Elements: To access an element in a 2D array, use two indices, e.g., arr[1][2] to access the element in the second row, third column.
• Applications:
• Matrices: Multidimensional arrays are often used to represent matrices in mathematical computations.
• Images: In computer graphics, 2D arrays can represent pixels in an image (rows and columns of pixels).
• Tables: They are used to represent data in tabular form, such as spreadsheets.

Strings: Implementation using Arrays

• Introduction: In C++, a string is an array of characters terminated by a special character called the null character ('\0').
• Declaration: A string can be declared as a character array. Example:
  char str[20]; (a string that can hold up to 19 characters and the null character).
• Initialization: You can initialize a string by assigning a string literal:

  
  char str[] = "Hello";
  

  This automatically adds the null character at the end.

Common String Operations

• Concatenation: The process of joining two strings together. In C++, we use strcat() function to concatenate strings:

  
  char str1[20] = "Hello ";
  char str2[] = "World";
  strcat(str1, str2);  // str1 becomes "Hello World"
  

• Comparison: To compare two strings, use the strcmp() function. It returns:
  • 0 if the strings are equal.
  • A negative value if the first string is lexicographically smaller.
  • A positive value if the first string is lexicographically greater.

  
  if (strcmp(str1, str2) == 0) {
      cout << "Strings are equal!";
  }
  

• Searching: To search for a substring within a string, use the strstr() function. It returns a pointer to the first occurrence of the substring or NULL if not found:

  
  char str[] = "Hello, World!";
  char *result = strstr(str, "World");  // result points to the "World" in the string
  if (result != NULL) {
      cout << "Substring found!";
  }

Example that demonstrates the implementation of strings using arrays and performs common string operations like concatenation, comparison, and searching:

#include <iostream>
#include <cstring>  // for strcat(), strcmp(), strstr()

using namespace std;

int main() {
    // Declaration and initialization of strings
    char str1[50] = "Hello ";
    char str2[] = "World!";
    char str3[] = "Hello World!";
    char str4[] = "world";

    // 1. Concatenation
    strcat(str1, str2);  // Concatenate str2 to str1
    cout << "After concatenation: " << str1 << endl;  // Output: "Hello World!"

    // 2. Comparison
    if (strcmp(str1, str3) == 0) {
        cout << "str1 and str3 are equal." << endl;  // This will be printed
    } else {
        cout << "str1 and str3 are not equal." << endl;
    }

    // Case-insensitive comparison (use strcasecmp or manual implementation for case insensitivity)
    if (strcasecmp(str3, str4) == 0) {
        cout << "str3 and str4 are equal (case-insensitive)." << endl;
    } else {
        cout << "str3 and str4 are not equal (case-insensitive)." << endl;  // This will be printed
    }

    // 3. Searching
    char *found = strstr(str1, "World");  // Search for "World" in str1
    if (found != NULL) {
        cout << "Substring 'World' found at position: " << found - str1 << endl;  // Output: position where "World" starts
    } else {
        cout << "'World' not found in the string." << endl;
    }

    return 0;
}

Explanation:

Concatenation: strcat() is used to join two strings, str1 and str2, resulting in the string "Hello World!".

Comparison: strcmp() compares two strings, str1 and str3. It returns 0 if they are equal, so it prints that they are equal.

Searching: strstr() is used to find the substring "World" in the string str1. If found, it prints the position of the substring.

Output:

After concatenation: Hello World!
str1 and str3 are equal.
str3 and str4 are not equal (case-insensitive).
Substring 'World' found at position: 6