线性表练习之ZUMA

线性表练习之ZUMA

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

线性表练习之ZUMA
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能,而回放功能的实现则委托你来完成。
游戏过程的记录中,首先是轨道上初始的珠子序列,然后是玩家接下来所做的一系列操作。你的任务是,在各次操作之后及时计算出新的珠子序列。

输入描述:
第一行是一个由大写字母’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

全代码:


# include<iostream>
# include<stdio.h>
using namespace std;

const int N = 10;
char str[100];

struct Node
{
 char data;
 Node  *next;
 Node  *prior;
};

class LinkList
{
public:
 LinkList(char a[], int n); //有参构造函数,使用含有n个元素的数组a初始化单链表
 ~LinkList();             //析构函数 
 void Insert(int n, char a);//插入
 Node * Get(int i);   //获取线性表第i个位置上的元素结点地址
 void Delete(Node * l,Node* r);  //删除两节点间的元素 
 void PrintList(bool boo);//输出结果
 void GoThrough();//遍历整个链表删除重复项
private:
 Node * front;  //头指针
 Node * tail;
};

LinkList::LinkList(char a[], int n)//构造链表
{
 front = new  Node;
 tail = new Node;
 tail->next = NULL;
 Node *r = front;//初始化头结点
 for (int i = 0; i < n; i++)
 {
  Node *s = new Node;
  s->data = a[i];
  s->next = tail;// 生成新结点
  r->next = s;// 链接在尾结点后面
  s->prior = r;
  tail->prior = s;
  r = s;// 尾指针后移
 }
}

LinkList::~LinkList()    //析构函数
{
 Node *p = NULL;  //初始化工作指针p 
 while (front->next != NULL)  //要释放的结点存在
 {
  p = front->next;   //暂存要释放的结点
  p->prior = front;
  delete front;    //释放结点
  front = p;       //移动工作指针
 }
}

void LinkList::Insert(int i, char x)
{
 Node * p = front;  //初始化工作指针
 //若不是在第1个位置插入,得到第i个元素的地址。
 if (i != 1) p = Get(i);
 if (p != NULL)
 {
  Node  * s = new Node ;//建立新结点
  s->data= x;
  s->next = p->next;
  s->prior=p;
  p->next = s;  //将新结点插入到p所指结点的后面
  s->next->prior = s;
 }
 else throw "插入位置错误";
}

Node  *LinkList::Get(int i)
{
 Node *p = front;  //初始化工作指针
 int j = 1;
 if (i != 1)
  while (j!=i && p != NULL)
  {
   p = p->next;
   j++;
  };
 if (p == NULL) throw "位置非法";
 return p;
}

void LinkList::PrintList(bool boo)
{
 static int count;
 Node *p = front->next;
 if (p==tail)
 {
  str[count++] = '-';
 }
 else
 {
  while (p->next)
  {
   str[count++] = p->data;
   p = p->next;
  }
 }
 str[count++] = '\n';
 if (boo)
 {
  cout << "Outcome:" << endl;
  str[count] = '\0';
  cout << str;
  count = 0;
 }
};

void LinkList::Delete(Node * l, Node *r)
{
 Node *s = l;
 Node *t =NULL;
 Node *R1 = r->next;
 //l->prior->next = r->next;
 while (s != R1)
 {
  t = s->next;
  s->prior->next = t;
  t->prior = s->prior;
  delete s;
  s = t;
 }
}

void LinkList::GoThrough()
{
 Node * first = front->next;
 Node * second = first->next;
 while (first->next!= tail)
 {
  if (first->data != second->data)
  {
   if (first->next->next!=second&&first->next!=second)
   {
    Delete(first, second->prior);
    first = front;
    second = first->next;
   }
   else
   {
    first = first->next;
    second = first->next;
   }
  }
  else
  {
   if(second->next!=NULL)
    second = second->next;
  }
 }
}

int main()
{
 int lens;
 int turn;
 char a[N];
 cout << "Start Zuma:";
 cin >> a;
 lens = strlen(a);
 LinkList zuma(a, lens);
 cout << "Turns:";
 cin >> turn;
 for (int i = 0; i < turn; i++)
 {
  int ts;
  char cs;
  do
  {
   cin >> ts >> cs;
  } while (cs <'A'&&cs> 'Z');
  zuma.Insert(ts + 1, cs);
  zuma.GoThrough();
  zuma.PrintList(i==turn-1?true:false);
 }
}

构造函数

LinkList::LinkList(char a[], int n)//构造链表
{
 front = new  Node;
 tail = new Node;
 tail->next = NULL;
 Node *r = front;//初始化头结点
 for (int i = 0; i < n; i++)
 {
  Node *s = new Node;
  s->data = a[i];
  s->next = tail;// 生成新结点
  r->next = s;// 链接在尾结点后面
  s->prior = r;
  tail->prior = s;
  r = s;// 尾指针后移
 }
}

浅析:
(1)双链表的构造方式,便于前后查找;
(2)首、尾结点的建立,有首有尾,任何时刻都能将整个链表拎起,便于遍历全链表的循环删除操作;

析构函数

LinkList::~LinkList()    //析构函数
{
 Node *p = NULL;  //初始化工作指针p 
 while (front->next != NULL)  //要释放的结点存在
 {
  p = front->next;   //暂存要释放的结点
  p->prior = front;
  delete front;    //释放结点
  front = p;       //移动工作指针
 }
}

浅析:
(1)由于尾结点的存在,所以while判断语句的条件换为“front->next != NULL”,其余操作任与传统双链表相同。

插入

void LinkList::Insert(int i, char x)
{
 Node * p = front;  //初始化工作指针
 //若不是在第1个位置插入,得到第i个元素的地址。
 if (i != 1) p = Get(i);
 if (p != NULL)
 {
  Node  * s = new Node ;//建立新结点
  s->data= x;
  s->next = p->next;
  s->prior=p;
  p->next = s;  //将新结点插入到p所指结点的后面
  s->next->prior = s;
 }
 else throw "插入位置错误";
}

(没有什么特殊的,常规操作)

获取元素位置

Node  *LinkList::Get(int i)
{
 Node *p = front;  //初始化工作指针
 int j = 1;
 if (i != 1)
  while (j!=i && p != NULL)
  {
   p = p->next;
   j++;
  };
 if (p == NULL) throw "位置非法";
 return p;
}

(没有什么特殊的,只要记住用的时候注意一下i,j的初始值设定)

输出

(这是一个挺新颖的函数,我以前没有用过这种方法)

void LinkList::PrintList(bool boo)
{
 static int count;
 Node *p = front->next;
 if (p==tail)
 {
  str[count++] = '-';
 }
 else
 {
  while (p->next)
  {
   str[count++] = p->data;
   p = p->next;
  }
 }
 str[count++] = '\n';
 if (boo)
 {
  cout << "Outcome:" << endl;
  str[count] = '\0';
  cout << str;
  count = 0;
 }
};

浅析:
(1)接口使用bool类型,便于判断是否循环到了最后一组,使结果可以在一起输入过后一起输出。
(2)用数组记录下来所有字符
(3)用static计数
(4)在相应位置录入’\n’即可满足回车的需求
PS:也可以试试freopen(),存到文件里

遍历

(前方压轴出场的是核心代码!)

void LinkList::GoThrough()
{
 Node * first = front->next;
 Node * second = first->next;
 while (first->next!= tail)
 {
  if (first->data != second->data)
  {
   if (first->next->next!=second&&first->next!=second)
   {
    Delete(first, second->prior);
    first = front;
    second = first->next;
   }
   else
   {
    first = first->next;
    second = first->next;
   }
  }
  else
  {
   if(second->next!=NULL)
    second = second->next;
  }
 }
}

浅析:
线性表练习之ZUMA
开始循环判断,直到F->next=tail:
1.如果F的值与S的值相等且S->next不为空
则S向右移动
线性表练习之ZUMA
2.如果F的值不等于S的值:
判断是否有三个或三个以上的重复(F的下一个不是S,F的下一个的下一个也不是S,这样就可以确定F与S之间有三个或三个以上重复元素了):
(1)若有,则删除(函数)F和S->prior中的结点,每完成一次操作删除后就将指针复原指回头。
(2)若无,则F移向下一位,S移向F的下一位

删除

void LinkList::Delete(Node * l, Node *r)
{
 Node *s = l;
 Node *t =NULL;
 Node *R1 = r->next;
 //l->prior->next = r->next;
 while (s != R1)
 {
  t = s->next;
  s->prior->next = t;
  t->prior = s->prior;
  delete s;
  s = t;
 }
}

浅析:
(1)单独成立一个函数,便于代码重用
(2)用结点作为参数,删除结点(包括结点本身)之间的结点


总算完成了这zuma…感动到哭泣

上一篇:hive练习


下一篇:oracle树中prior的用法