自学嵌入式Day19：数据结构基础与单链表-北京尧图网络

目录一、数据结构基础概念1. 逻辑结构数据之间的逻辑关系2. 存储结构数据在计算机中的存储方式3. 算法与复杂度二、链表的核心概念1. 链表相关术语2. 链表 vs 数组三、单链表的基本操作C语言实现1. 节点结构定义2. 创建空链表3. 插入操作4. 查找与修改5. 删除操作6. 遍历打印三、单链表的进阶操作1. 找到链表的中间节点快慢指针2. 找到链表的倒数第k个节点双指针3. 判断链表是否有环快慢指针4. 链表的逆序反转一、数据结构基础概念数据结构主要研究数据与数据之间的关系。它分为两个层次1. 逻辑结构数据之间的逻辑关系线性结构一对一。如线性表、栈、队列。树形结构一对多。如树、二叉树。图形结构多对多。如网、图。集合无关系仅仅属于同一个集合。2. 存储结构数据在计算机中的存储方式顺序存储一段连续的空间用数组实现。逻辑相邻物理也相邻。链式存储空间不连续通过指针地址链接。逻辑相邻物理不一定相邻。索引存储建立附加的索引表。散列存储根据关键字计算存储地址哈希表。3. 算法与复杂度算法是对特定问题求解步骤的描述有五个特性有穷性、确定性、可行性、输入、输出。衡量算法好坏的核心指标是时间复杂度和空间复杂度常用大O表示法。例如顺序存储数组随机访问 O(1) O(1)插入/删除 O(n) O(n)。链式存储链表随机访问 O(n) O(n)插入/删除 O(1) O(1)。二、链表的核心概念链表是一种动态地进行存储分配的结构。它不需要预先分配固定大小的空间而是根据需要动态申请。1. 链表相关术语头指针head指向链表中第一个结点的指针是链表的入口。头节点第一个结点前附加的一个结点数据域通常不存放有效数据可放链表长度等指针域指向首节点。引入头节点可以简化插入和删除第一个结点的操作。首节点链表中第一个有效结点。尾节点最后一个结点其指针域为NULL。2. 链表 vs 数组对比项数组顺序存储链表链式存储内存空间连续不连续动态分配随机访问支持下标不支持需遍历插入/删除效率低需移动元素效率高只需改指针空间大小固定动态变化三、单链表的基本操作C语言实现我们以带头节点的单链表为例。1. 节点结构定义typedef struct node { int data; // 数据域 struct node *next; // 指针域 } node_t;2. 创建空链表node_t *linklist_creat(void){ node_t *head malloc(sizeof(node_t)); if(head NULL){ printf(linklist malloc failed); return NULL; } head-next NULL; return head; }3. 插入操作头插法新节点插在头节点之后。常用于链表逆序。尾插法新节点插在尾部。常用于保持插入顺序。//头插 void linklist_insert_head(node_t *phead,data_t data){ if(phead NULL){ printf(head NULL\n); return ; } //创建新节点 node_t *pnew malloc(sizeof(node_t)); if(pnew NULL){ printf(new linklist malloc failed\n); return ; } pnew -data data; //插入 pnew-next phead-next; phead-next pnew; } //尾插 void linklist_insert_rail(node_t *phead,data_t data){ if(phead NULL){ return; } node_t *pnew malloc(sizeof(node_t)); if(pnew NULL){ printf(new linklist malloc failed\n); return ; } node_t *p phead-next; pnew-data data; while(p-next!NULL){ p p-next; } p-next pnew; pnew-next NULL; }4. 查找与修改//查找 node_t *linklist_find_key(node_t *phead,data_t key){ if(phead NULL||is_empty(phead) ){ printf(phead is empty\n); return NULL; } node_t *p phead-next; while(p!NULL){ if(p-data key){ return p; } p p-next; } return NULL; } //修改先找再改 node_t *linklist_update(node_t *phead,data_t old,data_t new){ if(phead NULL||is_empty(phead) ){ printf(phead is empty\n); return NULL; } node_t *p linklist_find_key(phead,old); if(p NULL){ printf(not found %d\n,old); return NULL; } p-data new; return p; }5. 删除操作//从头开始删 void linklist_delete_head(node_t *phead){ if(phead NULL){ printf(head NULL\n); return ; } if(is_empty(phead) 1 ){ printf(phead is empty\n); return ; } node_t *pphead-next; phead-next p-next; free(p); p NULL; } //从结尾开始删 void linklist_delete_tail(node_t *phead){ if(phead NULL){ printf(head NULL\n); return ; } if(is_empty(phead) 1 ){ printf(phead is empty\n); return ; } node_t *pphead; //找尾节点的前一个节点 while(p-next-next!NULL){ p p-next; } free(p-next);//释放当前节点的下一个节点 p-next NULL;//当前节点的地址域设为空 } //删除指定值 void linklist_delete_key(node_t *phead,data_t key){ node_t *q linklist_find_key(phead,key); if(q NULL){ printf(not found\n); return ; } node_t *p phead; while(p-next ! q){ p p-next; } p-next q-next; free(q); q NULL; }6. 遍历打印//遍历打印链表 void linklist_print(node_t *phead){ //判断phead是否为空 //判断是否为空链表 if(phead NULL||is_empty(phead) ){ printf(phead is empty\n); return; } //遍历 node_t *p phead-next; while(p ! NULL){ printf(%d ,p-data); p p-next; } putchar(\n); }三、单链表的进阶操作1. 找到链表的中间节点快慢指针思路快指针一次走两步慢指针一次走一步。快指针走到尾时慢指针正好在中间。node_t *linklist_find_mid(node_t *phead){ if(phead NULL || is_empty(phead) 1){ printf(mid find fail\n); return NULL; } node_t *p phead; node_t *q phead; while(p!NULL p-next!NULL){ p p-next-next; q q-next; } return q; }2. 找到链表的倒数第k个节点双指针思路先让快指针走k步然后快慢指针同时走。快指针走到NULL时慢指针正好在倒数第k个位置。//找倒数第k个值的位置双指针 node_t *linklist_find_behind_key(node_t *phead,int k){ if(pheadNULL||is_empty(phead)){ printf(find fail\n); return NULL; } node_t *p phead; node_t *q phead; while(k){ if(p-next NULL){ printf(have no enough node\n); return NULL; } p p-next; --k; } while(p!NULL){ p p-next; q q-next; } return q; }3. 判断链表是否有环快慢指针思路快指针一次走两步慢指针一次走一步。如果链表有环快慢指针必定相遇。//是否含有环快慢指针 int linklist_is_cirlc(node_t *phead){ if(phead NULL ||is_empty(phead) 1){ return -1; } node_t *p phead; node_t *q phead; while(p!NULL p-next !NULL){ p p-next-next; q q-next; if(pq){ return 1; } } return 0; }4. 链表的逆序反转思路1使用头插法。遍历原链表依次将每个节点插入到新链表的头部。//链表逆序双指针 void linklist_reverse(node_t *phead){ if(phead NULL || is_empty(phead) 1){ return ; } node_t *p phead-next; node_t *q p-next; if(q NULL){ return ; } phead-next NULL; while(p!NULL){ q p-next; p-next phead-next; phead-next p; p q; } }思路2使用三个指针prev、curr、next遍历链表逐个将当前节点的next指针反转最终让头节点指向新的首节点原来的尾节点。//链表逆序三指针 void linklist_reverse_plus(node_t *phead){ if(phead NULL || is_empty(phead) 1){ return ; } node_t *prev NULL; node_t *curr phead-next; if(curr-next NULL){ return ; } while(curr!NULL){ node_t *next curr-next; curr-next prev; prev curr; curr next; } phead-next prev; }对比项思路一头插法思路二三指针法核心操作从原链表取节点头插到新链表直接反转每个节点的 next 指针指针数量2~3 个p, q, head-next3 个prev, curr, next代码直观性较直观但需要理解头插过程更直观直接反映“反转”动作是否改变头节点不改变头节点只改变 head-next不改变头节点只改变 head-next

自学嵌入式Day19：数据结构基础与单链表

相关推荐

员工复用企业品牌内容用什么工具？2026 年品牌内容协作平台选型指南

Go语言与区块链全栈开发课程：从入门到项目实战的完整学习路径

Agent开发：多 Agent 协同系统中的上下文代际隔离，防范旧任期幽灵请求与状态机死锁实践

更多资讯

2串电池组均衡方案：基于MP2642GR-Z与STM32的备用电源设计

PDCurses实战：Windows终端文本界面编程与编译规避指南

Codeforces Round #661 Div.3 D题：贪心拆分子序列，双栈维护交替01串

rpyc远程调用实战：像本地函数一样调用远程Python对象

Scrapy爬虫实战：新片场视频列表数据抓取与MySQL存储

pyGIMLi二维ERT反演实战：从数据加载到参数调优与盲测

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？