CS- 5週目

データ構造の詳細な説明：アレイからツリー、そしてハッシュテーブルまで

この記事では、配列、リンクリスト、バイナリ検索ツリー（BST）、ハッシュテーブルなど、いくつかの一般的なデータ構造について説明し、メモリとその利点と短所で組織を説明します。

情報構造と抽象データ構造

情報構造とは、情報がメモリ内で編成される方法を指し、一方、抽象データ構造はこれらの構造の概念的な理解です。抽象データ構造を理解することで、実際にさまざまなデータ構造をよりよく実装することができます。

---

スタックとキュー

キューは、並んで待機するのと同様に、FIFO（最初の、最初のアウト）の原則に続く抽象的なデータ構造です。その主な操作には、エンキュー（キューのテールへの要素の追加）およびdequeuing（キューのヘッド要素の削除）が含まれます。

スタックは、プレートを積み重ねるように、LIFO（最初のアウトで最後に）原則に従います。その操作には、プッシュ（スタックの上部への要素の追加）およびポップ（スタックの上部要素の削除）が含まれます。

---

配列

配列は、メモリにデータを継続的に保存する構造です。以下の図に示すように、配列はメモリ内の連続ストレージスペースを占有します。

他のプログラム、関数、および変数は、メモリに存在する場合があり、以前に使用された冗長データが存在する場合があります。アレイに新しい要素を追加する必要がある場合は、メモリを再配置して配列全体をコピーする必要があります。これは非効率的です。

メモリを事前に割り当てるとコピー操作が減少する可能性がありますが、システムリソースを無駄にします。したがって、実際のニーズに応じてメモリを割り当てることが重要です。

---

リンクリスト

リンクされたリストは、異なるメモリ領域に配置された値をリストに連結し、動的な拡張または削減をサポートできる強力なデータ構造です。

各CS- 5週目には、データ値と次のCS- 5週目へのポインターの2つの値が含まれています。最後のCS- 5週目のポインター値はnullで、リンクリストの終了を示します。

C言語では、CS- 5週目は次のように定義できます。

 <code class="c">typedef struct node { int number; struct node *next; } node;</code>

次の例は、リンクリストを作成するプロセスを示しています。

リンクされたリストの欠点には、追加のメモリストレージポインターの必要性と、インデックスを介して要素に直接アクセスできないことが含まれます。

---

バイナリ検索ツリー（BST）

バイナリ検索ツリーは、データを効率的に保存、検索、取得するツリー構造です。

BSTの利点は動的および検索効率（O（log n））であり、不利な点は、ツリーが不均衡で追加のメモリストレージポインターが必要な場合、検索効率がO（n）に低下することです。

---

ハッシュテーブル

ハッシュテーブルは辞書に似ており、キー価値のペアが含まれています。ハッシュ関数を使用してキーを配列インデックスにマッピングするため、O（1）の平均ルックアップ時間を達成します。

ハッシュ競合（同じインデックスにマッピングされた複数のキー）は、リンクされたリストまたはその他のメソッドによって解決できます。ハッシュ関数の設計は、ハッシュテーブルのパフォーマンスにとって重要です。単純なハッシュ関数の例は次のとおりです。

 <code class="c">#include <ctype.h> unsigned int hash(const char *word) { return toupper(word[0]) - 'A'; }</ctype.h></code>

この記事は、CS50x 2024ソースコードに基づいてコンパイルされています。

以上がCS- 5週目の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。