双向循环链表

一、概念

双向循环链表是指每个结点由三部分组成：数据域、直接前驱结点指针、直接后继结点指针，该链表的最后一个结点的直接后继指针指向头结点，头结点的直接前驱指针指向尾节点。

二、图解

结点图示
在这里插入图片描述

双向循环链表图示
在这里插入图片描述

三、实现源码

常量定义

typedef int ET;

双向循环链表定义

typedef struct Node
{ 
    ET data;
    Node* next;
    Node* prev;
}Node;
typedef Node* BCList;

获取一个新节点

Node* CreateNode(ET val){ 
    Node* s = (Node*)malloc(sizeof(Node));
    assert(s != NULL);
    s->data = val;
    s->next = s->prev = s;
    return s;
}

初始化一个带头结点的双向循环链表

void BCLinkedListInitial(BCList* phead){ 
    *phead = CreateNode(-1);
}

头插法

void BCLinkedListAddFromHead(BCList* phead, ET val){ 
    assert(phead != NULL);
    Node* s = CreateNode(val);
    Node* p = (*phead)->next;
    s->next = p;
    s->prev = *phead;
    (*phead)->next = s;
    p->prev = s;
}

尾插法

void BCLinkedListAddFromBack(BCList* phead, ET val){ 
    assert(phead != NULL);
    Node* s = CreateNode(val);
    Node* p = (*phead)->prev;
    (*phead)->prev = s;
    s->next = *phead;
    s->prev = p;
    p->next = s;
}

显示数据

void BCLinkedListShowData(BCList phead){ 
    Node* p = phead->next;
    while (p != phead){ 
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

判断表是否为空

bool IsEmpty(BCList* phead){ 
    if ((*phead)->prev == (*phead)){ 
        return true;
    }
    return false;
}

删除尾部结点

void BCLinkedListDeleteFromBack(BCList* phead){ 
    assert(phead != NULL);
    if (IsEmpty(phead)){ 
        printf("表空，无法删除！\n");
        return;
    }
    Node* s = (*phead)->prev;
    (*phead)->prev = s->prev;
    s->prev->next = *phead;
    free(s);
}

删除首元结点

void BCLinkedListDeleteFromHead(BCList* phead){ 
    assert(phead != NULL);
    if (IsEmpty(phead)){ 
        printf("表空，无法删除！\n");
        return;
    }
    Node* s = (*phead)->next;
    Node* p = s->next;
    (*phead)->next = p;
    p->prev = *phead;
    free(s);
}

获取尾结点

Node* BCLinkedListGetBack(BCList* phead){ 
    assert(phead != NULL);
    if (IsEmpty(phead)){ 
        printf("表空，无法获得！\n");
        return NULL;
    }
    return (*phead)->prev;
}

获取首元结点

Node* BCLinkedListGetHead(BCList* phead){ 
    assert(phead != NULL);
    if (IsEmpty(phead)){ 
        printf("表空，无法获得！\n");
        return NULL;
    }
    return (*phead)->next;
}

获取表长度

size_t BCLinkedListGetListLength(BCList* phead){ 
    assert(phead != NULL);
    Node* p = (*phead)->next;
    size_t len = 0;
    while (p != (*phead)){ 
        p = p->next;
        len++;
    }
    return len;
}

清空表中数据

void BCLinkedListClear(BCList* phead){ 
    assert(phead != NULL);
    Node* p = (*phead)->next;
    Node* q = (*phead)->next;
    while (q != (*phead)){ 
        q = q->next;
        free(p);
        p = q;
    }
    (*phead)->next = *phead;
    (*phead)->prev = *phead;
}

摧毁表结构

void BCLinkedListDestroy(BCList* phead){ 
    assert(phead != NULL);
    Node* p = (*phead)->next;
    Node* q = (*phead)->next;
    (*phead)->next = NULL;
    while (q != NULL){ 
        q = q->next;
        free(p);
        p = q;
    }
    *phead = NULL;
}

按值查找

Node* BCLinkedListFindByValue(BCList* phead, ET key){ 
    assert(phead != NULL);
    Node* p = (*phead)->next;
    while (p != (*phead) && p->data != key){ 
        p = p->next;
    }
    if (p == *phead) return NULL;
    return p;
}

按值的大小插入

void BCLinkedListInsertByValue(BCList* phead, ET val){ 
    assert(phead != NULL);
    Node *p = (*phead)->next;
    while (p != *phead && p->data < val){ 
        p = p->next;
    }
    if (p == *phead){ 
        BCLinkedListAddFromBack(phead, val);
    }
    else{ 
        Node* s = CreateNode(val);
        Node* q = p->prev;
        q->next = s;
        s->next = p;
        p->prev = s;
        s->prev = q;
    }
}

将表中结点按照数据升序链接

void BCLinkedListSortByData(BCList* phead){ 
    assert(phead != NULL);
    Node *p = (*phead)->next->next;
    Node *q = (*phead)->next->next;
    (*phead)->prev->next = NULL;
    (*phead)->next->next = (*phead);
    (*phead)->prev = (*phead)->next;
    while (q != NULL){ 
        q = q->next;
        if ((*phead)->next->data > p->data){ 
            BCLinkedListAddFromHead(phead, p->data);
            free(p);
        }
        else{ 
            Node* temp = (*phead)->next;
            while (temp->next != (*phead) && temp->data < p->data){ 
                temp = temp->next;
            }
            if (temp->next == (*phead)){ 
                BCLinkedListAddFromBack(phead, p->data);
                free(p);
            }
            else{ 
                p->next = temp;
                p->prev = temp->prev;
                temp->prev->next = p;
                temp->prev = p;
            }
        }
        p = q;
    }
}

反转链表

void BCLinkedListReverseList(BCList* phead){ 
    assert(phead != NULL);
    if (IsEmpty(phead))    return;
    Node* p = (*phead)->prev;
    Node* q = (*phead)->prev;
    (*phead)->next->prev = NULL;    //创造循环结束条件 
    //将头结点置空
    (*phead)->next = (*phead)->prev = *phead;
    while (q != NULL){ 
        q = q->prev;
        BCLinkedListAddFromBack(phead, p->data);
        free(p);
        p = q;
    }
}