0

私は現在、ここ（ウィキペディア）で説明されているアルゴリズムを実装しています。
この記事では、2つの主要な構造について説明しています。

  • エッジの配列を含むノード
  • ターゲットノードへのポインタとラベルを含むエッジ

したがって、現在、Cコードに2つの構造体がradix_node_sあります。radix_edge_s

typedef struct radix_node_s radix_node_t;

typedef struct radix_edge_s {
    radix_node_t                *target_node;
    char                        *label;

    SLIST_ENTRY(radix_edge_s)   next;
} radix_edge_t;

struct radix_node_s {
    SLIST_HEAD(radix_edge_list_s, radix_edge_s) edges;
    void                                        *data;
};

エッジ構造を非表示にして、その包含をターゲットノードとマージできるかどうか疑問に思いました。したがって、エッジラベルはノードの新しいフィールドになります。

これを行うのに良い方法でしょうか、それとも何かが恋しいですか？

4

1 に答える 1

1

エッジのラベルがソースノードまたはターゲットノードのラベルと同じである場合は、エッジ構造をノードへのポインタに変更するだけで、データを複製する必要はありません。

ただし、それがエッジの名前であり、ノードに異なる名前のエッジがある場合は、実際には、エッジのデータの「タプル」（ターゲットと名前）が必要です。そして、これをCで処理する最良の方法は、エッジ構造体を持つことです。

念のためこれを言うと、おそらくそれはすでにこのようになっています（何であるかはわかりませんSLIST_*）：構造体が小さいので、値型として使用する必要があります。つまり、エッジ構造体へのポインタの配列またはエッジ構造体のリンクリストを使用する代わりに、エッジ構造体の値の配列へのポインタを使用します。小さな構造体の配列のサイズを変更する必要がある場合でも、リンクリストやポインタの配列を介した余分な間接参照を維持するよりも、最新のプロセッサを使用した方がはるかに効率的です。

于 2012-12-10T09:16:19.307 に答える