C语言|数据结构-双向循环链表
编译系统@CentOS 7 x86_64
gcc version 4.8.5
双向循环链表是一种比较实用的数据结构，在Linux 内核源码里常常使用，因而学习记录一下。
不同于单链表，双向循环链表 可以表示为
即
#define GENERAL_CREATE 0
// 1、一般结构体 构造
#if GENERAL_CREATE
//普通节点
struct llist_node_st
{
void *data;
llist_st *prev;
llist_st *next;
};
#else
//2、变长结构体 构造
struct llist_node_st
{
struct llist_node_st *prev;
struct llist_node_st *next;
char data[0];
// ps. C99后才支持 0字符数组 当作变长的占位符
// 也可以写为 char[1] 计算时 需要减去 sizeof(data/data[0])
// 变长的结构体需要 位于结构体声明最后
};
// 头节点
typedef struct llist_head
{
int size;
struct llist_node_st head;
}LLIST;
#endif
链表的创建
? 操作：创建一个头结点
//1、一般结构体 创建
/*
* @brief: 创建头节点
* @param: int initsize 头节点初始化大小
* @retvalue: LLIST*
*/
#if GENERAL_CREATE
LLIST *llist_create(int initsize)
{
LLIST *new;
// 动态申请内存
new = malloc(sizeof(*new));
// 如果申请为空 返回空
if(new == NULL)
return NULL;
// 初始化
new->size = initsize;
new->head.data= NULL;
new->head.prev = &new->head;
new->head.next = &new->head;
//双向循环链表 只有头，则 自己指向自己
return new;
}
#else
//2. 变长结构体 创建
LLIST *llist_create(int initsize)
{
LLIST *new;
new = malloc(sizeof(*new));
if(new == NULL)
return NULL;
new->size = initsize;
new->head.prev = &new->head;
new->head.next = &new->head;
return new;
}
#endif
链表的 销毁
操作 ：默认 链表成功创建 ，并销毁 目标链表
/*
*@brief: 销毁 目标链表
*@param: LLIST *llist 目标链表
*@retvalue: void
*/
void llist_destroy(LLIST *llist) // 默认 成功 创建
{
struct llist_node_st *cur,*next;
//ps.头节点的 头部的下次指针，由于 头节点 是循环的 如果 是头节点 则结束循环
for(cur = llist->head.next; cur != &llist->head; cur = next)
{
next = cur->next;
// free(cur->data);
free(cur);
}
free(llist);
}
链表的 插入
操作 ：插入模式
INSERT_MODE_FORWARD ,INSERT_MODE_REAR 如果要面向对象编程的话 也可以利用
函数指针 进行 操作
#include<string.h> // memcpy
#include<stdio.h>
#include<stdlib.h>
#define INSERT_MODE_REAR 1
#define INSERT_MODE_FORWARD 2
/*
*@brief: 插入 数据 到 链表
*@param: LLIST *llist 目标链表
* const void *data 插入数据
* int mode 模式
*@retvalue: int 状态值
**/
int llist_insert(LLIST *llist, const void *data,int mode) // 由于 循环列表 则只设置 两>种模式 头插 或者 尾插
{
struct llist_node_st *new_node;
new_node = malloc(sizeof(*new_node) + llist->size); //如果 要地址对齐，也要需要 减去至少四个字节
if(new_node == NULL) return -1;
// new_node->data = malloc(llist->size);
// if(new_node->data == NULL) return -2;
memcpy(new_node->data,data,llist->size);
// void *memcpy(void *dest, const void *src, size_t n);
if(mode == INSERT_MODE_FORWARD)
{
new_node->prev = &llist->head;
new_node->next = llist->head.next;
}
else if(mode == INSERT_MODE_REAR)
{
new_node->prev = llist->head.prev;
new_node->next = &llist->head;
}
else
{
return -3;
}
new_node->prev->next = new_node;
new_node->next->prev = new_node;
return 0;
}
链表的 查找
操作：根据关键字查找，可以创建回调函数查找关键字段，为删除和提取做准备
// 类型定义 返回值类型 函数类型名(参数列表); 可以当作回调函数 传入函数指针 来指定 关于关键字段的特定查找和比较方式
typedef int llist_cmp(const void*,const void*);
// 为删除和提取 封装 重复 操作
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;
}
/*
*@brief: 在 目标链表 根据关键字 根据回调函数进行寻找
*@param: LLIST *llist 目标链表
* const void *key 关键字
* llist_cmp *cmp 回调函数
*@retvalue: void *
**/
void* llist_find(LLIST* llist, const void* key,llist_cmp *cmp)
{
#if GENERAL_CREATE
return find_(llist,key,cmp)->data; // 获取 和删除 都要先查找 所以可以例化
#else
struct llist_node_st *node;
node = find_(llist,key,cmp);
//找到头节点 就 返回空 即 以头节点为存在基础
if(node == &llist->head)
return NULL;
return node->data;
#endif
链表的 删除 特定元素
操作：根据 关键字 删除 特定 元素
/*
*@brief: 在 目标链表 根据关键字 根据回调函数进行删除
*@param: LLIST *llist 目标链表
* const void *key 关键字
* llist_cmp *cmp 回调函数
*@retvalue: int 状态值
**/
int llist_delete(LLIST* llist, const void* key,llist_cmp*cmp)
{
struct llist_node_st *node;
node = find_(llist,key,cmp);
if(node == &llist->head)
return -1; // 不删除头结点
node->prev->next = node->next;
node->next->prev = node->prev;
///free(node->data);
free(node);
return 0;
}
链表的 寻找 特定元素
操作：根据 关键字 寻找 特定 元素
/*
*@brief: 在 目标链表 根据关键字 根据回调函数进行删除
*@param: LLIST *llist 目标链表
* const void *key 关键字
* llist_cmp *cmp 回调函数
* void *data 所寻找的数据
*@retvalue: int 状态值
**/
int llist_fetch(LLIST* llist, const void* key,llist_cmp* cmp,void* data)
{
struct llist_node_st *node;
node = find_(llist,key,cmp);
if(node == &llist->head)
return -1; // 不删除头结点
node->prev->next = node->next;
node->next->prev = node->prev;
if(data != NULL)
memcpy(data,node->data,llist->size);
//free(node->data);
free(node);
return 0;
}
函数指针的定义和插入
类似类的方法操作，可以用函数指针来完成操作
typedef struct llist_head
{
int size;
struct llist_node_st head;
int (*insert)(struct llist_head*,const void*,int);
// 函数指针 RetValueType (Pointer* Force Transfer)(Parameter List);
}LLIST;
则 在创建时就可以
int llist_insert(LLIST *llist, const void *data,int mode); // 由于 循环列表 则只设置 两
种模式 头插 或者 尾插
LLIST *llist_create(int initsize)
{
LLIST *new;
new = malloc(sizeof(*new));
if(new == NULL)
return NULL;
new->size = initsize;
// new->head.data= NULL;
new->head.prev = &new->head;
new->head.next = &new->head;
//！！！
new->insert = llist_insert;
//双向循环链表 只有头，则 自己指向自己
return new;
}
if(new == NULL)
return NULL;
new->size = initsize;
// new->head.data= NULL;
new->head.prev = &new->head;
new->head.next = &new->head;
//！！！
new->insert = llist_insert;
//双向循环链表 只有头，则 自己指向自己
return new;
}
写在最后
加油鼓劲，一切都是最好的安排！