如何理解计算物理中的元胞链接列表（Cell Linked List）算法？ 第1页

刚刚学了这块，授课老师讲的非常好，把这块讲明白了。

你的问题是：

1.Head是对应的元胞中序号最大的粒子么？

2.那List是怎么将粒子链接起来的呢？

先回答再解释。

1. HEAD这个数组存的是cell中序号最大粒子的序号，如果这个cell没有粒子，那么存的是0.

2. LIST用了一个技巧，把数组的标号跟存的内容巧妙结合。假如我们要遍历第i个cell中所有粒子，我们去HEAD(i)中找这个Cell的入口，HEAD(i)存的是这个cell最大序号粒子的序号，假设是m。然后我们去找LIST数组中LIST(m)这个元素，这个元素存的是cell中粒子序号第2小的序号，假设是n，然后找list(n)，这样就是是一个循环了。直到遇到存的值为0，认为我们把这个cell遍历完了。

=======

分子动力学模拟程序都是比较tricky的，就是说书上讲一个思路，操作上实际有多种实现方法，而且有的方法很巧妙、难以理解。这样需要你对着程序看，才能理解。你提的这两个问题就是如此，需要反复看程序去理解。

你需要看ftp://ftp.dl.ac.uk/ccp5/ALLEN_TILDESLEY/F.20这个程序，SUBROUTINE LINKS讲的是怎么构建Head跟list这两个至关重要的数列。

       C    ** ZERO HEAD OF CHAIN ARRAY **          DO 10 ICELL = 1, NCELL             HEAD(ICELL) = 0  10      CONTINUE      

先看这里，初始化把HEAD数组所有元素全都设为零。此时，HEAD数组的大小是的CELL个数。

       C    ** SORT ALL ATOMS **          DO 20 I = 1, N             ICELL = 1 + INT ( ( RX(I) + 0.5 ) * CELLI )      :               + INT ( ( RY(I) + 0.5 ) * CELLI ) * M      :               + INT ( ( RZ(I) + 0.5 ) * CELLI ) * M * M             LIST(I)     = HEAD(ICELL)            HEAD(ICELL) = I  20      CONTINUE       

再看这里，遍历所有粒子，看看这个粒子在哪个cell里面，就把它的标号作为这个Cell的head。

注意，在把粒子序号存在HEAD这个数组之前，前一个HEAD值存到了LIST(I)中，这部分与你第二个问题有关，稍后讲解。

问题1解决了，这样的话，HEAD数组里面存的是每个CELL中序号最大粒子的序号。但是有一个细节，就是如果这个CELL里面没有粒子，那么这个CELL的Head就是0。

========

现在解释问题2

LIST存的是什么呢？

按照上述第二个程序，LIST存的东西应该是这样。以两个CELL情况为例。

每个CELL粒子最大序号存在了HEAD数组中，这个序号指出了下个原子序号在数组LIST中的位置。例如上图，我们找第二个cell的head值，我们找到HEAD(2)=10，然后找LIST(10)，LIST(10)=9。然后找LIST(9),LIST(9)=6。然后找LIST(6)，...知道找到0，认为这个cell遍历完了。

然后你就能看懂你课件上的这个图了。

参看 Computer Simulation of Liquids'' by M.P. Allen and D. Tildesley Clarendon Press Oxford 1987.

@专治各种不收敛 把技术细节回答的差不多了，我来介绍一下元胞链表这个算法。

在分子模拟中，经常要计算某个粒子与其他粒子之间的相互作用。这个作用往往与距离密切相关，因此需要频繁的搜索粒子周围的“邻居”。

不妨把粒子比喻成一个个租客，他们住在一栋很大的公寓楼（模拟空间）里。假设此时你要确定A租客的邻居以及室友的名单，最傻大粗的办法当然是把整栋楼的租客都排查一遍，但这么做显然太费事。省事一点的做法是按房间（元胞）号来排查：

1. 判断A自己的房间号，假设为506。
2. 确定包括506自身在内的附近9个房间（405~407，505~507，605~607）。
3. 逐一确定以上9个房间内的租客名单。

显然，为了完成以上步骤，你需要先把公寓楼划分成一个个房间，并且要有每个房间的租客信息表。

在分子模拟中，粒子就是租客，整个模拟空间就是公寓楼，人为划分出来的元胞就是公寓楼的房间，而元胞链表就是房间的租客信息表。

租客信息表里没有真的住人，它只是记录了门牌号、租客个数、每个租客的姓名，床号（粒子的具体坐标）等信息的一个表，它大概长这样：

• 门牌号:516
• 租客1:张狗蛋（5号床铺）
• 租客2:李麻子（2号床铺）
• ...
• 租客n：王小六（m号床铺）

分子模拟中的粒子是会到处游走的，相当于租客经常换房间。因此，租客信息表（元胞链表）需要时不时的进行租客搬出、搬入等增减更新，且房间内住的租客上限不好确定。因此，在计算机中，租客信息表不方便用数组形式表达，往往以链表的形式储存。这也是为什么算法名字中有“链表”二字的原由。

欢迎关注我的专栏，虽然更新有点慢：