嵌入式数据结构以及算法（数据结构篇）

数据结构可以说是嵌入式开发学习中比较重要的一个部分了，而沉迷于基础硬件控制的我到现在才意识到这个东西的重要性可以说是比较迟钝了，但是迟钝总比知道也不学来的好（自我安慰请忽略）下面总结一下经过几天学习学到的数据结构知识和嵌入式开发的最最基本的数据结构对比。

数据结构是什么？

Sartaj Sahni 在《数据结构、算法与应用》中说到，数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系，这些联系可以通过定义相关的函数来给出。
用人话来说就是:（觉得是废话的自行跳过，不影响后期理解）

数据结构分为数据和结构，数据就是数据，结构就是数据的联系。

为什么要用数据结构？

在我还是嵌入式开发小白的时候也比较纠结这个问题，存数据我用变量和数组就好了啊，搞那么复杂干什么！现在想想真的是 Too young too simple，some times naive！
其实没有去理解嵌入式设备的存储地址之前都是想不清楚这个问题的，因为没有去考虑嵌入式芯片有限的片上存储空间，用数组申请的是内存是以数组头开始的地址申请一串连续的内存用于存储数组数据，项目简单的时候，用不完内存的情况下倒是没有问题，但是复杂项时，代码里需要的内存空间多了就会出现Hardware Fault之类的问题，知道是内存溢出，但是除了加EEPROM之外基本无解。
数据结构中链表的出现可以缓解一下这个问题，相对于连续申请的内存，数据结构的出现能够离散化数据位置，将整个内存空间碎片使用上，而且也能达到数组存储的效果。
当然与数组存储最最不同的优势是，数据结构不需要提前知道数据长度，相当于数据有多长就把数据结构加多长。这点我觉得是最大的优势了。

数据结构怎么用？

数据结构分为多种，常用的基本类别分为以下三种

接下来顺序介绍一下几种数据结构

顺序表

顺序表就是数组加存储最后更新数据位置的整形变量构成的结构体；该结构体为数据结构整体。

实现方式

#define MAXSIZE 10

typedef int datatype;
typedef int postype;

struct list{
datatype data[N];		//数据数组
postype last;			//整形变量，存储最后一个更新数据的数组位置
};

链表

1.单向链表

单向链表为单个数据和下个数据节点首地址两个元素构成的结构体；该结构体为数据结构单元，整体由多个单元构成。

实现方式

typedef int datatype;

typedef struct node {
datatype data;				//数据单元
struct node * next;			//下个数据节点指针
}Linknode, *Linklist;

2.双向循环链表

双向链表为单个数据和前一个数据位置、后一个数据位置三个元素与构成的结构体；该结构体为数据结构单元，整体由多个单元构成。

实现方式

typedef int datatype;

typedef struct node{
datatype data;			//数据
struct node *prior;		//上个单元首地址
struct node *next;		//下个单元首地址
}DLinkNode, * DLinkList;

栈

1.顺序栈

顺序栈为单个数据和栈总长度、最后入栈节点下标三个元素与构成的结构体；该结构体为数据结构单元，整体由多个单元构成。

实现方式

typedef int datatype;

typedef struct node{
datatype *data;		//数据
int maxlen;			//栈总长度
int top;			//最后入栈节点下标
}SeqStack，*SeqStack_t;

2.链式栈

链式栈为单个数据和上一个入栈节点首地址两个元素与构成的结构体；该结构体为数据结构单元，整体由多个单元构成。

实现方式

typedef int datatype;

typedef struct node{
datatype data;				//数据
struct lstacknode * next;	//上一个入栈节点首地址
}LinkStacknode, *LinkStacknode_t;

栈为先进后出，可以理解为一本一本堆书，堆完之后从顶上一本一本拿。

队列

1、顺序队列

顺序队列为队列数组和队头数据位置的前一个位置下标、队尾数据位置下标三个元素与构成的结构体；该结构体为数据结构整体。
实现方式

#define N 10

typedef int datatype;

typedef struct seqqueue{
datatype data[N];
int front;
int rear;
}SeqQueue, *SeqQueue_t;

2、链式队列

链式队列包括两个结构体，为数据域和队列模型，队列模型为队列首末地址两个元素构成，数据域为数据和下一个数据节点首地址两个元素构成。

实现方式

typedef int datatype;

typedef struct node{			//数据域
datatype data;					//数据
struct linkqueuenode *next;		//下一节点首地址
}Queuenode, *Queuenode_t;

typedef struct linkqueue{		//队列模型
linkqueue_pnode front;			//首节点地址
linkqueue_pnode rear;			//末节点地址
}LinkQueue, *LinkQueue_t;

针对于队列和堆栈的运作方式我听过一个更方便的记忆法：
1、队列是吃多了拉（先进先出）
2、堆栈是吃多了吐（先进后出）
这个记忆方法不优雅，但有效！