单片机C语言程序设计实训：100个案例中的数据结构与算法

# 1. 单片机C语言程序设计基础

单片机是一种集成了CPU、存储器和I/O接口等功能的微型计算机，广泛应用于各种电子设备中。C语言是单片机编程中常用的语言，具有高效、灵活、易于移植等特点。

### 1.1 C语言基础

C语言是一种结构化编程语言，由变量、数据类型、运算符、控制语句和函数等基本元素组成。变量用于存储数据，数据类型定义变量存储的数据类型，运算符用于对数据进行操作，控制语句用于控制程序的执行流程，函数用于封装代码块。

### 1.2 单片机C语言特点

单片机C语言与标准C语言相比，具有以下特点：

- **资源受限：**单片机内存和处理能力有限，因此需要优化代码以节省资源。
- **嵌入式系统：**单片机通常作为嵌入式系统的一部分，与硬件设备紧密结合。
- **实时性：**单片机系统往往需要对外部事件做出快速响应，因此需要考虑程序的实时性。

# 2. 数据结构基础

数据结构是组织和存储数据的特定方式，它决定了数据在计算机内存中的存储方式和访问方式。数据结构的选择对于程序的效率和性能至关重要。本章将介绍几种基本数据结构，包括数组、链表、栈、队列、树和图。

### 2.1 数组和链表

**2.1.1 一维数组和多维数组**

数组是一种线性数据结构，它将相同类型的数据元素存储在连续的内存空间中。数组中的每个元素都可以通过其索引来访问。一维数组是数组的最简单形式，它只包含一个维度。多维数组包含多个维度，例如二维数组（矩阵）和三维数组（立方体）。

// 一维数组
int arr[10];

// 多维数组
int matrix[3][3];

**2.1.2 链表的定义和操作**

链表是一种非线性数据结构，它将数据元素存储在彼此相连的节点中。每个节点包含数据元素和指向下一个节点的指针。链表可以动态地增长和缩小，因为它不需要预先分配内存空间。

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

// 创建链表
struct Node *head = NULL;

// 插入节点
void insert(int data) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = head;
    head = new_node;
}

// 删除节点
void delete(int data) {
    struct Node *current = head;
    struct Node *previous = NULL;

    while (current != NULL) {
        if (current->data == data) {
            if (previous == NULL) {
                head = current->next;
            } else {
                previous->next = current->next;
            }
            free(current);
            break;
        }
        previous = current;
        current = current->next;
    }
}

### 2.2 栈和队列

**2.2.1 栈的定义和操作**

栈是一种线性数据结构，它遵循后进先出（LIFO）原则。元素只能从栈顶添加或删除。栈通常用于函数调用、递归和表达式求值。

struct Stack {
    int *arr;
    int top;
    int size;
};

// 创建栈
struct Stack *create_stack(int size) {
    struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
    stack->arr = (int *)malloc(sizeof(int) * size);
    stack->top = -1;
    stack->size = size;
    return stack;
}

// 入栈
void push(struct Stack *stack, int data) {
    if (stack->top == stack->size - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

// 出栈
int pop(struct Stack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->arr[stack->top--];
}

**2.2.2 队列的定义和操作**

队列是一种线性数据结构，它遵循先进先出（FIFO）原则。元素从队列尾部添加，从队列头部删除。队列通常用于消息传递、任务调度和缓冲。

struct Queue {
    int *arr;
    int front;
    int rear;
    int size;
};

// 创建队列
struct Queue *create_queue(int size) {
    struct Queue *queue = (struct Queue *)malloc(sizeof(struct Queue));
    queue->arr = (int *)malloc(sizeof(int) * size);
    queue->front = -1;
    queue->rear = -1;
    queue->size = size;
    return queue;
}

// 入队
void enqueue(struct Queue *queue, int data) {
    if ((queue->rear + 1) % queue->size == queue->front) {
        printf("Queue overflow\n");
        return;
    }
    if (queue->front == -1) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % queue->size;
    queue->arr[queue->rear] = data;
}

// 出队
int dequeue(struct Queue *queue) {
    if (queue->front == -1) {
        printf("Queue underflow\n");
        return -1;
    }
    int data = queue->arr[queue->front];
    if (queue->front == queue->rear) {
        queue->front = -1;
        queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % queue->size;
    }
    return data;
}

### 2.3 树和图

**2.3.1 树的定义和操作**

树是一种非线性数据结构，它由一个根节点和多个子树组成。每个子树也是一棵树。树通常用于表示层次结构、文件系统和搜索算法。

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

// 创建树
struct Node *create_tree(int data) {
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 查找节点
struct Node *find_node(struct Node *root, int data) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == data) {
        return root;
    }
    struct Node *left = find_node(root->left, data);
    struct Node *right = find_node(root->right, data);
    return left ? left : right;
}

// 插入节点
void insert_node(struct Node *root, int data) {
    if (root == NULL) {
        root = create_tree(data);
        return;
    }
    if (data < root->data) {
        insert_node(root->left, data);
    } else {
        insert_node(root->right, data);
    }
}

**2.3.2 图的定义和操作**

图是一种非线性数据结构，它由一组顶点和连接顶点的边组成。图通常用于表示网络、社交网络和地图。

struct Graph {
    int num_vertices;
    int **adj_matrix;
};

// 创建图
struct Graph *create_graph(int num_vertices) {
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    graph->num_vertices = num_vertices;
    graph->adj_matrix = (int **)malloc(sizeof(int *) * num_vertices);
    for (int i = 0; i < num_vertices; i++) {