Data Structures in C

Hello there! Are you ready to dive into the world of data structures in C? Well, you’re in the right place! This tutorial will guide you through the essentials of data structures, providing practical examples and step-by-step instructions. So, let’s get started!

Introduction to Data Structures

Data structures are the building blocks of programming. They allow us to store, access, and organize data efficiently in computer memory. In C, we have a variety of data structures at our disposal, including arrays, linked lists, stacks, queues, and binary trees.

Arrays in C

Arrays are the most basic data structure in C. They store fixed-size sequential collections of elements of the same type. An array is used to store a collection of data, but it’s better to think of it as a collection of variables of the same type.

int array[10];

In the above code, we declare an array of integers. The size of the array is 10, which means it can hold 10 integers. The index of the array starts from 0, so the array[0] is the first element, array[1] is the second element, and so on.

Code Example

#include <stdio.h>

int main() {
    int numbers[5] = {1, 2, 3, 4, 5};
    int i;
    for(i = 0; i < 5; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

Code Explanation

In this code, we first define an array numbers of size 5 and initialize it with the values 1 through 5. We then use a for loop to iterate over the array and print each element. The printf function is used to print the elements of the array.

Linked Lists in C

A linked list is a linear data structure where each element is a separate object. Each element (we call it a node) of a list consists of two items – the data and a reference to the next node.

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

In the above code, we define a new data type struct Node that contains an integer and a pointer to the next node.

Code Example

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

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

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

int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;
  
    head = (struct Node*)malloc(sizeof(struct Node)); 
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));
  
    head->data = 1;
    head->next = second;
  
    second->data = 2;
    second->next = third;
  
    third->data = 3;
    third->next = NULL;
  
    printList(head);
  
    return 0;
}

Code Explanation

In this code, we first define a Node structure which has an integer data and a pointer next to the next node. We then define a function printList which prints the elements of the linked list. In the main function, we create three nodes head, second, and third and link them together to form a linked list. We then call the printList function to print the elements of the linked list.

Stacks in C

A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). There are two main functions in the stack: Push and Pop.

struct Stack {
  int top;
  unsigned capacity;
  int* array;
};

In the above code, we define a new data type struct Stack that contains an integer top, an unsigned integer capacity, and a pointer to an integer array.

Code Example

#include <stdio.h>
#define MAX 1000

int top;
int stack[MAX];

void push(int data) {
    if (top >= (MAX - 1)) {
        printf("Stack Overflow");
    }
    else {
        stack[++top] = data;
        printf("%d pushed to stack\n", data);
    }
}

int pop() {
    if (top < 0) {
        printf("Stack Underflow");
        return 0;
    }
    else {
        int data = stack[top--];
        return data;
    }
}

int main() {
    top = -1;
    push(10);
    push(20);
    push(30);
  
    printf("%d popped from stack\n", pop());
  
    return 0;
}

Code Explanation

In this code, we first define a stack array and a top variable to keep track of the top of the stack. We then define two functions push and pop to add and remove elements from the stack. In the main function, we initialize top to -1 and then push the numbers 10, 20, and 30 onto the stack. We then pop an element from the stack and print it.

Queues in C

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

struct Queue {
  int front, rear, size;
  unsigned capacity;
  int* array;
};

In the above code, we define a new data type struct Queue that contains two integers front and rear, an unsigned integer capacity, an integer size, and a pointer to an integer array.

Code Example

#include <stdio.h>
#define MAX 1000

int front = -1, rear = -1;
int queue[MAX];

void enqueue(int data) {
    if (rear == MAX - 1)
        printf("Queue Overflow \n");
    else{
        if (front == -1)
            front = 0;
        rear++;
        queue[rear] = data;
    }
}

void dequeue() {
    if (front == -1 || front > rear)
        printf("Queue Underflow \n");
    else {
        printf("Element deleted from queue is : %d\n", queue[front]);
        front++;
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
  
    dequeue();
  
    return 0;
}

Code Explanation

In this code, we first define a queue array and two variables front and rear to keep track of the front and rear of the queue. We then define two functions enqueue and dequeue to add and remove elements from the queue. In the main function, we enqueue the numbers 10, 20, and 30 onto the queue. We then dequeue an element from the queue and print it.

Binary Trees in C

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

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

In the above code, we define a new data type struct Node that contains an integer and two pointers to the left and right child nodes.

Code Example

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

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

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
  
    return(node);
}

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

int main() {
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
  
    printf("Postorder traversal of binary tree is \n");
    printPostorder(root);
  
    return 0;
}

Code Explanation

In this code, we first define a Node structure which has an integer data and two pointers left and right to the left and right child nodes. We then define a function newNode to create a new node, and a function printPostorder to print the elements of the binary tree in postorder. In the main function, we create a binary tree and then print its elements in postorder.

Wrapping Up

By now, you should have a good understanding of the basic data structures in C. Remember, the key to mastering data structures (and programming in general) is practice. So, don’t forget to write code and solve problems using these data structures!

Frequently Asked Questions (FAQ)

Related Tutorials

1. Trees in C
2. Advanced Data Structures: Binary Trees in C
3. Advanced Data Structures: Segment Trees in C
4. Advanced Data Structures: graphs in C
5. Advanced Data Structures: Heaps in C

That’s all for now, folks! Remember, the journey of a thousand miles begins with a single step. So, keep coding, keep learning, and most importantly, have fun!