双向链表

最近要做个OnlineJudge系统，其中要管理许多用户提交的文件。为了效率我还是决定以文件的形式存储。所以后台数据结构我选择双向链表。在图书馆借到了李先静先生编著的《系统程序员成长计划》收获很多。下面链表的实现基本是参照这本书的设计思想。有兴趣的可以去看看这本书！代码如下：

list.h

#ifndef DLIST_H
#define DLIST_H

#ifdef __cplusplus
extern "C" {
#endif /*__cplusplus*/

typedef enum _DListRet {
    DLIST_RET_OK,
    DLIST_RET_OOM,
    DLIST_RET_STOP,
    DLIST_RET_PARAMS,
    DLIST_RET_FAIL
}DListRet;

struct _DList;
typedef struct _DList DList;

typedef void (*DListDataDestroyFunc)(void* ctx, void* data);
typedef int (*DListDataCompareFunc)(void* ctx, void* data);
typedef DListRet (*DListDataVisitFunc)(void* ctx, void* data);

DList* dlist_create(DListDataDestroyFunc destroy, void* ctx);

DListRet dlist_insert(DList* thiz, size_t index, void* data);
DListRet dlist_prepend(DList* thiz, void* data);
DListRet dlist_append(DList* thiz, void* data);
DListRet dlist_delete(DList* thiz, size_t index);
DListRet dlist_get_by_index(DList* thiz, size_t index, void** data);
DListRet dlist_set_by_index(DList* thiz, size_t index, void* data);
size_t dlist_length(DList* thiz);
int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx);
DListRet dlist_traverse(DList* thiz, DListDataVisitFunc visit, void* ctx);

void dlist_destroy(DList* thiz);

#ifdef __cplusplus
}
#endif/*__cplusplus*/

#endif/*DLIST*/


list.c

 

#include <stdlib.h>
#include "dlist.h"

typedef struct _DListNode {
    struct _DListNode* prev;
    struct _DListNode* next;
    
    void* data;
}DListNode;

struct _DList {
    DListNode* first;
    DListDataDestroyFunc destroy;
    void* data_destroy_ctx;
};

static DListNode* dlist_node_create(void* data) {
    DListNode* node = malloc(sizeof(DListNode));

    if (node != NULL) {
        node->prev = NULL;
        node->next = NULL;
        node->data = data;
    }

    return node;
}

static void dlist_destroy_data(DList* thiz, void* data) {
    if (thiz->destroy != NULL) {
        thiz->destroy(thiz->data_destroy_ctx, data);
    }
    
    return ;
}

static void dlist_node_destroy(DList*thiz, DListNode* node) {
    if (node != NULL) {
        node->prev = NULL;
        node->next = NULL;
        dlist_destroy_data(thiz, node->data);
        free(node);
    }

    return;
}

DList* dlist_create(DListDataDestroyFunc destroy, void* ctx) {
    DList* thiz = malloc(sizeof(DList));
    
    if (thiz != NULL) {
        thiz->first = NULL;
        thiz->destroy = destroy;
        thiz->data_destroy_ctx = ctx;
    }

    return thiz;
}

static DListNode* dlist_get_node(DList* thiz, size_t index, int fail_return_last) {
    DListNode* iter = thiz->first;
    
    while (iter != NULL && iter->next != NULL && index > 0) {
        iter = iter->next;
        index--;
    }
    
    if (!fail_return_last) {
        iter = index > 0 ? NULL : iter;
    }

    return iter;
}

DListRet dlist_insert(DList* thiz, size_t index, void* data) {
    DListNode* node = NULL;
    DListNode* cursor = NULL;
    
    if ((node = dlist_node_create(data)) == NULL) {
        return DLIST_RET_OOM;
    }

    if (thiz->first == NULL) {
        thiz->first = node;
        return DLIST_RET_OK;
    }

    cursor = dlist_get_node(thiz, index, 1);

    if (index < dlist_length(thiz)) {
        if (thiz->first == cursor) {
            thiz->first = node;
        } else {
            cursor->prev->next = node;
            node->prev = cursor->prev;
        }
        node->next = cursor;
        cursor->prev = node;
    } else {
        cursor->next = node;
        node->prev = cursor;
    }
    
    return DLIST_RET_OK;
}

DListRet dlist_prepend(DList* thiz, void* data) {
    return dlist_insert(thiz, 0, data);
}

DListRet dlist_append(DList* thiz, void* data) {
    return dlist_insert(thiz, -1, data);
}

DListRet dlist_delete(DList* thiz, size_t index) {
    DListNode* cursor = dlist_get_node(thiz, index, 0);

    if (cursor != NULL) {
        if (cursor == thiz->first) {
            thiz->first = cursor->next;
        }

        if (cursor->next != NULL) {
            cursor->next->prev = cursor->prev;
        }
        
        if (cursor->prev != NULL) {
            cursor->prev->next = cursor->next;
        }
        dlist_node_destroy(thiz, cursor);
    }

    return DLIST_RET_OK;
}

DListRet dlist_get_by_index(DList* thiz, size_t index, void** data) {
    DListNode* cursor = dlist_get_node(thiz, index, 0);

    if (cursor != NULL) {
        *data = cursor->data;
    }
    
    return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

DListRet dlist_set_by_index(DList* thiz, size_t index, void* data) {
    DListNode* cursor = dlist_get_node(thiz, index, 0);

    if (cursor != NULL) {
        cursor->data = data;
    }
    return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

size_t dlist_length(DList* thiz) {
    size_t length = 0;
    DListNode* iter = thiz->first;

    while (iter != NULL) {
        length++;
        iter = iter->next;
    }

    return length;
}


void dlist_destroy(DList* thiz) {
    DListNode* iter = thiz->first;
    DListNode* next = NULL;

    while (iter != NULL) {
        next = iter->next;
        dlist_node_destroy(thiz, iter);
        iter = next;
    }

    thiz->first = NULL;
    free(thiz);

    return;
}

int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx) {
    int i = 0;
    DListNode* iter = thiz->first;
        
    while (iter != NULL) {
        if (cmp(iter->data, ctx)) {
            break;
        }
        i++;
        iter = iter->next;
    }

    return i;
}
DListRet dlist_traverse(DList* thiz, DListDataVisitFunc visit, void* ctx) {
    DListNode* iter = thiz->first;
    DListRet ret = DLIST_RET_OK;

    while (iter != NULL && ret == DLIST_RET_OK) {
        ret = visit(ctx, iter->data);

        iter = iter->next;
    }
    return DLIST_RET_OK;
    
}


测试程序main.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "dlist.h"
#include <assert.h>
    
static DListRet str_upper(void* ctx, void* data) {
    char* p = (char*)data;

    if (p != NULL) {
        while (*p != '\0') {
            if (islower(*p)) {
                *p = toupper(*p);
            }
            p++;
        }
    }
    
    return DLIST_RET_OK;
}

static DListRet int_print(void* ctx, void* data) {
    printf("%d ", (int)data);

    return DLIST_RET_OK;
}
static DListRet str_print(void* ctx, void* data) {
    printf("%s ", (char*)data);

    return     DLIST_RET_OK;
}

void data_free(void* ctx, void* data) {
    free(data);
}

static void demo_heap() {
    DList* dlist = dlist_create(data_free, NULL);

    dlist_append(dlist, strdup("it"));
    dlist_append(dlist, strdup("is"));
    dlist_append(dlist, strdup("heap"));

    dlist_traverse(dlist, str_upper, NULL);
    dlist_traverse(dlist, str_print, NULL);

    dlist_destroy(dlist);
}

typedef struct _MaxCtx {
    int is_first;
    int max;
}MaxCtx;

static DListRet int_get_max(void* ctx, void* data) {
    MaxCtx* max_ctx = ctx;
    
    if (max_ctx->is_first) {
        max_ctx->is_first = 0;
        max_ctx->max = (int)data;
    } else if(max_ctx->max < (int)data) {
        max_ctx->max = (int)data;
    }

    return DLIST_RET_OK;
}

static DListRet int_get_sum(void* ctx, void* data) {
    long long* result = ctx;
    *result += (int)data;
    
    return DLIST_RET_OK;
}
void test_int(void) {
    int i = 0;
    void *p = NULL;
    long long sum = 0;
    MaxCtx max_ctx = {.is_first = 1, 0};
    
    DList* dlist = dlist_create(NULL, NULL);
    
    for (i = 0; i < 5; i ++) {
        assert(dlist_append(dlist, (void*)i) == DLIST_RET_OK);
    }
    for (i = 0; i < 5; i ++) {
        assert(dlist_prepend(dlist, (void*)i) == DLIST_RET_OK);
    }
    
    assert(dlist_traverse(dlist, int_print, NULL) == DLIST_RET_OK);
    assert(dlist_get_by_index(dlist, 0, &p) == DLIST_RET_OK);    
    printf("\n%d\n", (int*)p);
    assert(dlist_set_by_index(dlist, 3, (void*)i) == DLIST_RET_OK);

    assert(dlist_get_by_index(dlist, 3, &p) == DLIST_RET_OK);    
    printf("\n%d\n", (int*)p);
    assert(dlist_delete(dlist, 0) == DLIST_RET_OK);    
    assert(dlist_delete(dlist, 3) == DLIST_RET_OK);
    assert(dlist_traverse(dlist, int_print, NULL) == DLIST_RET_OK);
    assert(dlist_traverse(dlist, int_get_sum, &sum) == DLIST_RET_OK);
    assert(dlist_traverse(dlist, int_get_max, &max_ctx) == DLIST_RET_OK);
}

int main()
{
    test_int();
    demo_heap();    
    printf("\n \n");
    return 0;
}