04-顺序表和堆栈练习

题目描述
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。

给定轨道上初始的珠子序列，然后是玩家所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。

输入
第一行是一个由大写字母’A’~'Z’组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。

第二行是一个数字n，表示玩家共有n次操作。

接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母描述，以空格分隔。其中，大写字母为新珠子的颜色。若插入前共有m颗珠子，位置0-m-1，则k ∈ [0, m]表示新珠子嵌入在轨道上的位置。


输出
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。

如果轨道上已没有珠子，则以“-”表示。

输入样例
ACCBA
5
1 B
0 A
2 B
4 C
0 A

ABCCBA
AABCCBA
AABBCCBA
—
A

以下有三个方法，实际上只有第一个可以过OJ，第二个方法存在编译错误，第三个方法存在溢出
很悲伤，只看得懂第二第三个方法

#include<iostream>
#include<string>
using namespace std;

class node
{
public:
 char ch;
 int data;
 node* next;
 node* prior;
};

void create(node* head, int n, string s)
{
    node* tail = head;
    head->data = 0;
    char ch;
    for (int i = 0; i < n; i++)
    {
        node* pnew = new node;
        pnew->next = NULL;
        pnew->prior = tail;
        pnew->ch = s[i];
        tail->next = pnew;
        tail = pnew;
        head->data++;
    }
}
void print(node* head)
{
    node* h = head->next;
    if (!head->data) cout << "-";
    else
    {
        for (int i = 0; i < head->data; i++)
        {
            cout << h->ch;
            h = h->next;
        }
    }
}

//插入
void insert(node* head, int index, char ch)
{
    node* p = head->next;
    if (index)
    {
        for (int i = 1; i < index; i++)
            p = p->next;
        
        node* pnew = new node;
        pnew->ch = ch;
        pnew->prior = p;
        pnew->next = p->next;
        p->next = pnew;
        
        if (pnew->next)
            pnew->next->prior = pnew;
        
        head->data++;
    }
    else if (head->data)
    {
        p = head;
        node *pnew = new node;
        
        pnew->ch = ch;
        pnew->prior = p;
        pnew->next = p->next;
        p->next = pnew;
        pnew->next->prior = pnew;
        
        head->data++;
    }
    else
    {
        p = head;
        node* pnew = new node;
        pnew->ch = ch;
        pnew->prior = p;
        pnew->next = p->next;
        p->next = pnew;
        head->data++;
    }
}
//遍历检查
void rearch(node* head)
{
 node* p = head->next;
 while (p)
 {
  if (!p->next) break;
  if (p->ch == p->prior->ch && p->ch == p->next->ch)
  {
   int sum = 3;
   //用d0指向需删除最左端珠子的前继
   node* d0 = p->prior->prior;
   //用d1指向需删除最右端珠子的后继
   node* d1 = p->next->next;
   if (d1)
    while (d1->ch == p->ch)
    {
     if (!d1->next) break;
     d1 = d1->next;
     //需删除总数++
     sum++;
    }
   if (d1)
   {
    d0->next = d1;
    d1->prior = d0;
   }
   else d0->next = NULL;

   head->data -= sum;
   p = head->next;
  }
  else
   p = p->next;
 }
}
int main()
{
 string s;
 char ch;
 int index;
 cin >> s;
 int n = s.length();
 node *head = new node;
 create(head, n, s);
 int t;
 cin >> t;
 while (t--)
 {
  cin >> index >> ch;
     
  insert(head, index, ch);
  rearch(head);
  print(head);
     
  if (t)cout << endl;
 }
 return 0;
}

#include<iostream>
#include<string.h>
#include<cstdio>
#define MAX 200000000
using namespace std;

typedef struct node
{
 char data;
 struct node *next;
 struct node *prior;
}node;

int main()
{
    int n,len,i,sum;
    node *L=new node;
    struct node *p=L;
    struct node *q;
    char a[100];

    gets(a);
    len=strlen(a);
    
    for(i=0;i<len;i++)
    {
        q=new node;
        q->data=a[i];
        q->prior=p;p->next=q;
        p=q;
    }
    
    cin>>n;
    
    while(n--)
    {
        
        int j;
        char ch;
        cin>>j>>ch;
        
        struct node *p,*q;
        p=L->next;
        while(j--)
            p=p->next;
        
        
        //在t之后插入ch
        q=new node;
        q->data=ch;
        q->prior=p->prior;
        p->prior->next=q;
        q->next=p;
        p->prior=q;
        
        len++;
        
        //删除三个一起的字母
        
        while(1)
        {
        while(q&&q->data==ch)
            q=q->next;
        while(p->prior&&p->data==ch)
            p=p->prior;
            
        struct node *r=p;
        sum=0;
        while(r&&r!=q)
        {
            r=r->next;
            sum++;
        }
        if(sum>=4)
        {
            p->next=q;
            if(q)
                q->prior=p;
            if(p!=L)
                ch=p->data;
            else if(q)
                ch=q->data;
                
            len-=(sum-1);
            //shanchu(ch,p,q,L,len);
        }
        else
            break;
        }
        
        if(len==0)
        cout<<"-";
        else
        {
            p=L;
            for(i=0;i<len;i++)
            {
                p=p->next;
                cout<<p->data;
            }
        }
        cout<<"\n";
    }
    
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAX 200000000

//祖玛色块类
struct Zuma{
    char date;
    Zuma *up;
    Zuma *down;
    Zuma(){};
    Zuma(char s):date(s){};
}*header,*tailer;    //首尾哨兵

char s[MAX];
int length;    //链表长度
int k;    //记录数据长度

//双向链表-尾插法
void Creat_zuma(char *s)
{
    header = new Zuma();
    header->up = NULL;

    Zuma *rear = header;    //定义尾部指针-穿针
    for (int i = 0; i < length; i++)
    {
        Zuma *p = new Zuma(s[i]);
        rear->down = p;
        p->up = rear;

        rear = p;    //换针
    }
    tailer = new Zuma();
    rear->down = tailer;
    tailer->up = rear;
    tailer->down = NULL;
}

//遍历查找pos位置的指针
Zuma* Find(int pos)
{
    int counter = 0;
    Zuma *p = header;
    if (length - pos >= pos)    //首部遍历
    {
        while (counter < pos && p->down != tailer)
        {
            p = p->down;
            counter++;
        }
    }
    else{                        //尾部遍历
        p = tailer;
        counter = length;
        while (counter >= pos && p->up != header)
        {
            p = p->up;
            counter--;
        }
    }
    return p;
}

//消除
Zuma* Remove(Zuma *cur,char c)
{
    while (1)
    {
        Zuma *pre = cur->down;
        int counter = 0;
        while (cur != header && cur->date == c)    //向前查重
        {
            cur = cur->up;
            counter++;
        }
        while (pre != tailer && pre->date == c)    //向后查重
        {
            pre = pre->down;
            counter++;
        }
        if (counter >= 3)    //重复元素大于三个
        {
            length -= counter;
            Zuma *p1 = cur->down, *p2;
            while (p1 != pre)    //delete
            {
                p2 = p1->down;
                delete p1;
                p1 = p2;
            }
            cur->down = pre;
            if (pre != NULL)
                pre->up = cur;
            c = cur->date;
        }
        else break;
    }
    return cur;
}

//插入
void Insert(Zuma *p, char c)
{
    Zuma *x = new Zuma(c);
    if (p->down != NULL)
    {
        x->up = p;
        x->down = p->down;
        p->down->up = x;
        p->down = x;
    }
    else{
        x->up = p;
        x->down = NULL;
        p->down = x;
    }
    length++;
}
int main()
{
    int n;
    gets(s);
    scanf("%d", &n);
    length = strlen(s);
    //搭建
    Creat_zuma(s);

    for (int t = 0; t < n; t++)
    {
        char c[2];
        int pos;
        scanf("%d%s", &pos, &c);

        Zuma *p = Find(pos);
        Insert(p, c[0]);
        Zuma *flag = Remove(p, c[0]);
        //Record
        if (flag == header && flag->down == tailer)
        {
            s[k++] = '-';
            s[k++] = '\n';
        }
        else{
            flag = header;
            while (flag->down != tailer)
            {
                s[k++] = flag->down->date;
                flag = flag->down;
            }
            s[k++] = '\n';
        }
        //Single Input
        if (t == n - 1)
        {
            s[k] = '\0';
            printf("%s", s);
            k = 0;
        }
    }
    return 0;
}