双向循环链表

双向链表

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

双向循环链表

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

结构体

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);
}