学习嵌入式Day21：C语言之双向链表和循环链表

前面我们学完单向链表、单链表排序今天进入双向链表。 单向链表只能向后遍历删除节点时必须从头遍历找到待删节点的前驱效率低。带头双向链表每个节点同时保存前驱prev、后继next指针可以向前、向后双向遍历查找前驱节点 O (1)极大简化删除操作。 最后拓展循环链表、队列的基础概念为后面环形队列做铺垫。统一节点定义typedef int data_t; typedef struct node { data_t data; struct node *next; //后继指针指向下一个节点 struct node *prev; //前驱指针指向上一个节点 }node_t;一、带头双向链表带头存在哨兵头节点 head头节点不存储有效业务数据用来简化空链表、边界节点插入删除的判断。1. 创建双向链表创建哨兵头节点node_t *dlinklist_create(void) { node_t *head malloc(sizeof(node_t)); if (head NULL) { printf(dlinklist_create malloc fail\n); return NULL; } head-next NULL; head-prev NULL; return head; }空链表状态phead-next NULL2. 头插法在头节点后面插入新节点步骤创建新节点填充数据新节点 next 指向原来头节点后面第一个有效节点新节点 prev 指向哨兵头节点头节点 next 指向新节点如果原链表不为空原首节点的 prev 要指向新节点边界坑链表只有一个节点的时候必须处理int dlinklist_insert_head(node_t *phead, data_t data) { if (phead NULL) { return -1; } node_t *pnew malloc(sizeof(node_t)); if (pnew NULL) { return -1; } pnew-data data; pnew-next phead-next; pnew-prev phead; //如果插入前链表不是空修改原第一个节点的prev if (phead-next ! NULL) { phead-next-prev pnew; } phead-next pnew; return 0; }3. 尾插法链表尾部插入节点思路先找到链表最后一个节点再修改指针链接。int dlinklist_insert_tail(node_t *phead, data_t data) { if (phead NULL) { return -1; } node_t *pnew malloc(sizeof(node_t)); if (pnew NULL) { return -1; } pnew-data data; //找到尾节点 node_t *p phead; while (p-next ! NULL) { p p-next; } pnew-next p-next; pnew-prev p; p-next pnew; return 0; }4. 遍历打印支持正向 / 反向打印dir1从头往后正向打印dir0从尾向前反向打印int dlinklist_dir_print(node_t *phead, data_t dir) { if (phead NULL || is_empty(phead) 1) { return -1; } node_t *p phead-next; if (dir 0) { //正向打印 while (p!NULL) { printf(%d ,p-data); p p-next; } putchar(\n); }else if(dir 1) { //反向打印先走到尾节点再向前遍历 while (p-next ! NULL) { p p-next; } while (p ! phead) { printf(%d ,p-data); p p-prev; } putchar(\n); } return 0; }5. 查找节点按值查找从头遍历匹配 data返回节点地址找不到返回 NULLnode_t *dlinklist_find_key(node_t *phead, data_t key) { if (phead NULL || is_empty(phead) 1) { return NULL; } node_t *p phead; while (p ! NULL) { if (p-data key) { return p;//找到返回节点地址 } p p-next; } return NULL; }6.更新链表值从头遍历匹配old更新成new。node_t *dlinklist_update(node_t *phead, data_t old, data_t new) { if (phead NULL || is_empty(phead) 1) { return NULL; } node_t *p phead-next; while (p ! NULL) { if (p-data old) { p-data new; return p; } p p-next; } return NULL; }7. 删除操作头删、尾删、按关键字删除头删删除第一个有效节点int dlinklist_delete_head(node_t *phead) { if (phead NULL) { return -1; } node_t *p phead-next; phead-next p-next; if (p-next ! NULL) { p-next-prev phead; }else//只剩一个节点 { phead-prev NULL;//变成空链表 } free(p); p NULL; return 0; }尾删删除最后一个节点int dlinklist_delete_tail(node_t *phead) { if (phead NULL) { return -1; } //找到尾节点 node_t *p phead; while (p-next ! NULL) { p p-next; } p-prev-next NULL; free(p); p NULL; return 0; }按关键字删除删除指定值的节点int dlinklist_delete_key(node_t *phead, data_t key) { if (phead NULL) { return -1; } node_t *p phead; node_t *q NULL; while (p ! NULL p-data ! key) { p p-next; } if (p NULL) { return -1; } //要删除的值 p-prev-next p-next; if(p-next ! NULL) { p-next-prev p-prev; } free(p); p NULL; return 0; }8. 销毁双向链表释放全部内存int dlinklist_destroy(node_t **pphead) { if (pphead NULL) { return -1; } node_t *p *pphead; node_t *q p; while (p ! NULL) { q p-next; free(p); p q; } //悬空指针 *pphead NULL; return 0; }双向链表小结优点双向遍历支持反向输出链表删除任意节点直接通过prev拿到前驱不需要从头遍历查找前驱效率高缺点每个节点多一个 prev 指针占用更多内存插入、删除操作要维护两组指针指针赋值顺序容易出错容易断链二、循环链表环形链表普通链表尾节点 next 为 NULL循环链表尾节点的 next 指针指向头节点形成闭环。单向循环链表尾节点 -next head双向循环链表尾节点 nexthead头节点 prev 尾节点特点没有严格意义上的链表末尾遍历的时候判断条件不再是p!NULL而是p ! phead适合环形场景循环队列、轮询调度、环形任务调度嵌入式很常用注意循环链表遍历的时候千万不要忘记终止条件否则死循环1. 创建环形链表创建哨兵头节点node_t *clinklist_create(void) { node_t *head malloc(sizeof(node_t)); if (head NULL) { printf(clinklist_create malloc fail\n); return NULL; } head-next head; return head; }2. 头插法在头节点后面插入新节点int clinklist_insert_head(node_t *phead, data_t data) { if (phead NULL) { return -1; } node_t *pnew malloc(sizeof(node_t)); if (pnew NULL) { return -1; } pnew-data data; pnew-next phead-next; phead-next pnew; return 0; }3. 尾插法链表尾部插入节点int clinklist_insert_tail(node_t *phead, data_t data) { if (phead NULL) { return -1; } node_t *pnew malloc(sizeof(node_t)); if (pnew NULL) { return -1; } pnew-data data; node_t *p phead-next; while (p-next ! phead) { p p-next; } p-next pnew; pnew-next phead; return 0; }4. 查找节点按值查找node_t *clinklist_find_key(node_t *phead, data_t key) { if (phead NULL || is_empty(phead) 1) { return NULL; } node_t *p phead-next; while (p ! phead) { if (p-data key) { return p; } p p-next; } return NULL; }5.更新链表值node_t *clinklist_update(node_t *phead, data_t old, data_t new) { if (phead NULL || is_empty(phead) 1) { return NULL; } node_t *p phead-next; while (clinklist_find_key(phead,old) ! NULL) { p clinklist_find_key(phead,old); p-data new; return p; } return NULL; }6. 删除操作头删、尾删、按关键字删除头删删除第一个有效节点int clinklist_delete_head(node_t *phead) { if (phead NULL) { return -1; } //待删除的值 node_t *p phead-next; phead-next p-next; free(p); p NULL; return 0; }尾删删除最后一个节点int clinklist_delete_tail(node_t *phead) { if (phead NULL) { return -1; } node_t *p phead; while (p-next-next ! phead) { p p-next; } node_t *q p-next; p-next phead; free(q); q NULL; return 0; }按关键字删除删除指定值的节点int clinklist_delete_key(node_t *phead, data_t key) { if (phead NULL) { return -1; } node_t *p phead; node_t *q NULL; while (p-next ! phead p-next-data ! key) { p p-next; } if (p-next phead) { return -1; } //待删除的值 q p-next; p-next q-next; free(q); q NULL; return 0; }8. 销毁循环链表释放全部内存int clinklist_destroy(node_t **pphead) { if (pphead NULL) { return -1; } node_t *p (*pphead)-next; node_t *q p-next;//用于循环 while (p ! *pphead) { q p-next; free(p); p q; } free(p); p NULL; printf(destroy succ\n); return 0; }三、队列的基础概念队列先进先出 FIFO的线性表。只允许队尾入队队头出队先进入队列的数据最先拿出来类似排队区分栈是后进先出 LIFO队列先进先出 FIFO。两种实现方式链式队列基于链表实现无容量上限顺序队列 / 环形队列基于数组实现固定大小嵌入式项目高频使用后续学习应用场景消息队列、任务队列、IO 缓冲、串口接收缓冲区。四、总结带头双向链表全套接口创建、头插、尾插、正向 / 反向遍历、查找、头删、尾删、按值删除、销毁。 核心要点操作节点时同时维护prev和next两个指针处理边界空链表、只有单个节点。循环链表尾节点指向头部形成环遍历终止条件不再是判断 NULL适合循环调度场景。队列FIFO 先进先出队尾入队队头出队分为链式队列、环形数组队列嵌入式消息处理大量使用。