双向链表

链表是平时开发工作中频繁使用的数据结构,本文提供一个通用性的链表数据结构,源码拷贝就可以直接使用。参考linux内核链表实现。

代码

// list.h
/*********************************************************************************************
* 版权所有 :  
* 文件名称 :  list.h
* 文件标识 :  无
* 内容摘要 :  实现队列功能
* 其它说明 :  其它内容的说明
* 当前版本 :  V1.00
* 作    者 :  
* 完成日期 :  2021-12-16
*********************************************************************************************/ 
#ifndef __LIST_H__
#define __LIST_H__

/***************************************************************/
/* 类型定义                                                    */
/***************************************************************/
typedef struct list {
    struct list *next; 
    struct list *prev;
}List;

/***************************************************************/
/* 宏定义                                                      */
/***************************************************************/
#define list_entry(ptr, type, member) \
            container_of(ptr, type, member)

#define container_of(ptr, type, member) ({          \
            const typeof(((type *)0)->member)*__mptr = (ptr);    \
            (type *)((char *)__mptr - offsetof(type, member)); })
             
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list name = LIST_HEAD_INIT(name)

#define list_for_each(pos, head) \
            for(pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)

/***************************************************************/
/* 函数声明                                                    */
/***************************************************************/
extern void init_list_head(struct list *list);
extern void list_add(struct list *new, struct list *prev, struct list *next);
extern void list_add_head(struct list *new, struct list *head);
extern void list_add_tail(struct list *new, struct list *head);
extern void list_del(struct list *entry);
extern void list_del_entry(struct list *prev, struct list *next);
extern int list_num(struct list *head);
extern int list_empty(const struct list *head);

#endif
// list.c
/*********************************************************************************************
* 版权所有 :  
* 文件名称 :  list.c
* 文件标识 :  无
* 内容摘要 :  实现队列功能
* 其它说明 :  其它内容的说明
* 当前版本 :  V1.00
* 作    者 :   
* 完成日期 :  2021-12-16
*********************************************************************************************/ 
#include "list.h"

/******************************************************************************
* 函数名称: init_list_head
* 功能描述: 初始化链表
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
void init_list_head(struct list *list)
{
    list->next = list;
    list->prev = list;
}

/******************************************************************************
* 函数名称: list_add
* 功能描述: 模块内部函数,在两个元素当中添加一个新元素
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
void list_add(struct list *new, struct list *prev, struct list *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

/******************************************************************************
* 函数名称: list_add_head
* 功能描述: 向链表头部添加元素
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
void list_add_head(struct list *new, struct list *head)
{
    list_add(new, head, head->next);
}

/******************************************************************************
* 函数名称: list_add_tail
* 功能描述: 向链表尾部添加元素
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
void list_add_tail(struct list *new, struct list *head)
{
    list_add(new, head->prev, head); 
}

/******************************************************************************
* 函数名称: list_del
* 功能描述: 删除元素
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
void list_del(struct list *entry)
{    
    list_del_entry(entry->prev, entry->next);
    entry->next = entry;
    entry->prev = entry;
}

/******************************************************************************
* 函数名称: list_del_entry
* 功能描述: 模块内部函数,删除两个元素之间的一个元素
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
void list_del_entry(struct list *prev, struct list *next)
{
    next->prev = prev;
    prev->next = next;
}

/******************************************************************************
* 函数名称: list_num
* 功能描述: 获取链表中元素的个数
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
int list_num(struct list *head)
{
    struct list *pos = (struct list *)0;
    int num = 0;
    
    list_for_each(pos, head)
    {
        num++;
    }
    
    return num;
}    

/******************************************************************************
* 函数名称: list_empty
* 功能描述: 查看链表是否为空
* 其它说明: 无                                                           
* 修改记录: 修改日期         修改人         修改内容
*           2021-12-16       创建
******************************************************************************/
int list_empty(const struct list *head)
{
    return head->next == head;
}

使用方法

#include <stdio.h>
#include "list.h"
#include "queue.h"

typedef struct node
{
    int data;
    List list;
}Node;

Node* init_node(int data)
{
    Node *pnode = malloc(sizeof(Node));
    pnode->data = data;
    init_list_head(&pnode->list);
    return pnode;
}

int main()
{
    LIST_HEAD(head);
    
    Node *node1 = init_node(1);
    Node *node2 = init_node(2);
    Node *node3 = init_node(3);
    Node *node4 = init_node(4);
    
    list_add_tail(&node1->list, &head);
    list_add_tail(&node2->list, &head);
    list_add_tail(&node3->list, &head);
    list_add_tail(&node4->list, &head);
    
    List *pos = NULL;
    Node *node = NULL;
    list_for_each(pos, &head)
    {
        node = list_entry(pos, Node, list);
        printf("%d ", node->data);
    }
    printf("num= %d\n\n", list_num(&head));
    
    list_del(head.next);
    list_for_each(pos, &head)
    {
        node = list_entry(pos, Node, list);
        printf("%d ", node->data);
    }
    printf("\n\n");
    
    return 0;
}

 

上一篇:CF1628A-Meximum Array【二分】


下一篇:halcon彩色转QImage彩色