Implementation of Data Structures and Algorithm Applications in C Language

In computer science, data structures and algorithms are fundamental and important concepts. They help us efficiently store, organize, and process data. In this article, we will introduce several common data structures and their implementations in C language, and demonstrate how to use these data structures to solve practical problems through simple examples.

1. Arrays

1.1 Introduction to Arrays

An array is a linear data structure that can store a fixed-size collection of elements of the same type. Each element in the array can be accessed via an index.

1.2 Example of Array Implementation

The following is a simple C program that demonstrates how to define and use an array:

#include <stdio.h>
int main() {
    int arr[5] = {10, 20, 30, 40, 50}; // Define an integer array
    int sum = 0;
    // Traverse the array and calculate the sum
    for (int i = 0; i < 5; i++) {
        sum += arr[i];
    }
    printf("Array Sum: %d\n", sum);
    return 0;
}

Output:

Array Sum: 150

2. Linked Lists

2.1 Introduction to Linked Lists

A linked list is a non-linear data structure consisting of a series of nodes, where each node contains a data part and a pointer to the next node. Linked lists have dynamic sizes and allow for easy insertion and deletion of elements.

2.2 Example of Singly Linked List Implementation

Below is a basic implementation of a singly linked list, including the insertion of new nodes and traversing the list:

#include <stdio.h>
#include <stdlib.h>
// Define linked list node
struct Node {
    int data;
    struct Node* next;
};
// Insert new node at the head of the list
void insert(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data; // Set new node's data
    new_node->next = (*head_ref); // Point new node to current head
    (*head_ref) = new_node; // Update head to new node
}
// Print linked list contents
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
}
int main() {
    struct Node* head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    printf("Linked List: ");
    printList(head);
    return 0;
}

Output:

Linked List: 30 -> 20 -> 10 ->

3. Stacks

3.1 Introduction to Stacks

A stack is a last-in, first-out (LIFO) data structure that allows insertion and deletion operations at one end only. It is commonly used in function call management, expression evaluation, and other scenarios.

3.2 Example of Stack Implementation

The following is a basic implementation of a stack in C, including push and pop operations:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // Define maximum stack capacity
struct Stack {
    int top;
    int items[MAX_SIZE];
};
// Create an empty stack
struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1; // Initialize top index to -1 indicating an empty stack
    return stack;
}
// Check if stack is empty
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}
// Push element onto stack
void push(struct Stack* stack, int item) {
    if(stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++stack->top] = item;
}
// Pop element from stack
int pop(struct Stack* stack) {
    if(isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack->items[stack->top--];
}
int main() {
    struct Stack *stack = createStack();
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    printf("%d popped from the stack\n", pop(stack));
    return(0);
}

Output:

30 popped from the stack.

4. Queues

4.1 Introduction to Queues

A queue is a first-in, first-out (FIFO) data structure that allows insertion from one end and deletion from the other end. It is widely used in task scheduling and other scenarios.

4.2 Example of Queue Implementation

The following is a basic implementation of a queue in C, including enqueue and dequeue operations:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
struct Queue {
    int items[SIZE];
    int front;
    int rear;
};
// Create an empty queue
struct Queue *createQueue() {
    struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}
// Check if queue is empty
int isEmpty(struct Queue *q) {
    return q->front == -1;
}
// Enqueue operation
void enqueue(struct Queue *q, int value) {
    if(q->rear == SIZE - 1) {
        printf("\nQueue is full!");
        return;
    }
    if(isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("\nInserted %d", value);
}
// Dequeue operation
int dequeue(struct Queue *q) {
    if(isEmpty(q)) {
        printf("\nQueue is empty!");
        return -1;
    }
    int item = q->items[q->front];
    if(q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}
void displayQueue(struct Queue *q) {
    for(int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}
int main() {
    struct Queue *q = createQueue();
    for(int i = 0; i < 3; i++) {
        enqueue(q, i + 10);
        displayQueue(q);
    }
    for(int j = 0; j < 3; j++) {
        dequeue(q);
        displayQueue(q);
    }
    return(0);
}

Output:

Inserted 10
Inserted 11
Inserted 12
10
11
12
Inserted 13

5. Conclusion

This article introduced several common data structures and their basic implementations in C language, including arrays, singly linked lists, stacks, and queues. This foundational knowledge is crucial for understanding more complex data processing methods. In practical development, choosing the appropriate data structure based on specific needs can significantly improve program performance and maintainability. I hope this article helps you in learning C language!