Array
An array is a collection of elements of the same data type stored at contiguous
memory locations. It's one of the simplest and most widely used data structures.
Each element can be accessed directly using an index.
1. One-Dimensional Array
A one-dimensional array is an array of elements of the same data type. It can be
visualized as a single row or column of data.
Memory Representation
Elements of an array are stored in adjacent memory cells. The address of an
element at a given index can be calculated using a formula:
Address(A[i]) = BaseAddress + (i * sizeof(DataType))
Where:
A[i] is the element at index i.
BaseAddress is the memory address of the first element (A[0]).
i is the index of the desired element.
sizeof(DataType) is the size of each element's data type (e.g., 4 bytes for an
int).
Problems 1: Integer Array
1. An integer array int arr[10] starts at memory address 1000. If an integer is 4
bytes, what is the address of arr[5]?
Solution:
Formula: Address(arr[i]) = BaseAddress + (i * sizeof(DataType))
Given:
o BaseAddress = 1000
o i=5
o sizeof(DataType) (size of an int) = 4 bytes
Calculation: Address(arr[5]) = 1000 + (5 * 4) Address(arr[5]) = 1000 + 20
Address(arr[5]) = 1020
The address of arr[5] is 1020.
Problem 2: Character Array
A character array char str[20] begins at address 2500. If a character is 1 byte, what
is the address of str[12]?
Solution:
Formula: Address(str[i]) = BaseAddress + (i * sizeof(DataType))
Given:
o BaseAddress = 2500
o i = 12
o sizeof(DataType) (size of a char) = 1 byte
Calculation: Address(str[12]) = 2500 + (12 * 1) Address(str[12]) = 2500 + 12
Address(str[12]) = 2512
The address of str[12] is 2512.
Problem 3: Double Array with a Different Starting Index
A double-precision floating-point array double numbers[50] has a base address of
3000. If a double is 8 bytes, what is the address of numbers[25]?
Solution:
Formula: Address(numbers[i]) = BaseAddress + (i * sizeof(DataType))
Given:
o BaseAddress = 3000
o i = 25
o sizeof(DataType) (size of a double) = 8 bytes
Calculation: Address(numbers[25]) = 3000 + (25 * 8) Address(numbers[25])
= 3000 + 200 Address(numbers[25]) = 3200
The address of numbers[25] is 3200.
2. Operations
Here are the common operations on a one-dimensional array, with algorithms,
pseudocode, and C programs. We'll use a simple array of integers for our
examples.
a) Traversing
Traversing means visiting each element of the array once, typically to print its
value.
Algorithm
1. Initialize a loop counter i to 0.
2. Repeat the loop until i reaches the size of the array.
3. In each iteration, access the element at index i and perform the desired
operation (e.g., print it).
4. Increment i by 1.
Pseudocode
PROCEDURE TRAVERSE(array, size)
FOR i FROM 0 TO size-1
PRINT array[i]
END FOR
END PROCEDURE
C Program
#include <stdio.h>
void traverse(int arr[], int size) {
printf("Array elements: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
traverse(arr, size);
return 0;
}
Note:
The line int size = sizeof(arr) / sizeof(arr[0]); calculates the number of elements in
a statically-sized array.
sizeof(arr): This part returns the total size of the entire array arr in bytes.
sizeof(arr[0]): This part returns the size of the first element of the array arr
in bytes. Since all elements in an array are of the same data type, this value
represents the size of any single element.
By dividing the total size of the array by the size of one element, you get the total
number of elements in the array. For example, if an array of five 4-byte integers
occupies 20 bytes in total, dividing 20 by 4 gives you 5, which is the correct
number of elements.
Output: Array elements: 10 20 30 40 50
b) Searching
Searching involves finding a specific element (the key) within the array. We'll use
a linear search algorithm, which checks each element one by one.
Algorithm
1. Initialize a loop counter i to 0.
2. Repeat the loop until i reaches the size of the array.
3. In each iteration, compare the element arr[i] with the key.
4. If arr[i] matches the key, print the index i and return.
5. If the loop finishes without finding a match, print a "not found" message.
Pseudocode
PROCEDURE SEARCH(array, size, key)
FOR i FROM 0 TO size-1
IF array[i] IS EQUAL TO key
PRINT "Element found at index " + i
RETURN
END IF
END FOR
PRINT "Element not found"
END PROCEDURE
C Program
#include <stdio.h>
void search(int arr[], int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
printf("%d found at index %d.\n", key, i);
return; // Exit after finding the element
}
}
printf("%d not found in the array.\n", key);
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr);
int key = 30;
search(arr, size, key);
key = 99;
search(arr, size, key);
return 0;
}
Output: 30 found at index 2. 99 not found in the array.
c) Insertion
Insertion adds a new element at a specified position. To make space, all elements
from that position to the end of the array must be shifted.
Algorithm
1. Check if the array is full. If so, insertion is not possible.
2. Check if the given position is valid (within the array bounds).
3. Shift elements: Loop from the end of the array down to the position. In each
iteration, move arr[i] to arr[i+1].
4. Insert the new element at the position.
5. Increment the size of the array.
Pseudocode
PROCEDURE INSERT(array, size, element, position)
IF size IS FULL
PRINT "Array is full."
RETURN
END IF
FOR i FROM size-1 DOWNTO position
array[i+1] = array[i]
END FOR
array[position] = element
size = size + 1
END PROCEDURE
C Program
#include <stdio.h>
int insert(int arr[], int size, int element, int position) {
// Assuming a max capacity of 10
if (size >= 10) {
printf("Array is full. Cannot insert.\n");
return size; // Return original size on failure
}
if (position < 0 || position > size) {
printf("Invalid position for insertion.\n");
return size; // Return original size on failure
}
// Shift elements to the right to make space for the new element
for (int i = size - 1; i >= position; i--) {
arr[i + 1] = arr[i];
}
// Insert the element at the specified position
arr[position] = element;
printf("%d inserted at position %d.\n", element, position);
// Return the new size
return size + 1;
}
void printArray(int arr[], int size) {
printf("Current array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int size = 5;
printArray(arr, size);
// Call insert and update the size with the returned value
size = insert(arr, size, 25, 2);
printArray(arr, size);
return 0;
}
Output:
Current array: 10 20 30 40 50
25 inserted at position 2.
Current array: 10 20 25 30 40 50
d) Deletion
Deletion removes an element from a specified position. To fill the gap, all
elements after that position must be shifted.
Algorithm
1. Check if the array is empty or if the given position is invalid.
2. Store the element to be deleted (optional).
3. Shift elements: Loop from the position to the end of the array. In each
iteration, move arr[i+1] to arr[i].
4. Decrement the size of the array.
Pseudocode
PROCEDURE DELETION(array, size, position)
IF size IS LESS THAN OR EQUAL TO 0
PRINT "Array is empty."
RETURN
END IF
IF position IS LESS THAN 0 OR position IS GREATER THAN OR EQUAL TO size
PRINT "Invalid position."
RETURN
END IF
FOR i FROM position TO size-2
array[i] = array[i+1]
END FOR
size = size - 1
END PROCEDURE
C Program
#include <stdio.h>
int deletion(int arr[], int size, int position) {
if (size <= 0) {
printf("Array is empty. Cannot delete.\n");
return size;
}
if (position < 0 || position >= size) {
printf("Invalid position for deletion.\n");
return size;
}
printf("Deleting element at position %d: %d\n", position, arr[position]);
for (int i = position; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
// Return the new size, which is one less than the old size
return size - 1;
}
void printArray(int arr[], int size) {
printf("Current array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = 5;
printArray(arr, size);
// Call deletion and update the size with the returned value
size = deletion(arr, size, 2);
printArray(arr, size);
return 0;
}
Output:
Current array: 10 20 30 40 50
Deleting element at position 2: 30
Current array: 10 20 40 50
e) Merge
Merging combines two arrays into a third, larger array. This is a common
operation in algorithms like Merge Sort.
Algorithm
1. Initialize a third array, mergedArr, with a size equal to the sum of the sizes
of the two input arrays.
2. Copy all elements from the first array (arr1) into mergedArr.
3. Copy all elements from the second array (arr2) into mergedArr, starting at
the end of the elements copied from arr1.
Pseudocode
PROCEDURE MERGE(array1, size1, array2, size2)
mergedSize = size1 + size2
DECLARE mergedArray OF size mergedSize
FOR i FROM 0 TO size1-1
mergedArray[i] = array1[i]
END FOR
FOR i FROM 0 TO size2-1
mergedArray[size1 + i] = array2[i]
END FOR
PRINT mergedArray
END PROCEDURE
C Program
#include <stdio.h>
void merge(int arr1[], int size1, int arr2[], int size2) {
int mergedSize = size1 + size2;
int mergedArr[mergedSize];
// Copy elements from the first array
for (int i = 0; i < size1; i++) {
mergedArr[i] = arr1[i];
}
// Copy elements from the second array
for (int i = 0; i < size2; i++) {
mergedArr[size1 + i] = arr2[i];
}
printf("Merged array: ");
for (int i = 0; i < mergedSize; i++) {
printf("%d ", mergedArr[i]);
}
printf("\n");
}
int main() {
int arr1[] = {10, 20, 30};
int size1 = 3;
int arr2[] = {40, 50, 60};
int size2 = 3;
merge(arr1, size1, arr2, size2);
return 0;
}
Output: Merged array: 10 20 30 40 50 60
