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

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,图像资源包5000点
视觉智能开放平台,分割抠图1万点
简介: 数据结构王道第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























相关文章
|
3天前
|
弹性计算 双11 开发者
阿里云ECS“99套餐”再升级!双11一站式满足全年算力需求
11月1日,阿里云弹性计算ECS双11活动全面开启,在延续火爆的云服务器“99套餐”外,CPU、GPU及容器等算力产品均迎来了全年最低价。同时,阿里云全新推出简捷版控制台ECS Lite及专属宝塔面板,大幅降低企业和开发者使用ECS云服务器门槛。
|
21天前
|
存储 弹性计算 人工智能
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
阿里云弹性计算产品线、存储产品线产品负责人Alex Chen(陈起鲲)及团队内多位专家,和中国电子技术标准化研究院云计算标准负责人陈行、北京望石智慧科技有限公司首席架构师王晓满两位嘉宾,一同带来了题为《通用计算新品发布与行业实践》的专场Session。本次专场内容包括阿里云弹性计算全新发布的产品家族、阿里云第 9 代 ECS 企业级实例、CIPU 2.0技术解读、E-HPC+超算融合、倚天云原生算力解析等内容,并发布了国内首个云超算国家标准。
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
|
3天前
|
人工智能 弹性计算 文字识别
基于阿里云文档智能和RAG快速构建企业"第二大脑"
在数字化转型的背景下,企业面临海量文档管理的挑战。传统的文档管理方式效率低下,难以满足业务需求。阿里云推出的文档智能(Document Mind)与检索增强生成(RAG)技术,通过自动化解析和智能检索,极大地提升了文档管理的效率和信息利用的价值。本文介绍了如何利用阿里云的解决方案,快速构建企业专属的“第二大脑”,助力企业在竞争中占据优势。
|
1天前
|
人工智能 自然语言处理 安全
创新不设限,灵码赋新能:通义灵码新功能深度评测
自从2023年通义灵码发布以来,这款基于阿里云通义大模型的AI编码助手迅速成为开发者心中的“明星产品”。它不仅为个人开发者提供强大支持,还帮助企业团队提升研发效率,推动软件开发行业的创新发展。本文将深入探讨通义灵码最新版本的三大新功能:@workspace、@terminal 和 #team docs,分享这些功能如何在实际工作中提高效率的具体案例。
|
7天前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品,用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书,快捷部署到阿里云产品中。
1850 6
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
|
10天前
|
Web App开发 算法 安全
什么是阿里云WoSign SSL证书?_沃通SSL技术文档
WoSign品牌SSL证书由阿里云平台SSL证书合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品。
1789 2
|
19天前
|
编解码 Java 程序员
写代码还有专业的编程显示器?
写代码已经十个年头了, 一直都是习惯直接用一台Mac电脑写代码 偶尔接一个显示器, 但是可能因为公司配的显示器不怎么样, 还要接转接头 搞得桌面杂乱无章,分辨率也低,感觉屏幕还是Mac自带的看着舒服
|
26天前
|
存储 人工智能 缓存
AI助理直击要害,从繁复中提炼精华——使用CDN加速访问OSS存储的图片
本案例介绍如何利用AI助理快速实现OSS存储的图片接入CDN,以加速图片访问。通过AI助理提炼关键操作步骤,避免在复杂文档中寻找解决方案。主要步骤包括开通CDN、添加加速域名、配置CNAME等。实测显示,接入CDN后图片加载时间显著缩短,验证了加速效果。此方法大幅提高了操作效率,降低了学习成本。
5386 15
|
13天前
|
人工智能 关系型数据库 Serverless
1024,致开发者们——希望和你一起用技术人独有的方式,庆祝你的主场
阿里云开发者社区推出“1024·云上见”程序员节专题活动,包括云上实操、开发者测评和征文三个分会场,提供14个实操活动、3个解决方案、3 个产品方案的测评及征文比赛,旨在帮助开发者提升技能、分享经验,共筑技术梦想。
1139 152
|
21天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1585 14

热门文章

最新文章

  • 1
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    12
  • 2
    2024重生之回溯数据结构与算法系列学习(11)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    6
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    9
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    10
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    10
  • 6
    2024重生之回溯数据结构与算法系列学习(7)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    7
  • 7
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    7
  • 8
    23
    6
  • 9
    2024重生之回溯数据结构与算法系列学习之单双链表精题(4)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    9
  • 10
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    6