【数据结构】带头结点双向循环链表相关操作

链表结构如下：

相关操作结构

因为带头结点，所以在任何结点的操作都是一致的，相对单链表来说简单一些。

相关操作参考代码

• DLinkLIst.h:

#ifndef __LINKLIST_H__
#define __LINKLIST_H__


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//带头结点循环双链表

typedef int DataType;
typedef struct DLinkList
{
    DataType data;
    struct DLinkList* pNext;
    struct DLinkList* pPrev;
}pDLinkList,*DLinkList;     //节点信息

/*typedef struct DLinkList
{
    DLinkList* pHead;
}DLinkList; */       //链表信息



void DLinkListInit(DLinkList* pHead);
void DLinkListDestory(DLinkList* pHead);

void DLinkListPushBack(DLinkList* pHead,DataType x);
void DLinkListPushFront(DLinkList* pHead,DataType x);
void DLinkListPopBack(DLinkList* pHead);
void DLinkListPopFront(DLinkList* pHead);

DLinkList DLinkListFind(DLinkList* pHead, DataType x);
void DLinkListInsert(DLinkList* pHead, DLinkList pos, DataType x);
void DLinkListErase(DLinkList* pHead, DLinkList pos);
void DLinkListReMove(DLinkList* pHead, DataType x);
void DLinkListReMoveAll(DLinkList* pHead, DataType x);

int DLinkListSize(DLinkList* pHead);
int DLinkListEmpty(DLinkList* pHead);

void PrintDLinkList(DLinkList pHead);
void testDLinkList();


#endif//__LINKLIST_H__

• DLinkLIst.c:

#include "DLinkList.h"

//////////////////////////////带头结点循环双链表/////////////////////////////////////
void DLinkListInit(DLinkList* pHead)
{
    assert((pHead));
    DLinkList tmp = (DLinkList)malloc(sizeof(pDLinkList));
    assert(tmp);
    *pHead = tmp;
    (*pHead)->pNext = (*pHead);
    (*pHead)->pPrev = (*pHead);
}
void DLinkListDestory(DLinkList* pHead)
{
    assert((pHead));
    DLinkList ptr = (*pHead)->pNext;;
    while (ptr != (*pHead))
    {
        DLinkList pCur = ptr->pNext;
        free(ptr);
        ptr = pCur;
    }
    free(*pHead);
    (*pHead) = NULL;
    printf("销毁成功\n");
}

void DLinkListPushBack(DLinkList* pHead, DataType x)
{
    assert((pHead));
    DLinkListInsert((pHead), (*pHead), x);
}
void DLinkListPushFront(DLinkList* pHead, DataType x)
{
    assert((pHead));

    DLinkListInsert((pHead), (*pHead)->pNext, x);

}
void DLinkListPopBack(DLinkList* pHead)
{
    assert((pHead));

    DLinkListErase((pHead), (*pHead)->pPrev);

}
void DLinkListPopFront(DLinkList* pHead)
{
    assert((pHead));

    DLinkListErase((pHead), (*pHead)->pNext);

}

 DLinkList BuyNode(DataType x)
{
    DLinkList tmp = (DLinkList)malloc(sizeof(pDLinkList));
    assert(tmp);
    tmp->data = x;
    tmp->pNext = NULL;
    tmp->pPrev = NULL;
    return tmp;

}
DLinkList DLinkListFind(DLinkList* pHead, DataType x)
{
    assert((pHead));
    DLinkList pCur = (*pHead)->pNext;
    while (pCur != (*pHead))
    {
        if (pCur->data == x)
        {
            return pCur;
        }
        pCur = pCur->pNext;
    }
    return NULL;

}
void DLinkListInsert(DLinkList* pHead, DLinkList pos, DataType x)
{
    assert(pos && (pHead));
    DLinkList pre = pos->pPrev;
    DLinkList pNewNode = BuyNode(x);
    pre->pNext = pNewNode;
    pNewNode->pPrev = pre;
    pNewNode->pNext = pos;
    pos->pPrev = pNewNode;

}
void DLinkListErase(DLinkList* pHead, DLinkList pos)
{
    assert(pos && (pHead));
    if ((*pHead) == pos)
    {
        printf("非法删除\n");
        return;
    }
    else
    {
        DLinkList next = pos->pNext;
        DLinkList pre = pos->pPrev;
        pre->pNext = next;
        next->pPrev = pre;
        free(pos);
        pos = NULL;
    }
}
void DLinkListReMove(DLinkList* pHead, DataType x)
{
    assert(pHead);
    DLinkList pCur = (*pHead)->pNext;
    while (pCur != (*pHead))
    {
        if (pCur->data == x)
        {
            DLinkList tmp = pCur->pPrev;
            tmp->pNext = pCur->pNext;
            pCur->pNext->pPrev = tmp;
            free(pCur);
            pCur = NULL;
            return;
        }
        else
        {
            pCur = pCur->pNext;
        }
    }
}
void DLinkListReMoveAll(DLinkList* pHead, DataType x)
{
    assert(pHead);
    DLinkList pCur = (*pHead)->pNext;
    while (pCur != (*pHead))
    {
        if (pCur->data == x)
        {
            DLinkList tmp = pCur->pPrev;
            tmp->pNext = pCur->pNext;
            pCur->pNext->pPrev = tmp;
            free(pCur);
            pCur = tmp->pNext;
        }
        else
        {
            pCur = pCur->pNext;
        }
    }
}

int DLinkListSize(DLinkList* pHead)
{
    assert((pHead));
    int len = 0;
    DLinkList pCur = (*pHead)->pNext;
    while (pCur!= (*pHead))
    {
        len++;
        pCur = pCur->pNext;
    }
    return len;
}
int DLinkListEmpty(DLinkList* pHead)
{
    assert((pHead));
    return (*pHead)->pNext == (*pHead);
}

void PrintDLinkList(DLinkList pHead)
{
    assert((pHead));
    DLinkList pCur = (pHead)->pNext;
    while (pCur != (pHead))
    {
        printf("%d ",pCur->data);
        pCur = pCur->pNext;
    }
    printf("\n");
}


void testDLinkList()
{
    DLinkList dl;
    DLinkListInit(&dl);


    DLinkListPushBack(&dl, 4);
    DLinkListPushBack(&dl, 5);
    DLinkListPushBack(&dl, 5);
    DLinkListPushBack(&dl, 5);
    DLinkListPushBack(&dl, 6);
    DLinkListPushBack(&dl, 7);
    DLinkListPushBack(&dl, 5);
    DLinkListPushBack(&dl, 5);
    DLinkListPushBack(&dl, 8);

    PrintDLinkList(dl);

    printf("大小 %d\n",DLinkListSize(&dl));
    if (DLinkListFind(&dl, 4) != NULL)
    {
        printf("查找           %d\n", DLinkListFind(&dl, 4)->data);
    }
    else
    {
        printf("找不到\n");
    }
    printf("为空： %d\n", DLinkListEmpty(&dl));

    DLinkListInsert(&dl, DLinkListFind(&dl, 4), 0);
    PrintDLinkList(dl);

    printf("大小%d\n", DLinkListSize(&dl));
    if (DLinkListFind(&dl, 7) != NULL)
    {
        printf("查找           %d\n", DLinkListFind(&dl, 7)->data);
    }
    else
    {
        printf("找不到\n");
    }
    printf("为空： %d\n", DLinkListEmpty(&dl));

    DLinkListErase(&dl, DLinkListFind(&dl, 8));
    PrintDLinkList(dl);

    printf("大小 %d\n", DLinkListSize(&dl));
    if (DLinkListFind(&dl, 8) != NULL)
    {
        printf("查找           %d\n", DLinkListFind(&dl, 8)->data);
    }
    else
    {
        printf("找不到\n");
    }
    printf("为空： %d\n", DLinkListEmpty(&dl));

    DLinkListReMove(&dl, 5);
    PrintDLinkList(dl);

    DLinkListReMoveAll(&dl, 5);
    PrintDLinkList(dl);
    DLinkListDestory(&dl);
}

结语

我希望你，眼里充满希望，手里握着阳光！