阅读本文前, 请先阅读以下一篇文章.

数据结构 – 单链表 – ()

一. 带头双向循环链表各种接口的完结

typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;    // 数据域
    struct ListNode* prev;    // 指向前驱节点的指针域
    struct ListNode* next;    // 指向后继节点的指针域
}LTNode;

1. 动态请求一个节点

使用 malloc 函数在堆区上动态拓荒一个节点, data 赋值为 x , prev 指针置空, next 指针置空.

LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newnode->prev = NULL;
    newnode->next = NULL;
    newnode->data = x;
    return newnode;
}

2. 初始化

初始化一个带头双向循环链表, 创造出虚拟头节点 phead, 其 prev 指针指向本身, 其 next 指针也指向本身.

LTNode* LTInit()
{
    LTNode* phead = BuyListNode(0);    // 创造出虚拟头节点 phead
    phead->prev = phead;    // prev 指针指向本身
    phead->next = phead;    // next 指针指向本身
    return phead;
}

3. 销毁

从第一个节点开端逐一销毁链表中的每个节点, 最后销毁虚拟头节点, 然后完结对链表的销毁.

void LTDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* curr = phead->next;
    while (curr != phead) {
        LTNode* curr = phead->next;
        free(curr);
        curr = curr->next;
    }
    free(phead);
}

4. 打印

逐一打印链表中的数据.

void LTPrint(LTNode* phead)
{
    assert(phead);
    printf("<=head=>");
    LTNode* curr = phead->next;
    while (curr != phead) {
        printf("%d<=>", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

5. 判空

判断链表是否为空(虚拟头节点的 next 指针 或 prev 指针指向本身链表即为空).

bool LTEmpty(LTNode* phead)
{
    assert(phead);
    return phead->next == phead;
}

6. 尾插

尾插, 即在链表的尾节点后刺进一个新节点.

尾插前.

LTNode* newnode = BuyListNode(x);

LTNode* tail = phead->prev;

tail->next = newnode;

newnode->prev = tail;

newnode->next = phead;

phead->prev = newnode;

完结尾插后.

void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

7. 尾删

尾删, 即删去链表的尾节点.

尾删前.

LTNode* tail = phead->prev;

LTNode* tailPrev = tail->prev;

tailPrev->next = phead;

phead->prev = tailPrev;

free(tail);

完结尾删后.

void LTPopBack(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev; 
    free(tail); 
}

8. 头插

头插, 即在链表的头节点前刺进一个新节点.

头插前.

LTNode* newnode = BuyListNode(x);

LTNode* first = phead->next;

phead->next = newnode;

newnode->prev = phead;

newnode->next = first;

first->prev = newnode;

完结头插后.

void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* first = phead->next;
    phead->next = newnode; 
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;
}

9. 头删

头删, 删去链表的头节点.

头删前.

LTNode* first = phead->next;

LTNode* second = first->next;

phead->next = second;

second->prev = phead;

free(first);

完结头删后.

void LTPopFront(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* first = phead->next;
    LTNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
}

10. 查找

查找到存放数据 x 的节点的地址, 若查找不到, 返回 NULL .

LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* curr = phead->next;
    while (curr != phead) {
        if (curr->data == x) {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}

11. pos 之前刺进

在内存地址为 pos 的节点前刺进一个新节点.

void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

12. pos 方位删去

删去内存地址为 pos 的节点.

void LTErase(LTNode* pos)
{
    assert(pos);  
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

13. 尾插, 尾删, 头插, 头删的常态化

我们可以认为, 头插、尾插是任意下标方位刺进的特殊化, 头删、尾删是任意下标方位删去的特殊化.

// 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTInsert(phead, x);
}
// 尾删
void LTPopBack(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    LTErase(phead->prev);
}
// 头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTInsert(phead->next, x);  
}
// 头删
void LTPopFront(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    LTErase(phead->next);
}

二. 带头双向循环链表的源码

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;    // 数据域
    struct ListNode* prev;    // 指向前驱节点的指针域
    struct ListNode* next;    // 指向后继节点的指针域 
}LTNode;
// 动态请求一个节点
LTNode* BuyListNode(LTDataType x);
// 初始化
LTNode* LTInit();
// 销毁
void LTDestroy(LTNode* phead);
// 打印
void LTPrint(LTNode* phead);
// 判空
bool LTEmpty(LTNode* phead);
// 尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 尾删
void LTPopBack(LTNode* phead);
// 头插
void LTPushFront(LTNode* phead, LTDataType x);
// 头删
void LTPopFront(LTNode* phead);
// 查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// pos 之前刺进
void LTInsert(LTNode* pos, LTDataType x);
// pos 方位删去
void LTErase(LTNode* pos);

List.c

#include "List.h"
LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newnode->prev = NULL;
    newnode->next = NULL;
    newnode->data = x;
    return newnode;
}
LTNode* LTInit()      
{
    LTNode* phead = BuyListNode(0);    // 创造出虚拟头节点 phead
    phead->prev = phead;    // prev 指针指向本身
    phead->next = phead;    // next 指针指向本身
    return phead;
}
void LTDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* curr = phead->next;
    while (curr != phead) {
        LTNode* curr = phead->next;
        free(curr);
        curr = curr->next;
    }
    free(phead);
}
void LTPrint(LTNode* phead)
{
    assert(phead);
    printf("<=head=>");
    LTNode* curr = phead->next;
    while (curr != phead) {
        printf("%d<=>", curr->data);
        curr = curr->next;
    }
    printf("\n");
}
bool LTEmpty(LTNode* phead)
{
    assert(phead);
    return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    //LTNode* newnode = BuyListNode(x);
    //LTNode* tail = phead->prev;
    //tail->next = newnode;
    //newnode->prev = tail;
    //newnode->next = phead;
    //phead->prev = newnode;
    LTInsert(phead, x);
}
void LTPopBack(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    //LTNode* tail = phead->prev;
    //LTNode* tailPrev = tail->prev;
    //tailPrev->next = phead;
    //phead->prev = tailPrev; 
    //free(tail); 
    LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    //LTNode* newnode = BuyListNode(x);
    //LTNode* first = phead->next;
    //phead->next = newnode; 
    //newnode->prev = phead;
    //newnode->next = first;
    //first->prev = newnode;
    LTInsert(phead->next, x);  
}
void LTPopFront(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    //LTNode* first = phead->next;
    //LTNode* second = first->next;
    //phead->next = second;
    //second->prev = phead;
    //free(first);
    LTErase(phead->next);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* curr = phead->next;
    while (curr != phead) {
        if (curr->data == x) {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
    assert(pos);  
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}