下面是C语言中双链表的基本操作的完整攻略。

双链表的基本操作

什么是双链表

双向链表（Doubly linked list）是链表的一种，它同样由一系列的节点组成，每个结点分别含有指向前驱和后继结点的两个指针。这种结构允许双向遍历。常见的操作有前插、后插、删除、查找等，下面详细介绍其基本操作。

双链表的结构

双链表的结构如下所示：

struct node{
    int data;
    struct node *pre;
    struct node *next;
};

其中，data表示该节点存储的数据，pre表示该节点的前驱指针，next表示该节点的后继指针。

新建双链表

新建一个双链表需要定义一个头指针，头指针指向链表的头结点，且头结点不存储数据，只是一个空节点。

struct node head;
struct node *list = &head;//定义头指针

head.pre = NULL;
head.next = NULL;

以上代码表示创建了一个空的双链表，头指针指向的是头结点。

双链表的插入

首节点插入

int insert_head(struct node *list, int data){
    struct node *new_node = (struct node*)malloc(sizeof(struct node));
    if(new_node == NULL){//内存分配失败，返回0
        return 0;
    }
    new_node->data = data;
    new_node->pre = list;//头结点的前驱指针指向空
    new_node->next = list->next;
    list->next->pre = new_node;
    list->next = new_node;
    return 1;//插入成功，返回1
}

在双链表的头部插入一个新的节点，需要执行以下步骤：

创建一个新的节点 new_node；
将新节点的数据域赋值为 data；
将新节点的前驱指针指向头结点；
将新节点的后继指针指向头结点的后继结点；
将头结点的后继结点的前驱指针指向新节点；
将头结点的后继指针指向新节点；
插入成功，返回1。

尾节点插入

int insert_tail(struct node *list, int data){
    struct node *new_node = (struct node*)malloc(sizeof(struct node));
    if(new_node == NULL){//内存分配失败，返回0
        return 0;
    }
    struct node *p = list;
    while(p->next != NULL){
        p = p->next;
    }
    new_node->data = data;
    new_node->pre = p;
    new_node->next = NULL;
    p->next = new_node;
    return 1;//插入成功，返回1
}

在双链表的尾部插入一个新的节点，需要执行以下步骤：

创建一个新的节点 new_node；
将新节点的数据域赋值为 data；
找到双链表的尾节点 p；
将新节点的前驱指针指向尾节点 p；
将新节点的后继指针指向空；
将尾节点 p 的后继指针指向新节点；
插入成功，返回1。

双链表的删除

int delete_node(struct node *list, int data){
    struct node *p = list->next;
    while(p != NULL){
        if(p->data == data){
            p->pre->next = p->next;
            p->next->pre = p->pre;
            free(p);
            return 1;//删除成功，返回1
        }
        p = p->next;
    }
    return 0;//删除失败，返回0
}

双链表的删除操作需要传入双链表的头指针和要删除节点的值 data，需要执行以下步骤：

找到要删除的节点 p；
将要删除节点前一个节点的后继指针指向要删除节点的后继节点；
将要删除节点后一个节点的前驱指针指向要删除节点的前一个节点；
释放要删除的节点的内存空间；
删除成功，返回1；
如果没有找到要删除的节点，返回0。

双链表的查找

struct node *search_node(struct node *list, int data){
    struct node *p = list->next;
    while(p != NULL){
        if(p->data == data){
            return p;//找到节点，返回该节点
        }
        p = p->next;
    }
    return NULL;//未找到节点，返回NULL
}

双链表的查找操作需要传入双链表的头指针和要查找节点的值 data，需要执行以下步骤：

找到要查找的节点 p；
如果找到了，返回该节点；
如果没有找到，返回 NULL。

示例说明

下面是双链表的创建、插入、删除和查找的示例：

int main(){
    struct node head;
    struct node *list = &head;

    head.pre = NULL;
    head.next = NULL;

    insert_head(list, 1);
    insert_head(list, 2);
    insert_tail(list, 3);

    printf("双链表为：");
    struct node *p = list->next;
    while(p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    delete_node(list, 2);

    printf("删除节点2后的双链表为：");
    p = list->next;
    while(p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    struct node *target_node = search_node(list, 3);
    if(target_node != NULL){
        printf("查找节点3成功！\n");
    }else{
        printf("查找节点3失败！\n");
    }

    return 0;
}

输出结果如下：

双链表为：2 1 3
删除节点2后的双链表为：1 3
查找节点3成功！

以上代码示例创建了一个双链表，并在双链表的头部和尾部插入节点，然后删除了值为2的节点，最后查找了值为3的节点。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言中双链表的基本操作 - Python技术站

C语言中双链表的基本操作