C Programming Concepts: Arrays, Functions, Structures, and Stacks

1. Arrays: Definition, Types, and Implementation

An array is a collection of elements of the same data type stored in contiguous memory locations. It is used to store multiple values in a single variable and can be accessed using index numbers. The indexing in an array starts from 0. Arrays help manage and process data efficiently, especially when dealing with large volumes of similar data.

Types of Arrays Based on Dimensions

• One-Dimensional Array: It stores data in a linear list format.
• Multi-Dimensional Array: It stores data in matrix form (like 2D, 3D arrays), which is useful in applications like image processing and tables.

Types of Arrays Based on Memory Allocation

1. Static Array:

   The size of the array is fixed at compile-time. Memory is allocated when the program starts. For example: int a[10];

2. Dynamic Array:

   The size of the array is decided at runtime using pointers and functions like malloc() or calloc(). This allows flexible memory use. Example:

   int *arr;
   arr = (int*)malloc(n * sizeof(int));

C Program Example: Sum of Static Array Elements

Here is a program to input ‘n’ numbers in a static array and display their sum:

#include <stdio.h>

int main() {
    int n, i, sum = 0;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int arr[n]; // Static array
    printf ("Enter %d numbers:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
    printf("Sum of elements = %d", sum);
    return 0;
}

If dynamic memory is required, we can use the malloc() function from <stdlib.h> instead of a static array.

2. Functions: Call by Value vs. Call by Reference

Understanding Functions in C

A function is a block of code in C that performs a specific task. It helps in breaking down a large program into smaller, manageable parts. Using functions avoids code repetition, improves readability, and makes debugging easier. Functions can be either built-in (like printf, scanf) or user-defined.

Syntax of Function Definition:

return_type function_name(parameter_list) {
    // body of function
}

Example:

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

Call by Value Mechanism

In Call by Value, a copy of the actual value is passed to the function. Any change made inside the function does not affect the original variable.

Example:

void change(int x) {
    x = x + 10;
}

int main() {
    int a = 5;
    change(a);
    printf("%d", a); // Output will be 5, original 'a' is not changed
}

Call by Reference Mechanism

In Call by Reference, the address of the variable is passed. Therefore, any changes made inside the function directly affect the original variable.

Example:

void change(int *x) {
    *x = *x + 10;
}

int main() {
    int a = 5;
    change(&a);
    printf("%d", a); // Output will be 15, because value at address is changed
}

The main difference is that call by value works on copies (safe but doesn't affect the original), while call by reference works on the original data through pointers (risky but efficient when updates are needed).

3. Structures and Array of Structures

Defining a Structure in C

A structure in C is a user-defined data type that allows grouping of variables of different data types under one name. It is used when we want to store related information together but of different types. Structures are very useful in real-life applications like storing student records, employee details, etc.

Syntax of Structure:

struct structure_name {
    data_type member1;
    data_type member2; 
    // Can add more members…
};

Example:

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

Demonstrating Array of Structures

An Array of Structures is used when we want to store data of multiple entities (like multiple students) using the same structure format. It works like an array, but each element is a full structure.

Program to Demonstrate:

#include <stdio.h>

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

int main() {
    int n, i;
    printf("Enter number of students: ");
    scanf("%d", &n);
    struct Student s[n];
    
    // Input loop
    for(i = 0; i < n; i++) {
        printf("\nEnter details for Student %d:\n", i + 1);
        printf("Roll: ");
        scanf("%d", &s[i].roll);
        printf("Name: ");
        scanf("%s", s[i].name);
        printf("Marks: ");
        scanf("%f", &s[i].marks);
    }
    
    // Output loop
    printf("\n--- Student Details ---\n");
    for(i = 0; i < n; i++) {
        printf("Roll: %d, Name: %s, Marks: %.2f\n", s[i].roll, s[i].name, s[i].marks);
    }
    return 0;
}

This program uses an array of structures to store and display details of 'n' students. Each element of the array s[i] holds one student's full information.

4. Recursion vs. Looping Comparison

Recursion is when a function calls itself to solve smaller parts of a problem. It requires a base condition to stop calling itself.

Looping repeats a block of code using for, while, or do-while until a condition becomes false.

Recursion Example (Factorial)

int fact(int n) {
    if(n == 0)
        return 1;
    else
        return n * fact(n - 1);
}

Looping Example (Factorial)

int fact = 1;
for(int i = 1; i <= n; i++) {
    fact *= i;
}

Main Difference: Recursion uses function calls and is useful for problems like trees or backtracking, often leading to cleaner code for complex problems. Looping is generally better for performance and uses less memory (no overhead of function calls).

5. Linked Lists: Types and Structure

A linked list is a linear data structure where each element (called a node) contains two parts: data and a pointer to the next node. Unlike arrays, linked lists do not store data in contiguous memory locations. They allow dynamic memory allocation, making insertion and deletion easier.

Defining a Node

Each node is defined using a self-referential structure like:

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

Different Types of Linked Lists

1. Singly Linked List: Each node points only to the next node. The last node’s pointer is NULL.

   Example: [10|*] → [20|*] → [30|NULL]

2. Doubly Linked List: Each node has two pointers – one to the next node and one to the previous node.

   Example: NULL ← [10|*|*] ↔ [20|*|*] ↔ [30|*|NULL]

3. Circular Linked List: In this list, the last node points back to the first node, forming a circle.

   Example: [10|*] → [20|*] → [30|*] → (back to first node)

4. Circular Doubly Linked List: It’s like a doubly linked list, but the last node points back to the first, and the first node points to the last.

6. Essential Linked List Operations

In a linked list, several operations can be performed to manage the nodes. Each operation handles the list by accessing or modifying the data and next pointers of the nodes.

1. Traversal: Traversal means visiting each node of the linked list from the beginning to the end using a loop. It helps in displaying the data stored in all nodes.

   Example:

   struct Node* temp = head;
   while(temp != NULL) {
       printf("%d ", temp->data);
       temp = temp->next;
   }

2. Insertion: Insertion means adding a new node. It can be done at the beginning, middle, or end. A new node is created, and its pointer is adjusted to link it properly with the list.

   Insert at Beginning Example:

   newNode->next = head;
   head = newNode;

3. Deletion: Deletion removes a node from the list. Like insertion, it can be from the start, middle, or end. After deleting, pointers must be updated to maintain the structure.

   Delete First Node Example:

   struct Node* temp = head;
   head = head->next;
   free(temp);

4. Updation: Updation means changing the data of a node at a specific position. We traverse to that node and simply change the data part.

   Example: temp->data = newValue;

5. Searching: Searching finds whether a value exists in the list. We traverse through each node and compare its data.

   Example:

   while(temp != NULL) {
       if(temp->data == key) {
           // found
       }
       temp = temp->next;
   }

7. Stacks: LIFO Principle and Algorithms

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last element inserted is the first one to be removed. Think of it like a pile of plates – you always remove the top plate first.

A stack can be implemented using arrays or linked lists. It mainly supports two basic operations: push() to insert an element and pop() to remove the top element.

The push() Operation Algorithm

push() is used to insert an element at the top of the stack.

1. Check if the stack is full (top == size - 1).
2. If not full, increment top.
3. Add the new element at stack[top].

Example (Array Implementation):

if(top == size - 1)
    printf("Stack Overflow");
else {
    top++;
    stack[top] = value;
}

The pop() Operation Algorithm

pop() removes the top element from the stack.

1. Check if the stack is empty (top == -1).
2. If not empty, remove and return the element at stack[top].
3. Decrement top.

Example (Array Implementation):

if(top == -1)
    printf("Stack Underflow");
else {
    value = stack[top];
    top--;
}

Stacks are used in expression evaluation, backtracking, recursion, undo operations in editors, and more.