プログラミング

このセクションでは、オープンアドレス法によるハッシュとは何かを説明します。オープンアドレッシングは、衝突を解決するためのもう1つの手法です。連鎖とは異なり、他のデータ構造に要素を挿入しません。データをハッシュテーブル自体に挿入します。ハッシュテーブルのサイズは、キーの数よりも大きくする必要があります。 オープンアドレッシング技術には、3つの異なる一般的な方法があります。これらのメソッドは-です 線形プロービング 二次プロービング ダブルハッシュ この手法では、他のハッシュ手法と同様にハッシュ関数を使用します。場所が空いている場合は、その場所に要素を挿入します。その場所

このセクションでは、オープンアドレッシングスキームでの線形プロービング手法とは何かを説明します。通常のハッシュ関数h´（x）：U→{0、1、。 。 。、m –1}。オープンアドレッシングスキームでは、実際のハッシュ関数h（x）は通常のハッシュ関数h’（x）を取り、それに別の部分を付加して1つの線形方程式を作成します。 h´（𝑥）=𝑥𝑚𝑜𝑑𝑚 ℎ（𝑥、𝑖）=（ℎ´（𝑥）+𝑖）𝑚𝑜𝑑𝑚 i|の値=0、1 、。 。 。、m – 1.したがって、i =0から開始し、1つの空き領域が得られるまでこれを増やします。したがって、最初にi =0の場合、h（x、i）はh´（x）

このセクションでは、オープンアドレッシングスキームにおける2次プロービング手法とは何かを説明します。通常のハッシュ関数h’（x）：U→{0、1、。 。 。、m –1}。オープンアドレッシングスキームでは、実際のハッシュ関数h（x）は通常のハッシュ関数h’（x）を取り、それに別の部分を付加して1つの2次方程式を作成します。 h´=（𝑥）=𝑥𝑚𝑜𝑑𝑚 ℎ（𝑥、𝑖）=（ℎ´（𝑥）+𝑖 2 ）𝑚𝑜𝑑𝑚 いくつかの定数を使用して、他の2次方程式を置くこともできます iの値=0、1 、。 。 。、m – 1.したがって、i =0から開始し、空き領域が1つになるまでこれ

このセクションでは、オープンアドレッシングスキームでのダブルハッシュ手法とは何かを説明します。通常のハッシュ関数h´（x）：U→{0、1、。 。 。、m –1}。オープンアドレッシングスキームでは、実際のハッシュ関数h（x）は、スペースが空でないときに通常のハッシュ関数h’（x）を使用し、別のハッシュ関数を実行してスペースを挿入します。 $$ h_ {1}（x）=x \：mod \：m $$ $$ h_ {2}（x）=x \：mod \：m ^ {\ prime} $$ $$ h（x、i）=（h ^ {1}（x）+ ih ^ {2}）\：mod \：m $$ iの値=0、1 、。

このセクションでは、オープンアドレスハッシュに関連するブレント法とは何かを説明します。この方法はヒューリスティックです。これにより、ハッシュテーブルでの検索が成功するまでの平均時間が最小限に抑えられます。 この方法は元々ダブルハッシュ手法に適用されていましたが、線形および二次プロービングなどのオープンアドレッシング手法に使用できます。要素xの経過時間は、オープンアドレス法のハッシュテーブルに格納され、最小値iであり、xはA [x iに配置されます。 ] ブレント法は、すべての要素の合計年齢を最小化しようとします。要素xを挿入すると、いくつかの手順が実行されます-A [x iのようなiの

ここでは、平衡二分探索木とは何かを確認します。二分探索木（BST）は二分木であり、左の子では要素が少なく、右の子では要素が大きくなります。 BSTで要素を検索するための平均時間計算量はO（log n）です。二分探索木の高さに依存します。二分探索木の特性を維持するために、木が歪むことがあります。したがって、歪んだ木は次のようになります- これは実際にはツリーですが、リンクリストのように見えます。この種の木の場合、検索時間はO（n）になります。これは二分木には効果的ではありません。 これらの問題を克服するために、高さのバランスが取れたツリーを作成できます。したがって、木は殺されません。

このセクションでは、非対称ハッシュ手法とは何かを説明します。この手法では、ハッシュテーブルはd個のブロックに分割されます。各分割の長さはn/dです。プローブ値xi、0≤i≤dは、$$ \ lbrace \ frac {i * n} {d}、...、\ frac {（i + 1）*n}{d-1}から均一に描画されます。 \rbrace$$。多肢選択式ハッシュと同様に、xを挿入するために、アルゴリズムはリストA [x 0の長さをチェックします。 ]、A [x 1 ]、。 。 。、A [x d – 1 ]。次に、これらのリストの最短にxを追加します。同点の場合は、インデックスが最小のリスト

このセクションでは、LCFSハッシュとは何かを説明します。これはオープンアドレッシング戦略の1つであり、衝突解決戦略を変更します。オープンアドレススキームでのハッシュのアルゴリズムを確認すると、2つの要素が衝突すると、優先度の高い要素がテーブルに挿入され、後続の要素が先に進む必要があることがわかります。したがって、オープンアドレッシングスキームのハッシュはFCFS基準であることがわかります。 LCFS（ラストカムファーストサーブ）スキームを使用。タスクはまったく逆の方法で実行されます。 1つの要素を挿入すると、その要素はx 0の位置に配置されます。 。 y j であるため、その場所がすで

グラフは1つの非線形データ構造であることがわかっています。このデータ構造では、いくつかの値をノードに入れ、ノードは異なるエッジを介して接続されています。データをグラフ構造に保存できるため、グラフから要素を検索して使用する必要もあります。 グラフで検索するには、2つの異なる方法があります。幅優先探索と深さ優先探索の手法。 幅優先探索（BFS） 幅優先探索（BFS）トラバーサルはアルゴリズムであり、特定のグラフのすべてのノードにアクセスするために使用されます。このトラバーサルアルゴリズムでは、1つのノードが選択され、隣接するすべてのノードが1つずつ訪問されます。隣接するすべての頂点を完了すると

グラフの深さ優先探索も同様です。しかし、有向グラフまたは有向グラフの場合、いくつかのタイプのエッジを見つけることができます。 DFSアルゴリズムは、DFSツリーと呼ばれるツリーを形成します。 -と呼ばれるエッジには4つのタイプがあります ツリーエッジ（T） −DFSツリーに存在するエッジ フォワードエッジ（F） −ツリーエッジのセットに平行。 （小さいDFS番号から大きいDFS番号へ、大きいDFS完了番号から小さいDFS完了番号へ） バックワードエッジ（B） −大きいDFS番号から小さいDFS番号へ、小さいDFS完了番号から大きいDFS完了番号へ。 クロスエッジ（C）

このセクションでは、オイラーグラフとハミルトングラフを表示します。しかし、それに飛び込む前に、最初にグラフの軌跡が何であるかを確認する必要があります。以下のようなグラフが1つあるとします- トレイルはパスであり、エッジ（v1、v2）、（v2、v3）、…、（vk-1、vk）のシーケンスであり、すべての頂点（v1、v2、…、vk）が区別されない場合があります。 、ただし、すべてのエッジが異なります。この例では、1つのトレイルは{（B、A）、（A、C）、（C、D）、（D、A）、（A、F）}です。これはトレイルです。ただし、頂点Aが2回アクセスされるため、これは単純なパスとは見なされません。最

二項ヒープは、二項ツリーのコレクションです。二項ツリーBkは、再帰的に定義された順序付きツリーです。二項ツリーB0は、単一のノードで構成されています。 二項ツリーBkは、2つの二項ツリーBk-1で構成されます。それは一緒にリンクされています。一方のルートは、もう一方のルートの左端の子です いくつかの二項ヒープは以下のようなものです- 二項ツリーのいくつかのプロパティは次のとおりです- B kの二項ツリー 2 kがあります ノード。 木の高さはkです 0からkの範囲のすべてのiについて、深さiに正確に$$ \ left（\ begin {array} {c

二項ヒープと同様に、フィボナッチヒープは木のコレクションです。それらは大まかに二項ヒープに基づいています。二項ヒープ内のツリーとは異なり、フィボナッチヒープ内のツリーはルート化されていますが、順序付けされていません。 フィボナッチヒープの各ノードxには、その親へのポインターp [x]と、その子のいずれかへのポインターchild[x]が含まれています。 xの子は、xの子リストと呼ばれる循環二重リンクリストでリンクされます。子リスト内の各子yには、それぞれyの左と右の兄弟を指すポインターleft[y]とright[y]があります。ノードyが一人っ子の場合、left [y] =right [y]=

ここでは、バイナリ最大ヒープデータ構造から要素を挿入する方法を説明します。最初のツリーが次のようになっていると仮定します- 挿入アルゴリズム insert(heap, n, item) − Begin    if heap is full, then exit    else       n := n + 1       for i := n, i > 1, set i := i / 2 in each iteration, do      

ここでは、バイナリ最大ヒープデータ構造から要素を削除する方法を説明します。最初のツリーが次のようになっていると仮定します- 削除アルゴリズム delete(heap, n) − Begin    if heap is empty, then exit    else       item := heap[1]       last := heap[n]       n := n – 1       for

ここでは、整数キーを使用したハッシュテーブルについて説明します。ここで、キー値𝑥はユニバース𝑈から取得され、𝑈={0、1、…、𝑢– 2、𝑢–1}となります。ハッシュ関数はℎです。このハッシュ関数の定義域は𝑈です。範囲は、セット{0、1、…、𝑚– 1}、および𝑚≤𝑢にあります。 ハッシュ関数hは、すべての𝑥∈𝑆に対してℎ（𝑥）が一意である場合、集合の完全なハッシュ関数であると言われます𝑆⊆𝑈。 𝑚=|𝑆|の場合、𝑆の完全なハッシュ関数ℎは最小になります。したがって、ℎはSと{0、1、…、𝑚–1}の間の全単射です。明らかに、最小の完全なハッシュ関数が望ましいです

ここでは、除算によるハッシュについて説明します。このために、ハッシュ関数-を使用します ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚 このハッシュ関数を使用するために、配列A [0、…m –1]を維持します。ここで、配列の各要素は、リンクリストの先頭へのポインターです。リンクリストLiは配列要素A[i]を指し、h（x）=iとなるすべての要素xを保持します。この手法は、連鎖によるハッシュとして知られています。 このようなハッシュテーブルで、要素xを増やしたい場合、これにはO（1）時間がかかります。インデックスi=h（x）を計算します。次に、リストLiにxを追加または追加します。要素を検索または削

ここでは、乗算法によるハッシュについて説明します。このために、ハッシュ関数-を使用します ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚 ここで、Aは実数値の定数です。この方法の利点は、mの値がそれほど重要ではないことです。 mを2の累乗としても取ることができます。 Aのどの値でもハッシュ関数が得られますが、Aの値の中には他の値よりも優れているものがあります。 Knuthによると、Aには黄金比を使用できるため、Aは $$ A =\ frac {\ sqrt5-1} {2} =0.61803398 $$ もちろん、Aにどの値を選択しても、鳩の巣原理は、

動的メモリ割り当てを使用して配列を作成する場合があります。動的メモリ割り当て手法を使用してアレイを割り当てる場合、いくつかの操作を実行することでアレイのサイズを2倍にすることができます。 初期配列サイズが5だったとします。 配列 0 1 2 3 4 要素1 要素2 要素3 要素4 要素5 配列を2倍にした後、サイズは- 0 1 2 3 4 5 6 7 8 9 要素1 要素2 要素3 要素4 要素5 要素6 要素7 要素8 要素

私たちが知っているように、配列は定義上同種です。したがって、同じタイプのデータを配列に配置する必要があります。しかし、異なるタイプのデータを保存したい場合、トリックは何でしょうか？古い言語のようなCでは、ユニオンを使用して、さまざまなタイプを1つのタイプに人為的に合体させることができます。次に、この新しいタイプで配列を定義できます。ここで、配列要素に実際に含まれるオブジェクトの種類は、タグによって決定されます。このような1つの構造を見てみましょう- struct Vehicle{    int id;    union {     &