数据结构第一次作业。
问题分析
题目要求书写程序对祖玛消除过程进行回放，输入为原始珠子序列以及玩家所做的一系列操作，要求我们按照游戏规则计算出每次操作后的珠子序列并进行输出。
祖玛游戏规则：有三个或更多同色珠子变成相邻就会立即消失，并且可能会发生连锁反应。需要注意，原始情况中出现的三个或更多相邻同色珠子，在没有新珠子或者连锁反应影响时是不会消除的。
解决方案
将新的珠子插入到原有序列，在插入位置向两侧判断同色珠子个数，满足条件则进行删除。考虑到删除后的连锁反应，需要将判断的过程循环执行到无法继续删除。
算法设计
考虑到整个过程需要多次插入删除的操作，并且查找过程只需要从插入的具体位置向两侧进行判断，所以使用list对珠子序列进行存储。
插入过程只需要简单的insert函数与advance函数相配合就可以了，使用advance函数使迭代器指到插入位置，之后再用insert函数进行插入。
比较难的地方在于是否消除的判断上，考虑到迭代器的特殊性，为了避免不必要的麻烦，当list中的元素少于三个的时候直接不进行判断。对三个以上的元素判断时，需要从插入元素的位置向两侧查找相同颜色，可以用end()和begin()来判断是否到达了查找的两端，当然，如果在查找过程中就发现了不同的珠子就可以直接停止查找过程。查找结束之后直接对查找到的区间进行删除，同时保留左开右闭区间的右端点作为下次查找过程的起始位置。
数据的输入和结果输出过程按照题目的要求进行编写即可。
流程图
编程实现
#include <iostream>
#include <list>
#include <string>
using namespace std;
void bang(list<char> & beads, int id, char bead){
list<char>::iterator i, r, l;
int num = 0; /*计数*/
i = beads.begin();
advance(i, id);
beads.insert(i, bead); /*插入元素*/
/*考虑到多次消除的可能，使用while循环进行消除*/
while(1){
if(beads.size() < 3)
break;
num = 0;
r = i--;
/*这步操作之后r指向被插入元素以后，i指向被插入元素*/
for(; r != beads.end(); r++){
if(*r == *i) num ++;
else break;
} /*向右判断*/
l = i;
/*if(i != beads.begin()){
l--;
while (1){
if(*l != *i){ l++;break;} //l需要加加
else num ++;
if(l == beads.begin()) break;
else l--;
}
} //向左判断*/
/*由流程图发现的简化方法*/
while(l != beads.begin()){
l--;
if(*l != *i){ l++; break;}
else num++;
}
/*删除部分*/
if(num > 1){
beads.erase(l, r);
i = r;
}
else
break;
}
/*输出*/
if(beads.empty())
cout << '-' << endl;
else{
for(i = beads.begin(); i != beads.end(); i++)
cout << *i;
cout << endl;
}
return ;
}
int main(){
int n, id;
char bead;
string initial_beads;
list<char> beads;
getline(cin, initial_beads);
for(int i = 0; i < initial_beads.size(); i++){
beads.push_back(initial_beads[i]);
}
/*构造初始状态*/
cin >> n;
while(n--){
cin >> id >> bead;
bang(beads, id, bead);
}
return 0;
}
结果分析
如上，经过测试，程序完成要求，并且能够处理初始序列为空的情况。👍
总结体会
- 增加了对erase函数的了解：
- 当参数只有一个的时候，原迭代器指向的位置被删除，迭代器无效化，不能对其继续进行操作，否则会造成错误，但函数会返回原位置之后的迭代器，所以可以利用这个特性进行区间删除（省略++步骤）。
- 当有两个参数的时候，函数结束之后前一个迭代器会无效化，而后一个迭代器因为删除区间为左闭右开的特点，其指向的位置不会被删除。
- 迭代器是一个很玄学的东西，使用不规范很容易带来错误，查错的时候可以优先考虑。
- 流程图可以帮忙理清逻辑结构！！！😀
- 写程序尽量一次性写完……🤧