Data Structures and Algorithms in C
1.0.0
ここでは、Cに実装されているいくつかのデータ構造とアルゴリズムがあります。これらのアルゴリズムは、主にThomas H. Cormenによるアルゴリズムの概要に基づいています。
すべてのモジュールは、少なくとも1つのヘッダーファイル（.h）とコードコーパス（.c）を含む1つのソースファイルで構成されています。これらのモジュールのいずれかを使用するために、次の手順に従うことをお勧めします。
/modulesから必要なデータ構造またはアルゴリズムを見つけるList.c ）を含むモジュールディレクトリ（EG /modules/List ）をダウンロードします/include/ folderに移動し、必要なヘッダー（.h）ファイル（ List.hなど）を見つけてダウンロードします。#include "foo.h" ）。ほとんどのモジュールには、たとえばHashFunctionsやComparators 、または他のデータ構造などが含まれます。必要なものを見つけて、すべてのファイルをダウンロードします。#include "foo.h"へのパスを修正します。フォルダー全体をクローンすると、実行できます。
make ：それはすべてのモジュールを複雑にしますmake run-tests ：すべてのモジュールをコンパイルし、すべてのテストを実行するのはどれですかmake valgind-tests ：すべてのモジュールをコンパイルし、Valgrindを使用してすべてのテストを実行する| データ構造 | 意味 |
|---|---|
| ブルームフィルター | ブルームフィルターは、1970年にバートンハワードブルームによって考案された空間効率の確率的データ構造であり、要素がセットのメンバーであるかどうかをテストするために使用されます。偽陽性の一致は可能ですが、誤ったネガはそうではありません。つまり、クエリは「おそらくセットで」または「間違いなくセットではない」を返します。要素はセットに追加できますが、削除されません（ただし、これはカウントブルームフィルターバリアントで対処できます）。アイテムが追加すればするほど、誤検知の確率が大きくなります。 |
| 赤黒の木 | 赤ブラックツリーは、一種の自己バランスのとれたバイナリ検索ツリーです。各ノードは、「色」（「赤」または「黒」）を表す余分なビットを保存します。ツリーが変更されると、新しいツリーが再配置され、「塗り直され」、最悪の場合にツリーがどれほど不均衡になるかを制約する色付け特性を復元します。このプロパティは、この再配置とリクロッシングを効率的に実行できるように設計されています。再バランスは完全ではありませんが、 o（logn）時間で検索することを保証します。ここで、nはツリーのノードの数です。挿入および削除操作は、ツリーの再配置とリクロッシングとともに、 o（logn）時間で実行されます。 |
| リンクリスト | リンクリストは、メモリに物理的な配置によって順序が与えられないデータ要素の線形コレクションです。代わりに、各要素は次の要素を指します。これは、シーケンスを表すノードのコレクションで構成されるデータ構造です。 |
| 列 | 優先キューは、各要素がさらに「優先度」が関連付けられている通常のキューまたはスタックデータ構造に似た抽象データ型です。優先キューでは、優先度の高い要素が優先度の低い要素の前に提供されます。 |
| リスト付きハッシュテーブル | キーとチェーンを使用した非常に単純なハッシュテーブルの一般的な実装。再構成は提供されていません。 |
| 赤黒樹のハッシュテーブル | このように、すべての行に赤い黒の木へのポインターがあるテーブルで構成されていました。 |
| 赤黒樹にバケツを備えたハッシュテーブル | ハッシュテーブルは、赤い黒い木へのポインターのバケツで構成されていました |
| Maxheap | 最大ヒープは、各内部ノードの値がそのノードの子供の値以上の完全なバイナリツリーです。ヒープの要素を配列にマッピングすることは簡単です。ノードにインデックスKが保存されている場合、左の子供はインデックス2K+1に保存され、右子はインデックス2K+2に保存されます。 |
| 分離 | ユニオンファインドデータ構造またはマージファインドセットとも呼ばれるディスジョイントセットのデータ構造は、ディスジョイント（非重複）セットのコレクションを保存するデータ構造です。同等に、セットのパーティションを馬鹿げたサブセットに保存します。新しいセットを追加し、セットをマージ（組合に置き換える）、セットの代表的なメンバーを見つけるための操作を提供します。最後の操作により、2つの要素が同じセットまたは異なるセットにある場合、効率的に見つけることができます。 |
| スレッド付きのジョブスケジューラ | UNIX PTHREADSを使用したマルチスレッドジョブスケジューラー。 |
| アルゴリズム | 意味 |
|---|---|
| heapsort | Heapsortは、比較ベースのソートアルゴリズムです。 Heapsortは改善された選択ソートと考えることができます。選択のように、Heapsortはその入力をソートされた領域と未装備の領域に分割し、それから最大の要素を抽出し、ソートされた領域に挿入することにより、非セリット領域を繰り返し縮小します。選択のソートとは異なり、Heapsortは、留められていない領域の線形スキャンで時間を無駄にしません。むしろ、ヒープソートは、ヒープデータ構造内の未解決の領域を維持し、各ステップで最大の要素をより迅速に見つけます。 |
| QuickSort | QuickSortは効率的なソートアルゴリズムです。 1959年にイギリスのコンピューター科学者であるトニー・ホアアが開発し、1961年に公開されました。適切に実装すると、マージソートよりもやや高速になり、Heapsortよりも約2〜3倍高速になります。 |
| ユーティリティ | 意味 |
|---|---|
| コンパレータ | 2つの値を比較し、0、> 0、<0を返す関数 |
| ハッシュ関数 | 文字列ハッシュ関数 |
作成されたモジュールのテストには、ライブラリacutest.hを使用しました。
Acutest Libraryの詳細
すべてのモジュールに例を使用して、簡単なプログラム（メイン関数）を作成します。
myrto Iglezouと協力して、一部のモジュールが作成されています。 ☑☑️
©Konstantinos nikoletos | 2021
