map模拟双链表操作:
相关题目推荐
考点:双链表的插入和删除
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
unordered_map<string, string> head, tail;
// 关于head和tail:
// head[a] = b表示a是头结点,且a的下一个结点为b
// tail[b] = a表示b是尾结点,且b的上一个结点为a
// head和tail组合使用实现了双链表的操作
// 由于只需要输出链表的头结点和尾结点,因此我们只需要维护一个长度为2的双链表即可
int q;
cin >> q;
while (q--) {
string a, b;
cin >> a >> b;
if (!tail.count(a)) { // 如果a不是尾结点,则a必然是一个新的链表的头结点
head[a] = b;
tail[b] = a;
}
else { // 如果a是某条链表的尾结点,则模拟双链表的操作,
auto pre = tail[a]; // 取出a结点的上一个结点pre
head[pre] = b; // 让结点pre指向结点b
tail[b] = pre; // 上结点b指向结点pre
tail.erase(a); // 删除结点a与结点pre之间的联系
}
}
cout << head.size() << endl;
for (auto& [k, v] : head) {
cout << k << " " << v << endl;
}
return 0;
}
for (auto& [k, v] : head) 这是什么意思
相当于int x : a;a为一个集合
head是头结点的集合,这句话是取出所有链表的头结点的意思