欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

带头结点的双向循环链表

程序员文章站 2022-03-15 19:27:49
...

DList.h //头文件

#ifndef __DLIST_H__
#define __DLIST_H__

typedef int DataType;

typedef struct DListNode
{
    struct DListNode* _pNext;
    struct DListNode* _pPre;
    DataType _data;
}DListNode;


void DListInit(DListNode** pHead);//初始化
void PrintDList(DListNode* pHead);//打印链表
void DListPushBack(DListNode* pHead, DataType data);// 双向链表的尾插 
void DListPopBack(DListNode* pHead);// 双向链表的尾删
void DListPushFront(DListNode* pHead, DataType data); // 双向链表的头插 
void DListPopFront(DListNode* pHead); // 双向链表的头删 
void DListInsert(DListNode* pos, DataType data);// 任意位置插入
void DListErase(DListNode* pos);// 任意位置删除
DListNode* DListFind(DListNode* pHead, DataType data);// 查找值为data的结点 
void DListDestroy(DListNode** pHead); // 销毁 
#endif //__DLIST_H__

//DList.c //源文件

#include "DList.h"
#include <malloc.h>
#include <assert.h>
#include <stdio.h>


DListNode* BuyDListNode(DataType data)
{
    DListNode* pNewNode = (DListNode*)malloc(sizeof(DListNode));
    if(NULL == pNewNode)
    {
        assert(0);
        return NULL;
    }

    pNewNode->_pNext = NULL;
    pNewNode->_pPre = NULL;
    pNewNode->_data = data;

    return pNewNode;
}

void DListInit(DListNode** pHead)
{
    assert(pHead);
    *pHead = BuyDListNode(0);

    (*pHead)->_pNext = (*pHead);
    (*pHead)->_pPre = (*pHead);
}
void PrintDList(DListNode* pHead)
{
    DListNode* pNode = pHead->_pNext;
    while(pNode != pHead)
    {
        printf("%d ", pNode->_data);
        pNode = pNode->_pNext;
    }


}
void DListPushBack(DListNode* pHead, DataType data)
{
    DListNode* pNewNode;
    assert(pHead);
    pNewNode = BuyDListNode(data);

    // 尾插
    pNewNode->_pPre = pHead->_pPre;
    pNewNode->_pNext = pHead;
    pNewNode->_pPre->_pNext = pNewNode;
    pHead->_pPre = pNewNode;
}

void DListPopBack(DListNode* pHead)
{
    DListNode* pDelNode = NULL;
    assert(pHead);

    pDelNode = pHead->_pPre;
    if(pHead != pDelNode)
    {
        pDelNode->_pPre->_pNext = pDelNode->_pNext;
        pDelNode->_pNext->_pPre = pDelNode->_pPre;
        free(pDelNode);
    }
}
void DListPushFront(DListNode* pHead, DataType data)
{
    DListNode* pNewNode =NULL;
    assert(pHead);
    pNewNode = BuyDListNode(data);
    pNewNode->_pNext = pHead->_pNext;
    pHead->_pNext->_pPre = pNewNode;
    pHead->_pNext = pNewNode;
    pNewNode->_pPre = pHead;

}
void DListPopFront(DListNode* pHead)
{
   DListNode* pDelNode = NULL;
   if(pHead == pHead->_pNext)
   {
      return;
   }
   pDelNode = pHead->_pNext;
   pDelNode->_pNext->_pPre = pHead;
   pHead->_pNext = pDelNode->_pNext;
   free(pDelNode);


}
void DListInsert(DListNode* pos, DataType data)
{
    DListNode* pNewNode;
    if(NULL == pos)
        return;

    pNewNode = BuyDListNode(data);
    pNewNode->_pNext = pos;
    pNewNode->_pPre = pos->_pPre;
    pos->_pPre = pNewNode;
    pNewNode->_pPre->_pNext = pNewNode;
}

void DListErase(DListNode* pos)
{
    if(pos)
    {
        pos->_pPre->_pNext = pos->_pNext;
        pos->_pNext->_pPre = pos->_pPre;
        free(pos);
    }
}

DListNode* DListFind(DListNode* pHead, DataType data)
{
    DListNode* pCur;
    assert(pHead);
    pCur = pHead->_pNext;

    while(pCur != pHead)
    {
        if(data == pCur->_data)
            return pCur;

        pCur = pCur->_pNext;
    }

    return NULL;
}
void DListDestroy(DListNode** pHead)
{
  DListNode* pDelNode = NULL;
  DListNode* pPreDelNode = NULL;
  assert(pHead);
  pDelNode = (*pHead)->_pNext;
  while(*pHead != pDelNode)
  {
     pPreDelNode = pDelNode;
     pDelNode = pDelNode->_pNext;
     free(pPreDelNode);

  }
  free(pDelNode);
  (*pHead) = NULL;


}

test.c //测试

#include "DList.h"
#include <stdio.h>
void TestDList()
{
    DListNode* pos;
    DListNode* pHead = NULL;
    DListInit(&pHead);  // 头结点

    DListPushBack(pHead, 1);
    DListPushBack(pHead, 2);
    DListPushBack(pHead, 3);
    DListPushBack(pHead, 4);
    DListPushBack(pHead, 5);
    DListPushBack(pHead, 6);
    PrintDList(pHead);
    printf("\n");

    DListPopBack(pHead);
    PrintDList(pHead);
    printf("\n");

    pos = DListFind(pHead, 3);
    printf("%p\n",pos);


    DListInsert(pos, 0);
    PrintDList(pHead);
    printf("\n");

    DListErase(pos);
    PrintDList(pHead);
    printf("\n");
    DListDestroy(&pHead);
    PrintDList(pHead);
}
int main()
{
    TestDList();
    return 0;
}