嵌入式从0到精通——数据结构总结[特殊字符]

📚期末复习 / 课程实验必备！ 学习 C 语言数据结构的时候，很多同学会头疼链表指针、内存管理、各种增删改查逻辑。网上代码片段多，完整带注释工程较少。

本篇把平时写的全套链式数据结构代码整理出来：单向链表、栈、队列、双向链表、哈希表、二叉树。 所有代码保留原始逻辑不动，给每一个函数添加注释，标明功能、参数、返回值，方便调试，也可以直接用于课程实验参考。

包含经典算法：快慢指针、二叉树四种遍历、哈希冲突处理、内核侵入链表实战示例。

注意：需要自行补全.h头文件，代码务必注意malloc之后配套free，避免内存泄漏。

📌说明：

1、link.c 有头单向链表

功能概述：带头部哨兵节点的单向链表。支持头插、尾插、头删、尾删、按值删除、查找、修改、链表销毁；快慢指针算法求中间结点、倒数第 k 个结点。

#include "link.h"
#include <stdlib.h>
#include <stdio.h>
/********************************
* 功能: 创建有头单向链表（哨兵头节点，不存业务数据）
* 参数：无
* 返回值：
*成功：返回头结点地址
*失败: NULL(malloc内存分配失败)
* *****************************/
Link_Node *create_link()
{
Link_Node *phead = NULL;

phead = malloc(sizeof(Link_Node));
if (NULL == phead)
{
printf("fail malloc\\n");
return NULL;
}

phead->pnext = NULL;
return phead;
}
/*************************************************
* 功能：单向链表头部插入新节点
* 参数：
*phead：链表哨兵头结点地址
*data: 需要插入的业务数据
* 返回值：
*成功：0
*失败：-1(malloc失败)
* ***********************************************/
int insert_head_link(Link_Node *phead, Data_Type data)
{
Link_Node *pinsert = malloc(sizeof(Link_Node));
if (NULL == pinsert)
{
printf("fail malloc\\n");
return -1;
}
pinsert->data = data;
pinsert->pnext = NULL;
pinsert->pnext = phead->pnext;
phead->pnext = pinsert;
return 0;
}
/*************************************************
* 功能：遍历链表，打印所有有效节点数据
* 参数：
*phead：链表哨兵头结点地址
* 返回值：无
* ***********************************************/
void link_for_each(Link_Node *phead)
{
Link_Node *p = NULL;
p = phead->pnext;
while (p != NULL)
{
printf("%d ", p->data);
p = p->pnext;
}
printf("\\n");
}
/*************************************************
* 功能：判断单向链表是否为空链表
* 参数：
*phead：链表哨兵头结点地址
* 返回值：
*链表为空：1
*链表非空：0
* ***********************************************/
int is_empty_link(Link_Node *phead)
{
if (NULL == phead->pnext)
{
return 1;
}
return 0;
}
/*************************************************
* 功能：单向链表尾部插入新节点
* 参数：
*phead：链表哨兵头结点地址
*data: 需要插入的业务数据
* 返回值：
*成功：0
*失败：-1(malloc失败)
* ***********************************************/
int insert_tail_link(Link_Node *phead, Data_Type data)
{
Link_Node *p = NULL;
Link_Node *pinsert = malloc(sizeof(Link_Node));
if (NULL == pinsert)
{
printf("fail malloc\\n");
return -1;
}
pinsert->data = data;
pinsert->pnext = NULL;

if (is_empty_link(phead))
{
phead->pnext = pinsert;
}
else
{
p = phead->pnext;
while (p->pnext != NULL)
{
p = p->pnext;
}
p->pnext = pinsert;
}

return 0;
}
/*********************************************
* 功能：删除链表第一个有效节点（删除头后面节点）
* 参数：
*phead：链表哨兵头结点地址
* 返回值：
*成功：0；空链表也返回0
* ********************************************/
int delete_head_link(Link_Node *phead)
{
if (is_empty_link(phead))
{
return 0;
}
Link_Node *pdel = phead->pnext;
phead->pnext = pdel->pnext;
free(pdel);
return 0;
}
/*******************************************
* 功能：删除链表尾有效节点
* 参数：
*phead：链表哨兵头结点地址
* 返回值：成功：0；空链表也返回0
* *****************************************/
int delete_tail_link(Link_Node *phead)
{
Link_Node *p = phead->pnext;
if (is_empty_link(phead))
{
return 0;
}
else if (NULL == p->pnext)
{
delete_head_link(phead);
}
else
{
while (p->pnext->pnext != NULL)
{
p = p->pnext;
}
free(p->pnext);
p->pnext = NULL;
}
return 0;
}
/*************************************************
* 功能：根据data值查找对应节点
* 参数：
*phead：链表哨兵头结点地址
*data：待匹配查找的数据
* 返回值：
*成功：匹配到的节点指针
*失败：NULL(头指针为空 / 没有找到节点)
* ***********************************************/
Link_Node *find_link(Link_Node *phead, Data_Type data)
{
if (NULL == phead)
{
printf("phead is null\\n");
return NULL;
}
Link_Node *p = phead->pnext;
while (p)
{
if (p->data == data)
{
return p;
}
p = p->pnext;
}

return NULL;
}
/*************************************************
* 功能：修改链表指定节点数据
* 参数：
*phead：链表哨兵头结点地址
*olddata：需要被修改的旧数据
*newdata：替换后的新数据
* 返回值：
*成功：0
*失败：-1(头指针空 / 找不到对应节点)
* ***********************************************/
int change_link(Link_Node *phead, Data_Type olddata, Data_Type newdata)
{
if (NULL == phead)
{
printf("phead is null\\n");
return -1;
}

Link_Node *ptmp = find_link(phead, olddata);
if (NULL == ptmp)
{
return -1;
}
ptmp->data = newdata;

return 0;
}
/*************************************************
* 功能：销毁整个链表，释放全部有效节点+哨兵头节点
* 参数：
*phead：链表哨兵头结点地址
* 返回值：无
* ***********************************************/
void destroy_link(Link_Node *phead)
{
if (NULL == phead)
{
printf("phead is null\\n");
return ;
}

while (!is_empty_link(phead))
{
delete_head_link(phead);
}
free(phead);
return ;
}
/*************************************************
* 功能：删除链表中第一个匹配data的节点
* 参数：
*phead：链表哨兵头结点地址
*data：待删除节点的业务数据
* 返回值：
*成功：0
*失败：-1(头指针空 / 找不到对应节点)
* ***********************************************/
int delete_point_node(Link_Node *phead, Data_Type data)
{
if (NULL == phead)
{
printf("phead is null\\n");
return -1;
}

Link_Node *pdel = NULL;
Link_Node *ppre = phead;
while (ppre->pnext != NULL)
{
if (ppre->pnext->data == data)
{
pdel = ppre->pnext;
ppre->pnext = pdel->pnext;
free(pdel);
return 0;
}
ppre = ppre->pnext;
}
return -1;
}
/*************************************************
* 功能：快慢指针算法查找链表中间节点
* 参数：
*phead：链表哨兵头结点地址
* 返回值：
*成功：中间节点指针
*失败：NULL(头空 / 链表为空)
* ***********************************************/
Link_Node * find_mid_node(Link_Node *phead)
{
if (NULL == phead)
{
printf("phead is null\\n");
return NULL;
}

if (is_empty_link(phead))
return NULL;
Link_Node *pfast = phead->pnext;
Link_Node *pslaw = pfast;

while (pfast != NULL)
{
pfast = pfast->pnext;
if (pfast != NULL)
{
pfast = pfast->pnext;
pslaw = pslaw->pnext;
}
}
return pslaw;
}
/*************************************************
* 功能：快慢指针查找链表倒数第K个节点
* 参数：
*phead：链表哨兵头结点地址
*K：倒数第k个节点下标
* 返回值：
*成功：倒数第K个节点指针
*失败：NULL(头空 / 链表空 / K值超出链表长度)
* ***********************************************/
Link_Node *find_last_k_node(Link_Node *phead, int K)
{
if (NULL == phead)
{
printf("phead is null\\n");
return NULL;
}
if (is_empty_link(phead))
{
return NULL;
}

Link_Node *pfast = phead->pnext;
Link_Node *pslow = phead->pnext;
for (int i = 0; i < K; i++)
{
if (NULL == pfast)
{
return NULL;
}
pfast = pfast->pnext;
}
while (pfast != NULL)
{
pfast = pfast->pnext;
pslow = pslow->pnext;
}

return pslow;
}

2、queue.c 链式队列

功能概述：链式实现队列，遵循先进先出 FIFO。队列控制块保存头指针、尾指针、元素计数；支持入队、出队、获取队头元素、清空队列、销毁队列。二叉树层序遍历依赖该队列。

#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
/*************************************************
* 功能：创建链式队列控制块，初始化头尾指针、元素计数
* 参数：无
* 返回值：
*成功：队列控制块指针
*失败：NULL(malloc失败)
* ***********************************************/
Queue *create_queue()
{
Queue *pque = malloc(sizeof(Queue));
if (NULL == pque)
{
printf("fail malloc\\n");
return NULL;
}
pque->phead = NULL;
pque->ptail = NULL;
pque->clen = 0;
return pque;
}
/*************************************************
* 功能：判断队列是否为空
* 参数：
*pque：队列控制块指针
* 返回值：
*队列为空：1
*队列非空：0
* ***********************************************/
int is_empty_queue(Queue *pque)
{
return NULL == pque->phead;
}
/*************************************************
* 功能：入队操作，在队尾新增节点
* 参数：
*pque：队列控制块指针
*data：待入队数据
* 返回值：
*成功：0
*失败：-1(队列指针为空 / malloc失败)
* ***********************************************/
int push_queue(Queue *pque, Data_Type data)
{
if (NULL == pque)
return -1;

Que_Node *pnode = malloc(sizeof(Que_Node));
if (NULL == pnode)
{
printf("fail malloc\\n");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;
if (is_empty_queue(pque))
{
pque->phead = pnode;
pque->ptail = pnode;
}
else
{
pque->ptail->pnext = pnode;
pque->ptail = pnode;
}
pque->clen++;
return 0;
}
/*************************************************
* 功能：出队操作，删除队头节点
* 参数：
*pque：队列控制块指针
*pdata：输出参数，保存出队数据，可以传入NULL不需要接收数据
* 返回值：
*成功：0
*失败：-1(队列为空 / 队列指针为空)
* ***********************************************/
int pop_queue(Queue *pque, Data_Type *pdata)
{
if (NULL == pque)
return -1;

if (is_empty_queue(pque))
return -1;

Que_Node *pdel = pque->phead;
pque->phead = pdel->pnext;
if (NULL == pque->phead)
{
pque->ptail = NULL;
}
if (pdata != NULL)
{
*pdata = pdel->data;
}
free(pdel);
pque->clen–;
return 0;
}
/*************************************************
* 功能：清空队列所有业务节点，不销毁队列控制块
* 参数：
*pque：队列控制块指针
* 返回值：无
* ***********************************************/
void clear_queue(Queue *pque)
{
if (NULL == pque)
return ;

while (!is_empty_queue(pque))
pop_queue(pque, NULL);
}
/*************************************************
* 功能：获取队头元素，不删除节点
* 参数：
*pque：队列控制块指针
*pdata：输出参数，接收队头数据
* 返回值：
*成功：0
*失败：-1(队列为空 / 队列指针为空)
* ***********************************************/
int get_queue_head(Queue *pque, Data_Type *pdata)
{

if (NULL == pque)
return -1;
if (is_empty_queue(pque))
return -1;

if (pdata != NULL)
{
*pdata = pque->phead->data;
}
return 0;
}
/*************************************************
* 功能：销毁整个队列，释放全部业务节点+队列控制块内存
* 参数：
*pque：队列控制块指针
* 返回值：无
* ***********************************************/
void destroy_queue(Queue *pque)
{
if (NULL == pque)
return;
clear_queue(pque);
free(pque);
}
/*************************************************
* 功能：遍历打印队列全部元素
* 参数：
*pque：队列控制块指针
* 返回值：无
* ***********************************************/
void queue_for_each(Queue *pque)
{
if (NULL == pque)
return ;

Que_Node *p = pque->phead;
while (p)
{
printf("%d ", p->data);
p = p->pnext;
}
printf("\\n");
}

3、stack.c 链式栈

功能概述：链式栈，遵循后进先出 LIFO；所有操作都在栈顶完成。支持入栈、出栈、获取栈顶、清空栈、销毁栈。

#include "stack.h"
#include <stdio.h>
#include <stdlib.h>
/*************************************************
* 功能：创建链式栈控制块，初始化栈顶指针、元素计数
* 参数：无
* 返回值：
*成功：栈控制块指针
*失败：NULL(malloc失败)
* ***********************************************/
Stack *create_stack()
{
Stack *pstack = malloc(sizeof(Stack));
if (NULL == pstack)
{
printf("fail malloc");
return NULL;
}
pstack->ptop = NULL;
pstack->clen= 0;
return pstack;
}
/*************************************************
* 功能：入栈，栈顶位置插入新节点
* 参数：
*pstack：栈控制块指针
*data：待入栈业务数据
* 返回值：
*成功：0
*失败：-1(栈指针为空 / malloc失败)
* ***********************************************/
int push_stack(Stack *pstack, Data_Type data)
{
if (NULL == pstack)
{
printf("pstack is null\\n");
return -1;
}

Stack_Node *pnode = malloc(sizeof(Stack_Node));
if (NULL == pnode)
{
printf("malloc fail\\n");
return -1;
}
pnode->data = data;
pnode->pnext = pstack->ptop;
pstack->ptop = pnode;
pstack->clen++;
return 0;
}
/*************************************************
* 功能：遍历打印栈，从栈顶向栈底输出
* 参数：
*pstack：栈控制块指针
* 返回值：无
* ***********************************************/
void stack_for_each(Stack *pstack)
{
if (NULL == pstack)
{
printf("pstack is null\\n");
return ;
}
Stack_Node *p = pstack->ptop;
while (p != NULL)
{
printf("%d ", p->data);
p = p->pnext;
}
printf("\\n");
}
/*************************************************
* 功能：判断栈是否为空
* 参数：
*pstack：栈控制块指针
* 返回值：
*栈为空：1
*栈非空：0
* ***********************************************/
int is_empty_stack(Stack *pstack)
{
return NULL == pstack->ptop;
}
/*************************************************
* 功能：出栈，删除栈顶节点
* 参数：
*pstack：栈控制块指针
*pdata：输出参数，接收出栈数据，可以传NULL
* 返回值：
*成功：0
*失败：-1(栈空 / 栈指针为空)
* ***********************************************/
int pop_stack(Stack *pstack, Data_Type *pdata)
{
if (NULL == pstack)
{
printf("pstack is null\\n");
return -1;
}

if (is_empty_stack(pstack))
return -1;
Stack_Node *pdel = pstack->ptop;
pstack->ptop = pdel->pnext;
if (pdata != NULL)
{
*pdata = pdel->data;
}
free(pdel);
pstack->clen–;
return 0;
}
/*************************************************
* 功能：获取栈顶数据，不弹出节点
* 参数：
*pstack：栈控制块指针
*pdata：输出参数，接收栈顶数据
* 返回值：
*成功：0
*失败：-1(栈空 / 栈指针为空)
* ***********************************************/
int get_stack_top(Stack *pstack, Data_Type *pdata)
{
if (NULL == pstack)
{
printf("pstack is null\\n");
return -1;
}
if (is_empty_stack(pstack))
return -1;
if (pdata != NULL)
{
*pdata = pstack->ptop->data;
}
return 0;
}
/*************************************************
* 功能：清空栈所有业务节点，不销毁栈控制块
* 参数：
*pstack：栈控制块指针
* 返回值：无
* ***********************************************/
void clear_stack(Stack *pstack)
{
if (NULL == pstack)
{
printf("pstack is null\\n");
return ;
}
while (!is_empty_stack(pstack))
pop_stack(pstack, NULL);
}
/*************************************************
* 功能：销毁整个栈，释放业务节点+栈控制块
* 参数：
*pstack：栈控制块指针
* 返回值：无
* ***********************************************/
void destroy_stack(Stack *pstack)
{
if (NULL == pstack)
{
printf("pstack is null\\n");
return ;
}
clear_stack(pstack);
free(pstack);
}

4、doulink.h 带头双向链表头文件

功能概述：带头双向链表，每个节点拥有前驱ppre、后继pnext指针；头文件只放结构体定义与函数声明。

#ifndef __DOULINK_H__
#define __DOULINK_H__
//双向链表存储业务数据结构体
typedef struct stu
{
int id;
char name[32];
int score;
}Data_Type;
//双向链表结点类型
typedef struct node
{
Data_Type data; //数据域
struct node *ppre; //前驱指针域
struct node *pnext; //后继指针域
}Dou_Node;

/**
* @brief 创建有头双向链表头节点
* @return 成功返回头节点指针；失败返回NULL
*/
extern Dou_Node *create_doulink();

/**
* @brief 双向链表头部插入节点
* @param phead 双向链表哨兵头节点
* @param data 待插入业务数据
* @return 成功0，失败-1
*/
extern int insert_head_doulink(Dou_Node *phead, Data_Type data);

/**
* @brief 双向链表遍历，dir控制正向/反向遍历
* @param phead 双向链表哨兵头节点
* @param dir 遍历方向标识
* @return 无返回值
*/
extern void doulink_for_each(Dou_Node*phead, int dir);

/**
* @brief 双向链表尾部插入节点
* @param phead 双向链表哨兵头节点
* @param data 待插入业务数据
* @return 成功0，失败-1
*/
extern int insert_tail_doulink(Dou_Node *phead, Data_Type data);

/**
* @brief 删除双向链表头部有效节点
* @param phead 双向链表哨兵头节点
* @return 成功0，失败-1
*/
extern int delete_head_doulink(Dou_Node *phead);

/**
* @brief 删除双向链表尾部有效节点
* @param phead 双向链表哨兵头节点
* @return 成功0，失败-1
*/
extern int delete_tail_doulink(Dou_Node *phead);

/**
* @brief 根据名字查找双向链表节点
* @param phead 双向链表哨兵头节点
* @param name 待查找名字字符串
* @return 找到返回节点指针；找不到返回NULL
*/
extern Dou_Node *find_doulink(Dou_Node *phead, char *name);

/**
* @brief 销毁双向链表全部节点内存
* @param phead 双向链表哨兵头节点
* @return 无返回值
*/
extern void destroy_doulink(Dou_Node *phead);
#endif

5、hash.c 拉链法哈希表

功能概述：采用拉链法解决哈希冲突；哈希函数取名字首字母映射数组下标；链表头插法插入元素；实现插入、遍历、查找、销毁哈希表。

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*************************************************
* @brief 哈希映射函数，字符转换哈希表数组下标
* @param key 输入字符，一般取姓名首字母
* @return 哈希数组下标
* @note 大小写a‑z/A‑Z映射0‑25；其他字符映射哈希表最后一个位置
* ***********************************************/
int hash_function(char key)
{
if (key >= 'a' && key <= 'z')
{
return key-'a';
}
else if (key >= 'A' && key <= 'Z')
{
return key-'A';
}
else
{
return HASH_MAX_SIZE-1;
}
}
/*************************************************
* @brief 拉链哈希表头插法插入一条数据
* @param hash_table 哈希表指针数组
* @param data 待插入业务数据
* @return 成功0；失败‑1(malloc失败)
* ***********************************************/
int insert_hash_table(Hash_Node **hash_table, Data_Type data)
{
int addr = hash_function(data.name[0]);
Hash_Node *pnode = malloc(sizeof(Hash_Node));
if (NULL == pnode)
{
printf("fail malloc\\n");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;

pnode->pnext = hash_table[addr];
hash_table[addr] = pnode;
return 0;
}
/*************************************************
* @brief 完整遍历哈希表输出全部存储元素
* @param hash_table 哈希表指针数组
* @return 无返回值
* ***********************************************/
void hash_for_each(Hash_Node **hash_table)
{
Hash_Node *p = NULL;
for (int i = 0; i < HASH_MAX_SIZE; i++)
{
p = hash_table[i];
while (p)
{
printf("%s:%s\\n", p->data.name, p->data.tel);
p = p->pnext;
}
printf("\\n");
}
}
/*************************************************
* @brief 根据姓名查找哈希表元素并打印匹配结果
* @param hash_table 哈希表指针数组
* @param name 待查找姓名
* @return 固定返回0
* ***********************************************/
int find_hash_table(Hash_Node **hash_table, char *name)
{
int addr = hash_function(name[0]);

Hash_Node *p = hash_table[addr];
while (p)
{
if (0 == strncmp(p->data.name, name, strlen(name)))
{
printf("%s:%s\\n", p->data.name, p->data.tel);
}
p = p->pnext;
}
return 0;
}
/*************************************************
* @brief 销毁哈希表所有链表节点内存
* @param hash_table 哈希表指针数组
* @return 无返回值
* ***********************************************/
void destroy_hash_table(Hash_Node **hash_table)
{
Hash_Node *pdel = NULL;
for (int i = 0; i < HASH_MAX_SIZE; i++)
{
while (hash_table[i] != NULL)
{
pdel = hash_table[i];
hash_table[i] = pdel -> pnext;
free(pdel);
}
}
}

6、tree.c 二叉树

功能概述：二叉树，使用先序序列化字符串（#代表空节点）递归构建二叉树；实现先序、中序、后序递归遍历；统计节点总数、求树深度；队列实现层序（广度）遍历；后序递归销毁整棵树。

#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
//二叉树先序序列化字符串，#代表空节点
char tree[] = "ABE#C##FM###DG##HI###";
int idx = 0;
/*************************************************
* @brief 根据先序序列化字符串递归创建二叉树
* @return 树根节点指针；失败返回NULL
* @note 全局变量tree读取字符串；idx记录当前读取位置；#代表空节点返回NULL
* ***********************************************/
Tree_Node *create_bin_tree()
{
BTData_Type mydata = tree[idx++];
if ('#' == mydata)
{
return NULL;
}
Tree_Node *pnode = malloc(sizeof(Tree_Node));
if (NULL == pnode)
{
printf("fail malloc\\n");
return NULL;
}
pnode->data = mydata;
pnode->pl = create_bin_tree();
pnode->pr = create_bin_tree();
return pnode;
}
/*************************************************
* @brief 二叉树先序遍历：根 → 左子树 → 右子树
* @param proot 二叉树根节点指针
* @return 无返回值
* ***********************************************/
void pre_order(Tree_Node *proot)
{
if (NULL == proot)
return ;
printf("%c", proot->data);
pre_order(proot->pl);
pre_order(proot->pr);
}
/*************************************************
* @brief 二叉树中序遍历：左子树 → 根 → 右子树
* @param proot 二叉树根节点指针
* @return 无返回值
* ***********************************************/
void mid_order(Tree_Node *proot)
{
if (NULL == proot)
return ;
mid_order(proot->pl);
printf("%c", proot->data);
mid_order(proot->pr);
}
/*************************************************
* @brief 二叉树后序遍历：左子树 → 右子树 → 根
* @param proot 二叉树根节点指针
* @return 无返回值
* ***********************************************/
void pos_order(Tree_Node *proot)
{
if (NULL == proot)
return;
pos_order(proot->pl);
pos_order(proot->pr);
printf("%c", proot->data);
}
/*************************************************
* @brief 统计二叉树总节点数量
* @param proot 二叉树根节点指针
* @return 节点个数；空树返回0
* ***********************************************/
int get_tree_node_cnt(Tree_Node *proot)
{
if (NULL == proot)
return 0;
return 1+get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr);
}
/*************************************************
* @brief 获取二叉树深度（树层数）
* @param proot 二叉树根节点指针
* @return 树深度；空树返回0
* ***********************************************/
int get_tree_layer_cnt(Tree_Node *proot)
{
if (NULL == proot)
return 0;
int cntl = get_tree_layer_cnt(proot->pl);
int cntr = get_tree_layer_cnt(proot->pr);

return cntl > cntr ? cntl+1 : cntr+1;
}
/*************************************************
* @brief 后序递归销毁二叉树所有节点内存
* @param proot 二叉树根节点指针
* @return 无返回值
* ***********************************************/
void destroy_tree(Tree_Node *proot)
{
if (NULL == proot)
return;
destroy_tree(proot->pl);
destroy_tree(proot->pr);
free(proot);
}
/*************************************************
* @brief 二叉树层序遍历（广度优先BFS），依赖队列实现
* @param proot 二叉树根节点指针
* @return 无返回值
* ***********************************************/
void layer_order(Tree_Node *proot)
{
if (NULL == proot)
return;

Queue *pque = create_queue();
if (NULL == pque)
return;
Data_Type outdata;
push_queue(pque, proot);
while (!is_empty_queue(pque))
{
pop_queue(pque, &outdata);
printf("%c",outdata->data);
if (outdata->pl != NULL)
{
push_queue(pque, outdata->pl);
}
if (outdata->pr != NULL)
{
push_queue(pque, outdata->pr);
}

}
destroy_queue(pque);
}

📝知识点总结

一、单向链表 link.c

• 带哨兵头节点；头插 O (1)、尾插 O (n)；
• 经典算法：快慢指针求中间节点、快慢指针求倒数第 K 节点；
• 内存管理：销毁必须释放头节点 + 全部业务节点。

二、链式栈 stack.c

• LIFO 后进先出；全部操作在栈顶；
• 入栈头插，出栈删除头节点。

三、链式队列 queue.c

• FIFO 先进先出；队尾入队，队头出队；维护头、尾指针提升效率；
• 典型应用场景：二叉树层序遍历（BFS 广度优先搜索）。

四、双向链表 doulink.h

• 节点同时保存前驱ppre、后继pnext；找前驱不需要遍历；插入删除注意两个指针都要修改。

五、二叉树 tree.c