Table of Contents

DATA STRUCTURES USING C

When working with data structures in C, the fundamental notions are generally similar to Python or other languages, but the implementation necessitates a more in-depth grasp of pointers, memory management, and low-level operations. The following is an overview of some essential C data structures, as well as examples of how to implement them.

C Programming: The primary language used for implementing these data structures.
Data Structures: Refers to foundational data structures implemented in C.
Arrays: An array implementation and example code.
Linked List: A simple singly linked list with insertion and traversal.
Stack: Stack implementation using arrays, with push and pop operations.
Queue: A circular queue implementation using arrays, with enqueue and dequeue functions.
Binary Tree: Basic binary tree structure with node creation and inorder traversal.
Pointers: Usage of pointers for linked lists and dynamic memory allocation.
Memory Management: Use of malloc and free for dynamic memory allocation in linked lists and trees.
Algorithms: Basic traversal algorithms for linked lists, stacks, queues, and binary trees.
Dynamic Memory Allocation: For linked lists and binary trees in C.
Circular Queue: A specific queue implementation that wraps around in memory.
Node Structure: Struct-based node definitions for linked lists and trees.
Inorder Traversal: Specific tree traversal method shown in the binary tree example.
LIFO: Stack’s Last In, First Out property.
FIFO: Queue’s First In, First Out property.

#include <stdio.h> int main() { printf("Hello World!"); return 0; }

Result:

Hello World!

1. Arrays.

An array is a collection of things stored in contiguous memory regions.

#include <stdio.h>

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

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArray(arr, size);
    return 0;
}

2. Linked List.

A linked list is a linear data structure in which elements are stored in nodes that contain pointers to the following node in the list.

Each of these examples demonstrates a basic implementation of several data structures in C. To improve them, try adding features such as dynamic memory allocation, better error handling, and more complex traversal or sorting techniques. Please let me know if you require any extra information or support with other C data structures!

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

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

// Function to add a node at the beginning
void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    printList(head);
    return 0;
}

3. Stack.

A stack is a Last In, First Out (LIFO) data structure. It can be implemented using arrays or linked lists. This is an array-based implementation.

#include <stdio.h>
#define MAX 100

struct Stack {
    int items[MAX];
    int top;
};

void initializeStack(struct Stack* stack) {
    stack->top = -1;
}

int isFull(struct Stack* stack) {
    return stack->top == MAX - 1;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, int value) {
    if (isFull(stack))
        printf("Stack overflow\n");
    else
        stack->items[++stack->top] = value;
}

int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->items[stack->top--];
}

int main() {
    struct Stack stack;
    initializeStack(&stack);
    push(&stack, 10);
    push(&stack, 20);
    printf("Popped: %d\n", pop(&stack));
    return 0;
}

4. Queue.

A queue is a First In, First Out (FIFO) data structure. Here’s an array-based circular queue implementation.

#include <stdio.h>
#define SIZE 5

struct Queue {
    int items[SIZE];
    int front, rear;
};

void initializeQueue(struct Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(struct Queue* q) {
    return (q->front == 0 && q->rear == SIZE - 1) || (q->rear == (q->front - 1) % (SIZE - 1));
}

int isEmpty(struct Queue* q) {
    return q->front == -1;
}

void enqueue(struct Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
    } else {
        if (q->front == -1) q->front = 0;
        q->rear = (q->rear + 1) % SIZE;
        q->items[q->rear] = value;
    }
}

int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % SIZE;
    }
    return item;
}

int main() {
    struct Queue q;
    initializeQueue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    printf("Dequeued: %d\n", dequeue(&q));
    return 0;
}

5. Binary Tree.

A binary tree is a hierarchical structure with a maximum of two children per node.

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Inorder traversal
void inorder(struct Node* node) {
    if (node == NULL)
        return;
    inorder(node->left);
    printf("%d ", node->data);
    inorder(node->right);
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    inorder(root);
    return 0;
}