复合对象解析为XML的顺序表算法

上两个图，说明复合对象的关系以及XML表示的方法：

简单来说就是Root中有objectA跟objectB，objectB中包含objectC，objectC中又包含了objectA，即引用了objectA。




    注意看objectC这个节点中，reference属性使用相对路径表示出了objectA的位置。
大家从上面两个图应该了解这是个什么情况了。

    那么先说一下树形结构的解决方案，当然是构建多叉树，然后开始对树进行遍历，效率是很低的~~

    那么再说下我的解决方案：
    看图：

    Root伴随着一个长度为1的数组，第一个元素为0，表示这是根节点，objectA伴随着长度为2的数组，表示它是Root的第一个节点，objectB和objectC应该也很好理解了吧。
这样，当把Root解析为XML时，发现objectC引用了ObjectA，那么怎样获得reference的值呢？因为这是一个顺序表，所以我们去遍历它。首先取得objectA的标志性数组{0，1}那么先查找数组第一个元素为0的元素，在绝对路径上加上“Root”，得到“/Root”，然后开始搜索第二个元素为1的节点，找到后加到绝对路径上就得到“/Root/objectA”了。

    另外需要说明的是，再设计这个算法的时候，我不确定xml是否必须只有一个根节点，所以采用了现在的思路，如果能够确定只有一个根节点的话，那么就可以稍作更改了，总的思路就是这样的，至于在具体实现中，采用数组还是ArrayList，还是HashMap，大家就随意了。我刚刚构思出这个算法，也没有通过实际的例子与树形结构的算法进行性能比较，但是顺序表查找快是无需置疑的，所以我感觉这个算法还是应该很有效率的，欢迎大家拍砖~~

 

评论

2 楼 E-Hunter 2010-08-22  

恩恩~楼上所言极是，所以后来我才又发表了《复合对象解析为XML的顺序表算法的改进》，改掉了这个算法中的一些缺陷。另外，由于时间关系我还没有来得及进行实际测试的相关工作，编码过程中所遇到的一些其他问题，会陆续在博客中发表，与大家进行交流~

1 楼 zozoh 2010-08-22  

这个算法有两个关键：

  1. 什么是对象的 ID
  2. 如何根据对象反查出对象的 ID // 在 refer A 时，你需要知道 A 的 ID
 
楼主给出的答案是
 
  1. ID 就是一个数组，表示一条路径
  2. 循环遍历索引表
 
我的问题是：
 
  1. ID 为什么是一个数组而不是一个整数呢？
  2. 至少要用散列吧

我的详细建议：

如果，每输出一个节点，都将这个对象放到一个数组里

ids[i] = obj;
i++

并且将 i 为这个对象的 ID，如果你知道了一个对象的ID，则可以很快拿到这个对象的实例引用

那么其他对象 refer 这对象时，如果获得这个对象的ID呢？
因此你还需要一个这个对象的反查索引：

ids[i] = obj;
indexes.add(obj, i);
i++

根据一个对象，获取其 ID

int objId = indexes.get(obj);

如果采用 HashMap，则对象的 hashCode() 方法给出的散列值是效率的关键，但是效果最差也比遍历索引表要快很多
因为它是对基于 hasCode 的散列表进行二分查找

无论从 POJO 到 XML，还是从 XML 到 POJO，大体都可以用这种思路