0
0

深度探索 C 语言数据结构——双链表：从键盘输入到增删查改及去重操作全解析

C 语言数据结构——双链表：从键盘输入到增删查改及去重操作全解析

例题

请你基于 C 语言实现一个双链表数据结构，并完成以下功能：

  1. 创建链表：
  • 编写函数通过键盘输入一系列整数来创建一个双链表，输入以特定值（例如 -1）作为结束标志。
  1. 增加节点操作：
  • 实现一个函数，能够在双链表的指定位置插入新的节点。用户需输入要插入的位置（从 1 开始计数，表示第几个节点之前插入）以及要插入节点的值。
  1. 删除节点操作：
  • 编写函数，可根据用户输入的节点值准确删除双链表中对应的节点。若存在多个相同值的节点，需全部删除。
  1. 链表销毁：
  • 当完成所有操作后，实现一个函数将双链表彻底销毁，释放其所占用的全部内存资源，确保无内存泄漏。
  1. 去重操作：
  • 编写函数对已创建的双链表中的数据进行检查，依据节点的数据域判断是否存在重复的值。若有重复节点，仅保留其中一个，删除其余重复的节点，使得链表中每个数据值仅出现一次。

一、创建双链表

  • 我们先回顾一下什么是双链表
  • 双向链表是一种链式数据结构，每个节点包含两个指针，分别指向前驱和后继节点

在这里插入图片描述
在这里插入图片描述

  • 双链表的应用场景
  • 例如，在缓存机制中，可以使用双向链表来实现LRU（最近最少使用）缓存淘汰算法。
  • 在操作系统的任务管理中，也可以使用双向链表来维护任务队列，以便快速地添加、删除和查找任务。
  • 此外，双向链表还常用于实现文本编辑器中的撤销和重做功能、图的深度优先搜索和广度优先搜索等算法中。

（一）定义双链表

  • 接下来定义一个双链表
// 定义双向链表（结点）结构typedefint LTDatatype;typedefstructListNode{
    LTDatatype data;structListNode* next;//下一个节点structListNode* prev;//上一个节点} LTNode;
  • 大家思考一下这段话是做什么的？typedef int LTDatatype;

在这个结构体定义中，data 字段的类型被定义为 LTDatatype，即 int，因此，这段话是将所有使用 data的地方都会自动更新为int数据类型，而不需要逐个修改每个字段的定义

（二）双链表的创建函数

// 创建新节点
LTNode*buyNode(LTDatatype x){
    LTNode* node =(LTNode*)malloc(sizeof(LTNode));
    node->data = x;
    node->next = node->prev = node;return node;}
  • 这个函数的主要目的是创建一个新的双向链表节点，并对其进行初始化，然后返回这个新创建的节点指针

node->data = x

  • 将传入的参数 x 的值赋给新节点的 data 成员变量

node->next = node->prev = node

  • 这行代码将新节点的 next（指向下一个节点的指针）和 prev（指向前一个节点的指针）都初始化为指向自身形成单个双链表

在这里插入图片描述

// 初始化双向链表
LTNode*LTInit(){
    LTNode* phead =buyNode(-1);return phead;}
  • 该函数用于初始化一个双向链表，具体做法是创建一个带有特殊标记值（这里是 -1 ）的头节点，并返回这个头节点的指针，这个头节点将作为整个双向链表的起始标识

总而言之就是将-1设置为双链表的头结点

二、双链表的增加操作

（一）头插

头插操作图解
在这里插入图片描述

// 头插操作voidLTPushFront(LTNode* phead, LTDatatype x){assert(phead);
    LTNode* newnode =buyNode(x);
    newnode->next = phead->next;
    newnode->prev = phead;

    phead->next->prev = newnode;
    phead->next = newnode;}

设置新节点的指针关系：

  • newnode->next = phead->next;：将新节点的next指针指向头节点phead的下一个节点（即原来链表中的第一个实际数据节点）。
  • newnode->prev = phead;：将新节点的prev指针指向头节点phead,调整头节点及其下一个节点的指针关系完成插入：
  • phead->next->prev = newnode;：将原来头节点下一个节点的prev指针指向新节点newnode。
  • phead->next = newnode：将头节点的next指针指向新节点newnode，使得新节点成为新的链表首节点（在不考虑特殊头节点存储数据的情况下）

（二）尾插

在这里插入图片描述

// 尾插操作voidLTPushBack(LTNode* phead, LTDatatype x){assert(phead);
    LTNode* newnode =buyNode(x);
    newnode->prev = phead->prev;
    newnode->next = phead;

    phead->prev->next = newnode;
    phead->prev = newnode;}

设置新节点的指针关系：

  • newnode->prev = phead->prev;：将新节点的prev指针指向当前链表尾节点（因为phead->prev指向链表的尾节点，在带有哑节点的链表结构中通常是这样的设计）。
  • newnode->next = phead;：将新节点的next指针指向头节点phead。

最后调整链表尾节点和头节点的指针关系以完成插入：

  • phead->prev->next = newnode;：将原来的尾节点的next指针指向新节点newnode。
  • phead->prev = newnode;：将头节点的prev指针指向新节点newnode，使得新节点成为新的尾节点

（三）在pos位置之后插入数据

在这里插入图片描述

// 在pos位置之后插入数据voidLTInsert(LTNode* pos, LTDatatype x){assert(pos);

    LTNode* newnode =buyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;

    pos->next->prev = newnode;
    pos->next = newnode;}
  • newnode->next = pos->next;：将新节点的next指针指向pos节点的下一个节点。
  • newnode->prev = pos;：将新节点的prev指针指向pos节点，建立新节点与pos节点的双向连接。
  • pos->next->prev = newnode;：将pos节点原来的下一个节点的prev指针指向新节点newnode。
  • pos->next = newnode;：将pos节点的next指针指向新节点newnode，完成插入操作

三、双链表的删除操作

（一）头删

在这里插入图片描述

// 头删操作voidLTPopFront(LTNode* phead){assert(!LTEmpty(phead));

    LTNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;free(del);
    del =NULL;}
  • 首先通过LTNode* del = phead->next; 找到要删除的节点，也就是链表的第二个节点，并把这个节点的指针存到 del 变量里
  • 然后进行双向链表的指针调整：
  • del->next->prev = phead;

  • 这一步是让要删除节点（del）的下一个节点的 prev（前驱）指针指向链表的头节点 phead。这样就把链表中 del 节点后面的部分和头节点重新连接起来了，保证链表在删除 del 节点后还是一个完整的双向链表。

  • phead->next = del->next;

  • 这一步是让头节点 phead 的 next（后继）指针指向要删除节点（del）的下一个节点。这就相当于把要删除的节点从链表中 “摘” 出去了，链表现在跳过了 del 节点直接连到它后面的节点

（二）尾删

// 尾删操作voidLTPopBack(LTNode* phead){assert(!LTEmpty(phead));

    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;free(del);
    del =NULL;}

  • 首先，通过LTNode* del = phead->prev;语句找到要删除的节点。

  • 在双向链表中，表头节点的prev指针指向链表的最后一个节点，所以这里将链表的最后一个节点的指针赋给del变量，从而确定了要删除的目标节点。
  • 接下来进行双向链表的指针调整操作：
  • del->prev->next = phead;这行代码是让要删除节点（del）的前一个节点（即倒数第二个节点）的next指针指向链表的头节点phead。这样就重新建立了链表倒数第二个节点与头节点的后继关系，使得在删除del节点后，链表的后半部分能够正确地与头节点连接起来，保证了链表结构的完整性。
  • phead->prev = del->prev;这行代码则是让头节点phead的prev指针指向要删除节点（del）的前一个节点（即倒数第二个节点）。

（三）删除指定位置节点

// 删除指定位置节点voidLTErase(LTNode* pos){assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;free(pos);
    pos =NULL;}
  • 对于双向链表，每个节点都有指向前一个节点的prev指针和指向后一个节点的next指针。

  • 当要删除节点pos时：

  • pos->prev->next = pos->next;这行代码使得pos节点的前一个节点（通过pos->prev获取）的next指针指向pos节点的后一个节点（通过pos->next获取）。
  • 这样就重新建立了pos节点前后节点之间的后继关系，相当于-在链表中 “跳过” 了要删除的pos节点，使得链表在删除pos节点后这部分的连接依然是正确的。
  • pos->next->prev = pos->prev;这行代码则是让pos节点的后一个节点（通过pos->next获取）的prev指针指向pos节点的前一个节点（通过pos->next获取）

四、双链表去重操作

// 对双链表去重函数voidListRemoveDuplicates(LTNode* phead){if(phead ==NULL){return;}

    LTNode* pcur = phead->next;while(pcur != phead){
        LTNode* pnext = pcur->next;
        LTNode* prev = pcur->prev;
        LTNode* finder = pcur->next;while(finder != phead){if(finder->data == pcur->data){
                prev->next = finder->next;
                finder->next->prev = prev;
                LTNode* temp = finder;
                finder = finder->next;free(temp);}else{
                prev = finder;
                finder = finder->next;}}
        pcur = pnext;}}

首先检查链表是否为空：

  • 函数一开始先看看传入的链表头指针 phead 是不是为空。要是为空，那就说明链表不存在或者是空链表呀，这种情况下就不用做去重操作了，直接返回就行。

遍历链表：

  • 先让一个指针 pcur 指向链表头节点 phead 的下一个节点，因为通常头节点可能只是个标识，真正要处理数据的节点从它下一个开始。
  • 然后通过一个 while 循环，只要 pcur 指向的节点不是头节点（因为双向链表遍历一圈回来就到头节点了），就一直循环下去。在每次循环结束时，会把 pcur 指针更新为它当前指向节点的下一个节点，这样就能遍历整个链表啦。

查找并删除重复节点：

  • 对于 pcur 指向的每一个当前节点：先准备好几个指针，一个指向 pcur 的下一个节点 pnext，一个指向 pcur 的前一个节点 prev，还有一个 finder 指针也指向 pcur 的下一个节点。然后让 finder 指针从 pcur 的下一个节点开始，沿着链表往后找，一直找到头节点为止（这就是一圈啦）。

在找的过程中：

  • 如果发现 finder 指针指向的节点数据值和 pcur 指向的节点数据值一样，那就说明找到了重复节点，这时候就要删掉它啦。

  • 删掉的办法就是调整一下链表的指针，让 pcur 的前一个节点 prev 的下一个指针指向 finder 指针指向节点的下一个节点，同时让 finder 指针指向节点的下一个节点的前一个指针指向 prev。然后把要删掉的节点用一个临时指针 temp 存起来，把 finder 指针更新为它下一个节点，最后用 free 把存起来的节点释放掉，这样就删掉重复节点啦。

  • 如果发现 finder 指针指向的节点数据值和 pcur 指向的节点数据值不一样，那就把 prev 指针更新为 finder 指针指向的节点，把 finder 指针更新为它下一个节点，接着继续找有没有其他重复节点

五、销毁双链表

// 销毁双向链表voidLTDesTroy(LTNode* phead){
    LTNode* pcur = phead->next;while(pcur != phead){
        LTNode* next = pcur->next;free(pcur);
        pcur = next;}free(phead);
    phead =NULL;}

六、菜单函数的实现

// 菜单函数intmenu(){int choose;printf("请选择对双链表的操作：\n");printf("1. 删除数据\n");printf("2. 插入数据\n");printf("3. 销毁双链表\n");printf("4. 查找数据\n");printf("5. 对双链表去重\n");printf("请输入你的选择：");scanf("%d",&choose);return choose;}// 插入数据菜单函数intinsmenu(){int choose;printf("请选择插入数据的方式：\n");printf("1. 头插\n");printf("2. 尾插\n");printf("3. 指定一个数之前插入\n");printf("请输入你的插入操作选择：\n");scanf("%d",&choose);return choose;}// 删除数据菜单函数intdelmenu(){int delchoice;printf("1. 在头部删除节点\n");printf("2. 在尾部删除节点\n");printf("3. 删除指定位置的节点\n");printf("4. 删除指定值的节点\n");printf("请输入你的删除操作选择: \n");scanf("%d",&delchoice);return delchoice;}

七、主函数的实现

intmain(){
    LTNode* plist =LTInit();int num;printf("请输入双链表的节点个数：");scanf("%d",&num);printf("请依次输入双链表的节点值：\n");for(int i =0; i < num; i++){int value;scanf("%d",&value);LTPushBack(plist, value);}printf("初始化后的双链表为：\n");LTPrint(plist);int input;
    LTNode* find;int value;do{
        input =menu();switch(input){case1:{int delchoice =delmenu();switch(delchoice){case1:if(!LTEmpty(plist)){LTPopFront(plist);}break;case2:if(!LTEmpty(plist)){LTPopBack(plist);}break;case3:{printf("请输入要删除节点的位置：");int pos;scanf("%d",&pos);
                LTNode* pcur = plist->next;for(int i =0; i < pos; i++){
                    pcur = pcur->next;}LTErase(pcur);break;}case4:{printf("请输入要删除的值：");scanf("%d",&value);
                find =LTFind(plist, value);if(find !=NULL){LTErase(find);}break;}default:printf("无效的删除操作选择\n");break;}break;}case2:{int inschoice =insmenu();switch(inschoice){case1:printf("请输入要插入的值：");scanf("%d",&value);LTPushFront(plist, value);break;case2:printf("请输入要插入的值：");scanf("%d",&value);LTPushBack(plist, value);break;case3:{printf("请输入指定的数：");scanf("%d",&value);
                find =LTFind(plist, value);if(find !=NULL){printf("请输入要插入的值：");scanf("%d",&value);LTInsert(find, value);}else{printf("未找到指定的数\n");}break;}default:printf("无效的插入操作选择\n");break;}break;}case3:LTDesTroy(plist);
            plist =NULL;break;case4:printf("请输入要查找的值：");scanf("%d",&value);
            find =LTFind(plist, value);if(find !=NULL){printf("找到了，该值所在节点的下一个节点数据为：%d\n", find->next->data);}else{printf("未找到指定的值\n");}break;case5:ListRemoveDuplicates(plist);break;default:printf("无效的操作选择\n");break;}if(plist !=NULL){LTPrint(plist);}}while(input !=3);return0;}

八、本文的所有源代码

List.h文件

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>// 定义双向链表（结点）结构typedefint LTDatatype;typedefstructListNode{
    LTDatatype data;structListNode* next;//下一个节点structListNode* prev;//上一个节点} LTNode;// 初始化
LTNode*LTInit();// 销毁链表voidLTDesTroy(LTNode* phead);// 打印链表voidLTPrint(LTNode* phead);// 判断链表是否为空
bool LTEmpty(LTNode* phead);// 尾插voidLTPushBack(LTNode* phead, LTDatatype x);// 头插voidLTPushFront(LTNode* phead, LTDatatype x);// 尾删voidLTPopBack(LTNode* phead);// 头删voidLTPopFront(LTNode* phead);// 在pos位置之后插入数据voidLTInsert(LTNode* pos, LTDatatype x);// 删除指定位置节点voidLTErase(LTNode* pos);// 查找指定值的节点
LTNode*LTFind(LTNode* phead, LTDatatype x);// 菜单函数intmenu();// 插入数据菜单函数intinsmenu();// 删除数据菜单函数intdelmenu();// 对双链表去重函数voidListRemoveDuplicates(LTNode* phead);

List.c文件

#pragmawarning(disable:4996)#include"List.h"// 创建新节点
LTNode*buyNode(LTDatatype x){
    LTNode* node =(LTNode*)malloc(sizeof(LTNode));
    node->data = x;
    node->next = node->prev = node;return node;}// 初始化双向链表
LTNode*LTInit(){
    LTNode* phead =buyNode(-1);return phead;}// 销毁双向链表voidLTDesTroy(LTNode* phead){
    LTNode* pcur = phead->next;while(pcur != phead){
        LTNode* next = pcur->next;free(pcur);
        pcur = next;}free(phead);
    phead =NULL;}// 打印双向链表voidLTPrint(LTNode* phead){
    LTNode* pcur = phead->next;while(pcur != phead){printf("%d <-> ", pcur->data);
        pcur = pcur->next;}printf("\n");}// 判断双向链表是否为空
bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}// 尾插操作voidLTPushBack(LTNode* phead, LTDatatype x){assert(phead);
    LTNode* newnode =buyNode(x);
    newnode->prev = phead->prev;
    newnode->next = phead;

    phead->prev->next = newnode;
    phead->prev = newnode;}// 头插操作voidLTPushFront(LTNode* phead, LTDatatype x){assert(phead);
    LTNode* newnode =buyNode(x);
    newnode->next = phead->next;
    newnode->prev = phead;

    phead->next->prev = newnode;
    phead->next = newnode;}// 尾删操作voidLTPopBack(LTNode* phead){assert(!LTEmpty(phead));

    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;free(del);
    del =NULL;}// 头删操作voidLTPopFront(LTNode* phead){assert(!LTEmpty(phead));

    LTNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;free(del);
    del =NULL;}// 在pos位置之后插入数据voidLTInsert(LTNode* pos, LTDatatype x){assert(pos);

    LTNode* newnode =buyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;

    pos->next->prev = newnode;
    pos->next = newnode;}// 删除指定位置节点voidLTErase(LTNode* pos){assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;free(pos);
    pos =NULL;}// 查找指定值的节点
LTNode*LTFind(LTNode* phead, LTDatatype x){

    LTNode* pcur = phead->next;while(pcur != phead){if(pcur->data == x){return pcur;}
        pcur = pcur->next;}returnNULL;}// 对双链表去重函数voidListRemoveDuplicates(LTNode* phead){if(phead ==NULL){return;}

    LTNode* pcur = phead->next;while(pcur != phead){
        LTNode* pnext = pcur->next;
        LTNode* prev = pcur->prev;
        LTNode* finder = pcur->next;while(finder != phead){if(finder->data == pcur->data){
                prev->next = finder->next;
                finder->next->prev = prev;
                LTNode* temp = finder;
                finder = finder->next;free(temp);}else{
                prev = finder;
                finder = finder->next;}}
        pcur = pnext;}}// 菜单函数intmenu(){int choose;printf("请选择对双链表的操作：\n");printf("1. 删除数据\n");printf("2. 插入数据\n");printf("3. 销毁双链表\n");printf("4. 查找数据\n");printf("5. 对双链表去重\n");printf("请输入你的选择：");scanf("%d",&choose);return choose;}// 插入数据菜单函数intinsmenu(){int choose;printf("请选择插入数据的方式：\n");printf("1. 头插\n");printf("2. 尾插\n");printf("3. 指定一个数之前插入\n");printf("请输入你的插入操作选择：\n");scanf("%d",&choose);return choose;}// 删除数据菜单函数intdelmenu(){int delchoice;printf("1. 在头部删除节点\n");printf("2. 在尾部删除节点\n");printf("3. 删除指定位置的节点\n");printf("4. 删除指定值的节点\n");printf("请输入你的删除操作选择: \n");scanf("%d",&delchoice);return delchoice;}

test.c文件

#pragmawarning(disable:4996)#include"List.h"intmain(){
    LTNode* plist =LTInit();int num;printf("请输入双链表的节点个数：");scanf("%d",&num);printf("请依次输入双链表的节点值：\n");for(int i =0; i < num; i++){int value;scanf("%d",&value);LTPushBack(plist, value);}printf("初始化后的双链表为：\n");LTPrint(plist);int input;
    LTNode* find;int value;do{
        input =menu();switch(input){case1:{int delchoice =delmenu();switch(delchoice){case1:if(!LTEmpty(plist)){LTPopFront(plist);}break;case2:if(!LTEmpty(plist)){LTPopBack(plist);}break;case3:{printf("请输入要删除节点的位置：");int pos;scanf("%d",&pos);
                LTNode* pcur = plist->next;for(int i =0; i < pos; i++){
                    pcur = pcur->next;}LTErase(pcur);break;}case4:{printf("请输入要删除的值：");scanf("%d",&value);
                find =LTFind(plist, value);if(find !=NULL){LTErase(find);}break;}default:printf("无效的删除操作选择\n");break;}break;}case2:{int inschoice =insmenu();switch(inschoice){case1:printf("请输入要插入的值：");scanf("%d",&value);LTPushFront(plist, value);break;case2:printf("请输入要插入的值：");scanf("%d",&value);LTPushBack(plist, value);break;case3:{printf("请输入指定的数：");scanf("%d",&value);
                find =LTFind(plist, value);if(find !=NULL){printf("请输入要插入的值：");scanf("%d",&value);LTInsert(find, value);}else{printf("未找到指定的数\n");}break;}default:printf("无效的插入操作选择\n");break;}break;}case3:LTDesTroy(plist);
            plist =NULL;break;case4:printf("请输入要查找的值：");scanf("%d",&value);
            find =LTFind(plist, value);if(find !=NULL){printf("找到了，该值所在节点的下一个节点数据为：%d\n", find->next->data);}else{printf("未找到指定的值\n");}break;case5:ListRemoveDuplicates(plist);break;default:printf("无效的操作选择\n");break;}if(plist !=NULL){LTPrint(plist);}}while(input !=3);return0;}

非常感谢您的阅读，喜欢的话记得三连哦
在这里插入图片描述

标签： c语言 数据结构 开发语言
本文转载自: https://blog.csdn.net/2402_83322742/article/details/143914004
版权归原作者 珹洺 所有， 如有侵权，请联系我们删除。
登录后发布评论

“深度探索 C 语言数据结构——双链表：从键盘输入到增删查改及去重操作全解析”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航