1-1 C语言链表

目录

目录

1.0 定义

2.0 为什么使用链表

3.0 链表原理

4.0 创建链表节点

5.0 链表原理续

6.0 链表实现

6.0.1 创建节点

6.0.2 初始化链表

6.0.3 添加链表节点

6.0.4 循环遍历

6.0.5 插入节点

6.0.6 插入头结点main函数

7.0 完整代码

8.0 节点添加方案二

8.0.1 循环遍历关键点

8.0.2 添加节点的关键

9.0 遍历链表节点

10.0 程序实现

10.0.1 创建链表节点

10.0.2 初始化链表

10.0.3 模拟节点数据

10.0.4 添加节点

10.0.5 打印节点

10.0.6 main函数部分

---

1.0 定义

---

链表是由一系列节点组成，每个节点包含数据域和指针域，线性表的顺序存储用一块连续的内存空间，线性表的链式存储有一块不连续的存储空间。

---

---

2.0 为什么使用链表

---

智能网关需要具备动态管理子设备的功能，注册、添加、删除、获取数据等等，如何设计网关软件的数据结构，管理所有的子设备，假如使用TempHumisensor结构体表示单点子设备的数据:

如果使用数组进行管理存在一个问题，元素数量如何定义，不同环境部署的子设备数量是有差异的，太大会浪费内存太小会导致子设备数量受限，需要找到一种按需分配的方案，我们首先会想到指针和动态内存:

各子设备对应的动态内存不像数组，内存布局是不连续的，所以需要找到一种方案能将这些动态内存串联起来，这就要用到链表数据结构了。

---

3.0 链表原理

---

第一个链表节点保存的是第二个节点的地址，第二个节点保存的是第三个节点的地址，第三个节点保存的是下一个节点的地址。

---

4.0 创建链表节点

---

/*** @brief       创建链表节点* @param id    链表id编号* @param humi  温度数据* @param temp  湿度数据* */
typedef struct LINKNODE
{uint8_t id;uint8_t humi;uint8_t temp;struct LINKNODE *next;
} LinkNode_t;

---

注：为什么结构体中能嵌套自己，编译不会报错吗? 如果成员是struct TempHumiListNode next;会报错，因为编译器在解析这个成员时，结构体还没结束，不知道该为它分配多大内存空间;如果是*next，因为是指针类型，对于ARM 32平台，编译器会固定分配4个字节内存空间，用于保存下个子设备对应的动态内存首地址。

---

5.0 链表原理续

---

现在能将动态内存的数据串联起来了，但是还不够，需要设计一个“火车头”，火车头不需要对应实际的子设备，火车厢对应实际子设备，保存设备数据。

注：链表的火车头称之为头节点，火车厢叫做“节点”

“头节点”和“节点”只是动态内存块，在程序中还需要一个变量来保存头节点的首地址，这个变量就叫做“头指针”，准确的说应该是“头指针变量”,这样通过这个头指针就可以访问头节点数据，再通过头节点的next成员访问后面的节点:

---

6.0 链表实现

以下是实现链表的步骤：

1.0 链表初始化(创建头结点);
2.0 添加节点，当检测到新子设备时，添加到链表尾部;
3.0 遍历链表节点:
4.0 删除节点，当检测到子设备下线时，从链表中删除，

---

6.0.1 创建节点

---

typedef struct LINKNODE
{uint8_t id;uint8_t humi;uint8_t temp;struct LINKNODE *next;
} LinkNode_t;

注：节点中包含数据域和指针域，数据域包括id， humi， temp，指针域就是*next保存下一个节点的地址。

---

6.0.2 初始化链表

注：该操作的作用是创建头节点，用一个指针保存头节点的地址，方便头节点去访问后面的节点

LinkNode_t *InitLinkList(void)
{LinkNode_t *header = (LinkNode_t *)malloc(sizeof(LinkNode_t));if (header == NULL){return;}else{header->id = 0;header->next = NULL;return header;}
}

---

6.0.3 添加链表节点

---

出现新节点时，追加到链表的尾部,添加节点，尾节点的特点是NEXT成员保存的地址值为NULL

定义一个局部变量TempHumiListNode *current，从头节点开始循环遍历节点: 

// 定义局部变量TempHumiListNode *current
LinkNode_t *current = header;
while (current->next != NULL)
{current = current->next;
}

添加节点

初始化赋值，TempHumiListNode *current = header，header==400，所以赋值以后current保存了地址400:

---

6.0.4 循环遍历

---

遍历链表节点，使得current从一个节点指向下一个节点，

循环边界，条件表达式:目标是找到next成员保存地址值为NULL的节点

---

遍历链表节点，使得current从一个节点指向下一个节点:要想current指向节点1，只需要将40C地址值赋值给current，这个地址值是保存在前向节点的next成员中，所以使用current->next可以获得40C地址值，接下来将它赋值给current就可以:current = current->next;

循环边界，条件表达式
目标是找到成员next保存地址值是NULL的节点就结束，所以循环条件表达式设计为

while (current->next != NULL)。

---

 添加到新节点到链表尾部:current->next= node; node->next =NULL;

---

/*** @brief  模拟节点数据* @param  无参数* @return LinkNode_t**/
LinkNode_t *Search_LinkList_Data(void)
{LinkNode_t *node = (LinkNode_t *)malloc(sizeof(LinkNode_t));if (node == NULL){return NULL;}else{static uint8_t id = 100;id--;node->humi = 40;node->temp = 20.5f;return node;}
}

---

6.0.5 插入节点

static LinkNode_t *g_header;// 插入一个节点node
void Add_LinkList_Data(LinkNode_t *header, LinkNode_t *node)
{LinkNode_t *current = header;if (current->next != NULL){current = current->next;}current->next = node;node->next = NULL;
}

---

6.0.6 插入头结点main函数

int main(void)
{g_header = InitLinkList();if (g_header == NULL){return -1;}LinkNode_t *node;for (uint8_t i = 0; i < 3; i++){node = Search_LinkList_Data();if (node == NULL){continue;}Add_LinkList_Data(g_header, node);}return 0;
}

---

7.0 完整代码

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>/*** @brief       创建链表节点* @param id    链表id编号* @param humi  温度数据* @param temp  湿度数据**/
typedef struct LINKNODE
{uint8_t id;uint8_t humi;uint8_t temp;struct LINKNODE *next;
} LinkNode_t;/*** @brief  初始化链表* @param  无参数* @return LinkNode_t**/
LinkNode_t *InitLinkList(void)
{LinkNode_t *header = (LinkNode_t *)malloc(sizeof(LinkNode_t));if (header == NULL){return NULL;}else{header->id = 0;header->next = NULL;return header;}
}/*** @brief  模拟节点数据* @param  无参数* @return LinkNode_t**/
LinkNode_t *Search_LinkList_Data(void)
{LinkNode_t *node = (LinkNode_t *)malloc(sizeof(LinkNode_t));if (node == NULL){return NULL;}else{static uint8_t id = 100;id--;node->humi = 40;node->temp = 20.5f;return node;}
}static LinkNode_t *g_header;// 插入一个节点node
void Add_LinkList_Data(LinkNode_t *header, LinkNode_t *node)
{LinkNode_t *current = header;if (current->next != NULL){current = current->next;}current->next = node;node->next = NULL;
}int main(void)
{g_header = InitLinkList();if (g_header == NULL){return -1;}LinkNode_t *node;for (uint8_t i = 0; i < 3; i++){node = Search_LinkList_Data();if (node == NULL){continue;}Add_LinkList_Data(g_header, node);}return 0;
}

---

8.0 节点添加方案二

---

使用两个指针变量prev和current，prev，一直指向current的前向节点，初始化为：

TempHumiListNode *prev = g_header;TempHumiListNode *current = g_header->next;

---

8.0.1 循环遍历关键点

---

注：以下是使用这种方式的关键点

1： 遍历链表节点，使得prev和current从一个节点指向下一个节点

2： 循环边界，条件表达式:目标是通过prev找到next成员保存地址值为NULL的节点

---

8.0.2 添加节点的关键

步骤一

遍历链表节点，使得prev和current从一个节点指向下一个节点:

要想prev指向下一个节点，也就是current指向的节点，执行:prev=current;

要想current指向不一个节点，执行:current=current->next;

---

步骤二

循环边界，条件表达式;目标是通过prev找到next成员保存地址值为NULL的节点就结束:此时current指向为NULL，所以条件表达式设计为:while(current!= NULL)

---

第三步

添加到新节点到链表尾部

prev->next =node;node->next =NULL;

---

9.0 遍历链表节点

---

注：这样做的目的是打印所有节点的数据

使用一个指针变量current，参照添加节点第2种方案，从节点1开始循环遍历每一个节点，初始化

TempHumiListNode *currentcurrent = g header->next;

循环遍历关键点

遍历链表节点，使得current从一个节点指向下一个节点;

循环边界，条件表达式;目标是通过current遍历完所有节点

---

遍历链表节点，使得current从一个节点指向下一个节点:

要想current指向下一个节点，执行:current=current->next;

---

循环边界

循环边界，条件表达式;目标是通过current遍历完所有节点就结束:

此时current指向为NULL，所以条件表达式设计为:while(current!= NULL)

---

10.0 程序实现

注：以下是基于方案二代码的程序设计与实现，仅供学习参考

10.0.1 创建链表节点

 相当于是链表里面的内存块，就是一个一个的节点，以下是具体的程序代码

// 创建链表节点
typedef struct LINKNODE
{uint8_t id;uint8_t humi;uint8_t temp;struct LINKNODE *next;
} LinkNode_t;

---

10.0.2 初始化链表

实际的初始化链表，表示的是设置链表的头部，也就是上面讲到的火车头，头指针保存的是头节点的地址。

实际代码程序：下面做实际的讲解

// 初始化链表
LinkNode_t *LinkNode_Init(void)
{// 创建结构体指针LinkNode_t *header = (LinkNode_t *)malloc(sizeof(LinkNode_t));if (header == NULL){printf("malloc has give space faild");return NULL;}else{header->id = 0;header->next = NULL;return header;}
}

LinkNode_t *LinkNode_Init(void) 是一个指针函数，函数的返回值是结构体类型，可以使用这个

LinkNode_t *header = (LinkNode_t *)malloc(sizeof(LinkNode_t));这段代码的意思是创建了一个结构体指针变量，给结构体指针变量分配内存地址

这段代码的意思是判断动态内存有没有分配成功，如果header == NULL表示没有分配成功，如果

header != NULL 表示动态内存开辟成功，这个时候else后面的代码就是给第一个内存块，也就是

链表的头部赋初始值，返回的第第一个节点（头节点）的地址。

---

10.0.3 模拟节点数据

注：这段代码的意思是，创建一个指针变量给它分配内存，如果分配失败返回NULL，分配成功写入一些固定的初始化值，返回节点的地址。

---

10.0.4 添加节点

注：这段代码的意思是创建一个添加节点的函数，函数的名字是LinkNode_Add，函数的参数是

(LinkNode_t *header, LinkNode_t *node)，创建两个局部变量分别是：LinkNode_t *prev = header;  LinkNode_t *pCurrent = header->next;用来保存头指针变量的地址和头指针变量下一个节点的地址。

这段代码的意思是，如果当前current指向的节点不是最后一个节点，那么prev和pCurrent分别向后移动一位，然后追加新的节点到链表的尾部，prev->next = node;其中prev保存的是下一个节点的地址，然后下一个节点的地址指向的是MULL。

---

10.0.5 打印节点

 创建打印节点函数，参数是链表，创建一个指针指向头节点的下一个节点，判断内存分配有没有成功，如果没有成功直接返回，如果成工表示有节点，给节点赋值，然后当前的节点指向下一个节点，直到变量完最后一个节点为止。

---

10.0.6 main函数部分

---

  g_header = LinkNode_Init(); 将结构体的地址赋值给全局变量，通过这个变量访问第一个头节点的地址，然后判断内存分配是否成功这个是基本的操作，成功打印节点，创建局部变量node

使用while循环里面嵌套了一个for循环次数是3次，然后给node赋值一个地址也就是节点的数据

判断内存分配是否成功不成功使用continue结束本次循环进入下一次循环，不是直接添加节点，打印输出。

---

.....删除节点......