C 语言数据结构——双链表：从键盘输入到增删查改及去重操作全解析
例题
请你基于 C 语言实现一个双链表数据结构，并完成以下功能：
- 创建链表：
- 编写函数通过键盘输入一系列整数来创建一个双链表，输入以特定值（例如 -1）作为结束标志。
- 增加节点操作：
- 实现一个函数，能够在双链表的指定位置插入新的节点。用户需输入要插入的位置（从 1 开始计数，表示第几个节点之前插入）以及要插入节点的值。
- 删除节点操作：
- 编写函数，可根据用户输入的节点值准确删除双链表中对应的节点。若存在多个相同值的节点，需全部删除。
- 链表销毁：
- 当完成所有操作后，实现一个函数将双链表彻底销毁，释放其所占用的全部内存资源，确保无内存泄漏。
- 去重操作：
- 编写函数对已创建的双链表中的数据进行检查，依据节点的数据域判断是否存在重复的值。若有重复节点，仅保留其中一个，删除其余重复的节点，使得链表中每个数据值仅出现一次。
一、创建双链表
- 我们先回顾一下什么是双链表
- 双向链表是一种链式数据结构，每个节点包含两个指针，分别指向前驱和后继节点
- 双链表的应用场景
- 例如，在缓存机制中，可以使用双向链表来实现LRU（最近最少使用）缓存淘汰算法。
- 在操作系统的任务管理中，也可以使用双向链表来维护任务队列，以便快速地添加、删除和查找任务。
- 此外，双向链表还常用于实现文本编辑器中的撤销和重做功能、图的深度优先搜索和广度优先搜索等算法中。
（一）定义双链表
- 接下来定义一个双链表
// 定义双向链表（结点）结构
typedef int LTDatatype;
typedef struct ListNode
{
LTDatatype data;
struct ListNode* next;//下一个节点
struct ListNode* 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设置为双链表的头结点
二、双链表的增加操作
（一）头插
头插操作图解
// 头插操作
void LTPushFront(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，使得新节点成为新的链表首节点（在不考虑特殊头节点存储数据的情况下）
（二）尾插
// 尾插操作
void LTPushBack(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位置之后插入数据
void LTInsert(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，完成插入操作
三、双链表的删除操作
（一）头删
// 头删操作
void LTPopFront(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 节点直接连到它后面的节点
（二）尾删
// 尾删操作
void LTPopBack(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）的前一个节点（即倒数第二个节点）。
（三）删除指定位置节点
// 删除指定位置节点
void LTErase(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获取）
四、双链表去重操作
// 对双链表去重函数
void ListRemoveDuplicates(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 指针更新为它下一个节点，接着继续找有没有其他重复节点
五、销毁双链表
// 销毁双向链表
void LTDesTroy(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
六、菜单函数的实现
// 菜单函数
int menu() {
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;
}
// 插入数据菜单函数
int insmenu() {
int choose;
printf("请选择插入数据的方式：\n");
printf("1. 头插\n");
printf("2. 尾插\n");
printf("3. 指定一个数之前插入\n");
printf("请输入你的插入操作选择：\n");
scanf("%d", &choose);
return choose;
}
// 删除数据菜单函数
int delmenu() {
int delchoice;
printf("1. 在头部删除节点\n");
printf("2. 在尾部删除节点\n");
printf("3. 删除指定位置的节点\n");
printf("4. 删除指定值的节点\n");
printf("请输入你的删除操作选择: \n");
scanf("%d", &delchoice);
return delchoice;
}
七、主函数的实现
int main()
{
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)
{
case 1:
{
int delchoice = delmenu();
switch (delchoice)
{
case 1:
if (!LTEmpty(plist))
{
LTPopFront(plist);
}
break;
case 2:
if (!LTEmpty(plist))
{
LTPopBack(plist);
}
break;
case 3: {
printf("请输入要删除节点的位置：");
int pos;
scanf("%d", &pos);
LTNode* pcur = plist->next;
for (int i = 0; i < pos; i++)
{
pcur = pcur->next;
}
LTErase(pcur);
break;
}
case 4:
{
printf("请输入要删除的值：");
scanf("%d", &value);
find = LTFind(plist, value);
if (find != NULL)
{
LTErase(find);
}
break;
}
default:
printf("无效的删除操作选择\n");
break;
}
break;
}
case 2:
{
int inschoice = insmenu();
switch (inschoice)
{
case 1:
printf("请输入要插入的值：");
scanf("%d", &value);
LTPushFront(plist, value);
break;
case 2:
printf("请输入要插入的值：");
scanf("%d", &value);
LTPushBack(plist, value);
break;
case 3:
{
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;
}
case 3:
LTDesTroy(plist);
plist = NULL;
break;
case 4:
printf("请输入要查找的值：");
scanf("%d", &value);
find = LTFind(plist, value);
if (find != NULL) {
printf("找到了，该值所在节点的下一个节点数据为：%d\n", find->next->data);
}
else
{
printf("未找到指定的值\n");
}
break;
case 5:
ListRemoveDuplicates(plist);
break;
default:
printf("无效的操作选择\n");
break;
}
if (plist != NULL)
{
LTPrint(plist);
}
} while (input != 3);
return 0;
}
八、本文的所有源代码
List.h文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 定义双向链表（结点）结构
typedef int LTDatatype;
typedef struct ListNode
{
LTDatatype data;
struct ListNode* next;//下一个节点
struct ListNode* prev;//上一个节点
} LTNode;
// 初始化
LTNode* LTInit();
// 销毁链表
void LTDesTroy(LTNode* phead);
// 打印链表
void LTPrint(LTNode* phead);
// 判断链表是否为空
bool LTEmpty(LTNode* phead);
// 尾插
void LTPushBack(LTNode* phead, LTDatatype x);
// 头插
void LTPushFront(LTNode* phead, LTDatatype x);
// 尾删
void LTPopBack(LTNode* phead);
// 头删
void LTPopFront(LTNode* phead);
// 在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x);
// 删除指定位置节点
void LTErase(LTNode* pos);
// 查找指定值的节点
LTNode* LTFind(LTNode* phead, LTDatatype x);
// 菜单函数
int menu();
// 插入数据菜单函数
int insmenu();
// 删除数据菜单函数
int delmenu();
// 对双链表去重函数
void ListRemoveDuplicates(LTNode* phead);
List.c文件
#pragma warning(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;
}
// 销毁双向链表
void LTDesTroy(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
// 打印双向链表
void LTPrint(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;
}
// 尾插操作
void LTPushBack(LTNode* phead, LTDatatype x)
{
assert(phead);
LTNode* newnode = buyNode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
// 头插操作
void LTPushFront(LTNode* phead, LTDatatype x)
{
assert(phead);
LTNode* newnode = buyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
// 尾删操作
void LTPopBack(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
// 头删操作
void LTPopFront(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}
// 在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x)
{
assert(pos);
LTNode* newnode = buyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
// 删除指定位置节点
void LTErase(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;
}
return NULL;
}
// 对双链表去重函数
void ListRemoveDuplicates(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;
}
}
// 菜单函数
int menu() {
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;
}
// 插入数据菜单函数
int insmenu() {
int choose;
printf("请选择插入数据的方式：\n");
printf("1. 头插\n");
printf("2. 尾插\n");
printf("3. 指定一个数之前插入\n");
printf("请输入你的插入操作选择：\n");
scanf("%d", &choose);
return choose;
}
// 删除数据菜单函数
int delmenu() {
int delchoice;
printf("1. 在头部删除节点\n");
printf("2. 在尾部删除节点\n");
printf("3. 删除指定位置的节点\n");
printf("4. 删除指定值的节点\n");
printf("请输入你的删除操作选择: \n");
scanf("%d", &delchoice);
return delchoice;
}
test.c文件
#pragma warning(disable:4996)
#include"List.h"
int main()
{
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)
{
case 1:
{
int delchoice = delmenu();
switch (delchoice)
{
case 1:
if (!LTEmpty(plist))
{
LTPopFront(plist);
}
break;
case 2:
if (!LTEmpty(plist))
{
LTPopBack(plist);
}
break;
case 3: {
printf("请输入要删除节点的位置：");
int pos;
scanf("%d", &pos);
LTNode* pcur = plist->next;
for (int i = 0; i < pos; i++)
{
pcur = pcur->next;
}
LTErase(pcur);
break;
}
case 4:
{
printf("请输入要删除的值：");
scanf("%d", &value);
find = LTFind(plist, value);
if (find != NULL)
{
LTErase(find);
}
break;
}
default:
printf("无效的删除操作选择\n");
break;
}
break;
}
case 2:
{
int inschoice = insmenu();
switch (inschoice)
{
case 1:
printf("请输入要插入的值：");
scanf("%d", &value);
LTPushFront(plist, value);
break;
case 2:
printf("请输入要插入的值：");
scanf("%d", &value);
LTPushBack(plist, value);
break;
case 3:
{
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;
}
case 3:
LTDesTroy(plist);
plist = NULL;
break;
case 4:
printf("请输入要查找的值：");
scanf("%d", &value);
find = LTFind(plist, value);
if (find != NULL) {
printf("找到了，该值所在节点的下一个节点数据为：%d\n", find->next->data);
}
else
{
printf("未找到指定的值\n");
}
break;
case 5:
ListRemoveDuplicates(plist);
break;
default:
printf("无效的操作选择\n");
break;
}
if (plist != NULL)
{
LTPrint(plist);
}
} while (input != 3);
return 0;
}
| 非常感谢您的阅读，喜欢的话记得三连哦 |
