当前位置：网站首页>C杂讲 双向循环链表
C杂讲 双向循环链表
2022-07-06 09:04:00 【Bright-SKY】
目录
知识点1【双向循环链表】
知识点2【双向链表的尾部插入】
STU* insert_link(STU *head, STU tmp)
{
//为插入的节点申请空间
STU *pi = (STU *)calloc(1,sizeof(STU));
if(pi == NULL)
{
perror("calloc");
return head;
}
*pi = tmp;
//尾部插入
if(NULL == head)
{
pi->next = pi;
pi->pre = pi;
head = pi;
return head;
}
else
{
head->pre->next = pi;
pi->next = head;
pi->pre = head->pre;
head->pre = pi;
}
return head;
}知识点3【双向链表的遍历】
void printf_link(STU *head)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return;
}
else
{
STU *pb = head;
STU *pr = head->pre;
while(1)
{
if(pb == pr)
{
printf("%d %s %f\n", pb->num, pb->name, pb->score);
break;
}
else
{
printf("%d %s %f\n", pb->num, pb->name, pb->score);
printf("%d %s %f\n", pr->num, pr->name, pr->score);
}
if(pb->next == pr)
break;
pb=pb->next;
pr = pr->pre;
}
}
return;
}知识点3【双向链表查询某个节点】
STU *search_link(STU *head, int num)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return head;
}
else
{
STU *pb = head;
STU *pr = head->pre;
while((pb->num != num) && (pr->num != num))
{
if(pb->next == pr) break;
if(pb == pr) break;
pb = pb->next;
pr = pr->pre;
}
if(pb->num == num)
return pb;
else if(pr->num == num)
return pr;
else
{
printf("未找到相关节点\n");
return NULL;
}
}
return NULL;
}知识点4【双向链表删除指定节点】
STU* delete_link(STU *head, int num)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return head;
}
else
{
STU *pb = head;
STU *pr = head->pre;
while((pb->num != num) && (pr->num != num))
{
if(pb->next == pr) break;
if(pb == pr) break;
pb = pb->next;
pr = pr->pre;
}
if(pb->num == num)
{
if(head == pb)//删除头结点
{
if(pb->next == pb)//链表只有一个节点
{
head = NULL;
}
else//链表不止一个节点
{
head->pre->next = head->next;
head->next->pre = head->pre;
head = head->next;
}
free(pb);
return head;
}
else//删除、中尾部节点
{
pb->pre->next = pb->next;
pb->next->pre = pb->pre;
}
}
else if(pr->num == num)
{
pr->pre->next = pr->next;
pr->next->pre = pr->pre;
}
else
{
printf("未找到相关节点\n");
return NULL;
}
}
return head;
}知识点4【双向链表释放链表节点】
STU* free_link(STU *head)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return head;
}
else
{
STU *pb = head;
head->pre->next = NULL;
while(pb != NULL)
{
head = head->next;
free(pb);
pb = head;
}
}
return head;
}知识点5【Linux内核链表】
list.h
/**
* 简易版双向循环链表（参考Linux内核链表实现方式）
* @auther: BrightSKY
* @function: 未指定数据端，可以挂载各种类型数据，实现了链表任意节点位置的插入和删除，任意节点的替换，提供正向反向的遍历方式
* @extend: 欢迎根据已有API进行功能扩展，可以实现扩展多链表操作，链表检索和排列等算法
*/
#ifndef __LIST_H__
#define __LIST_H__
/**
* 新节点初始化宏定义
* @name: 需要初始化的节点
*/
#define LIST_NODE_INIT(name) {&(name), &(name)}
/**
* 计算指针域位于宿主结构的偏移量
* @type: 宿主结构体类型
* @member: 指针域成员名
*/
#define offsetof(type, member) ((char *) &((type *)0)->member)
/**
* 已知宿主结构体类型、指针域成员名、指针域地址反推宿主结构体地址
* @ptr: 指针域地址
* @type: 宿主结构体类型
* @member: 指针域成员名
*/
#define list_entry(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/**
* 链表正向遍历，不包含头节点
* @pos: 指向链表节点的指针，类似于c++迭代器
* @head: 链表头节点
* @member: 指针域成员名
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->member.next, typeof(*pos), member); \
&(pos->member) != &((head)->member); \
pos = list_entry((pos)->member.next, typeof(*pos), member))
/**
* 链表反向遍历，不包含头节点
* @pos: 指向链表节点的指针，类似于c++迭代器
* @head: 链表头节点
* @member: 指针域成员名
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->member.prev, typeof(*pos), member); \
&(pos->member) != &((head)->member); \
pos = list_entry((pos)->member.prev, typeof(*pos), member))
/**
* 链表指针域数据结构
*/
typedef struct list_node{
struct list_node *next, *prev;
}list_node;
/**
* API方法
*/
void list_push_node_back(list_node *new, list_node *node);
void list_push_node_front(list_node *new, list_node *node);
void list_del_node(list_node *node);
void list_replace(list_node *new, list_node *old);
#endiflist.c
/**
* 简易版双向循环链表（参考Linux内核链表实现方式）
* @auther: BrightSKY
* @function: 未指定数据端，可以挂载各种类型数据，实现了链表任意节点位置的插入和删除，任意节点的替换，提供正向反向的遍历方式
* @extend: 欢迎根据已有API进行功能扩展，可以实现扩展多链表操作，链表检索和排列等算法
*/
#include "list.h"
/**
* 链表任意位置插入的底层实现
* @new: 新链表节点地址
* @prev: 新节点插入位置的前一节点地址
* @next: 新节点插入位置的下一节点地址
*/
static inline void __list_push(list_node *new, list_node *prev, list_node *next){
next->prev = new;
prev->next = new;
new->next = next;
new->prev = prev;
}
/**
* 插入节点：新节点在指定节点后方位置插入
* @new: 新链表节点地址
* @node: 指定节点地址，新节点将在此节点后方插入
*/
void list_push_node_back(list_node *new, list_node *node){
__list_push(new, node, node->next);
}
/**
* 插入节点：新节点在指定节点前方位置插入
* @new: 新链表节点地址
* @node: 指定节点地址，新节点将在此节点前方插入
*/
void list_push_node_front(list_node *new, list_node *node){
__list_push(new, node->prev, node);
}
/**
* 删除节点：指定节点移除链表
* @node: 指定节点地址，即将删除的节点
*/
void list_del_node(list_node *node){
node->next->prev = node->prev;
node->prev->next = node->next;
}
/**
* 替换节点：用新节点替换旧节点
* @new: 新节点地址
* @old: 旧节点地址
*/
void list_replace(list_node *new, list_node *old){
list_del_node(old);
list_push_node_back(new, old->prev);
}main.c
/**
* 简易版双向循环链表 使用例程（Demo）
* @auther: BrightSKY
* @function: 未指定数据端，可以挂载各种类型数据，实现了链表任意节点位置的插入和删除，任意节点的替换，提供正向反向的遍历方式
* @extend: 欢迎根据已有API进行功能扩展，可以实现扩展多链表操作，链表检索和排列等算法
*/
#include "list.h"
#include "stdio.h"
/**
* 自定义链表结构（包含指针域与数据域，指针域需要使用list_node）
* @data: 自定义的数据域，可以是任意多个数据和类型
* @list_node: 指针域，双向循环链表的操作核心
*/
typedef struct my_list{
int data;
list_node list;
}my_list;
/**
* 创建链表头，指针域初始化可以使用LIST_NODE_INIT宏进行初始化
*/
my_list head = {0, LIST_NODE_INIT(head.list)};
/**
* 主函数，本例程直接以最简单的方式进行链表的插入和遍历，便于大家进行学习
*/
int main(int argc, char const *argv[])
{
/* 创建节点 */
my_list node1 = {1, LIST_NODE_INIT(node1.list)};
my_list node2 = {2, LIST_NODE_INIT(node2.list)};
my_list node3 = {3, LIST_NODE_INIT(node3.list)};
/* 头插法插入节点 */
list_push_node_back(&node1.list, &head.list);
list_push_node_back(&node2.list, &head.list);
/* 尾插法插入节点 */
list_push_node_front(&node3.list, &head.list);
/* 创建链表迭代器 */
my_list *n = NULL;
/* 调用链表正向便利，使用迭代器进行访问并输出 */
list_for_each_entry(n, &head, list)
{
printf("n = %d\n", n->data);
}
printf("-------------------------\n");
/* 删除头节点指向的节点 */
list_del_node(head.list.next);
/* 调用链表反向便利，使用迭代器进行访问并输出 */
list_for_each_entry_reverse(n, &head, list)
{
printf("n = %d\n", n->data);
}
return 0;
}边栏推荐
- 【深度学习】语义分割:论文阅读：（2021-12）Mask2Former
- I2C summary (single host and multi host)
- Nc29 search in two-dimensional array
- 听哥一句劝，按这套嵌入式的课程内容和课程体系去学习
- Why data Tiering
- Automation sequences of canoe simulation functions
- CANoe的数据回放（Replay Block），还是要结合CAPL脚本才能说的明白
- Nc17 longest palindrome substring
- 六月刷题02——字符串
- MapReduce instance (V): secondary sorting
猜你喜欢
【深度學習】語義分割-源代碼匯總
A wave of open source notebooks is coming
Single chip microcomputer realizes modular programming: Thinking + example + system tutorial (the degree of practicality is appalling)
嵌入式开发比单片机要难很多？谈谈单片机和嵌入式开发设计经历
小白带你重游Spark生态圈！
Une grande vague d'attaques à la source ouverte
![[deep learning] semantic segmentation: paper reading: (2021-12) mask2former](/img/dd/fe2bfa3563cf478afe431ac87a8cb7.png)
[deep learning] semantic segmentation: paper reading: (2021-12) mask2former
MapReduce工作机制
Compilation of libwebsocket
在CANoe中通過Panel面板控制Test Module 運行（初級）
随机推荐
tn-c为何不可用2p断路器？
May brush question 01 - array
Vh6501 Learning Series
英雄联盟轮播图自动轮播
MapReduce工作机制
Download address of canoe, download and activation of can demo 16, and appendix of all canoe software versions
Why is 51+ assembly in college SCM class? Why not come directly to STM32
手把手教您怎么编写第一个单片机程序
MapReduce instance (IV): natural sorting
Competition vscode Configuration Guide
Some thoughts on the study of 51 single chip microcomputer
硬件工程师的真实前途我说出来可能你们不信
[deep learning] semantic segmentation - source code summary
嵌入式开发比单片机要难很多？谈谈单片机和嵌入式开发设计经历
There are software load balancing and hardware load balancing. Which one to choose?
Webrtc blog reference:
【深度學習】語義分割-源代碼匯總
Research and implementation of hospital management inpatient system based on b/s (attached: source code paper SQL file)
大学C语言入门到底怎么学才可以走捷径
MapReduce instance (V): secondary sorting