Arrays & Strings: Storage, Manipulation & Real-World Data

TAKEAWAYS:

• Arrays store contiguous memory blocks of the same data type, enabling efficient indexing and bulk operations.
• Strings in C are null-terminated character arrays, requiring careful handling of memory and bounds.
• Sorting algorithms (e.g., Bubble Sort, Selection Sort) transform arrays into ordered sequences for faster searches.
• 2D arrays model matrices (e.g., matrices in linear algebra) and grids (e.g., game boards), while multi-dimensional arrays generalize this.
• String operations (concatenation, comparison, substring extraction) are foundational for text processing in apps like eSewa and Daraz.
• Memory management for arrays/strings is critical to avoid buffer overflows and undefined behavior.

1. Introduction to Arrays

Arrays are fixed-size collections of elements of the same data type, stored in contiguous memory locations. They allow efficient access via indices (0-based in C).

1.1 Array Declaration and Initialization

// Declaration (size must be constant)
int arr[5]; // Uninitialized array of 5 integers

// Initialization (all elements set to 0 by default)
int arr2[3] = {10, 20, 30}; // Explicit initialization
int arr3[3] = {10};         // Remaining elements = 0
int arr4[] = {1, 2, 3};     // Size inferred (4)

Visualization: Memory Layout of Arrays

Address: 1000  1004  1008  100C  1010
Value:   10    20    30    0     0

Each element occupies sizeof(int) bytes (typically 4 bytes).

1.2 Accessing and Traversing Arrays

#include <stdio.h>
int main() {
    int arr[4] = {5, 10, 15, 20};
    for (int i = 0; i < 4; i++) {
        printf("arr[%d] = %d\n", i, arr[i]);
    }
    return 0;
}

Output:

arr[0] = 5
arr[1] = 10
arr[2] = 15
arr[3] = 20

1.3 Array Bounds and Safety

• No built-in bounds checking in C → danger of buffer overflows.
• Example of unsafe access:

  int arr[3] = {1, 2, 3};
  printf("%d", arr[5]); // Undefined behavior (accesses memory beyond array)
  

• Solution: Always validate indices before access.

2. Multidimensional Arrays

Multidimensional arrays generalize 2D tables (e.g., matrices) or higher-dimensional grids.

2.1 2D Array Declaration and Initialization

// Declaration
int matrix[3][3]; // 3x3 matrix

// Initialization
int matrix2[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

Visualization: 2D Array Memory Layout

Address: 1000  1004  1008 | 100C  1010  1014
Value:    1    2    3    |    4    5    6

Rows are contiguous, but columns are not.

2.2 Accessing 2D Arrays

#include <stdio.h>
int main() {
    int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
    printf("matrix[1][2] = %d\n", matrix[1][2]); // Output: 6
    return 0;
}

2.3 Multi-Dimensional Arrays (3D+)

// 3D array (e.g., voxel grid for 3D games)
int voxel[2][2][2] = {
    {{1, 2}, {3, 4}},
    {{5, 6}, {7, 8}}
};

Use Case: Storing pixel data in image processing or game levels.

3. Arrays vs. Structures

Example Comparison:

// Array of integers
int scores[3] = {90, 85, 92};

// Structure of student records
struct Student {
    int roll;
    char name[50];
};
struct Student students[3] = {
    {1, "Alice"},
    {2, "Bob"},
    {3, "Charlie"}
};

4. Sorting Arrays

Sorting rearranges elements in ascending/descending order. Common algorithms:

• Bubble Sort (simple, inefficient for large arrays)
• Selection Sort (better than Bubble for small datasets)
• Insertion Sort (efficient for nearly sorted data)

4.1 Bubble Sort Implementation

flowchart TD
    A["Start"] --> B["i = 0 to n-1"]
    B --> C["j = 0 to n-i-2"]
    C --> D["if arr[j] > arr[j+1] swap"]
    D -->|"Yes"| E["Repeat"]
    E --> C
    D -->|"No"| F["Increment j"]
    F -->|"j < n-i-1"| C
    F -->|"Done"| G["Increment i"]
    G -->|"i < n-1"| B
    G --> H["End"]

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Tracing Bubble Sort on [5, 3, 8, 4]:

4.2 Selection Sort Implementation

flowchart TD
    A["Start"] --> B["i = 0 to n-1"]
    B --> C["min_idx = i"]
    C --> D["j = i+1 to n-1"]
    D --> E["if arr[j] < arr[min_idx] update min_idx"]
    E -->|"Yes"| D
    E -->|"No"| F["Swap arr[i] and arr[min_idx]"]
    F --> G["Increment i"]
    G -->|"i < n-1"| B
    G --> H["End"]

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

Tracing Selection Sort on [64, 25, 12, 22, 11]:

5. Searching Arrays

5.1 Linear Search

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

Time Complexity: O(n) (worst case).

5.2 Binary Search (Requires Sorted Array)

flowchart TD
    A["Start"] --> B["low = 0, high = n-1"]
    B --> C["mid = (low + high)/2"]
    C --> D["if arr[mid] == key return mid"]
    D -->|"Yes"| E["Key found"]
    D -->|"No"| F["if key < arr[mid] high = mid-1"]
    F -->|"Yes"| B
    F -->|"No"| G["low = mid+1"]
    G --> B
    G --> H["Key not found"]

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n-1;
    while (low <= high) {
        int mid = (low + high)/2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

Time Complexity: O(log n).

6. Strings in C

Strings in C are null-terminated character arrays ('\0' marks the end).

6.1 String Declaration and Initialization

char str1[6] = {'H', 'e', 'l', 'l', 'o', '\0'}; // Explicit null
char str2[] = "Hello"; // Implicit null (size = 6)

6.2 String Operations

Common functions in <string.h>:

• strlen(): Returns length (excluding null).
• strcpy(): Copies one string to another.
• strcat(): Concatenates two strings.
• strcmp(): Compares two strings.

Example:

#include <stdio.h>
#include <string.h>
int main() {
    char str1[20] = "Hello";
    char str2[] = " World";
    strcat(str1, str2); // str1 = "Hello World"
    printf("%s\n", str1);
    return 0;
}

6.3 Manual String Operations

// Concatenate two strings manually
void strcatManual(char dest[], char src[]) {
    int i = 0, j = 0;
    while (dest[i] != '\0') {
        i++;
    }
    while (src[j] != '\0') {
        dest[i] = src[j];
        i++;
        j++;
    }
    dest[i] = '\0';
}

Tracing strcatManual on dest = "Hi" and src = " there":

7. Practical Applications of Arrays and Strings

7.1 eSewa: Transaction Queues

• Idea: Arrays model waiting queues for transaction processing.
• How: Transactions are stored in an array, processed in FIFO order (like a queue).
• Example: If 5 users initiate payments simultaneously, eSewa stores them in an array and processes them sequentially.

7.2 Daraz: Inventory Management

• Idea: 2D arrays track stock levels for products.
• How: inventory[product_id][warehouse_id] stores quantity.
• Example:

  int inventory[100][5]; // 100 products, 5 warehouses
  inventory[42][2] = 15; // Product 42 has 15 units in warehouse 2
  

7.3 Pathao: Ride Allocation

• Idea: Sorting algorithms optimize driver-rider matching.
• How: Pathao sorts drivers by proximity (using arrays of coordinates) to assign the nearest driver first.
• Example:

  struct Driver {
      int id;
      float x, y; // Coordinates
  };
  Driver drivers[100];
  // Sort drivers by distance from rider (using bubble sort)
  

8. Exam Tips

1. Arrays vs. Pointers:

   • Arrays decay to pointers when passed to functions (e.g., func(arr) becomes func(&arr[0])).
   • Example:

     void printArray(int *arr, int size) { ... }
     int main() {
         int arr[3] = {1, 2, 3};
         printArray(arr, 3); // Passes address of arr[0]
     }
     

2. String Safety:

   • Always check for null terminators when copying/concatenating strings to avoid buffer overflows.
   • Example of unsafe code:

     char small[5] = "Hi";
     char large[] = "Hello World";
     strcpy(small, large); // Undefined behavior (small too small)
     

3. Sorting Algorithms:

   • Know time complexity (e.g., Bubble Sort: O(n²), Binary Search: O(log n)).
   • For exams, trace 1-2 steps of a sorting algorithm on a small array.

4. 2D Arrays:

   • Remember that matrix[i][j] is row-major order (all rows stored contiguously).
   • Example:

     int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
     // Memory layout: 1, 2, 3, 4, 5, 6
     

5. Common Pitfalls:

   • Off-by-one errors in loops (e.g., for (int i = 0; i <= n; i++) → infinite loop).
   • Uninitialized arrays (use memset or explicit initialization).
   • String operations without null checks (e.g., strlen("") returns 0, not 1).

6. Practical Questions:

   • Expect programming questions on:
     • Sorting/searching arrays.
     • Manipulating strings (e.g., reverse a string, check palindrome).
     • 2D array operations (e.g., matrix multiplication).
   • Example Question: "Write a program to reverse a string using recursion."

Final Note: Arrays and strings are fundamental for data manipulation in C. Master their memory layout, operations, and real-world applications (like eSewa queues or Daraz inventory) to excel in exams and practical projects. Always validate indices and handle strings carefully to avoid runtime errors.