用 C 语言编程实现双向链表

一、引言

双向链表是一种重要的数据结构，其每个节点包含两个指针：一个指向前一个节点，另一个指向后一个节点。这种双向链接的特性使得在链表中进行双向遍历变得更加灵活。双向链表的首个节点的左指针和最后一个节点的右指针均为NULL，表示链表的边界。

二、双向链表的插入操作

双向链表的插入操作包括在头部、尾部以及指定位置插入节点。以下是不同插入位置的详细步骤。

A. 在链表头部插入节点

目标：在链表的开始位置添加新节点。

1. 分配新节点并复制数据

   temp = (struct telephone *) malloc(sizeof(struct telephone)); // 动态分配内存
   if (temp == NULL) { // 检查内存分配是否成功
       printf("无法分配内存...\n");
       exit(0); // 退出程序
   }
   printf("输入电话号码: "); 
   scanf("%d", &temp->phone_no); // 读取电话号码
   printf("输入客户姓名: "); 
   scanf("%s", temp->name_cust); // 读取客户姓名
   printf("输入客户地址: "); 
   scanf("%s", temp->address); // 读取客户地址
   temp->next = NULL; // 新节点的下一个指针初始化为NULL
   temp->previous = NULL; // 新节点的前一个指针初始化为NULL
   

2. 使新节点指向原始的第一个节点

   temp->next = begin; // 将新节点的下一个指针指向当前的头节点
   

3. 原始头节点指向新节点

   if (begin != NULL) { // 检查链表是否为空
       begin->previous = temp; // 将原头节点的前指针指向新节点
   }
   

4. 调整头指针

   begin = temp; // 更新头指针指向新节点
   

5. 结束操作

   // 退出插入操作
   

B. 在链表中间插入节点

目标：在指定位置的节点之前插入新节点。

1. 分配新节点并复制数据

   temp = (struct telephone *) malloc(sizeof(struct telephone)); // 分配新节点内存
   printf("输入电话号码: "); 
   scanf("%d", &temp->phone_no); // 读取电话号码
   

2. 新节点指向当前节点的前一个节点

   temp->previous = current->previous; // 新节点的前指针指向当前节点的前一个节点
   

3. 旧节点的下一个节点指向新节点

   current->previous->next = temp; // 更新前一个节点的下一个指针指向新节点
   

4. 更新当前节点的前一个指针

   current->previous = temp; // 将当前节点的前指针指向新节点
   

5. 结束操作

   // 退出插入操作
   

C. 在链表尾部插入节点

目标：在链表的末尾添加新节点。

1. 分配新节点并复制数据

   temp = (struct telephone *) malloc(sizeof(struct telephone)); // 动态分配内存
   printf("输入电话号码: "); 
   scanf("%d", &temp->phone_no); // 读取电话号码
   temp->next = NULL; // 新节点的下一个指针初始化为NULL
   

2. 使最后一个节点指向新节点

   end->next = temp; // 更新最后一个节点的下一个指针指向新节点
   

3. 更新新节点的前指针

   temp->previous = end; // 将新节点的前指针指向当前最后一个节点
   

4. 更新尾指针

   end = temp; // 将尾指针更新为新节点
   

5. 结束操作

   // 退出插入操作
   

三、创建和遍历双向链表的示例程序

以下是一个示例程序，演示如何创建和遍历一个双向链表。

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

// 定义电话号码结构体
struct telephone {
    struct telephone *previous; // 指向前一个节点的指针
    int phone_no; // 电话号码
    char name_cust[20]; // 客户姓名
    char address[30]; // 客户地址
    struct telephone *next; // 指向下一个节点的指针
};

struct telephone *nodepointer = NULL; // 声明链表头指针

// 添加节点的函数
void _add() {
    struct telephone *new_node, *temp;

    new_node = (struct telephone *) malloc(sizeof(struct telephone)); // 分配新节点内存
    if (new_node == NULL) { // 检查内存分配是否成功
        printf("无法分配内存...\n");
        exit(0); // 退出程序
    }

    // 输入数据
    printf("输入电话号码: ");
    scanf("%d", &new_node->phone_no); // 读取电话号码
    printf("输入客户姓名: ");
    scanf("%s", new_node->name_cust); // 读取客户姓名
    printf("输入客户地址: ");
    scanf("%s", new_node->address); // 读取客户地址

    new_node->next = NULL; // 初始化新节点的下一个指针
    new_node->previous = NULL; // 初始化新节点的前一个指针

    if (nodepointer == NULL) { // 如果链表为空
        nodepointer = new_node; // 将新节点设为头节点
    } else {
        temp = nodepointer; // 从头节点开始遍历
        while (temp->next != NULL) { // 遍历到链表末尾
            temp = temp->next; // 移动到下一个节点
        }
        temp->next = new_node; // 最后节点指向新节点
        new_node->previous = temp; // 新节点的前一个指针指向最后节点
    }
}

// 打印链表的函数
void print_list() {
    struct telephone *temp = nodepointer; // 从头节点开始遍历

    while (temp != NULL) { // 当当前节点不为NULL
        printf("\n电话号码: %d", temp->phone_no); // 打印电话号码
        printf("\n客户姓名: %s", temp->name_cust); // 打印客户姓名
        printf("\n地址: %s\n", temp->address); // 打印客户地址
        temp = temp->next; // 移动到下一个节点
    }
}

void main() {
    char answer = 'Y'; // 初始化继续添加的标志

    while (answer == 'y' || answer == 'Y') { // 当用户选择继续添加时
        _add(); // 添加新节点
        printf("\n是否继续添加记录 (Y/N): "); 
        scanf(" %c", &answer); // 读取用户输入
    }

    print_list(); // 打印链表
}

四、总结

双向链表是一种灵活的数据结构，允许在任意位置高效插入和删除节点。本文详细介绍了双向链表的插入操作，并提供了相应的示例代码。通过使用动态内存分配，用户可以有效管理链表节点的创建与销毁。双向链表的双向遍历特性使得其在许多应用中具有广泛的适用性，如浏览器的历史记录管理、音乐播放列表等。