当前位置：网站首页>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;
}边栏推荐
- Vs All comments and uncomments
- 五月刷题26——并查集
- Nc17 longest palindrome substring
- 51单片机进修的一些感悟
- Download address of canoe, download and activation of can demo 16, and appendix of all canoe software versions
- Vh6501 Learning Series
- [deep learning] semantic segmentation: paper reading: (2021-12) mask2former
- Why is 51+ assembly in college SCM class? Why not come directly to STM32
- Hero League rotation map automatic rotation
- Random notes
猜你喜欢
Counter attack of noodles: redis asked 52 questions in a series, with detailed pictures and pictures. Now the interview is stable
Listen to my advice and learn according to this embedded curriculum content and curriculum system
Take you back to spark ecosystem!
大学C语言入门到底怎么学才可以走捷径
Can I learn PLC at the age of 33
![[deep learning] semantic segmentation: paper reading: (2021-12) mask2former](/img/dd/fe2bfa3563cf478afe431ac87a8cb7.png)
[deep learning] semantic segmentation: paper reading: (2021-12) mask2former
Hero League rotation map automatic rotation
Mapreduce实例（五）：二次排序
在CANoe中通過Panel面板控制Test Module 運行（初級）
五月集训总结——来自阿光
随机推荐
嵌入式开发比单片机要难很多？谈谈单片机和嵌入式开发设计经历
Automation sequences of canoe simulation functions
018. Valid palindromes
Control the operation of the test module through the panel in canoe (primary)
MySQL数据库优化的几种方式(笔面试必问)
Vs All comments and uncomments
068.查找插入位置--二分查找
Popularization of security knowledge - twelve moves to protect mobile phones from network attacks
Cap theory
Several silly built-in functions about relative path / absolute path operation in CAPL script
【深度学习】语义分割：论文阅读：(CVPR 2022) MPViT（CNN+Transformer）：用于密集预测的多路径视觉Transformer
MapReduce工作机制
Mapreduce实例（六）：倒排索引
Release of the sample chapter of "uncover the secrets of asp.net core 6 framework" [200 pages /5 chapters]
Webrtc blog reference:
Design and implementation of online snack sales system based on b/s (attached: source code paper SQL file)
max-flow min-cut
Some thoughts on the study of 51 single chip microcomputer
在CANoe中通过Panel面板控制Test Module 运行（初级）
英雄联盟轮播图自动轮播