AI 助理
备案控制台
开发者社区 视觉智能 文章 正文

2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

2024-11-04 26
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
视觉智能开放平台，分割抠图1万点
视觉智能开放平台，图像资源包5000点
视觉智能开放平台，视频资源包5000点
简介： 数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

image.gif

专栏跑道二

➡️ 24 Network Security -LJS

image.gif

image.gif

image.gif

专栏跑道三


➡️ MYSQL REDIS Advance operation

image.gif

专栏跑道四

➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

image.gif

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

image.png

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

image.gif

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

image.gif

image.gif

上节回顾






(1)题目：设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。

解题思路:

>利用递归，不断将节点的下个节点传入函数
>每个函数执行对应删除操作
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
    int data;           // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是 LNode 指针类型的别名
// 头插法构建链表
void HeadInsert(LinkList &L)
{
    int val = 0;
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点的next指向当前头节点的下一个节点
        L->next = s;         // 头指针的next指向新节点
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0;
    LNode *r = L; // r为指向链表最后一个节点的指针
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 尾节点的next指向新节点
        r = s;               // r更新为新节点
        r->next = NULL;      // 新节点的next设为nullptr
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从头节点的下一个节点开始遍历
    while (p) // 当p不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 删除链表中所有值为x的节点
void DelValue(LinkList &L, int x)
{
    if (L == NULL) // 如果链表为空，直接返回
    {
        return;
    }
    LNode *p;
    // 如果当前节点的值等于x
    if (L->data == x)
    {
        p = L;            // 将当前节点赋值给p
        L = L->next;     // 将链表的头指针指向下一个节点
        delete p;        // 删除当前节点
        DelValue(L, x);  // 递归调用，继续删除后面的节点
    }
    else
    {
        DelValue(L->next, x); // 否则，递归到下一个节点
    }
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    L->next = NULL; // 初始化头节点的next指针为NULL
    TailInsert(L); // 调用尾插法插入数据
    DelValue(L, 2); // 删除值为2的节点
    Print(L);       // 打印链表
}
image.gif

image.gif 编辑

(2)题目：在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一，试编写算法以实现上述操作。

解题思路:

>定义工作指针p、前驱指针pre
>遍历链表，删除元素
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
    int data;           // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是 LNode 指针类型的别名
// 头插法构建链表
void HeadInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点的next指向当前头节点的下一个节点
        L->next = s;         // 头指针的next指向新节点
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    LNode *r = L; // r指向链表的尾节点
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 尾节点的next指向新节点
        r = s;               // r更新为新节点
        r->next = NULL;      // 新节点的next设为NULL
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从头节点的下一个节点开始遍历
    while (p) // 当p不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 删除链表中所有值为x的节点
void DelValue(LinkList &L, int x)
{
    LNode *p, *pre; // p指向当前节点，pre指向前一个节点
    p = L->next; // 从头节点的下一个节点开始
    pre = L;     // pre初始化为头节点
    while (p) // 当p不为空时
    {
        if (p->data == x) // 如果当前节点的值等于x
        {
            LNode *q = p; // 将当前节点赋值给q
            pre->next = p->next; // 前一个节点的next指向当前节点的下一个节点
            p = p->next; // p移动到下一个节点
            delete q;    // 删除当前节点
        }
        else // 当前节点的值不等于x
        {
            pre = p;     // 更新前一个节点为当前节点
            p = p->next; // p移动到下一个节点
        }
    }
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    L->next = NULL; // 初始化头节点的next指针为NULL
    TailInsert(L);  // 调用尾插法插入数据
    DelValue(L, 2); // 删除值为2的节点
    Print(L);       // 打印链表
}
image.gif

(3)题目：设L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

解题思路:

>利用递归栈进行实现
>栈的特性是后进先出
>所以可以采用递归实现
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
    int data;           // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是 LNode 指针类型的别名
// 头插法构建链表
void HeadInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点的next指向当前头节点的下一个节点
        L->next = s;         // 头指针的next指向新节点
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    LNode *r = L; // r指向链表的尾节点
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 尾节点的next指向新节点
        r = s;               // r更新为新节点
        r->next = NULL;      // 新节点的next设为NULL
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从头节点的下一个节点开始遍历
    while (p) // 当p不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 递归逆序打印链表
void ReversePrint(LinkList &L)
{
    if (L == NULL) // 如果链表为空，直接返回
    {
        return;
    }
    ReversePrint(L->next); // 递归调用，先打印后面的节点
    cout << L->data << '\t'; // 打印当前节点的数据
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    L->next = NULL;         // 初始化头节点的next指针为NULL
    TailInsert(L);          // 调用尾插法插入数据
    // 逆序打印链表的元素
    ReversePrint(L->next); 
}
image.gif

(4)题目：试编写在带头结点的单链表L 中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。

解题思路:

>定义工作指针p、pre
>定义用于保存最小值的指针minP、minPre
>遍历链表找到最小值，用指针标记
>最后修改指针将其删除释放空间
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
    int data;           // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是 LNode 指针类型的别名
// 头插法构建链表
void HeadInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点的next指向当前头节点的下一个节点
        L->next = s;         // 头指针的next指向新节点
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    LNode *r = L; // r指向链表的尾节点
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 尾节点的next指向新节点
        r = s;               // r更新为新节点
        r->next = NULL;      // 新节点的next设为NULL
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从头节点的下一个节点开始遍历
    while (p) // 当p不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 删除链表中的最小值节点
void DelMinValue(LinkList &L)
{
    // 工作节点
    LNode *p, *pre; // p是当前节点，pre是前驱节点
    p = L->next;     // 从链表的第一个节点开始
    pre = L;        // 前驱节点初始化为头节点
    // 用于保存最值的节点
    LNode *minP, *minPre; // minP是当前最小值节点，minPre是其前驱节点
    minP = p; // 初始化为第一个节点
    minPre = pre; // 初始化为头节点
    // 遍历链表查找最小值节点
    while (p)
    {
        if (p->data < minP->data) // 找到更小的值
        {
            minPre = pre; // 更新前驱节点
            minP = p;     // 更新最小值节点
        }
        pre = p; // 前驱节点向后移动
        p = p->next; // 当前节点向后移动
    }
    // 删除最小值节点
    minPre->next = minP->next; // 将前驱节点的next指向最小值节点的下一个节点
    delete minP; // 释放内存
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    L->next = NULL;         // 初始化头节点的next指针为NULL
    TailInsert(L);          // 调用尾插法插入数据
    DelMinValue(L);         // 删除链表中的最小值节点
    Print(L);               // 打印修改后的链表
}
image.gif

(5)题目：试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为 O(1)。

解题思路:

>头插法
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
    int data;           // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是 LNode 指针类型的别名
// 头插法构建链表
void HeadInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点的next指向当前头节点的下一个节点
        L->next = s;         // 头指针的next指向新节点
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0; // 用于存储输入值
    LNode *r = L; // r指向链表的尾节点
    while (cin >> val) // 从标准输入读取数据
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 尾节点的next指向新节点
        r = s;               // r更新为新节点
        r->next = NULL;      // 新节点的next设为NULL
        // 如果读取到换行符，结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从头节点的下一个节点开始遍历
    while (p) // 当p不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 反转链表
void fn(LinkList &L)
{
    LNode *p, *r; // p用于遍历链表，r用于保存当前节点的下一个节点
    p = L->next;  // 从头节点的下一个节点开始
    L->next = NULL; // 初始化头节点的next为NULL，准备反转
    // 反转链表
    while (p)
    {
        r = p->next; // 保存当前节点的下一个节点
        p->next = L->next; // 将当前节点的next指向当前头节点的next
        L->next = p; // 更新头节点的next为当前节点
        p = r; // 移动到下一个节点
    }
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    TailInsert(L);          // 调用尾插法插入数据
    fn(L); // 反转链表
    Print(L); // 打印反转后的链表
}
image.gif























文章标签：
算法
Linux
安全
搜索推荐
NoSQL
关键词：
数据结构链表
算法链表
回溯数据结构
回溯数据结构学习王道包
算法包
肾透侧视攻城狮
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
53 4
龙大吉
|
22天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
43 5
肾透侧视攻城狮
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串（12）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丟脸好嘛？】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明；【含常见的报错问题及其对应的解决方法】你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
28 2
2024重生之回溯数据结构与算法系列学习之串（12）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丟脸好嘛？】
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
83 4
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
25 1
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
47 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
56 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
175 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
32 1
德国都芳最好
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
83 21

视觉智能

热门文章

最新文章

  • 1
    OpenCV+深度学习预训练模型，简单搞定图像识别 | 教程
  • 2
    【OpenCV学习笔记 023】两种图像分割方法比较
  • 3
    [AR]ImageTarget(图像识别)
  • 4
    Python黑科技：50行代码运用Python＋OpenCV实现人脸追踪+详细教程+快速入门+图像识别+人脸识别+大神讲解
  • 5
    图像识别试验 - 字符验证码、车牌号、身份证号
  • 6
    详解阿里99大促活动页内容识别技术实现
  • 7
    阿里云图像识别Java调用示例参考
  • 8
    图像识别试验 - 字符验证码、车牌号、身份证号
  • 9
    【图像算法】彩色图像分割专题七：基于分水岭的彩色分割
  • 10
    图像识别落地B端应用，商业化的“绣球”先抛给了哪些行业？
  • 1
    【一步步开发AI运动小程序】十七、如何识别用户上传视频中的人体、运动、动作、姿态？
    37
  • 2
    uni-app开发AI康复锻炼小程序，帮助肢体受伤患者康复！
    29
  • 3
    【一步步开发AI运动小程序】十六、AI运动识别中，如何判断人体站位？
    56
  • 4
    【一步步开发AI运动小程序】十五、AI运动识别中，如何判断人体站位的远近？
    123
  • 5
    【一步步开发AI运动小程序】十四、主包超出2M大小限制，如何将插件分包发布？
    25
  • 6
    【一步步开发AI运动小程序】十三、自定义一个运动分析器，实现计时计数02
    41
  • 7
    【一步步开发AI运动小程序】十二、自定义一个运动分析器，实现计时计数01
    39
  • 8
    【一步步开发AI运动小程序】十一、人体关键点跳跃追踪
    27
  • 9
    【一步步开发AI运动小程序】十、姿态动作相似度比较
    38
  • 10
    用PDF转换图片的方式弥补通义千问在扫描版PDF支持方面的缺失
    38

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 超全算法笔试-模拟题精解合集

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 代码质量提升小妙招
  • RSA密码算法设计与实现
  • 重温童年的“五子棋”，赢取专属阿里云Serverless证书
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks