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

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