Question

如何用c语言编生命游戏程序

1． 如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生，即该细胞若原先为死，则转为生，若原先为生，则保持不变；
2． 如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；
3． 在其它情况下，该细胞为死，即该细胞若原先为生，则转为死，若原先为死，则保持不变设定图像中每个像素的初始状态后依据上述的游戏规则演绎生命的变化，由于初始状态和迭代次数不同，将会得到令人叹服的优美图案。
要求：有完整的思想，就是请把思路解释一下
各位，谢谢哈

Answer 1

写了这么多，记得追点分啊~~~~~`

这个问题分解为两部分

1、用什么方式表示某时刻有哪些细胞是活的
一种简单的想法是用一个二位数组将某时刻所有的细胞的状态都记录下来，不过这样的内存开销太大，同时又给细胞网格设定了界限，而且效率也并不高
比较好的做法是用一个线形表int list[][2]来记录某时刻的所有的活细胞的坐标，同时用一个整数int n记录当前的活细胞数量

2、如何从某时刻的状态推导出下一时刻有哪些细胞为活的
根据规则，显然，某时刻某个细胞是否活着完全取决于前一时刻周围有多少活着的细胞，以及该时刻该细胞是否活着
因此，推导下一时刻状态时，根据当前list中的活细胞，可以得到该时刻有哪些细胞是与活细胞相临的，进而得知这些细胞在该时刻与多少个活细胞相临，于是可以知道下一时刻有哪些细胞是活的
具体实现时，需要一个能够储存坐标并给每个坐标附带了一个计数器(记录该坐标的细胞与多少个活细胞相临)和一个标志(0或1，表示当前该坐标的细胞是活是死)的容器，假设为T，容器T的功能是检查某个坐标是否在其中，以及向其中添加带有某个标志某个坐标并将该坐标的计数器清零，以及将某个坐标的计数器累进一

比如，假设已经定义了

struct Container
{
...
};//容器类型
void Clear(Container *T);//清空容器T
int Exist(Container *T,int x,int y);//返回坐标(x,y)是否存在于T中
void Insert(Container *T,int x,int y,int flag);//将标志为flag的坐标(x,y)加入T
void Add(Container *T,int x,int y);//将坐标(x,y)的计数器累加
void Promote(Container *T,int *n,int list[][2]);//将容器中所有计数器值为3的坐标以及所有计数器为2并且标志为1的坐标添加到list中，并将其个数记录于n

此外，为了方便找出某个坐标的所有相邻坐标，设置以下方向常量
const int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,1},{1,-1},{-1,-1}};

那么，从某时刻状态生成下一时刻状态的主要代码如下

...
Container T;
int i,j;
...
Clear(&T);
for (i=0;i<n;i++) Insert(&T,list[i][0],list[i][1],1);
for (i=0;i<n;i++)
for (j=0;j<8;j++)
{
int x,y;
x=list[i][0]+dir[j][0];
y=list[i][1]+dir[j][1];
if (!Exist(&T,x,y)) Insert(&T,x,y,0);
Add(&T,x,y);
}
Promote(&T,&n,list);
...

关于容器T如何实现，一种简单的思路是用线形表并将元素有序记录，不过这样的查找/插入效率难以兼顾
用哈希表的话，最后的Promote很难实现
块状链表可以兼顾查找与插入的效率，但是写起来太恶心，效率也不是特别高
个人认为，最佳的解决方案是用平衡二叉搜索树，常见的AVL树或者红黑树什么的，不过写起来也太麻烦。
这里强烈推荐Size Balanced Tree，由中国一位现在读高二的高中生所发明，原理清晰，效率高，实现简单