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

admin管理员组
文章数量:1794759

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

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

解题思路:

代码语言：javascript代码运行次数：0运行复制

>利用递归，不断将节点的下个节点传入函数

>每个函数执行对应删除操作

实现代码:

代码语言：javascript代码运行次数：0运行复制

#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);       // 打印链表
}

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

解题思路:

代码语言：javascript代码运行次数：0运行复制

>定义工作指针p、前驱指针pre

>遍历链表，删除元素

实现代码:

代码语言：javascript代码运行次数：0运行复制

#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);       // 打印链表
}

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

解题思路:

代码语言：javascript代码运行次数：0运行复制

>利用递归栈进行实现

>栈的特性是后进先出

>所以可以采用递归实现

实现代码:

代码语言：javascript代码运行次数：0运行复制

#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); 
}

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

解题思路:

代码语言：javascript代码运行次数：0运行复制

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

实现代码:

代码语言：javascript代码运行次数：0运行复制

#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);               // 打印修改后的链表
}

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

解题思路:

代码语言：javascript代码运行次数：0运行复制

>头插法

实现代码:

代码语言：javascript代码运行次数：0运行复制

#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); // 打印反转后的链表
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent 删除数据数据结构与算法指针遍历链表

本文标签： 2024重生之回溯数据结构与算法系列学习（9）无论是王道考研人还是IKUN都能包会的不然别给我家鸽鸽丢脸好嘛

版权声明：本文标题：2024重生之回溯数据结构与算法系列学习（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】内容由林淑君副主任自发贡献，该文观点仅代表作者本人，转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754674518a1705051.html，本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。

写会百科网

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

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

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

实现代码:

更多相关文章

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

发表评论

推荐文章

【C++】入门篇一

【Java】IO 操作详解

OpenHarmony 5.0.0 Release发布

类型推导的一二件事

Linux：进程地址空间

热门文章

SQL日期函数

树的4种遍历

手把手教会你安装Linux系统

鸿蒙（HarmonyOS）应用开发之性能优化实战

初识C++ · string的使用(1)

【C语言】数据在内存中的存储(万字解析)

Android 组件化利器：WMRouter 与 DRouter 的选择与实践

【C++篇】C++类与对象深度解析（六）：全面剖析拷贝省略、RVO、NRVO优化策略

【C语言篇】自定义类型：联合体和枚举详细介绍

python知识点100篇系列（13）

最新文章

Linux系统之jobs命令的基本使用

手把手教学！简单上手“AI复活”技术

单细胞Seruat和h5ad数据格式互换(R与python)方法学习和整理

JVM专题

学会5个图表，让数据分析简洁高效

写“藤”的作文1200字

有关于进步的作文

幼儿园见习报告

语数英寒假作业上册答案五年级

伊索寓言经典语词句摘抄