[数据结构与算法]双链表的算法之删除节点

双链表的算法之删除节点

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

struct node
{
    int data;           //有效数据
    struct node* pPrev; //前向指针，指向前一个节点
    struct node* pNext; //后向指针，指向后一个节点
};

struct node* create_node(int data)
{
    struct node* p = (struct node*)malloc(sizeof(struct node));
    if(NULL == p)
    {
        printf("create_node malloc failed\n");
        return NULL;
    }
    p->data = data;
    p->pPrev = NULL;
    p->pNext = NULL;

    return p;
}
//蒋新节点new插入到链表pH的尾部
void insert_tail(struct node* pH, struct node* new)
{
    //第一步：先走到链表的尾结点
    struct node* p = pH;
    while(NULL != p->pNext)
    {
        p = p->pNext;  //第一次循环走过了头结点
    }
    //循环结束后p就指向了原来的最后一个节点
    //第二步：将新节点插入到原来的尾结点的后面
    p->pNext = new;  //后向指针关联
    new->pPrev = p;   //前向指针关联
}
//将新节点new前插入链表pH中
void insert_head(struct node* pH, struct node* new)
{
    //新节点的next指针指向原来的第1个有效节点的地址
    new->pNext = pH->pNext;
    //原来第一个有效节点的prev指针指向新节点的地址
    if(NULL != pH->pNext) //只有头结点，没有第一个有效节点时，pH->pNext = NULL
        pH->pNext->pPrev = new;
    //第一步：头结点的next指针指向新节点的地址
    pH->pNext = new;
    //新节点的prev指针指向头结点的地址
    new->pPrev = pH;
    
    
}
//后向遍历
void ergodic(struct node *pH)
{
    struct node* p = pH;
    while(NULL != p->pNext)
    {
        p = p->pNext;
        printf("data = %d\n",p->data);
    }
}
//前向遍历
void forward(struct node *pTail)
{
    struct node* p = pTail;
    while(NULL != p->pPrev)
    {
        printf("data = %d\n",p->data);
        p = p->pPrev;
    }
}
//删除节点
int delete_node(struct node* pH, int data)
{
    struct node* p = pH;
    while(NULL != p->pNext)
    {
        p = p->pNext;
        //判断当前节点是否是要删除的节点
        if(p->data == data)
        {
            //当前节点为p
            if(NULL == p->pNext)  //尾结点
            {
                //p表示当前节点地址，p->pNext表示后一个节点的地址，p->pPrev表示当前一个节点的地址
                p->pPrev->pNext = NULL;
                p->pNext = NULL;
                free(p);
            }
            else  //普通节点
            {
                //前一个节点的next指针指向后一个节点的首地址
                p->pPrev->pNext = p->pNext;
                //后一个节点的prev指针指向前一个节点的首地址
                p->pNext->pPrev = p->pPrev;

                free(p);
            }
            return 0;
        }
    }

    printf("node find failed\n");
    return -1;
}
int main()
{
    struct node* pHeader = create_node(0);  //头指针
    insert_head(pHeader, create_node(1));
    insert_head(pHeader, create_node(2));
    insert_head(pHeader, create_node(3));

    /*//遍历
    printf("node 1 data: %d\n", pHeader->pNext->data);
    printf("node 2 data: %d\n", pHeader->pNext->pNext->data);
    printf("node 3 data: %d\n", pHeader->pNext->pNext->pNext->data);

    struct node* p = pHeader->pNext->pNext->pNext; //p指向了最后一个节点
    printf("node 3 data: %d\n", p->data);
    printf("node 2 data: %d\n", p->pPrev->data);
    printf("node 1 data: %d\n", p->pPrev->pPrev->data);*/
    ergodic(pHeader);
    //struct node* p = pHeader->pNext->pNext->pNext; //p指向了最后一个节点
    //forward(p);
    delete_node(pHeader,1);
    printf("after delete node\n");
    ergodic(pHeader);


    return 0;
}