Skip to content

C_Reference_Notes_DSA.md

Latest commit

 

History

History
1457 lines (1190 loc) · 61.8 KB

C_Reference_Notes_DSA.md

File metadata and controls

1457 lines (1190 loc) · 61.8 KB

C Programming & Data Structures (DSA) Reference Notes

This manual is a comprehensive, self-contained reference guide for learning C Programming and core Data Structures and Algorithms (DSA) in C.

Throughout this guide, you will find highlighted Notes pointing out compiler optimizations, memory management guidelines, and potential traps, alongside Practice Questions to test understanding. The Answer Key & Explanations are placed at the absolute end of this document.

Table of Contents

  1. Introduction to C & The Compilation Process
  2. Variables, Core Data Types & Memory Sizes
  3. Operators & Control Flow
  4. Functions, Scopes & Parameter Passing
  5. Arrays & String Manipulation
  6. Pointers: Memory Addresses & Pointer Arithmetic
  7. Structures, Unions & Typedef
  8. Dynamic Memory Allocation (DMA)
  9. DSA 1: Linked Lists (Singly & Doubly Linked Lists)
  10. DSA 2: Stacks & Queues
  11. DSA 3: Trees (Binary Search Trees & Self-Balancing Trees)
  12. Algorithms: Sorting & Searching
  13. Answer Key & Explanations

1. Introduction to C & The Compilation Process

C is a compiled, statically typed, procedural programming language developed by Dennis Ritchie at Bell Labs in 1972. It provides low-level memory access while maintaining structural program organization, making it the bedrock language for operating systems, compilers, database engines, and embedded systems.

The C Compilation Pipeline

Unlike Python, which is interpreted line-by-line, C code must be translated into machine-readable binary code before running. This pipeline consists of four distinct phases:

  1. Preprocessing: Resolves directives starting with #. It expands headers (#include), replaces macros (#define), and strips comments. Output: Pure preprocessed source code (typically .i files).
  2. Compilation: The compiler translates the preprocessed C source code into assembly language instructions specific to the target CPU architecture. Output: Assembly files (.s or .asm).
  3. Assembly: The assembler converts assembly code into machine code instruction sets. Output: Object code binary files (.o or .obj).
  4. Linking: The linker merges multiple object files and external precompiled system libraries (like libc) to resolve function references. Output: The final executable file (.exe or .out).
#include <stdio.h> // Preprocessor Directive

int main() {
    printf("Hello World\n"); // Execution entry point
    return 0; // Return code 0 tells OS process terminated successfully
}

Note

C Memory Layout Segments When a compiled C program runs, it occupies four memory regions:

  • Code Segment (Text): Stores the read-only machine instructions.
  • Data Segment: Divided into Initialized Data (global/static variables initialized with values) and BSS (uninitialized global/static variables defaulted to 0).
  • Stack Segment: Allocates local variables and return addresses for function calls. Grows downward.
  • Heap Segment: Allocated dynamically at runtime by the programmer (via malloc/calloc). Grows upward.

Common Compiler Flags (GCC/Clang)

When compiling C applications in a production setting, compiler flags configure optimization, safety, and standards behavior:

  • -Wall: Enables all common compiler warnings. Essential for detecting bug patterns early.
  • -g: Generates debugging information required for diagnostic tools like gdb.
  • -O2: Applies a moderate level of compiler optimization for execution speed without inflating executable size.
  • -std=c99: Enforces syntax compliance with the C99 standard specification.

Makefile Basics

For projects spanning multiple source files, recompiling everything manually is tedious. Makefiles automate compilation by building only the source files that have changed:

# Simple Makefile structure
CC = gcc
CFLAGS = -Wall -g -O2

app.exe: main.o helper.o
	$(CC) $(CFLAGS) -o app.exe main.o helper.o

main.o: main.c
	$(CC) $(CFLAGS) -c main.c

helper.o: helper.c
	$(CC) $(CFLAGS) -c helper.c

clean:
	rm -f *.o app.exe

Preprocessor Macros with Parameters

Macros are simple textual replacement tokens resolved during preprocessing. While powerful, unparenthesized macros introduce dangerous precedence bugs:

#include <stdio.h>

// DANGEROUS MACRO: SQUARE(5 + 5) becomes 5 + 5 * 5 + 5 = 35!
#define SQUARE_BAD(x) x * x

// SAFE MACRO: SQUARE(5 + 5) becomes ((5 + 5) * (5 + 5)) = 100
#define SQUARE_SAFE(x) ((x) * (x))

int main() {
    printf("Bad Square: %d\n", SQUARE_BAD(5 + 5));  // Prints 35
    printf("Safe Square: %d\n", SQUARE_SAFE(5 + 5)); // Prints 100
    return 0;
}

🌍 Real-World Analogy

  • Compilation Pipeline: Translating code is like translating a book from English to Japanese:
    • Preprocessor: A proofreader that does find-and-replace text shortcuts (#define), inserts header files (#include), and cuts out draft chapters (#ifdef).
    • Compiler: A translator who converts English sentences to standard Japanese grammar drafts (assembly code).
    • Assembler: A typesetter who prints the drafts into raw stamped pages (machine-readable binary object files).
    • Linker: A bookbinder who gathers the chapters, links footnotes, binds external libraries, and packages them into a single hardcover book (executable).
  • Makefile: A construction foreman's checklist: they only rebuild the sections of the building that were damaged or modified, rather than rebuilding the entire structure from scratch.

💼 Industry Application: Large scale project build tools like the Linux Kernel or Chromium use Makefiles and compiler flags (-O3) to organize compilation of millions of lines of code efficiently, skipping unmodified files to reduce developers' build wait times.

⌨️ Developer Productivity Shortcuts (GDB & Vim & Editors)

Systems programmers write C code and debug algorithms using command-line tools like GDB (GNU Debugger) and Vim. Mastering these console-based commands is essential for low-level development:

1. GDB Debugging Command Shortcuts

When running a compiled binary with debug symbols (gcc -g program.c -o program), load it in GDB (gdb ./program) and use these shorthand command keys:

  • r or run: Starts executing the program from the beginning.
  • b <line_number> or b <function_name>: Sets a breakpoint at the specified line or function.
  • n or next: Executes the next line of code, stepping over function calls (does not enter them).
  • s or step: Executes the next line of code, stepping into function calls.
  • c or continue: Resumes program execution until the next breakpoint is hit or the program exits.
  • p <variable_name>: Prints the current value of a variable in memory.
  • bt or backtrace: Prints the call stack, showing the active functions that led to the current line.
  • q or quit: Exits the GDB debugger console.

2. Vim Editor Console Shortcuts

Vim is the standard terminal editor for C systems programming. Use these modal editing shortcuts:

  • i: Enter Insert Mode (to type code) at the cursor.
  • Esc: Return to Normal Mode (to navigate or run commands).
  • dd / yy / p: Cut line / Copy (yank) line / Paste copied text (in Normal Mode).
  • /pattern: Search for text in the file. Press n to go to the next match.
  • u / Ctrl + r: Undo / Redo the last change.
  • gg / G: Jump to the top / bottom of the document instantly.
  • :w / :q / :wq: Save / Quit / Save and Quit (write-quit).

Practice Questions

  • Question 1: Describe the inputs and outputs of each of the four compilation stages when compiling a C file named program.c.
  • Question 2: Explain what a Makefile is and write a simple Makefile to compile main.c and helper.c into an executable named app.exe using gcc with warning flags.

2. Variables, Core Data Types & Memory Sizes

Datatypes and Specifiers

Variables in C represent named storage addresses. Since C is statically typed, every variable's data type must be declared at write-time so the compiler knows how many bytes to allocate.

Datatype Description Typical Size (bytes) Format Specifier
char Single ASCII Character 1 %c or %d (ASCII integer)
int Standard integer value 4 %d or %i
float Single-precision floating point 4 %f
double Double-precision floating point 8 %lf
void Represents empty/incomplete type 0 N/A

Datatype Qualifiers

  • Size Qualifiers: short, long (e.g., long int allocates 8 bytes).
  • Sign Qualifiers: signed (allows negative numbers), unsigned (non-negative only, doubling upper capacity limit).
  • Type Qualifiers:
    • const: Defines a variable whose value cannot be modified after initialization.
    • volatile: Informs the compiler that a variable's value can be changed by factors outside the program's direct control (e.g., hardware registers, interrupt service routines, or concurrent threads). This disables compiler caching optimizations on that memory address.
#include <stdio.h>

int main() {
    const double PI = 3.14159; // Cannot be reassigned
    volatile int status_register = 0; // CPU will read this from memory every time

    int score = 95;
    double price = 129.99;
    char grade = 'A';
    unsigned int counter = 50000;

    printf("Score: %d, Price: %.2lf, Grade: %c, Counter: %u\n", score, price, grade, counter);
    printf("Size of integer: %zu bytes\n", sizeof(score)); // sizeof returns size_t bytes
    return 0;
}

The sizeof Operator

sizeof is a compile-time operator, not a runtime function. It returns the size in bytes of a data type or expression. Because it evaluates during compilation, expressions inside sizeof are not executed at runtime:

int a = 5;
size_t s = sizeof(a++); // s will store 4 (size of int), but 'a' remains 5!

Type Casting: Implicit vs. Explicit

Type casting changes a value's data type.

  • Implicit Casting (Coercion): Handled automatically by the compiler. Smaller data types are safely promoted to larger ones (e.g., int to double).
  • Explicit Casting: Forced manually by the developer using parentheses. Crucial to prevent integer division trashing or double-to-int data truncation errors:
int sum = 17, count = 5;
double avg_bad = sum / count;          // Avg: 3.00 (Integer division first, then cast to double)
double avg_good = (double)sum / count; // Avg: 3.40 (Explicitly cast sum to double before division)

Important

Initialization and Garbage Values Unlike Python, uninitialized local variables inside C functions do not default to 0 or NULL. Instead, they retain whatever random leftover byte data existed in that stack memory address. Printing or accessing uninitialized variables leads to undefined behavior and garbage outputs. Always initialize variables: int score = 0;.

🌍 Real-World Analogy

  • sizeof: This is like measuring a shipping box's dimensions: you do not open it or care about the items inside; you only measure the outer space it occupies to calculate shipping rates (memory footprint).
  • const: A variable qualified as const is like a museum exhibit behind glass: you can view the values, but you cannot reach in and modify them.
  • volatile: A volatile variable is like a live stock market ticker on a wall screen: the compiler cannot assume the value remains constant just because the program didn't change it; the outside world (hardware registers, interrupt handlers) can change it at any second, so the program must check the screen every time.

💼 Industry Application: Driver developers and embedded system programmers use volatile pointers to read direct physical inputs from temperature sensors or network chips, as those values change independently of the CPU instruction execution loop.

Practice Questions

  • Question 3: Explain the difference in value range between a signed char and an unsigned char (both occupying 1 byte of memory).
  • Question 4: What does the volatile keyword do in C, and why is it critical when interacting with memory-mapped I/O hardware?

3. Operators & Control Flow

Operators in C

  • Arithmetic: +, -, *, / (Integer division yields integer; E.g., 5 / 2 evaluates to 2), % (Modulo, only works on integers).
  • Increment/Decrement: ++x (prefix increment: update then execute), x++ (postfix increment: execute then update).
  • Relational: ==, !=, >, <, >=, <=.
  • Logical: && Logical AND (short-circuiting), || Logical OR (short-circuiting), ! Logical NOT.
  • Bitwise: Operates directly on binary bits: & AND, | OR, ^ XOR, ~ NOT, << Left Shift, >> Right Shift.
  • Comma Operator (,): Evaluates multiple expressions from left to right, returning the value of the rightmost expression:
int a = (x = 5, y = 10, x + y); // x becomes 5, y becomes 10, a becomes 15

Operator Precedence & Associativity

Operators are evaluated based on their precedence. When operators have equal precedence, their associativity (left-to-right or right-to-left) determines the order:

Precedence Operator Category Operators Associativity
1 Postfix (), [], ->, ., post++/post-- Left-to-Right
2 Unary !, ~, pre++/pre--, +, -, * (dereference), &, sizeof, casting Right-to-Left
3 Multiplicative *, /, % Left-to-Right
4 Additive +, - Left-to-Right
5 Shift <<, >> Left-to-Right
6 Relational <, <=, >, >= Left-to-Right
7 Equality ==, != Left-to-Right
8 Bitwise & then ^ then ` `
9 Logical && then `
10 Conditional (Ternary) ? : Right-to-Left
11 Assignment =, +=, -=, *=, /=, etc. Right-to-Left
12 Comma , Left-to-Right

Control Flow (Decision Making)

C uses if-else blocks and switch-case statements to fork decisions.

// Switch statement syntax
int option = 2;
switch (option) {
    case 1:
        printf("Option 1\n");
        break;
    case 2:
        printf("Option 2\n");
        break; // break is required to prevent falling through to subsequent cases!
    default:
        printf("Fallback Option\n");
}

Loops

  • for loop: Used when loop iteration count is defined.
  • while loop: Runs as long as a condition evaluates to non-zero (True).
  • do-while loop: Executes the body block at least once before checking the loop condition.
// Do-While loop example
int count = 5;
do {
    printf("%d ", count);
    count++;
} while (count < 5); // Prints: 5

Note

C Boolean Evaluation In C, there was no native built-in boolean datatype prior to C99 (which introduced <stdbool.h>). Any numeric value that is 0 evaluates to False. Any non-zero numeric value (including negative values) evaluates to True.

🌍 Real-World Analogy

  • Operator Precedence: This follows the exact same logic as mathematics order of operations (PEMDAS/BODMAS): multiplication and division are performed before addition and subtraction unless parentheses override the default flow.
  • Bitwise Operators: Flipping bits is like operating a light switch panel on a wall: you can toggle individual switches (&, |, ^) on and off to control specific circuits without disturbing the states of any other switches.

💼 Industry Application: Graphic rendering engines and network packet protocols pack multiple configuration flags into a single integer using bitwise operations (bitmasking) to optimize network bandwidth and memory footprint.

Practice Questions

  • Question 5: What is printed by this code block, and why? 
    int x = 5;
int y = x++;
printf("x=%d, y=%d", x, y);

4. Functions, Scopes & Parameter Passing

Functions segment programs into reusable components.

Syntax & Declaration

C requires every function to be declared or defined before it is called. If you want to define a function below the main entry point, you must place a function prototype (forward declaration) at the top of the file.

#include <stdio.h>

// Function Prototype
int add(int a, int b);

int main() {
    printf("Sum: %d\n", add(5, 7));
    return 0;
}

// Function Definition
int add(int a, int b) {
    return a + b;
}

Parameter Passing

  • Call by Value: A copy of the arguments is passed to the function parameters. Modifying the parameter inside the function has no effect on the caller's variables.
  • Call by Reference (Using Pointers): The memory addresses of variables are passed to the function. This allows the function to modify the caller's variables directly by dereferencing those pointers.
// Call by Reference Swap Function
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

Recursion Patterns

A recursive function is one that calls itself to solve smaller instances of the same problem. Every recursive function must contain a base case to halt recursion and prevent a stack overflow crash:

// Factorial recursion: n! = n * (n-1)!
int factorial(int n) {
    if (n <= 1) return 1; // Base case
    return n * factorial(n - 1); // Recursive case
}

Function Pointers & Callbacks

In C, functions reside in memory, and their entry point address can be stored in function pointers. This allows passing behaviors as parameters (callbacks):

#include <stdio.h>

// Callback function examples
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }

// Function taking a function pointer as a parameter (Callback)
void execute_op(int (*op_ptr)(int, int), int x, int y) {
    printf("Result: %d\n", op_ptr(x, y));
}

int main() {
    // Declaring function pointer matching signature: int (int, int)
    int (*calc)(int, int) = add;
    execute_op(calc, 10, 5);      // Prints 15
    execute_op(subtract, 10, 5);  // Prints 5
    return 0;
}

Variable Scopes

  • Local Variables: Exist only within the stack frame of their declaring function.
  • Global Variables: Declared outside all functions. Accessible throughout the entire file.
  • Static Local Variables: Declared inside a function but retained across function calls. They are initialized once and reside in the Data Segment, preserving their value even after the function returns.

🌍 Real-World Analogy

  • Functions: A function is like a department employee hired to do a specific job.
  • Call-by-Value: This is like photocopying a document and giving the copy to the employee: they can scribble on the copy, but your original document on your desk remains untouched.
  • Call-by-Reference: Handing over pointer addresses is like passing the original document: any edits they make directly modify your original copy.
  • Function Pointers: A function pointer is like a TV remote's programmable buttons: you can assign different channels (functions) to the same button depending on user configuration.

💼 Industry Application: The standard C library function qsort() utilizes function pointers as callback comparators, allowing developers to pass custom comparison criteria to sort arrays of custom structs.

Practice Questions

  • Question 6: What is the output of three consecutive calls to increment_counter()? 
    void increment_counter() {
    static int count = 0;
    count++;
    printf("%d ", count);
}
  • Question 7: Declare a function pointer variable named op that points to a function taking two double arguments and returning a double. Show how to call it.

5. Arrays & String Manipulation

Arrays

An array is a contiguous memory block storing multiple elements of the same data type.

Syntax

datatype array_name[array_size];

Because memory is contiguous, element indexing can be resolved instantly via math computations: address_of_index = base_address + index * sizeof(datatype).

int scores[3] = {85, 90, 95}; // Initialized array
scores[1] = 92;               // Overwriting element index 1

Multidimensional (2D) Arrays

2D arrays represent matrices and are stored in memory in row-major order (row-by-row consecutively):

int matrix[2][3] = {
    {1, 2, 3}, // Row 0
    {4, 5, 6}  // Row 1
};
// In memory: [1, 2, 3, 4, 5, 6]

Passing Arrays to Functions

In C, when an array is passed to a function, it decays into a pointer referencing its first element. Therefore, inside the function, the sizeof operator will return the size of the pointer, not the array. You must pass the size as a separate parameter:

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

Variable-Length Arrays (VLAs)

Introduced in C99, VLAs allow allocating an array on the stack whose size is determined at runtime.

  • Risk: Large VLA sizes can easily trigger a stack overflow since stack size is highly limited compared to the heap. Avoid VLAs for large or unvalidated size limits.
void create_vla(int n) {
    int temp_arr[n]; // Stack allocated VLA
    temp_arr[0] = 42;
}

Warning

Array Bound Safety C does not perform bound-checking on array reads or writes. If you declare an array of size 5 and attempt to write to index 10 (scores[10] = 100), the C compiler will run the instruction without warning. This overwrites whatever data exists at that memory location, resulting in memory corruption, segmentation faults, or security vulnerabilities (buffer overflows).

C Strings (Character Arrays)

In C, a string is a character array terminated by a special null character ('\0').

Syntax

char message[] = "Hello"; 
// Behind the scenes: {'H', 'e', 'l', 'l', 'o', '\0'}

Common Library Functions (<string.h>)

  • strlen(str): Returns the number of characters in the string (excludes the null-terminator \0).
  • strcpy(dest, src): Copies the source string to the destination array.
  • strcat(dest, src): Appends the source string to the end of the destination array.
  • strcmp(str1, str2): Compares two strings character-by-character. Returns 0 if they match, a positive value if str1 is lexicographically greater, and a negative value if str2 is greater.
#include <stdio.h>
#include <string.h>

int main() {
    char source[] = "World";
    char destination[20] = "Hello "; // Must allocate enough byte space for concats!

    strcat(destination, source);
    printf("Resulting String: %s\n", destination); // Resulting String: Hello World
    printf("Length: %zu\n", strlen(destination));   // Length: 11
    return 0;
}

🌍 Real-World Analogy

  • Arrays: An array is like a row of school lockers: they are contiguously laid out in a hallway, all the same size, and if you know the starting locker number, you can find the $n$-th locker instantly by counting indices.
  • 2D Arrays: A 2D array is like a spreadsheet grid with rows and columns.
  • Buffer Overflow: Writing past array limits is like writing past the edge of a whiteboard: you run out of designated space and write directly onto the wall, defacing other data.

💼 Industry Application: High-performance graphic frame buffers and audio processing engines represent multi-channel frames as flat contiguous arrays to optimize CPU cache hits and memory access speeds.

Practice Questions

  • Question 8: What is the byte size of char word[] = "C Language";? Why does strlen(word) return a different value than sizeof(word)?

6. Pointers: Memory Addresses & Pointer Arithmetic

Pointers are variables that store the memory addresses of other variables.

Declaring & Dereferencing

  • & (Address-of operator): Retrieves the memory address of a variable.
  • * (Dereference operator): Declares pointer variables or accesses the value stored at a pointer's target address.
int val = 10;
int *ptr = &val; // ptr stores the address of val (e.g., 0x7ffd2)

printf("Address: %p\n", (void*)ptr);
printf("Value stored in target address: %d\n", *ptr); // dereferencing: 10
*ptr = 20; // Modifies the value of val to 20

Pointer Arithmetic

Pointers are memory addresses (hexadecimal numbers), meaning you can perform arithmetic operations on them. When you increment a pointer (ptr++), C increments it by sizeof(pointed_datatype) bytes, automatically pointing to the next element in memory.

int numbers[3] = {10, 20, 30};
int *p = numbers; // Array name evaluates to the base address of its first element: &numbers[0]

printf("First element: %d\n", *p);     // 10
p++; // Increments address pointer by 4 bytes (sizeof int)
printf("Second element: %d\n", *p);    // 20

Note

Array Name Pointer Equivalence The array variable syntax arr[i] is internally evaluated by the compiler as *(arr + i). Because addition is commutative, *(i + arr) is also valid, meaning i[arr] is syntactically equivalent to arr[i] in C!

Pointer Qualifiers (Const Pointers)

  • const int *ptr: Pointer to a constant integer. The value pointed to cannot be changed, but you can change the pointer address.
  • int * const ptr: Constant pointer to an integer. The value pointed to can be changed, but the pointer address cannot.
  • const int * const ptr: Constant pointer to a constant integer. Neither the address nor the value can be modified.
int x = 10, y = 20;
const int *p1 = &x; 
// *p1 = 15; // ERROR: Value is read-only
p1 = &y;     // OK: Address can change

int * const p2 = &x;
*p2 = 15;    // OK: Value can change
// p2 = &y;  // ERROR: Address is read-only

Generic Pointers (void*)

A void* is a generic pointer that can point to any data type without casting. However, it cannot be dereferenced directly or subjected to pointer arithmetic without first casting to a specific concrete type:

int a = 5;
void *g_ptr = &a;
// printf("%d", *g_ptr); // ERROR: Cannot dereference void*
printf("%d", *(int*)g_ptr); // OK: Cast first, then dereference

Double Pointers (Pointers to Pointers)

A double pointer stores the address of another pointer. It is commonly used to modify a pointer passed into a function or to construct dynamic 2D arrays:

int val = 42;
int *p = &val;
int **dp = &p; // dp points to p, which points to val
printf("%d\n", **dp); // Prints 42

Common Pointer Pitfalls

  • Null Pointer: A pointer assigned to point to address 0 (e.g., int *ptr = NULL;). Dereferencing a NULL pointer instantly crashes the program with a segmentation fault.
  • Dangling Pointer: A pointer referencing a memory address that has already been deallocated (e.g., pointing to local memory returned from an exited function or freed dynamic allocation).
  • Wild Pointer: An uninitialized pointer pointing to a random garbage memory address.

🌍 Real-World Analogy

  • Pointers: A pointer is like a GPS coordinate or a street address written on a card: it tells you exactly where to find a house, but it is not the house itself.
  • Double Pointers: A double pointer is like a map that leads you to another map.
  • Generic Pointers (void*): A generic pointer is like a universal power adapter: it can fit into any socket, but you must declare what device it is powering (type cast) before turning the power on.
  • Dangling Pointer: This is like an eviction notice on a torn-down building: the building is gone (freed), but you still have the address card and might try to visit it, resulting in a crash.

💼 Industry Application: Operating systems use raw pointers to manage virtual memory tables, process stack boundaries, and write drivers that map hardware buffers directly into user space.

Practice Questions

  • Question 9: Predict the values printed by this program: 
    int values[4] = {11, 22, 33, 44};
int *p = values;
printf("%d ", *p);
p += 2;
printf("%d ", *p);
printf("%d ", *(p - 1));
  • Question 10: Categorize the pointer declarations below and state what can/cannot be modified:
    1. const char *ptr;
    2. char * const ptr;

7. Structures, Unions & Typedef

C allows you to define custom datatypes by grouping variables of different types.

Structures (struct)

Structures represent composite datatypes that group related variables (called member fields) under a single name. Each member field has its own independent address space in memory.

struct Student {
    char name[50];
    int roll_no;
    float gpa;
}; // Semicolon is required at struct definition closure!

Accessing Members

  • Use the dot operator (.) for struct instances.
  • Use the arrow operator (->) when accessing members through a pointer.
typedef struct Student Student;
Student s1 = {"Alice", 101, 3.9};
Student *ptr_s = &s1;

printf("GPA: %.2f\n", s1.gpa);       // Using dot operator
printf("GPA: %.2f\n", ptr_s->gpa);   // Pointer access using arrow operator

Structure Padding & Memory Alignment

The memory footprint of a struct is not always the sum of its member sizes. Compilers insert padding bytes to align members with boundaries (e.g., 4-byte boundaries for integers), optimizing CPU data read speeds.

  • Minimizing Padding: Order members from largest to smallest size to reduce alignment gaps.
  • Disabling Padding: Use #pragma pack(1) to force the compiler to arrange members tightly without padding, which is useful for serializing data over networks.
#include <stdio.h>

struct Unpacked {
    char a;   // 1 byte
    // 3 bytes padding
    int b;    // 4 bytes
    char c;   // 1 byte
    // 3 bytes padding
}; // Size: 12 bytes

#pragma pack(1)
struct Packed {
    char a;   // 1 byte
    int b;    // 4 bytes
    char c;   // 1 byte
}; // Size: 6 bytes
#pragma pack() // Restore default padding

Flexible Array Members (C99)

A struct can contain an unsized array as its last member. This is useful for declaring dynamic payload structures:

struct Packet {
    int length;
    char payload[]; // Flexible Array Member
};
// Allocate memory for struct + payload buffer
struct Packet *p = malloc(sizeof(struct Packet) + 100 * sizeof(char));

Bit Fields

Bit fields allow specifying the exact number of bits allocated to variables, which is useful for memory-efficient flags or hardware interfaces:

struct Flags {
    unsigned int is_visible : 1; // Occupies 1 bit
    unsigned int color_code : 3; // Occupies 3 bits (0-7 range)
};

Unions (union)

Unions are similar to structs but allocate only enough memory to hold their single largest member. All member variables share the same memory location, meaning only one member field can contain a value at any given time.

union Data {
    int i;
    float f;
    char c;
}; // Allocates 4 bytes (size of float/int). Struct would allocate 9+ bytes.

Type Aliasing (typedef)

typedef creates aliases for complex type names, simplifying code declarations.

typedef struct Student Student; // Now we can type "Student" instead of "struct Student"
Student student_1;

🌍 Real-World Analogy

  • Structs: A struct is like a patient medical record form: it has designated spots for different datatypes (name, age, height) all bundled into one physical file.
  • Unions: A union is like a shared hotel conference room: it can be styled for a wedding, a lecture, or a concert — but only one event can occupy the room at any given time.
  • Bit Fields: Bit fields are like checkboxes on a form: instead of wasting a whole line of paper for a single "yes/no" question, you pack multiple checkboxes into a single line to save space.

💼 Industry Application: Network communication protocols and disk controllers define structures with #pragma pack to match exact binary headers for network frames (e.g., TCP/IP packets) without padding.

Practice Questions

  • Question 11: Describe what happens to union member values when you execute this sequence: 
    union Data data;
data.i = 10;
data.f = 220.5;
    What will be the value of data.i?
  • Question 12: Assuming standard 4-byte integers and 1-byte characters, what is the size of the following struct, and how can its ordering be optimized to reduce memory padding? 
    struct Record {
    char a;
    int b;
    char c;
    double d;
};

8. Dynamic Memory Allocation (DMA)

Dynamic Memory Allocation lets you request memory from the Heap at runtime when variable sizes are unknown before execution. You must import <stdlib.h> to use DMA functions.

Core DMA Functions

  1. malloc(size_t size): Allocates size bytes of uninitialized heap memory. Returns a void pointer (void*) to the base address. Returns NULL if allocation fails.
  2. calloc(size_t num, size_t size): Allocates memory for an array of num elements of size bytes. Initializes all allocated bytes to 0.
  3. realloc(void *ptr, size_t new_size): Resizes an existing heap allocation. It expands or contracts the memory block in place, or moves it to a new location if necessary.
  4. free(void *ptr): Returns dynamic heap memory back to the operating system.
#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 5;
    // Allocating array of 5 integers dynamically
    int *arr = (int*)malloc(n * sizeof(int));

    if (arr == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }

    // Populate array
    for (int i = 0; i < n; i++) {
        arr[i] = i * 10;
    }

    // Free heap memory when finished
    free(arr);
    arr = NULL; // Prevent dangling pointer behavior
    return 0;
}

realloc Edge Cases & Safe Handling

When calling realloc(ptr, new_size), if allocation fails, the function returns NULL but the original memory block remains valid and allocated. Assigning the result directly back to the original pointer creates an instant memory leak:

// DANGEROUS METHOD: If realloc fails, 'arr' becomes NULL, leaking the original block!
arr = realloc(arr, new_size);

// SAFE METHOD: Use a temporary pointer
int *temp = realloc(arr, new_size);
if (temp != NULL) {
    arr = temp;
} else {
    // Handle error; 'arr' is still allocated and must be freed eventually
}
  • Note: realloc(NULL, size) behaves exactly like malloc(size). realloc(ptr, 0) behaves like free(ptr) (returns NULL).

Dynamic 2D Arrays

To create a dynamic 2D array, allocate an array of pointers (rows) and then allocate columns for each row pointer:

int rows = 3, cols = 4;
int **arr = (int**)malloc(rows * sizeof(int*));
for (int i = 0; i < rows; i++) {
    arr[i] = (int*)malloc(cols * sizeof(int));
}

// Access: arr[r][c]

// Freeing sequence: Free sub-arrays first, then the row array!
for (int i = 0; i < rows; i++) {
    free(arr[i]);
}
free(arr);

Memory Debugging (Valgrind)

Valgrind is a runtime analysis tool that monitors memory allocation behaviors to detect:

  • Memory Leaks: Allocations that were never released using free().
  • Invalid Reads/Writes: Accessing arrays out-of-bounds or using pointers to freed zones.
  • Uninitialized value usage: Performing computations using uninitialized memory values.
# Compilation and Valgrind run command
gcc -Wall -g main.c -o app.exe
valgrind --leak-check=full ./app.exe

Warning

Memory Leaks Memory allocated on the Heap remains allocated until it is explicitly released via free(). If a program continually allocates memory without freeing it, it will eventually exhaust all available system RAM, resulting in a crash. This is known as a Memory Leak.

🌍 Real-World Analogy

  • malloc: Renting dynamic memory is like booking a hotel room: you ask the desk for a room of a certain size.
  • free: This is like checking out: you hand back the key card so the hotel can clean the room and let someone else rent it.
  • realloc: This is like asking for a room upgrade: if the room next door is empty, they expand your room; if not, they move you to a new suite and transfer your bags automatically.
  • Memory Leak: This is like forgetting to check out of your hotel room: the room remains locked and empty, but the hotel cannot rent it out, eventually running out of rooms.

💼 Industry Application: Dynamic databases (like SQLite) allocate variable-sized page blocks on the heap at runtime using memory allocation to store incoming database rows dynamically.

Practice Questions

  • Question 13: Explain the differences between malloc() and calloc() regarding parameters and memory initialization.
  • Question 14: Write a safe C function to resize a dynamic integer array pointer and handle potential failures without creating memory leaks.

9. DSA 1: Linked Lists (Singly & Doubly Linked Lists)

A Linked List is a linear data structure consisting of dynamic Nodes connected by pointers. Unlike arrays, nodes are not stored contiguously in memory, meaning elements must be traversed sequentially ($O(n)$ search access).

Singly Linked Lists (SLL)

Each node points to the next node in the sequence. The last node points to NULL.

Head -> [Data | Next] -> [Data | Next] -> [Data | NULL]

typedef struct Node {
    int data;
    struct Node *next; // Self-referential pointer
} Node;

Insertion & Traversal Functions

To modify a list's head pointer inside a function, we must pass a double pointer (Node **head_ref) to edit the pointer value within the caller's scope:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Traversal Function
void print_list(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Insertion at Head (Modifies original head pointer)
void insert_at_head(Node **head_ref, int new_data) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = *head_ref; // Point to old head
    *head_ref = new_node;       // Dereference and update head pointer
}

Reversal Algorithm (Iterative)

To reverse a singly linked list in $O(n)$ time and $O(1)$ space, adjust node pointers using three trackers: prev, current, and next:

void reverse_list(Node **head_ref) {
    Node *prev = NULL;
    Node *current = *head_ref;
    Node *next = NULL;
    while (current != NULL) {
        next = current->next;    // Save next node link
        current->next = prev;    // Reverse current node's link
        prev = current;          // Move prev step forward
        current = next;          // Move current step forward
    }
    *head_ref = prev; // Update head pointer to new list root
}

Doubly Linked Lists (DLL)

Each node stores pointers to both the next and the previous node, allowing bidirectional traversal at the expense of extra memory overhead:

NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL

typedef struct DLLNode {
    int data;
    struct DLLNode *prev;
    struct DLLNode *next;
} DLLNode;

Circular Linked Lists

In a circular list, the last node's next pointer points back to the head node rather than NULL. Useful for round-robin scheduling algorithms.

Important

List Cleanup Operations When deleting a linked list, you cannot simply free the head node. If you do, you lose the references to all subsequent nodes in the list, creating a massive memory leak. You must traverse the list, saving the pointer to the next node before freeing the current node.

🌍 Real-World Analogy

  • Singly Linked List: A linked list is like a treasure hunt: each location contains a clue (pointer) leading to the next location.
  • Doubly Linked List: A doubly linked list is like a two-way train: passengers can walk forwards or backwards between connected carriages.
  • Circular Linked List: A circular list is like a merry-go-round where the last horse sits right behind the first one.

💼 Industry Application: Operating systems use linked lists to schedule running threads and manage free memory blocks in list structures.

Practice Questions

  • Question 15: Write a function void delete_node(Node **head_ref, int key) that deletes the first node containing the value key from a singly linked list.
  • Question 16: Write a function void reverse_list(Node **head_ref) that reverses a singly linked list in-place using an iterative three-pointer algorithm.

10. DSA 2: Stacks & Queues

Stack (LIFO: Last-In, First-Out)

A Stack limits insertion and deletion operations to one end (called the Top). Think of it like a stack of plates.

  • push: Insert an item onto the stack.
  • pop: Remove and return the top item.
  • peek: Return the top item without removing it.

Real-World Use Cases

  • Recursion management (Call Stack).
  • Syntax evaluation (balanced bracket checks).
  • Undo/Redo buffers.

Stack Implementations: Array vs. Linked List

  • Array Stack: Fixed maximum capacity, fast $O(1)$ operations, risk of Stack Overflow.
  • Linked List Stack: Dynamic capacity, no stack overflow limits, but requires extra pointer overhead ($O(1)$ operations at the head of the list).
// Linked-List Stack Implementation
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

void push(StackNode **top, int val) {
    StackNode *new_node = malloc(sizeof(StackNode));
    new_node->data = val;
    new_node->next = *top;
    *top = new_node;
}

int pop(StackNode **top) {
    if (*top == NULL) return -1; // Stack Underflow
    StackNode *temp = *top;
    int popped = temp->data;
    *top = (*top)->next;
    free(temp);
    return popped;
}

Queue (FIFO: First-In, First-Out)

A Queue inserts new items at one end (the Rear) and removes items from the opposite end (the Front). Think of it like a line at a store.

  • enqueue: Insert an item at the Rear.
  • dequeue: Remove and return the item at the Front.

Real-World Use Cases

  • CPU task scheduling (FCFS).
  • Buffering data streams (Printer queues, network routers).
  • Breadth-First Search (BFS) graph traversals.

Circular Queues

Queue operations implemented using standard arrays can leave unused space at the beginning of the array as elements are dequeued. To prevent this, Circular Queues wrap indexes back to the start using the modulo operator %:

#define SIZE 5
typedef struct {
    int arr[SIZE];
    int front, rear;
} CircularQueue;

void init_queue(CircularQueue *q) {
    q->front = q->rear = -1;
}

int is_full(CircularQueue *q) {
    return (q->front == (q->rear + 1) % SIZE);
}

int is_empty(CircularQueue *q) {
    return (q->front == -1);
}

void enqueue(CircularQueue *q, int val) {
    if (is_full(q)) {
        printf("Queue Full\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % SIZE;
    q->arr[q->rear] = val;
}

🌍 Real-World Analogy

  • Stack (LIFO): A stack is like a stack of cafeteria trays: you can only place a tray on the top (push), and you must take the top tray off first (pop).
  • Queue (FIFO): A queue is like a line at a ticket counter: the first person to stand in line is the first one served.
  • Circular Queue: This is like a revolving door at a hotel entrance: people enter and exit in a continuous loop without running out of doorway space.

💼 Industry Application: Web browser navigation history uses a stack (clicking back pops the last page). Network routers use queues (packet buffers) to process incoming packets in order of arrival.

Practice Questions

  • Question 17: Write out structural pseudocode or a C implementation for an array-based stack containing helper check methods: is_full() and is_empty().

11. DSA 3: Trees (Binary Search Trees & Self-Balancing Trees)

A Tree is a non-linear, hierarchical data structure. A Binary Search Tree (BST) enforces a structural ordering rule:

  • The left subtree of a node contains only values less than the node's value.
  • The right subtree of a node contains only values greater than the node's value.
        50 (Root)
       /  \
     30    70
    /  \
   20  40

Node Representation & Insertion

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Recursive BST Insertion
TreeNode* insert(TreeNode *root, int val) {
    if (root == NULL) {
        TreeNode *new_node = (TreeNode*)malloc(sizeof(TreeNode));
        new_node->data = val;
        new_node->left = new_node->right = NULL;
        return new_node;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    }
    return root;
}

Tree Traversals (Depth-First Search)

There are three standard depth-first methods to traverse a tree recursively:

  1. Pre-Order: Visit Root $\rightarrow$ Left Subtree $\rightarrow$ Right Subtree.
  2. In-Order: Visit Left Subtree $\rightarrow$ Root $\rightarrow$ Right Subtree.
  3. Post-Order: Visit Left Subtree $\rightarrow$ Right Subtree $\rightarrow$ Root.
void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

Important

In-Order Traversal Sorting Property An In-Order traversal of a Binary Search Tree (BST) will visit nodes in sorted, ascending order.

BST Deletion Algorithm

Deleting a node from a BST requires handling three scenarios:

  1. Node is a Leaf: Delete the node and set its parent pointer to NULL.
  2. Node has One Child: Copy the child to the node, then delete the child.
  3. Node has Two Children: Find the In-Order Successor (smallest value in the right subtree), copy its value to the node, and delete the In-Order Successor.
TreeNode* find_min(TreeNode *root) {
    while (root->left != NULL) root = root->left;
    return root;
}

TreeNode* delete_node(TreeNode* root, int key) {
    if (root == NULL) return root;
    
    if (key < root->data) {
        root->left = delete_node(root->left, key);
    } else if (key > root->data) {
        root->right = delete_node(root->right, key);
    } else { // Found the node
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        // Node with two children
        TreeNode* temp = find_min(root->right);
        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }
    return root;
}

Tree Height Calculation

The height of a tree is the length of the longest path from the root to a leaf node:

int get_height(TreeNode *root) {
    if (root == NULL) return -1; // Height of empty tree is -1
    int left_h = get_height(root->left);
    int right_h = get_height(root->right);
    return (left_h > right_h ? left_h : right_h) + 1;
}

Self-Balancing Trees (AVL Trees)

Standard BSTs can skew into linear lists ($O(n)$ search time) if values are inserted in sorted order. AVL Trees solve this by enforcing a balance constraint: the height difference between the left and right subtrees (the Balance Factor) of any node must be at most 1.

  • Rotations: AVL trees perform single (L, R) or double (LR, RL) rotations to rebalance themselves during insertions and deletions, guaranteeing $O(\log n)$ search, insertion, and deletion times.

🌍 Real-World Analogy

  • Binary Search Tree (BST): A BST is like looking up a word in a physical dictionary: you open it in the middle, and if your word is alphabetically smaller, you look left; if larger, you look right.
  • AVL Tree: An AVL tree is like a self-balancing bookshelf: if one side gets too heavy with books, the shelf performs a quick rotation to distribute the weight evenly, preventing it from tipping over.

💼 Industry Application: Database indexing structures (B-trees, AVL trees) are used in SQL databases (like MySQL and PostgreSQL) to perform query searches in $O(\log n)$ time.

Practice Questions

  • Question 18: Write recursive traversal functions for both preorder() and postorder() methods.

12. Algorithms: Sorting & Searching

Algorithms define step-by-step instructions for solving problems.

Sorting Algorithms

  • Bubble Sort: Iteratively compares adjacent elements and swaps them if they are in the wrong order.
    • Time Complexity: $O(n^2)$ Average/Worst. Space: $O(1)$.
  • Selection Sort: Divides the array into sorted and unsorted regions, repeatedly finding the minimum element in the unsorted region and swapping it with the first unsorted element.
    • Time Complexity: $O(n^2)$ Average/Worst. Space: $O(1)$. Unstable.
  • Insertion Sort: Iteratively inserts elements from the unsorted region into their correct sorted position.
    • Time Complexity: $O(n^2)$ Average/Worst, $O(n)$ Best (sorted list). Space: $O(1)$. Stable.
  • Merge Sort: A divide-and-conquer algorithm. It divides the array in half, recursively sorts both halves, and merges the sorted halves.
    • Time Complexity: $O(n \log n)$ all cases. Space: $O(n)$ (requires auxiliary merge array). Stable.
  • Quick Sort: A divide-and-conquer algorithm. It selects a pivot element, partitions the array around the pivot, and recursively sorts the sub-arrays.
    • Time Complexity: $O(n \log n)$ Average, $O(n^2)$ Worst-case (when pivot selection is poor). Space: $O(\log n)$ call stack space. Unstable.
// Selection Sort Implementation
void selection_sort(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;
    }
}

Searching Algorithms

  • Linear Search: Scans elements one by one from beginning to end.
    • Time Complexity: $O(n)$. Space: $O(1)$.
  • Binary Search: A divide-and-conquer algorithm that repeatedly divides a sorted search range in half.
    • Time Complexity: $O(\log n)$. Space: $O(1)$.

Important

Binary Search Prerequisite Binary Search requires that the target array be sorted. If the array is unsorted, Binary Search will fail to locate elements correctly.

// Binary Search Implementation
int binary_search(int arr[], int size, int target) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // Prevents overflow: (low+high)/2 can overflow int
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // Target not found
}

Sorting Algorithm Complexity & Stability

An algorithm is stable if it preserves the relative order of equal elements.

Algorithm Best Time Average Time Worst Time Space Complexity Stability
Bubble Sort $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ Stable
Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ Unstable
Insertion Sort $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ Stable
Merge Sort $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ Stable
Quick Sort $O(n \log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$ Unstable

🌍 Real-World Analogy

  • Bubble Sort: This is like sorting playing cards by repeatedly comparing adjacent cards and swapping them until the largest cards float to the end like bubbles.
  • Binary Search: This is like playing the higher/lower guessing game: with every guess, you divide the search space in half.
  • Sorting Stability: Stability is like maintaining alphabetical order among students who have the same grade score: stable sorting keeps their original relative order.

💼 Industry Application: Database query engines use Merge Sort to sort index keys stably, and Quick Sort to sort datasets in memory quickly when stability is not required.

Practice Questions

  • Question 19: Why is low + (high - low) / 2 preferred over (low + high) / 2 when calculating the middle index in Binary Search?
  • Question 20: Fill in the complexity table comparing Bubble, Selection, Insertion, Merge, and Quick Sort regarding time complexities (Best, Avg, Worst), Space complexities, and Stability.

13. Answer Key & Explanations

Section 1: Introduction to C & The Compilation Process

  • Answer 1:
    • Preprocessing: Input: program.c. Output: Preprocessed source file (program.i). (Directives resolved, macros expanded).
    • Compilation: Input: program.i. Output: Assembly instructions (program.s). (C code converted to assembly code).
    • Assembly: Input: program.s. Output: Machine-code Object file (program.o or .obj). (Assembly converted to raw binary instructions).
    • Linking: Input: program.o and system libraries. Output: Executable file (program.exe or a.out). (References resolved, libraries merged).
  • Answer 2:
    • A Makefile is a file containing commands and rules that the make utility executes to automate compiler building, compiling only modified files.
    • Simple Makefile: 
      CC = gcc
CFLAGS = -Wall -g

app.exe: main.o helper.o
	$(CC) $(CFLAGS) -o app.exe main.o helper.o

main.o: main.c
	$(CC) $(CFLAGS) -c main.c

helper.o: helper.c
	$(CC) $(CFLAGS) -c helper.c

clean:
	rm -f *.o app.exe

Section 2: Variables, Core Data Types & Memory Sizes

  • Answer 3:
    • Both occupy 1 byte (8 bits) of memory, offering $2^8 = 256$ state combinations.
    • A signed char reserves 1 bit for the sign, yielding values from -128 to 127.
    • An unsigned char uses all 8 bits for the magnitude, yielding values from 0 to 255.
  • Answer 4:
    • The volatile qualifier tells the compiler that the value of the variable can be modified at any time outside the program's control.
    • This prevents the compiler from optimizing variable accesses by caching the value in a CPU register, forcing the CPU to fetch it directly from physical RAM every time. It is vital for hardware I/O programming (registers mapped to RAM addresses) where the value can change due to hardware activities.

Section 3: Operators & Control Flow

  • Answer 5:
    • Output: x=6, y=5
    • Explanation: Postfix increment (x++) assigns the current value of x to y first, and then increments x. Therefore, y receives the initial value 5, and x is incremented to 6 immediately afterward.

Section 4: Functions, Scopes & Parameter Passing

  • Answer 6:
    • Output: 1 2 3
    • Explanation: Because count is declared as static, it is stored in the static Data segment instead of the stack. Its state is preserved across function calls, incrementing by 1 on each execution.
  • Answer 7:
    • Declaration: double (*op)(double, double);
    • Call using the pointer (assuming op points to a function named multiply): 
      double result = op(5.5, 2.0); // or (*op)(5.5, 2.0)

Section 5: Arrays & String Manipulation

  • Answer 8:
    • Byte size of word is 11 bytes.
    • strlen("C Language") returns 10 because it counts only the visible letters.
    • sizeof(word) returns 11 because it includes the hidden null-terminator character '\0' that terminates the string in memory.

Section 6: Pointers: Memory Addresses & Pointer Arithmetic

  • Answer 9:
    • Output: 11 33 22
    • Explanation:
      1. *p starts at index 0: 11.
      2. p += 2 shifts the pointer forward by two integer steps to index 2: 33.
      3. *(p - 1) dereferences the element immediately preceding the current pointer location (index 1): 22.
  • Answer 10:
    1. const char *ptr;: Pointer to a constant character. The character value pointed to cannot be modified (read-only), but the pointer address itself can be reassigned to point elsewhere.
    2. char * const ptr;: Constant pointer to a character. The character value can be modified, but the pointer address is fixed and cannot be changed.

Section 7: Structures, Unions & Typedef

  • Answer 11:
    • Output: data.i will print a corrupted garbage value.
    • Explanation: In a union, all member variables share the same memory location. Setting data.f = 220.5 overwrites the bytes previously allocated to data.i, corrupting the integer value.
  • Answer 12:
    • The size of the struct is 24 bytes. Due to member alignment boundaries:
      • char a (1 byte) + 3 bytes padding (to align int b on a 4-byte boundary)
      • int b (4 bytes)
      • char c (1 byte) + 7 bytes padding (to align double d on an 8-byte boundary)
      • double d (8 bytes)
      • Total: 1 + 3 + 4 + 1 + 7 + 8 = 24 bytes.
    • Optimization: Reorder members from largest to smallest to eliminate padding: 
      struct Record {
    double d; // 8 bytes
    int b;    // 4 bytes
    char a;   // 1 byte
    char c;   // 1 byte
    // 2 bytes padding at the end to align structure size to 8 bytes
}; // Total: 16 bytes

Section 8: Dynamic Memory Allocation (DMA)

  • Answer 13:
    • malloc(size_t size) takes a single parameter (the total bytes to allocate). It leaves the allocated memory unit initialized with garbage data.
    • calloc(size_t num, size_t size) takes two parameters (element count and element byte size). It automatically initializes all allocated bytes to zero.
  • Answer 14:
    • Safe realloc handling: 
      int* safe_resize(int *arr, int new_size) {
    int *temp = (int*)realloc(arr, new_size * sizeof(int));
    if (temp == NULL) {
        // Reallocation failed, original arr is still intact
        printf("Resize failed!\n");
        return arr;
    }
    return temp; // Return resized pointer
}

Section 9: DSA 1: Linked Lists (Singly Linked Lists)

  • Answer 15: 
    void delete_node(Node **head_ref, int key) {
    Node *temp = *head_ref, *prev = NULL;
    
    // If head node itself holds the key
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // Changed head
        free(temp);            // free old head
        return;
    }
    
    // Search for the key to be deleted
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    // If key was not present in linked list
    if (temp == NULL) return;
    
    // Unlink the node from linked list
    prev->next = temp->next;
    free(temp); // Free memory
}
  • Answer 16: 
    void reverse_list(Node **head_ref) {
    Node *prev = NULL;
    Node *current = *head_ref;
    Node *next = NULL;
    while (current != NULL) {
        next = current->next;    // Store next node link
        current->next = prev;    // Reverse current node pointer link
        prev = current;          // Move prev step forward
        current = next;          // Move current step forward
    }
    *head_ref = prev; // Update head reference pointer to new root
}

Section 10: DSA 2: Stacks & Queues

  • Answer 17: 
    #include <stdio.h>
#include <stdbool.h>
#define MAX 5

typedef struct {
    int arr[MAX];
    int top;
} Stack;

void init(Stack *s) { s->top = -1; }
bool is_full(Stack *s) { return s->top == MAX - 1; }
bool is_empty(Stack *s) { return s->top == -1; }

void push(Stack *s, int val) {
    if (is_full(s)) {
        printf("Stack Overflow\n");
        return;
    }
    s->arr[++(s->top)] = val;
}

int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

Section 11: DSA 3: Trees (Binary Search Trees)

  • Answer 18: 
    // Pre-Order: Root -> Left -> Right
void preorder(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Post-Order: Left -> Right -> Root
void postorder(TreeNode *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

Section 12: Algorithms: Sorting & Searching

  • Answer 19:
    • In systems with memory constraints, if variables low and high contain large integer values near the datatype limit, calculating (low + high) can exceed the maximum capacity of a signed integer, causing integer overflow.
    • Calculating mid-point index as low + (high - low) / 2 mathematically achieves the identical value without ever exceeding the bound threshold of high, preventing overflow errors.
  • Answer 20:
    • The completed sorting algorithm table is:
      • Bubble Sort: Best $O(n)$, Avg $O(n^2)$, Worst $O(n^2)$, Space $O(1)$, Stable.
      • Selection Sort: Best $O(n^2)$, Avg $O(n^2)$, Worst $O(n^2)$, Space $O(1)$, Unstable.
      • Insertion Sort: Best $O(n)$, Avg $O(n^2)$, Worst $O(n^2)$, Space $O(1)$, Stable.
      • Merge Sort: Best $O(n \log n)$, Avg $O(n \log n)$, Worst $O(n \log n)$, Space $O(n)$, Stable.
      • Quick Sort: Best $O(n \log n)$, Avg $O(n \log n)$, Worst $O(n^2)$, Space $O(\log n)$, Unstable.

Made by NotAryanSinha

(Created with care for your programming journey!)