Introduction to Data Structures

Introduction to Data Structures

• Data is a collection of raw facts and figures.
• Data structures are techniques for organizing data logically and mathematically.
• Data structures organize data in a specific format.
• Linked Lists are a common example of data structures, where data is stored in nodes linked together by addresses.

Purpose of Data Structures

• Data structures improve program efficiency by reducing storage requirements.
• They help manage memory effectively, reducing memory waste and increasing program speed.

Classification of Data Structures

• Linear vs Non-Linear:
  • Linear data structures store data in a sequential manner, such as linked lists.
  • Non-linear structures store data in a hierarchical or network form, like trees and graphs.
• Homogeneous vs Non-Homogeneous:
  • Homogeneous structures store similar types of data, like arrays.
  • Non-homogeneous structures store different types of data, like structures and unions.
• Static vs Dynamic:
  • Static data structures have a fixed size allocated at compile time.
  • Dynamic data structures can expand or shrink in size during program execution, based on the needs of the program.

Operations Performed on Data Structures

• Searching: Finding a specific element in a data structure.
• Traversing: Accessing and processing each element in a data structure sequentially.
• Inserting: Adding a new element to a data structure.
• Updating: Modifying an existing element in a data structure.
• Deleting: Removing an element from a data structure.
• Merging: Combining two data structures into one.
• Sorting: Arranging elements in a specific order, like ascending or descending order.

What is an Algorithm?

• An algorithm is a step-by-step description of a program written in a general language.
• Algorithms provide a clear set of instructions for solving a problem.

Properties of Algorithms

• Input: Every algorithm requires input data.
• Output: Every algorithm produces an output after processing input data.
• Definiteness: Every instruction within an algorithm must be clear and unambiguous.
• Finiteness: An algorithm must terminate after a finite number of steps.
• Effectiveness: Each instruction in an algorithm must be basic enough to be carried out in a finite amount of time.

Example: Adding Two Numbers

• Algorithm:

  • Begin
  • Input: Two numbers, A and B.
  • Sum: A + B
  • Output: Display the sum of A and B.
  • End

• C++ Program:

  #include <iostream>
  using namespace std;
  
  int main() {
      int A, B, sum;
      cout << "Enter two numbers: ";
      cin >> A >> B;
      sum = A + B;
      cout << "Sum of A and B: " << sum << endl;
      return 0;
  }
  

Example: Printing Natural Numbers

• Algorithm:

  • Begin
  • Set: I = 1
  • Repeat (until I <= 10)
    • Print: Value of I
    • Increment: I = I + 1
  • End

• C++ Program:

  #include <iostream>
  using namespace std;
  
  int main() {
      int I = 1;
      while (I <= 10) {
          cout << I << " ";
          I++;
      }
      return 0;
  }