Unit 5: Introduction to Arrays

An array is a collection of elements of the same data type stored in contiguous memory locations and accessed through a single name and an integer index. Arrays let a program hold many related values (marks of 60 students, pixels of an image) without declaring a separate variable for each, and they underpin strings, matrices, and every table-driven algorithm in C.

• Homogeneous: every element shares one type: int, float, char, or a struct.
• Contiguous: element i sits at base_address + i * sizeof(type); this arithmetic makes access O(1).
• Zero-based indexing: valid indices run 0 to size-1; C performs no bounds checking, so a[size] is undefined behaviour.
• Fixed size: the length is fixed at declaration (for classic arrays) and must be a compile-time constant.
• Name as address: the array name decays to a pointer to its first element (a equals &a[0]) in most expressions.

II. Declaring Arrays in C

Declaration reserves the block of memory and fixes the element type and count.

A. declaring arrays in C

• Syntax: type name[size]; — e.g. int marks[5]; reserves 5 * sizeof(int) bytes (typically 20).
• Size rule: size is a positive integer constant or #defined macro; int a[N] needs N known at compile time.
• Initialization at declaration:
  • Full list: int a[5] = {10, 20, 30, 40, 50};
  • Partial: int a[5] = {10, 20}; sets remaining elements to 0.
  • Size inferred: int a[] = {1, 2, 3}; creates a 3-element array.
  • All zero: int a[100] = {0}; clears every element.
• Storage and default values: an uninitialized array with automatic (local) storage holds garbage; a static or global array defaults to 0.

III. Defining and Processing 1D and 2D Arrays

Processing means visiting elements by index, usually inside loops, to read, transform, or output them.

A. defining and processing 1d arrays

A one-dimensional array is a single row of elements addressed by one index.

• Access: a[i] reads or writes the element at index i.
• Traversal: a for loop drives the index across the range.
• Input/output pattern:

int a[5], i, sum = 0;
for (i = 0; i < 5; i++)
    scanf("%d", &a[i]);        /* &a[i] gives address of element */
for (i = 0; i < 5; i++)
    sum += a[i];               /* accumulate */

• Common operations: summation, finding max/min (track a running best), reversing (swap a[i] with a[n-1-i]), counting matches.

B. defining and processing 2d arrays

A two-dimensional array is a table of rows and columns, stored in memory row by row (row-major order).

• Declaration: type name[rows][cols]; — int m[3][4]; holds 12 elements.
• Access: m[i][j] where i is the row, j the column.
• Initialization: int m[2][3] = {{1,2,3},{4,5,6}}; — inner braces group rows.
• Nested-loop processing:

int m[3][3], i, j;
for (i = 0; i < 3; i++)
    for (j = 0; j < 3; j++)
        scanf("%d", &m[i][j]);

• Applications: matrices (addition adds m1[i][j]+m2[i][j]), transpose (swap m[i][j] and m[j][i]), grids and tables of records.

IV. Array Applications: Sorting and Searching

Sorting arranges elements into order; searching locates a target. Both are the classic workloads that justify arrays.

A. sorting

Sorting reorders elements ascending or descending; bubble sort is the standard teaching algorithm.

• Bubble sort principle: repeatedly compare adjacent pairs and swap if out of order, so the largest value "bubbles" to the end each pass.
• Complexity: two nested loops give O(n²) comparisons; simple but slow for large n.
• Code:

for (i = 0; i < n - 1; i++)
    for (j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j+1]) {           /* swap for ascending */
            temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
        }

• Other methods: selection sort (pick the minimum each pass), insertion sort (insert each element into a sorted prefix) — also O(n²) but with fewer swaps.

B. searching

Searching returns the position of a target value, or a sentinel like -1 if absent.

1. Linear search: scan every element until a match. Works on unsorted data; O(n).

for (i = 0; i < n; i++)
    if (a[i] == key) { pos = i; break; }

2. Binary search: requires a sorted array; repeatedly halve the range by comparing the middle element. O(log n).

low = 0; high = n - 1;
while (low <= high) {
    mid = (low + high) / 2;
    if (a[mid] == key)      { pos = mid; break; }
    else if (a[mid] < key)  low = mid + 1;
    else                    high = mid - 1;
}

• Trade-off: linear search is general but slow; binary search is fast but needs prior sorting.

V. Character Arrays and Strings

In C a string is not a distinct type but a character array terminated by the null character '\0'.

A. character arrays

A character array stores a sequence of char values and, when null-terminated, functions as a string.

• Declaration: char name[20]; reserves 20 bytes.
• Null terminator: the '\0' (ASCII 0) marks the end; a 5-letter word like "Hello" needs 6 bytes.
• Access: individual characters via index, name[0] = 'H';.

B. declaration and initialization of string

Strings can be built character by character or from a string literal.

• Character list: char s[6] = {'H','e','l','l','o','\0'}; — you must add '\0' yourself.
• String literal: char s[6] = "Hello"; — the compiler appends '\0' automatically.
• Size inferred: char s[] = "Hello"; allocates 6 bytes.
• Input/output:
  • scanf("%s", s): reads one whitespace-delimited word; no & since s is already an address.
  • gets/fgets: read a full line including spaces (fgets(s, size, stdin) is the safe choice).
  • printf("%s", s): prints until '\0'.

C. string handling functions

The <string.h> library supplies functions that operate on null-terminated strings.

• strlen(s): returns length excluding '\0' — strlen("Hello") is 5.
• strcpy(dest, src): copies src into dest including the terminator.
• strcat(dest, src): appends src to the end of dest.
• strcmp(s1, s2): returns 0 if equal, negative if s1 < s2, positive if s1 > s2 (lexicographic).
• strrev(s): reverses the string (non-standard, common on some compilers).
• Note: str1 == str2 compares addresses, not contents; always use strcmp for equality.

VI. Structure and Union

Structures and unions are user-defined types that group members of different types under one name, extending arrays (which are homogeneous) to heterogeneous data.

A. structure: declaration, definition and initialization

A structure groups related members that each occupy their own memory, so a struct holds all members at once.

• Declaration (template):

struct Student {
    int roll;
    char name[20];
    float marks;
};

• Definition (variable): struct Student s1; allocates memory sized as the sum of members (plus padding).
• Initialization: struct Student s1 = {1, "Amit", 88.5}; fills members in order.
• Member access: dot operator s1.roll = 1;; through a pointer, arrow operator p->roll.
• Size: sizeof(struct Student) is at least the sum of member sizes; the compiler may add padding for alignment.
• Arrays of structures: struct Student cls[60]; stores 60 records, each cls[i].marks.

B. union: declaration, definition and initialization

A union groups members that share the same memory block, so only one member holds a valid value at a time.

• Declaration:

union Data {
    int i;
    float f;
    char c;
};

• Definition: union Data d;
• Shared storage: all members start at the same address; sizeof(union Data) equals the size of the largest member (here float, 4 bytes), not their sum.
• Initialization: only the first member may be brace-initialized — union Data d = {10}; sets d.i.
• Behaviour: writing d.f = 3.14; overwrites the bytes, so a later read of d.i gives meaningless data.

1. Structure: separate storage for every member; use when all fields are needed together (a complete record). Larger memory footprint.
2. Union: overlapping storage for one member at a time; use to save memory when fields are mutually exclusive (a value that is sometimes an int, sometimes a float). Smaller footprint but only one live member.

• Nesting: structures and unions can contain each other and can be members of arrays, enabling records, tables, and tagged variants for real-world data modelling.