里仁学院论文模板2013

第3章 Index Lookup Eager算法原理与实现

5. 求B中每个节点v在Si中的左匹配和右匹配

6. 求节点v和它的左（右）匹配的最低公共祖先（LCA）

7. 如果v在Si中的左匹配和有匹配都存在则定有一个节点是父亲节点一个是孩子节点，将孩子节点（descendant）是x； 8. 判断x是否符合SLCA的条件符合则加入result中 9. 返回result，重复4-9，直到i>n; 10. 重复3-9，直到S1为空。

在有明确的数据结构以后就可以完成对整个算法的实现。

3.3.1查询左右匹配节点

由算法3.2和3.3可知要求关键字的SLCA首先需要求出缓冲区B中节点在Si中的左匹配节点和右匹配节点。具体算法：

左匹配：

public ArrayList lm(ArrayListv, ArrayList>S1) { int i; if (v.size()==0) { return null; } else { for (i = 0;i < S1.size();i++) { ArrayList pCur=new ArrayList(); pCur = S1.get(i); if (pCur.get(pCur.get(0)) == v.get(v.get(0))) { return pCur; } //没有左 if ((pCur.get(pCur.get(0)) > v.get(v.get(0))) && i==0) { return null; }

23

燕山大学本科生毕业设计（论文）

} }

//有左 if ((pCur.get(pCur.get(0))> v.get(v.get(0))) && i > 0) { return S1.get(i-1); } }

return S1.get(S1.size() - 1);//所有的元素都在v的左边

右匹配 public ArrayList rm(ArrayListv,ArrayList>S1) {

int i;

if (v.size()==0) {

return null; }

for(i=0;i

ArrayList a=new ArrayList(); a=S1.get(i);

if ((a.get(a.get(0)))>=v.get(v.get(0))) {

return S1.get(i); } }

return null;

}

3.3.2求解最低公共祖先LCA

求解两个节点的LCA只需将它们编码中从第零位开始相同的部分取出到遇到第一个不同的编码为止。具体函数如下：

ArrayList lca(ArrayList v,ArrayList v1) { if (v==null||v1==null) {

24

第3章 Index Lookup Eager算法原理与实现

return null; } else { ArrayList m1=new ArrayList(); int n = v.get(0)<=v1.get(0)? v.get(0):v1.get(0); int i; for ( i=1;i<=n;i++) { int a=v.get(i); int b=v1.get(i); if(a==b) m1.add(a); else break; } m1.add(0, i-1); return m1; } }

3.3.3求解孩子节点

在本算法中descendant（）函数中两个参数若都不为空则一定存在父亲与孩子的关系，所以只需返回两节点中最后一位小的节点便是孩子节点。若有一个参数为空则返回另一个，若都为空则返回空。具体算法如下： public ArrayList descendant(ArrayList v1,ArrayList v2) { if (v1==null && v2!=null) { return v2; } else if (v1!=null && v2==null) { return v1; } else if(v1!=null && v2!=null) { int c=v1.get(v1.get(0));

25

燕山大学本科生毕业设计（论文）

} }

int d=v2.get(v2.get(0)); if (c <= d) { return v2; }

if (c > d) { return v1; }

return null;

3.3.4求解节点的祖先关系

在两个参数中如果第一个是第二个参数的祖先，则第一个节点编码是第二个节点编码的一部分，则可以通过比较实现。具体算法如下： public boolean parent(ArrayList paru,ArrayList descv) { if (paru.size()==0||descv.size()==0) { return false; } else { int a=paru.get(0); int b=descv.get(0); if (a > b) //相等不为祖先 { return false; } else { int i; for (i=1;i<=a;i++) { int c=paru.get(i); int d=descv.get(i); if(c != d) { break;

26