C数据结构之双链表详细示例分析

作为本网站的作者，我很高兴为你讲解C数据结构之双链表详细示例分析的完整攻略。

双链表简介与定义

双链表是链表的一种，在链表中每一个节点都有一个指针域，指向下一个节点，这个指针域称为next指针；而在双链表中每一个节点也有两个指针域，一个指向前驱节点，另一个指向后继节点，即prev指针与next指针。由于双链表存在两个指针域，因此它支持双向遍历，无论是正向还是反向遍历，都是很方便的。

在C语言中，我们可以采用结构体来定义双链表节点的数据类型，结构体中包含节点数据和两个指针域，定义如下：

struct DListNode {
    int val;
    struct DListNode *prev, *next;
};

其中，val表示双链表节点存储的数据，prev指针域表示指向前驱节点的指针，next指针域表示指向后继节点的指针。

双链表基本操作

双链表的基本操作包括插入节点、删除节点、查找节点和遍历节点等。下面我们介绍这些操作的具体实现。

插入节点

双链表中插入一个节点需要分三步操作：

1. 创建一个新节点
2. 将新节点的next指针指向原链表中当前位置下一个节点（插入在链表中间或尾部）或者指向NULL（插入在链表头部或空链表）
3. 将新节点的prev指针指向原链表中当前位置的前一个节点（插入在链表中间或头部）或者指向NULL（插入在链表尾部或空链表）

以下是一个示例代码：

void DListInsert(struct DListNode **head, struct DListNode *node, int pos) {
    if (pos < 1) pos = 1;
    if (!*head) {
        *head = node;
        return;
    }
    if (pos == 1) {
        node->next = *head;
        (*head)->prev = node;
        *head = node;
        return;
    }
    struct DListNode *p = *head;
    for (int i = 2; i < pos && p->next; i++) p = p->next;
    node->next = p->next;
    p->next = node;
    node->prev = p;
    if (node->next) node->next->prev = node;
}

上述代码实现了指定位置插入元素的操作，并考虑了空链表和插入头节点的情况。

删除节点

双链表中删除一个节点需要分两步操作：

1. 修改被删除节点前驱节点的next指针，使其指向被删除节点的后继节点
2. 修改被删除节点的后继节点的prev指针，使其指向被删除节点的前驱节点

以下是一个示例代码：

void DListDelete(struct DListNode **head, int val) {
    struct DListNode *p = *head;
    while (p && p->val != val) p = p->next;
    if (p) {
        if (p->prev) p->prev->next = p->next;
        else *head = p->next;
        if (p->next) p->next->prev = p->prev;
        free(p);
    }
}

上述代码实现了删除指定元素的操作，并考虑了被删除元素是头节点的情况。

查找节点

对于双链表查找指定元素，我们可以用遍历的方式逐个比较节点的元素值。以下是一个示例代码：

struct DListNode *DListFind(struct DListNode *head, int val) {
    struct DListNode *p = head;
    while (p && p->val != val) p = p->next;
    return p;
}

遍历节点

双链表的遍历可以使用指针移动实现。以下是一个示例代码：

void DListTraverse(struct DListNode *head) {
    struct DListNode *p = head;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

示例说明

示例一：双向链表的构建

int main() {
    struct DListNode *head = NULL;
    int a[] = {1, 2, 3, 4, 5};
    int n = sizeof(a) / sizeof(int);
    for (int i = 0; i < n; i++)
        DListInsert(&head, GetNewDListNode(a[i]), i + 1);
    DListTraverse(head);
    return 0;
}

上述代码中，我们首先定义双链表头节点为NULL，然后插入1,2,3,4,5五个元素到双链表中，并使用DListTraverse函数遍历节点。输出结果应该为：

1 2 3 4 5

示例二：双向链表的删除操作

int main() {
    struct DListNode *head = NULL;
    int a[] = {1, 2, 3, 4, 5};
    int n = sizeof(a) / sizeof(int);
    for (int i = 0; i < n; i++)
        DListInsert(&head, GetNewDListNode(a[i]), i + 1);
    DListTraverse(head);
    DListDelete(&head, 3);
    DListDelete(&head, 1);
    DListTraverse(head);
    return 0;
}

上述代码中，我们首先定义双链表头节点为NULL，然后插入1,2,3,4,5五个元素到双链表中。接着使用DListTraverse函数遍历双链表，输出结果应该为：

1 2 3 4 5

然后，我们使用DListDelete函数依次删除元素3以及元素1，并使用DListTraverse再次遍历双链表，输出结果应该为：

2 4 5

总结

本篇文章中，我们讲解了C数据结构之双链表的基本定义及常见操作，包括插入节点、删除节点、查找节点和遍历节点等。我们还使用了两个示例说明双链表的构建和删除两个操作。希望这篇文章能对大家有所帮助。