这个基于数组的数据结构有名称吗

Question

我对一个特定的数据结构做了很多工作，我主要将其用作平面树结构中项目的索引。它由一个正整数数组（或字节，或长度或其他）组成，每个整数都被认为处于等于其在数组中索引的"深度"。

将其视为树中的索引，树的根有一个空数组作为其索引，并且具有索引{a, b... c}的给定节点的第N个子节点有索引{a, b... c, N}。

对它的常见操作是递增/递减数组中的最后一个数字，从前面或后面删除一些元素，并将一些元素添加到前面或后面。在树索引上下文中，它们分别对应于向前/向后遍历同级节点、在子树中查找索引或查找父节点的索引、在树根固定到另一棵树时查找索引以及查找某个子节点的索引。

尽管我最初只是将它们用作索引，但我不断发现使用它们的新方法，从加快数据序列化到提高代码可读性。这让我想知道，这种数据结构或类似的东西是其他地方常用的吗？如果是，它有名字吗？我很想看看我还能用这个做些什么。

（C#中的示例实现，省略了错误检查以保持可读性）

class TreeIndex
{
    public readonly int depth
    {
        get
        {
            return widths.Length;
        }
    }
    public readonly int[] widths;
    public TreeIndex()
    {
        widths = new int[0];
    }
    public TreeIndex(params int[] indices)
    {
        widths = indices;
    }
    public static implicit operator int(TagIndex ti)
    {
        return ti[ti.depth - 1];
    }
    public static operator TagIndex +(TagIndex ti, int i)
    {
        int[] newwidths = ti.widths.Clone();
        newwidths[newwidths.Length - 1] += i;
        return new TagIndex(newwidths);
    }
    public static operator TagIndex -(TagIndex ti, int i) { return ti + (-i); }
    public static operator TagIndex <<(TagIndex ti, int i)
    {
        int[] newwidths = new int[ti.depth - i];
        Array.Copy(ti.widths, newwidths, ti.depth - i);
        return new TagIndex(newwidths);
    }
    public static operator TagIndex >>(TagIndex ti, int i)
    {
        int newwidths = new int[ti.depth - i];
        Array.Copy(ti.widths, i, newwidths, 0, ti.depth - i);
        return new TagIndex(newwidths);
    }
    public static operator TagIndex ^(TagIndex tia, TagIndex tib) 
    {
        int newwidths = new int[tia.depth + tib.depth];
        Array.Copy(tia.widths, newwidths, tia.depth);
        Array.Copy(tib.widths, 0, newwidths, tia.depth, tib.depth);
        return new TagIndex(newwidths);
    }
}

Answer 1

注释是正确的：它只是一个列表。

考虑List<T>类。您可以通过设置Capacity属性来增加或减少其容量（类似于-和+运算符）。您可以通过调用AddRange将项目添加到列表的末尾。您可以通过调用InsertRange在列表中的任何位置插入项目。删除项目就是调用RemoveRange。

您的^操作员很简单：

list1.AddRange(list2);

List<T>完成数据结构所做的一切，除此之外，还包括实现所有常见的收集接口：IList、ICollection、IEnumerable等。NET程序员很熟悉。如果您曾经设想过其他人在处理您的代码，那么建议您使用List<T>，而不是使用其他人不熟悉的非标准语义和疯狂重载来滚动自己的自定义类。