Abstract
This article delves into commonly used algorithms and data structures in embedded programming, aiming to provide a comprehensive reference for embedded developers. By detailing various algorithms and data structures such as sorting algorithms, search algorithms, linked lists, stacks, and queues, along with C language code examples, it demonstrates their practical applications in embedded systems. Additionally, it analyzes the advantages and disadvantages of different algorithms and data structures as well as their applicable scenarios, helping developers make more suitable choices in real projects.
1. Introduction
Embedded systems are widely used in various fields such as industrial control, automotive electronics, and smart homes. In embedded programming, the reasonable selection and application of algorithms and data structures are crucial for improving system performance, efficiency, and stability. An algorithm is a series of steps to solve a problem, while a data structure is a way to organize and store data. Different algorithms and data structures exhibit varying performance in terms of time complexity and space complexity, thus requiring selection based on specific application scenarios.
2. Sorting Algorithms
2.1 Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly visits the elements of the array to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. This process is repeated until no more swaps are needed, meaning the array is sorted.
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}The time complexity of bubble sort is O(n^2), and the space complexity is O(1), making it suitable for scenarios with a small amount of data.
2.2 Selection Sort
Selection sort is a simple and intuitive sorting algorithm. Its working principle is to select the smallest (or largest) element from the unsorted data elements and place it at the beginning of the sequence, then continue to find the smallest (or largest) element from the remaining unsorted elements and place it at the end of the sorted sequence. This process continues until all data elements are sorted.
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}The time complexity of selection sort is O(n^2), and the space complexity is O(1). Its advantage is that it has fewer swaps, making it suitable for scenarios where the cost of swap operations is high.
2.3 Insertion Sort
Insertion sort is a simple and intuitive sorting algorithm. Its working principle is to build a sorted sequence, and for the unsorted data, it scans backward through the sorted sequence to find the appropriate position and insert it.
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}The best-case time complexity of insertion sort is O(n), while the average and worst-case time complexity is O(n^2), and the space complexity is O(1). Insertion sort is more efficient for data that is already mostly sorted.
2.4 Quick Sort
Quick sort is a divide-and-conquer sorting algorithm. It selects a pivot value, partitions the array into two parts such that all elements on the left are less than or equal to the pivot, and all elements on the right are greater than or equal to the pivot, and then recursively sorts the left and right parts.
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}The average time complexity of quick sort is O(n log n), while the worst-case time complexity is O(n^2), and the space complexity is O(log n). It is an efficient sorting algorithm that performs well in most cases.
3. Search Algorithms
3.1 Linear Search
Linear search is a simple search algorithm that starts from the first element of the array and compares each element one by one until the target element is found or the entire array is traversed.
#include <stdio.h>
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = linearSearch(arr, n, x);
if (result == -1) {
printf("Element is not present in array");
} else {
printf("Element is present at index %d", result);
}
return 0;
}The time complexity of linear search is O(n), making it suitable for searching in unordered arrays.
3.2 Binary Search
Binary search is an efficient search algorithm that requires the array to be sorted. It continuously narrows the search interval by half until the target element is found or it is determined that the target element does not exist.
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1) {
printf("Element is not present in array");
} else {
printf("Element is present at index %d", result);
}
return 0;
}The time complexity of binary search is O(log n), making it suitable for searching in sorted arrays.
4. Linked Lists
4.1 Singly Linked List
A singly linked list is a linear data structure consisting of a series of nodes, each containing a data element and a pointer to the next node.
#include <stdio.h>
#include <stdlib.h>
// Define linked list node
struct Node {
int data;
struct Node* next;
};
// Insert node at the beginning of the linked list
void insertAtBeginning(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;
}
// Print linked list
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
printf("Created Linked list is: ");
printList(head);
return 0;
}The time complexity for insertion and deletion operations in a singly linked list is O(1) (when the node is known), but the time complexity for search operations is O(n).
4.2 Doubly Linked List
A doubly linked list is a more complex linked list structure where each node contains a data element, a pointer to the next node, and a pointer to the previous node.
#include <stdio.h>
#include <stdlib.h>
// Define doubly linked list node
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Insert node at the beginning of the linked list
void insertAtBeginning(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);
new_node->prev = NULL;
if ((*head_ref) != NULL) {
(*head_ref)->prev = new_node;
}
(*head_ref) = new_node;
}
// Print linked list
void printList(struct Node* node) {
struct Node* last;
while (node != NULL) {
printf("%d ", node->data);
last = node;
node = node->next;
}
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
printf("Created Doubly Linked list is: ");
printList(head);
return 0;
}Doubly linked lists allow for easier operations on previous and next nodes during insertion and deletion, but require additional space to store the backward pointers.
5. Stacks
5.1 Sequential Stack
A sequential stack is a stack structure implemented using an array, following the Last In First Out (LIFO) principle.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Define stack structure
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// Initialize stack
void initStack(Stack* s) {
s->top = -1;
}
// Check if stack is empty
int isEmpty(Stack* s) {
return s->top == -1;
}
// Check if stack is full
int isFull(Stack* s) {
return s->top == MAX_SIZE - 1;
}
// Push operation
void push(Stack* s, int value) {
if (isFull(s)) {
printf("Stack is full!\n");
return;
}
s->data[++(s->top)] = value;
}
// Pop operation
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->data[(s->top)--];
}
int main() {
Stack s;
initStack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("Popped element: %d\n", pop(&s));
return 0;
}The time complexity for push and pop operations in a sequential stack is O(1), but it requires pre-allocated fixed-size arrays.
5.2 Linked Stack
A linked stack is a stack structure implemented using a linked list, also following the Last In First Out (LIFO) principle.
#include <stdio.h>
#include <stdlib.h>
// Define stack node
struct Node {
int data;
struct Node* next;
};
// Define stack structure
typedef struct {
struct Node* top;
} Stack;
// Initialize stack
void initStack(Stack* s) {
s->top = NULL;
}
// Check if stack is empty
int isEmpty(Stack* s) {
return s->top == NULL;
}
// Push operation
void push(Stack* s, int value) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = value;
new_node->next = s->top;
s->top = new_node;
}
// Pop operation
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
struct Node* temp = s->top;
int value = temp->data;
s->top = temp->next;
free(temp);
return value;
}
int main() {
Stack s;
initStack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("Popped element: %d\n", pop(&s));
return 0;
}The time complexity for push and pop operations in a linked stack is O(1), and it can dynamically allocate memory.
6. Queues
6.1 Sequential Queue
A sequential queue is a queue structure implemented using an array, following the First In First Out (FIFO) principle.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Define queue structure
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Queue;
// Initialize queue
void initQueue(Queue* q) {
q->front = 0;
q->rear = -1;
}
// Check if queue is empty
int isEmpty(Queue* q) {
return q->rear < q->front;
}
// Check if queue is full
int isFull(Queue* q) {
return q->rear == MAX_SIZE - 1;
}
// Enqueue operation
void enqueue(Queue* q, int value) {
if (isFull(q)) {
printf("Queue is full!\n");
return;
}
q->data[++(q->rear)] = value;
}
// Dequeue operation
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}
return q->data[(q->front)++];
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("Dequeued element: %d\n", dequeue(&q));
return 0;
}The time complexity for enqueue and dequeue operations in a sequential queue is O(1), but it has the problem of false overflow.
6.2 Circular Queue
A circular queue is an improvement over the sequential queue, which solves the problem of false overflow by connecting the ends of the array.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Define circular queue structure
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} CircularQueue;
// Initialize circular queue
void initCircularQueue(CircularQueue* q) {
q->front = 0;
q->rear = 0;
}
// Check if circular queue is empty
int isEmpty(CircularQueue* q) {
return q->front == q->rear;
}
// Check if circular queue is full
int isFull(CircularQueue* q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}
// Enqueue operation
void enqueue(CircularQueue* q, int value) {
if (isFull(q)) {
printf("Queue is full!\n");
return;
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % MAX_SIZE;
}
// Dequeue operation
int dequeue(CircularQueue* q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}
int value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return value;
}
int main() {
CircularQueue q;
initCircularQueue(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("Dequeued element: %d\n", dequeue(&q));
return 0;
}The time complexity for enqueue and dequeue operations in a circular queue is O(1), effectively utilizing the array space.
7. Trees
7.1 Binary Tree
A binary tree is a tree structure where each node has at most two child nodes.
#include <stdio.h>
#include <stdlib.h>
// Define binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Create new node
struct TreeNode* newNode(int data) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// Preorder traversal
void preOrder(struct TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
int main() {
struct TreeNode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Preorder traversal: ");
preOrder(root);
return 0;
}The time complexity for traversal operations (preorder, inorder, postorder) in a binary tree is O(n), where n is the number of nodes.
7.2 Binary Search Tree
A binary search tree is a special type of binary tree where for each node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value.
#include <stdio.h>
#include <stdlib.h>
// Define binary search tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Create new node
struct TreeNode* newNode(int data) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// Insert node
struct TreeNode* insert(struct TreeNode* root, int data) {
if (root == NULL) {
return newNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// Inorder traversal
void inOrder(struct TreeNode* root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
int main() {
struct TreeNode* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal: ");
inOrder(root);
return 0;
}The average time complexity for insertion, search, and deletion operations in a binary search tree is O(log n), but in the worst case (when the tree degenerates into a linked list), it is O(n).
8. Graphs
8.1 Adjacency Matrix Representation
An adjacency matrix is a method of representing a graph using a two-dimensional array, where the elements of the matrix indicate whether there is an edge connecting two vertices.
#include <stdio.h>
#define V 5
// Define graph structure
typedef struct {
int adjMatrix[V][V];
} Graph;
// Initialize graph
void initGraph(Graph* g) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g->adjMatrix[i][j] = 0;
}
}
}
// Add edge
void addEdge(Graph* g, int src, int dest) {
g->adjMatrix[src][dest] = 1;
g->adjMatrix[dest][src] = 1;
}
// Print graph
void printGraph(Graph* g) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", g->adjMatrix[i][j]);
}
printf("\n");
}
}
int main() {
Graph g;
initGraph(&g);
addEdge(&g, 0, 1);
addEdge(&g, 0, 4);
addEdge(&g, 1, 2);
addEdge(&g, 1, 3);
addEdge(&g, 1, 4);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
printGraph(&g);
return 0;
}The space complexity of an adjacency matrix is O(V^2), where V is the number of vertices.
8.2 Adjacency List Representation
An adjacency list is a method of representing a graph using linked lists, where each vertex corresponds to a linked list that stores the vertices adjacent to it.
#include <stdio.h>
#include <stdlib.h>
// Define adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Define adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Define graph structure
typedef struct {
int V;
struct AdjList* array;
} Graph;
// Create new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Create graph
Graph* createGraph(int V) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; i++) {
graph->array[i].head = NULL;
}
return graph;
}
// Add edge
void addEdge(Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// Print graph
void printGraph(Graph* graph) {
for (int v = 0; v < graph->V; v++) {
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main() {
int V = 5;
Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}The space complexity of an adjacency list is O(V + E), where V is the number of vertices and E is the number of edges.
9. Conclusion
In embedded programming, the choice of algorithms and data structures directly affects system performance and efficiency. This article introduced various common algorithms and data structures, including sorting algorithms, search algorithms, linked lists, stacks, queues, trees, and graphs, along with corresponding C language code examples. Developers should consider specific needs and scenarios in real projects, taking into account factors such as time complexity, space complexity, and implementation difficulty, to select the most suitable algorithms and data structures. Furthermore, optimizing algorithms and data structures can further enhance system performance. In the future, as embedded systems continue to evolve, research and application of algorithms and data structures will also deepen.
This article provides a relatively comprehensive reference for embedded developers by detailing common algorithms and data structures in embedded programming, along with code examples. Due to space limitations, some content may not be sufficiently in-depth, and readers can refer to relevant materials for further study as needed.