Unit 4 - Notes

CSE109

Unit 4: Arrays and Pointers

1. Introduction to Arrays

An array is a collection of variables of the same data type that are stored in contiguous memory locations. It allows the storage of multiple values under a single variable name, accessible via indices.

Declaring and Initializing Arrays

Declaration Syntax:
data_type array_name[array_size];

Initialization:
Arrays can be initialized at the time of declaration.

Static Initialization:

    int numbers[5] = {10, 20, 30, 40, 50};
    int partial[5] = {1, 2}; // Remaining elements become 0
    int autoSize[] = {1, 2, 3}; // Size inferred as 3

Dynamic Initialization: Using loops to input values at runtime.

2. Defining and Processing Arrays

One Dimensional (1D) Arrays

A linear list of elements.

Memory Layout: Elements are stored sequentially. If address of arr[0] is 1000 and type is int (4 bytes), arr[1] is at 1004.
Access: arr[index] where index starts at 0.

Processing Logic:

int arr[5];
// Input
for(int i = 0; i < 5; i++) {
    scanf("%d", &arr[i]);
}
// Output
for(int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);
}

Two Dimensional (2D) Arrays

An array of arrays, visualized as a matrix or table with rows and columns.

Declaration: int matrix[rows][cols];

Initialization:

    int mat[2][3] = {
        {1, 2, 3}, // Row 0
        {4, 5, 6}  // Row 1
    };

Processing: Requires nested loops.

    for(int i = 0; i < rows; i++) {       // Outer loop for rows
        for(int j = 0; j < cols; j++) {   // Inner loop for columns
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

3. Array Applications and Operations

Common Applications:

Storing data tables (Matrices).
Implementing other data structures (Stacks, Queues, Heaps).
Databases and caching mechanisms.
String processing (Character arrays).

Passing Arrays to Functions

In C, arrays are passed to functions by reference (decaying to a pointer to the first element).

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

int main() {
    int nums[3] = {1, 2, 3};
    printArray(nums, 3); // Passing array name
}

Inserting and Deleting Elements

Insertion:
To insert an element at index pos, elements from pos to the end must be shifted one position to the right.

// Insert 'val' at 'pos'
for (int i = n; i >= pos; i--) {
    arr[i] = arr[i - 1];
}
arr[pos - 1] = val;
n++; // Increase size count

Deletion:
To delete an element at index pos, elements from pos+1 to the end must be shifted one position to the left to fill the gap.

// Delete element at 'pos'
for (int i = pos - 1; i < n - 1; i++) {
    arr[i] = arr[i + 1];
}
n--; // Decrease size count

4. Searching and Sorting

Linear Search

Method: Iterates through the array sequentially from the first element.
Condition: Works on sorted or unsorted arrays.
Complexity: O(n).
Logic: Compare target with arr[i]. If match, return index; otherwise continue.

Binary Search

Method: Divide and conquer.
Condition: Array must be sorted.
Complexity: O(log n).
Logic:
1. Find mid = (low + high) / 2.
2. If arr[mid] == key, return mid.
3. If key < arr[mid], search left half (high = mid - 1).
4. If key > arr[mid], search right half (low = mid + 1).

Bubble Sort

Method: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Complexity: O(n²).

Logic:

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

5. Introduction to Pointers

A pointer is a variable that stores the memory address of another variable.

Declaration and Initialization

Declaration: data_type *pointer_name;

Initialization: Using the address-of operator (&).

    int a = 10;
    int *ptr = &a; // ptr holds the address of 'a'

Pointer Operators

& (Address-of Operator): Returns the memory address of a variable.
*`` (Dereference/Indirection Operator):** Returns the value stored at the address held by the pointer.

Pointer Expressions and Arithmetic

Pointers operate based on the size of the data type they point to.

Increment (ptr++): Moves to the next memory location based on type size (e.g., +4 bytes for int).
Decrement (ptr--): Moves to the previous memory location.
Addition (ptr + n): Skips n elements forward.
Subtraction (ptr1 - ptr2): Returns the number of elements between two pointers (valid only if both point to the same array).

6. Types of Pointers

1. Null Pointer

A pointer that points to nothing. It is a best practice to initialize pointers to NULL if not assigned a valid address immediately.
int *p = NULL;

2. Dangling Pointer

A pointer that points to a memory location that has been deleted (freed) or is out of scope.

int *ptr = (int *)malloc(sizeof(int));
free(ptr); 
// ptr is now dangling. It points to freed memory.
ptr = NULL; // Fix: Assign NULL immediately after free.

3. Wild Pointer

A pointer that has not been initialized to anything (not even NULL). It points to an arbitrary ("garbage") memory location. Using this can crash the program.
int *p; // Wild pointer

4. Generic (Void) Pointer

A pointer that has no associated data type. It can hold addresses of any type but cannot be dereferenced directly without typecasting.

int a = 10;
void *ptr = &a;
printf("%d", *(int*)ptr); // Must typecast to (int*) before dereferencing

7. Advanced Pointer Operations

Passing Pointer to a Function (Call by Reference)

Allows a function to modify the actual values of the arguments.

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}
// Call: swap(&a, &b);

Pointer and One Dimensional Array

The name of an array acts as a constant pointer to the first element.

arr is equivalent to &arr[0].
*(arr + i) is equivalent to arr[i].
(arr + i) is the address of the i-th element.

Pointer to a Group of 1D Arrays (Pointer to Array)

A pointer that points to an entire array, rather than just the first element. Used mostly with 2D arrays.

Syntax: data_type (*ptr)[size];

Example:

    int arr[5] = {1, 2, 3, 4, 5};
    int (*p)[5] = &arr; 
    // p points to the whole array block of 5 integers.
    // p++ would skip the entire 5 integers (20 bytes).

Array of Pointers

An array where each element is a pointer.

Syntax: data_type *array_name[size];
Usage: Often used for handling strings of different lengths or ragged arrays.