Week 5: Arrays (2)

Searching Arrays

Searching an array involves examining each element of the array sequentially or using a more efficient algorithm to find a specific value or a set of values that meet certain criteria. In programming, two primary searching techniques are commonly used: linear search and binary search. Here's a brief summary of each:

Linear Search (Sequential Search)

  • Approach: Examines each element of the array sequentially from the first to the last.

  • Algorithm:

    1. Start from the first element.

    2. Compare each element with the value being searched.

    3. If a match is found, return the index of the element.

    4. If the end of the array is reached without finding the value, the value is not present.

  • Time Complexity: O(n) - As the size of the array (n) grows, the worst-case number of comparisons grows linearly.

  • Advantages: Simple to implement; works on unsorted arrays.

  • Disadvantages: Inefficient for large arrays as it may require examining every element.

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Target found, return index
        }
    }
    return -1; // Target not found
}

int main() {
    int array[] = {34, 51, 23, 8, 3, 17, 10};
    int size = sizeof(array) / sizeof(array[0]);
    int target = 23;

    int result = linearSearch(array, size, target);
    if (result != -1) {
        printf("Element %d found at index: %d\n", target, result);
    } else {
        printf("Element %d not found in the array\n", target);
    }

    return 0;
}

Binary Search

  • Approach: Significantly faster than linear search, but it requires the array to be sorted beforehand.

  • Algorithm:

    1. Start with the middle element of the array.

    2. If the middle element is equal to the value being searched, return its index.

    3. If the middle element is greater than the value, repeat the search on the left half of the array.

    4. If the middle element is less than the value, repeat the search on the right half of the array.

    5. Continue this process until the value is found or the subarray size becomes 0 (meaning the value is not present).

  • Time Complexity: O(log n) - The size of the search space is reduced by half with each comparison.

  • Advantages: Highly efficient for large, sorted arrays.

  • Disadvantages: Requires the array to be sorted; more complex than linear search.

#include <stdio.h>

// Function to perform binary search
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found, return index
        }

        // If the target is greater, ignore the left half
        if (arr[mid] < target) {
            left = mid + 1;
        }
        // If the target is smaller, ignore the right half
        else {
            right = mid - 1;
        }
    }
    return -1; // Target not found
}

int main() {
    int array[] = {3, 8, 10, 17, 23, 34, 51}; // Sorted array
    int size = sizeof(array) / sizeof(array[0]);
    int target = 23;

    int result = binarySearch(array, 0, size - 1, target);
    if (result != -1) {
        printf("Element %d found at index: %d\n", target, result);
    } else {
        printf("Element %d not found in the array\n", target);
    }

    return 0;
}

Multidimensional Arrays

Multidimensional arrays in C are arrays of arrays, providing a way to store data in a grid or table-like structure. They are particularly useful for representing matrices, 3D space, or any data that naturally fits in a multi-axis structure.

  • Syntax: The syntax for declaring a multidimensional array is an extension of the one-dimensional array. For a 2D array, it looks like type name[size1][size2];, where size1 is the number of rows and size2 is the number of columns.

  • Initialization: Multidimensional arrays can be initialized at the time of declaration. For nested arrays, initialization happens row by row.

  • Accessing Elements: Elements are accessed using multiple indices, like array[i][j] for a 2D array, where i is the row index and j is the column index.

  • Memory Layout: Multidimensional arrays are stored in row-major order in memory, meaning the entire first row is stored contiguously, followed by the entire second row, and so on.

Example: 2D Array in C

Here's an example of how to declare, initialize, and access a 2D array in C:

#include <stdio.h>

int main() {
    // Declare and initialize a 2D array
    int matrix[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };

    // Display the 2D array
    for (int i = 0; i < 3; i++) { // Loop through rows
        for (int j = 0; j < 4; j++) { // Loop through columns
            printf("%d ", matrix[i][j]);
        }
        printf("\n"); // Newline at the end of each row
    }

    return 0;
}

This program declares a 2D array named matrix with 3 rows and 4 columns. It initializes the array with values, loops through the array to access each element, and prints the values in a matrix format.

Multidimensional arrays are a powerful feature in C, allowing complex data structures to be represented and manipulated efficiently. However, it's essential to manage their dimensions and indices carefully to avoid out-of-bounds errors and ensure the integrity of the data.

Example:

Multidimensional array to calculate and store the electric field components resulting from a set of point charges in a 3D space:

#include <stdio.h>
#include <math.h>

#define Nx 10
#define Ny 10
#define Nz 10

// Structure to represent a 3D point or vector
typedef struct {
    double x, y, z;
} Vector3D;

// Function to calculate the electric field at a point due to a point charge
Vector3D electricFieldAtPoint(Vector3D point, Vector3D chargePosition, double charge) {
    Vector3D rVector = {chargePosition.x - point.x, chargePosition.y - point.y, chargePosition.z - point.z};
    double distanceSquared = rVector.x * rVector.x + rVector.y * rVector.y + rVector.z * rVector.z;
    double distance = sqrt(distanceSquared);
    double k = 8.9875517873681764 * pow(10, 9); // Coulomb's constant in N m²/C²
    
    // Ensure we don't divide by zero
    if (distance == 0) {
        return (Vector3D){0, 0, 0};
    }
    
    double fieldMagnitude = k * charge / distanceSquared;
    
    // Normalize the rVector to get the direction (unit vector)
    Vector3D fieldDirection = {rVector.x / distance, rVector.y / distance, rVector.z / distance};
    // Multiply the magnitude by the direction to get the vector field
    return (Vector3D){fieldMagnitude * fieldDirection.x, fieldMagnitude * fieldDirection.y, fieldMagnitude * fieldDirection.z};
}

int main() {
    // Define the electric field array
    Vector3D electricField[Nx][Ny][Nz] = {0};

    // Define a point charge
    Vector3D chargePosition = {5, 5, 5}; // Position of the charge
    double charge = 1e-9; // Charge in Coulombs

    // Calculate the electric field at each point in space
    for (int x = 0; x < Nx; x++) {
        for (int y = 0; y < Ny; y++) {
            for (int z = 0; z < Nz; z++) {
                Vector3D point = {x, y, z};
                electricField[x][y][z] = electricFieldAtPoint(point, chargePosition, charge);
            }
        }
    }

    // Output the electric field at each point in space
    for (int x = 0; x < Nx; x++) {
        for (int y = 0; y < Ny; y++) {
            for (int z = 0; z < Nz; z++) {
                printf("E at (%d, %d, %d): (%f, %f, %f)\n", x, y, z, 
                        electricField[x][y][z].x, electricField[x][y][z].y, electricField[x][y][z].z);
            }
        }
    }

    return 0;
}

Variable-Length Arrays

Variable-Length Arrays (VLAs) in C are arrays where the length or size is determined at runtime, rather than at compile time. Introduced in the C99 standard, VLAs provide a more flexible way to handle array data structures when the size of the array cannot be predetermined. Here's a short introduction to VLAs and their advantages:

Question: Do you know which version of gcc and standard using in onlinegdb you are using?

Introduction to Variable-Length Arrays (VLAs)

  • Dynamic Size: Unlike traditional arrays in C, where the size must be a compile-time constant, VLAs allow the size to be determined during program execution.

  • Syntax and Usage: Similar to regular arrays, making them easy to use and integrate into existing codebases.

  • Allocation: Typically allocated on the stack, which can lead to faster access and deallocation compared to heap allocation.

Advantages of Variable-Length Arrays

  1. Flexibility in Size: The most significant advantage of VLAs is their ability to adapt to the required size at runtime. This feature is particularly useful when dealing with data whose size is not fixed and only known during execution.

  2. Ease of Use: VLAs are used just like fixed-size arrays, which means most existing code and algorithms can work with VLAs without modification. This makes them easy to adopt in place of fixed-size arrays.

  3. No Need for Dynamic Memory Management: Unlike dynamically allocated arrays (using malloc or calloc), VLAs do not require explicit memory management. There's no need to free the memory, as it is automatically reclaimed when the array goes out of scope, reducing the risk of memory leaks.

  4. Performance: Being allocated on the stack, VLAs might offer performance benefits for small to medium-sized arrays due to faster allocation and deallocation. However, this comes with the caveat of being mindful of the stack's size limitations.

  5. Local Scope: As VLAs are automatically allocated and deallocated, they provide a clean and local scope for array data, ensuring that memory is efficiently used and released in functions or code blocks.

In summary, Variable-Length Arrays in C offer a flexible and convenient way to handle arrays whose size is not known until runtime. Their ease of use, coupled with the advantages of stack allocation, makes them a useful feature in scenarios where array sizes are dynamic and memory management needs to be straightforward. However, it's essential to be aware of their limitations, especially regarding stack size and portability across different compiler implementations.

#include <stdio.h>

int main() {
    int size;

    // Ask the user for the number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &size);

    if (size <= 0) {
        printf("Invalid size. Size should be a positive integer.\n");
        return 1;
    }

    // Declare a Variable-Length Array with the given size
    float numbers[size];

    // Input elements of the array
    printf("Enter %d numbers:\n", size);
    for (int i = 0; i < size; i++) {
        scanf("%f", &numbers[i]);
    }

    // Calculate the sum of the numbers
    float sum = 0.0;
    for (int i = 0; i < size; i++) {
        sum += numbers[i];
    }

    // Calculate the average
    float average = sum / size;

    // Output the result
    printf("The average is: %.2f\n", average);

    return 0;
}

Question: What is the stack mentioned above?

Stack and Heap

The stack and the heap are two fundamental areas of memory used for different purposes in programming, especially evident in languages like C and C++. Understanding their differences is crucial for effective memory management and program stability.

Here's a comparison:

1. Memory Management

  • Stack:

    • Automatic Management: Memory allocation and deallocation on the stack are automatically handled when functions are called and return. This is done using the LIFO (Last-In, First-Out) principle.

    • Scope-Based: Variables allocated on the stack are local to the function they were declared in. They are automatically destroyed once the function exits.

  • Heap:

    • Manual Management: Memory on the heap must be manually allocated and deallocated by the programmer (using functions like malloc, calloc, free in C).

    • Controlled Lifetime: Memory on the heap remains allocated until it is explicitly freed, regardless of the scope where it was allocated.

2. Allocation Speed

  • Stack:

    • Fast Allocation: Memory allocation on the stack is very fast. Allocating memory is typically just a matter of incrementing the stack pointer.

  • Heap:

    • Slower Allocation: Allocating memory on the heap is comparatively slower due to the need to find a free block of the desired size, manage fragmentation, and maintain bookkeeping information.

3. Size and Limitations

  • Stack:

    • Limited Size: The stack has a limited size, usually determined at the start of the program. Exceeding this limit results in a stack overflow.

    • Large Allocations Not Ideal: Not suitable for large data structures or for variables that need to exist beyond the scope of a single function call.

  • Heap:

    • Larger Size: The heap size is typically much larger, limited by the size of the virtual memory or the free memory of the operating system.

    • Suitable for Large Allocations: Ideal for large data structures or for data that needs to persist across function calls.

4. Fragmentation

  • Stack:

    • No Fragmentation: The stack does not suffer from fragmentation due to its LIFO nature of allocation and deallocation.

  • Heap:

    • Fragmentation Possible: The heap can suffer from fragmentation as blocks of memory are allocated and freed in an arbitrary order.

5. Usage

  • Stack:

    • Function Calls and Local Variables: Mainly used for function call stacks, local variables, and function parameters.

  • Heap:

    • Dynamic Memory Allocation: Used for dynamically allocated memory that needs to persist beyond the scope of a single function call or for large blocks of memory.

6. Safety and Complexity

  • Stack:

    • Safety: Using the stack is generally safer as the management is done automatically and errors like forgetting to deallocate memory cannot occur.

    • Simplicity: Simpler to use for local variables that have a short lifespan.

  • Heap:

    • Complexity and Bugs: Requires careful management. Improper handling can lead to bugs like memory leaks (not freeing memory), dangling pointers (using freed memory), and heap corruption.

Understanding the differences between the stack and the heap is crucial for writing efficient, reliable, and safe programs, especially in languages like C and C++ where the programmer is responsible for memory management.

Secure C Programming

Bounds Checking for Array Subscripts

Ensuring that array element access is always within the defined bounds is crucial for program stability and security. For a one-dimensional array, this means that any subscript used to access an element must be at least 0 and less than the total number of elements in the array. Similarly, for a two-dimensional array, the subscripts for both rows and columns must be at least 0 and less than the total number of rows and the total number of columns, respectively. This principle of bounds checking extends to arrays with more dimensions as well, where each subscript must fall within the valid range for its respective dimension.

if (index >= 0 && index < ARRAY_SIZE) {
    // Safe to access array[index]
} else {
    // Handle the error: Index out of bounds
}

scanf_s

Bounds checking is crucial in string processing to prevent buffer overflows. When using scanf to read a string into a char array, it's important to note that scanf does not inherently restrict the number of characters read to the size of the array. As a result, if the input string exceeds the array's capacity, scanf will continue writing characters, including the string's terminating null character ('\0'), beyond the array's allocated space. This can lead to the overwriting of adjacent memory locations, potentially affecting the values of other variables. Moreover, subsequent write operations to these adjacent variables might corrupt the string by overwriting its null terminator, leading to undefined behavior when the string is accessed.

#define MAX_LENGTH 50
char inputString[MAX_LENGTH];
scanf("%49s", inputString);

Using fgets for Enhanced Security

While the method above helps to prevent buffer overflows, scanf still has limitations, such as not handling white spaces well. A more robust alternative for reading strings is fgets. Here's how you can use fgets:

fgets(inputString, MAX_LENGTH, stdin);

Classwork - Week 5

Create a basic flight seat reservation system using strings and multidimensional arrays in C. Your program can handle:

  • Implement a seat reservation system for a small airplane.

  • The airplane has 10 rows, with 4 seats in each row (labelled 'A' to 'D').

  • The program should allow users to:

    • Display available seats.

    • Book a seat.

    • Cancel a booking.

    • Display the seating chart.

Homework - Week 5

A palindrome is a sequence of characters that reads the same backward as forward. Examples include "lilil", "radar," "able was i ere i saw elba," and, when disregarding spaces, "a man a plan a canal panama." Create a recursive function testPalindrome that returns 1 if the string in the array constitutes a palindrome, and 0 if not. This function should overlook spaces and punctuation in the string.

PreviousWeek 4: Arrays (1)NextWeek 6: Pointer (1)

Last updated