嵌入式开发学习日记——数据结构基础

数据结构基础

学习内容概述 今天我开始学习数据结构，重点理解了它在编程中的重要性。数据结构是为了高效访问数据而设计的一种数据组织和存储方式。它不仅仅关注数据的存储位置，还关注数据元素之间的关系。

计算机科学家尼古拉斯·沃斯提出了著名的公式：

算法 + 数据结构 = 程序

这说明数据结构与算法是程序设计的核心。数据结构就像战场上的排兵布阵，设计良好的数据结构能让我们在处理问题时事半功倍。

内存的理解 数据结构的基础是对内存的理解。内存由许多存储单元组成，每个单元都有唯一的地址。数据可以保存在连续的内存单元中，也可以保存在分散的单元中。选择哪种方式，取决于我们想如何组织和操作这些数据。

数据结构的逻辑结构 数据的逻辑结构主要描述数据元素之间的逻辑关系，可以分为以下几类：

• 集合结构：数据元素之间只有属于同一集合的关系。

• 线性结构：数据元素之间存在一对一的关系，比如数组、链表等。

• 树形结构：数据元素之间存在一对多的关系，比如家谱、文件系统。

• 图形结构：数据元素之间存在多对多的关系，比如社交网络。

数据的存储结构 数据的存储结构是逻辑结构在计算机中的实现，可以分为：

• 顺序存储结构：相邻的数据元素在内存中也相邻，比如数组。

• 链式存储结构：相邻的数据元素可以在内存中不相邻，用指针链接，比如链表。

• 索引存储结构：在数据存储之外，有一个索引目录，比如数据库的索引。

• 散列存储结构：通过计算关键字来确定数据存储地址，比如散列表。

线性结构之数组

学习内容概述 在C语言中，数组是具有相同类型数据元素的集合。数组的特点是访问速度快，因为可以通过下标直接访问指定位置的元素。今天我学到了如何用C语言实现数组的基础操作。

代码示例：数组的定义与操作

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

// 动态数组结构体
typedef struct
{
    int *data;       // 指向动态数组的指针
    size_t size;     // 当前数组中的元素个数
    size_t capacity; // 当前数组的容量（可以容纳的最大元素个数）
} DynamicArray;

// 初始化动态数组
void initDynamicArray(DynamicArray *array, size_t initialCapacity)
{
    array->data = (int *)malloc(initialCapacity * sizeof(int)); // 分配初始内存
    array->size = 0;       // 初始化元素个数为0
    array->capacity = initialCapacity;     // 设置初始容量
}

// 释放动态数组内存
void destroyDynamicArray(DynamicArray *array)
{
    free(array->data);   // 释放动态数组内存
    array->size = 0;     // 重置元素个数为0
    array->capacity = 0; // 重置容量为0
}

// 调整动态数组内存大小
void resizeDynamicArray(DynamicArray *array, size_t newCapacity)
{
    array->data = (int *)realloc(array->data, newCapacity * sizeof(int)); // 调整数组内存大小
    array->capacity = newCapacity;       // 更新容量
}

// 获取动态数组长度（元素个数）
size_t getLength(const DynamicArray *array)
{
    return array->size; // 返回数组中的元素个数
}

// 在指定位置插入新元素
void insertAt(DynamicArray *array, size_t index, int element)
{
    if (index > array->size)
    {
        return; // 忽略无效的插入位置
    }

    if (array->size >= array->capacity)
    {
        size_t newCapacity = array->capacity * 2; // 如果容量不足，扩大容量
        resizeDynamicArray(array, newCapacity);
    }

    for (size_t i = array->size; i > index; i--)
    {
        array->data[i] = array->data[i - 1]; // 后移元素以腾出插入位置
    }

    array->data[index] = element; // 在指定位置插入新元素
    array->size++;                // 更新元素个数
}

// 在末尾插入新元素
void insertEnd(DynamicArray *array, int element)
{
    insertAt(array, array->size, element); // 在末尾插入新元素
}

// 删除指定位置的元素并返回被删除的元素
int deleteAt(DynamicArray *array, size_t index)
{
    if (index >= array->size)
    {
        return -1; // 忽略无效的删除位置
    }

    int deletedElement = array->data[index]; // 获取被删除的元素

    for (size_t i = index; i < array->size - 1; i++)
    {
        array->data[i] = array->data[i + 1]; // 前移元素以填补删除位置
    }

    array->size--; // 更新元素个数

    return deletedElement; // 返回被删除的元素
}

// 删除末尾的元素并返回被删除的元素
int deleteEnd(DynamicArray *array)
{
    return deleteAt(array, array->size - 1); // 删除末尾的元素
}

// 遍历所有的元素
void print(DynamicArray *array)
{
    for (int i = 0; i < array->size; i++)
    {
        printf("%d  ", array->data[i]);
    }
    printf("\n");
}

int main()
{
    DynamicArray myArray; // 声明动态数组

    // 初始化动态数组
    initDynamicArray(&myArray, 2);
    printf("初始化动态数组,初始容量为2\n");

    // 向动态数组尾部插入元素
    insertEnd(&myArray, 1);
    insertEnd(&myArray, 2);
    printf("向动态数组尾部插入了2个元素\n");

    // 打印动态数组当前长度
    printf("动态数组当前长度:%zu\n", getLength(&myArray));

    // 在索引1的位置插入元素3
    insertAt(&myArray, 1, 3);
    printf("在索引1的位置插入元素3\n");

    // 再次打印动态数组当前长度
    printf("动态数组当前长度:%zu\n", getLength(&myArray));

    // 删除索引1的元素
    printf("删除索引1的元素,该元素是%d\n", deleteAt(&myArray, 1));

    // 删除动态数组末尾元素
    printf("删除动态数组末尾元素,该元素是%d\n", deleteEnd(&myArray));

    // 释放动态数组内存
    destroyDynamicArray(&myArray);
    printf("动态数组内存释放完成\n");

    return 0;
}

通俗理解 数组就像是一排连续的储物柜，每个储物柜都有一个编号（下标），你可以通过编号快速找到需要的物品（数据）。数组的长度一旦确定就不能改变，这就好比一排储物柜数量固定了，不能再增加新的储物柜。

线性结构之链表

学习内容概述 链表是由一系列结点组成的线性结构，每个结点包含一个数据域和一个指针域。链表的优点是可以动态扩展，不需要预先指定大小，适合频繁插入和删除的场景。

代码示例：链表的定义与操作

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

// 链表节点结构
typedef struct Node
{
    int data;          // 节点存储的数据
    struct Node *next; // 指向下一个节点的指针
} Node;

// 链表结构
typedef struct
{
    Node *head;  // 链表头节点指针
    size_t size; // 链表中的节点个数
} LinkedList;

// 初始化链表
void initLinkedList(LinkedList *list)
{
    list->head = NULL; // 初始化头节点为空
    list->size = 0;    // 初始化节点个数为0
}

// 返回链表的长度
size_t getLength(const LinkedList *list)
{
    return list->size; // 返回链表的节点个数
}

// 在指定位置插入元素
void insertAt(LinkedList *list, size_t index, int element)
{
    if (index > list->size)
    {
        return; // 忽略无效的插入位置
    }

    Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新节点
    newNode->data = element; // 设置新节点的数据

    if (index == 0) // 如果插入的位置是头部
    {
        newNode->next = list->head; // 将新节点的下一个节点指向当前的头节点
        list->head = newNode; // 新节点成为新的头节点
    }
    else // 插入在链表的其他位置
    {
        Node *prevNode = list->head; // 从头节点开始查找插入位置

        // 遍历到插入位置的前一个节点
        for (size_t i = 0; i < index - 1; i++)
        {
            prevNode = prevNode->next; // 前一个节点指向下一个节点
        }

        newNode->next = prevNode->next; // 将新节点的下一个节点指向前一个节点的下一个节点
        prevNode->next = newNode; // 将前一个节点的下一个节点指向新节点
    }

    list->size++; // 更新节点个数
}

// 在末尾插入元素
void insertEnd(LinkedList *list, int element)
{
    insertAt(list, list->size, element); // 在链表末尾插入元素
}

// 删除指定位置的元素并返回被删除的元素
int deleteAt(LinkedList *list, size_t index)
{
    if (index >= list->size) // 如果索引无效
    {
        return -1; // 返回-1表示删除失败
    }

    int deletedElement; // 存储被删除的元素值

    if (index == 0) // 如果删除的是头节点
    {
        Node *temp = list->head; // 保存当前头节点
        list->head = temp->next; // 将头节点指向下一个节点
        deletedElement = temp->data; // 记录被删除节点的数据
        free(temp); // 释放被删除节点的内存
    }
    else // 删除链表中间或尾部的节点
    {
        Node *prevNode = list->head; // 从头节点开始查找删除位置

        // 遍历到删除位置的前一个节点
        for (size_t i = 0; i < index - 1; i++)
        {
            prevNode = prevNode->next; // 前一个节点指向下一个节点
        }

        Node *temp = prevNode->next; // 获取待删除的节点
        prevNode->next = temp->next; // 将前一个节点的下一个节点指向待删除节点的下一个节点
        deletedElement = temp->data; // 记录被删除节点的数据
        free(temp); // 释放被删除节点的内存
    }

    list->size--; // 更新节点个数
    return deletedElement; // 返回被删除的元素值
}

// 删除末尾元素
int deleteEnd(LinkedList *list)
{
    return deleteAt(list, list->size - 1); // 删除链表末尾的元素
}

// 获取指定位置的元素
int getElementAt(const LinkedList *list, size_t index)
{
    if (index >= list->size) // 如果索引无效
    {
        return -1; // 返回-1表示无效索引
    }

    Node *currentNode = list->head; // 从头节点开始遍历
    for (size_t i = 0; i < index; i++)
    {
        currentNode = currentNode->next; // 遍历到指定的索引
    }

    return currentNode->data; // 返回指定位置的元素
}

// 修改指定位置的元素
void modifyAt(LinkedList *list, size_t index, int newValue)
{
    if (index >= list->size) // 如果索引无效
    {
        return; // 忽略无效的修改位置
    }

    Node *currentNode = list->head; // 从头节点开始遍历

    for (size_t i = 0; i < index; i++)
    {
        currentNode = currentNode->next; // 遍历到指定的索引
    }

    currentNode->data = newValue; // 修改节点的值
}

// 释放链表内存
void destroyLinkedList(LinkedList *list)
{
    Node *currentNode = list->head; // 从头节点开始遍历
    while (currentNode != NULL) // 遍历链表
    {
        Node *temp = currentNode; // 保存当前节点
        currentNode = currentNode->next; // 移动到下一个节点
        free(temp); // 释放每个节点的内存
    }

    list->head = NULL; // 头节点置为空
    list->size = 0;    // 节点个数置为0
}

int main()
{
    LinkedList myList; // 声明链表

    initLinkedList(&myList); // 初始化链表
    printf("初始化链表成功!\n");

    insertEnd(&myList, 1); // 链表尾部插入元素1
    insertEnd(&myList, 2); // 链表尾部插入元素2
    printf("向链表插入了2个元素\n");

    printf("链表长度为: %zu\n", getLength(&myList)); // 获取链表长度

    insertAt(&myList, 1, 3); // 在索引1处插入元素3
    printf("在索引1处插入元素3\n");

    printf("链表长度为: %zu\n", getLength(&myList)); // 再次获取链表长度

    printf("索引1处的元素为: %d\n", getElementAt(&myList, 1)); // 获取索引1处的元素

    modifyAt(&myList, 0, 4); // 修改索引0处的元素
    printf("把索引0处的元素修改为4\n");

    printf("删除索引1处的元素,该元素值是: %d\n", deleteAt(&myList, 1)); // 删除索引1处的元素

    destroyLinkedList(&myList); // 销毁链表
    printf("链表销毁成功!\n");

    return 0; // 返回0表示程序正常结束
}

通俗理解 链表就像是一串珍珠项链，每颗珍珠（节点）都有一根线（指针）连接到下一颗珍珠。你可以随时在项链中加入或取出一颗珍珠，而不需要重新排列所有珍珠，因此链表非常适合需要频繁添加或删除数据的场景。

线性结构之栈

学习内容概述 今天我还学习了栈这一数据结构。栈是一种只能在表的一端进行插入和删除操作的线性表，其特点是后进先出（LIFO）。栈的应用非常广泛，比如函数调用栈、表达式求值等。

代码示例：栈的实现（基于数组）

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

// 栈结构
typedef struct
{
    int *data;       // 动态数组存储栈元素
    size_t size;     // 栈内元素个数
    size_t capacity; // 动态数组的容量
} Stack;

// 初始化栈
void initStack(Stack *stack, size_t capacity)
{
    stack->data = (int *)malloc(capacity * sizeof(int)); // 分配初始容量的内存
    stack->size = 0;                                     // 初始元素个数为0
    stack->capacity = capacity;                          // 设置容量
}

// 返回栈内元素个数
size_t getSize(const Stack *stack)
{
    return stack->size; // 返回栈内元素个数
}

// 添加新元素
void push(Stack *stack, int element)
{
    if (stack->size == stack->capacity) // 检查栈是否已满
    {
        // 如果栈已满，需要扩展容量
        stack->capacity *= 2; // 将容量翻倍
        stack->data = (int *)realloc(stack->data, stack->capacity * sizeof(int)); // 重新分配内存
    }
    stack->data[stack->size] = element; // 将元素压入栈顶
    stack->size++;                      // 更新元素个数
}

// 栈顶元素出栈并返回
int pop(Stack *stack)
{
    if (stack->size == 0) // 检查栈是否为空
    {
        return -1; // 栈为空，返回无效值
    }
    stack->size--;                   // 更新元素个数
    return stack->data[stack->size]; // 返回栈顶元素
}

// 释放栈内存
void destroyStack(Stack *stack)
{
    free(stack->data); // 释放动态数组内存
    stack->data = NULL; // 将指针置为NULL以避免悬挂指针
    stack->size = 0;    // 重置栈内元素个数
    stack->capacity = 0; // 重置容量
}

int main()
{
    Stack myStack; // 声明一个栈变量

    // 初始化栈
    initStack(&myStack, 2); // 设置初始容量为2
    printf("初始化栈,初始容量为2\n");

    // 向栈压入元素
    push(&myStack, 1); // 压入元素1
    push(&myStack, 2); // 压入元素2

    printf("栈内元素个数:%zu\n", getSize(&myStack)); // 打印栈内元素个数

    // 弹出栈顶元素
    printf("弹出栈顶元素:%d\n", pop(&myStack)); // 弹出栈顶元素并打印

    // 释放栈内存
    destroyStack(&myStack); // 释放栈的内存
    printf("栈内存已释放\n");

    return 0; // 返回0，表示程序正常结束
}

通俗理解 栈就像是一摞书，新的书只能放在最上面（压栈），取书也只能从最上面开始拿（弹栈）。这种“后进先出”的特点非常适合处理那些需要按相反顺序进行的操作，比如浏览器的后退功能或者函数的递归调用。

线性结构之队列

学习内容概述 今天我学习了队列这一数据结构。队列是一种只能在一端插入数据，在另一端删除数据的线性表，其特点是先进先出（FIFO）。队列的应用也非常广泛，比如任务调度、数据流处理等。

代码示例：队列的实现（基于数组）

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

// 队列结构
typedef struct
{
    int *data;       // 动态数组存储队列元素
    size_t size;     // 队列内元素个数
    size_t capacity; // 动态数组的容量
    size_t front;    // 队列头指针
    size_t rear;     // 队列尾指针
} Queue;

// 初始化队列
void initQueue(Queue *queue, size_t capacity)
{
    queue->data = (int *)malloc(capacity * sizeof(int)); // 分配初始容量的内存
    queue->size = 0;                                     // 初始元素个数为0
    queue->capacity = capacity;                          // 设置容量
    queue->front = 0;                                    // 队列头指针初始化
    queue->rear = 0;                                     // 队列尾指针初始化
}

// 返回队列内元素个数
size_t getSize(const Queue *queue)
{
    return queue->size; // 返回队列当前元素个数
}

// 添加新元素
void enqueue(Queue *queue, int element)
{
    if (queue->size == queue->capacity) // 检查队列是否已满
    {
        printf("队列已满，添加失败\n"); // 输出提示信息
        return; // 队列已满，无法添加新元素
    }
    queue->data[queue->rear] = element; // 将元素添加到队列尾部
    queue->rear = (queue->rear + 1) % queue->capacity; // 循环更新队列尾指针
    queue->size++; // 更新元素个数
}

// 元素出队列
int dequeue(Queue *queue)
{
    if (queue->size == 0) // 检查队列是否为空
    {
        return -1; // 队列为空，返回无效值
    }
    int dequeuedElement = queue->data[queue->front]; // 获取队列头部元素
    queue->front = (queue->front + 1) % queue->capacity; // 循环更新队列头指针
    queue->size--; // 更新元素个数
    return dequeuedElement; // 返回出队的元素
}

// 释放队列内存
void destroyQueue(Queue *queue)
{
    free(queue->data); // 释放动态数组内存
    queue->data = NULL; // 将指针置为NULL以避免悬挂指针
    queue->size = 0; // 重置队列元素个数
    queue->capacity = 0; // 重置队列容量
    queue->front = 0; // 重置队列头指针
    queue->rear = 0; // 重置队列尾指针
}

// 遍历队列并打印元素
void printQueue(Queue *queue)
{
    for (size_t i = queue->front, j = 0; j < queue->size; i++, j++)
    {
        int data = queue->data[i % queue->capacity]; // 计算实际索引并获取元素
        printf("%d  ", data); // 打印元素
    }
    printf("\n"); // 换行
}

int main()
{
    Queue myQueue; // 声明一个队列变量

    // 初始化队列
    initQueue(&myQueue, 2); // 设置初始容量为2
    printf("初始化队列,初始容量为2\n");

    // 入队元素
    enqueue(&myQueue, 1); // 添加元素1到队列
    enqueue(&myQueue, 2); // 添加元素2到队列

    printf("队列内元素个数:%zu\n", getSize(&myQueue)); // 打印队列内元素个数

    // 出队元素
    printf("出队元素:%d\n", dequeue(&myQueue)); // 弹出队列头部元素并打印

    // 释放队列内存
    destroyQueue(&myQueue); // 释放队列的内存
    printf("队列内存已释放\n");

    return 0; // 返回0，表示程序正常结束
}

通俗理解 队列就像排队买票的人群，新的顾客只能站到队伍的末尾（入队），而服务总是从队伍的最前面开始（出队）。这种“先进先出”的特点非常适合任务调度的场景，比如打印机任务或者操作系统中的进程管理。

心得总结 栈的“后进先出”特性在程序设计中非常有用，尤其是处理递归调用或需要逆序操作的场景。通过实际编写代码，我更好地理解了栈的工作原理，并体验到了栈在内存管理和函数调用中的重要性。对于实现栈，我学到了基于数组的顺序栈和基于链表的链式栈的不同实现方式，分别有各自的优缺点，选择时需要根据具体场景进行权衡。通过学习队列，我理解了队列的先进先出特性，以及它在数据处理和任务调度中的重要性。通过编写队列代码，我更好地理解了如何用数组实现队列，并学会了如何判断队列的空和满情况。对于队列的实现，还可以使用链表来实现一个动态队列，这样就不再受限于数组的固定大小。