C杂讲 双向循环链表

目录

知识点1【双向循环链表】

知识点2【双向链表的尾部插入】

知识点3【双向链表的遍历】

知识点3【双向链表查询某个节点】

知识点4【双向链表删除指定节点】

知识点4【双向链表释放链表节点】

知识点5【Linux内核链表】

知识点1【双向循环链表】

知识点2【双向链表的尾部插入】

STU* insert_link(STU *head, STU tmp)
{
    //为插入的节点申请空间
    STU *pi = (STU *)calloc(1,sizeof(STU));
    if(pi == NULL)
    {
        perror("calloc");
        return head;
    }
    *pi = tmp;

    //尾部插入
    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;
}

知识点3【双向链表的遍历】

void printf_link(STU *head)
{
    //判断链表是否存在
    if(NULL == head)
    {
        printf("链表不存在\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;
}

知识点3【双向链表查询某个节点】

STU *search_link(STU *head, int num)
{
    //判断链表是否存在
    if(NULL == head)
    {
        printf("链表不存在\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("未找到相关节点\n");
            return NULL;
        }
    }
    return NULL;
}

知识点4【双向链表删除指定节点】

STU* delete_link(STU *head, int num)
{
    //判断链表是否存在
    if(NULL == head)
    {
        printf("链表不存在\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)//删除头结点
            {
                if(pb->next == pb)//链表只有一个节点
                {
                    head = NULL;  
                }
                else//链表不止一个节点
                {
                    head->pre->next = head->next;
                    head->next->pre = head->pre;
                    head = head->next;
                }
                free(pb);
                return head;
            }
            else//删除、中尾部节点
            {
                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("未找到相关节点\n");
            return NULL;
        }
    }
    return head;
}

知识点4【双向链表释放链表节点】

STU* free_link(STU *head)
{
    //判断链表是否存在
    if(NULL == head)
    {
        printf("链表不存在\n");
        return head;
    }
    else
    {
        STU *pb = head;
        head->pre->next = NULL;
        while(pb != NULL)
        {
            head = head->next;
            free(pb);
            pb = head;
        }
    }

    return head;
}

知识点5【Linux内核链表】

list.h

/**
 * 简易版双向循环链表（参考Linux内核链表实现方式）
 * @auther: BrightSKY
 * @function: 未指定数据端，可以挂载各种类型数据，实现了链表任意节点位置的插入和删除，任意节点的替换，提供正向反向的遍历方式
 * @extend: 欢迎根据已有API进行功能扩展，可以实现扩展多链表操作，链表检索和排列等算法
 */
#ifndef __LIST_H__
#define __LIST_H__

/**
 * 新节点初始化宏定义
 * @name: 需要初始化的节点
 */
#define LIST_NODE_INIT(name) {&(name), &(name)}

/**
 * 计算指针域位于宿主结构的偏移量
 * @type: 宿主结构体类型
 * @member: 指针域成员名
 */
#define offsetof(type, member) ((char *) &((type *)0)->member)

/**
 * 已知宿主结构体类型、指针域成员名、指针域地址反推宿主结构体地址
 * @ptr: 指针域地址
 * @type: 宿主结构体类型
 * @member: 指针域成员名
 */
#define list_entry(ptr, type, member) ({                                \
const typeof( ((type *)0)->member ) *__mptr = (ptr);                    \
(type *)( (char *)__mptr - offsetof(type,member) );})

/**
 * 链表正向遍历，不包含头节点
 * @pos: 指向链表节点的指针，类似于c++迭代器
 * @head: 链表头节点
 * @member: 指针域成员名
 */
#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))

/**
 * 链表反向遍历，不包含头节点
 * @pos: 指向链表节点的指针，类似于c++迭代器
 * @head: 链表头节点
 * @member: 指针域成员名
 */
#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))

/**
 * 链表指针域数据结构
 */
typedef struct list_node{
    struct list_node *next, *prev;  
}list_node;

/**
 * API方法
 */
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

/**
 * 简易版双向循环链表（参考Linux内核链表实现方式）
 * @auther: BrightSKY
 * @function: 未指定数据端，可以挂载各种类型数据，实现了链表任意节点位置的插入和删除，任意节点的替换，提供正向反向的遍历方式
 * @extend: 欢迎根据已有API进行功能扩展，可以实现扩展多链表操作，链表检索和排列等算法
 */
#include "list.h"
/**
 * 链表任意位置插入的底层实现
 * @new: 新链表节点地址
 * @prev: 新节点插入位置的前一节点地址
 * @next: 新节点插入位置的下一节点地址
 */
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;
}
/**
 * 插入节点：新节点在指定节点后方位置插入
 * @new: 新链表节点地址
 * @node: 指定节点地址，新节点将在此节点后方插入
 */
void list_push_node_back(list_node *new, list_node *node){
    __list_push(new, node, node->next);
}
/**
 * 插入节点：新节点在指定节点前方位置插入
 * @new: 新链表节点地址
 * @node: 指定节点地址，新节点将在此节点前方插入
 */
void list_push_node_front(list_node *new, list_node *node){
    __list_push(new, node->prev, node);
}
/**
 * 删除节点：指定节点移除链表
 * @node: 指定节点地址，即将删除的节点
 */
void list_del_node(list_node *node){
    node->next->prev = node->prev;
    node->prev->next = node->next;
}
/**
 * 替换节点：用新节点替换旧节点
 * @new: 新节点地址
 * @old: 旧节点地址
 */
void list_replace(list_node *new, list_node *old){
    list_del_node(old);
    list_push_node_back(new, old->prev);
}

main.c

/**
 * 简易版双向循环链表 使用例程（Demo）
 * @auther: BrightSKY
 * @function: 未指定数据端，可以挂载各种类型数据，实现了链表任意节点位置的插入和删除，任意节点的替换，提供正向反向的遍历方式
 * @extend: 欢迎根据已有API进行功能扩展，可以实现扩展多链表操作，链表检索和排列等算法
 */
#include "list.h"               
#include "stdio.h"

/**
 * 自定义链表结构（包含指针域与数据域，指针域需要使用list_node）
 * @data: 自定义的数据域，可以是任意多个数据和类型
 * @list_node: 指针域，双向循环链表的操作核心
 */
typedef struct my_list{
    int data;
    list_node list;
}my_list;

/**
 * 创建链表头，指针域初始化可以使用LIST_NODE_INIT宏进行初始化
 */
my_list head = {0, LIST_NODE_INIT(head.list)};

/**
 * 主函数，本例程直接以最简单的方式进行链表的插入和遍历，便于大家进行学习
 */
int main(int argc, char const *argv[])
{
    /* 创建节点 */
    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)};
    
    /* 头插法插入节点 */
    list_push_node_back(&node1.list, &head.list);
    list_push_node_back(&node2.list, &head.list);

    /* 尾插法插入节点 */
    list_push_node_front(&node3.list, &head.list);

    /* 创建链表迭代器 */
    my_list *n = NULL;

    /* 调用链表正向便利，使用迭代器进行访问并输出 */
    list_for_each_entry(n, &head, list)
    {
        printf("n = %d\n", n->data);
    }

    printf("-------------------------\n");

    /* 删除头节点指向的节点 */
    list_del_node(head.list.next);

    /* 调用链表反向便利，使用迭代器进行访问并输出 */
    list_for_each_entry_reverse(n, &head, list)
    {
        printf("n = %d\n", n->data);
    }
    

    return 0;
}