如何将数组指针操作 ( &(*t)->next[x] ) 从 C 转换为 C#

Question

我正在尝试将一些旧的“C”代码转换为 C#，但语法有问题

t = &(*t)->next[u];

和

(*t)->end = 1;

原代码相关部分如下

typedef struct Trie Trie;

struct Trie {
    int end;
    Trie *next[26];
};

void trie_insert(Trie **t, const char *p)
{
    while (*p) {
        unsigned u = trie_index(*p++);
        if (u < 26) {
            if (*t == NULL) {
                *t = calloc(1, sizeof(**t));
            }

            t = &(*t)->next[u];  // how to convert this??
        }
    }
    if (*t == NULL) {
        *t = calloc(1, sizeof(**t));
    }
    (*t)->end = 1;
}

Trie *trie_from(const char **data)
{
    Trie *t = NULL;

    while (*data) {
        trie_insert(&t, *data++);
    }

    return t;
}

我转换后的代码（到目前为止）看起来像这样

class Trie
{
    int end { get; set; }
    public Trie[] next;

    public Trie()
    {
        next = new Trie[26];
    }
    public Trie(string[] data)
    {
        Trie[] t = null;
        foreach (string cc in data)
        {
            insert(t, cc);
        }
    }
    void insert(Trie[] t, String p)
    {
       foreach (char c in p) { 
            UInt32 u = index(c);
            if (u < 26)
            {
                if (t[0] == null)
                {
                    t[0] = new Trie();
                }

                t = &(*t)->next[u]; // how to convert this line??
            }
        }
        if (t[0] == null)
        {
            t[0] = new Trie();
        }
        (*t)->end = 1; // and this line??
    }

欢迎任何有关这些行的帮助（以及我做错的任何其他事情！）。

C代码中还有一个Trie比较函数：

int trie_cmp(const void* pa, const void* pb)
{
    const void* const* a = pa;
    const void* const* b = pb;

    return (*a > *b) - (*a < *b);
}

我已经转换如下：

public int CompareTo(Object obj)
        {
            Trie that = (Trie)obj;
            if (this == null && that == null)
                return 0;
            if (this == null) 
                return -1;
            if (that == null) 
                return +1;

            for (int n=0; n< 26; n++)
            {
                Trie t1 = this.next[n];
                Trie t2 = that.next[n];
                if (t1 == null && t2 == null)
                    continue;
                if (t1 == null)
                    return -1;
                if (t2 == null)
                    return +1;
                if (t1.end || t2.end) {
                    int foo = 1;        // debug point
                }
                return (t1.CompareTo(t2));
            }
            return 0;
        }

但是调试显示每个 Trie 引用都是 NULL（代码永远不会超出

if (t1 == null && t2 == null)  continue;

）

我确实尝试了商业 C++ 到 C# 转换器的免费版本，但没有帮助。

Answer 1

我从问题中了解到，算法不一定要在C#中逐行实现，而是比照。

由于实例 var

end

指示已到达单词的末尾，因此它将在 C# 中而不是类型

bool

而不是

int

.

假设类 Trie 中有方法封装了对内部的访问，也可以将此变量设为私有，并将名称适当调整为

_end

。

private bool _end;

这题主要关心的是定义一个树节点结构。该程序有一个节点数组，其中每个元素可以是

null

或指向下一个节点。目标是为由字母组成的字符串建立树状结构，例如 a-z。这需要一个包含 26 个节点的数组，每个位置对应字母表中的一个字符。这种方法可以识别常见的前缀，这对于自动完成等功能很有用。

单词数组的图形示例

new[]{"intranet","interstate","indecisive","intense"}

看起来像这样：

每个单词的结尾在图中都标有

*

。

可以在here.

中找到对尝试的一个很好的解释。

在 C 代码中，节点是动态分配的结构。然后将指向结构的指针放置在基于数组中字符的位置。在 C# 中，等效项是使用

new

关键字创建节点对象并将其分配给数组中的相应位置。注意：数组被初始化为

null

引用。

因此，Trie

next

数组可以这样声明：

private readonly Trie?[] _next = new Trie?[26];

方法

Insert

可以像这样递归地实现：

private void Insert(String p)
{
    if (string.IsNullOrEmpty(p))
    {
        _end = true;
        return;
    }

    var u = Index(p[0]);
    if (u < 26)
    {
        var t = _next[u] ??= new Trie();
        t.Insert(p[1..]);
    }
}

如果您更喜欢非递归变体，比如：

private void Insert(String p)
{
    var t = this;
    foreach (var c in p)
    {
        var u = Index(c);
        if (u < 26)
        {
            t = t._next[Index(c)] ??= new Trie();
        }
    }

    t._end = true;
}

为了完整起见，这里的构造函数：

private Trie()
{
}

public Trie(string[] data)
{
    foreach (var cc in data)
    {
        Insert(cc);
    }
}

你可以这样称呼它：

Trie trie = new Trie(new[]
{
    "intranet",
    "interstate",
    "indecisive",
    "intense"
});
//call some method on trie...