双向链表

typedef int ELEMTYPE;

typedef struct DNode
{
    ELEMTYPE data;//数据域
    DNode* next;//指向直接后继
    DNode* prior;//指向直接前驱
}DNode, * Dlist;//Dlist == DNode*


//初始化
void Initlist(Dlist plist);

//头插
bool Insert_head(Dlist plist, ELEMTYPE val);

//尾插
bool Insert_tail(Dlist plist, ELEMTYPE val);

//按位置pos插入
bool Insert_pos(Dlist plist, int pos, ELEMTYPE val);

//判空
bool IsEmpty(Dlist plist);

//获取链表有效节点个数
int GetLength(Dlist plist);

//查找第一个值是key的节点，找到的话返回这个节点，没找到的话返回NULL
DNode* Search(Dlist plist, ELEMTYPE key);

//删除位置pos
bool Delpos(Dlist plist, int pos);

//删除第一个值为key的节点
bool Delval(Dlist plist, ELEMTYPE key);

//尾删
bool Del_tail(Dlist plist);

//头删
bool Del_head(Dlist plist);

//找节点的前驱
DNode* Getprior(Dlist plist, ELEMTYPE val);

//找节点的后继
DNode* Getnext(Dlist plist, ELEMTYPE val);

//清空， 直接调用销毁
void Clear(Dlist plist);

//销毁
void Destroy(Dlist plist);

//打印
void Show(Dlist plist);

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>// #include <malloc.h>
#include "dlist.h"


//define 0 ((void*)0)
//nullptr     NULL        nullptr

//初始化
void Initlist(Dlist plist)
{
    //断言
    assert(plist != NULL);//nullptr
    if (plist == NULL)
        return;

    //赋值为我们给的初始值
    //plist->data; 数据域不需要赋值
    plist->next = NULL;
    plist->prior = NULL;
}

static DNode* BuyNode(ELEMTYPE val)
{
    DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
    if (pnewnode == NULL)
        return false;
    pnewnode->data = val;
    pnewnode->next = NULL;
    pnewnode->prior = NULL;

    return pnewnode;
}
//头插
bool Insert_head(Dlist plist, ELEMTYPE val)
{
    //断言

    //创建一个新节点
    //DNode * pnewnode = BuyNode(val);
    DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
    if (pnewnode == NULL)
        return false;
    pnewnode->data = val;
    pnewnode->next = NULL;
    pnewnode->prior = NULL;

    //插入
    pnewnode->next = plist->next;//永远第一步  先让新节点把下一个节点绑住  //结点
    pnewnode->prior = plist;

    //特殊：两种情况  一种有节点存在， 一个光杆司令
    if (plist->next != NULL)
    {
        plist->next->prior = pnewnode;// -> = (*).
    }

    plist->next = pnewnode;
    return true;
}

//尾插
bool Insert_tail(Dlist plist, ELEMTYPE val)
{
    //assert
    //创建新节点
    DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
    pnewnode->data = val;

    //找到前驱

    DNode* p;
    for (p = plist; p->next != NULL; p = p->next);

    //插入

    pnewnode->next = NULL;
    pnewnode->prior = p;

    p->next = pnewnode;
    return true;
}


//按位置pos插入
bool Insert_pos(Dlist plist, int pos, ELEMTYPE val)
{
    //断言
    assert(plist != NULL && pos >= 0 && pos <= GetLength(plist));
    if (plist == NULL || pos<0 || pos>GetLength(plist))
        return false;

    //创建新节点
    DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
    pnewnode->data = val;
    //找到插入的位置pos
    DNode* p = plist;
    for (int i = 0; i < pos; i++)
    {
        p = p->next;
    }
    //for(p=plist,int i=0; i<pos; i++,p=p->next);
    //插入
    pnewnode->next = p->next;
    pnewnode->prior = p;
    if (p->next != NULL)
    {
        p->next->prior = pnewnode;
    }
    p->next = pnewnode;
    return true;
}

//判空
bool IsEmpty(Dlist plist)
{
    return plist->next == NULL;
}

//获取链表有效节点个数
int GetLength(Dlist plist)
{
    int count = 0;
    for (DNode* p = plist->next; p != NULL; p = p->next)
    {
        count++;
    }

    return count;
}

//查找第一个值是key的节点，找到的话返回这个节点，没找到的话返回NULL
DNode* Search(Dlist plist, ELEMTYPE key)
{
    //assert
    //遍历找值为key的第一个节点

    for (DNode* p = plist->next; p != NULL; p = p->next)
    {
        if (p->data == key)
        {
            return p;
        }
    }

    return NULL;
}

//删除位置pos
bool Delpos(Dlist plist, int pos)
{
    //assert
    assert(plist != NULL && pos >= 0 && pos < GetLength(plist));
    if (plist == NULL || pos < 0 || pos >= GetLength(plist))
        return false;
    //找到删除的位置
    DNode* p = plist;
    for (int i = 0; i <= pos; i++)
    {
        p = p->next;
    }
    //删除节点
    p->prior->next = p->next;
    if (p->next != NULL)
    {
        p->next->prior = p->prior;
    }
    //释放空间
    free(p);
    p = NULL;

    return true;
}

//删除第一个值为key的节点
bool Delval(Dlist plist, ELEMTYPE key)
{
    //断言
    if (plist == NULL)
        return false;

    //找到位置pos的节点
    DNode* p = Search(plist, key);
    if (p == NULL)
    {
        return false;
    }

    //删除
    p->prior->next = p->next;
    if (p->next != NULL)
    {
        p->next->prior = p->prior;
    }

    //释放空间
    free(p);
    p = NULL;
    return true;
}


//尾删
bool Del_tail(Dlist plist)
{
    //断言
    if (plist == NULL)
        return false;
    //找删除的节点
    DNode* p;
    for (p = plist; p->next != NULL; p = p->next);

    //删除
    p->prior->next = NULL;

    //释放内存
    free(p);
    p = NULL;
    return true;
}

//头删
bool Del_head(Dlist plist)
{
    //assert
    if (plist == NULL || plist->next == NULL)
        return false;

    //找到位置
    DNode* p = plist->next;

    //删除
    plist->next = p->next;
    if (p->next != NULL)
    {
        p->next->prior = plist;
    }

    //释放内存
    free(p);
    p = NULL;

    return true;

}

//找节点的前驱
DNode* Getprior(Dlist plist, ELEMTYPE val)
{
    //assert
    DNode* p = Search(plist, val);
    /*if(p == NULL)
    {
        return NULL;
    }
    return p->prior;*/
    return p == NULL ? NULL : p->prior;

}

//找节点的后继
DNode* Getnext(Dlist plist, ELEMTYPE val)
{
    DNode* p = Search(plist, val);
    return p == NULL ? NULL : p->next;
}

//清空， 直接调用销毁
void Clear(Dlist plist)
{
    Destroy(plist);
}

//销毁
void Destroy(Dlist plist)
{
    //assert
    if (plist == NULL || plist->next == NULL)
        return;
    DNode* p = plist->next;

    while (plist->next != NULL)
    {
        p = plist->next;
        plist->next = p->next;
        free(p);
    }
}

//void Destroy1(Dlist plist)
//{
//    if(plist == NULL ||plist->next == NULL)
//        return;
//    DNode *p = plist->next;
//    DNode *q;
//    while(p != NULL)
//    {
//        q = p->next;
//        free(p);
//        p = q;
//    }
//
//    plist->next = NULL;
//}

//打印
void Show(Dlist plist)
{
    for (DNode* p = plist->next; p != NULL; p = p->next)
    {
        printf("%d ", p->data);
    }
    printf("\n");
}

for (p = plist; p->next != NULL; p = p->next);

for (DNode* p = plist->next; p != NULL; p = p->next)