数据结构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;
}
