Chapter 1
Introduction
What is Data Structure?
• A data structure is a fundamental building block
of computer programming. It defines how data is:
– Organized: How data elements are arranged relative
to each other (i.e., contiguous or non-contiguous).
– Stored: How data is kept in memory or on disk for
easy retrieval and use (e.g., following LIFO or FIFO
principles).
– Manipulated: How data is modified, updated, or
processed within a program to ensure efficient access
and updates.
Classifications of Data Structures:
What is an Algorithm?
• An algorithm is a finite sequence of well-defined
instructions that can be used to solve a
computational problem.
• It provides a step-by-step procedure that convert
an input into a desired output.
• Algorithms typically follow a logical structure:
– Input: The algorithm receives input data.
– Processing: The algorithm performs a series of
operations on the input data.
– Output: The algorithm produces the desired output.
Program = Data Structure + Algorithm
Problem: Find the highest number in a list of numbers.
1. Data Structure: First, you need to decide how to store the data (the
list of numbers). You can use an array or a linked list to store the
numbers.
2. Algorithm: Next, you design a step-by-step method to solve the
problem.
• To find the highest number, you can iterate through the list and keep
track of the largest number you've seen so far.
Algorithm steps:
1. Assume the first number is the largest.
2. Compare it with the next number.
3. If the next number is larger, update the largest number.
4. Repeat until you've checked all numbers.
5. Return the largest number.
3. Program: Finally, you implement the data structure and
algorithm in code. Here’s an example in C++:
Review of C++ Concepts
1.1 Arrays
• An array in C++ is a collection of elements of the same
data type stored in contiguous memory locations.
• Syntax: int squares [4]; // Declares an array of 4
integers
• Initialization: Arrays can be initialized at the time of
declaration: int squares[4] = {1, 4, 9, 16};
– If fewer values are provided, the remaining elements are
initialized to zero.
– If more values are provided than the array size, it results in
an error.
• Accessing Elements: cout << squares[2]; // Outputs 9
• The size of the Array can be skipped if the size should be same as the number of values.
int x[] = {34,21,2,66,567}
Looping through an array:
for (int i = 0; i < 5; i++) {
cout << x[i] << " ";
}
Two dimensional Arrays:
int matrix[3][3] = {
{1,2,3},
{4,5,6},
{7,8,9}};
Accessing elements:
cout << matrix[1][2]; // Outputs 6
Three dimensional Arrays:
Limitation’s of Array:
• Arrays are of fixed size.
• Data elements are stored in contiguous
memory locations which may not be always
available.
• Insertion and deletion of elements can be
problematic because of shifting of elements
from their positions.
However, these limitations can be solved by
using linked lists.
1.2 Structures
• A structure (struct) is a user-defined data type
that groups variables of different types under
one name.
• It helps in managing related data efficiently.
Declaring a Structure: Using Structures:
struct Student { Student s1 = {"Alice", 20, 85.5};
string name; cout << "Name: " << [Link] << "
int age; Age: " << [Link] << " Grade: " <<
float grade; [Link];
};
Structure Arrays:
Student students[2] = {
{"Bob", 21, 90.2},
{"Charlie", 19, 88.5}
};
for (int i = 0; i < 2; i++) {
cout << students[i].name << " " << students[i].age << "
" << students[i].grade << endl;}
1.3 Functions
Functions allow modular programming by breaking down code into reusable blocks.
How functions work:
Types of function:
Function Call Methods:
Call By Value:
• In this calling method, you only pass the copies of the variable and not the
actual argument to the function.
• As the copies of the variable or arguments are being passed, any changes
made to the variable in the function don’t affect the actual argument.
Call By Reference:
• In this calling technique, you pass the address or reference of the
argument, and the function receives the memory address of the
argument.
• In this case, the actual value of the variable changes, or you can
say that it reflects the changes back to the actual variable.
What will be the output?
What will be the output?
1.4 Pointers
• A pointer is a variable that holds the memory
address of another variable.
int x = 10;
Null Pointers:
int *ptr = &x; • A pointer that does not point to any
cout << *ptr; // Outputs 10 valid memory location is called a null
pointer.
Pointer Arithmetic: int *ptr = nullptr;
• Pointers can be incremented or
decremented: Pointers and Arrays:
int arr[] = {1, 2, 3}; int numbers[] = {10, 20, 30};
int *p = arr; int *ptr = numbers;
p++; cout << *(ptr + 1); // Outputs 20
cout << *p; // Outputs 2
Some programming languages do not support pointers explicitly or restrict their usage for
safety reasons. Here are a few examples: Java , Python , C#, JavaScript , Swift , Kotlin ,
Go (Golang).
1.5 File Operations
• .
To read data from a file, use ifstream: To write data to a file, use ofstream:
#include <fstream>ifstream #include <fstream>ofstream
infile("[Link]"); outfile("[Link]");
string line; outfile << "Hello, File!";
while (getline(infile, line)) { [Link]();
cout << line << endl;
}
[Link]();
Use ios::app mode to append data instead of
overwriting:
ofstream outfile("[Link]",
ios::app);
outfile << "New data";
[Link]();
Thank You!
Any Question