C语言实现通用双向链表

话不多说 直接上代码

dlist.c

#include "./include/dlist.h"

//产生一个节点
static DListNode* _dlist_create_node(DList* head, void* data)
{
    DListNode* node = (DListNode*)malloc(sizeof(DListNode));

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

//通过index获取一个节点
static DListNode* _dlist_get_node(DList* head, size_t index, int fail_return_last)
{
    DListNode* iter = head->first;

    while (iter != NULL && iter->next != NULL && index > 0)
    {
        iter = iter->next;
        index--;
    }

    if (!fail_return_last)
    {
        iter = index > 0 ? NULL : iter;
    }

    return iter;
}

//销毁一个节点
static void dlistDestroyNode(DList* head, DListNode* node)
{
    if (node != NULL)
    {
        node->next = NULL;
        node->prior = NULL;
        free(node);
    }
    return;
}



DList* dlist_create()
{
    DList* head = malloc(sizeof(DList));

    if (head != NULL)
    {
        head->first = NULL;
        head->count=0;
        //head->data_destroy = data_destroy;
        //head->data_destroy_ctx = data_destroy_ctx;
    }
    return head;
}

//尾插
DListRet dlistAppend(DList* head, void* data)
{
    DListNode* node = NULL;
    DListNode* cursor = NULL;
    int index=head->count;
    node = _dlist_create_node(head, data);

    //构造节点
    if (node == NULL)
    {
        return DLIST_RET_OOM;
    }

    //第一个节点
    if (head->first == NULL)

    {
        head->first = node;
        head->count+=1;
        return DLIST_RET_OK;
    }
    cursor=head->first;
    //获取目标节点位置，1表示若超过链表长度length，则插在最后
    while(index!=1){
        index=index-1;
        cursor=cursor->next;
    }
    cursor->next = node;
    node->prior=cursor;
    head->count+=1;
    return DLIST_RET_OK;
}


//删除一个节点
DListRet dlistDelete(DList* head, size_t index)
{
    //获取目标节点位置，0表示index超过length就返回NULL
    DListNode* cursor = _dlist_get_node(head, index, 0);

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

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

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

        dlistDestroyNode(head, cursor);
    }
    head->count-=1;
    return DLIST_RET_OK;
}

//通过index获取一个节点的data
DListRet dlist_get_by_index(DList* head, size_t index, void** data)
{
    DListNode *cursor = _dlist_get_node(head, index, 0);

    if (cursor != NULL)
    {
        *data = cursor->data;
    }

    return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

//通过index设置一个节点的data
DListRet dlist_set_by_index(DList* head, size_t index, void* data)
{
    DListNode *cursor = _dlist_get_node(head, index, 0);

    if (cursor != NULL)
    {
        cursor->data = data;
    }

    return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

//获取链表的长度
size_t dlist_length(DList* head)
{
    size_t length = 0;
    DListNode* iter = head->first;
    return head->count;
}


//插摘目标数据所在的节点，比较函数采用回调的方法
int dlist_find(DList* head, DListDataCompareFunc cmp, void* ctx)
{
    int i = 0;
    DListNode* iter = head->first;

    while (iter != NULL)
    {
        int ans=cmp(ctx, iter->data);
        if (ans == 0)
        {
            break;
        }
        i++;
        iter = iter->next;
    }

    return i;
}

//遍历链表，并调用回调函数
DListRet dlist_foreach(DList* head, DListDataVisitFunc visit, void* ctx)
{
    DListRet ret = DLIST_RET_OK;
    DListNode* iter = head->first;

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

    return ret;
}

DListRet dlist_forquantity(DList* head, DListDataVisitFunc visit, void* ctx,int num)
{
    DListRet ret = DLIST_RET_OK;
    DListNode* iter = head->first;
    int i;

    for (i=0;i
        ret = visit(ctx, iter->data);
        iter = iter->next;
    }

    return ret;
}

//销毁整个链表
void dlistDestroy(DList* head)
{
    DListNode* iter = head->first;
    DListNode* next = NULL;

    while (iter != NULL)
    {
        next = iter->next;
        dlistDestroyNode(head, iter);
        iter = next;
    }
    head->first = NULL;
    free(head);
    return;
}
//交换的函数
void swap(DListNode* q,DListNode* p)
{
    void* t=q->data;
    q->data=p->data;
    p->data=t;
}


//冒泡排序
DListRet BubbleSort(DList* head,DListDataCompareFunc cmp)
{
    DListNode* p;
    DListNode* q;
    int length=(int)dlist_length(head);

    if((head->first->next) != NULL)
    {
        int i=0;
        
        while(i
            q = head->first;
            p = q->next;
        while(p != NULL)
        {
            
            if(cmp(q->data, p->data) >0 )
            {
               swap(q,p);
            }

            else
            {
                q = q->next;
                p = p->next;
            }

        }
        i++;
        }
    }

    return DLIST_RET_OK;
}

DListRet selectSort(DList* head,DListDataCompareFunc cmp){

    DListNode* p;
    DListNode* q;
    int length=(int)dlist_length(head);

    if((head->first->next) != NULL)
    {
        q = head->first;
        while(q!=NULL)
        {
            
            p = q->next;
        while(p != NULL)
        {
            if(cmp(q->data, p->data) >0)
            {
               swap(q,p);
            }

            else
            {
                p = p->next;
            }

        }
        q = q->next;
        }
    }

    return DLIST_RET_OK;
}

DListRet mergeDList(DList* p,DList *q){
    DListNode* d1=p->first;
    while(d1->next!=NULL){
        d1=d1->next;
    }
    d1->next=q->first;
    d1->next->prior=d1;
    p->count=p->count+q->count;
    free(q);
    return DLIST_RET_OK;
}

DListRet reverseDList(DList* p){
    DListNode* d1=p->first;
    DListNode* pre=NULL;
    DListNode* nxt=NULL;
    p->first=NULL;
    d1->prior=NULL;
    while(d1!=NULL){
        nxt=d1->next;
        d1->next=pre;
        d1->prior=nxt;

        pre=d1;
        d1=nxt;
    }
    p->first=pre;
    return DLIST_RET_OK;
    
}

DListRet updateInfo(DList* head,DListDataCompareFunc cmp,void *data){
    DListNode* d1=head->first;
    while(d1!=NULL){
        if(cmp(d1->data,data)==0){
            d1->data=data;
            return DLIST_RET_OK;
        }
        d1=d1->next;
    }
    return DLIST_RET_FAIL;
}

dlist.h

#include 


typedef struct DListNode
{
    struct DListNode* prior;
    struct DListNode* next;
    void* data;
}DListNode;


struct DList
{
    DListNode* first;
    //DListDataDestroyFunc data_destroy;
    //void* data_destroy_ctx;
    int count;
};

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

//DList用于描述整个链表，定义在dlist.c中
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 data_destroy, void* data_destroy_ctx);
DList* dlist_create();
///DListRet dlist_insert(DList* head, size_t index, void* data);
//DListRet dlist_insert(DList* head, void* data);
//DListRet dlist_prepend(DList* head, void* data);
DListRet dlistAppend(DList* head, void* data);
DListRet dlistDelete(DList* head, size_t index);
DListRet dlist_get_by_index(DList* head, size_t index, void** data);
DListRet dlist_set_by_index(DList* head, size_t index, void* data);
size_t dlist_length(DList* head);
int dlist_hasnot(DList* head, DListDataCompareFunc cmp, void* ctx,void* data);
int dlist_find(DList* head, DListDataCompareFunc cmp, void* ctx);
DListRet dlist_foreach(DList* head, DListDataVisitFunc visit, void* ctx);
DListRet dlist_forquantity(DList* head, DListDataVisitFunc visit, void* ctx,int num);
void dlistDestroy(DList* head);
DListRet BubbleSort(DList* head,DListDataCompareFunc cmp);
DListRet selectSort(DList* head,DListDataCompareFunc cmp);
DListRet mergeDList(DList* p,DList *q);
DListRet reverseDList(DList* p);
DListRet updateInfo(DList* head,DListDataCompareFunc cmp,void *data);

test1.c

#include "./include/dlist.h"
#include 
#include 
#include 


struct Staff
{
   int wordID;
   char name[10];
   char ip[15];
   char seatNumber[10];
   char groupNumber[10];
} ;

DListRet print(void* ctx, void* data)
{
    //printf("%d",sizeof(data));
    printf("wordID: %d ", ((*(struct Staff*)data).wordID));
    printf("name: %s ", ((*(struct Staff*)data).name));
    printf("ip: %s ", ((*(struct Staff*)data).ip));
    printf("seatNumber: %s ", ((*(struct Staff*)data).seatNumber));
    printf("groupNumber: %s n", ((*(struct Staff*)data).groupNumber));
    return DLIST_RET_OK;
}

int CompareIDFunc(void* data1, void* data2)
{

    if((*(struct Staff*)data1).wordID == (*(struct Staff*)data2).wordID)
        return 0;
    else if((*(struct Staff*)data1).wordID> (*(struct Staff*)data2).wordID)
       return 1;
    else
        return -1;
}

int CompareNameFunc(void* data1, void* data2)
{
    return strcmp((*(struct Staff*)data1).name,(*(struct Staff*)data2).name);
}
int CompareIPFunc(void* data1, void* data2)
{
    return strcmp((*(struct Staff*)data1).ip,(*(struct Staff*)data2).ip);
}
int CompareSeatFunc(void* data1, void* data2)
{
    return strcmp((*(struct Staff*)data1).seatNumber,(*(struct Staff*)data2).seatNumber);
}
int CompareGroupNumberFunc(void* data1, void* data2)
{
    return strcmp((*(struct Staff*)data1).groupNumber,(*(struct Staff*)data2).groupNumber);
}

static void dlist_temp()
{
    FILE *fp = NULL;

    fp = fopen("./input/data1.txt", "r");
    

    DList* dlist = dlist_create(NULL, NULL);
    DList* dlist1 = dlist_create(NULL, NULL);
    struct Staff* newPerson;
    newPerson = (struct Staff*)malloc(sizeof(struct Staff)*50);
    int j=0;
    while(fscanf(fp, "%d %s %s %s %sn", &newPerson->wordID,newPerson->name,newPerson->ip,newPerson->seatNumber,newPerson->groupNumber)!=EOF)
    {
        
        printf("%d %s %s %s %sn",newPerson->wordID,newPerson->name,newPerson->ip,newPerson->seatNumber,newPerson->groupNumber);
        dlistAppend(dlist, newPerson);
        newPerson=(struct Staff*)malloc(sizeof(struct Staff)*50);
        
    }
    dlist_forquantity(dlist, print, NULL,dlist->count);
    printf("nAfter BubbleSort:n");
    BubbleSort(dlist,CompareIDFunc);
    dlist_forquantity(dlist, print, NULL,dlist->count);
    printf("n");
    fclose(fp);

    fp = fopen("./input/data2.txt", "r");

    while(fscanf(fp, "%d %s %s %s %sn", &newPerson->wordID,newPerson->name,newPerson->ip,newPerson->seatNumber,newPerson->groupNumber)!=EOF)
    {
        
        printf("%d %s %s %s %sn",newPerson->wordID,newPerson->name,newPerson->ip,newPerson->seatNumber,newPerson->groupNumber);
        dlistAppend(dlist1, newPerson);
        newPerson=(struct Staff*)malloc(sizeof(struct Staff)*50);
        
    }
    dlist_forquantity(dlist1, print, NULL,dlist1->count);
    printf("nAfter selectSort:n");
    selectSort(dlist1,CompareIDFunc);
    dlist_forquantity(dlist1, print, NULL,dlist1->count);
    printf("n");
    printf("nAfter merging and bubbleSort ID in descending order:n");
    mergeDList(dlist,dlist1);
    BubbleSort(dlist,CompareIDFunc);
    reverseDList(dlist);
    dlist_forquantity(dlist, print, NULL,dlist->count);
    printf("n");
    
    printf("After merging and bubbleSort seatNumbern");
    BubbleSort(dlist,CompareSeatFunc);
    dlist_forquantity(dlist, print, NULL,dlist->count);
    printf("n");
    
    printf("After merging and selectSort namen");
    selectSort(dlist,CompareNameFunc);
    dlist_forquantity(dlist, print, NULL,dlist->count);
    printf("n");
}

int main()
{
    dlist_temp();

    
    return 0;
}