vlambda博客
学习文章列表

c语言 | 双链表的实现

上一次我们说过单链表,其实双链表和单链表没有什么很大的区别,只不过多了一条前向的链子而已。单链表只能从前往后找,而双链表可以向两边找,这一点是相对于单链表的优势。
这里就不再详细解释双链表的实现过程了,可以回顾一下之前写过的:
直接将我写的代码附上,供参考:
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
struct  node
{

    int data;
    struct  nodeprev;
    struct  node*pnext;
};

//创建节点
struct  node * creat_node(int data)
{
    struct  node*p=mallocsizeof(struct  node) );
    bzero(p,sizeof(struct  node) );
    p->data=data;p->prev=NULL;p->pnext=NULL;
    return p;
}

//头插入
void insert_head(int data,struct  node * ph)
{
    struct  node * p;
    p=creat_node(data);
    if(ph->pnext==NULL)
    {
        ph->pnext=p;
        p->prev=ph;
    }
    else
    {
        p->pnext=ph->pnext;
        p->prev=ph;
        ph->pnext->prev=p;
        ph->pnext=p;
    }
    ph->data++;
}
//尾插入
void insert_tail(int data,struct  node * ph)    
{
    struct  node * pcur=ph;
    struct  node * p=creat_node(data);
    while(pcur->pnext!=NULL)
    {
        pcur=pcur->pnext;
    }
    pcur->pnext=p;
    p->prev=pcur;
    ph->data++;
}

//遍历
void traverse(struct  node * ph,int mode)           
{
    struct  node * p=ph;
    switch (mode)
    {
        case 0:         //正向遍历
        while(p->pnext!=NULL)
        {
            printf("%d\n",p->pnext->data);
            p=p->pnext;
        }
            printf("一共有%d个数据\n",ph->data);
        break;
        case 1:          //逆向遍历
        while(p->pnext!=NULL)  //找到最后一个节点
        {
            p=p->pnext;
        }
        while(p->prev!=NULL)
        {
            printf("%d\n",p->data);
            p=p->prev;
        }
        printf("一共有%d个数据\n",ph->data);
        break;
        default:break;
    }
}

//删除节点
void delete_node(int data,struct  node * ph,int mode)
{
    struct  node * p=ph;
    struct  node * pback=p;
    //判断有没有可删除的节点
    if(ph->pnext==NULL)
    {
        printf("没有可删除的节点");
        return;
    }
    pback=p->pnext;
    switch(mode)
    {
        case 0:                            //删除所有含该数字的节点
        while(p->pnext!=NULL)
        {
            while(p->pnext->data==data)       //找到了数据
            {
                if(p->pnext->pnext==NULL//该节点是尾节点
                {
                    p->pnext->prev=NULL;
                    p->pnext=NULL;
                    free(pback);
                    ph->data--;
                    break;
                }
                else                      //该节点是普通节点
                {
                    pback->pnext->prev=p;
                    p->pnext=pback->pnext;
                    pback->pnext=NULL;
                    pback->prev=NULL;
                    free(pback);
                    pback=p->pnext;
                }
                ph->data--;
            }
            if(p->pnext!=NULL)   //判断p是否已经是尾节点       
            p=p->pnext;      
            pback=p->pnext;

        }   
        break;
        case 1:                             //只删除第一个找到的节点
        while(p->pnext!=NULL)
        {
            if(p->pnext->data==data)       //找到了数据
            {
                if(p->pnext->pnext==NULL//该节点是尾节点
                {
                    p->pnext->prev=NULL;
                    p->pnext=NULL;
                    free(pback);
                }
                else                      //该节点是普通节点
                {
                    pback->pnext->prev=p;
                    p->pnext=pback->pnext;
                    pback->pnext=NULL;
                    pback->prev=NULL;
                    free(pback);
                    pback=p->pnext;
                }
                ph->data--;
                break;
            }
            if(p->pnext!=NULL)   //判断p是否已经是尾节点       
            p=p->pnext;      
            pback=p->pnext;

        }   
        break;
        default:break;
    }

}


void main(void)
{
    struct  node *phead;
    phead=creat_node(0); //头节点
    insert_head(4,phead);
    insert_tail(8,phead);
    insert_tail(7,phead);
    insert_tail(8,phead);
    insert_head(5,phead);
    delete_node(8,phead,1);
    // printf("%d\n",phead->data);
    // printf("%d\n",phead->pnext->data);
    // printf("%d\n",phead->pnext->pnext->data);
    traverse(phead,0);
    traverse(phead,1);
}
运行结果如下: