3

リンクされたリストがある場合:

first node -----> second node ------> third node ---> ?

従来のリスト線形検索アルゴリズムを使用せずに、3 番目のノード値 (たとえば ) を表示できますか?

n番目のノードを取得する私の試み:

struct node* indexof( struct node* head, int i )
{
    int offset = (int)((char*)head->next - (char*)head);
    return ((struct node*)((char*)head + offset * i));
}
4

3 に答える 3

1

それはあなたの正確なリンクリストの実装に依存しますが、一般的には違います。n番目の要素にアクセスするには、リストをトラバースする必要があります。

これはリンクリストの特徴であり、配列または他のシーケンスのような構造へのオフセットを計算するために使用できる通常のトリックは機能しません。これは、個々のリスト要素がメモリ内に配置されることが保証されていないためです。賢明な方法であるためnext、3番目の要素を取得するためにポインタをたどることを余儀なくされます。

リンクリストへの一定時間のインデックス付きアクセスを提供する他のデータ構造を検討できます。

于 2012-11-05T18:59:51.893 に答える
1

間違ったデータ構造を選択したようです。n 番目に直接移動する場合は、配列を使用する必要があります。

それができなければ、直線的に進むことの何が悪いのでしょうか? パフォーマンスの問題を引き起こすには、非常に長いリンク リストで何度も呼び出す必要があります。

于 2012-11-05T19:24:36.980 に答える
0

リンクリストの目的の1つは、わずかなコストでノードを簡単に追加および削除できるようにすることです。

その機能を放棄してペイロードポインタの配列を使用することはできますが、リンクリストではなくなります（同じノードを算術増分で簡単に取得できる場合、次のノードへのポインタを使用する目的は何ですか？）。

例：

struct
{
    struct node *next;
    void *payload;
    ...
} node;

node *root = NULL;

ノードにスペースを割り当てない場合は、

typedef struct
{
    void *payload;
    ...
} node;
node *vector = NULL;
size_t vectorsize = 0;

そして、最初に必要な数のノードにスペースを割り当て、realloc必要に応じてリストを拡張するために使用しmemmove、削除されたノードを超えてノードをシフトバックすることによってノードを削除します。これにより、ノードを追加または削除するときに明らかにパフォーマンスが低下します。一方、n番目のノードはちょうどvector[n]です。

繰り返しますが、これはもはやリンクリストではありません。これが必要な場合は、リンクリストではなくポインタの配列を使用する方が適切な場合があります。

それは私に思い出させます、あなたはあなたが直接アドレス指定能力を必要とする理由を説明するのが良いでしょう（「問題を述べてください、解決策を実装する方法を尋ねないでください」）：それはあなたが必要とするのは配列でもないかもしれませんリンクリストでもありませんが、誰が知っているのでしょうか？おそらく、リングバッファ、スタック、丘、または二分木です。

一部の実装では、 2つの結合構造を展開することもできます。たとえば、特に最近挿入されたデータの多くの挿入と削除を伴う最初のフェーズで（二重に？）リンクリストを使用する場合があります。次に、ノード番号によって駆動される直接アドレス指定が必要な第2フェーズのポインター配列を作成して切り替えます（配列をリストノードアドレスの「キャッシュ」として使用します）。

for (listsize = 0, scan = root; scan; scan = scan->next)
    listsize++;
if (NULL == (vector = (node *)malloc(listsize * sizeof(node))))
{
    // out of memory
    return EXIT_FAILURE;
}
for (listsize = 0, scan = root; scan; scan = scan->next)
    vector[listsize++] = scan;
// Now vector[i]->payload is the payload of the i-th node
于 2012-11-05T19:20:30.813 に答える