Home
CSE101
Notes

CSE101 Unit 4 Notes

Arrays in C

Arrays are fundamental data structures in programming that allow you to store multiple values of the same type under a single variable name. This unit will explore the concept of arrays in C, including their declaration, initialization, manipulation, and applications. Understanding arrays is crucial for efficient data management and manipulation in your programs.

Introduction to Arrays

Definition

  • Array: An array is a collection of elements of the same data type stored in contiguous memory locations, which can be individually referenced by adding an index to a unique identifier.

Purpose

  • Efficient Data Management: Arrays allow you to store and manage large amounts of data efficiently.
  • Indexed Access: Elements can be accessed directly using their index, providing fast retrieval and modification.
  • Homogeneous Data Storage: Ideal for storing collections of data items that are logically related and of the same type.

Characteristics

  • Homogeneous Elements: All elements in an array must be of the same data type (e.g., all integers, all floats).
  • Fixed Size: The size of an array must be specified at the time of declaration and cannot be altered during program execution.
  • Contiguous Memory Allocation: Elements are stored in consecutive memory locations, facilitating efficient access and manipulation.

Declaring and Initializing Arrays

Declaring Arrays

Syntax

data_type array_name[array_size];
  • data_type: The type of data the array will hold (e.g., int, float, char).
  • array_name: The identifier for the array.
  • array_size: The number of elements the array will hold; must be a positive integer.

Examples

One-Dimensional Array
int numbers[10]; // Declares an array named 'numbers' that can hold 10 integers
Two-Dimensional Array
float matrix[3][4]; // Declares a 2D array (matrix) with 3 rows and 4 columns

  • General Syntax for 2D Arrays:

    data_type array_name[rows][columns];

Initializing Arrays

Arrays can be initialized at the time of declaration.

One-Dimensional Arrays

Full Initialization
int numbers[5] = {1, 2, 3, 4, 5};
  • Each element is explicitly assigned a value.
Partial Initialization
int numbers[5] = {1, 2}; // Remaining elements are set to zero (for global/static arrays)
  • Uninitialized elements:
    • For static and global arrays: Remaining elements are automatically initialized to zero.
    • For automatic (local) arrays: Remaining elements contain garbage values (undefined).
Size Inference
int numbers[] = {1, 2, 3}; // Array size is inferred from the number of initializers (size is 3)
  • The compiler determines the array size based on the initial values provided.

Two-Dimensional Arrays

Row-Major Initialization
int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};
  • Each sub-array represents a row in the matrix.
Flattened Initialization
int matrix[2][3] = {1, 2, 3, 4, 5, 6};
  • Values are assigned row by row:
    • matrix[0][0] = 1
    • matrix[0][1] = 2
    • matrix[0][2] = 3
    • matrix[1][0] = 4
    • matrix[1][1] = 5
    • matrix[1][2] = 6

Defining and Processing One-Dimensional Arrays

Defining One-Dimensional Arrays

Declaration

data_type array_name[array_size];

Example

char letters[26]; // An array to hold the 26 letters of the English alphabet

Accessing Array Elements

Syntax

array_name[index];
  • Indexing:
    • The first element has an index of 0.
    • The last element has an index of array_size - 1.

Example

int numbers[5] = {10, 20, 30, 40, 50};

int first = numbers[0]; // Accesses the first element (10)
int last = numbers[4];  // Accesses the last element (50)

Processing Arrays

Traversal

Using loops to iterate over array elements.

Example: Printing Array Elements
for (int i = 0; i < 5; i++) {
    printf("%d\n", numbers[i]);
}

Calculations

Perform operations like sum, average, find maximum/minimum.

Example: Calculating Sum and Average
int sum = 0;
for (int i = 0; i < 5; i++) {
    sum += numbers[i];
}
float average = sum / 5.0;
printf("Sum: %d, Average: %.2f\n", sum, average);

Modifying Elements

for (int i = 0; i < 5; i++) {
    numbers[i] *= 2; // Doubles each element
}

Defining and Processing Two-Dimensional Arrays

Defining Two-Dimensional Arrays

Declaration

data_type array_name[rows][columns];

Example

int matrix[3][4]; // Declares a 2D array with 3 rows and 4 columns

4.2 Accessing Elements

Syntax

array_name[row_index][column_index];
  • Indexing starts from 0 for both rows and columns.

Example

int value = matrix[1][2]; // Accesses element at second row and third column

Processing Two-Dimensional Arrays

Traversal

Using nested loops to iterate over rows and columns.

Example: Printing Matrix Elements
for (int i = 0; i < 3; i++) {        // Iterates over rows
    for (int j = 0; j < 4; j++) {    // Iterates over columns
        printf("%d ", matrix[i][j]);
    }
    printf("\n"); // Newline after each row
}

Initializing Elements

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        matrix[i][j] = i + j; // Example initialization
    }
}

Applications

  • Matrix Operations: Addition, subtraction, multiplication.
  • Data Representation: Grids, tables, images, game boards.
  • Statistical Data: Storing data sets with multiple attributes.

Array Applications

Common Uses

  • Data Storage: Efficiently store and manage collections of data.
  • Statistical Analysis: Hold data sets for calculations like mean, median, mode.
  • String Handling: Character arrays (char[]) are used for strings.
  • Matrices and Vectors: Perform mathematical computations.
  • Lookup Tables: Store precomputed values for quick retrieval.

Examples

Storing Marks of Students

int marks[50]; // Stores the marks of 50 students

Temperature Readings

float temperatures[24]; // Stores hourly temperature readings for a day

Character Arrays (Strings)

char message[] = "Hello, World!";
  • Note: In C, strings are represented as arrays of characters terminated by a null character '\0'.

Passing Arrays to Functions

Passing One-Dimensional Arrays

Function Definition

void functionName(data_type array_name[], int size);
  • data_type: Type of the array elements.
  • array_name[]: Indicates that an array is expected.
  • size: Number of elements in the array.

Function Call

functionName(array, array_size);

Example: Printing an Array

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5};
    printArray(numbers, 5);
    return 0;
}

Passing Two-Dimensional Arrays

Requirement

  • When passing a 2D array, you must specify the number of columns in the function definition.

Function Definition

void functionName(data_type array_name[][columns], int rows);
  • columns: The size of the second dimension (number of columns) must be known.

Function Call

functionName(matrix, number_of_rows);

Example: Printing a Matrix

void printMatrix(int matrix[][3], int rows) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < 3; j++) { // '3' is the number of columns
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int matrix[2][3] = {
        {1, 2, 3},
        {4, 5, 6}
    };
    printMatrix(matrix, 2);
    return 0;
}

Notes on Passing Arrays

  • Passed by Reference:
    • The array name acts as a pointer to the first element.
    • Modifications to array elements within the function affect the original array.
  • Size Information:
    • The function needs to know the size of the array (either passed as a parameter or predetermined).

Inserting and Deleting Elements in an Array

Insertion

Process

  1. Validate Position: Ensure the position is within the valid range (0 to size).
  2. Shift Elements: Move elements starting from the position to the right to create space.
  3. Insert Element: Place the new element at the desired position.
  4. Update Size: Increment the array size.

Example Function: Inserting an Element

void insertElement(int arr[], int *size, int element, int position) {
    if (position < 0 || position > *size) {
        printf("Invalid position!\n");
        return;
    }
    for (int i = *size; i > position; i--) {
        arr[i] = arr[i - 1]; // Shift elements right
    }
    arr[position] = element;
    (*size)++; // Increment size
}

Deletion

Process

  1. Validate Position: Ensure the position is within valid range (0 to size - 1).
  2. Remove Element: Element at the position is to be removed.
  3. Shift Elements: Move elements after the position to the left to fill the gap.
  4. Update Size: Decrement the array size.

Example Function: Deleting an Element

void deleteElement(int arr[], int *size, int position) {
    if (position < 0 || position >= *size) {
        printf("Invalid position!\n");
        return;
    }
    for (int i = position; i < *size - 1; i++) {
        arr[i] = arr[i + 1]; // Shift elements left
    }
    (*size)--; // Decrement size
}

Searching in Arrays

Algorithm

  • Start from the first element.
  • Compare each element with the search key.
  • Continue until the key is found or the array ends.

Time Complexity

  • Worst Case: O(n), where n is the number of elements.

Implementation

int linearSearch(int arr[], int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i; // Key found at index i
        }
    }
    return -1; // Key not found
}

Use Cases

  • Suitable for unsorted arrays.
  • Simple and easy to implement.

Precondition

  • The array must be sorted in ascending or descending order.

Algorithm

  1. Initialize:
    • low = 0
    • high = size - 1
  2. Loop:
    • While low <= high:
      • Calculate mid = (low + high) / 2.
      • If arr[mid] == key, return mid.
      • If arr[mid] < key, set low = mid + 1.
      • If arr[mid] > key, set high = mid - 1.
  3. Not Found:
    • If the loop exits, the key is not in the array.

Time Complexity

  • Average and Worst Case: O(log n)

Implementation

int binarySearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid; // Key found at index mid
        } else if (arr[mid] < key) {
            low = mid + 1; // Search in the right half
        } else {
            high = mid - 1; // Search in the left half
        }
    }
    return -1; // Key not found
}

Use Cases

  • Efficient for large datasets.
  • Requires that the data is sorted.

Sorting Arrays

Bubble Sort

Algorithm

  1. Outer Loop: Iterate over each element of the array.
  2. Inner Loop: For each element, compare it to the next element.
    • If the current element is greater than the next one, swap them.
  3. Repeat:
    • After each pass, the largest unsorted element "bubbles" to its correct position at the end.

Time Complexity

  • Average and Worst Case: O(n²)
  • Best Case (already sorted): O(n) with optimization.

Implementation

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) { // Number of passes
        for (int j = 0; j < size - i - 1; j++) { // Pairwise comparisons
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j + 1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Steps Explained

  • First Pass:

    • Compare arr[0] and arr[1], swap if necessary.
    • Continue for all elements up to arr[size - 1].
    • Largest element moves to arr[size - 1].

  • Subsequent Passes:

    • Repeat the process, ignoring the already sorted elements at the end.

Optimization: Early Termination

  • Introduce a flag to monitor if any swaps occurred during a pass.
  • If no swaps occurred, the array is sorted, and you can break early.
Optimized Implementation
void optimizedBubbleSort(int arr[], int size) {
    int swapped;
    for (int i = 0; i < size - 1; i++) {
        swapped = 0; // Reset swap flag
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1; // Set swap flag
            }
        }
        if (swapped == 0) {
            break; // The array is sorted
        }
    }
}

Applications of Sorting

  • Searching: Prepare data for efficient searches (e.g., binary search).
  • Data Organization: Facilitates data analysis and reporting.
  • Duplicate Removal: Easier to identify duplicates in sorted data.
  • Data Normalization: Sorting data before processing.

Best Practices with Arrays

Bounds Checking

  • Ensure Valid Indices:
    • Always check that your index is within 0 and array_size - 1.
  • Avoid Out-of-Bounds Access:
    • Accessing beyond array boundaries can lead to undefined behavior, crashes, or security vulnerabilities.

Initializing Arrays

  • Initialize Arrays:
    • Set default values to avoid working with garbage values.
  • Global vs. Local:
    • Global/static arrays are automatically initialized to zero.
    • Local (automatic) arrays contain garbage values unless explicitly initialized.

Passing Arrays to Functions

  • Prevent Stack Overflow:
    • Be cautious when passing large arrays by value; it can consume significant stack memory.
  • Use Pointers When Appropriate:
    • For large data, pass a pointer to the array to avoid copying the entire array.

Memory Considerations

  • Large Arrays:
    • Be aware that large arrays consume significant memory.
    • Consider using dynamic memory allocation (malloc, calloc, realloc, free) for very large arrays.

Multi-Dimensional Arrays

  • Visualization:
    • Think of 2D arrays as arrays of arrays.
  • Index Management:
    • Carefully manage loop variables and indices when traversing multi-dimensional arrays.

Avoiding Magic Numbers

  • Use Constants:

    • Instead of hardcoding numbers, define constants or use #define directives.

      #define SIZE 10
int numbers[SIZE];

  • Improves Readability:

    • Makes code easier to understand and maintain.

Documentation

  • Comment Your Code:
    • Explain the purpose of arrays, especially when sizes and dimensions are critical.
  • Function Comments:
    • Document functions that manipulate arrays, including preconditions (e.g., arrays must be sorted).

Error Handling

  • Robust Functions:
    • When writing functions that manipulate arrays, include error checking for invalid inputs.

Post a Comment