C语言之双向链表详解及实例代码

本文将详细讲解C语言中双向链表的实现原理及实例代码，让读者能够深入理解双向链表的基本概念和用法。

什么是双向链表？

双向链表是一种常见的数据结构，它由多个节点构成，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点，在实际应用中可以用来存储一系列元素，以股票数据为例，将每支股票的编码和名称存储在一个双向链表中，方便快捷地查找和修改。

双向链表的实现原理

在C语言中，我们可以用结构体来定义双向链表中每个节点的数据结构，如下所示：

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

其中，data表示节点中存储的数据，prev指针表示上一个节点的地址，next指针表示下一个节点的地址。当链表为空时，prev和next指针都指向NULL。

插入节点的操作分为两种情况：

• 在链表头部插入节点
• 在链表尾部插入节点

可以定义两个函数来分别实现这两种操作：

// 在链表头部插入节点
void insert_at_head(struct Node **head_ref, int new_data) {
    struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    new_node->prev = NULL;
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*head_ref) = new_node;
}

// 在链表尾部插入节点
void insert_at_end(struct Node **head_ref, int new_data) {
    struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node *last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
    new_node->prev = last;
    return;
}

这两个函数的实现原理都类似，主要是通过malloc函数动态分配内存用来存储新节点的数据，然后判断链表是为空，如果不为空就在头部插入新节点或在尾部插入新节点。

示例说明

下面给出两个示例说明如何使用双向链表来实现对数据的快速查找和修改。

示例1: 股票查询系统

假设我们要实现一个股票查询系统，其中需要存储大量的股票数据，每支股票包括股票代码和股票名称两个信息。我们可以利用双向链表来存储这些数据，然后按照股票代码进行快速查找和修改。实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Stock {
    char code[10];
    char name[100];
    struct Stock *prev;
    struct Stock *next;
};

void insert_stock(struct Stock **head_ref, char code[], char name[]) {
    struct Stock *new_node = (struct Stock*)malloc(sizeof(struct Stock));
    strcpy(new_node->code, code);
    strcpy(new_node->name, name);
    new_node->next = (*head_ref);
    new_node->prev = NULL;
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*head_ref) = new_node;
}

void search_stock(struct Stock **head_ref, char code[]) {
    struct Stock *temp = *head_ref;
    while (temp != NULL) {
        if (strcmp(temp->code, code) == 0) {
            printf("股票代码：%s\n股票名称：%s\n", temp->code, temp->name);
            return;
        }
        temp = temp->next;
    }
    printf("未查找到该股票，请重新输入股票代码！\n");
}

void modify_stock(struct Stock **head_ref, char code[], char name[]) {
    struct Stock *temp = *head_ref;
    while (temp != NULL) {
        if (strcmp(temp->code, code) == 0) {
            strcpy(temp->name, name);
            printf("股票信息修改成功！\n");
            return;
        }
        temp = temp->next;
    }
    printf("未查找到该股票，请重新输入股票代码！\n");
}

int main() {
    struct Stock *head = NULL;
    insert_stock(&head, "000001", "平安银行");
    insert_stock(&head, "000002", "万科A");
    insert_stock(&head, "600036", "招商银行");
    insert_stock(&head, "600519", "贵州茅台");
    insert_stock(&head, "601318", "中国平安");
    char code[10]; char name[100];
    printf("请输入要查询的股票代码：");
    scanf("%s", code);
    search_stock(&head, code);
    printf("请输入要修改的股票代码和股票名称：");
    scanf("%s%s", code, name);
    modify_stock(&head, code, name);
    return 0;
}

示例2: 学生信息管理系统

双向链表还可以用来实现学生信息管理系统，在学生信息管理系统中，我们需要将每个学生的信息存储在一个链表中，然后实现对学生信息的更新、删除和查询等操作。实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Student {
    char name[20];
    int age;
    int id;
    struct Student *prev;
    struct Student *next;
};

void insert_student(struct Student **head_ref, char name[], int age, int id) {
    struct Student *new_node = (struct Student*)malloc(sizeof(struct Student));
    strcpy(new_node->name, name);
    new_node->age = age;
    new_node->id = id;
    new_node->next = (*head_ref);
    new_node->prev = NULL;
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*head_ref) = new_node;
}

void search_student(struct Student **head_ref, int id) {
    struct Student *temp = *head_ref;
    while (temp != NULL) {
        if (temp->id == id) {
            printf("学生姓名：%s\n学生年龄：%d\n学生ID：%d\n", temp->name, temp->age, temp->id);
            return;
        }
        temp = temp->next;
    }
    printf("未查找到该学生，请重新输入学生ID！\n");
}

void delete_student(struct Student **head_ref, int id) {
    struct Student *temp = *head_ref;
    while (temp != NULL) {
        if (temp->id == id) {
            if (temp->prev == NULL) {
                *head_ref = temp->next;
                (*head_ref)->prev = NULL;
                free(temp);
                printf("学生信息删除成功！\n");
                return;
            }
            if (temp->next == NULL) {
                temp->prev->next = NULL;
                free(temp);
                printf("学生信息删除成功！\n");
                return;
            }
            temp->prev->next = temp->next;
            temp->next->prev = temp->prev;
            free(temp);
            printf("学生信息删除成功！\n");
            return;
        }
        temp = temp->next;
    }
    printf("未查找到该学生，请重新输入学生ID！\n");
}

int main() {
    struct Student *head = NULL;
    insert_student(&head, "Tom", 18, 1001);
    insert_student(&head, "Jerry", 20, 1002);
    insert_student(&head, "Lucy", 19, 1003);
    insert_student(&head, "Amy", 18, 1004);
    int option, id, age; char name[20];
    while (1) {
        printf("---------------------------\n");
        printf("1.查询学生信息\n2.删除学生信息\n3.退出\n");
        printf("---------------------------\n");
        printf("请选择要执行的操作：");
        scanf("%d", &option);
        switch(option) {
            case 1:
                printf("请输入要查询的学生ID：");
                scanf("%d", &id);
                search_student(&head, id);
                break;
            case 2:
                printf("请输入要删除的学生ID：");
                scanf("%d", &id);
                delete_student(&head, id);
                break;
            case 3:
                printf("退出系统成功！\n");
                return 0;
            default:
                printf("输入错误，请重新输入！\n");
        }
    }
    return 0;
}

总结

本文详细讲解了C语言中双向链表的实现原理及其应用，同时给出了两个实际示例，希望读者通过学习本文，掌握C语言中链表的基本使用方法，加深对链表的理解，有助于提高C语言程序的编写能力。