距离开启数据结构学习已经过去十九天前面啃完了顺序表的基础逻辑今天正式攻坚单向链表。嵌入式开发里链表的使用场景非常多设备任务管理、数据缓存、串口数据帧缓存都会用到它不用连续内存的特性刚好适配嵌入式 RAM 资源紧张的环境今天先把单向链表的整体结构和核心接口梳理清楚。一、单向链表基础结构单向链表的核心是节点串联每个节点包含数据域和指针域整体结构如下Plain Textphead → data → data → data → data → data → NULLolen pnext pnext pnext pnext pnextphead链表头指针指向链表首节点olen链表当前节点个数长度data节点的数据域存放业务数据pnext节点的指针域指向下一个节点末尾节点的pnext指向NULL代表链表结束和顺序表最大的区别就是链表节点在内存中不需要连续存放依靠指针串联逻辑关系这也是嵌入式场景下灵活管理内存的关键。二、单向链表核心 API 应用接口我把链表的常规操作封装成 7 个标准接口覆盖增删改查全流程也是嵌入式开发中链表驱动的常用设计思路序号接口功能说明1创建链表初始化头节点申请链表头内存设置初始长度为 02链表插入支持头插法、尾插法两种插入方式适配不同业务场景3链表删除支持头删、尾删也可扩展指定节点删除4查找根据关键字遍历链表匹配目标数据节点5修改找到目标节点后更新节点内的 data 数据6遍历从头到尾依次访问每个节点常用于数据打印、批量处理7链表销毁释放所有节点内存避免嵌入式系统内存泄漏思维导图梳理操作逻辑三、代码示例link.h #ifndef __LINK_H__ #define __LINK_H__ typedef struct node { int data; struct node *pnext; }Node_s; typedef struct link { Node_s *phead; int clen; }Link_s; extern Link_s *create_link(); //创造一个单向链条 extern int insert_link_head(Link_s *plink,int data); //从头插入一个结点 extern int insert_link_tail(Link_s *plink,int data); //从尾插入一个结点 extern int delete_link_head(Link_s *plink); //从头删除一个结点 extern int delete_link_tail(Link_s *plink); //从尾删除一个结点 extern int delete_link_k_data(Link_s *plink,int data); //删除在指定数据的结点 extern Node_s *get_only_data(Link_s *plink,int data); //获取指定数据地址并返回 extern Node_s *get_mid_link(Link_s *plink); //获取中间数据地址并返回 //extern void update_data(Node_s *ptmp,int num); // extern int update_data(Link_s *plink,int olddata,int newdata); //指定一个旧数据修改为新数据 extern Node_s *find_last_k_data(Link_s *plink,int k); //获取倒数k位置的数据地址并返回 extern void reverse_link(Link_s *plink); //逆序链条 extern void sort_link(Link_s *plink); //排序链条 extern void show_link(Link_s *plink); //打印链条 extern void destroy_link(Link_s *plink); //释放空间 #endiflink.c #includestdio.h #includestdlib.h #includelink.h Link_s *create_link() { Link_s *plinkmalloc(sizeof(Link_s)); if(plinkNULL) { printf(malloc error\n); } plink-pheadNULL; plink-clen0; return plink; } int is_empty_link(Link_s *plink) { if(plink-pheadNULL) { return 1; } return 0; } int insert_link_head(Link_s *plink,int data) { Node_s *pinsertmalloc(sizeof(Node_s)); if(pinsertNULL) { printf(malloc error\n); return -1; } pinsert-datadata; pinsert-pnextNULL; pinsert-pnextplink-phead; plink-pheadpinsert; plink-clen; return 0; } int insert_link_tail(Link_s *plink,int data) { Node_s *pinsertmalloc(sizeof(Node_s)); if(pinsertNULL) { printf(malloc error\n); return -1; } pinsert-datadata; pinsert-pnextNULL; if(is_empty_link(plink)) { plink-pheadpinsert; } else { Node_s *ptmpplink-phead; while(ptmp-pnext!NULL) { ptmpptmp-pnext; } ptmp-pnextpinsert; } plink-clen; return 0; } int delete_link_head(Link_s *plink) { Node_s *pfreeplink-phead; if(!is_empty_link(plink)) { plink-pheadpfree-pnext; free(pfree); plink-clen--; return 0; } else { return -1; } } int delete_link_tail(Link_s *plink) { Node_s *pfreeplink-phead; if(is_empty_link(plink)) { return -1; } else if(pfree-pnextNULL) { delete_link_head(plink); } else { while(pfree-pnext-pnext!NULL) { pfreepfree-pnext; } free(pfree-pnext); pfree-pnextNULL; plink-clen--; } return 0; } int delete_link_k_data(Link_s *plink,int data) { Node_s *ptmpplink-phead; Node_s *ppreptmp; while (plink-phead!NULL) { if(dataplink-phead-data) { delete_link_head(plink); return 0; } else { ppreptmp; ptmpptmp-pnext; if(dataptmp-dataNULL!ptmp-pnext) { ppre-pnextptmp-pnext; free(ptmp); plink-clen--; return 0; } else if(dataptmp-dataNULLptmp-pnext) { delete_link_tail(plink); plink-clen--; return 0; } } } return -1; } Node_s *get_only_data(Link_s *plink,int data) { Node_s *ptmpplink-phead; if(!is_empty_link(plink)) { while(ptmp) { if(ptmp-datadata) { return ptmp; ptmpptmp-pnext; } ptmpptmp-pnext; } } return NULL; } /*Node_s *get_mid_link(Link_s *plink) { Node_s *ptmpplink-phead; if(plink!NULL) { for(int i1;iplink-clen/2;i) { ptmpptmp-pnext; } return ptmp; } return NULL; }*/ Node_s *get_mid_link(Link_s *plink) { Node_s *pfastplink-phead; Node_s *pslowpfast; while(pfast!NULL) { pfastpfast-pnext; if(NULLpfast) { break; } pfastpfast-pnext; pslowpslow-pnext; } return pslow; } /*void update_data(Node_s *ptmp,int num) { ptmp-datanum; }*/ int update_data(Link_s *plink,int olddata,int newdata) { Node_s *ptmpNULL; ptmpget_only_data(plink,olddata); if(NULL!ptmp) { ptmp-datanewdata; return 0; } return 1; } Node_s *find_last_k_data(Link_s *plink,int k) { Node_s *pfastplink-phead; Node_s *pslowpfast; for(int i0;ik;i) { if(NULLpfast) { return NULL; } pfastpfast-pnext; } while(pfast!NULL) { pfastpfast-pnext; pslowpslow-pnext; } return pslow; } void show_link(Link_s *plink) { Node_s *ptmpplink-phead; int a0; while(ptmp!NULL) { printf(%d ,ptmp-data); ptmpptmp-pnext; } printf(\n); } void reverse_link(Link_s *plink) { if(is_empty_link(plink)||NULLplink-phead-pnext) { return; } Node_s *ptmpplink-phead-pnext; Node_s *pinsertNULL; plink-phead-pnextNULL; while(ptmp! while(ptmp!NULL) { pinsertptmp; ptmpptmp-pnext; pinsert-pnextplink-phead; plink-pheadpinsert; } } void sort_link(Link_s *plink) { if(is_empty_link(plink)||NULLplink-phead-pnext) { return; } Node_s *ptmpplink-phead-pnext; Node_s *pinsertNULL; Node_s *pNULL; plink-phead-pnextNULL; while(NULL!ptmp) { pinsertptmp; ptmpptmp-pnext; if(pinsert-dataplink-phead-data) { pinsert-pnextplink-phead; plink-pheadpinsert; } else { pplink-phead; while(p-pnext!NULLpinsert-datap-pnext-data) { pp-pnext; } pinsert-pnextp-pnext; p-pnextpinsert; } } } void destroy_link(Link_s *plink) { while (!is_empty_link(plink)) { delete_link_head(plink); } free(plink); NULL) }四、今日学习思考嵌入式 C 语言开发里手写链表是必备技能。顺序表访问快但插入删除低效链表牺牲了随机访问效率换来了灵活的内存分配和高效的节点增删。今天先把接口框架确定下来接下来的任务就是用 C 语言逐个实现这些 API重点处理边界条件空链表判断、只有一个节点的删插操作、内存申请失败的容错处理避免嵌入式程序跑飞、内存泄露这类问题。后续会基于这套接口写一个简单的串口数据缓存链表 demo把理论落地到嵌入式实际场景里。