当前位置： 首页 > news >正文

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

news 来源：原创 2024/9/30 1:35:40

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

你的三连是我最大的动力

以下图片仅代表专栏特色 

专栏跑道一
 ➡️ MYSQL REDIS Advance operation


专栏跑道二
➡️ 24 Network Security -LJS 

​

​ 

​

专栏跑道三

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

​

专栏跑道四
➡️RHCE-LJS[Linux高端骚骚操作实战篇]​

专栏跑道五

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

​

上节回顾icon-default.png?t=O83Ahttps://netsecur-cloud-ljs.blog.csdn.net/article/details/142605044

目录

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

你的三连是我最大的动力

专栏跑道一 ➡️ MYSQL REDIS Advance operation

专栏跑道二➡️ 24 Network Security -LJS 

专栏跑道三

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

专栏跑道四➡️RHCE-LJS[Linux高端骚骚操作实战篇]​编辑​

专栏跑道五

上节回顾https://netsecur-cloud-ljs.blog.csdn.net/article/details/142605044

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

实现代码:

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

解题思路:

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

实现代码:

#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;// 如果当前节点的值等于xif (L->data == x){p = L;            // 将当前节点赋值给pL = L->next;     // 将链表的头指针指向下一个节点delete p;        // 删除当前节点DelValue(L, x);  // 递归调用，继续删除后面的节点}else{DelValue(L->next, x); // 否则，递归到下一个节点}
}int main()
{LinkList L = new LNode; // 创建链表头节点L->next = NULL; // 初始化头节点的next指针为NULLTailInsert(L); // 调用尾插法插入数据DelValue(L, 2); // 删除值为2的节点Print(L);       // 打印链表
}

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

解题思路:

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

实现代码:

#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; // 将当前节点赋值给qpre->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指针为NULLTailInsert(L);  // 调用尾插法插入数据DelValue(L, 2); // 删除值为2的节点Print(L);       // 打印链表
}

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

解题思路:

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

实现代码:

#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指针为NULLTailInsert(L);          // 调用尾插法插入数据// 逆序打印链表的元素ReversePrint(L->next); 
}

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

解题思路:

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

实现代码:

#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指针为NULLTailInsert(L);          // 调用尾插法插入数据DelMinValue(L);         // 删除链表中的最小值节点Print(L);               // 打印修改后的链表
}

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

解题思路:

>头插法

实现代码:

#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指向当前头节点的nextL->next = p; // 更新头节点的next为当前节点p = r; // 移动到下一个节点}
}int main()
{LinkList L = new LNode; // 创建链表头节点TailInsert(L);          // 调用尾插法插入数据fn(L); // 反转链表Print(L); // 打印反转后的链表
}

相关文章：

  • Android常用C++特性之std::unique_lock
  • 【Android】BottomSheet基本用法总结（BottomSheetDialog,BottomSheetDialogFragment）
  • TRIZ理论在机器人性能优化中的应用
  • 曲线图异常波形检测系统源码分享
  • Linux基础（三）：安装CentOS7（系统安装+桥接联网+换源）
  • linux服务器安装原生的php环境
  • 文心一言 VS 讯飞星火 VS chatgpt （357）-- 算法导论24.2 3题
  • 「Python入门」vscode的安装和python插件下载
  • 【车联网安全】车端网络攻击及检测的框架/模型
  • netty之Future和Promise
  • 【STM32开发环境搭建】-3-STM32CubeMX Project Manager配置-自动生成一个Keil(MDK-ARM) 5的工程
  • docker - 镜像操作（拉取、查看、删除）
  • 报错Invalid HADOOP_HDFS_HOME
  • [深度学习]卷积神经网络CNN
  • 二分查找详解（Java版）
  • 【从零开始安装kubernetes-1.7.3】2.flannel、docker以及Harbor的配置以及作用
  • Docker容器管理
  • ES6简单总结（搭配简单的讲解和小案例）
  • JAVA_NIO系列——Channel和Buffer详解
  • Java多线程（4）：使用线程池执行定时任务
  • java中具有继承关系的类及其对象初始化顺序
  • Linux中的硬链接与软链接
  • nginx 负载服务器优化
  • Python代码面试必读 - Data Structures and Algorithms in Python
  • spring学习第二天
  • vagrant 添加本地 box 安装 laravel homestead
  • Vultr 教程目录
  • 从零搭建Koa2 Server
  • 分享自己折腾多时的一套 vue 组件 --we-vue
  • 如何在 Tornado 中实现 Middleware
  • 使用 5W1H 写出高可读的 Git Commit Message
  • 网页视频流m3u8/ts视频下载
  • 问题之ssh中Host key verification failed的解决
  • 优化 Vue 项目编译文件大小
  • 由插件封装引出的一丢丢思考
  • 智能网联汽车信息安全
  • ​ 轻量应用服务器：亚马逊云科技打造全球领先的云计算解决方案
  • ​LeetCode解法汇总2583. 二叉树中的第 K 大层和
  • # Swust 12th acm 邀请赛# [ K ] 三角形判定 [题解]
  • # 职场生活之道：善于团结
  • #快捷键# 大学四年我常用的软件快捷键大全，教你成为电脑高手！！
  • #我与Java虚拟机的故事#连载04：一本让自己没面子的书
  • (C++17) std算法之执行策略 execution
  • (NO.00004)iOS实现打砖块游戏(十二):伸缩自如,我是如意金箍棒(上)!
  • (翻译)terry crowley： 写给程序员
  • （力扣记录）235. 二叉搜索树的最近公共祖先
  • （六）Hibernate的二级缓存
  • （十七）Flink 容错机制
  • (实战)静默dbca安装创建数据库 --参数说明+举例
  • （一）VirtualBox安装增强功能
  • （原创）boost.property_tree解析xml的帮助类以及中文解析问题的解决
  • ***检测工具之RKHunter AIDE
  • ... fatal error LINK1120：1个无法解析的外部命令 的解决办法
  • .NET CF命令行调试器MDbg入门（二） 设备模拟器
  • .net mvc actionresult 返回字符串_.NET架构师知识普及