Data Structure and Algorithm

Instructor: Hafiz Abdul Rehman

Lecture 02: Array

1
Arrays
• Array is a data structure that represents a collection of elements in
Sequence
• The items in an array are called array elements.
• Each component (array element) is accessed by an index.
• Each element has unique index or position.
• The index of first element is called Lower bound and last is upper
bound.
• Index of array starts from 0(Lower bound).
• Maximum Number of elements in array:
upper Bound – Lower Bound + 1
num[3]=2-0+1=3
NEED OF ARRAY
ARRAYS ARE USEFUL BECAUSE -
• Sorting and searching a value in an array is easier.
• Arrays are best to process multiple values quickly and easily.
• Arrays are good for storing multiple values in a single variable.
• In computer programming, most cases require storing a large amount of
data of a similar type.
• To store such an amount of data, we need to define a large number of
variables.
• It would be very difficult to remember the names of all the variables
while writing the programs.
• Instead of naming all the variables with a different name, it is better to
define an array and store all the elements into it.
Properties of Array
• Homogeneous Elements: All elements in an array must have the same data
type (e.g., integers, floating-point numbers, characters).
• Fixed or Dynamic Size:
• Fixed-size arrays have a predetermined number of elements that cannot
be changed once the array is created.
• Dynamic arrays can grow or shrink in size during program execution,
allowing for flexibility in managing data.
• Contiguous Memory Allocation: Elements in an array are stored in
contiguous memory locations, which means they are stored one after
another in memory. This property enables efficient element access through
indexing.
• Zero-Based Indexing: In many programming languages, arrays are zero-
indexed, meaning the index of the first element is 0, the second element is 1,
and so on.
Array Declaration and Initialization
• Initializer List
• Initializer list to directly initialize an array with values when declaring it.
int array[] = {1, 2, 3, 4, 5}; // Initializes an integer array with values
• Explicit Size Declaration
• If you want to specify the size of the array explicitly, you can do so while using
an initializer list.
int array[5] = {1, 2, 3, 4, 5}; // Initializes a 5-element integer array with values
Array Declaration and Initialization
• Default Initialization
• Global and static arrays that are not explicitly initialized are automatically
initialized to zero.
• int array[5]; // Initializes all elements to 0

• Partial Initialization
• You can partially initialize an array, and the remaining elements will be
initialized to zero.
• int array[5] = {1, 2}; // Initializes the first two elements, the rest are set to 0
Array Declaration and Initialization
• Designated Initializers (C++20 and later)
• you can use designated initializers to specify values for specific elements in
the array.
• int array[5] = {1, 2, [3] = 10, [4] = 20}; // Initializes specific elements with
values

• Loop Initialization
• You can use loops to initialize the elements of an array programmatically
int myArray[5];
for (int i = 0; i < 5; ++i) {
myArray[i] = i + 1;
}
REPRESENTATION OF ARRAY IN MEMORY

• Each box represents the amount of memory needed to hold one array
element.
• For int this is usually 4 bytes.
• We can write the value of an element inside the box.
• Starting address of array is called base address.
• We can find any element’s address through base address.
ACCESS AN ELEMENT FROM THE ARRAY

• We required the information given below to access any random element from
the array
• Base address of the array.
• Size of an element in bytes.
• Type of indexing, array follows.
• The formula to calculate the address to access an array element

BYTE ADDRESS OF ELEMENT A[I] = BASE ADDRESS + SIZE * I

ACCESS AN ELEMENT FROM THE ARRAY
BASIC OPERATIONS IN ARRAYS

• TRAVERSE − Print all the array elements one by one.

• INSERTION − Adds an element at the given index.
• DELETION − Deletes an element at the given index.
• SEARCH − Searches an element using the given index or by the
value.
• UPDATE − Updates an element at the given index.
• SORTING – Sorting the elements in ascending or descending order
TRAVERSING AN ARRAY
1. START
2. INITIALIZE COUNTER VARIABLE(INT I) AND I=LOWERBOUND.
3. REPEAT I=LB TO UPPER BOUND BY INCREMENTING I.
4. APPLY PROCESS TO ARRAY[I]
5. END LOOP
6. STOP
EXAMPLE OF TRAVERSE

// writing a program in C++ to perform traverse operation on an array

//lower bound is 0 and upper bound is 4
#include <iostream>
using namespace std;
int main()
{
int i, size=5;
int arr[5]={53, 99, -11, 5, 102}; //declaring and initializing array
cout << "The array elements are: ";
for(i=0 ; i<size ; i++)
cout << "\n" << "arr[" << i << "]= " << arr[i];
return 0;
}
EVEN VALUES ARRAY TRAVERSAL

INT ARR[10], I;
COUT<<"ENTER ANY 10 NUMBERS: ";
FOR(I=0; I<10; I++)
CIN>>ARR[I];
COUT<<"\NEVEN NUMBERS ARE:\N";
FOR(I=0; I<10; I++)
{
IF(ARR[I]%2==0)
COUT<<ARR[I]<<" ";
}
ACTIVITY#1

CALCULATE SUM OF ELEMENTS OF ARRAY OF SIZE 5?

FIND THE SMALLEST NUMBER OF THE ARRAY OF SIZE 10?
INSERTION AND DELETION OF ELEMENT

INSERTION
#include <iostream>
int main() {
int staticArray[5] = {1, 2, 3, 4, 5};
staticArray[2] = 10;
for (int i = 0; i < 5; ++i) {
std::cout << staticArray[i] << " ";
}
return 0;
}
INSERTION AND DELETION OF ELEMENT

DELETION
#include <iostream>
int main() {
int staticArray[5] = {1, 2, 3, 4, 5};
staticArray[2] = 0;
for (int i = 0; i < 5; ++i) {
std::cout << staticArray[i] << " ";
}
return 0;
}
SEARCH ELEMENT FROM ARRAY
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
SEARCH [ C++ CODE ]
#include <iostream>
using namespace std;
main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
cout<<"The original array elements are:"<<endl;
for(i = 0; i<n; i++) {
cout<<i<<"="<<LA[i]<<endl;
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
cout<<"Found element at position="<< j+1 <<" and index="<<j;
}
ACTIVITY#2

• SEARCH AND UPDATE

2D-ARRAY

• A MULTI-DIMENSIONAL ARRAY CAN BE TERMED AS AN

ARRAY OF ARRAYS THAT STORES HOMOGENEOUS
DATA IN TABULAR FORM. DATA IN MULTIDIMENSIONAL
ARRAYS ARE STORED IN ROW-MAJOR ORDER.
• SIZE OF MULTIDIMENSIONAL ARRAYS:
• THE TOTAL NUMBER OF ELEMENTS THAT CAN BE STORED IN
A MULTIDIMENSIONAL ARRAY CAN BE CALCULATED BY
MULTIPLYING THE SIZE OF ALL THE DIMENSIONS.
• FOR EXAMPLE:
• THE ARRAY INT X[10][20] CAN STORE TOTAL (10*20) =
200 ELEMENTS.
EXAMPLE OF 2D-ARRAY C++
INT ARR[3][2] = {{5, -5},{4, 7}, {9, 17}}; // USE OF NESTED FOR LOOP
// ACCESS ROWS OF THE ARRAY
FOR (INT I = 0; I < 3; ++I) {
// ACCESS COLUMNS OF THE ARRAY
FOR (INT J = 0; J < 2; ++J) {
COUT << “ARR[" << I << "][" << J << "] = " << ARR[I][J] << ENDL;
}
}
TRANSPOSE OF MATRIX

FOR (INT I = 0; I < ROW; ++I)

FOR (INT J = 0; J < COLUMN; ++J) {

TRANSPOSE[J][I] = ARR[I][J];

}
Static VS Dynamic Array
Static Array:
• A static array has a fixed size that is determined at compile time.
• You declare it by specifying the array's data type, name, and size.
int myArray[5]; // Declares an integer array with 5 elements
Dynamic Array (using pointers):
• A dynamic array's size can be determined at runtime, and it is typically
allocated on the heap using pointers.
• You need to use new operator to allocate memory for the array
int* dynamicArray = new int[10]; // Declares a dynamic integer array with 10 elements
// Don't forget to delete it when done to prevent memory leaks
delete[] dynamicArray;
• COMPLETE DYNAMIC MEMORY ALLOCATION PROBLEM WILL BE DISCUSS
IN NEXT LECTURE
Thank You

26