数据结构作业一 Zuma List

wanakiki 收录于数据结构

2019-04-20 约 1213 字预计阅读 3 分钟

数据结构第一次作业。

问题分析

题目要求书写程序对祖玛消除过程进行回放，输入为原始珠子序列以及玩家所做的一系列操作，要求我们按照游戏规则计算出每次操作后的珠子序列并进行输出。

祖玛游戏规则：有三个或更多同色珠子变成相邻就会立即消失，并且可能会发生连锁反应。需要注意，原始情况中出现的三个或更多相邻同色珠子，在没有新珠子或者连锁反应影响时是不会消除的。

解决方案

将新的珠子插入到原有序列，在插入位置向两侧判断同色珠子个数，满足条件则进行删除。考虑到删除后的连锁反应，需要将判断的过程循环执行到无法继续删除。

算法设计

考虑到整个过程需要多次插入删除的操作，并且查找过程只需要从插入的具体位置向两侧进行判断，所以使用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函数的了解：
1. 当参数只有一个的时候，原迭代器指向的位置被删除，迭代器无效化，不能对其继续进行操作，否则会造成错误，但函数会返回原位置之后的迭代器，所以可以利用这个特性进行区间删除（省略++步骤）。
2. 当有两个参数的时候，函数结束之后前一个迭代器会无效化，而后一个迭代器因为删除区间为左闭右开的特点，其指向的位置不会被删除。
迭代器是一个很玄学的东西，使用不规范很容易带来错误，查错的时候可以优先考虑。
流程图可以帮忙理清逻辑结构！！！😀
写程序尽量一次性写完……🤧

目录