单链表的定义
由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。
单链表的特点：单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。
单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
对于每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表中结点类型的描述：
有头节点：指针指向的一个数据是头节点，头节点指向真正的数据节点。
无头节点：指针直接指向数据节点。
区别：有头节点操作可以直接对头节点进行操作，便于管理，无头节点在头节点插入元素需要修改指针指向的元素。
头结点和头指针的区分：不管带不带头结点，头指针始终指向单链表的第一个结点，而头结点是带头结点的单链表中的第一个结点，结点内通常不存储信息。
那么单链表的初始化操作就是申请一个头结点，将指针域置空。
<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_H
typedef 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 -c
all:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $^ $(CFLAGS) -o $@
clean:
$(RM) -r all $(OBJS)
无头节点的单链表
结构体
#define NAMESIZE 32
struct 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 32
struct 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 -c
all:$(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;
}
else
r->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合并到p1
printf("--------------我是可爱的分界线---------------------\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 8
struct 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 1
LLIST* 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");
else
print_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
{
// err
return -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_st
11 {
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
{
// err
return -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_head
19 {
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 2
typedef 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");
}
else
print_s(data_ptr);
return 0;
}
list.h
#ifndef LINUX_LIST_H
#define LINUX_LIST_H
struct 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
