C数据结构：链表高级篇

单链表的定义

由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

单链表的特点：单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。
单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
对于每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表中结点类型的描述：

有头节点：指针指向的一个数据是头节点，头节点指向真正的数据节点。
无头节点：指针直接指向数据节点。
区别：有头节点操作可以直接对头节点进行操作，便于管理，无头节点在头节点插入元素需要修改指针指向的元素。

头结点和头指针的区分：不管带不带头结点，头指针始终指向单链表的第一个结点，而头结点是带头结点的单链表中的第一个结点，结点内通常不存储信息。
那么单链表的初始化操作就是申请一个头结点，将指针域置空。

<span style="color:#000000"><span style="background-color:#282c34"></span></span>

有头节点的单链表

通常会用头指针来标识一个单链表，头指针为NULL时表示一个空表。但是，为了操作方便，会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。在本链表中，指定了头节点不是下标为0 的节点，0节点是头节点后的一个节点。

typedef int datatype;typedef struct note_st
{datatype data; //存放数据struct note_st* next; //存放下一个位置的指针
}list;

创建有头单链表


list* list_create()
{list* me; me = malloc(sizeof(*me));if(me == NULL)return NULL;me->next = NULL; //头元素指向空return me; 
}

按照位置插入元素

这里所说的插入是将值为data的新结点插入到单链表L的第i个位置上。（不包括头结点）

算法思想：从表头开始遍历，查找第 i-1个结点，即插入位置的前驱结点为p，然后令新结点newnode的指针域指向node的后继结点，再令结点node的指针域指向新结点*newnode。

int list_insert_at(list*me,int i,datatype*data)
{int j = 0;list* node = me,*newnode;if(i<0)return -1; while(j< i && node != NULL){   node = node->next;j++;}   if(node){   newnode = malloc(sizeof(*newnode));if(newnode == NULL)return -2;newnode->data = *data;newnode->next = node->next;node->next = newnode;return 0;}else{return -3;}}

显示元素

算法思想：声明一个指针p，从头结点指向的第一个结点开始，如果p不为空，那么就输出当前结点的值，并将p指向下一个结点，直到遍历到最后一个结点为止。

oid list_display(list*me)
{list*node = me->next;if(list_isempty(me) == 0)return;while(node != NULL){printf("%d ",node->data );node = node->next;}printf("\n");}

销毁链表

先获取到头节点执行的节点，不为空则删除全部信息，删除完毕后，最后删除头节目信息。


void list_destroy(list*me)
{list*next;list*node = me->next;while(node != NULL){next  = node->next;free(node);node  = next;}free(me);return;
}

按位置插入排序


int list_order_insert(list* me,datatype *data)
{//按照顺序进行排序list *p = me,*q;while(p->next && (p->next->data < *data) ){p = p->next;}q = malloc(sizeof(*q));if(q == NULL)return -1;q->data = *data;q->next = p->next;p->next = q;return 0;}

有头链表的全部实现

main.c

#include <stdlib.h>
#include <stdio.h>
#include "list.h"
int main()
{list*l;datatype arr[] = {11,2,33,4,55};l = list_create();if(l == NULL)exit(1);for(int i=0;i<sizeof(arr)/sizeof(*arr);i++ ){//if(list_insert_at(l,0,&arr[i]) != 0)if(list_order_insert(l,&arr[i]) != 0)exit(1);}list_insert_at(l,1,&arr[0]);list_display(l);int val = 11;list_delete(l,&val);list_display(l);list_destroy(l);return 0;
}

list.c

#include "list.h"
#include <stdlib.h>
#include <stdio.h>list* list_create()
{list* me;me = malloc(sizeof(*me));if(me == NULL)return NULL;me->next = NULL;return me;
}int list_insert_at(list*me,int i,datatype*data)
{int j = 0;list* node = me,*newnode;if(i<0)return -1;while(j< i && node != NULL){node = node->next;j++;}if(node){newnode = malloc(sizeof(*newnode));if(newnode == NULL)return -2;newnode->data = *data;newnode->next = node->next;node->next = newnode;return 0;}else{return -3;}}void list_display(list*me)
{list*node = me->next;if(list_isempty(me) == 0)return;while(node != NULL){printf("%d ",node->data );node = node->next;}printf("\n");}int list_order_insert(list* me,datatype *data)
{//按照顺序进行排序list *p = me,*q;while(p->next && (p->next->data < *data) ){p = p->next;}q = malloc(sizeof(*q));if(q == NULL)return -1;q->data = *data;q->next = p->next;p->next = q;return 0;}int list_delete_at(list* me,int i,datatype * data)
{int j = 0;list *p = me,*q;*data = -1;if(i< 0)return -1;while(j< i && p ){p = p->next;j++;}if(p){q = p->next;p->next = q->next;*data = q->data;free(q);q = NULL;return 0;}else{return -2;}}int list_delete(list* me,datatype* data)
{list*p =me,*q;while(p->next && p->next->data != *data){p = p->next;}if(p->next == NULL)return -1;q = p->next;p->next = q->next;free(q);q = NULL;return 0;
}int list_isempty(list*me)
{if(me->next == NULL)return 0;return 1;
}void list_destroy(list*me)
{list*next;list*node = me->next;while(node != NULL){next  = node->next;free(node);node  = next;}free(me);return;
}

list.h

#ifndef LIST_H
#define LIST_Htypedef int datatype;typedef struct note_st
{datatype data;struct note_st* next;
}list;list* list_create();int list_insert_at(list*,int i,datatype*);int list_order_insert(list*,datatype *);int list_delete_at(list*,int i,datatype *);int list_delete(list*,datatype* );int list_isempty(list*);void list_display(list*me);void list_destroy(list*);#endif

makefile

CC = gcc
OBJS = main.o list.o
CFLAGS =  -g -Wall -call:$(OBJS)$(CC) $^  -o $@%.o:%.c$(CC) $^ $(CFLAGS) -o $@	clean:$(RM) -r all $(OBJS)

无头节点的单链表

结构体

#define NAMESIZE 32struct score_st
{int id; char name[NAMESIZE];int math;int chinese;
};struct node_st
{struct score_st data;struct node_st* next;
};

插入元素

struct node_st* list_insert(struct node_st*list ,struct score_st*data)
{struct node_st* new;new =  malloc(sizeof(*new));if(new == NULL)return NULL;new->data = *data;new->next = NULL;new->next =list;list = new;return list; //要将list返回，否则会失去元素，这里的指针是值传递传递的，也可以使用二级指针}

显示元素

void list_show(struct node_st*list)
{struct node_st*cur;for(cur = list;cur !=NULL;cur = cur->next){   printf("id = %d name - %s math = %d chinese = %d \n",cur->data.id,cur->data.name,cur->data.math,cur->data.chinese);}   
}

查找元素


int list_find(struct node_st*list,int id) 
{struct node_st* cur;for(cur = list;cur !=NULL;cur = cur->next){   if(cur->data.id == id) {   printf("%d 已经找到了\n",cur->data.id);return 0;}   }   return -1; 
}

无头链表的全部实现

main.c

#include <stdlib.h>
#include <stdio.h>
#include "nohand.h"int main()
{struct node_st* list = NULL;struct score_st temp;for(int i=0;i<7;i++){temp.id = i;snprintf(temp.name,NAMESIZE,"stu%d",i);temp.math = rand()%100;temp.chinese = rand()%100;//list = list_insert(list,&temp);list_insert_point(&list,&temp);}list_show(list);list_delete(&list);printf("-------------------------------------------\n");// list_show(list);int i = 3;struct score_st*ptr;ptr = list_find(list,i);if(ptr == NULL){printf("no find \n");}else{printf("find id = %d \n",ptr->id );}list_destroy(list);return 0;
}

nohead.h

#ifndef NOHAND_H__
#define NOHEAD_H__#define NAMESIZE 32struct score_st
{int id;char name[NAMESIZE];int math;int chinese;
};struct node_st
{struct score_st data;struct node_st* next;
};struct node_st* list_insert(struct node_st* ,struct score_st* );
int  list_insert_point(struct node_st** ,struct score_st* );void list_show(struct node_st*);int list_delete(struct node_st**);struct score_st* list_find(struct node_st*,int);void list_destroy(struct node_st*);#endif

nohead.c

#include <stdlib.h>
#include <stdio.h>
#include "nohand.h"struct node_st* list_insert(struct node_st*list ,struct score_st*data)
{struct node_st* new;new =  malloc(sizeof(*new));if(new == NULL)return NULL;new->data = *data;new->next = NULL;new->next =list;list = new;return list; //要将list返回，否则会失去元素}
int list_insert_point(struct node_st**list ,struct score_st*data)
{struct node_st* new;new =  malloc(sizeof(*new));if(new == NULL)return -1;new->data = *data;new->next =*list;*list = new;return 0;
}void list_show(struct node_st*list)
{struct node_st*cur;for(cur = list;cur !=NULL;cur = cur->next){printf("id = %d name - %s math = %d chinese = %d \n",cur->data.id,cur->data.name,cur->data.math,cur->data.chinese);}
}
int list_delete(struct node_st** list)
{if(*list == NULL)return -1;struct node_st* cur;cur = (*list);*list = cur->next;free(cur);return 0;}struct score_st* list_find(struct node_st*list,int id)
{struct node_st* cur;for(cur = list;cur !=NULL;cur = cur->next){if(cur->data.id == id){return &cur->data;}}return NULL;
}void list_destroy(struct node_st* list)
{struct node_st* cur;for(cur = list;cur !=NULL;cur = list){list = cur->next;free(cur);cur = NULL;}printf("list destroy \n");
}

makefile

CC = gcc
OBJS = main.o nohand.o
CFLAGS =  -g -Wall -call:$(OBJS)$(CC) $^  -o $@%.o:%.c$(CC) $^ $(CFLAGS) -o $@	clean:$(RM) -r all $(OBJS)

实战

多项式合并

#include <stdlib.h>
#include <stdio.h>struct node_st
{int coef;int expe;struct node_st* next;
};struct node_st* poly_create(int a[][2],int n)
{struct node_st* me, *cur;me = malloc (sizeof(*me));if(me == NULL){return NULL;}cur = me;for(int i= 0;i<n;i++){struct node_st* newnode;newnode = malloc(sizeof(*newnode));if(newnode == NULL)return NULL;newnode->coef = a[i][0];newnode->expe  = a[i][1];newnode->next = NULL;cur->next = newnode;cur = newnode;}return me;
};void poly_show(struct node_st*me)
{struct node_st*cur;for(cur = me->next; cur!= NULL;cur = cur->next ){printf("(%d ,%d )",cur->coef,cur->expe);}printf("\n");
};void poly_union(struct node_st*p1,struct node_st*p2)
{struct node_st*cur1,*cur2,*r;r = p1;cur1 = p1->next;cur2 = p2->next;while(cur1 && cur2){if(cur1->expe <cur2->expe){r->next = cur1;r = cur1;cur1 = cur1->next;}else if(cur1->expe > cur2->expe){r->next = cur2;r = cur2;cur2 = cur2->next;}else  // cur1->expe == cur2->expe{cur1->coef += cur2->coef;if(cur1->coef){r->next = cur1;r = cur1;}cur1 = cur1->next;cur2 = cur2->next;}}if(cur1 ==NULL){r->next = cur2;}elser->next = cur1;}
int main()
{struct node_st* p1,*p2;int a[][2] = {{5,0},{2,1},{8,8},{3,16} };int b[][2] = {{6,1},{16,6},{-8,8} };p1 = poly_create(a,4);printf("--------------我是可爱的分界线---------------------\n");p2 = poly_create(b,3);poly_show(p1);poly_show(p2);poly_union(p1,p2); //将P2合并到p1printf("--------------我是可爱的分界线---------------------\n");poly_show(p1);return 0;
}

循环无头单链表

背景

约瑟夫环（杀人游戏）

举例：某天你去原始森林玩,碰到了一群土著邀请你去玩一个杀人游戏8个人围坐一圈，报数，报到3的人拿根绳吊死，问如何保命，笑到最后

提示：N个人看作是N个链表节点，节点1指向节点2，节点2指向节点3，……，节点N - 1指向节点N，节点N指向节点1，这样就形成了一个环。然后从节点1开始1、2、3……往下报数，每报到M，就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。

#include <stdlib.h>
#include <stdio.h>
#define JOSE_NUM 8struct node_st
{int data;struct node_st*next;
};struct node_st* jose_create(int num)
{struct node_st *me,*newnode,*cur;int i = 1;me = malloc(sizeof(*me));if(me ==NULL)return NULL;me->data = i;me->next = me;i++;cur = me; //保证me不变，出错误方便调试for(;i<=num;i++){newnode = malloc(sizeof(*newnode));if(newnode ==NULL)exit(1);newnode->data = i;newnode->next = me;cur->next = newnode;cur = newnode;}return me;}
void jose_show(struct node_st*me)
{struct node_st*cur;for(cur = me;cur->next!=me; cur = cur->next){printf("%d ",cur->data);}printf("%d \n",cur->data);}void jose_kill(struct node_st**me,int num)
{struct node_st*cur,*node;cur = *me;while(cur != cur->next){int i = 1;while(i<num){node = cur;cur = cur->next;i++;}printf("%d ",cur->data);node->next = cur->next;free(cur);cur = node->next;i = 1;}*me = cur;printf("\n ");}int main()
{struct node_st*list;list = jose_create(JOSE_NUM);if(list == NULL)return -1;jose_show(list);int n = 3;jose_kill(&list,n);jose_show(list);    return 0;
}

双向循环链表

双向循环链表是一种特殊的数据结构，它允许我们在两个方向上遍历链表。与单向链表相比，双向链表在每个节点中增加了两个指针，一个指向前一个节点，另一个指向下一个节点。这种设计使得我们可以更加灵活地处理数据，并且可以更容易地进行插入和删除操作。

全部实现（lib1）

main.c

#include <stdlib.h>
#include <stdio.h>
#include "llist.h"
#include <string.h>struct score_st
{int id;char name[32];int math;int chinese;
};void print_s(const void *record)
{const struct score_st*r = record;printf("%d %s %d %d \n",r->id,r->name,r->math ,r->chinese);}static int id_cmp(const void*key,const void *record)
{const int*k = key;const struct score_st* r = record;return (*k - r->id);}
static int name_cmp(const void*key,const void *record)
{const char*k = key;const struct score_st* r = record;return strcmp(k,r->name);
}
int main()
{
#if 1LLIST* handler;struct score_st temp;int ret; handler = llist_create(sizeof(struct score_st) );if(handler == NULL)exit(1);for(int i=0;i<7;i++){temp.id = i;snprintf(temp.name,sizeof(temp.name),"stu_%d",i);temp.math = rand()%100;temp.chinese = rand()%100;ret = llist_insert(handler,&temp,LLIST_BACKWARD);if(ret)exit(1);}llist_travel(handler,print_s);printf("=====================\n");int id = 3;struct score *data;data = llist_find(handler,&id,id_cmp);if(data == NULL)printf("没有找到\n");elseprint_s(data);printf("=====================\n");char *del_name = "stu_4";ret = llist_delete(handler,del_name,name_cmp);if(ret)printf("delete error");printf("========删除成功============\n");llist_travel(handler,print_s);llist_destroy(handler);printf("=====================\n");
#endif  return 0;
}

llist.c

#include <stdlib.h>
#include <stdio.h>
#include "llist.h"
#include <string.h>LLIST* llist_create(int size)
{LLIST* new;new = malloc(sizeof(*new));if(new == NULL)return NULL;new->size = size;new->head.data = NULL;new->head.prev = &new->head;new->head.next = &new->head;return new;}int llist_insert(LLIST*ptr,const void*data,int mode)
{struct llist_node_st* newnode;newnode = malloc(sizeof(*newnode));if(newnode == NULL)return -1;newnode->data = malloc(ptr->size);if(newnode->data == NULL)return -2;memcpy(newnode->data,data,ptr->size);if(mode == LLIST_FORWARD){newnode->prev = &ptr->head;newnode->next = ptr->head.next;}else if (mode == LLIST_BACKWARD){newnode->prev = ptr->head.prev;newnode->next = &ptr->head;}else{// errreturn -3;}newnode->prev->next = newnode;newnode->next->prev = newnode;return 0;}
static struct llist_node_st* find_(LLIST*ptr,const void*key ,llist_cmp* cmp)
{struct llist_node_st*cur;for(cur = ptr->head.next;cur != &ptr->head; cur = cur->next ){if(cmp(key,cur->data)== 0)break;}return cur;}void* llist_find(LLIST*ptr,const void* key,llist_cmp* cmp)
{return  find_(ptr,key,cmp)->data;
}int llist_delete(LLIST* ptr,const void*key,llist_cmp*cmp)
{struct llist_node_st*node;node = find_(ptr,key,cmp);if(node == &ptr->head )return -1;node->prev->next = node->next;node->next->prev = node->prev;free(node->data);free(node);return 0;
}
int llist_fetch(LLIST*ptr,const void*key,llist_cmp*cmp,void* data)
{struct llist_node_st* node;node = find_(ptr,key,cmp);if(node == &ptr->head)return -1;node->prev->next = node->next;node->next->prev = node->prev;if(data != NULL)memcpy(data,node->data,ptr->size);free(node->data);free(node);return 0;
}void llist_travel(LLIST*ptr,llist_op* op)
{struct llist_node_st *cur;for(cur = ptr->head.next;cur != &(ptr->head);cur = cur->next) {op(cur->data);}
}void llist_destroy(LLIST*ptr)
{struct llist_node_st* cur,*next;for(cur = ptr->head.next; cur != &(ptr->head);cur = next){next = cur->next;free(cur->data);free(cur);}free(ptr);
}

llist.h

#ifndef _LLIST_H__
#define _LLIST_H__#define LLIST_FORWARD  1
#define LLIST_BACKWARD 2
typedef void llist_op(const void *);   // typedef声明了一个函数类型，可以用 list_op *p生成一个函数指针
typedef int llist_cmp(const void *,const void* );  struct llist_node_st
{void *data;struct llist_node_st* prev;struct llist_node_st* next;
};typedef struct  // llist_node_head
{int size;struct llist_node_st head;
}LLIST;LLIST* llist_create(int size);
#if 1 
int llist_insert(LLIST*,const void*data,int mode);void * llist_find(LLIST*,const void*,llist_cmp*);int llist_delete(LLIST*,const void*key,llist_cmp*);int llist_fetch(LLIST*,const void*key,llist_cmp*,void* data);void llist_travel(LLIST*,llist_op* );void llist_destroy(LLIST*);#endif #endif

使用变长结构体实现(lib2)

 10 struct llist_node_st11 {12     struct llist_node_st* prev;13     struct llist_node_st* next;14     char  data[1];  //变长结构体，去data就是一块地址 C语言空结构体占用0字节，C++占用1字节。15     16 };使用变长结构体，用户输入的数据我们可以通过data来获取到，方便使用和计算

llist.c

#include <stdlib.h>
#include <stdio.h>
#include "llist.h"
#include <string.h>LLIST* llist_create(int size)
{LLIST* new;new = malloc(sizeof(*new));if(new == NULL)return NULL;new->size = size;new->head.prev = &new->head;new->head.next = &new->head;return new;}int llist_insert(LLIST*ptr,const void*data,int mode)
{struct llist_node_st* newnode;newnode = malloc(sizeof(*newnode)+ ptr->size);if(newnode == NULL)return -1;memcpy(newnode->data,data,ptr->size);if(mode == LLIST_FORWARD){newnode->prev = &ptr->head;newnode->next = ptr->head.next;}else if (mode == LLIST_BACKWARD){newnode->prev = ptr->head.prev;newnode->next = &ptr->head;}else{// errreturn -3;}newnode->prev->next = newnode;newnode->next->prev = newnode;return 0;}
static struct llist_node_st* find_(LLIST*ptr,const void*key ,llist_cmp* cmp)
{struct llist_node_st*cur;for(cur = ptr->head.next;cur != &ptr->head; cur = cur->next ){if(cmp(key,cur->data)== 0)break;}return cur;}void* llist_find(LLIST*ptr,const void* key,llist_cmp* cmp)
{struct llist_node_st*node;node = find_(ptr,key,cmp);if(node == &ptr->head)return NULL;return node->data;}int llist_delete(LLIST* ptr,const void*key,llist_cmp*cmp)
{struct llist_node_st*node;node = find_(ptr,key,cmp);if(node == &ptr->head )return -1;node->prev->next = node->next;node->next->prev = node->prev;free(node);return 0;
}
int llist_fetch(LLIST*ptr,const void*key,llist_cmp*cmp,void* data)
{struct llist_node_st* node;node = find_(ptr,key,cmp);if(node == &ptr->head)return -1;node->prev->next = node->next;node->next->prev = node->prev;if(data != NULL)memcpy(data,node->data,ptr->size);free(node);return 0;
}void llist_travel(LLIST*ptr,llist_op* op)
{struct llist_node_st *cur;for(cur = ptr->head.next;cur != &(ptr->head);cur = cur->next) {op(cur->data);}
}void llist_destroy(LLIST*ptr)
{struct llist_node_st* cur,*next;for(cur = ptr->head.next; cur != &(ptr->head);cur = next){next = cur->next;free(cur);}free(ptr);
}

llist.h

#ifndef _LLIST_H__
#define _LLIST_H__#define LLIST_FORWARD  1
#define LLIST_BACKWARD 2
typedef void llist_op(const void *);   // typedef声明了一个函数类型，可以用 list_op *p生成一个函数指针
typedef int llist_cmp(const void *,const void* );  struct llist_node_st
{struct llist_node_st* prev;struct llist_node_st* next;char  data[1];  //变长结构体，去data就是一块地址 C语言空结构体占用0字节，C++占用1字节。};typedef struct  // llist_node_head
{int size;struct llist_node_st head;
}LLIST;LLIST* llist_create(int size);
#if 1 
int llist_insert(LLIST*,const void*data,int mode);void * llist_find(LLIST*,const void*,llist_cmp*);int llist_delete(LLIST*,const void*key,llist_cmp*);int llist_fetch(LLIST*,const void*key,llist_cmp*,void* data);void llist_travel(LLIST*,llist_op* );void llist_destroy(LLIST*);#endif #endif

使用类封装来实现

 typedef struct   llist_head19 {           20     int size;21     struct llist_node_st head;22     int (*insert)(struct llist_head*,const void*,int);23     void* (*find)(struct llist_head*,const void*,llist_cmp*);24     int (*del)(struct llist_head*,const void*,llist_cmp*);25     int (*fetch)(struct llist_head*,const void*,llist_cmp*i,void *);26     void (*travel)(struct llist_head*,llist_op *);27     28     29 }LLIST; int (*insert)(struct llist_head*,const void*,int);7 void (*find)(struct llist_head*,const void*,llist_cmp*);8 int (*del)(struct llist_head*,const void*,llist_cmp*);9 int (*fetch)(struct llist_head*,const void*,llist_cmp*i,void *);10 int (*travel)(struct llist_head*,llist_op *);11 12 13 LLIST* llist_create(int size)14 {   15     LLIST* new;16     new = malloc(sizeof(*new));17     if(new == NULL)18         return NULL;19     new->size = size;20     new->head.prev = &new->head;21     new->head.next = &new->head;22     23     new->insert = llist_insert;24     new->del = llist_delete;25     new->find = llist_find;26     new->fetch = llist_fetch;27     new->travel = llist_travel;28     return new;29 30 }

实现数据隐藏(lib3)

llist.c

#include <stdlib.h>
#include <stdio.h>
#include "llist.h"
#include <string.h>struct llist_node_st
{struct llist_node_st* prev;struct llist_node_st* next;char  data[1];  //变长结构体，去data就是一块地址 C语言空结构体占用0字节，C++占用1字节。};struct  llist_head_st
{int size;struct llist_node_st head;
};LLIST* llist_create(int size)
{struct llist_head_st* new;new = malloc(sizeof(*new));if(new == NULL)return NULL;new->size = size;new->head.prev = &new->head;new->head.next = &new->head;return new;}int llist_insert(LLIST*p,const void*data,int mode)
{struct llist_node_st* newnode;struct llist_head_st*ptr = p;newnode = malloc(sizeof(*newnode)+ ptr->size);if(newnode == NULL)return -1;memcpy(newnode->data,data,ptr->size);if(mode == LLIST_FORWARD){newnode->prev = &ptr->head;newnode->next = ptr->head.next;}else if (mode == LLIST_BACKWARD){newnode->prev = ptr->head.prev;newnode->next = &ptr->head;}else{return -3;}newnode->prev->next = newnode;newnode->next->prev = newnode;return 0;}
static struct llist_node_st* find_(struct llist_head_st*ptr,const void*key ,llist_cmp* cmp)
{struct llist_node_st*cur;for(cur = ptr->head.next;cur != &ptr->head; cur = cur->next ){if(cmp(key,cur->data)== 0)break;}return cur;}void* llist_find(LLIST*p,const void* key,llist_cmp* cmp)
{struct llist_node_st*node;struct llist_head_st *ptr = p;node = find_(ptr,key,cmp);if(node == &ptr->head)return NULL;return node->data;}int llist_delete(LLIST* p,const void*key,llist_cmp*cmp)
{struct llist_node_st*node;struct llist_head_st *ptr = p;node = find_(ptr,key,cmp);if(node == &ptr->head )return -1;node->prev->next = node->next;node->next->prev = node->prev;free(node);return 0;
}
int llist_fetch(LLIST*p,const void*key,llist_cmp*cmp,void* data)
{struct llist_node_st* node;struct llist_head_st *ptr = p;node = find_(ptr,key,cmp);if(node == &ptr->head)return -1;node->prev->next = node->next;node->next->prev = node->prev;if(data != NULL)memcpy(data,node->data,ptr->size);free(node);return 0;
}void llist_travel(LLIST*p,llist_op* op)
{struct llist_head_st* ptr = p;struct llist_node_st *cur;for(cur = ptr->head.next;cur != &(ptr->head);cur = cur->next) {op(cur->data);}
}void llist_destroy(LLIST*p)
{struct llist_head_st *ptr = p;struct llist_node_st* cur,*next;for(cur = ptr->head.next; cur != &(ptr->head);cur = next){next = cur->next;free(cur);}free(ptr);
}

llist.h

#ifndef _LLIST_H__
#define _LLIST_H__#define LLIST_FORWARD  1
#define LLIST_BACKWARD 2typedef void LLIST;typedef void llist_op(const void *);   // typedef声明了一个函数类型，可以用 list_op *p生成一个函数指针
typedef int llist_cmp(const void *,const void* );  LLIST* llist_create(int size);int llist_insert(LLIST*,const void*data,int mode);void * llist_find(LLIST*,const void*,llist_cmp*);int llist_delete(LLIST*,const void*key,llist_cmp*);int llist_fetch(LLIST*,const void*key,llist_cmp*,void* data);void llist_travel(LLIST*,llist_op* );void llist_destroy(LLIST*);#endif

内核源码实现-双向环链(kernal)

路径：/usr/src/linux-headers-5.15.0-105-generic/include/linux

内核中头宏定义的实现一般都是前加下划线，我们最好定义宏的时候采用后加下划线，来防止定义冲突。

使用命令查找container_of函数的实现：grep "#define container_of(" -R .

main.c

#include <stdlib.h>
#include <stdio.h>
#include "list.h"struct score_st
{int id;char name[32];int math;int chinese;struct list_head node;
};static void print_s(struct score_st *d)
{printf("%d %s %d %d \n",d->id,d->name,d->math,d->chinese);
}int main()
{struct score_st *data_ptr;struct list_head*  cur;LIST_HEAD(head);for(int i=0;i<7;i++){data_ptr = malloc(sizeof(*data_ptr));if(data_ptr == NULL)return -1;data_ptr->id = i;data_ptr->math = rand()%100;data_ptr->chinese = rand()%100;snprintf(data_ptr->name,32,"stu_%d",i);list_add(&data_ptr->node,&head); }__list_for_each(cur,&head){data_ptr = list_entry(cur,struct score_st,node);print_s(data_ptr);}printf("=============================\n");__list_for_each(cur,&head){data_ptr = list_entry(cur,struct score_st,node);if(data_ptr->id = 5)break;}if(cur == &head){printf("no find \n");}elseprint_s(data_ptr);return 0;
}

list.h

#ifndef LINUX_LIST_H
#define LINUX_LIST_Hstruct list_head
{struct list_head* prev;struct list_head* next;};#define LIST_HEAD_INIT(name) {&(name),&(name)}#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next)
{next->prev = new;new->next = next;new->prev = prev;prev->next = new;}static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}#define __list_for_each(pos, head) \for (pos = (head)->next; pos !=(head); pos = pos->next)
#if 0
ptr->cur;
type->struct score_st
member->node 
#endif #define offsetof(TYPE, MEMBER)  ((size_t) &((TYPE *)0)->MEMBER)#if 1
#define container_of(ptr,type,member) \({ (type*)( (char*)ptr - offsetof(type,member)  ); })#else#define container_of(ptr,type,member)({     \const typeof( ((type*)0)->member) *__mptr = (ptr); \(type*)( (char*)__mptr - offsetof(type,member) ); })
#endif #define list_entry(ptr, type, member) container_of(ptr,type,member)#endif