这是清华大学邓公的数据结构第三章列表(list)所对应的problem assignment，贴出text：
描述 祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
输入 第一行是一个由大写字母’A’~'Z’组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示整个回放过程共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。
输出 输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
样例 输入
ACCBA 5 1 B 0 A 2 B 4 C 0 A输出
ABCCBA AABCCBA AABBCCBA - A限制 0 ≤ n ≤ 10^4
0 ≤ 初始珠子数量 ≤ 10^4
时间：2 sec
内存：256 MB
这是一道模拟类的算法题，简而言之就是题目给出流程，用代码实现即可。这道题的大体思路不是很难，最主要的消除算法可以采用多指针遍历的思路。但是这题的坑点很多。一是要特判输入为空的情形（没错，就是你玩一局祖玛点了开局，然后发现管道里一个球都没有的情况），其二是祖玛不一定是三消，有可能是四个同色的消除，如果采用的是三指针遍历的话，发现三个指针指向的珠子同色时，一定要考虑最右端或者左端之外的第一个珠子是否还是同色的。
下面贴出本人的代码，但是是有问题的：
#include <cstdio> #define INPUT_SIZE 10086 typedef struct ListNode //链表结点 { char m_data; ListNode* m_predecessor; ListNode* m_successor; ListNode() : m_data('A'), m_predecessor(nullptr), m_successor(nullptr) {} //默认构造方法 ListNode* getSuccessor(void) const { return m_successor; } ListNode* getPredecessor(void) const { return m_predecessor; } }ListNode; class List { private: int m_size; ListNode* m_header; ListNode* m_trailer; public: List() : m_size(0) //默认构造方法 { m_header = new ListNode(); m_trailer = new ListNode(); m_header->m_successor = m_trailer; m_trailer->m_predecessor = m_header; } ~List() //析构 { while(0 < m_size) remove(m_header->getSuccessor()); delete m_header; m_header = nullptr; delete m_trailer; m_header = nullptr; } ListNode* insertAsLast(const char& _data) //插入，用作于初始化扩容 { ListNode* inserted = new ListNode(); //新的插入节点的链接 inserted->m_data = _data; inserted->m_predecessor = last(); inserted->m_successor = m_trailer; m_trailer->m_predecessor->m_successor = inserted; m_trailer->m_predecessor = inserted; m_size++; return inserted; } int size() const { return m_size; } ListNode* first(void) const { return m_header->m_successor; } ListNode* last(void) const { return m_trailer->m_predecessor; } ListNode* header(void) const { return m_header; } ListNode* trailer(void) const { return m_trailer; } ListNode* insertAsBefore(const char& _char_in, int _rank) //寻址前插插入，用于状态转移，复杂度O(n)*O(1) { //循秩到待插入的结点 ListNode* inserted_position = first(); while (_rank-- > 0) { inserted_position = inserted_position->m_successor; } //进行插入 ListNode* inserted = new ListNode; inserted->m_data = _char_in; inserted->m_predecessor = inserted_position->m_predecessor; inserted->m_successor = inserted_position; //待插入结点首尾与链表结点相连 inserted_position->m_predecessor->m_successor = inserted; inserted_position->m_predecessor = inserted; m_size++; return inserted; } char remove(ListNode* _deleted) //删除单节点 { _deleted->m_successor->m_predecessor = _deleted->m_predecessor; _deleted->m_predecessor->m_successor = _deleted->m_successor; char deleted_data = _deleted->m_data; delete _deleted; _deleted = nullptr; m_size--; return deleted_data; } void display(void) //遍历输出链表中保存的所有数据 { ListNode* current = first(); if (current == m_trailer) //当前链表为空 { printf("-"); } while (current != m_trailer) { printf("%c", current->m_data); current = current->getSuccessor(); } printf("\n"); //换行 } }; bool eliminated(ListNode* _p1, ListNode* _p2, ListNode* _p3) //是否可以一键三连消除 { if ((_p1->m_data == _p2->m_data) && (_p2->m_data == _p3->m_data)) { return true; } return false; } void transition(List& zuma) //状态转移（一键消除）处理 { //对链表结点<=3的情况进行特判 if (zuma.size() < 3) zuma.display(); else if (zuma.size() == 3) { ListNode* p1 = zuma.first(), * p2 = p1->getSuccessor(), * p3 = p2->getSuccessor(); if (eliminated(p1, p2, p3)) printf("-"); else zuma.display(); } else { ListNode* p1 = zuma.first(), * p2 = p1->getSuccessor(), * p3 = p2->getSuccessor(); //注意！！！不要被一键三连迷惑，有可能一键四连的！！！ eg：AABBAA 插入：2 B while ((p1 != zuma.header()) && (p3 != zuma.trailer())) //p1，p3没到哨兵的位置 { if (eliminated(p1, p2, p3)) //如果可以一键三连 { ListNode* original_p1 = p1; //p3后移一位，p1、p2前移两位，然后三消 if (p3->getSuccessor()->m_data != p3->m_data) //这是一键三连 { p3 = p3->getSuccessor(); if (p1 == zuma.first()) //特判p1指向链表首结点的情况 { p1 = p1->getPredecessor(); p2 = p1; //p1，p2，p3前者位置不超过后者的位置，应对p2野指针的状况 } else { p1 = p1->getPredecessor()->getPredecessor(); p2 = p1->getSuccessor(); } zuma.remove(original_p1->getSuccessor()->getSuccessor()); zuma.remove(original_p1->getSuccessor()); zuma.remove(original_p1); } else //这是一键四连 { p3 = p3->getSuccessor()->getSuccessor(); //p3往后走两个身位 //p1，p2两个指针处理同一键三连的情况 if (p1 == zuma.first()) //特判p1指向链表首结点的情况 { p1 = p1->getPredecessor(); p2 = p1; //p1，p2，p3前者位置不超过后者的位置，应对p2野指针的状况 } else { p1 = p1->getPredecessor()->getPredecessor(); p2 = p1->getSuccessor(); } zuma.remove(original_p1->getSuccessor()->getSuccessor()->getSuccessor()); zuma.remove(original_p1->getSuccessor()->getSuccessor()); zuma.remove(original_p1->getSuccessor()); zuma.remove(original_p1); } //特判左边界指针p1提前走到header，但是p3还没到trailer，且链表仍可以一键三连的情况 //原因是p1绝大多数情况一次移动2个相对位置，p3一次移动1个相对位置，所以两边移动的速度是不平衡的，加上间隔的问题 //eg：ABBAA 插入：1 B 输出：AAA if (p1 == zuma.header() && zuma.size() >= 3) { p3 = p3->getSuccessor(); p2 = p3->getPredecessor(); p1 = p2->getPredecessor(); } } else //不能三消 { p3 = p3->getSuccessor(); p2 = p2->getSuccessor(); p1 = p1->getSuccessor(); } } zuma.display(); //输出 } } List zuma; char original_state[INPUT_SIZE] = { '0' }; int main() { //输入部分，original_state记录输入的原始数组，n记录回放次数 //List zuma; fgets(original_state, INPUT_SIZE, stdin); //链表初始化 int i = 0; while ((original_state[i] >= 'A' && original_state[i] <= 'Z') || (original_state[i] == '-')) { zuma.insertAsLast(original_state[i++]); } int n; scanf("%d", &n); //算法部分，采用 p1,p2,p3 3指针遍历 for (int i = 0; i < n; i++) { //每次插入新的元素 int position; char in; scanf("%d %c", &position, &in); zuma.insertAsBefore(in, position); //状态转移 transition(zuma); } if(zuma.size() == 0 && n == 0) printf("-"); //特判不玩游戏也不初始化的玩家 if(n == 0) zuma.display(); //特判不做动作的玩家 return 0; }最后一个测试用例TLE（超时）了，但是诡异的是第17个测试用例和第19个测试用例直接导致操作系统发送sigsegv中断信号，程序退出了。查了一下是非法访问、读写内存导致的，调大了输入部分的数组，但是并没有什么卵用。估计是链表指针的问题，于是特地去看了好几遍的transition()函数。但是看了好几圈没发现可能会导致指针越过头尾哨兵的地方，也没有一处指针会指向不确定的地址的地方，反正排查了很久都没找到问题出在具体的哪个部分，断断续续折腾了我快一个星期的时间。最后感觉可能是要卡死在这个问题上了，遂直接提交，最后除了第20个测试用例TLE，第17、19个RE（sigsegv），其它的都ac掉了。
