美文网首页
双向循环链表

双向循环链表

作者: 又是一只小白鼠 | 来源:发表于2020-04-02 11:34 被阅读0次

    双向链表

    双向链表的每个结点除含有数据域外,还有两个指针域,分别指向直接前驱结点和直接后继结点。因此,从双向链表中的任一结点开始,均可方便地访问其前驱结点和后继结点。

    双向循环链表

    双向循环链表需要注意的就是:链表为空时, 让头指向尾

    结构体

    typedef int ElemType;
    typedef struct Dline {
        struct Line *prior; //指针域,指向直接前趋元素
        ElemType data; //数据域
        struct Link *next; //指针域, 指向直接后继元素
    }Dline, *pDline;
    

    初始化

    //初始化
    void InitDLine(pDline *head, pDline *tail) {
        (*head) = (Dline *)malloc(sizeof(Dline));
        (*tail) = (Dline *)malloc(sizeof(Dline));
        if (!(*head) || !(*tail)) {
            return;
        }
        (*head)->prior = NULL;
        (*tail)->next = NULL;
        //链表为空时, 让头指向尾
        (*head)->next = (*tail);
        (*tail)->prior = (*head);
    }
    

    创建结点

    //为新节点开辟空间 这是一块存储空间,包括一个数据域+两个指针域
    pDline NewD(ElemType data) {
        pDline temp = (Dline *)malloc(sizeof(Dline));
        assert(temp);
        temp->data = data;
        temp->prior = NULL;
        temp->next = NULL;
        return temp;
    }
    

    打印

    //打印
    void PrintDLine(pDline head, pDline tail) {
        pDline pmove = head->next;
        while (pmove != tail) {
            printf("%d\t", pmove->data);
            pmove = pmove->next;
        }
        printf("\n");
    }
    

    获取链表长度

    //获取链表长度
    int GetDLineLength(pDline *head, pDline *tail) {
        if (!(*head) || !(*tail)) {
            return -1;
        }
        pDline pmove = (*head)->next;
        int count = 0;
        while (pmove != (*tail)) {
            pmove = pmove->next;
            count++;
        }
        return count;
    }
    

    插入结点

    //尾插
    void InsertDLineTail(pDline *head, pDline *tail, ElemType data) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline temp = NewD(data);
        if (!temp) {
            return;
        }
        pDline tfront = (*tail)->prior;
        tfront->next = temp;
        temp->prior = (*tail)->prior;
        temp->next = (*tail);
        (*tail)->prior = temp;
    }
    
    //头插
    void InsertDLineHead(pDline *head, pDline *tail, ElemType data) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline temp = NewD(data);
        if (!temp) {
            return;
        }
        pDline pmove = (*head)->next;
        pmove->prior = temp;
        temp->next = pmove;
        (*head)->next = temp;
        temp->prior = (*head);
    }
    //  指定位置pos插入data
    void InsertDLinePos(pDline *head, pDline *tail, ElemType data, int pos) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline pmove = (*head)->next;
        if (pos == 1) {
            InsertDLineHead(head, tail, data);
            return;
        }
        if (pos == GetDLineLength(head, tail) + 1) {
            InsertDLineTail(head, tail, data);
            return;
        }
        else {
            for (int i=1; i<pos; i++) {
                pmove = pmove->next;
                if (pmove == (*tail)) {
                    printf("超过链表长度...\n");
                    return;
                }
            }
            pDline temp = NewD(data);
            pDline pprior = pmove->prior;
            pprior->next = temp;
            temp->prior = pmove->prior;
            temp->next = pmove;
            pmove->prior = temp;
        }
    }
    

    删除结点

    //尾删
    void DeleteDLineTail(pDline *head, pDline *tail) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline pmove = (*tail)->prior;
        pDline pprior = pmove->prior;
        pprior->next = (*tail);
        (*tail)->prior = pmove->prior;
        free(pmove);
    }
    
    //首删
    void DeleteDLineHead(pDline *head, pDline *tail) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline pmove = (*head)->next;
        pDline pmove_next = pmove->next;
        (*head)->next = pmove_next;
        pmove_next->prior = (*head);
        free(pmove);
    }
    
    //删除指定位置pos的元素
    void DeleteDLinePos(pDline *head, pDline *tail, int pos) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline pmove = (*head)->next;
        if (pos == 1) {
            DeleteDLineHead(head, tail);
            return;
        }
        else {
            for (int i=1; i<pos; i++) {
                pmove = pmove->next;
                if (pmove == (*tail)) {
                    printf("超过链表长度...\n");
                    return;
                }
            }
            pDline pmove_next = pmove->next;
            pDline pprior = pmove->prior;
            pprior->next = pmove_next;
            pmove_next->prior = pmove->prior;
            free(pmove);
        }
    }
    

    查找元素

    //查找元素的位置
    int FindDLinePos(pDline *head, pDline *tail, ElemType data) {
        if (!(*head) || !(*tail)) {
            return -1;
        }
        pDline pmove = (*head)->next;
        int pos = 1;
        while (pmove) {
            if (pmove->data == data) {
                return pos;
            }
            else {
                pmove = pmove->next;
                pos ++;
            }
        }
        printf("找不到...\n");
        return -1;
    }
    

    按元素删除

    //删除找到的第一个元素
    void DeleteDLineFindData(pDline *head, pDline *tail, ElemType data) {
        if (!(*head) || !(*tail)) {
            return;
        }
        int pos = FindDLinePos(head, tail, data);
        if (pos == -1) {
            return;
        }
        else {
            DeleteDLinePos(head, tail, pos);
            return;
        }
    }
    
    //删除所有值为data的结点
    void DeleteDLineFindAllData(pDline *head, pDline *tail, ElemType data) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline pmove = (*head)->next;
        int pos = FindDLinePos(head, tail, data);
        if (pos == -1) {
            return;
        }
        while (pos != -1) {
            DeleteDLinePos(head, tail, pos);
            pmove = (*head)->next;
            pos = FindDLinePos(head, tail, data);
        }
    }
    

    逆置

    //逆置
    void ReverseDLine(pDline *head, pDline *tail) {
        if (!(*head) || !(*tail)) {
            return;
        }
        pDline begin =  (*head);
        pDline end = (*tail);
        while(!(begin==end||begin->prior==end))
        {
            ElemType data = begin->data;
            begin->data = end->data;
            end->data = data;
            end = end->prior;
            begin = begin->next;
        }
    }
    

    拼接

    //拼接
    void JoinDLine(pDline *Lahead, pDline *Latail, pDline *Lbhead, pDline *Lbtail) {
        if (!(*Lahead) || !(*Latail)) {
            return;
        }
        if (!(*Lbhead) || !(*Lbtail)) {
            return;
        }
        if (*Lahead == *Latail && (*Lahead)->next != *Lbtail) {
            *Lahead = *Lbhead;
            *Latail = *Lbtail;
            return;
        }
        if ((*Lahead)->next != *Latail && (*Lahead) == *Lbtail) {
            return;
        }
        pDline pa = (*Lahead)->next;
        pDline pb = (*Lbhead)->next;
        if (pa->data >= pb->data) {
            pDline next = pb->next;
            (*Lahead)->next = pb;
            pb->next = pa;
            pa->prior = pb;
            pa = pb;
            pb = next;
        }
        while (pa && pb) {
            if (pa->data >= pb->data) {
                printf("%d %d\n", pa->data, pb->data);
                pDline next = pb->next;
                pDline front = pa->prior;
                front->next = pb;
                pb->prior = front;
                pb->next = pa;
                pa->prior = pb;
                pa = pb;
                pb = next;
            }
            if (pb == (*Lbtail)) {
                return;
            }
            else {
                pa = pa->next;
            }
        }
        if (pb) {
            pDline front = pa->prior;
            front->next = pb;
            pb->prior = front;
            pa = pb;
        }
    }
    

    测试函数

    void test() {
        Dline Dline;
        pDline head = &Dline;
        pDline tail = &Dline;
        InitDLine(&head, &tail);
        pDline head2 = &Dline;
        pDline tail2 = &Dline;
        InitDLine(&head2, &tail2);
        InsertDLineTail(&head, &tail, 23);
        PrintDLine(head, tail);
        InsertDLineHead(&head, &tail, 20);
        PrintDLine(head, tail);
        DeleteDLineTail(&head, &tail);
        PrintDLine(head, tail);
        DeleteDLineHead(&head, &tail);
        PrintDLine(head, tail);
        InsertDLinePos(&head, &tail, 23, 1);
        InsertDLinePos(&head, &tail, 30, 2);
        InsertDLinePos(&head, &tail, 48, 3);
        InsertDLinePos(&head, &tail, 24, 2);
        InsertDLinePos(&head, &tail, 36, 4);
        InsertDLineHead(&head, &tail, 23);
        InsertDLineTail(&head, &tail, 23);
        PrintDLine(head, tail);
        DeleteDLinePos(&head, &tail, 3);
        PrintDLine(head, tail);
        DeleteDLineFindData(&head, &tail, 23);
        PrintDLine(head, tail);
        DeleteDLineFindAllData(&head, &tail, 23);
        PrintDLine(head, tail);
    //    ReverseDLine(&head, &tail);
    //    PrintDLine(head, tail);
        printf("head2...\n");
        InsertDLineTail(&head2, &tail2, 2);
        InsertDLineTail(&head2, &tail2, 10);
        InsertDLineTail(&head2, &tail2, 13);
        InsertDLineTail(&head2, &tail2, 23);
        InsertDLineTail(&head2, &tail2, 26);
        InsertDLineTail(&head2, &tail2, 60);
        PrintDLine(head2, tail2);
        printf("JoinDLine...\n");
        JoinDLine(&head2, &tail2, &head, &tail);
        PrintDLine(head2, tail2);
    }
    

    相关文章

      网友评论

          本文标题:双向循环链表

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