4.数据结构之通用链表实现

淡淡的烟草味﹌ 2022-08-09 11:47 161阅读 0赞

# 数据结构之通用链表实现 #

## 通用链表简介 ##

在redis数据库和acl库中，通用双端链表的应用随处可见。之前我们接触过链表的相关操作，前两章：《数据结构之单链表》以及《数据结构之链表面试题》接触了不少链表的问题，但是对于问题的处理总是无法逃脱类型的限定，所以我们需要将类型的问题从数据结构中剥离出来。具体的类型在数据结构的使用者进行具体的限定。好吧，我们首先来看看头文件dlist.h中关于链表节点结构的定义和接口的声明：

//防止头文件的内容被重复包含
    #ifndef _DLIST_H_
    #define _DLIST_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <strings.h>
    
    #define ZERO (0)
    #define ONLY_ONE (1)
    #define TRUE (1)
    #define FALSE (0)
    
    struct Dlist;
    typedef struct Dlist Dlist;             //双端链表控制信息
    
    struct Dlist_node;
    typedef struct Dlist_node Dlist_node;   //双短链表节点信息
    
    typedef unsigned char Boolean;          //C语言中的布尔值
    
    //链表控制信息
    struct Dlist{   
        struct Dlist_node *head;   //指向双端链表的头节点
        struct Dlist_node *tail;   //指向双端链表的尾节点
        int               count;   //双端链表中的元素个数
    
        //释放链表节点数据域
        void    (*free)(void *ptr);    //void (*)(void *ptr) free;
        //匹配链表节点数据域
        Boolean (*match)(void *val1, void *val2);
        //拷贝链表节点数据域
        void    *(*copy_node)(void *src);
    };
    
    //链表节点信息
    struct Dlist_node{
        struct Dlist_node *prev;    //前一个节点指针
        struct Dlist_node *next;    //后一个节点指针
        void              *data;    //数据（指针）
    };
    
    typedef void (*Print_func)(void *value);
    
    //双端链表的接口(ADT)
    Dlist      *init_dlist(void)                    ;    //链表的初始化
    void       destroy_dlist(Dlist **dlist)         ;    //链表的销毁
    Boolean    push_front(Dlist *dlist, void *value);    //链表头部插入
    Boolean    push_back(Dlist *dlist, void *value) ;    //链表尾部插入
    Boolean    pop_back(Dlist *dlist)               ;    //链表尾部删除
    Boolean    pop_front(Dlist *dlist)              ;    //链表头部删除
    Boolean    insert_prev_node(Dlist *dlist,
                 Dlist_node *node, void *value)     ;    //插入指定节点的前边
    Boolean    insert_next_node(Dlist *dlist,
                 Dlist_node *node, void *value)     ;    //插入指定节点的后边
    Boolean    remove_dlist_node(Dlist *dlist,
                 Dlist_node *node, void **value)             ;    //删除链表中的节点 
    void       print_dlist(Dlist *dlist, Print_func print)   ;    //打印双端链表
    Dlist_node  *get_index_node(Dlist *dlist, int index)     ;    //得到下标为index的链表元素
    Boolean    get_front(Dlist *dlist, void **value)         ;    //得到链表头节点的数据域
    Boolean    get_tail(Dlist *dlist, void **value)          ;    //得到链表尾节点的数据域
    int        get_dlist_count(Dlist *dlist)                 ;    //得到链表元素个数
    
    
    //
    void print_int(void *value);    //打印整形值
    
    #endif

在参数传递中我们对于数据的传递都是采用的指针的传递，并且都是void \*类型，这样就可以接受任意类型的数据。在结构上我们依然设计了**链表控制信息**和**链表节点信息**两部分，这里我们使用了**函数指针**的技术，函数指针可以让该指针指向相同类型的函数（返回值和参数列表相同）。首先我们得定义出函数指针的这种类型：

typedef void (*Print_func)(void *value);

这就是说Print\_func是一种类型，这种类型可以定义相关指针，该指针可以指向型如  
void func1(void \*value)类型的函数。

关于链表接口的实现我们在dlist.c中进行实现，代码如下所示：

#include "dlist.h"
    #include "tools.h"
    
    
    void       destroy_dlist(Dlist **dlist)    //链表的销毁
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || *dlist == NULL){
            return ;
        }
    
        p_node = (*dlist)->head;
    
        while((*dlist)->head != NULL){
            (*dlist)->head = p_node->next;
            if((*dlist)->free != NULL){
                (*dlist)->free(p_node->data);
            }
            free(p_node);
            p_node = (*dlist)->head;
        }
        free(*dlist);
        *dlist = NULL;
    
    }
    
    static Dlist_node *buy_node(void)
    {
        Dlist_node *result = (Dlist_node *)Malloc(sizeof(Dlist_node));
        bzero(result, sizeof(Dlist_node));
    
        return result;
    }
    
    Boolean    push_front(Dlist *dlist, void *value)    //链表头部插入
    {
        Dlist_node *node = NULL;
    
        if(dlist == NULL || value == NULL){
            return FALSE;
        }
    
        node = buy_node();
        node->data = value;
    
        if(dlist->count == ZERO){    //链表没有元素时
            dlist->head = dlist->tail = node;
        }else{
            node->next = dlist->head;
            dlist->head->prev = node;
            dlist->head = node;
        }
        dlist->count++;
        return TRUE;
    }
    
    Boolean    push_back(Dlist *dlist, void *value)    //链表尾部插入
    {
        Dlist_node *node = NULL;
    
        if(dlist == NULL || value == NULL){
            return FALSE;
        }
    
        node = buy_node();
        node->data =value;
    
        if(dlist->count == ZERO){
            dlist->head = dlist->tail = node;
        }else{
            node->prev = dlist->tail;
            dlist->tail->next = node;
            dlist->tail = node;
        }
        dlist->count++;
        return TRUE;
    }
    Boolean    pop_back(Dlist *dlist)    //链表尾部删除
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || dlist->count == ZERO){
            return FALSE;
        }
    
        p_node = dlist->tail;
    
        if(dlist->count == ONLY_ONE){
            dlist->head = dlist->tail = NULL;
        }else{
            dlist->tail = p_node->prev;
            dlist->tail->next = NULL;
        } 
        if(dlist->free != NULL){
            dlist->free(p_node->data);
        }
        free(p_node);
        dlist->count--;
        return TRUE;
    }
    Boolean    pop_front(Dlist *dlist)    //链表头部删除
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || dlist->count == ZERO){
            return FALSE;
        }
    
        p_node = dlist->head;
    
        if(dlist->count == ONLY_ONE){
            dlist->head = dlist->tail = NULL;
        }else{
            dlist->head = p_node->next;
            dlist->head->prev = NULL;
        }
        if(dlist->free != NULL){
            dlist->free(p_node->data);
        }
        free(p_node);
        dlist->count--;
        return TRUE;
    }
    
    Dlist_node *get_index_node(Dlist *dlist, int index)   //得到下标为index的链表节点
    {
        Dlist_node *node = NULL;
        int move_count = 0;
    
        if(dlist == NULL || dlist->count == ZERO
        || index < ZERO || index >= dlist->count){
             return NULL;
        }
    
        node = dlist->head;
        move_count = index;
    
        //找到指定下标元素
        while(move_count--){
            node = node->next;
        }
    
        return node;
    }
    
    Boolean    remove_dlist_node(Dlist *dlist, 
                   Dlist_node *node, void **value)    //删除指定节点
    {
        if(dlist == NULL || node == NULL){
            return FALSE;
        }
    
        if(value != NULL){    //取得被删除节点数据域信息
            *value = node->data;
        }
    
        if(node->next == NULL){    //node在尾部
            pop_back(dlist);
        }else if(node->prev == NULL){
            pop_front(dlist);
        }else{
            node->prev->next = node->next;
            node->next->prev = node->prev;
            if(dlist->free != NULL){
                dlist->free(node->data); 
            }
            free(node);   //Free(node)
            dlist->count--;
    
            /* * * #define Free(node) (node->prev->next = node->next;) \ * (node->next->prev = node->prev;) \ * * * */
        }
        return TRUE;
    }
    
    Boolean    insert_next_node(Dlist *dlist,
                   Dlist_node *node, void *value)    //插入到指定节点的后边
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || node == NULL || value){
            return FALSE;
        }
    
        p_node = buy_node();
        p_node->data = value;
    
        p_node->prev = node;
        p_node->next = node->next;
        if(node->next == NULL){
            dlist->tail = p_node;
        }else{
            node->next->prev = p_node;
        }
        node->next = p_node;
        dlist->count++;
        return TRUE;
    }
    
    Boolean    insert_prev_node(Dlist *dlist,
                   Dlist_node *node, void *value)    //插入到指定节点的前边
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || node == NULL || value == NULL){
            return FALSE;
        }
    
        p_node = buy_node();
        p_node->data = value;
    
        //进行插入操作
        p_node->next = node;
        p_node->prev = node->prev;
        if(node->prev == NULL){    //node为第一个节点
            dlist->head = p_node;
        }else{    //node不是第一个节点
            node->prev->next = p_node;
        }
        node->prev = p_node;
        dlist->count++; 
        return TRUE;
    }
    
    void print_int(void *value)
    {
        printf("%d ", *(int *)value);
    }
    
    void print_dlist(Dlist *dlist, Print_func print)    //打印链表信息
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || dlist->count == ZERO){
            return ;
        }
    
        for(p_node = dlist->head; p_node ; p_node = p_node->next){
            print(p_node->data);
        }
        printf("\n");
    }
    
    
    Dlist *init_dlist(void)    //双端链表的初始化
    {
        Dlist *dlist = NULL; 
    
        dlist = (Dlist *)Malloc(sizeof(Dlist));
        bzero(dlist, sizeof(Dlist));   //对dlist进行初始化
    
        return dlist;
    }
    
    Boolean get_front(Dlist *dlist, void **value)
    {
        if(dlist == NULL || dlist->count == ZERO){
            return FALSE;
        }
    
        if(value != NULL){
            *value = dlist->head->data;
        }
        return TRUE;
    }
    
    Boolean get_tail(Dlist *dlist, void **value)
    {
        if(dlist == NULL || dlist->count == ZERO){ 
            return FALSE;
        }
    
        if(value != NULL){
             *value = dlist->tail->data;
        }
        return TRUE;
    }
    
    int get_dlist_count(Dlist *dlist)
    {
        if(dlist == NULL){
            return -1;
        }
        return dlist->count;
    }

在dlist.c文件中我们包含了一个tools.h,这个是我们的工具类文件，其中包含了对内存和简单算法的相关接口，分为tools.h和tools.c两个文件：

#ifndef _TOOLS_H_
    #define _TOOLS_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    void *Malloc(size_t size);   //申请堆空间
    void swap(void *a, void *b, int length);   //交换任意两个值
    #endif

对应的tools.c文件：

#include "tools.h"
    
    void *Malloc(size_t size)
    {
        void *result = malloc(size);
        if(result == NULL){ 
            fprintf(stderr, "the memory is full!\n");
            exit(1);
        } 
        return result;
    }
    
    void swap(void *a, void *b, int length)
    {
        void *temp = malloc(length);
        memcpy(temp, a, length);
        memcpy(a, b, length);
        memcpy(b, temp, length);
    
        free(temp);
    }

关于通用链表的测试代码入下所示：

//通用链表测试代码
    #include <stdio.h>
    #include "dlist.h"
    
    int main(int argc, char **argv)
    {
        Dlist *dlist1 = NULL;
        int array[] = {
       12, 23, 34, 4, 1, 33, 24};
        int array1[] = {
       1, 33, 44, 2, 33, 222, 444};
        int arr_len = sizeof(array) / sizeof(array[0]);
        int i  = 0;   
    
        dlist1 = init_dlist();   //双端链表的初始化
        //初始化完成后，如果有需要，应修改free、match和dup的指向
    
        for(i = 0; i < arr_len; ++i){
            push_back(dlist1, &array[i]);       
        }
    
        print_dlist(dlist1, print_int);
        pop_back(dlist1);
    
        push_front(dlist1, &array1[2]);
    
    
        print_dlist(dlist1, print_int);
    
        destroy_dlist(&dlist1);    //双端链表的销毁
        return 0;
    }

通用链表在redis数据库中具有着非常多的应用：  
可以作为底层容器的实现，用来改造，添加保存节点长度的字段。或者说python的基本数据类型列表、元组的底层容器。以及后期我们将要使用适配器模式对通用双端链表进行封装，创建出栈和队列。

敬请期待！