Data structure and algorithm

Department of
Software Engineering
2nd year
Data structure and
Algorithms
Presented by: Demeke M.
Data structure and algorithm

Chapter one
Overviews of C++ concepts

Presented by: Demeke M.

 CH 1: Overviews of C++ concepts
Data structure and algorithm 3
Contents to be covered
❑ Arrays
❑ Functions
❑ Structures
❑ Pointers
❑ Data structure
❑ Abstract data type
❑ Algorithm
❑ Properties of algorithm
 CH 1: Overviews of C++ concepts
4
Arrays
o An array is a data structure that can hold multiple values (elements) of the same
type. These elements are stored in contiguous memory locations, and each element
can be accessed via an index. It is fixed size, meaning the number of elements
cannot be changed once the array is created.
o Array - consists of a set of objects, all of which are of the same type.
o A collection of identical data objects, which are stored in consecutive memory
locations under a common heading or a variable name.
o In other words, an array is a group or a table of values referred to by the same name.
o int arr[5] = {1, 2, 4, 6, 7}- // Array of 5 integers
• Elements: set of objects in the array. Each element is identified by an index.
• Index denotes the position of the element in the array. It start from 0 to n -1. n is
the size or the dimension of array. In this case 5
• Dimension: the number of elements in the array.
 CH 1: Overviews of C++ concepts
5
Declaring and initializing Array in C++
o Declaring
• To declare an array, you specify the data type, the array name, and the number of
elements in the array.
int arr[5]; // Declares an array of 5 integers
o Array Initialization:
int arr[5] = {1, 2, 3, 4, 5}; // Initialize an array with values
• if you don't initialize all elements, C++ will fill the remaining elements with
default values (0 for integers).
int arr[5] = {1, 2}; // The remaining elements will be initialized to 0
// arr = {1, 2, 0, 0, 0}
• If the number of elements in the initialization list exceeds the declared size, it will
result in an error.
 CH 1: Overviews of C++ concepts
6
Accessing Array Elements
o You access elements of an array using indexes. Array indexes in C++ start at 0.
Example:-
#include <iostream>
using namespace std;
int main() {
int arr[5] = {10, 20, 30, 40, 50};
cout << "First element: " << arr[0] << endl; // Output: 10
cout << "Third element: " << arr[2] << endl; // Output: 30
return 0;
}
 CH 1: Overviews of C++ concepts
7
Modifying Array Elements
o You can modify an array element by specifying its index and assigning a new value.
Example:-
#include <iostream>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
arr[2] = 10; // Modify the third element to 10
cout << "Modified array: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " "; // Output: 1 2 10 4 5
}
return 0;
}
 CH 1: Overviews of C++ concepts
8
Array in Loop
o To perform operations on each element of an array, we typically use loops (like for
loop).
Example:-
#include <iostream>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
// Looping through array using for loop
for (int i = 0; i < 5; i++) {
cout << "Element " << i << ": " << arr[i] << endl;
}
return 0;
}
 CH 1: Overviews of C++ concepts
9
Multidimensional Arrays (2D Arrays)
o C++ supports multidimensional arrays, which are arrays of arrays (like matrices).
o A two-dimensional array in C++ is a collection of elements organized in rows and
columns. It can be visualized as a table or a grid, where each element is accessed
using two indices: one for the row and one for the column.
o Syntax:
data_Type array_name[n][m]; // n : number of row and m: number of column
o Initialization
• Different ways to initialize a 2D array are given below:
• Using Initializer List
Example: int arr[2][4] = {0, 1, 2, 3, 4, 5, 6, 7};
Or int x[2][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}};
o Accessing Elements
Syntax: array_name[i][j]; //where i for row index, and j for column index
 CH 1: Overviews of C++ concepts

Cont … 10
// c++ program to illustrate the two dimensional
array
#include <iostream> // Printing the element of 2D array
using namespace std; for (int i = 0; i < 3; i++) {
int main() for (int j = 0; j < 4; j++) {
{ cout << array1[i][j] << " ";
int count = 1; }
// Declaring 2D array cout << endl;
int array1[3][4]; }
// Initialize 2D array using loop
for (int i = 0; i < 3; i++) { return 0;
for (int j = 0; j < 4; j++) { }
array1[i][j] = count;
count++;
}
}
 CH 1: Overviews of C++ concepts
11
Function
o Function is a block of code that performs a specific task, can be called from other
parts of the program, and may or may not return a value.
o Functions help break down complex programs into smaller, more manageable tasks,
making code more modular and reusable.
o Function Declaration:
• Before defining a function, you can declare it. The declaration (or prototype)
specifies the function's name, return type, and parameters (if any). It doesn't
contain the actual body of the function but simply informs the compiler about the
function's signature.
• Syntax:-
return_type function_name(parameter_list
Example:-
int add(int, int); // Function declaration
 CH 1: Overviews of C++ concepts
12
Function Definition
➢ The function definition includes the function body, where the actual task is performed. This is
where the code to execute is placed.
• Syntax:
return_type function_name(parameter_list) {
// Function body and Code that performs the task
return value; // If the return type is not `void`
}
• Example:
// Function to add two numbers
int add(int a, int b) {
return a + b; // Returning the sum of a and b
}
int main() {
int result = add(5, 10); // Function call
cout << "Sum: " << result << endl;
return 0;
}
 CH 1: Overviews of C++ concepts

Overloading function 13

o Function Overloading
• C++ allows function overloading, which means you can define multiple functions
with the same name, but with different parameter types or numbers of
parameters.
• Example
class Calculator {
public:
int add(int a, int b) {
return a + b;
}
double add(double a, double b) {
return a + b;
}
int add(int a, int b, int c) {
return a + b + c;
}
 CH 1: Overviews of C++ concepts
14
Structures
o A structure in C++ is a user-defined data type that groups different types of data
together in single unit. It allows you to store multiple data members of different data
types under a single name.
• For example, if you want to represent a student, you can use a structure to store
details like name, age, and marks.
o Defining a structure
• To define a structure, you use the struct keyword followed by the structure name
and the list of variables (members) it contains.
• Syntax: o Example
struct StructureName { struct Student {
datatype member1; string name;
datatype member2; int age;
// Other members float marks;
}; };
 CH 1: Overviews of C++ concepts

Cont … 15
o Structure initialization
• You can initialize a structure at the time of declaration. This allows you to assign
values to structure members when the structure is created.
• Syntax:
StructureName structureName = {value1, value2, ...};
• Example
Student s1 = {"Bob", 22, 90.5}; // Directly initializing values
o Accessing Structure Members
• Structure members can be accessed using the dot operator ( . ) when working
with an instance of the structure.
• And using arrow method
 CH 1: Overviews of C++ concepts

Cont … 16
Example:
struct Person {
string name;
int age;
float height;
};
int main() {
// Create an instance / variable of the structure
Person p1;
// Assign values to the structure members
p1.name = "John";
p1.age = 25;
p1.height = 5.9;
// Access and print the structure members
cout << "Name: " << p1.name << endl; // Output: John
cout << "Age: " << p1.age << endl; // Output: 25
cout << "Height: " << p1.height << endl; // Output: 5.9
return 0;
}
 CH 1: Overviews of C++ concepts
17
Pointers
o A pointer in C++ is a variable that stores the memory address of another variable.
Pointers are a powerful feature of C++ that allow you to directly manipulate memory,
pass large structures or arrays efficiently to functions, and even work with dynamic
memory.
o A pointer is a variable that holds the address of another variable in memory, rather
than holding the actual value. To declare a pointer, you use the * symbol in the
declaration.
• Syntax to declare a pointer:
datatype* pointer_name;
• Example:
int* ptr;
 CH 1: Overviews of C++ concepts

Cont … 18
o Address of Operator ( &)
• The address-of operator ( & ) is used to get the memory address of a variable.
Example:
int x = 10;
int* ptr = &x; // ptr now holds the address of x
o Dereferencing Operator (*)
• The dereferencing operator ( * ) is used to access the value stored at the memory
address the pointer is pointing to.
Example:
int x = 10;
int* ptr = &x; // ptr holds the address of x ; ptr point to x
int value = *ptr; // Dereferencing ptr, so value gets the value of x, which is 10
• &x - gives the address of the variable of x
• *ptr - gives the value stored at the address pointed to by ptr.
 CH 1: Overviews of C++ concepts

Cont … 19
o Pointer Arithmetic
• You can perform arithmetic operations on pointers, like incrementing,
decrementing, and adding an offset. When you increment a pointer, it moves to
the next memory location of the type it points to.
• Example:
int main() {
int arr[] = {10, 20, 30, 40, 50};
int* ptr = arr; // Pointer points to the first element of the array

cout << "First element: " << *ptr << endl; // Output: 10
ptr++; // Move the pointer to the next element
cout << "Second element: " << *ptr << endl; // Output: 20

return 0;
}
 CH 1: Overviews of C++ concepts
20
Program
o Program is a set of instruction which is written in to solve a problem.
o A solution to a problem actually consists of two things:
• A way to organize the data
• Sequence of steps to solve the problem
o The way data are organized in a computers memory is said to be Data
Structure.
o The sequence of computational steps to solve a problem is said to be an
Algorithm.
o Therefore a program is data structure plus algorithm
 CH 1: Overviews of C++ concepts
21
Why we study data structure and algorithm?
o The primary goal of this course is efficiency.
o Efficiency of program come from
• Efficiency of data structure and
• Efficiency of algorithm
o The choice of data structure and algorithm can make the difference between
a program running in few second or may days.
 CH 1: Overviews of C++ concepts

Data structure 22
o A data structure is a way to store and organize data so that it can be accessed and
modified efficiently. C++ provides several built-in and user-defined data structures,
which help in organizing and manipulating data in different ways based on the
requirements of the program.
o Data structure can be classified in to two based on arrangement
1. Linear Data Structures
• In linear data structures, elements are arranged in a sequential manner, where
each element has a unique predecessor and successor (except the first and last
elements) one after another.
• Example: Array, linked list, queue, stack, deque
2. Non-Linear Data Structures
• In non-linear data structures, the elements are not arranged in a sequential
manner. Each element may have more than one predecessor and successor.
• The elements are arranged in such a way that they do not follow a strict
sequence. Elements are arranged in a hierarchical or interconnected manner.
• Example: Tree, graph
 CH 1: Overviews of C++ concepts
23
Abstract Data type
oAn Abstract Data Type (ADT) is a model for a data structure that defines the behavior
(or operations) of a data structure without specifying its implementation. In other
words, an ADT specifies what operations can be performed on the data but does not
define how the operations will be implemented. This abstraction allows for the
creation of more modular, reusable, and maintainable code.
oKey Characteristics of ADT
• Encapsulation: An ADT hides the internal details of data and its operations.
Only the operations that the ADT exposes are available to the user.
• Abstraction: It provides a clear interface (set of operations) for interaction,
without worrying about the underlying implementation.
• Modularity: Since the implementation of an ADT can be changed without
affecting its interface, it supports modular programming.
 CH 1: Overviews of C++ concepts
24
Types of Abstract Data Types (ADT)
o Here are some common ADT examples in C++:
1. Stack
• Operations: push(), pop(), top() and other
2. Queue
• Operations: enqueue(), dequeue(), front() and other
3. Linke list
• Operations: insert(), delete(), search() and other
4. Deque And other
o Generally, An Abstract Data Type (ADT) defines a set of operations that can be
performed on a data structure but does not specify how the operations are
implemented.
 CH 1: Overviews of C++ concepts
25
ADT Vs data structure
o ADT
• Logical specification of operations and behaviors.
• Focuses on operations and behaviors of data.
• Abstract, hides implementation details.
• Not concerned with how operations are implemented.
• Defines what operations should be possible
o Data structure
• Concrete implementation of an ADT.
• Focuses on how data is stored and manipulated.
• Concrete, specifies the actual implementation.
• Specifies how operations will be implemented.
• Defines how data will be stored and manipulated.
 CH 1: Overviews of C++ concepts
26
Algorithm
o Is clearly defined as set of simple instruction to be followed to solve a problem.
o An algorithm is a step-by-step procedure or set of instructions for performing a
specific task or solving a problem. In computer science, algorithms are used to
manipulate data, perform calculations, or process information efficiently.
o In essence, an algorithm is a well-defined sequence of operations that take inputs
and produce an output in a finite amount of time.
 CH 1: Overviews of C++ concepts
27
Type of algorithm
➢ Algorithms can be categorized based on their functionality, design techniques, or
complexity. Here are some common types:
1. Sorting algorithm – bubble, selection, insertion and other
2. Searching algorithm – linear , binary search
3. Graph algorithm – DFS, BFS, Prim algorithm and other
4. Divider and conquer algorithm
5. Greedy algorithm and other
 CH 1: Overviews of C++ concepts
28
How algorithm works?
o The process of how an algorithm typically operates:
1. Input: The algorithm takes an input (or multiple inputs) from the user or another
system.
2. Processing: The algorithm performs a series of steps (often involving loops,
conditionals, and recursion) on the input data.
3. Output: The algorithm produces a result or output after completing the
processing steps.
o Generally, it takes a set of value, as input and produce a value, or set of value as
output.
o A problem can have many algorithm (i.e. solution) but we choose the best efficient
algorithm.
 CH 1: Overviews of C++ concepts
29
Properties of Algorithm
o The following are the character tics of algorithm
• Finiteness: The algorithm must terminate after a finite number of steps. It
cannot run indefinitely.
• Definiteness: Each step must be clearly defined, having one and only one
interpretation. At each point in computation, one should be able to tell
exactly what happens next.
• Efficiency: It must solve with the least amount of computational
resources such as time and space.
• Feasibility: It must be possible to perform each instruction. Each
instruction should have possibility to be executed.
• Language Independence: It must not depend on any one programming
language.
CH 1: Overviews of C++ concepts

Cont … 30
• Correctness: It must compute correct answer for all possible legal inputs.
And the output should be as expected and required and correct.
• Completeness: It must solve the problem completely.
• Generality: The algorithm should be applicable to a range of problems,
not just a single instance.
• Input/Output: There must be a specified number of input values, and one
or more result values.
• Effectiveness: The operations must be basic enough to be carried out, in
principle, by a human using a pencil and paper.
• Simplicity: The algorithm should be simple as much as possible every
body who can understand it.
Thank You