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

数据结构MOOC
PTA习题
这道题也是相当费事，不外比上一个题好一些，这里我使用了C++的STL库，使得代码量大幅淘汰。

题干机翻：

1、条件准备

这里我准备接纳map来存地点和值，由于map的查找服从也是不错的

数组arr是存链表的地点，而且依次相连的。

大概这里没有看懂，等背面看map的实现时应该就明确了。

主函数使cin、cout更快

1. #include <iostream>
2. #include <string>
3. #include <map>
4. using namespace std;
6. const int M = 100005;
7. string arr[M];  //存链表起始地址
9. int main()
10. {
11.     std::ios::sync_with_stdio(false);
12.     cin.tie(0);
13.     cout.tie(0);   //加速

复制代码

2、map界说，存储输入数据

这里重要分析一下map：

map<string,pair<int,string>> 可以让我们后续通过输入一个地点就能获取该结点的全部信息。

输入数据每一举动： address  data   next，

address用string这个键来存，data用pair里的int存，next用pair里的string存

1. map<string, pair<int, string>> m;
2.     string qi;//起始地址
3.     int n;    //总共数据个数
4.     int k;    //反转数
5.     cin >> qi >> n >> k;
6.     for (int i = 1; i <= n; i++)
7.     {
8.         string a;
9.         cin >> a;
10.         cin >> m[a].first >> m[a].second;
11.      //Address Data Next为输入格式，Address与Next存为string类型，data用int来存
12.     }

复制代码

3、初始化arr数组

这里我们arr数组存的是每一行输入数据的address，循环遍历用过查找本数据的next来使数据毗连起来，如许arr数组存的就是首尾相连的数据的address。

1. string t = qi;  
2.     int len = 0;   //记录arr数组长度
3.     while (m.find(t) != m.end())  //直到next为-1停下
4.     {
5.         arr[len++] = t;     
6.         t = m[t].second;   //更新t
7.     }
8.    

复制代码

4、反转（重点）

此处反转我们思量恰好能全反转和留有几个小数据不反转的情况。
但无论怎样都要先辈行反转判断。

1. int flag = 0;  //标记，规范输出方式
2.     for (int i = 1; i * k <= len; i++)
3.     {
4. //i代表当前进行第几轮反转，i*k比arr中链表长度短都可以进行
5.         for (int j = i * k - 1; j >= (i - 1) * k; j--)
6.         {
7.        //j表示当前该输出的位置
8.             if (flag)
9.                 cout << ' ' << arr[j] << endl;    //因为输出的是下一行的地址所以，第一行输出不进行
10.             cout << arr[j] << ' ' << m[arr[j]].first;  //输出地址和数据
11.             flag = 1;   //除第一行后面都多输出一个并换行
12.         }
13.     }

复制代码

这里用两重循环，第一重是当进步行第几轮反转，假如轮数与每轮反转数相乘小于arr数组长度即可进入循环体。

第二重是循环该轮反转的位置，从该轮的末了一处倒着遍历，就是i*k-1，直到反转k个竣事。

内里flag是不让第一行输出举行的，每一行输出末了与下一行开头相连，以是j又移动一次才输出该行next。

但是这里有一个标题，假如len==k时恰好输出完，但末了一行next没输出，我们一会再处理处罚这个标题。

下面思量剩几个数据不敷k时不反转输出。

2.     if (len % k)
3.     {//取模不为0则证明有数据不反转直接输出
4.         for (int i = len - len % k; i < len; i++)
5.         {
6.          //找到起始位置，一个一个输出
7.             cout << ' ' << arr[i] << endl;
8.             cout << arr[i] << ' ' << m[arr[i]].first;
9.        }
10.     }

复制代码

我们通过取模就能判断剩没剩下，用len-len%k找到不反转的起始位置，今后不停输出到末了。

留意这里循环体内先输出了next和换行，由于刚才说了反转竣事后末了一行没输出完，而恰好这组数据有有不反转的，那这里可以处理处罚。

背面输出意思跟前面雷同。就是在末了的时间单独处理处罚一下。

末了再把末了一行输出完，是-1直接输出就行

1.         cout << ' ' << "-1" << endl;

复制代码

5、总结

这里使用了stl库里map的一些用法，假如不太熟的话可以先去学一下stl
完备代码如下：

1. #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;}

复制代码