浙大数据结构:02-线性结构3 Reversing Linked List

news/2024/9/17 8:24:20/ 标签: 数据结构

数据结构MOOC

PTA习题

这道题也是相当费事,不过比上一个题好一些,这里我使用了C++的STL库,使得代码量大幅减少。

1、条件准备

这里我准备采用map来存地址和值,因为map的查找效率也是不错的
数组arr是存链表的地址,并且依次相连的。
可能这里没有看懂,等后面看map的实现时应该就明白了。
主函数使cin、cout更快
#include <iostream>
#include <string>
#include <map>
using namespace std;const int M = 100005;
string arr[M];  //存链表起始地址int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);   //加速

2、map定义,存储输入数据

这里主要说明一下map:
map<string,pair<int,string>> 可以让我们后续通过输入一个地址就能获取该结点的所有信息。
输入数据每一行为: address  data   next,
address用string这个键来存,data用pair里的int存,next用pair里的string存
 map<string, pair<int, string>> m;string qi;//起始地址int n;    //总共数据个数int k;    //反转数cin >> qi >> n >> k;for (int i = 1; i <= n; i++){string a;cin >> a;cin >> m[a].first >> m[a].second;//Address Data Next为输入格式,Address与Next存为string类型,data用int来存}

3、初始化arr数组

这里我们arr数组存的是每一行输入数据的address,循环遍历用过查找本数据的next来使数据连接起来,这样arr数组存的就是首尾相连的数据的address。
string t = qi;  int len = 0;   //记录arr数组长度while (m.find(t) != m.end())  //直到next为-1停下{arr[len++] = t;     t = m[t].second;   //更新t} 

4、反转(重点)

此处反转我们考虑恰好能全反转和留有几个小数据不反转的情况。

但无论如何都要先进行反转判断。

 int flag = 0;  //标记,规范输出方式for (int i = 1; i * k <= len; i++){
//i代表当前进行第几轮反转,i*k比arr中链表长度短都可以进行for (int j = i * k - 1; j >= (i - 1) * k; j--){//j表示当前该输出的位置if (flag)cout << ' ' << arr[j] << endl;    //因为输出的是下一行的地址所以,第一行输出不进行cout << arr[j] << ' ' << m[arr[j]].first;  //输出地址和数据flag = 1;   //除第一行后面都多输出一个并换行}}
这里用两重循环,第一重是当前进行第几轮反转,如果轮数与每轮反转数相乘小于arr数组长度即可进入循环体。
第二重是循环该轮反转的位置,从该轮的最后一处倒着遍历,就是i*k-1,直到反转k个结束。
里面flag是不让第一行输出进行的,每一行输出结尾与下一行开头相连,所以j又移动一次才输出该行next。
但是这里有一个问题,如果len==k时恰好输出完,但最后一行next没输出,我们一会再处理这个问题。
下面考虑剩几个数据不够k时不反转输出。
if (len % k){//取模不为0则证明有数据不反转直接输出for (int i = len - len % k; i < len; i++){//找到起始位置,一个一个输出cout << ' ' << arr[i] << endl;cout << arr[i] << ' ' << m[arr[i]].first;}}
我们通过取模就能判断剩没剩下,用len-len%k找到不反转的起始位置,往后一直输出到结尾。
注意这里循环体内先输出了next和换行,因为刚才说了反转结束后最后一行没输出完,而恰好这组数据有有不反转的,那这里可以处理。
后面输出意思跟前面类似。就是在最后的时候单独处理一下。
最后再把最后一行输出完,是-1直接输出就行
        cout << ' ' << "-1" << endl;

5、总结

这里使用了stl库里map的一些用法,如果不太熟的话可以先去学一下stl

完整代码如下:

#include <iostream>
#include <string>
#include <map>
using namespace std;const int M = 100005;
string arr[M];int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);map<string, pair<int, string>> m;string qi;int n;int k;cin >> qi >> n >> k;for (int i = 1; i <= n; i++){string a;cin >> a;cin >> m[a].first >> m[a].second;}string t = qi;int len = 0;while (m.find(t) != m.end()){arr[len++] = t;t = m[t].second;}int flag = 0;for (int i = 1; i * k <= len; i++){for (int j = i * k - 1; j >= (i - 1) * k; j--){if (flag)cout << ' ' << arr[j] << endl;cout << arr[j] << ' ' << m[arr[j]].first;flag = 1;}}if (len % k){for (int i = len - len % k; i < len; i++){cout << ' ' << arr[i] << endl;cout << arr[i] << ' ' << m[arr[i]].first;}}cout << ' ' << "-1" << endl;return 0;
}


http://www.ppmy.cn/news/1521711.html

相关文章

随笔1:数学建模与数值计算

目录 1.1 矩阵运算 1.2 基本数学函数 1.3 数值求解 数学建模与数值计算 是将实际问题通过数学公式和模型进行描述&#xff0c;并通过计算获得模型解的过程。这是数学建模中最基本也是最重要的环节之一。下面是详细的知识点讲解及相应的MATLAB代码示例。 1.1 矩阵运算 知识点…

2024高教社杯全国大学生数学建模竞赛(A题)深度剖析 _ 建模完整过程+详细思路+代码全解析

问题1解答过程 1.1 螺线运动的基本几何模型 板凳龙的舞动路径为等距螺线。螺线是极坐标中一类常见曲线&#xff0c;其特点是半径随角度线性增加。我们可以用以下极坐标方程描述这条螺线&#xff1a; r ( θ ) p 2 π θ r(\theta) \frac{p}{2\pi} \theta r(θ)2πp​θ 其…

计算机毕业设计选题推荐-客栈管理系统-酒店预订-民宿管理系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

地平线SuperDrive首秀:千人研发投入,出场即「比肩第一梯队」

作者 |德新 编辑 |王博 8月底&#xff0c;地平线在北京开放了第一批面向媒体的高阶智驾方案SuperDrive体验。 预计到明年第三季度&#xff0c;SuperDrive将伴随主机厂客户的第一款量产车交付。 目前在国内&#xff0c;仅有英伟达和华为两家的平台基础上&#xff0c;有车企向…

网络安全售前入门09安全服务——安全加固服务

目录 1.服务概述 2.流程及工具 2.1服务流程 2.2服务工具 3.服务内容 ​​​​​​​4.服务方式 ​​​​​​​5.风险规避措施 ​​​​​​​6.服务输出 1.服务概述 安全加固服务是参照风险评估、等保测评、安全检查等工作的结果,基于科学的安全思维方式、长期的安全…

红队攻防 | 利用GitLab nday实现帐户接管

在一次红队任务中&#xff0c;目标是一家提供VoIP服务的公司。该目标拥有一些重要的客户&#xff0c;如政府组织&#xff0c;银行和电信提供商。该公司要求外部参与&#xff0c;资产测试范围几乎是公司拥有的每一项互联网资产。 第一天是对目标进行信息收集。这一次&#xff0…

Python编码系列—Python项目架构的艺术:最佳实践与实战应用

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

高级java每日一道面试题-2024年8月30日-基础篇-你对泛型了解多少?

如果有遗漏,评论区告诉我进行补充 面试官: 你对泛型了解多少? 我回答: 泛型的基本概念 泛型是一种编程语言特性&#xff0c;它允许在类、接口或方法定义时使用类型参数&#xff08;Type Parameters&#xff09;。类型参数允许在编译时指定具体的类型&#xff0c;从而避免了…

Ceph集群维护相关操作

1、通过套接字进行单机管理 node节点&#xff1a; [rootceph-node1 ~]# ll /var/run/ceph/ total 0 drwxrwx--- 2 ceph ceph 140 Aug 19 08:46 ./ drwxr-xr-x 25 root root 840 Aug 19 11:26 ../ srwxr-xr-x 1 ceph ceph 0 Aug 19 08:46 ceph-osd.0.asok srwxr-xr-x 1 ceph c…

计算机毕业设计推荐-基于Java的乡村农家乐管理系统

&#x1f496;&#x1f525;作者主页&#xff1a;毕设木哥 精彩专栏推荐订阅&#xff1a;在 下方专栏&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; 实战项目 文章目录 实战项目 一、基于Java的乡村农家乐管理系…

NGINX 中配置负载均衡器

Nginx 提供了多种负载均衡策略&#xff0c;如轮询&#xff08;Round Robin&#xff09;、最少连接数&#xff08;Least Connections&#xff09;、IP 哈希&#xff08;IP Hash&#xff09;等。这里以轮询策略为例进行配置。 1. 准备工作 假设你有以下几台 PHP 服务器&#xf…

Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解

A. Dora’s Set Problem Statement Dora has a set s s s containing integers. In the beginning, she will put all integers in [ l , r ] [l, r] [l,r] into the set s s s. That is, an integer x x x is initially contained in the set if and only if l ≤ x ≤…

electron-vite打包出错

问题&#xff1a;1 electron-vite 安装&#xff0c; 打包下载资源失败&#xff0c;设置国内镜像 由于electron默认打包会从github上下载相关二进制包&#xff0c;众所周知&#xff0c;国内GitHub访问是相当慢的&#xff0c;所以经常会出现下载失败导致打包不成功&#xff0c;…

生信圆桌x生信宝库:生物信息学资源与工具的终极指南

介绍 生物信息学作为现代生物科学的重要分支&#xff0c;涉及到大量的数据处理、分析和存储工作。随着领域的不断发展&#xff0c;各类生物信息学资源与工具也如雨后春笋般涌现。这些资源涵盖了从基因组数据、蛋白质结构到代谢路径的方方面面&#xff0c;极大地丰富了科研人员的…

ElementUI 动态表格高度,使页面一屏显示

一、效果 二、代码 <script> export default {data () {return {maxHeight: 500}},methods: {handlePageReSize () {let card document.querySelector(.el-card);this.maxHeight card.clientHeight - 108;}},mounted () {let _this this;window.onresize () > {re…

pytorch view 函数介绍

view 是 PyTorch 中用于改变张量形状(tensor shape)的函数。与其他形状转换操作不同的是,view 并不改变张量的数据,而是返回一个新的张量,该张量与原始数据共享内存。 1. 基本用法 view 的作用是将一个张量重新排列成新的形状。它的基本语法是: tensor.view(shape)sha…

ES之三:springboot集成ES

一.选择版本很重要&#xff0c;不然会找不到好多方法 明明有Timeout方法&#xff0c;不报红&#xff0c;运行时&#xff0c;报错&#xff0c;找不到该类 ClassNotFoundException 为了避免使用的Elasticsearch版本和SpringBoot采用的版本不一致导致的问题&#xff0c;尽量使用…

高级算法设计与分析 学习笔记3 哈希表

首先我们要讨论一个把n个数据放到列表S里面的问题&#xff1a; 但很显然&#xff0c;这些数据的范围有多大这个T就得有多大&#xff0c;而实际上要放的数字可能就几个&#xff08;比如就放一个1和一个10000000&#xff0c;那我还是要准备一个巨大的T&#xff09;&#xff0c;不…

华为达芬奇人像引擎2.0,人像体验有哪些升级

对于年轻人而言&#xff0c;拍照已成为生活中不可或缺的一部分&#xff0c;不仅是为了记录世界、更重要的是成为生活的主角&#xff0c;大胆表达自己。然而很多喜欢使用手机记录生活的人&#xff0c;既希望能够实现媲美单反的影像实力&#xff0c;同时还想呈现出真实、更具自然…

利用机器人自动回复软件,显著提升客户体验

随着科技的飞速发展及互联网普及&#xff0c;机器人自动回复软件成为了现代企业的重要工具。无论是在客户服务领域&#xff0c;还是在营销、销售等方面&#xff0c;自动回复机器人都表现出了强大的功能和显著的效果。究竟什么是机器人自动回复技术?它是如何运行的?本文将为您…