2

C では、比較的大きくなる (数千項目) 短い文字列 (char*) のリストを格納する必要があります。
文字列は削除または挿入できますが、変更することはできません。順序は重要ではありません。
これを行うためのより効率的なデータ構造が何であるかはわかりません。
struct を使用できます：

struct node_s {
  char *str;
  node_s *next;
}

または char * の配列:

char **strings;

文字列に直接アクセスする必要はありません。別のデータ構造 (基数トライ) が文字列の一部のポインターを保持しているため、文字列が存在する必要があります。

4

6 に答える 6

2

初期化時にエントリの正確な数がわからない場合は、通常、配列を使用するよりも連結リストを使用する方が適切です。

配列は固定サイズです。エントリの数がわからず、配列を使用したい場合は、2 つのオプションがあります。必要となるものよりもはるかに大きな配列を割り当てるか、これは大量のメモリの浪費になります (また、合理的な上限がどうあるべきかを事前に知ることはしばしば困難です)。または、小さな配列から始めて、いっぱいになるまで待ちます。次に、新しいより大きな配列を割り当て、すべてのエントリを新しい配列にコピーし、古い配列の割り当てを解除します。これは、CPU サイクルの膨大な浪費です。

ただし、リンクされたリストを使用すると、動的に拡大および縮小できるため、その問題はありません。

ただし、さまざまな操作の実行時間の違いに注意してください。

配列では、インデックスによる要素の取得は非常に高速です。ただし、空のエントリを残さずに特定のインデックスを持つ要素を削除すると、後続のすべての要素を 1 つのインデックスだけ戻す必要があるため、非常にコストがかかります。既存のエントリを上書きせずに途中にエントリを挿入することは、後続のすべてを 1 つ前に移動する必要があるため、同様にコストがかかります。

リンクされたリストを使用すると、挿入されたノードとその先行ノード以外のノードに触れる必要がないため、途中のノードの削除または挿入は高速です (先行ノードが既にある場合)。ただし、この操作を実行する必要があるノードを見つけるには、前にあるすべてのノードを介してリンクをたどる必要があるため、コストがかかる可能性があります。

高速なルックアップと高速な挿入/削除の両方が必要な場合は、バイナリ ツリーを使用することをお勧めします。

于 2012-12-11T14:52:49.843 に答える
1

したがって、私が正しく理解していれば、文字列のリストはデータにアクセスする主要な方法ではなく、他のすべての古いデータをグラブすることなく解放する必要があるポインターの「クリーンアップリスト」にすぎません。

その場合、リンクされたリストを使用しますが、通常の方法ではありません。上記node_sでは、文字列ごとmallocに、構造体に対して1つ、文字列自体に対して1つ行う必要があります。

代わりに、次のような構造体を定義します。

struct string_list {
  struct string_list *next;
  char data[0];
};

長さゼロの配列は、構造体のスペースを占有しませんが、取得できる型付きアドレスを提供します。次に、構造体と実際の文字列のメモリを malloc できます。

struct string_list *newstr = malloc (sizeof(struct string_list) + my_desired_size);

次に、データを に配置し、ポインタnewstr->dataをリンクします。next

newstr->next = list_head;
strcpy (newstr->data, my_data, my_desired_size);
list_head = newstr;

弦を離すときは、1本freeあれば十分です。ああ、もちろん、リンクを修正します。

于 2012-12-11T15:59:18.460 に答える
1

それはあなたがそれらをどうしたいかによります。

順序が重要でない場合、ほとんどの操作は追加\削除になると思います。そうであれば、リスト データ構造 (最初のバリアント) を選択する必要があります。

要素への一定時間のアクセスが必要な場合は配列が適していますが、順序付けられていない配列では機能しません。文字列の検索には、リストのように O(n) 時間がかかります。

于 2012-12-11T14:50:40.887 に答える
1

それはあなたのプログラムに依存します。

文字列の数がわかっている場合。配列を使用することをお勧めします

文字列の数がわからない場合は、リンクされたリストを使用することをお勧めします

文字列が C で定数として定義される場合。次の方法で使用できます。

char *strings[1000] = {
  "string 0",
  "string 1",
  "string 2",
  "string 3",
   .
   .
   .
  "string 999"
}
于 2012-12-11T14:47:15.573 に答える
1

実際にchar **stringsは、単なる文字列の配列です。配列≠連結リスト。それならnode_s間違いなく解決策です。

于 2012-12-11T14:47:17.743 に答える
0

アイテム数が多く、アイテムの追加・削除を頻繁に行いたい場合や、ランダムアクセスO(log n)に近いアクセス時間を確保したい場合は、ハッシュテーブルを検討する必要があります。

リンクされたリストは、ノードに数千を追加するとアクセス時間が非常に遅くなり、配列は頻繁な追加/削除には適していません.

于 2012-12-11T15:41:08.027 に答える