数据结构和算法是程序的核心，虽然在嵌入式应用中很少会用到，但了解认知这种思维过程是非常有必要的。一个好的程序员应该把数据结构和算法看的比代码更重要。
1.数据结构是什么？
定义1(宏观)：数据结构是为了高效访问数据而设计出的一种数据的组织和存储方式。
定义2(微观)：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
简言之，数据结构是带结构的数据元素的集合，“结构”就是指数据元素之间存在的关系。
数据结构，关注的是对这些数据元素的操作和数据元素之间的关系，不关心具体的数据项内容。目的是为了高效的访问数据。
2.内存的理解
一般而言，数据结构针对的是内存中的数据。所以在学习数据结构之前，需要先对内存有一个简单的了解。
内存由许多存储单元组成，每个存储单元可以存储一个固定大小的数据块，通常以字节（Byte）为单位。每个存储单元都有一个唯一的地址，操作系统正是根据这一地址去访问内存中的数据的。
我们讨论的数据结构中的数据元素就保存在这些一个个的内存单元中，这些数据元素或存储在连续的内存单元中，或存储在分散的内存单元中。
3.线性结构之数组
C 语言中，数组是具有相同类型的数据元素的集合。在所有的数据结构中，数组算是最常见、最简单的一种数据结构。
C 语言中，数组的长度一旦确定就不可以再变了。
（1）数组优缺点
优点：
1》查找容易（通过下标），时间复杂度为O(1)。不需要额外申请或删除空间。
2》使用下标位置索引(index)十分高效的访问任意元素，修改快
缺点：
- 插入、删除元素难，效率低。（需要移动大量元素以使元素空间连续）。
- 插入操作平均需要移动n/2个元素。
- 删除操作平均需要移动(n-1)/2个元素。
- 扩展相对繁琐。一方面需要确保能提供更大区域的连续内存空间，另一方面需要将原有数据复制到新的顺序表中。
（2）功能定义
| //初始化动态数组 |
| void initDynamicArray(DynamicArray *array, size_t initialCapacity) |
| //释放动态数组内存 |
| void destroyDynamicArray(DynamicArray *array) |
| //调整动态数组内存大小 |
| void resizeDynamicArray(DynamicArray *array, size_t newCapacity) |
| //获取动态数组长度（元素个数） |
| size_t getLength(const DynamicArray *array) |
| //在指定位置插入新元素 |
| void insertAt(DynamicArray *array, size_t index, int element) |
| //在末尾插入新元素 |
| void insertEnd(DynamicArray *array, int element) |
| //删除指定位置的元素并返回被删除的元素 |
| int deleteAt(DynamicArray *array, size_t index) |
| //删除末尾的元素并返回被删除的元素 |
| int deleteEnd(DynamicArray *array) |
| //遍历所有的元素 |
| void print(DynamicArray *array) |
（3）实现原理
可变长的动态数组是一种数据结构，它允许在运行时根据需要动态地调整数组的大小，而不需要提前指定固定的大小。这种动态数组通常被称为动态数组、动态分配数组、动态增长数组或动态内存数组。int arr[10];
C语言中是通过使用指针和内存分配函数来实现动态数组，常见的内存分配函数是malloc、realloc和free。下面是一些相关的概念和操作：
- 分配内存（malloc）： 在C语言中，可以使用malloc函数来分配一块指定大小的内存。例如，int *arr = (int *)malloc(n * sizeof(int)); 将分配能够存储n个整数的内存空间。
- 重新分配内存（realloc）： 如果需要改变动态数组的大小，可以使用realloc函数来重新分配内存。这允许你在保留原有数据的情况下扩展或缩小数组的大小。
- 释放内存（free）： 当不再需要动态数组时，应使用free函数释放之前分配的内存，以避免内存泄露。à 内存溢出
（4）代码实现
初始化动态数组
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
// 保存动态数组元素个数
int size;
// 保存指针变量动态数组开辟内存地址
int *data;
// 数组内部元素数量限制
int maxsize;
} DynamicArray;
// 第一个参数结构体指针，第二个参数开辟元素个数
void initDynamicArray(DynamicArray *array, size_t maxsize)
{
//动态开辟内存
array->data=(int*)malloc(sizeof(int)*maxsize);
//动态数组内部元素的个数
array->size=0;
//存储动态数组最大元素的个数
array->maxsize=maxsize;
}
int main()
{
// 创建结构体变量
DynamicArray array;
// 初始化动态数组
initDynamicArray(&array, 10);
return 0;
}释放动态数组内存
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
// 保存动态数组元素个数
int size;
// 保存指针变量动态数组开辟内存地址
int *data;
// 数组内部元素数量限制
int maxsize;
} DynamicArray;
// 第一个参数结构体指针，第二个参数开辟元素个数
void initDynamicArray(DynamicArray *array, size_t maxsize)
{
//动态开辟内存
array->data=(int*)malloc(sizeof(int)*maxsize);
//动态数组内部元素的个数
array->size=0;
//存储动态数组最大元素的个数
array->maxsize=maxsize;
}
//释放内存，传结构体指针
void destroyDynamicArray(DynamicArray *array)
{
free(array->data);//释放
//清空
array->size=0;
array->maxsize=0;
}
int main()
{
// 创建结构体变量
DynamicArray array;
// 初始化动态数组
initDynamicArray(&array, 10);
destroyDynamicArray(&array);
return 0;
}调整动态数组内存大小
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
// 保存动态数组元素个数
int size;
// 保存指针变量动态数组开辟内存地址
int *data;
// 数组内部元素数量限制
int maxsize;
} DynamicArray;
// 第一个参数结构体指针，第二个参数开辟元素个数
void initDynamicArray(DynamicArray *array, size_t maxsize)
{
//动态开辟内存
array->data=(int*)malloc(sizeof(int)*maxsize);
//动态数组内部元素的个数
array->size=0;
//存储动态数组最大元素的个数
array->maxsize=maxsize;
}
//释放内存，传结构体指针
void destroyDynamicArray(DynamicArray *array)
{
free(array->data);//释放
//清空
array->size=0;
array->maxsize=0;
}
void resizeDynamicArray(DynamicArray *array, size_t newMaxsize)
{
//判断数组需不需要扩充内存
if(array->size>=array->maxsize)
{
//动态数组内存变大
array->data=realloc(array->data,sizeof(int)*newMaxsize);
}
//存储一下最新的最大元素个数
array->maxsize=newMaxsize;
}
int main()
{
// 创建结构体变量
DynamicArray array;
// 初始化动态数组
initDynamicArray(&array, 10);
destroyDynamicArray(&array);
return 0;
}为节省时间，部分功能在代码内体现。
#include <stdio.h>
#include <stdlib.h>
// 结构体
typedef struct
{
// 保存动态数组内部的元素个数
int size;
// 指针变量存储动态开辟内存地址
int *data;
// 保存数组内部元素的存储上限制
int maxSize;
} DynamicArray;
// 初始化动态数组[占多少内层]
// 第一个参数:结构体指针 第二个参数:元素个数
void initDynamicArray(DynamicArray *array, int maxSize)
{
// 动态开辟内存
array->data = (int *)malloc(sizeof(int) * maxSize);
// 动态数组内部的元素的个数
array->size = 0;
// 存储动态数组存储的元素的最大的个数
array->maxSize = maxSize;
}
// 释放内存
void destroyDynamicArray(DynamicArray *array)
{
// 释放
free(array->data);
// 清空size、maxSize
array->size = 0;
array->maxSize = 0;
}
// 调整内存大小
// 第一个参数:动态数组 第二参数:
void resizeDynamicArray(DynamicArray *array, int newMaxSize)
{
// 判断动态数组是否需要拓展内层大小
if (array->size >= array->maxSize)
{
// 动态数组内存变大
array->data = realloc(array->data, sizeof(int) * newMaxSize);
}
// 存储一下最新的最大元素个数
array->maxSize = newMaxSize;
}
// 获取动态数组内部元素的个数
int getLength(DynamicArray *array)
{
return array->size;
}
// 动态数组指定位置插入元素
// 第一个参数:动态数组 第二个参数:插入元素的角标 第三个参数:插入的数据
void insertAt(DynamicArray *array, int index, int element)
{
// 先判断角标是否合理
if (index < 0 || index > array->maxSize)
{
return;
}
// 是否拓容
if (array->size >= array->maxSize)
{
resizeDynamicArray(array, array->maxSize * 2);
}
// 插入元素 size = 4 index = 2
for (int i = array->size; i > index; i--)
{
array->data[i] = array->data[i - 1];
}
// 将新的元素插入
array->data[index] = element;
// 元素的个数+1
array->size++;
}
// 打印动态数组的数组
void print(DynamicArray *array)
{
// 循环打印出动态数组内部的元素
for (int i = 0; i < array->size; i++)
{
printf("%d\n", array->data[i]);
}
}
int main()
{
// 创建一个动态数组结构体变量
DynamicArray array;
// 初始化动态数组
initDynamicArray(&array, 5);
insertAt(&array, 0, 10);
insertAt(&array, 1, 20);
insertAt(&array, 2, 30);
insertAt(&array, 3, 40);
insertAt(&array, 4, 50);
insertAt(&array, 5, 60);
insertAt(&array, 6, 70);
insertAt(&array, 7, 80);
print(&array);
return 0;
}4.线性结构之链表
（1）链表优缺点
1》优点
- 插入和删除操作效率高。
- 动态扩展性能更好，链表不需要像数组那样预先指定固定的大小，而是可以随时动态的增长或缩小。链表是真正的动态数据结构，不需要处理固定容量的问题。
2》缺点
- 查找慢。由于链表中的结点不是连续存储的，无法像数组一样根据索引直接计算出每个结点的地址。必须从头结点开始遍历链表，直到找到目标结点，这导致了链表的随机访问效率较低。
- 额外的存储空间。链表的每个结点都需要存储指向下一个结点的指针，这会占用额外的存储空间。所以，相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。
（2）功能定义
| 初始化链表 |
| void initLinkedList(LinkedList *list) |
| 返回链表的长度 |
| size_t getLength(const LinkedList *list) |
| 在指定位置插入元素 |
| void insertAt(LinkedList *list, size_t index, int element) |
| 在末尾插入元素 |
| void insertEnd(LinkedList *list, int element) |
| 删除指定位置的元素并返回被删除的元素 |
| int deleteAt(LinkedList *list, size_t index) |
| 删除末尾元素 |
| int deleteEnd(LinkedList *list) |
| 获取指定位置的元素 |
| int getElementAt(const LinkedList *list, size_t index) |
| 修改指定位置的元素 |
| void modifyAt(LinkedList *list, size_t index, int newValue) |
| 释放链表内存 |
| void destroyLinkedList(LinkedList *list) |
（3）代码实现
#include <stdio.h>
#include <stdlib.h>
// 定义一个结点
typedef struct Node
{
// 结点保存数据的地方
int data;
// 指针保存下一个结点的地址
struct Node *next;
} Node;
// 链表
typedef struct
{
// 存储结点的个数
int size;
// 存储"头结点"
Node *head;
} LinkedList;
// 初始化链表
void initLinkedList(LinkedList *list)
{
// 链表的结点的个数
list->size = 0;
// 头结点指向NULL
list->head = NULL;
}
// 返回结点的个数
int getLength(LinkedList *list)
{
return list->size;
}
// 在指定位置插入元素
// 第一个参数:链表 第二个参数:插入这个数据角标 第三个参数:节点保存的数据
void insertAt(LinkedList *list, int index, int element)
{
// 先判断插入的位置是不是合法的
if (index < 0 || index > list->size)
{
return;
}
// 创建新的结点:动态开辟内存的,结点保存数据、保存下一个节点的地址
Node *node = (Node *)malloc(sizeof(Node));
// 创建新节点需要保存的数据
node->data = element;
// 第一个位置插入
if (index == 0)
{
// 当前节点保存下一个节点的地址(暂时没有下一个)
node->next = list->head;
// 链表的头结点指向第一个节点的地址
list->head = node;
}
else
{
// 先找到插入位置的上一个节点
Node *prevNode = list->head;
for (int i = 1; i < index; i++)
{
prevNode = prevNode->next;
}
// 找到上一个节点的位置
node->next = prevNode->next;
prevNode->next = node;
}
// 节点的个数+1
list->size++;
}
// 在链表的末尾插入元素
void insertEnd(LinkedList *list, int element)
{
insertAt(list, list->size, element);
}
// 封装一个函数,专门找链表的某一个位置的前一个节点
Node *findPrevNode(LinkedList *list, int index)
{
// 从第一个结点向后找
Node *prevNode = list->head;
for (int i = 1; i < index; i++)
{
prevNode = prevNode->next;
}
// 返回不就是某一个位置前面的结点
return prevNode;
}
// 删除指定的元素
// 返回结点保存data数据 第一个参数:链表 第二个参数:删除元素的角标
int deleteAt(LinkedList *list, int index)
{
// 先判断给的角标对不对
if (index < 0 || index > list->size - 1)
{
return -1;
}
// 准备一个节点-代表将来要删除节点
Node *deleteNode = NULL;
// 删除的第一个节点
if (index == 0)
{
// 删除的结点
deleteNode = list->head;
// 修改头结点的地址
list->head = deleteNode->next;
}
else
{
// 找到index这个位置的前面节点
Node *prevNode = findPrevNode(list, index);
// 确定删除的结点
deleteNode = prevNode->next;
prevNode->next = deleteNode->next;
}
// 执行到这里说明干掉的结点已经找到了
// 取出结点的数据
int deleteData = deleteNode->data;
// 链表长度-1
list->size--;
// 节点空间free
free(deleteNode);
return deleteData;
}
// 删除末尾的元素
int deleteEnd(LinkedList *list)
{
return deleteAt(list, list->size - 1);
}
// 获取指定位置的元素
int getElementAt(LinkedList *list, int index)
{
// 先判断角标是否合法化
if (index < 0 || index > list->size - 1)
{
return -1;
}
// 第一个
if (index == 0)
{
return list->head->data;
}
else
{
// 获取上一个节点
Node *prevNode = findPrevNode(list, index);
return prevNode->next->data;
}
}
// 修改指定的元素
void modifyAt(LinkedList *list, int index, int newValue)
{
// 判断角标合法性
if (index < 0 || index > list->size - 1)
{
return;
}
// 判断第一个元素
if (index == 0)
{
list->head->data = newValue;
}
else
{
Node *prevNode = findPrevNode(list, index);
prevNode->next->data = newValue;
}
}
// 释放链表
void destroyLinkedList(LinkedList *list)
{
// 释放全部节点
Node *node = list->head;
// 全部节点释放
while (node != NULL)
{
Node *tmp = node;
node = node->next;
free(tmp);
}
// 节点的长度归零
list->size = 0;
// 头结点指向NULL
list->head = NULL;
}
// 打印输出
void print(LinkedList *list)
{
Node *node = list->head;
while (node != NULL)
{
printf("%d\n", node->data);
node = node->next;
}
}
int main()
{
// 进行初始化链表
LinkedList list;
initLinkedList(&list);
insertAt(&list, 0, 10);
insertAt(&list, 1, 20);
insertAt(&list, 2, 30);
insertAt(&list, 3, 40);
insertAt(&list, 4, 50);
insertAt(&list, 5, 150);
insertAt(&list, 6, 250);
// 尾巴插入一个350
insertEnd(&list, 350);
insertEnd(&list, 450);
// 删除元素
printf("干掉的====%d\n", deleteAt(&list, 4));
printf("干掉的====%d\n", deleteAt(&list, -2));
deleteEnd(&list);
deleteEnd(&list);
modifyAt(&list, 0, 12306);
modifyAt(&list, 5, 6666);
printf("0==%d\n", getElementAt(&list, 0));
print(&list);
destroyLinkedList(&list);
return 0;
}5.线性结构之栈
栈先进后出。
（1）功能定义
| 初始化栈 |
| void initStack(Stack *stack, size_t capacity) |
| 返回栈内元素个数 |
| size_t getSize(const Stack *stack) |
| 添加新元素 |
| void push(Stack *stack, int element) |
| 栈顶元素出栈并返回 |
| int pop(Stack *stack) |
| 释放栈内存 |
| void destroyStack(Stack *stack) |
（2）代码实现
#include <stdio.h>
#include <stdlib.h>
// 定义一个栈
typedef struct
{
// 栈需要内存空间
int *data;
// 统计元素的个数
int size;
// 限制元素的上线个数
int maxSize;
} Stack;
// 初始化栈
// 第一个参数:栈 结构体指针 第二个参数:首次创建的栈的最大容量
void initStack(Stack *stack, int maxSize)
{
// 初始化栈
stack->data = (int *)malloc(sizeof(int) * maxSize);
// 元素个数为零
stack->size = 0;
// 首次初始化栈元素上限个数
stack->maxSize = maxSize;
}
// 获取栈内元素的个数
int getSize(Stack *stack)
{
return stack->size;
}
// 添加元素,向栈内压数据
void push(Stack *stack, int element)
{
// 考虑是否拓容
if (stack->size >= stack->maxSize)
{
// 上限修改为元素2倍
stack->maxSize *= 2;
// 拓容
stack->data = (int *)realloc(stack->data, sizeof(int) * stack->maxSize);
}
// 栈压数据
stack->data[stack->size] = element;
stack->size++;
}
// 出栈
// 出栈:返回int,代表的是出栈的那个元素的数据
// 形参:栈
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;
stack->size = 0;
stack->maxSize = 0;
}
int main()
{
// 创建栈
Stack stack;
initStack(&stack, 5);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
push(&stack, 50);
push(&stack, 60);
printf("出栈了:%d\n", pop(&stack));
printf("出栈了:%d\n", pop(&stack));
printf("出栈了:%d\n", pop(&stack));
printf("出栈了:%d\n", pop(&stack));
printf("出栈了:%d\n", pop(&stack));
printf("出栈了:%d\n", pop(&stack));
printf("出栈了:%d\n", pop(&stack));
printf("获取栈内的元素个数:%d\n", getSize(&stack));
return 0;
}6.线性结构之队列
先进先出
（1）出现的问题
顺序队列中存在“假溢出”现象：尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针rear已超出向量空间的上界而不能做入队操作。
为充分利用空间，克服上述“假溢出”现象，有两种方法
方法1：使用数组实现，入队列时添加到队列的最后，出队列时移除第一个元素同时将右侧的元素左移。
方法2：为队列分配的向量空间看成是一个首尾相接的圆环，这种队列称为循环队列。
（2）功能定义
| 初始化队列 |
| void initQueue(Queue *queue, size_t capacity) |
| 返回队列内元素个数 |
| size_t getSize(const Queue *queue) |
| 添加新元素 |
| void enqueue(Queue *queue, int element) |
| 元素出队列 |
| int dequeue(Queue *queue) |
| 释放队列内存 |
| void destroyQueue(Queue *queue) |
| 遍历队列 |
| void printQueue(Queue *queue) |
7.代码实现
#include <stdio.h>
#include <stdlib.h>
// 结构体标识循环队列
typedef struct
{
// 设置队列的所占空间
int *data;
// 当前队列有多少个元素
int size;
// 队列存储数据上限制
int maxSize;
// 队首的标记
int front; // 数据出去的标记
// 对尾的标记
int rear; // 数据进来的标记
} Queue;
// 初始化队列
// 第一个队列空间 队列存储数据的上限
void initQueue(Queue *queue, int maxSize)
{
// 初始化
queue->data = (int *)malloc(sizeof(int) * maxSize);
// 对列的元素的个数
queue->size = 0;
// 上限值
queue->maxSize = maxSize;
// 队首
queue->front = 0;
// 队尾
queue->rear = 0;
}
// 返回队列的元素的个数
int getSize(Queue *queue)
{
return queue->size;
}
// 添加元素->入队
void enqueue(Queue *queue, int element)
{
// 先判断能否入队
if (queue->size >= queue->maxSize)
{
printf("队列已满!你先等着\n");
return;
}
// 入队
queue->data[queue->rear] = element;
queue->rear = (queue->rear + 1) % queue->maxSize;
// 元素的个数+1
queue->size++;
}
// 删除元素->离队
// int返回数据类型:出队的元素的数据
int dequeue(Queue *queue)
{
// 合法,如果是空的队列
if (queue->size == 0)
{
return -1;
}
// 出队
int data = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->maxSize;
queue->size--;
return data;
}
// 遍历队列
void printQueue(Queue *queue)
{
int index = queue->front;
for (int i = 0; i < queue->size; i++)
{
printf("%d\n", queue->data[index]);
index = (index + 1) % queue->maxSize;
}
}
// 释放内存
void destroyQueue(Queue *queue)
{
free(queue->data);
queue->data = NULL;
queue->size = 0;
queue->maxSize = 0;
queue->front = 0;
queue->rear = 0;
}
int main()
{
// 初始化队列
Queue queue;
initQueue(&queue, 6);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
enqueue(&queue, 50);
enqueue(&queue, 60);
enqueue(&queue, 9990); // 没有入队
// 出队列
printf("我%d数出去离开队伍\n", dequeue(&queue));
printf("我%d数出去离开队伍\n", dequeue(&queue));
enqueue(&queue, 70);
enqueue(&queue, 80);
printf("我%d数出去离开队伍\n", dequeue(&queue));
// 获取队列的元素的个数
printf("队列当前元素的个数:%d\n", getSize(&queue));
printf("*********");
printQueue(&queue);
return 0;
}