来源 | 技能让梦想更伟大（ID：TechDreamer）
说真的，任何提及嵌入式软件怎么入门啊？须要学些什么东西啊，我差不多同等的回答都是：软件方面C措辞和数据构造加上一些大略常用的算法，这些须要学好。
借着自己的回顾学习，我也写一些根本的数据构造知识，多画图，少打字，与大家一起学习数据构造。
顺序存储和链式存储数组—顺序存储数组作为一个顺序储存办法的数据构造，可是有大作为的，它的灵巧利用为我们的程序设计带来了大量的便利；
但是，但是，数组最大的缺陷便是我们的插入和删除时须要移动大量的元素，以是呢，大量的花费韶光，以及冗余度难以接管了。
以C措辞数组插入一个元素为例，当我们须要在一个数组 {1,2,3,4} 的第1个元素后的位置插入一个’A’时，我们须要做的有：
将第1个元素后的整体元素后移，形成新的数组 {1,2,2,3,4}；
再将第2个元素位置的元素更换为我们所须要的元素’A’；
终极形成我们的预期，这须要很多的操作喔。
上图可以看出，利用数组都有这两大缺陷：
插入删除操作所须要移动的元素很多，摧残浪费蹂躏算力。
必须为数组开足够的空间，否则有溢出风险。
链表—链式存储
由于数组的这些缺陷，自然而然的就产生链表的思想了。
链表通过不连续的储存办法，自适应内存大小，以及指针的灵巧利用，奥妙的简化了上述的内容。
链表的基本思维是，利用构造体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互串联，就形成了链表。
个中 DATA 为自定义的数据类型，NEXT 为指向下一个链表结点的指针，通过访问 NEXT，可以勾引我们去访问链表的下一个结点。
对付持续串的结点而言，就形成了链表如下图：
上文所说的插入删除操作只须要修正指针所指向的区域就可以了，不须要进行大量的数据移动操作。如下图：
比较起数组，链表办理了数组未便利移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存捐躯换来的这些功能的实现。
链表概述
包含单链表，双链表，循环单链表，实际运用中的功能不同，但实现办法都差不多。
单链表就像是美国男篮，一代一代往下传；
双链表像是中国男足，你传球给我，我传球给你，终极传给了守门员；
循环链表就像是中国男篮，火炬从姚明传给王治郅，王治郅传给易建联，现在易建联伤了，又传给了姚明。
单链表
单链表观点和大略的设计单链表是一种链式存取的数据构造，链表中的数据因此结点来表示的，每个结点由元素和指针构成。
元素表示数据元素的映象，便是存储数据的存储单元；指针指示出后继元素存储位置，便是连接每个结点的地址数据。
以结点的序列表示的线性表称作线性链表，也便是单链表，单链表是链式存取的构造。
对付链表的每一个结点，我们利用构造体进行设计，其紧张内容有：
个中，DATA数据元素，可以为你想要储存的任何数据格式，可以是数组，可以是int，乃至可以是构造体（这便是传说中的构造体套构造体）
NEXT为一个指针，其代表了一个可以指向的区域，常日是用来指向下一个结点，链表的尾部NEXT指向（空），由于尾部没有任何可以指向的空间了
故，对付一个单链表的结点定义，可以代码描述成：
//定义结点类型
typedef struct Node {
int data; //数据类型，你可以把int型的data换成任意数据类型，包括构造体struct等复合类型
struct Node next; //单链表的指针域
} Node,LinkedList;
//Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型
链表的初始化初始化紧张完成以下事情：创建一个单链表的前置节点并向后逐步添加节点，一样平常指的是申请结点的空间，同时对一个结点赋空值，其代码可以表示为：
LinkedList listinit{
Node L;
L=(Node)malloc(sizeof(Node)); //开辟空间
if(L==){ //判断是否开辟空间失落败，这一步很有必要
printf(\公众申请空间失落败\"大众);
//exit(0); //开辟空间失落败可以考虑直接结束程序
}
L->next=; //指针指向空
}
把稳：一定要判断是否开辟空间失落败，否则生产中由于未知的情形造成空间开辟失落败，仍旧在连续实行代码，后果将不堪设想啦，因此养成这样的判断是很有必要的。
头插入法创建单链表
利用指针指向下一个结点元素的办法进行逐个创建，利用头插入法终极得到的结果是逆序的。如图所示：
从一个空表开始，天生新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
//头插法建立单链表
LinkedList LinkedListCreatH {
Node L;
L = (Node )malloc(sizeof(Node)); //申请头结点空间
L->next = ; //初始化一个空链表
int x; //x为链表数据域中的数据
while(scanf(\公众%d\"大众,&x) != EOF) {
Node p;
p = (Node )malloc(sizeof(Node)); //申请新的结点
p->data = x; //结点数据域赋值
p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->
L->next = p;
}
return L;
}
尾插入法创建单链表如图所示为尾插入法的创建过程。
头插法天生的链表中，结点的次序和输入数据的顺序不一致。若希望两者次序同等，则须要尾插法。
该方法是将新结点逐个插入到当前链表的表尾上，为此必须增加一个尾指针r, 使其始终指向当前链表的尾结点，代码如下：
//尾插法建立单链表
LinkedList LinkedListCreatT {
Node L;
L = (Node )malloc(sizeof(Node)); //申请头结点空间
L->next = ; //初始化一个空链表
Node r;
r = L; //r始终指向终端结点，开始时指向头结点
int x; //x为链表数据域中的数据
while(scanf(\"大众%d\"大众,&x) != EOF) {
Node p;
p = (Node )malloc(sizeof(Node)); //申请新的结点
p->data = x; //结点数据域赋值
r->next = p; //将结点插入到表头L-->|1|-->|2|-->
r = p;
}
r->next = ;
return L;
}
遍历单链表如打印、修正从链表的头开始，逐步向后进行每一个元素的访问，称为遍历。
对付遍历操作，我们可以衍生出很多常用的数据操作，比如查询元素，修正元素，获取元素个数，打印全体链表数据等等。
进行遍历的思路极其大略，只须要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可，代码如下：
//便利输出单链表
void printList(LinkedList L){
Node p=L->next;
int i=0;
while(p){
printf(\"大众第%d个元素的值为:%d\n\"大众,++i,p->data);
p=p->next;
}
}
对付元素修正操作，以下是代码实现：
//链表内容的修正，在链表中修正值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
Node p=L->next;
int i=0;
while(p){
if(p->data==x){
p->data=k;
}
p=p->next;
}
return L;
}
大略的遍历设计的函数只须要void无参即可，而当涉及到元素操作时，可以设计一个LinkedList类型的函数，使其返回一个操作后的新链表。
插入操作
链表的插入操作紧张分为查找到第i个位置，将该位置的next指针修正为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。
其操作办法可以设置一个先驱结点，利用循环找到第i个位置，再进行插入。
如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：
从原来的链表状态：
到新的链表状态：
代码实现如下：
//单链表的插入，在链表的第i个位置插入x的元素
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
Node pre; //pre为先驱结点
pre = L;
int tempi = 0;
for (tempi = 1; tempi < i; tempi++) {
pre = pre->next; //查找第i个位置的先驱结点
}
Node p; //插入的结点为p
p = (Node )malloc(sizeof(Node));
p->data = x;
p->next = pre->next;
pre->next = p;
return L;
}
删除操作删除元素要建立一个先驱结点和一个当前结点，当找到了我们须要删除的数据时，直策应用先驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数开释掉。如图所示：
代码如下：
//单链表的删除，在链表中删除值为x的元素
LinkedList LinkedListDelete(LinkedList L,int x) {
Node p,pre; //pre为先驱结点，p为查找的结点。
p = L->next;
while(p->data != x) { //查找值为x的元素
pre = p;
p = p->next;
}
pre->next = p->next; //删除操作，将其先驱next指向其后继。
free(p);
return L;
}
双向链表
双向链表的简介以及观点单链表是指结点中只有一个指向其后继的指针，具有单向性，但是有时须要搜索大量数据的时候，就须要多次进行从头开始的遍历，这样的搜索就不是很高效了。
在单链表的根本上，对付每一个结点设计一个先驱结点，先驱结点与前一个结点相互连接，构成一个链表，就产生了双向链表的观点了。
双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接先驱。以是，从双向链表中的任意一个结点开始，都可以很方便地访问它的先驱结点和后继结点。
双向链表示意图
一个完全的双向链表该当是头结点的pre指针指为空，尾结点的next指针指向空，别的结点前后相链。
双向链表的结点设计
对付每一个结点而言，有：
个中，DATA表示数据，其可以是大略的类型也可以是繁芜的构造体；
pre代表的是先驱指针，它总是指向当前结点的前一个结点，如果当前结点是头结点，则pre指针为空；
next代表的是后继指针，它总是指向当前结点的下一个结点，如果当前结点是尾结点，则next指针为空
其代码设计如下：
typedef struct line{
int data; //data
struct line pre; //pre node
struct line next; //next node
}line,a;
//分别表示该结点的先驱(pre)，后继(next)，以及当前数据(data)
双链表的创建
创建双向链表须要先创建头结点，然后逐步的进行添加双向链表的头结点是有数据元素的，也便是头结点的data域中是存有数据的，这与一样平常的单链表是不同的。
对付逐步添加数据，先开辟一段新的内存空间作为新的结点，为这个结点进行的data进行赋值，然后将已成链表的上一个结点的next指针指向自身，自身的pre指针指向上一个结点。
其代码可以设计为：
//创建双链表
line initLine(line head){
int number,pos=1,input_data;
//三个变量分别代表结点数量，当前位置，输入的数据
printf(\"大众请输入创建结点的大小\n\"大众);
scanf(\"大众%d\"大众,&number);
if(number<1){return ;} //输入造孽直接结束
//////头结点创建///////
head=(line)malloc(sizeof(line));
head->pre=;
head->next=;
printf(\公众输入第%d个数据\n\"大众,pos++);
scanf(\公众%d\"大众,&input_data);
head->data=input_data;
line list=head;
while (pos<=number) {
line body=(line)malloc(sizeof(line));
body->pre=;
body->next=;
printf(\公众输入第%d个数据\n\"大众,pos++);
scanf(\公众%d\"大众,&input_data);
body->data=input_data;
list->next=body;
body->pre=list;
list=list->next;
}
return head;
}
双向链表创建的过程可以分为：创建头结点->创建一个新的结点->将头结点和新结点相互链接->再度创建新结点，这样会有助于理解。
双向链表的插入操作
如图所示：
对付每一次的双向链表的插入操作，首先须要创建一个独立的结点，并通过malloc操作开辟相应的空间；
其次我们选中这个新创建的独立节点，将其的pre指针指向所需插入位置的前一个结点；
同时，其所需插入的前一个结点的next指针修正指向为该新的结点，该新的结点的next指针将会指向一个原来的下一个结点，而修正下一个结点的pre指针为指向新结点自身，这样的一个操作我们称之为双向链表的插入操作。
其代码可以表示为：
//插入数据
line insertLine(line head,int data,int add){
//三个参数分别为：进行此操作的双链表，插入的数据，插入的位置
//新建数据域为data的结点
line temp=(line)malloc(sizeof(line));
temp->data=data;
temp->pre=;
temp->next=;
//插入到链表头，要分外考虑
if (add==1) {
temp->next=head;
head->pre=temp;
head=temp;
}else{
line body=head;
//找到要插入位置的前一个结点
for (int i=1; i<add-1; i++) {
body=body->next;
}
//判断条件为真，解释插入位置为链表尾
if (body->next==) {
body->next=temp;
temp->pre=body;
}else{
body->next->pre=temp;
temp->next=body->next;
body->next=temp;
temp->pre=body;
}
}
return head;
}
双向链表的删除操作如图：
删除操作的过程是：选择须要删除的结点->选中这个结点的前一个结点->将前一个结点的next指针指向自己的下一个结点->选中该节点的下一个结点->将下一个结点的pre指针修正指向为自己的上一个结点。
在进行遍历的时候直接将这一个结点给跳过了，之后，我们开释删除结点，归还空间给内存，这样的操作我们称之为双链表的删除操作。
其代码可以表示为：
//删除元素
line deleteLine(line head,int data){
//输入的参数分别为进行此操作的双链表，须要删除的数据
line list=head;
//遍历链表
while (list) {
//判断是否与此元素相等
//删除该点方法为将该结点前一结点的next指向该节点后一结点
//同时将该结点的后一结点的pre指向该节点的前一结点
if (list->data==data) {
list->pre->next=list->next;
list->next->pre=list->pre;
free(list);
printf(\公众--删除成功--\n\"大众);
return head;
}
list=list->next;
}
printf(\公众Error:没有找到该元素，没有产生删除\n\"大众);
return head;
}
双向链表的遍历双向链表的遍历利用next指针逐步向后进行索引即可。
把稳，在判断这里，我们既可以用while(list)的操作直接判断是否链表为空，也可以利用while(list->next)的操作判断该链表是否为空，其下一节点为空和本结点是否为空的判断条件是一样的效果。
其大略的代码可以表示为：
//遍历双链表,同时打印元素数据
void printLine(line head){
line list = head;
int pos=1;
while(list){
printf(\公众第%d个数据是:%d\n\"大众,pos++,list->data);
list=list->next;
}
}
循环链表循环链表观点对付单链表以及双向链表，就像一个小巷，无论怎么走终极都能从一端走到另一端，顾名思义，循环链表则像一个有传送门的小巷，当你以为你走到结尾的时候，实在这便是开头。
循环链表和非循环链表实在创建的过程唯一不同的是，非循环链表的尾结点指向空，而循环链表的尾指针指向的是链表的开头。
通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）
一个完全的循环单链表如图：
循环链表结点设计（以单循环链表为例）
对付循环单链表的结点，可以完备参照于单链表的结点设计，如图：
单向循环链表结点
data表示数据；
next表示指针，它总是指向自身的下一个结点，对付只有一个结点的存在，这个next指针则永久指向自身，对付一个链表的尾部结点，next永久指向开头。
其代码如下：
typedef struct list{
int data;
struct list next;
}list;
//data为存储的数据，next指针为指向下一个结点
循环单链表初始化先创建一个头结点并且给其开辟内存空间，在开辟内存空间成功之后，将头结点的next指向head自身，创建一个init函数来完成；
为了重复创建和插入，我们可以在init函数重新创建的结点next指向空，而在主函数调用创建之后，将head头结点的next指针指向自身。
这样的操作办法可以方便过后的创建单链表，直策应用多次调用的插入函数即可完成整体创建。
其代码如下：
//初始结点
list initlist{
list head=(list)malloc(sizeof(list));
if(head==){
printf(\"大众创建失落败，退出程序\"大众);
exit(0);
}else{
head->next=;
return head;
}
}
在主函数重调用可以是这样：
//////////初始化头结点//////////////
list head=initlist;
head->next=head;
循环链表的创建操作如图所示：
单向循环链表的创建
通过逐步的插入操作，创建一个新的节点，将原有链表尾结点的next指针修正指向到新的结点，新的结点的next指针再重新指向头部结点，然后逐步进行这样的插入操作，终极完玉成部单项循环链表的创建。
其代码如下：
//创建——插入数据
int insert_list(list head){
int data; //插入的数据类型
printf(\"大众请输入要插入的元素：\"大众);
scanf(\"大众%d\"大众,&data);
list node=initlist;
node->data=data;
//初始化一个新的结点，准备进行链接
if(head!=){
list p=head;
//找到末了一个数据
while(p->next!=head){
p=p->next;
}
p->next=node;
node->next=head;
return 1;
}else{
printf(\"大众头结点已无元素\n\公众);
return 0;
}
}
循环单链表的插入操作如图，对付插入数据的操作，可以创建一个独立的结点，通过将须要插入的结点的上一个结点的next指针指向该节点，再由须要插入的结点的next指针指向下一个结点的办法完成插入操作。
其代码如下：
//插入元素
list insert_list(list head,int pos,int data){
//三个参数分别是链表，位置，参数
list node=initlist; //新建结点
list p=head; //p表示新的链表
list t;
t=p;
node->data=data;
if(head!=){
for(int i=1;i<pos;i++){
t=t->next; //走到须要插入的位置处
}
node->next=t->next;
t->next=node;
return p;
}
return p;
}
循环单链表的删除操作如下图所示，循环单链表的删除操作是先找到须要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点即可。
须要把稳的是尾结点，由于删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点须要指向的是头结点而不是空。
其代码如下：
//删除元素
int delete_list(list head) {
if(head == ) {
printf(\"大众链表为空！
\n\公众);
return 0;
}
//建立临时结点存储头结点信息（目的为了找到退出点）
//如果不这么建立的化须要利用一个数据进行计数标记，计数达到链表长度时自动退出
//循环链表当找到末了一个元素的时候会自动指向头元素，这是我们不想让他发生的
list temp = head;
list ptr = head->next;
int del;
printf(\"大众请输入你要删除的元素：\"大众);
scanf(\公众%d\"大众,&del);
while(ptr != head) {
if(ptr->data == del) {
if(ptr->next == head) {
temp->next = head;
free(ptr);
return 1;
}
temp->next = ptr->next; //核心删除操作代码
free(ptr);
//printf(\"大众元素删除成功！
\n\"大众);
return 1;
}
temp = temp->next;
ptr = ptr->next;
}
printf(\"大众没有找到要删除的元素\n\"大众);
return 0;
}
循环单链表的遍历与普通的单链表和双向链表的遍历不同，循环链表须要进行结点的分外判断。
先找到尾节点的位置，由于尾节点的next指针是指向头结点的，以是不能利用链表本身是否为空的方法进行大略的循环判断，我们须要通过判断结点的next指针是否即是头结点的办法进行是否完成循环的判断。
此外还有一种计数的方法，即建立一个计数器count=0，每一次next指针指向下一个结点时计数器+1，当count数字与链表的节点数相同的时候即完成循环；
但是这样做会有一个问题，便是获取到链表的节点数同时，也须要完成一次遍历才可以达成目标。
其代码如下：
//遍历元素
int display(list head) {
if(head != ) {
list p = head;
//遍历头节点到，末了一个数据
while(p->next != head ) {
printf(\"大众%d \"大众,p->next->data);
p = p->next;
}
printf(\"大众\n\"大众); //换行
//把末了一个节点赋新的节点过去
return 1;
} else {
printf(\"大众头结点为空!\n\"大众);
return 0;
}
}
进阶观点——双向循环链表循环单链表也有一个孪生兄弟——双向循环链表，其设计思路与单链表和双向链表的设计思路一样，便是在原有的双向链表的根本上，将尾部结点和头部结点进行相互连接。交给大家了。
关于链表的总结
在顺序表中做插入删除操作时，均匀移动大约表中一半的元素，因此对n较大的顺序表效率低。并且须要预先分配足够大的存储空间，而链表正好是个中利用的精华。
基于存储，运算，环境这几方面考虑，可以让我们更好的在项目中利用链表。
本日链表根本就讲到这里，下一期，我们再见！
点分享
