当前位置:网站首页>C miscellaneous two-way circular linked list
C miscellaneous two-way circular linked list
2022-07-06 09:59:00 【Bright-SKY】
Catalog
Knowledge point 1【 Bidirectional circular linked list 】
Knowledge point 2【 Tail insertion of bidirectional linked list 】
Knowledge point 3【 Traversal of double linked list 】
Knowledge point 3【 Two way linked list queries a node 】
Knowledge point 4【 Delete the specified node from the bidirectional linked list 】
Knowledge point 4【 Two way linked list release linked list node 】
Knowledge point 5【Linux Kernel list 】
Knowledge point 1【 Bidirectional circular linked list 】
Knowledge point 2【 Two way linked list Tail insertion 】
STU* insert_link(STU *head, STU tmp)
{
// Apply for space for the inserted node
STU *pi = (STU *)calloc(1,sizeof(STU));
if(pi == NULL)
{
perror("calloc");
return head;
}
*pi = tmp;
// Tail insertion
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;
}
Knowledge point 3【 Two way linked list Traverse 】
void printf_link(STU *head)
{
// Determine whether the linked list exists
if(NULL == head)
{
printf(" The list does not exist \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;
}
Knowledge point 3【 Double linked list Inquire about A node 】
STU *search_link(STU *head, int num)
{
// Determine whether the linked list exists
if(NULL == head)
{
printf(" The list does not exist \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(" No related nodes found \n");
return NULL;
}
}
return NULL;
}
Knowledge point 4【 Double linked list Delete Specify nodes 】
STU* delete_link(STU *head, int num)
{
// Determine whether the linked list exists
if(NULL == head)
{
printf(" The list does not exist \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)// Delete header node
{
if(pb->next == pb)// A linked list has only one node
{
head = NULL;
}
else// The linked list has more than one node
{
head->pre->next = head->next;
head->next->pre = head->pre;
head = head->next;
}
free(pb);
return head;
}
else// Delete 、 Middle tail node
{
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(" No related nodes found \n");
return NULL;
}
}
return head;
}
Knowledge point 4【 Double linked list Release List nodes 】
STU* free_link(STU *head)
{
// Determine whether the linked list exists
if(NULL == head)
{
printf(" The list does not exist \n");
return head;
}
else
{
STU *pb = head;
head->pre->next = NULL;
while(pb != NULL)
{
head = head->next;
free(pb);
pb = head;
}
}
return head;
}
Knowledge point 5【Linux kernel Linked list 】
list.h
/**
* Simple version of two-way circular linked list ( Reference resources Linux Kernel linked list implementation )
* @auther: BrightSKY
* @function: No data end specified , You can mount various types of data , It realizes the insertion and deletion of any node position in the linked list , Replacement of any node , Provide forward and reverse traversal
* @extend: Welcome according to the existing API Expand the function , It can realize the operation of extended multi linked list , Linked list retrieval and arrangement algorithms
*/
#ifndef __LIST_H__
#define __LIST_H__
/**
* New node initializes macro definitions
* @name: Nodes that need to be initialized
*/
#define LIST_NODE_INIT(name) {&(name), &(name)}
/**
* Calculate the offset of the pointer field in the host structure
* @type: Host structure type
* @member: Pointer domain member name
*/
#define offsetof(type, member) ((char *) &((type *)0)->member)
/**
* Known host structure type 、 Pointer domain member name 、 The pointer field address reverses the host structure address
* @ptr: Pointer field address
* @type: Host structure type
* @member: Pointer domain member name
*/
#define list_entry(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/**
* Forward traversal of linked list , Does not contain the head node
* @pos: Pointer to the linked list node , Be similar to c++ iterator
* @head: Chain header node
* @member: Pointer domain member name
*/
#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))
/**
* Reverse traversal of linked list , Does not contain the head node
* @pos: Pointer to the linked list node , Be similar to c++ iterator
* @head: Chain header node
* @member: Pointer domain member name
*/
#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))
/**
* Linked list pointer field data structure
*/
typedef struct list_node{
struct list_node *next, *prev;
}list_node;
/**
* API Method
*/
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);
#endif
list.c
/**
* Simple version of two-way circular linked list ( Reference resources Linux Kernel linked list implementation )
* @auther: BrightSKY
* @function: No data end specified , You can mount various types of data , It realizes the insertion and deletion of any node position in the linked list , Replacement of any node , Provide forward and reverse traversal
* @extend: Welcome according to the existing API Expand the function , It can realize the operation of extended multi linked list , Linked list retrieval and arrangement algorithms
*/
#include "list.h"
/**
* The bottom implementation of inserting anywhere in the linked list
* @new: New linked list node address
* @prev: The address of the previous node where the new node is inserted
* @next: The address of the next node where the new node is inserted
*/
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;
}
/**
* Insert node : The new node is inserted behind the specified node
* @new: New linked list node address
* @node: Specify the node address , The new node will be inserted after this node
*/
void list_push_node_back(list_node *new, list_node *node){
__list_push(new, node, node->next);
}
/**
* Insert node : The new node is inserted in front of the specified node
* @new: New linked list node address
* @node: Specify the node address , The new node will be inserted in front of this node
*/
void list_push_node_front(list_node *new, list_node *node){
__list_push(new, node->prev, node);
}
/**
* Delete node : Specify the node to remove the linked list
* @node: Specify the node address , Node to be deleted
*/
void list_del_node(list_node *node){
node->next->prev = node->prev;
node->prev->next = node->next;
}
/**
* Replacement node : Replace the old node with the new node
* @new: New node address
* @old: Old node address
*/
void list_replace(list_node *new, list_node *old){
list_del_node(old);
list_push_node_back(new, old->prev);
}
main.c
/**
* Simple version of two-way circular linked list Using routines (Demo)
* @auther: BrightSKY
* @function: No data end specified , You can mount various types of data , It realizes the insertion and deletion of any node position in the linked list , Replacement of any node , Provide forward and reverse traversal
* @extend: Welcome according to the existing API Expand the function , It can realize the operation of extended multi linked list , Linked list retrieval and arrangement algorithms
*/
#include "list.h"
#include "stdio.h"
/**
* Custom linked list structure ( Including pointer field and data field , Pointer fields need to use list_node)
* @data: Custom data fields , It can be any number of data and types
* @list_node: Pointer to the domain , The operation core of bidirectional circular linked list
*/
typedef struct my_list{
int data;
list_node list;
}my_list;
/**
* Create a chain header , Pointer field initialization can use LIST_NODE_INIT Macro initialization
*/
my_list head = {0, LIST_NODE_INIT(head.list)};
/**
* The main function , This routine directly inserts and traverses the linked list in the simplest way , It is convenient for everyone to learn
*/
int main(int argc, char const *argv[])
{
/* Create nodes */
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)};
/* Insert the node by head insertion */
list_push_node_back(&node1.list, &head.list);
list_push_node_back(&node2.list, &head.list);
/* The tail insertion method inserts the node */
list_push_node_front(&node3.list, &head.list);
/* Create a linked list iterator */
my_list *n = NULL;
/* Call the forward convenience of the linked list , Use iterators to access and output */
list_for_each_entry(n, &head, list)
{
printf("n = %d\n", n->data);
}
printf("-------------------------\n");
/* Delete the node pointed to by the header node */
list_del_node(head.list.next);
/* Call the reverse convenience of the linked list , Use iterators to access and output */
list_for_each_entry_reverse(n, &head, list)
{
printf("n = %d\n", n->data);
}
return 0;
}
边栏推荐
猜你喜欢
jar运行报错no main manifest attribute
CANoe下载地址以及CAN Demo 16的下载与激活,并附录所有CANoe软件版本
Une grande vague d'attaques à la source ouverte
112 pages of mathematical knowledge sorting! Machine learning - a review of fundamentals of mathematics pptx
嵌入式開發中的防禦性C語言編程
Automation sequences of canoe simulation functions
A wave of open source notebooks is coming
51单片机进修的一些感悟
Elk project monitoring platform deployment + deployment of detailed use (II)
History of object recognition
随机推荐
Tianmu MVC audit II
大学想要选择学习自动化专业,可以看什么书去提前了解?
May brush question 26 - concurrent search
Canoe CAPL file operation directory collection
Installation de la pagode et déploiement du projet flask
MySQL ERROR 1040: Too many connections
在CANoe中通过Panel面板控制Test Module 运行(初级)
Vh6501 Learning Series
51单片机进修的一些感悟
MapReduce instance (VIII): Map end join
I2C summary (single host and multi host)
听哥一句劝,按这套嵌入式的课程内容和课程体系去学习
16 医疗挂号系统_【预约下单】
Hero League rotation map automatic rotation
CANoe不能自动识别串口号?那就封装个DLL让它必须行
tn-c为何不可用2p断路器?
A new understanding of RMAN retention policy recovery window
Delayed note learning
四川云教和双师模式
Regular expressions are actually very simple