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

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语言程序的编写能力。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言之双向链表详解及实例代码 - Python技术站

(0)
上一篇 2023年5月24日
下一篇 2023年5月24日

相关文章

  • Android保存App异常信息到本地

    下面是一份完整的攻略,详细讲解了如何在Android应用中保存App异常信息到本地: 1. 异常信息及其重要性 在Android应用开发中,异常信息是非常重要的一个方面。当应用程序出现错误或崩溃时,异常信息能够提供有关错误的详细信息,例如错误的栈追踪信息和错误发生的原因。 因为Android应用的结构和环境复杂,异常情况的出现也是时有发生。在使用Androi…

    C 2023年5月23日
    00
  • 在C语言中向链接列表添加节点

    下面是在C语言中向链接列表添加节点的完整使用攻略。 什么是链接列表 链接列表(Linked List)是由多个节点组成的数据结构,每个节点包含一个数据元素和指向下一个节点的指针。 链接列表的优点是可以高效地插入和删除节点,而且不需要预先知道列表的大小。但缺点是访问任意一个节点的时间复杂度为O(n),不如数组高效。 如何向链接列表添加节点 首先,我们需要定义节…

    C 2023年5月9日
    00
  • C语言中的结构体的入门学习教程

    下面就是针对“C语言中的结构体的入门学习教程”的完整攻略: 什么是结构体 在C语言中,结构体是一种自定义的数据类型,可以将多个不同类型的数据组合成一个整体,以实现更方便的数据处理。 结构体定义的格式如下: struct 结构体名{ 数据类型1 成员名1; 数据类型2 成员名2; …… 数据类型n 成员名n; }; 其中,结构体名是自定义的类型名称,成…

    C 2023年5月23日
    00
  • C++中Boost的转换函数

    Boost库是一个为C++编程语言提供了许多扩展和增强功能的库。其中Boost库中的转换函数以简单的方式支持数字、字符串、日期和时间之间的转换。此处介绍Boost库转换函数的相关知识和应用。 Boost库的转换函数 Boost库提供了一些方便的转换函数,这些转换函数能够涉及到数字、字符串和时间等类型之间的转换。以下为一些常见的转换函数: lexical_ca…

    C 2023年5月23日
    00
  • 详解C++中的ANSI与Unicode和UTF8三种字符编码基本原理与相互转换

    下面是详解C++中的ANSI与Unicode和UTF8三种字符编码基本原理与相互转换的攻略。 一、字符编码的概念 字符编码是将字符集中的每个字符映射到某个二进制值的一种方法。常见的字符编码方式包括ASCII、ANSI、Unicode和UTF-8等。 ANSI编码指的是使用单字节表示每个字符的编码方式,它的编码范围是0-127,这种编码方式主要在早期的计算机和…

    C 2023年5月23日
    00
  • Postgresql 数据库转义字符操作

    介绍 PostgreSQL是一个自由、开放源代码的对象-关系型数据库管理系统。当需要在数据库中进行特殊字符的插入或查询时,就需要转义这些字符,否则数据无法正常插入或查询。PostgreSQL提供了多种转义字符的操作方法。 转义字符 以下是在PostgreSQL中使用转义字符的方法: 使用反斜杠:使用 “\” 来转义字符,前面跟上该字符。例如: sql INS…

    C 2023年5月23日
    00
  • 如何利用C++实现mysql数据库的连接池详解

    如何利用C++实现mysql数据库的连接池详解 什么是数据库连接池 数据库连接池是一种用来缓存数据库连接的技术,它可以提高数据库的访问效率,避免重复连接数据库导致的资源浪费和性能下降。在高并发的情况下,数据库连接池会发挥更大的优势。 如何利用C++实现mysql数据库的连接池 1. 安装mysql C++ Connector mysql C++ Connec…

    C 2023年5月22日
    00
  • C语言如何利用异或进行两个值的交换详解

    可以使用异或运算符(^)来交换两个变量的值,其原理是利用异或运算符具有自反性和对称性的特点。 具体来说,设有两个变量 a 和 b,其初始值分别为 A 和 B,则交换过程可以如下描述: 1.将 a 与 b 进行异或运算,即 a = a ^ b; 2.将 b 与 a 进行异或运算,即 b = b ^ a; 3.将 a 与 b 进行异或运算,即 a = a ^ b…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部