美文网首页数据结构和算法分析
2018-10-02 数据结构学习---双向链表的实现

2018-10-02 数据结构学习---双向链表的实现

作者: 回不去的温柔 | 来源:发表于2018-10-02 22:13 被阅读24次

    2018.10.2 数据结构学习---双向链表的实现

    /*
     * 学习时间:2018-10-2
     * 学习内容:数据结构之尾插法实现双向链表,以及链表的增删查改
     * 学习人:田超
     * QQ:770925351
     * Email:770925351@qq.com
     * 开发环境:Ubuntu 16.04 + CLion
     * */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    typedef struct DLNode   //定义循环链表结构体
    {
        int data;
        struct DLNode *prior;
        struct DLNode *next;
    }DLNode;
    
    void createDList(DLNode *&L,int a[],int n)  //创建双向链表
    {
        DLNode *s,*r;                           //s用于新建节点,r用于跟踪L的尾端节点
        int i;                                  //for循环临时变量
        L=(DLNode*)malloc(sizeof(DLNode));      //开辟循环链表头结点空间
        L->prior=NULL;                          //初始化头结点前驱指针
        L->next=NULL;                           //初始化头结点后继指针
        r=L;                                    //初始化r
        for(i=0;i<n;i++)
        {
            s=(DLNode*)malloc(sizeof(DLNode));  //开辟新节点空间
            s->data=a[i];                       //将数值赋值给新节点的数据域
            r->next=s;                          //将r指向的后继变成s
            s->prior=r;                         //将s指向的前趋设置为r
            r=s;                                //r移位,变成链表的最后一个节点
        }
        r->next=NULL;                           //此时r为最后一个节点,将它的后继指针变成NULL,创建链表结束
    }
    
    void travelNode(DLNode *L)
    {
        DLNode *p=L->next;
        while(p!=NULL)
        {
            printf("data=%d\n",p->data);
            p=p->next;
        }
    }
    
    DLNode* findNode(DLNode *L,int x)           //在双向链表中查找x元素
    {
        DLNode *p=L->next;                      //p为指向链表的指针,并初始化指向除头节点第一个节点
        while(p!=NULL)                          //当p不为空时候,一直循环
        {
            if(p->data==x)                      //比较值的大小,如果相等,则找到,立即结束循环
                break;
            p=p->next;                          //没有找到,p指向下一个节点
        }
            return p;                           //返回p指针,如果找到则会返回节点的地址,如果找不到,说明p到了最后一个节点,最后一个节点的next指针是NULL
    }
    
    void insertNode_tail(DLNode *L,int x)       //在双向链表中插入x元素,尾插法
    {
        DLNode *p,*s;                           //s用来新建节点,p用来寻找当前链表中最后一个节点
        p=L->next;                              //初始化p节点
        while(p&&p->next!=NULL)                 //循环找到L的最后一个节点,并赋值给p,在这里判断的逻辑是:p不能为空且p的后继指针不能为空,当为空时候结束循环,说明p是最后一个节点
        {
            p=p->next;
        }
        s=(DLNode*)malloc(sizeof(DLNode));      //新建节点
        s->data=x;                              //将传进来的数据赋值给s
        if(p==NULL)                             //如果此时链表为空,则插入的节点是第一个节点
        {
            s->prior=L;                         //s节点的前趋指向头结点
            s->next=p;                          //s节点的后继指向p,也就是NULL
            L->next=s;                          //此时s作为链表的第一个节点,也就是L->next
        }
        else
        {
            s->prior=p;                         //将s的前趋指针指向p
            s->next=p->next;                    //将s的后继指针指向原先p的后继,因为p是最后一个节点,所以是NULL,如果说是中间的节点的话,就不是NULL
            p->next=s;                          //将p的后继重新指向s
        }
    
    }
    
    void insertNode_head(DLNode *L,int x)       //在双向链表中插入x元素,头插法
    {
        DLNode *s;                              //s用来新建节点
        s=(DLNode*)malloc(sizeof(DLNode));      //为s开辟空间
        s->data=x;                              //将数据赋值给新建的节点s的data域
        s->prior=L;                             //将s的前趋指针指向头结点
        s->next=L->next;                        //将s的后继指针指向原先的第一个节点
        if(L->next==NULL)                       //如果此时链表为空,那么s节点将
            L->next=s;
        else
        {
            L->next->prior=s;                   //将原先第一个节点的前趋指针指向s
            L->next=s;                          //将头节点的next指针指向s
        }
    
    }
    
    int deleteNode(DLNode *L,int x)             //在双向链表中删除节点
    {
        DLNode *p=L->next;                      //让p指向除头节点外的第一个节点
        while(p!=NULL)                          //循环至最后一个节点
        {
            if(p->data==x)                      //如果找到节点
            {
                if(p->next==NULL)               //如果找到的是最后一个节点
                {
                    p->prior->next = p->next;   //将p节点前趋的后继指针指向NULL
                    free(p);                    //释放空间
                }
                else
                {
                    p->prior->next = p->next;   //将p节点前趋的后继指针指向p的后继
                    p->next->prior = p->prior;  //将p节点后继的前趋指针指向p的前趋
                    free(p);                    //释放空间
                }
                return TRUE;                    //返回真
            }
            p=p->next;                          //没有找到将p指向下一个节点
        }
        return FALSE;                           //循环结束,没有找到,返回假
    }
    
    int main()
    {
        int a[5]={1,2,3,4,5};
        int n=5;
        DLNode *L;
        createDList(L,a,n);
        travelNode(L);
        printf("\n");
        deleteNode(L,5);
        travelNode(L);
        printf("\n");
        insertNode_tail(L,6);
        travelNode(L);
        printf("\n");
        insertNode_head(L,7);
        travelNode(L);
        printf("\n");
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:2018-10-02 数据结构学习---双向链表的实现

        本文链接:https://www.haomeiwen.com/subject/jnwaoftx.html