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

数据结构基础

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

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

算法 + 数据结构 = 程序

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

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

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

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

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

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

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

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

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

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

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

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

线性结构之数组

学习内容概述 在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;       // 初始化元素个数为0array->capacity = initialCapacity;     // 设置初始容量
}// 释放动态数组内存
void destroyDynamicArray(DynamicArray *array)
{free(array->data);   // 释放动态数组内存array->size = 0;     // 重置元素个数为0array->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的位置插入元素3insertAt(&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); // 链表尾部插入元素1insertEnd(&myList, 2); // 链表尾部插入元素2printf("向链表插入了2个元素\n");printf("链表长度为: %zu\n", getLength(&myList)); // 获取链表长度insertAt(&myList, 1, 3); // 在索引1处插入元素3printf("在索引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;                                     // 初始元素个数为0stack->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); // 设置初始容量为2printf("初始化栈,初始容量为2\n");// 向栈压入元素push(&myStack, 1); // 压入元素1push(&myStack, 2); // 压入元素2printf("栈内元素个数:%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;                                     // 初始元素个数为0queue->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); // 设置初始容量为2printf("初始化队列,初始容量为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，表示程序正常结束
}

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

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