无法用XML表示的数据结构？

这是一个棘手的问题. XML是一个非常不受限制的树,它已经覆盖了所有数据结构的一半.即使是最奇特,最复杂的树仍然是树 – 我仍然不太了解vBE trees的创建和操作,但我知道它是一棵树,所以我可以将给定的vBE树变成XML.

为每个节点分配一个ID,或设计另一个轻量级方案来引用一个节点而不使它成为引用者的子节点,并且您可以毫无困难地构建任何类型的图形.图形几乎是通用数据结构的全部和最终结果.例如,有向循环图如下所示：

<graph>
  <vertex id="1">
    <!-- vertex data -->
    <edge to="3"/>
  </vertex>
  <vertex id="2">
    <!-- vertex data -->
    <edge to="1"/>
    <edge to="3"/>
  </vertex>
  <vertex id="3">
    <!-- vertex data -->
    <edge to="1"/>
    <edge to="2"/>
  </vertex>
</graph>

很明显这是如何映射到邻接列表的.支持更复杂的图形,如超图(边可以包含任意数量的顶点),您只需要一个单独的边列表,每个边包含一个顶点引用列表(参见下面的列表).

更普通的数据结构更容易映射到XML：

>数组,列表,队列,堆栈和其他有序的扁平集合：将每个项目作为节点,将它们放在单个< seq>中.父节点所以他们是兄弟姐妹.
>元组(k值)：为每个项目分配一个标识符,然后将它们作为属性.或者,制作一个<元组>具有k个子节点的节点,并且您不需要标识符,因为节点顺序(与属性顺序不同)被保留.
>词典：将它们视为(键,值)元组的序列.
>集合没有顺序,但我所知道的每个集合数据结构都在内部对元素进行排序(通过比较,通过散列和碰撞,或者仅仅通过初始情况下的插入顺序).当您要求数据结构枚举其元素时,要么使用该顺序,要么使用任何顺序(如果它不同).
>缺少数据结构？将其编码为记录(使用间接替换指针用于图形),然后将记录映射到具有每个记录成员的子节点或属性的节点.对于像链接列表这样的东西来说,这会变得很难看,但是对于它们来说,存在如上所述的更简单的表示.

这些表示中没有一个像真正的交易一样好,但你可以很好地使用它们并在内存中构建真实的数据结构是一个小而简单的循环与正确的库(例如Python中的lxml,部分原因是由于XPath的).

有一类数据结构不能很容易地映射到树.当你为每个元素使用几十个字节(或每个真元素,或每个虚假元素 – 问题)时,布尔矩阵,位掩码等从每个元素的单个位获得效率会大大增加遗迹).但是,较少以树为中心的编码可以解决这个问题.例如,您可以为一维位掩码存储base64字符串,并使用更高维度的序列(包括布尔矩阵).连接这些位以形成一个数字,并在base64中对其进行编码 – 或者更确切地说是在线进行以避免大精度算术.结果不是完全XML,但仍然足够简单,可以生成和解析.

因此,我无法为您提供无法在XML中合理表示的数据结构.这太普遍了,特别是当我们利用在base64等中嵌入任意二进制数据的能力时.如果你因为不是纯XML而拒绝它,那么带回家：在纯XML中无法有效地表示位掩码和布尔矩阵.但请注意,纯XML编码仍然是合理的,它只占用大量空间.如果假值的真实值很少(例如非常密集或稀疏图的邻接矩阵),通过仅存储较少的一个并使另一个隐含,则可以减轻这种情况.

但是,这并不意味着XML是编码这些数据结构的最佳选择,甚至是不错的选择.它是一种流行的数据交换格式,但对于任何给定的数据结构,都有更简单,更有效的表示.因此,如果您不需要灵活性并且可以承担额外的工作,请不要使用它.或者使用其他通用数据格式之一.上面描述的所有编码都在YAML中完美地工作,没有更多的冗长,并且有些工作甚至更好,因为内置了映射和数组.树木变得更加丑陋,因为你必须将它们编码为嵌套记录(读取：列表/映射),但这就是你用编程语言代表它们的方式.我也很确定JSON可以处理所有这些,但是由于我没有花费大量时间生成和解析它(我使用XML和YAML),我不能肯定地说.