数据结构--带控制信息的双向链表

带控制信息的双向链表

双向链表的主要操作

链表的初始化
头部插入
尾部插入
头部删除
尾部删除
插入到指定结点的前面
插入到指定结点的后面
删除双向链表中的结点
打印双端链表
.......还有很多...

双向链表的声明

源代码请看dlist.h

//防止头文件的内容被重复包含
#ifndef _DLIST_H_
#define _DLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include "tools.h"

struct Dlist;
typedef struct Dlist Dlist;             //双端链表控制信息

struct Dlist_node;
typedef struct Dlist_node Dlist_node;   //双短链表节点信息

typedef unsigned char Boolean;          //C语言中的布尔值

typedef void (*Print_func)(void *value);
typedef Boolean (*Match_func)(const void *value1, const void *value2);
//typedef void (*)(void *value) Print_func;
#if 1
//链表控制信息
struct Dlist{   
    struct Dlist_node *head;   //指向双端链表的头节点
    struct Dlist_node *tail;   //指向双端链表的尾节点
    int               count;   //双端链表中的元素个数

    //释放链表节点数据域
    void    (*free)(void *ptr);    //void (*)(void *ptr)  free;
    //匹配链表节点数据域
    Boolean (*match)(const void *value1, const void *value2);
    //拷贝链表节点数据域
    void    *(*copy_node)(void *src);
};

//链表节点信息
struct Dlist_node{
    struct Dlist_node *prev;    //前一个节点指针
    struct Dlist_node *next;    //后一个节点指针
    void              *data;    //数据（指针）
};

#define ZERO      (0)
#define TRUE      (1)
#define FALSE     (0)
#define ONLY_ONE  (1)


#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define next_node(node)  ((node)->next)
#define prev_node(node)  ((node)->prev)
#define node_data(node)  ((node)->data)

#endif
//双端链表的接口(ADT)
Dlist      *init_dlist(Match_func match_func)                    ;    //链表的初始化
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)                 ;    //得到链表元素个数
Boolean find_dlist_value(Dlist *dlist, const void *value);//判断指定元素是否在链表中
Boolean delete_dlist_value(Dlist *dliat, void *value);//删除指定值的结点


//
void print_int(void *value);    //打印整形值
 
#endif

函数的实现

源代码请看dlist.c

#include "dlist.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--;

    }
    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){
        printf("\n");
        return ;
    }

    for(p_node = dlist->head; p_node ; p_node = p_node->next){
        print(p_node->data);
    }
    printf("\n");
}


Dlist *init_dlist(Match_func match_func)    //双端链表的初始化
{
    Dlist *dlist = NULL; 
   
    dlist = (Dlist *)Malloc(sizeof(Dlist));
    bzero(dlist, sizeof(Dlist));   //对dlist进行初始化
    dlist->match = match_func;
    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;
}

Boolean delete_dlist_value(Dlist *dlist, void *data)
{
    Dlist_node *node = NULL;
    if(dlist == NULL || data == NULL){
        return FALSE;
    }
    
    for(node = dlist->head; node != NULL; node = node->next){
        if(dlist->match != NULL){
            if(dlist->match(node->data, data) == TRUE){
                remove_dlist_node(dlist, node, NULL);
                return TRUE;
            }
        }else{
            if(node->data == data){
                remove_dlist_node(dlist, node, NULL);
                return TRUE;
            }
        }
    }

    return FALSE;
}

Boolean find_dlist_value(Dlist *dlist, const void *data)
{
    Dlist_node *node = NULL;
    if(dlist == NULL|| data == NULL){
        return FALSE;
    }
    
    for(node = dlist->head; node != NULL; node = node->next){
        if(dlist->match != NULL){
            if(dlist->match(node->data, node) == TRUE){
                return TRUE;
            }
        }else{
            if(node->data == data){
                return TRUE;
            }
        }
    }
    
    return FALSE;
}