Data-structures-algorithms-quick-guide

提供：Dev Guides
2020年7月1日 (水) 09:47時点におけるMaintenance script (トーク | 投稿記録)による版 (Imported from text file)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

データ構造とアルゴリズム-概要

データ構造は、効率的に使用するためにデータを体系化する体系的な方法です。 次の用語は、データ構造の基本用語です。

  • インターフェース-各データ構造にはインターフェースがあります。 インターフェイスは、データ構造がサポートする一連の操作を表します。 インターフェースは、サポートされる操作のリスト、それらが受け入れることができるパラメーターのタイプ、およびこれらの操作のタイプを返すだけです。
  • 実装-実装は、データ構造の内部表現を提供します。 実装では、データ構造の操作で使用されるアルゴリズムの定義も提供されます。

データ構造の特性

  • 修正-データ構造の実装は、そのインターフェイスを正しく実装する必要があります。
  • 時間の複雑さ-実行時間またはデータ構造の操作の実行時間はできるだけ短くする必要があります。
  • スペースの複雑さ-データ構造操作のメモリ使用量はできるだけ少なくする必要があります。

データ構造の必要性

アプリケーションが複雑になり、データが豊富になるにつれて、アプリケーションが現在直面している3つの一般的な問題があります。

  • データ検索-店舗の100万（10 ^ 6 ^）アイテムの在庫を考えます。 アプリケーションがアイテムを検索する場合、検索速度が低下するたびに100万（10 ^ 6 ^）アイテムのアイテムを検索する必要があります。 データが大きくなると、検索が遅くなります。
  • プロセッサの速度-プロセッサの速度は非常に高速ですが、データが10億レコードに達すると制限されます。
  • 複数のリクエスト-数千のユーザーがWebサーバーで同時にデータを検索できるため、高速サーバーでもデータの検索中に障害が発生します。

上記の問題を解決するために、データ構造が助けになります。 すべてのアイテムを検索する必要がないようにデータをデータ構造に編成でき、必要なデータをほぼ瞬時に検索できます。

実行時間のケース

通常、さまざまなデータ構造の実行時間を相対的に比較するために使用される3つのケースがあります。

  • 最悪のケース-これは、特定のデータ構造操作にかかる時間が最大になるシナリオです。 操作の最悪の場合の時間がƒ（n）である場合、この操作はƒ（n）時間以上かかりません。ここで、ƒ（n）はnの関数を表します。
  • 平均ケース-これは、データ構造の操作の平均実行時間を示すシナリオです。 操作の実行にƒ（n）時間かかる場合、m個の操作にはmƒ（n）時間かかります。
  • ベストケース-これは、データ構造の操作の実行時間を最短にするシナリオです。 操作の実行にƒ（n）時間かかる場合、実際の操作には、ƒ（n）として最大になる乱数として時間がかかる場合があります。

基本用語

  • データ-データは値または値のセットです。
  • データ項目-データ項目は単一の値の単位を指します。
  • グループ項目-サブ項目に分割されるデータ項目は、グループ項目と呼ばれます。
  • 基本項目-分割できないデータ項目は基本項目と呼ばれます。
  • 属性とエンティティ-エンティティとは、特定の属性またはプロパティを含むエンティティであり、値を割り当てることができます。
  • エンティティセット​​-同様の属性のエンティティがエンティティセットを形成します。
  • フィールド-フィールドは、エンティティの属性を表す情報の単一の基本単位です。
  • レコード-レコードは、特定のエンティティのフィールド値のコレクションです。
  • ファイル-ファイルは、特定のエンティティセット内のエンティティのレコードのコレクションです。

データ構造-環境設定

ローカル環境のセットアップ

Cプログラミング言語用に環境をセットアップする場合は、コンピューターで次の2つのツールを使用できる必要があります。（a）テキストエディターと（b）Cコンパイラ。

テキストエディタ

これは、プログラムの入力に使用されます。 いくつかのエディターの例には、Windows Notepad、OS Editコマンド、Brief、Epsilon、EMACS、vimまたはviが含まれます。

テキストエディタの名前とバージョンは、オペレーティングシステムによって異なる場合があります。 たとえば、Windowsではメモ帳が使用され、LinuxまたはUNIXと同様にWindowsでもvimまたはviを使用できます。

エディターで作成するファイルはソースファイルと呼ばれ、プログラムのソースコードが含まれています。 Cプログラムのソースファイルには通常、拡張子「 .c 」が付いています。

プログラミングを開始する前に、1つのテキストエディターを用意し、コンピュータープログラムを作成し、ファイルに保存し、コンパイルして、最後に実行する十分な経験があることを確認してください。

Cコンパイラ

ソースファイルに記述されたソースコードは、プログラムの人間が読めるソースです。 CPUが指定された命令に従って実際にプログラムを実行できるように、機械語に変換するには、「コンパイル」する必要があります。

このCプログラミング言語コンパイラは、ソースコードを最終的な実行可能プログラムにコンパイルするために使用されます。 プログラミング言語コンパイラに関する基本的な知識があることを前提としています。

最も頻繁に使用され、無料で利用できるコンパイラはGNU C/C＆plus;＆plus;です。コンパイラ。 それ以外の場合、それぞれのオペレーティングシステム（OS）があれば、HPまたはSolarisのコンパイラを使用できます。

次のセクションでは、GNU C/C＆plus;＆plus;のインストール方法について説明します。さまざまなOS上のコンパイラ。 C/C＆plus;＆plus;に言及しています。 GNU GCCコンパイラがCとC＆plus;＆plus;の両方で機能するためです。プログラミング言語。

UNIX/Linuxでのインストール

*LinuxまたはUNIX* を使用している場合は、コマンドラインから次のコマンドを入力して、GCCがシステムにインストールされているかどうかを確認します-
$ gcc -v

あなたのマシンにGNUコンパイラがインストールされている場合は、次のようなメッセージを出力するはずです- 

Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix =/usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)

GCCがインストールされていない場合は、https://gcc.gnu.org/install/にある詳細な手順を使用して自分でインストールする必要があります。

このチュートリアルはLinuxに基づいて作成されており、指定された例はすべてLinuxシステムのCent OSフレーバーでコンパイルされています。

Mac OSへのインストール

Mac OS Xを使用している場合、GCCを入手する最も簡単な方法は、AppleのWebサイトからXcode開発環境をダウンロードし、簡単なインストール手順に従うことです。 Xcodeのセットアップが完了したら、C/C＆plus;＆plus;のGNUコンパイラを使用できるようになります。

Xcodeは現在https://developer.apple.com/technologies/tools/[developer.apple.com/technologies/tools/]で入手できます。

Windowsへのインストール

GCCをWindowsにインストールするには、MinGWをインストールする必要があります。 MinGWをインストールするには、MinGWホームページhttp://www.mingw.org [www.mingw.org]にアクセスし、MinGWダウンロードページへのリンクをたどってください。 MinGW- <バージョン> .exeという名前のMinGWインストールプログラムの最新バージョンをダウンロードします。

MinWGのインストール中に、少なくともgcc-core、gcc-g＆plus;＆plus;、binutils、およびMinGWランタイムをインストールする必要がありますが、さらにインストールすることもできます。

MinGWインストールのbinサブディレクトリを PATH 環境変数に追加して、コマンドラインでこれらのツールを簡単な名前で指定できるようにします。

インストールが完了すると、gcc、g＆plus;＆plus;、ar、ranlib、dlltool、およびその他のいくつかのGNUツールをWindowsコマンドラインから実行できるようになります。

データ構造-アルゴリズムの基本

アルゴリズムは、目的の出力を取得するために特定の順序で実行される一連の命令を定義するステップバイステップの手順です。 アルゴリズムは通常、基礎となる言語とは無関係に作成されます。 アルゴリズムは複数のプログラミング言語で実装できます。

ビューのデータ構造の観点から、以下はアルゴリズムのいくつかの重要なカテゴリです-

  • 検索-データ構造内のアイテムを検索するアルゴリズム。
  • ソート-特定の順序でアイテムをソートするアルゴリズム。
  • 挿入-データ構造にアイテムを挿入するアルゴリズム。
  • 更新-データ構造内の既存のアイテムを更新するアルゴリズム。
  • 削除-データ構造から既存のアイテムを削除するアルゴリズム。

アルゴリズムの特性

すべての手順がアルゴリズムと呼ばれるわけではありません。 アルゴリズムは、次の特性を持つ必要があります-

  • 明確-アルゴリズムは明確で明確でなければなりません。 各ステップ（またはフェーズ）、およびそれらの入力/出力は明確である必要があり、1つの意味のみにつながる必要があります。
  • 入力-アルゴリズムには0以上の明確に定義された入力が必要です。
  • 出力-アルゴリズムには、1つ以上の明確に定義された出力があり、目的の出力と一致する必要があります。
  • 有限-アルゴリズムは有限数のステップの後に終了する必要があります。
  • 実現可能性-利用可能なリソースで実現可能でなければなりません。
  • 独立-アルゴリズムには、プログラミングコードに依存しない段階的な指示が必要です。

アルゴリズムの書き方

アルゴリズムを記述するための明確な標準はありません。 むしろ、問題とリソースに依存しています。 特定のプログラミングコードをサポートするためにアルゴリズムが記述されることはありません。

すべてのプログラミング言語は、ループ（do、for、while）、フロー制御（if-else）などの基本的なコード構造を共有していることがわかっています。 これらの一般的な構成体は、アルゴリズムを記述するために使用できます。

アルゴリズムを段階的に記述しますが、常にそうとは限りません。 アルゴリズムの記述はプロセスであり、問​​題ドメインが明確に定義された後に実行されます。 つまり、ソリューションを設計している問題領域を知る必要があります。

例

例を使用して、アルゴリズムの記述を学習してみましょう。

問題-2つの数値を追加して結果を表示するアルゴリズムを設計します。 

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

アルゴリズムは、プログラムのコーディング方法をプログラマに伝えます。 あるいは、アルゴリズムは次のように書くことができます- 

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a &plus; b
Step 4 − display c
Step 5 − STOP

アルゴリズムの設計と分析では、通常、アルゴリズムを記述するために2番目の方法が使用されます。 アナリストは、不要な定義をすべて無視して、アルゴリズムを簡単に分析できます。 彼は、どの操作が使用されているか、プロセスがどのように流れているかを観察できます。

  • ステップ番号*の記述はオプションです。

特定の問題の解決策を得るためのアルゴリズムを設計します。 問題は複数の方法で解決できます。

1つの問題、多くの解決策

したがって、特定の問題に対して多くの解決アルゴリズムを導き出すことができます。 次のステップでは、提案されたソリューションアルゴリズムを分析し、最適なソリューションを実装します。

アルゴリズム分析

アルゴリズムの効率は、実装前と実装後の2つの異なる段階で分析できます。 彼らは次のとおりです-

  • A Priori Analysis -これはアルゴリズムの理論的分析です。 アルゴリズムの効率は、プロセッサー速度などの他のすべての要因が一定であり、実装に影響を与えないと仮定して測定されます。
  • * _A事後分析*-これはアルゴリズムの経験的分析です。 選択したアルゴリズムは、プログラミング言語を使用して実装されます。 これは、ターゲットコンピューターマシンで実行されます。 この分析では、実行時間や必要なスペースなどの実際の統計が収集されます。

事前のアルゴリズム分析について学習します。 アルゴリズム分析は、関連するさまざまな操作の実行時間または実行時間を扱います。 操作の実行時間は、操作ごとに実行されるコンピューター命令の数として定義できます。

アルゴリズムの複雑さ

*X* がアルゴリズムであり、 *n* が入力データのサイズであり、アルゴリズムXで使用される時間とスペースが2つの主な要因であり、Xの効率を決定すると仮定します。
  • 時間係数-時間は、ソートアルゴリズムの比較などの主要な操作の数をカウントすることで測定されます。
  • スペース係数-スペースは、アルゴリズムに必要な最大メモリスペースをカウントすることにより測定されます。

アルゴリズムの複雑さ* f（n）は、入力データのサイズとしての *n に関して、アルゴリズムに必要な実行時間および/またはストレージスペースを与えます。

スペースの複雑さ

アルゴリズムのスペースの複雑さは、そのライフサイクルでアルゴリズムが必要とするメモリスペースの量を表します。 アルゴリズムに必要なスペースは、次の2つのコンポーネントの合計に等しいです-

  • 特定のデータと変数を保存するために必要なスペースであり、問​​題のサイズに依存しない固定部分。 たとえば、使用される単純な変数と定数、プログラムサイズなど。
  • 変数部分は、変数が必要とするスペースであり、そのサイズは問題のサイズに依存します。 たとえば、動的なメモリ割り当て、再帰スタックスペースなど。

任意のアルゴリズムPの空間複雑度S（P）は、S（P）= C＆plus;です。 SP（I）、ここでCは固定部分で、S（I）はインスタンス特性Iに依存するアルゴリズムの可変部分です。 以下は、概念を説明しようとする簡単な例です- 

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A &plus; B &plus; 10
Step 3 -  Stop

ここには、3つの変数A、B、Cと1つの定数があります。 したがって、S（P）= 1＆plus; 3。 現在、スペースは特定の変数のデータ型と定数型に依存し、それに応じて乗算されます。

時間の複雑さ

アルゴリズムの時間の複雑さは、アルゴリズムが完了するまでに実行するのに必要な時間を表します。 時間要件は数値関数T（n）として定義できます。各ステップが一定の時間を消費する場合、T（n）はステップ数として測定できます。

たとえば、2つのnビット整数の加算には、 n ステップかかります。 したがって、合計計算時間はT（n）= c ∗ nです。ここで、cは2ビットの加算にかかる時間です。 ここで、入力サイズが増加するにつれてT（n）が線形に増加することがわかります。

データ構造-漸近解析

アルゴリズムの漸近解析とは、実行時のパフォーマンスの数学的境界/フレーミングを定義することです。 漸近解析を使用して、アルゴリズムのベストケース、平均ケース、最悪ケースのシナリオを非常によく結論付けることができます。

漸近解析は入力境界です。つまり、アルゴリズムへの入力がない場合、一定時間で機能すると結論付けられます。 「入力」以外のすべての要因は一定と見なされます。

漸近解析とは、計算の数学的単位で任意の操作の実行時間を計算することです。 たとえば、ある操作の実行時間は_f_（n）として計算され、別の操作の実行時間は_g_（n ^ 2 ^）として計算される場合があります。 これは、 n の増加に伴い最初の操作の実行時間が線形に増加し、 n が増加すると2番目の操作の実行時間が指数関数的に増加することを意味します。 同様に、 n が非常に小さい場合、両方の操作の実行時間はほぼ同じになります。

通常、アルゴリズムに必要な時間は3種類に分類されます-

  • ベストケース-プログラムの実行に必要な最小時間。
  • 平均ケース-プログラムの実行に必要な平均時間。
  • 最悪のケース-プログラムの実行に必要な最大時間。

漸近記法

以下は、アルゴリズムの実行時間の複雑さを計算するために一般的に使用される漸近表記法です。

  • Ο表記
  • Ω表記
  • θ表記

Big Oh Notation、Ο

表記Ο（n）は、アルゴリズムの実行時間の上限を表す正式な方法です。 最悪の場合の時間の複雑さ、またはアルゴリズムが完了するまでにかかる可能性のある最長時間を測定します。

ビッグO表記

たとえば、関数* f（n）*の場合 

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

オメガ表記、Ω

表記Ω（n）は、アルゴリズムの実行時間の下限を表す正式な方法です。 これは、最適な時間の複雑さ、またはアルゴリズムが完了するまでにかかる可能性のある最適な時間を測定します。

オメガ表記

たとえば、関数* f（n）*の場合 

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

シータ表記、θ

表記法θ（n）は、アルゴリズムの実行時間の下限と上限の両方を表す正式な方法です。 次のように表されます-

シータ表記法 

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

一般的な漸近記法

以下は、いくつかの一般的な漸近表記法のリストです-

constant − Ο(1)
logarithmic − Ο(log n)
linear − Ο(n)
n log n − Ο(n log n)
quadratic − Ο(n2)
cubic − Ο(n3)
polynomial − nΟ(1)
exponential − 2Ο(n)

データ構造-貪欲なアルゴリズム

アルゴリズムは、特定の問題に対して最適なソリューションを実現するように設計されています。 貪欲なアルゴリズムアプローチでは、特定のソリューションドメインから決定が行われます。 貪欲であるため、最適なソリューションを提供すると思われる最も近いソリューションが選択されます。

貪欲なアルゴリズムは、ローカライズされた最適なソリューションを見つけようとしますが、最終的にはグローバルに最適化されたソリューションにつながる可能性があります。 ただし、一般的に貪欲なアルゴリズムは、グローバルに最適化されたソリューションを提供しません。

コインを数える

この問題は、可能な限り最小のコインを選択することにより、望ましい値にカウントすることであり、貪欲なアプローチは、アルゴリズムに可能な限り最大のコインを選択させる。 私たちが£1、2、5、および10のコインを提供され、£18を数えるように求められた場合、貪欲な手順は次のようになります-

  • 1 -£10コインを1つ選択します。残りのカウントは8です
  • 2 -その後、1つの£5コインを選択します。残りのカウントは3です
  • 3 -次に1つの£2コインを選択します。残りのカウントは1です
  • 4 -そして最後に、1コインを1枚選択すると問題が解決します

しかし、それはうまく機能しているように見えますが、このカウントのために私たちはたった4枚のコインを選ぶ必要があります。 ただし、問題をわずかに変更すると、同じアプローチでは同じ最適な結果が得られない場合があります。

値が1、7、10のコインがある通貨システムでは、値18のコインを数えることは絶対に最適ですが、15のようなカウントでは必要以上のコインを使用する可能性があります。 たとえば、貪欲なアプローチでは10＆plus;を使用します。 1＆plus; 1＆plus; 1＆plus; 1＆plus; 1、合計6コイン。 同じ問題は、3枚のコイン（7＆plus; 7＆plus; 1）を使用するだけで解決できますが、

したがって、貪欲なアプローチは即座に最適化されたソリューションを選択し、グローバルな最適化が主要な関心事である場合に失敗する可能性があると結論付けることができます。

例

ほとんどのネットワークアルゴリズムは、貪欲なアプローチを使用します。 ここにそれらのいくつかのリストがあります-

  • 巡回セールスマン問題
  • プリムの最小スパニングツリーアルゴリズム
  • クラスカルの最小スパニングツリーアルゴリズム
  • ダイクストラの最小スパニングツリーアルゴリズム
  • グラフ-地図の色付け
  • グラフ-頂点カバー
  • ナップザックの問題
  • ジョブスケジューリングの問題

貪欲なアプローチを使用して最適なソリューションを見つける同様の問題がたくさんあります。

データ構造-分割と征服

分割統治アプローチでは、手元の問題は小さな副問題に分割され、各問題は個別に解決されます。 サブ問題をさらに小さなサブ問題に分割し続けると、最終的には、それ以上分割できない段階に達する可能性があります。 それらの「アトミックな」最小のサブ問題（分数）は解決されます。 元の問題の解決策を得るために、すべての副問題の解決策が最終的にマージされます。

分割統治

概して、3段階のプロセスで「分割統治」アプローチを理解できます。

分割/分割

このステップでは、問題をより小さなサブ問題に分割します。 サブ問題は、元の問題の一部を表す必要があります。 このステップでは、一般に再帰的なアプローチを使用して、問題をさらに分割できるサブ問題がなくなるまで問題を分割します。 この段階では、サブ問題は本質的にアトミックになりますが、実際の問題の一部を表します。

征服/解決

このステップには、解決すべき小さな副次的な問題がたくさんあります。 一般に、このレベルでは、問題はそれ自体で「解決」されたと見なされます。

結合/結合

小さなサブ問題が解決されると、この段階では元の問題の解決策が定式化されるまで再帰的に結合されます。 このアルゴリズムのアプローチは再帰的に機能し、征服とマージのステップは非常に近いため、1つのように見えます。

例

次のコンピューターアルゴリズムは、*分割統治*プログラミングアプローチに基づいています-

  • ソートのマージ
  • クイックソート
  • バイナリ検索
  • Strassenの行列乗算
  • 最も近いペア（ポイント）

コンピューターの問題を解決する方法はさまざまありますが、言及されているのは、分割統治アプローチの良い例です。

データ構造-動的プログラミング

動的プログラミングのアプローチは、問題をより小さな、さらに小さな可能なサブ問題に分解する点で、分割して征服することに似ています。 しかし、分割して征服するのとは異なり、これらの副問題は独立して解決されません。 むしろ、これらの小さな副問題の結果は記憶され、類似または重複する副問題に使用されます。

動的プログラミングは、問題がある場合に使用されます。問題は同様のサブ問題に分けられ、その結果を再利用できます。 ほとんどの場合、これらのアルゴリズムは最適化に使用されます。 手持ちの副問題を解決する前に、動的アルゴリズムは以前に解決された副問題の結果を調べようとします。 最適なソリューションを実現するために、サブ問題のソリューションが組み合わされます。

だから我々はそれを言うことができます-

  • 問題は、より小さな重複する副問題に分割できる必要があります。
  • より小さいサブ問題の最適なソリューションを使用することにより、最適なソリューションを実現できます。
  • 動的アルゴリズムはメモ化を使用します。

比較

局所的な最適化に対処する貪欲なアルゴリズムとは対照的に、動的アルゴリズムは問題の全体的な最適化に動機付けられます。

ソリューションを組み合わせて全体的なソリューションを実現する分割統治アルゴリズムとは対照的に、動的アルゴリズムは小さなサブ問題の出力を使用してから、大きなサブ問題の最適化を試みます。 動的アルゴリズムは、メモ化を使用して、すでに解決された副問題の出力を記憶します。

例

次のコンピュータの問題は、動的プログラミングのアプローチを使用して解決することができます-

  • フィボナッチ数列
  • ナップザック問題
  • ハノイの塔
  • フロイド・ワーシャルによる全ペア最短経路
  • ダイクストラによる最短経路
  • プロジェクトのスケジューリング

動的プログラミングは、トップダウン方式とボトムアップ方式の両方で使用できます。 もちろん、ほとんどの場合、以前のソリューションの出力を参照する方が、CPUサイクルの観点から再計算するよりも安価です。

データ構造とアルゴリズムの基本概念

この章では、データ構造に関連する基本的な用語について説明します。

データ定義

データ定義は、次の特性を持つ特定のデータを定義します。

  • アトミック-定義は単一の概念を定義する必要があります。
  • Traceable -定義は、いくつかのデータ要素にマップできる必要があります。
  • 正確-定義は明確でなければなりません。
  • 明確かつ簡潔-定義は理解可能であるべきです。

データオブジェクト

データオブジェクトは、データを持つオブジェクトを表します。

データ・タイプ

データ型は、整数、文字列などのさまざまな種類のデータを分類する方法です。 これは、対応するタイプのデータで使用できる値、対応するタイプのデータで実行できる操作のタイプを決定します。 2つのデータタイプがあります-

  • 組み込みデータ型
  • 派生データ型

組み込みデータ型

言語に組み込みのサポートがあるデータ型は、組み込みデータ型と呼ばれます。 たとえば、ほとんどの言語は次の組み込みデータ型を提供します。

  • 整数
  • ブール値（true、false）
  • 浮動小数点（10進数）
  • 文字と文字列

派生データ型

いずれかの方法で実装できるため、実装に依存しないこれらのデータ型は、派生データ型と呼ばれます。 これらのデータ型は、通常、プライマリまたは組み込みのデータ型とそれらに関連付けられた操作の組み合わせによって構築されます。 たとえば-

  • List
  • アレイ
  • スタック
  • キュー

基本操作

データ構造内のデータは、特定の操作によって処理されます。 選択される特定のデータ構造は、データ構造に対して実行する必要がある操作の頻度に大きく依存します。

  • 横断
  • 検索中
  • 挿入
  • 削除
  • ソート
  • マージ

データ構造とアルゴリズム-配列

配列は、一定数のアイテムを保持できるコンテナであり、これらのアイテムは同じタイプである必要があります。 ほとんどのデータ構造は、配列を使用してアルゴリズムを実装します。 以下は、配列の概念を理解するための重要な用語です。

  • 要素-配列に格納されている各項目は要素と呼ばれます。
  • インデックス-配列内の要素の各位置には、要素を識別するために使用される数値インデックスがあります。

配列表現

配列は、さまざまな言語でさまざまな方法で宣言できます。 例として、C配列の宣言を見てみましょう。

配列宣言

配列は、さまざまな言語でさまざまな方法で宣言できます。 例として、C配列の宣言を見てみましょう。

配列表現

上記の図に従って、考慮すべき重要な点を次に示します。

  • インデックスは0で始まります。
  • 配列の長さは10です。つまり、10個の要素を格納できます。
  • 各要素には、そのインデックスを介してアクセスできます。 たとえば、インデックス6の要素を9としてフェッチできます。

基本操作

以下は、配列によってサポートされる基本的な操作です。

  • Traverse -すべての配列要素を1つずつ印刷します。
  • 挿入-指定されたインデックスに要素を追加します。
  • 削除-指定されたインデックスの要素を削除します。
  • 検索-指定されたインデックスを使用して、または値で要素を検索します。
  • Update -指定されたインデックスの要素を更新します。

Cでは、配列がサイズで初期化されると、次の順序で要素にデフォルト値が割り当てられます。

Data Type Default Value
bool false
char 0
int 0
float 0.0
double 0.0f
void
wchar_t 0

トラバース操作

この操作は、配列の要素をトラバースすることです。

例

次のプログラムは、配列の要素を走査して出力します。 

#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;
   printf("The original array elements are :\n");
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

上記のプログラムをコンパイルして実行すると、次の結果が生成されます-

出力

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8

挿入操作

挿入操作は、1つ以上のデータ要素を配列に挿入することです。 要件に基づいて、配列の先頭、末尾、または任意のインデックスに新しい要素を追加できます。

ここでは、配列の最後にデータを追加する挿入操作の実用的な実装を確認します-

例

以下は、上記のアルゴリズムの実装です- 

#include <stdio.h>

main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   n = n &plus; 1;

   while( j >= k) {
      LA[j&plus;1] = LA[j];
      j = j - 1;
   }

   LA[k] = item;

   printf("The array elements after insertion :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

上記のプログラムをコンパイルして実行すると、次の結果が生成されます-

出力

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8

配列挿入操作のその他のバリエーションリンク：/data_structures_algorithms/array_insertion_algorithm [ここをクリック]

削除操作

削除とは、配列から既存の要素を削除し、配列のすべての要素を再編成することです。

アルゴリズム

*LA* は *N* 要素の線形配列であり、 *K* は *K <= N* のような正の整数であると考えてください。 LAのK ^ th ^位置で使用可能な要素を削除するアルゴリズムは次のとおりです。
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J&plus;1
6. Set N = N-1
7. Stop

例

以下は、上記のアルゴリズムの実装です- 

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5;
   int i, j;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   j = k;

   while( j < n) {
      LA[j-1] = LA[j];
      j = j &plus; 1;
   }

   n = n -1;

   printf("The array elements after deletion :\n");

   for(i = 0; i<n; i&plus;&plus;) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

上記のプログラムをコンパイルして実行すると、次の結果が生成されます-

出力

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8

検索操作

値またはインデックスに基づいて配列要素の検索を実行できます。

アルゴリズム

*LA* は *N* 要素の線形配列であり、 *K* は *K <= N* のような正の整数であると考えてください。 以下は、順次検索を使用してITEMの値を持つ要素を見つけるアルゴリズムです。
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

例

以下は、上記のアルゴリズムの実装です- 

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int item = 5, n = 5;
   int i = 0, j = 0;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   while( j < n){
      if( LA[j] == item ) {
         break;
      }

      j = j + 1;
   }

   printf("Found element %d at position %d\n", item, j+1);
}

上記のプログラムをコンパイルして実行すると、次の結果が生成されます-

出力

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3

更新操作

更新操作とは、特定のインデックスで配列から既存の要素を更新することです。

アルゴリズム

*LA* は *N* 要素の線形配列であり、 *K* は *K <= N* のような正の整数であると考えてください。 以下は、LAのK ^ th ^位置で利用可能な要素を更新するアルゴリズムです。
1. Start
2. Set LA[K-1] = ITEM
3. Stop

例

以下は、上記のアルゴリズムの実装です- 

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5, item = 10;
   int i, j;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   LA[k-1] = item;

   printf("The array elements after updation :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

上記のプログラムをコンパイルして実行すると、次の結果が生成されます-

出力

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8

データ構造とアルゴリズム-リンクリスト

リンクリストは、データ構造のシーケンスであり、リンクを介して互いに接続されています。

リンクリストは、アイテムを含む一連のリンクです。 各リンクには、別のリンクへの接続が含まれています。 リンクリストは、配列の次によく使用されるデータ構造です。 以下は、リンクリストの概念を理解するための重要な用語です。

  • リンク-リンクリストの各リンクは、要素と呼ばれるデータを保存できます。
  • Next -リンクリストの各リンクには、Nextという次のリンクへのリンクが含まれています。
  • LinkedList -リンクリストには、Firstという最初のリンクへの接続リンクが含まれています。

リンクリストの表現

リンクリストは、すべてのノードが次のノードを指すノードのチェーンとして視覚化できます。

リンクリスト

上記の図に従って、考慮すべき重要な点を次に示します。

  • リンクリストには、最初に呼び出されるリンク要素が含まれています。
  • 各リンクには、データフィールドとnextというリンクフィールドがあります。
  • 各リンクは、次のリンクを使用して次のリンクにリンクされます。
  • 最後のリンクは、リストの終わりを示すためにリンクをヌルとして運びます。

リンクリストの種類

以下は、さまざまなタイプのリンクリストです。

  • シンプルリンクリスト-アイテムのナビゲーションは前方のみです。
  • 二重リンクリスト-アイテムは前後にナビゲートできます。
  • 循環リンクリスト-最後のアイテムには、次のように最初の要素のリンクが含まれ、最初の要素には前の最後の要素へのリンクがあります。

基本操作

リストでサポートされる基本的な操作は次のとおりです。

  • 挿入-リストの先頭に要素を追加します。
  • 削除-リストの先頭にある要素を削除します。
  • 表示-完全なリストを表示します。
  • 検索-指定されたキーを使用して要素を検索します。
  • 削除-指定されたキーを使用して要素を削除します。

挿入操作

リンクリストに新しいノードを追加することは、複数のステップアクティビティです。 ここで図でこれを学習します。 最初に、同じ構造を使用してノードを作成し、ノードを挿入する場所を見つけます。

リンクリスト挿入 

*A* （LeftNode）と *C* （RightNode）の間にノード *B* （NewNode）を挿入するとします。 次に、Cの横にあるB.
NewNode.next −> RightNode;

それはこのように見えるはずです-

リンクリスト挿入

これで、左側の次のノードが新しいノードを指すようになります。 

LeftNode.next −> NewNode;

リンクリスト挿入

これにより、2つの中央に新しいノードが配置されます。 新しいリストは次のようになります-

リンクリスト挿入

リストの先頭にノードを挿入する場合、同様の手順を実行する必要があります。 最後に挿入する間、リストの最後から2番目のノードは新しいノードを指し、新しいノードはNULLを指します。

削除操作

削除も複数のステップのプロセスです。 絵入りで学習します。 最初に、検索アルゴリズムを使用して、削除するターゲットノードを見つけます。

リンクリストの削除

ターゲットノードの左（前）ノードは、ターゲットノードの次のノードを指すようになります- 

LeftNode.next −> TargetNode.next;

リンクリストの削除

これにより、ターゲットノードを指していたリンクが削除されます。 ここで、次のコードを使用して、ターゲットノードが指しているものを削除します。 

TargetNode.next −> NULL;

リンクリストの削除

削除されたノードを使用する必要があります。 それをメモリに保持できます。そうしないと、メモリの割り当てを解除して、ターゲットノードを完全に消去できます。

リンクリストの削除

逆運転

この操作は徹底的なものです。 最後のノードをヘッドノードが指すようにし、リンクリスト全体を逆にする必要があります。

リンクリストの逆操作

まず、リストの最後まで移動します。 NULLを指している必要があります。 今、私たちはそれが前のノードを指すようにします-

リンクリストの逆操作

最後のノードが最後のノードではないことを確認する必要があります。 そのため、ヘッドノードが最後のノードを指しているように見える一時ノードがあります。 ここで、すべての左側のノードが以前のノードを1つずつ指すようにします。

リンクリストの逆操作

ヘッドノードが指すノード（最初のノード）を除いて、すべてのノードは前のノードを指し、それらを新しい後継ノードにする必要があります。 最初のノードはNULLを指します。

リンクリストの逆操作

一時ノードを使用して、ヘッドノードが新しい最初のノードを指すようにします。

リンクリストの逆操作

リンクされたリストが逆になりました。 Cプログラミング言語でのリンクリストの実装を確認するには、link：/data_structures_algorithms/linked_list_program_in_c [ここをクリック]をクリックしてください。

データ構造-二重リンクリスト

二重リンクリストは、リンクリストのバリエーションであり、単一リンクリストと比較して、前方向と後方向のどちらでも簡単にナビゲーションが可能です。 以下は、二重リンクリストの概念を理解するための重要な用語です。

  • リンク-リンクリストの各リンクは、要素と呼ばれるデータを保存できます。
  • Next -リンクリストの各リンクには、Nextという次のリンクへのリンクが含まれています。
  • Prev -リンクリストの各リンクには、Prevと呼ばれる前のリンクへのリンクが含まれています。
  • LinkedList -リンクリストには、Firstという最初のリンクとLastという最後のリンクへの接続リンクが含まれています。

二重リンクリスト表現

二重リンクリスト

上記の図に従って、考慮すべき重要な点を次に示します。

  • 二重リンクリストには、firstおよびlastというリンク要素が含まれています。
  • 各リンクには、データフィールドと、nextおよびprevと呼ばれる2つのリンクフィールドがあります。
  • 各リンクは、次のリンクを使用して次のリンクにリンクされます。
  • 各リンクは、前のリンクを使用して前のリンクにリンクされます。
  • 最後のリンクは、リストの終わりを示すためにリンクをヌルとして運びます。

基本操作

リストでサポートされる基本的な操作は次のとおりです。

  • 挿入-リストの先頭に要素を追加します。
  • 削除-リストの先頭にある要素を削除します。
  • 最後に挿入-リストの最後に要素を追加します。
  • Delete Last -リストの最後から要素を削除します。
  • 挿入後-リストの項目の後に要素を追加します。
  • 削除-キーを使用してリストから要素を削除します。
  • 前方表示-完全なリストを前方に表示します。
  • 後方に表示-完全なリストを後方に表示します。

挿入操作

次のコードは、二重リンクリストの先頭での挿入操作を示しています。

例

//insert link at the first location
void insertFirst(int key, int data) {

  //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;

   if(isEmpty()) {
     //make it the last link
      last = link;
   } else {
     //update first prev link
      head->prev = link;
   }

  //point it to old first link
   link->next = head;

  //point first to new first link
   head = link;
}

削除操作

次のコードは、二重リンクリストの先頭にある削除操作を示しています。

例

//delete first item
struct node *deleteFirst() {

  //save reference to first link
   struct node* tempLink = head;

  //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }

   head = head->next;

  //return the deleted link
   return tempLink;
}

操作の終了時の挿入

次のコードは、二重リンクリストの最後の位置での挿入操作を示しています。

例

//insert link at the last location
void insertLast(int key, int data) {

  //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;

   if(isEmpty()) {
     //make it the last link
      last = link;
   } else {
     //make link a new last link
      last->next = link;

     //mark old last node as prev of new link
      link->prev = last;
   }

  //point last to new last node
   last = link;
}

Cプログラミング言語での実装を確認するには、リンクしてください：/data_structures_algorithms/doubly_linked_list_program_in_c [ここをクリック]。

データ構造-循環リンクリスト

循環リンクリストは、最初の要素が最後の要素を指し、最後の要素が最初の要素を指すリンクリストのバリエーションです。 単一リンクリストと二重リンクリストの両方を循環リンクリストにすることができます。

循環としての単一リンクリスト

単一リンクリストでは、最後のノードの次のポインターは最初のノードを指します。

循環リンクリストとしての単一リンクリスト

循環としての二重リンクリスト

二重リンクリストでは、最後のノードの次のポインターは最初のノードを指し、最初のノードの前のポインターは最後のノードを指し、両方向に循環します。

循環リンクリストとしての二重リンクリスト

上記の図に従って、考慮すべき重要な点を次に示します。

  • 最後のリンクの次は、単一リンクリストと二重リンクリストの両方の場合のリストの最初のリンクを指します。
  • 二重にリンクされたリストの場合、最初のリンクの前のポイントはリストの最後を指します。

基本操作

以下は、循環リストでサポートされる重要な操作です。

  • 挿入-リストの先頭に要素を挿入します。
  • delete -リストの先頭から要素を削除します。
  • display -リストを表示します。

挿入操作

次のコードは、単一のリンクリストに基づく循環リンクリストへの挿入操作を示しています。

例

insertFirst(data):
Begin
   create a new node
   node -> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

削除操作

次のコードは、単一のリンクリストに基づく循環リンクリストでの削除操作を示しています。 

deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

リスト表示操作

次のコードは、循環リンクリストでのリスト表示操作を示しています。 

display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End

Cプログラミング言語での実装については、リンクしてください：/data_structures_algorithms/circular_linked_list_program_in_c [ここをクリック]。

データ構造とアルゴリズム-スタック

スタックは、ほとんどのプログラミング言語で一般的に使用される抽象データ型（ADT）です。 それは、実世界のスタックのように動作するため、スタックと呼ばれます。たとえば、カードのデッキやプレートの山などです。

スタックの例

実際のスタックでは、片側のみで操作が可能です。 たとえば、スタックの上部からのみカードまたはプレートを配置または削除できます。 同様に、スタックADTでは、すべてのデータ操作を一方の端でのみ許可します。 常に、スタックの最上位要素にのみアクセスできます。

この機能により、LIFOデータ構造になります。 LIFOは後入れ先出しの略です。 ここでは、最後に配置（挿入または追加）された要素が最初にアクセスされます。 スタックの用語では、挿入操作は PUSH 操作と呼ばれ、削除操作は POP 操作と呼ばれます。

スタック表現

次の図は、スタックとその操作を示しています-

スタック表現

スタックは、配列、構造、ポインター、およびリンクリストによって実装できます。 スタックは固定サイズにすることも、動的にサイズ変更することもできます。 ここでは、配列を使用してスタックを実装します。これにより、固定サイズのスタック実装になります。

基本操作

スタック操作には、スタックの初期化、使用、および初期化解除が含まれます。 これらの基本的なものとは別に、スタックは次の2つの主要な操作に使用されます-

  • * push（）*-スタック上の要素をプッシュ（保存）します。
  • * pop（）*-スタックから要素を削除（アクセス）します。

データがスタックにプッシュされたとき。

スタックを効率的に使用するには、スタックのステータスも確認する必要があります。 同じ目的で、次の機能がスタックに追加されます-

  • * peek（）*-スタックの最上位データ要素を削除せずに取得します。
  • * isFull（）*-スタックがいっぱいかどうかを確認します。
  • * isEmpty（）*-スタックが空かどうかを確認します。

常に、スタック上の最後のプッシュされたデータへのポインターを維持します。 このポインターは常にスタックの最上部を表すため、 top という名前が付けられます。 top ポインターは、実際にスタックを削除することなく、スタックの最高値を提供します。

まず、スタック機能をサポートする手順について学ぶ必要があります-

ピーク（）

peek（）関数のアルゴリズム- 

begin procedure peek
   return stack[top]
end procedure

Cプログラミング言語でのpeek（）関数の実装-

例 

int peek() {
   return stack[top];
}

一杯（）

isfull（）関数のアルゴリズム- 

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif

end procedure

Cプログラミング言語でのisfull（）関数の実装-

例 

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

isempty（）

isempty（）関数のアルゴリズム- 

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif

end procedure

Cプログラミング言語でのisempty（）関数の実装はわずかに異なります。 配列のインデックスは0から始まるため、topを-1で初期化します。 そのため、スタックが空かどうかを判断するために、トップが0または-1未満かどうかを確認します。 ここにコードがあります-

例 

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

プッシュ操作

新しいデータ要素をスタックに配置するプロセスは、プッシュ操作と呼ばれます。 プッシュ操作には、一連のステップが含まれます-

  • *ステップ1 *-スタックがいっぱいかどうかを確認します。
  • *ステップ2 *-スタックがいっぱいの場合、エラーを生成して終了します。
  • ステップ3 *-スタックが満杯でない場合、 *top をインクリメントして次の空きスペースを指します。
  • *ステップ4 *-topが指しているスタック位置にデータ要素を追加します。
  • *ステップ5 *-成功を返します。

スタックプッシュ操作

リンクリストを使用してスタックを実装する場合は、手順3でスペースを動的に割り当てる必要があります。

PUSH操作のアルゴリズム

プッシュ操作の簡単なアルゴリズムは、次のように導出することができます- 

begin procedure push: stack, data

   if stack is full
      return null
   endif

   top ← top + 1
   stack[top] ← data

end procedure

Cでのこのアルゴリズムの実装は非常に簡単です。 次のコードを参照してください-

例 

void push(int data) {
   if(!isFull()) {
      top = top &plus; 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

ポップ操作

スタックからコンテンツを削除しながらコンテンツにアクセスすることを、ポップ操作と呼びます。 pop（）操作の配列実装では、データ要素は実際には削除されず、代わりに top がスタック内の下位位置までデクリメントされ、次の値を指します。 しかし、リンクリストの実装では、pop（）は実際にデータ要素を削除し、メモリ空間の割り当てを解除します。

ポップ操作には、次の手順が含まれる場合があります-

  • *ステップ1 *-スタックが空かどうかを確認します。
  • *ステップ2 *-スタックが空の場合、エラーを生成して終了します。
  • ステップ3 *-スタックが空でない場合、 *top が指しているデータ要素にアクセスします。
  • *ステップ4 *-topの値を1減らします。
  • *ステップ5 *-成功を返します。

スタックポップ操作

ポップ操作のアルゴリズム

ポップ操作の簡単なアルゴリズムは、次のように導出することができます- 

begin procedure pop: stack

   if stack is empty
      return null
   endif

   data ← stack[top]
   top ← top - 1
   return data

end procedure

Cでのこのアルゴリズムの実装は、次のとおりです-

例 

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Cプログラミング言語の完全なスタックプログラムについては、リンクしてください：/data_structures_algorithms/stack_program_in_c [ここをクリック]。

データ構造-式の解析

算術式を記述する方法は、*表記法*と呼ばれます。 算術式は、3つの異なるが同等の表記法で、つまり式の本質や出力を変更せずに記述できます。 これらの表記法は-

  • 中置記法
  • プレフィックス（ポーランド語）表記
  • 後置（逆ポーランド）表記

これらの表記は、式で演算子を使用する方法として名前が付けられています。 この章でも同じことを学びます。

中置記法

式を infix 表記で記述します。 a-b＆plus; c、オペランド間で演算子が使用されます。 私たち人間は中置記法で読み、書き、話すことは簡単ですが、同じことがコンピューティングデバイスにはうまくいきません。 中置記法を処理するアルゴリズムは、時間とスペースの消費の観点から困難でコストがかかる可能性があります。

プレフィックス表記

この表記では、演算子はオペランドに接頭辞が付けられています。 演算子はオペランドの前に記述されます。 たとえば、＆plus; ab *。 これは、中置表記 *a＆plus;と同じです。 b 。 プレフィックス表記は、*ポーランド表記*とも呼ばれます。

後置記法

この表記スタイルは*逆ポーランド表記*として知られています。 この表記スタイルでは、演算子はオペランドに後置されます。つまり、演算子はオペランドの後に記述されます。 たとえば、 ab＆plus; 。 これは、中置表記 a＆plus;と同じです。 b 。

次の表では、3つの表記すべての違いを簡単に示します-

Sr.No. Infix Notation Prefix Notation Postfix Notation
1 a PLUS b PLUS a b a b PLUS
2 (a PLUS b) ∗ c ∗ PLUS a b c a b PLUS c ∗
3 a ∗ (b PLUS c) ∗ a PLUS b c a b c PLUS ∗
4 a/b PLUS c/d PLUS/a b/c d a b/c d/PLUS
5 (a PLUS b) ∗ (c PLUS d) ∗ PLUS a b PLUS c d a b PLUS c d PLUS ∗
6 ((a PLUS b) ∗ c) - d - ∗ PLUS a b c d a b PLUS c ∗ d -

式の解析

すでに説明したように、中置表記法を解析するためのアルゴリズムまたはプログラムを設計するのは非常に効率的な方法ではありません。 代わりに、これらのインフィックス表記法は、最初にポストフィックスまたはプレフィックス表記法に変換されてから計算されます。

算術式を解析するには、演算子の優先順位と結合性にも注意する必要があります。

優先順位

オペランドが2つの異なる演算子の間にある場合、どちらの演算子が最初にオペランドを取るかは、演算子の優先順位によって決定されます。 たとえば-

演算子の優先順位

乗算演算は加算よりも優先されるため、b * cが最初に評価されます。 演算子の優先順位の表は後で提供されます。

連想性

結合性は、同じ優先順位を持つ演算子が式に現れるルールを記述します。 たとえば、式で＆plus; b-c、両方＆plus;および–同じ優先順位を持ち、式のどの部分が最初に評価されるかは、それらの演算子の結合性によって決まります。 ここでは、両方の＆plus;および-は連想式のままなので、式は*（a＆plus; b）-c *として評価されます。

優先順位と結合性は、式の評価の順序を決定します。 以下は、演算子の優先順位と結合性テーブル（最高から最低）です-

Sr.No. Operator Precedence Associativity
1 Exponentiation ^ Highest Right Associative
2 Multiplication ( ∗ ) & Division (/) Second Highest Left Associative
3 Addition ( PLUS ) & Subtraction ( − ) Lowest Left Associative

上記の表は、演算子のデフォルトの動作を示しています。 式評価の任意の時点で、括弧を使用して順序を変更できます。 たとえば- 

*a＆plus; b* c *、式部分 *b* * *c* が最初に評価され、乗算が加算よりも優先されます。 ここでは、 *a＆plus;に括弧を使用します。* （a＆plus; b） *c* のように、最初に評価されるb *。

後置評価アルゴリズム

ここで、後置記法の評価方法に関するアルゴリズムを見てみましょう- 

Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation

Cプログラミング言語での実装を確認するには、リンク：/data_structures_algorithms/expression_parsing_using_statck [ここをクリック]をクリックしてください。

データ構造とアルゴリズム-キュー

キューは抽象的なデータ構造で、Stacksに多少似ています。 スタックとは異なり、キューは両端で開いています。 一方の端は常にデータの挿入（エンキュー）に使用され、もう一方の端はデータの削除（デキュー）に使用されます。 キューは先入れ先出し法に従います。つまり、最初に保存されたデータ項目が最初にアクセスされます。

キューの例

キューの実際の例は、車線が最初に出て最初に出る単一車線の片道です。 より現実的な例は、チケットの窓口やバス停の待ち行列として見ることができます。

キュー表現

現在、キューでそれを理解しているので、さまざまな理由で両端にアクセスします。 以下に示す次の図は、キュー構造をデータ構造として説明しようとしています-

キューの例

スタックと同様に、キューは配列、リンクリスト、ポインター、および構造体を使用して実装することもできます。 簡単にするために、1次元配列を使用してキューを実装します。

基本操作

キュー操作には、キューの初期化または定義、キューの使用、メモリからの完全消去が含まれます。 ここでは、キューに関連付けられている基本的な操作を理解しようとします-

  • * enqueue（）*-アイテムをキューに追加（保存）します。
  • * dequeue（）*-キューからアイテムを削除（アクセス）します。

上記のキュー操作を効率的にするには、さらに多くの機能が必要です。 これらは-

  • * peek（）*-キューの先頭にある要素を削除せずに取得します。
  • * isfull（）*-キューがいっぱいかどうかを確認します。
  • * isempty（）*-キューが空かどうかを確認します。

キューでは、常に front ポインターが指すデータをデキュー（またはアクセス）し、キューにデータをキュー（または格納）する際に rear ポインターを使用します。

最初にキューのサポート機能について学びましょう-

ピーク（）

この関数は、キューの*先頭*にあるデータを確認するのに役立ちます。 peek（）関数のアルゴリズムは次のとおりです-

アルゴリズム 

begin procedure peek
   return queue[front]
end procedure

Cプログラミング言語でのpeek（）関数の実装-

例 

int peek() {
   return queue[front];
}

一杯（）

1次元配列を使用してキューを実装しているため、後方のポインターがMAXSIZEに到達するようにチェックして、キューがいっぱいであることを判断します。 循環リンクリストでキューを維持する場合、アルゴリズムは異なります。 isfull（）関数のアルゴリズム-

アルゴリズム 

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif

end procedure

Cプログラミング言語でのisfull（）関数の実装-

例 

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

isempty（）

isempty（）関数のアルゴリズム-

アルゴリズム 

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif

end procedure
*front* の値がMINまたは0より小さい場合、キューはまだ初期化されていないため、空であることを示します。

ここにCプログラミングコードがあります-

例 

bool isempty() {
   if(front < 0 || front > rear)
      return true;
   else
      return false;
}

エンキュー操作

キューは、 front と rear の2つのデータポインターを保持します。 したがって、その操作は、スタックの操作よりも実装が比較的困難です。

キューにデータをエンキュー（挿入）するには、次の手順を実行する必要があります-

  • *ステップ1 *-キューがいっぱいかどうかを確認します。
  • *ステップ2 *-キューがいっぱいの場合、オーバーフローエラーを生成して終了します。
  • ステップ3 *-キューがいっぱいでない場合は、 *rear ポインターをインクリメントして、次の空のスペースを指します。
  • *ステップ4 *-後方が指しているキューの場所にデータ要素を追加します。
  • *ステップ5 *-成功を返します。

挿入操作

予期しない状況を処理するために、キューが初期化されているかどうかを確認することもあります。

エンキュー操作のアルゴリズム

procedure enqueue(data)

   if queue is full
      return overflow
   endif

   rear ← rear + 1
   queue[rear] ← data
   return true

end procedure

Cプログラミング言語でのenqueue（）の実装-

例 

int enqueue(int data)
   if(isfull())
      return 0;

   rear = rear &plus; 1;
   queue[rear] = data;

   return 1;
end procedure

デキュー操作

キューからのデータへのアクセスは、2つのタスクのプロセスです- front が指しているデータにアクセスし、アクセス後にデータを削除します。 *デキュー*操作を実行するには、次の手順が取られます-

  • *ステップ1 *-キューが空かどうかを確認します。
  • *ステップ2 *-キューが空の場合、アンダーフローエラーを生成して終了します。
  • ステップ3 *-キューが空でない場合、 *front が指しているデータにアクセスします。
  • ステップ4 *-次の利用可能なデータ要素を指すように *front ポインタをインクリメントします。
  • *ステップ5 *-成功を返します。

操作の削除

デキュー操作のアルゴリズム

procedure dequeue

   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Cプログラミング言語でのdequeue（）の実装-

例 

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Cプログラミング言語の完全なキュープログラムについては、リンクしてください：/data_structures_algorithms/queue_program_in_c [ここをクリック]。

データ構造とアルゴリズムの線形検索

線形検索は非常に単純な検索アルゴリズムです。 このタイプの検索では、すべてのアイテムを1つずつ順番に検索します。 すべてのアイテムがチェックされ、一致が見つかった場合、その特定のアイテムが返されます。それ以外の場合は、データ収集が終了するまで検索が続行されます。

線形検索アニメーション

アルゴリズム

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

疑似コード

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

Cプログラミング言語での線形検索の実装については、リンク：/data_structures_algorithms/linear_search_program_in_c [click-here]をご覧ください。

データ構造とアルゴリズムのバイナリ検索

バイナリ検索は、実行時の複雑さがΟ（log n）の高速検索アルゴリズムです。 この検索アルゴリズムは、分割統治の原則に基づいて機能します。 このアルゴリズムが適切に機能するためには、データ収集がソートされた形式である必要があります。

バイナリ検索は、コレクションの最も中央のアイテムを比較することにより、特定のアイテムを探します。 一致する場合、アイテムのインデックスが返されます。 中央のアイテムがアイテムよりも大きい場合、アイテムは中央のアイテムの左側のサブ配列で検索されます。 それ以外の場合、アイテムは中央のアイテムの右側のサブ配列で検索されます。 このプロセスは、サブアレイのサイズがゼロになるまでサブアレイでも継続されます。

バイナリ検索の仕組み

バイナリ検索を機能させるには、ターゲット配列を並べ替える必要があります。 絵の例を使用して、バイナリ検索のプロセスを学習します。 以下はソートされた配列であり、バイナリ検索を使用して値31の場所を検索する必要があると仮定しましょう。

バイナリ検索

まず、この式を使用して配列の半分を決定します- 

mid = low &plus; (high - low)/2

ここでは、0＆plus;です。 （9-0）/2 = 4（整数値4.5）。 したがって、4は配列の中央です。

バイナリ検索

ここで、ロケーション4に保存されている値と検索対象の値を比較します。 31. ロケーション4の値は27であり、一致していません。 値が27より大きく、ソートされた配列があるため、ターゲット値が配列の上部にある必要があることもわかります。

バイナリ検索

低から中にプラスを変更します。 1、新しい中間値を再度見つけます。 

low = mid &plus; 1
mid = low &plus; (high - low)/2

私たちの新しいミッドは今7です。 ロケーション7に格納されている値とターゲット値31を比較します。

バイナリ検索

場所7に格納されている値は一致ではなく、探している値以上のものです。 そのため、値はこの場所から下部になければなりません。

バイナリ検索

したがって、midを再度計算します。 今回は5です。

バイナリ検索

場所5に保存されている値を目標値と比較します。 一致することがわかりました。

バイナリ検索

ターゲット値31はロケーション5に格納されていると結論付けます。

バイナリ検索では、検索可能なアイテムが半分になるため、比較の数が非常に少なくなります。

疑似コード

バイナリ検索アルゴリズムの擬似コードは次のようになります- 

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n

   while x not found
      if upperBound < lowerBound
         EXIT: x does not exists.

      set midPoint = lowerBound &plus; ( upperBound - lowerBound )/2

      if A[midPoint] < x
         set lowerBound = midPoint &plus; 1

      if A[midPoint] > x
         set upperBound = midPoint - 1

      if A[midPoint] = x
         EXIT: x found at location midPoint
   end while

end procedure

Cプログラミング言語の配列を使用したバイナリ検索の実装については、リンク：/data_structures_algorithms/binary_search_program_in_c [ここをクリック]をご覧ください。

データ構造-内挿検索

補間検索は、バイナリ検索の改良版です。 この検索アルゴリズムは、必要な値の調査位置で機能します。 このアルゴリズムが適切に機能するためには、データ収集はソートされた形式で等しく分散されている必要があります。

バイナリ検索には、線形検索よりも時間の複雑さという大きな利点があります。 線形検索にはworst（n）の最悪の複雑さがありますが、バイナリ検索にはΟ（log n）があります。

ターゲットデータの場所が事前にわかっている場合があります。 たとえば、電話帳の場合、モルフィウスの電話番号を検索したい場合。 ここでは、「M」から始まる名前が保存されているメモリ空間に直接ジャンプできるため、線形検索やバイナリ検索さえも遅く見えるでしょう。

バイナリ検索での配置

バイナリ検索では、目的のデータが見つからない場合、リストの残りの部分は下位と上位の2つの部分に分割されます。 どちらかで検索が実行されます。

BSTステップ1 BSTステップ2 BSTステップ3 image:/data_msith bst_step_four.jpg [BSTステップ4]

データがソートされている場合でも、バイナリ検索は目的のデータの位置をプローブするのに利用されません。

内挿検索での位置探索

補間検索は、プローブの位置を計算することにより特定のアイテムを見つけます。 最初は、プローブの位置はコレクションの最も中央のアイテムの位置です。

補間ステップ1 補間ステップ2

一致した場合、アイテムのインデックスが返されます。 リストを2つの部分に分割するには、次の方法を使用します- 

mid = Lo &plus; ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

中央のアイテムがアイテムよりも大きい場合、プローブの位置は中央のアイテムの右側のサブアレイで再び計算されます。 それ以外の場合、アイテムは中央のアイテムの左側のサブ配列で検索されます。 このプロセスは、サブアレイのサイズがゼロになるまでサブアレイでも継続されます。

補間検索アルゴリズムの実行時の複雑さは、有利な状況でのBSTの*Ο（log n）*と比較して*Ο（log（log n））*です。

アルゴリズム

それは既存のBSTアルゴリズムの即興であるため、位置探査を使用して「ターゲット」データ値インデックスを検索する手順に言及しています- 

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

疑似コード

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match

      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if

      Set Mid = Lo + ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Cプログラミング言語での補間検索の実装については、リンク：/data_structures_algorithms/interpolation_search_in_c [ここをクリック]をクリックしてください。

データ構造とアルゴリズム-ハッシュテーブル

ハッシュテーブルは、データを連想的に格納するデータ構造です。 ハッシュテーブルでは、データは配列形式で格納され、各データ値には独自のインデックス値があります。 目的のデータのインデックスがわかれば、データへのアクセスは非常に高速になります。

したがって、データのサイズに関係なく、挿入および検索操作が非常に高速なデータ構造になります。 ハッシュテーブルは、記憶媒体として配列を使用し、ハッシュ手法を使用して、要素の挿入元または検索元のインデックスを生成します。

ハッシング

ハッシュは、キー値の範囲を配列のインデックスの範囲に変換する技術です。 モジュロ演算子を使用して、キー値の範囲を取得します。 サイズ20のハッシュテーブルの例を考えてみましょう。次のアイテムが格納されます。 アイテムは（キー、値）形式です。

ハッシュ関数

  • （1,20）
  • （2,70）
  • （42,80）
  • （4,25）
  • （12,44）
  • （14,32）
  • （17,11）
  • （13,78）
  • （37,98）
Sr.No. Key Hash Array Index
1 1 1 % 20 = 1 1
2 2 2 % 20 = 2 2
3 42 42 % 20 = 2 2
4 4 4 % 20 = 4 4
5 12 12 % 20 = 12 12
6 14 14 % 20 = 14 14
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 37 % 20 = 17 17

線形探査

ご覧のように、配列の既に使用されているインデックスを作成するためにハッシュ手法が使用される場合があります。 このような場合、空のセルが見つかるまで次のセルを調べることにより、配列内の次の空の場所を検索できます。 この手法は、線形プローブと呼ばれます。

Sr.No. Key Hash Array Index After Linear Probing, Array Index
1 1 1 % 20 = 1 1 1
2 2 2 % 20 = 2 2 2
3 42 42 % 20 = 2 2 3
4 4 4 % 20 = 4 4 4
5 12 12 % 20 = 12 12 12
6 14 14 % 20 = 14 14 14
7 17 17 % 20 = 17 17 17
8 13 13 % 20 = 13 13 13
9 37 37 % 20 = 17 17 18

基本操作

ハッシュテーブルの基本的な基本操作は次のとおりです。

  • 検索-ハッシュテーブルの要素を検索します。
  • 挿入-ハッシュテーブルに要素を挿入します。
  • delete -ハッシュテーブルから要素を削除します。

DataItem

検索がハッシュテーブルで実行されることに基づいて、いくつかのデータとキーを持つデータ項目を定義します。 

struct DataItem {
   int data;
   int key;
};

ハッシュ法

データ項目のキーのハッシュコードを計算するハッシュメソッドを定義します。 

int hashCode(int key){
   return key % SIZE;
}

検索操作

要素を検索する場合は常に、渡されたキーのハッシュコードを計算し、そのハッシュコードを配列のインデックスとして使用して要素を見つけます。 計算されたハッシュコードで要素が見つからない場合は、線形プローブを使用して要素を先に取得します。

例

struct DataItem *search(int key) {
  //get the hash
   int hashIndex = hashCode(key);

  //move in array until an empty
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

     //go to next cell
      ++hashIndex;

     //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}

挿入操作

要素を挿入するときは常に、渡されたキーのハッシュコードを計算し、そのハッシュコードを配列のインデックスとして使用してインデックスを見つけます。 計算されたハッシュコードで要素が見つかった場合、空の場所に線形プローブを使用します。

例

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;
   item->key = key;

  //get the hash
   int hashIndex = hashCode(key);

  //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
     //go to next cell
      ++hashIndex;

     //wrap around the table
      hashIndex %= SIZE;
   }

   hashArray[hashIndex] = item;
}

削除操作

要素を削除するときは常に、渡されたキーのハッシュコードを計算し、そのハッシュコードを配列のインデックスとして使用してインデックスを見つけます。 計算されたハッシュコードで要素が見つからない場合は、線形プローブを使用して要素を先に取得します。 見つかったら、そこにダミーのアイテムを保存して、ハッシュテーブルのパフォーマンスを維持します。

例

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

  //get the hash
   int hashIndex = hashCode(key);

  //move in array until an empty
   while(hashArray[hashIndex] !=NULL) {

      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex];

        //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem;
         return temp;
      }

     //go to next cell
      ++hashIndex;

     //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}

Cプログラミング言語でのハッシュの実装については、リンク：/data_structures_algorithms/hash_table_program_in_c [ここをクリック]をご覧ください。

データ構造-ソート手法

並べ替えとは、特定の形式でデータを配置することです。 並べ替えアルゴリズムは、特定の順序でデータを配置する方法を指定します。 最も一般的な順序は、数字順または辞書順です。

ソートの重要性は、データがソートされた方法で保存されている場合、データ検索を非常に高いレベルに最適化できるという事実にあります。 ソートは、より読みやすい形式でデータを表すためにも使用されます。 以下は、実際のシナリオでのソートの例の一部です-

  • 電話帳-電話帳には、名前で簡単に検索できるように、名前でソートされた人々の電話番号が格納されます。
  • 辞書-辞書には単語がアルファベット順に保存されているため、単語の検索が容易になります。

インプレースソートと非インプレースソート

並べ替えアルゴリズムでは、比較のために余分なスペースが必要になる場合があり、いくつかのデータ要素を一時的に保存します。 これらのアルゴリズムは余分なスペースを必要とせず、ソートはインプレースで、またはたとえば配列自体内で行われると言われています。 これは、 in-place sort と呼ばれます。 バブルソートは、インプレースソートの例です。

ただし、一部のソートアルゴリズムでは、プログラムにはソートされる要素以上のスペースが必要です。 同等以上のスペースを使用する並べ替えは、* in-in-place並べ替え*と呼ばれます。 マージソートは、インプレースソートの例です。

安定したソートと不安定なソート

コンテンツをソートした後、ソートアルゴリズムが表示される類似コンテンツのシーケンスを変更しない場合、それは*安定ソート*と呼ばれます。

安定した並べ替え

コンテンツをソートした後、ソートアルゴリズムが表示される類似コンテンツのシーケンスを変更する場合、それは*不安定なソート*と呼ばれます。

不安定な並べ替え

たとえばタプルのように、元の要素のシーケンスを維持したい場合、アルゴリズムの安定性が重要です。

適応および非適応ソートアルゴリズム

並べ替えられるリスト内の既に「並べ替えられた」要素を利用する場合、並べ替えアルゴリズムは適応型と呼ばれます。 つまり、ソースリストに既に並べ替えられた要素がある場合は並べ替え中に、適応アルゴリズムはこれを考慮して、並べ替えを行わないようにします。

非適応アルゴリズムとは、すでにソートされている要素を考慮しないアルゴリズムです。 ソートされていることを確認するために、すべての要素を強制的に並べ替えようとします。

重要な用語

いくつかの用語は、一般的に分類手法を議論する際に造られています、ここにそれらの簡単な紹介があります-

増加する順序

連続する要素が前の要素よりも大きい場合、値のシーケンスは*昇順*と呼ばれます。 たとえば、次のすべての要素が前の要素よりも大きいため、1、3、4、6、8、9は昇順です。

降順

連続する要素が現在の要素より小さい場合、値のシーケンスは*降順*と呼ばれます。 たとえば、次のすべての要素が前の要素よりも小さいため、9、8、6、4、3、1は降順です。

非増加注文

値のシーケンスは、連続する要素がシーケンス内の前の要素以下である場合、*非増加順*であると言われます。 この順序は、シーケンスに重複した値が含まれている場合に発生します。 たとえば、9、8、6、3、3、1は、次のすべての要素が（3の場合）以下であるが以前の要素よりも大きくないため、増加しない順序です。

非減少注文

値のシーケンスは、連続する要素がシーケンス内の前の要素以上である場合、*非減少順*であると言われます。 この順序は、シーケンスに重複した値が含まれている場合に発生します。 たとえば、1、3、3、6、8、9は、次のすべての要素が（3の場合）以上で前の要素よりも大きいため、減少しない順序になっています。

データ構造-バブルソートアルゴリズム

バブルソートは、単純なソートアルゴリズムです。 このソートアルゴリズムは比較ベースのアルゴリズムであり、隣接する要素の各ペアが比較され、要素が順序どおりでない場合は要素が交換されます。 このアルゴリズムは、平均および最悪の場合の複雑さがare（n ^ 2 ^）であるため、大きなデータセットには適していません。ここで、 n はアイテムの数です。

バブルソートの仕組み

この例では、ソートされていない配列を使用します。 バブルソートはΟ（n ^ 2 ^）時間かかるため、短く正確に保ちます。

バブルソート

バブルソートは最初の2つの要素から始まり、それらを比較してどちらが大きいかを確認します。

バブルソート

この場合、値33は14より大きいため、既にソートされた場所にあります。 次に、33と27を比較します。

バブルソート

27は33より小さく、これら2つの値を交換する必要があることがわかります。

バブルソート

新しい配列は次のようになります-

バブルソート

次に、33と35を比較します。 両方がすでにソートされた位置にあることがわかります。

バブルソート

次に、次の2つの値35と10に移動します。

バブルソート

そうすると、10が35より小さいことがわかります。 したがって、それらはソートされません。

バブルソート

これらの値を交換します。 配列の最後に到達したことがわかります。 1回の反復後、配列は次のようになります-

バブルソート

正確に言うと、各反復後に配列がどのように見えるかを示しています。 2回目の反復の後、それはこのように見えるはずです-

バブルソート

各反復の後、少なくとも1つの値が最後に移動することに注意してください。

バブルソート

また、スワップが不要な場合、バブルソートは配列が完全にソートされていることを学習します。

バブルソート

次に、バブルソートの実用的な側面を検討する必要があります。

アルゴリズム

*list* は *n* 要素の配列であると仮定します。 さらに、 *swap* 関数は、指定された配列要素の値を交換すると想定しています。
begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for

   return list

end BubbleSort

疑似コード

アルゴリズム全体では、配列全体が昇順で完全にソートされていない限り、バブルソートは配列要素の各ペアを比較します。 これにより、すべての要素がすでに昇順であるため、配列でスワッピングが不要になった場合など、複雑な問題が発生する可能性があります。

問題を緩和するために、1つのフラグ変数 swapped を使用します。これは、スワップが発生したかどうかを確認するのに役立ちます。 スワップが発生していない場合、つまり 配列はソートするためにこれ以上の処理を必要とせず、ループから出ます。

BubbleSortアルゴリズムの擬似コードは次のように書くことができます- 

procedure bubbleSort( list : array of items )

   loop = list.count;

   for i = 0 to loop-1 do:
      swapped = false

      for j = 0 to loop-1 do:

        /*compare the adjacent elements*/
         if list[j] > list[j+1] then
           /*swap them*/
            swap( list[j], list[j+1] )
            swapped = true
         end if

      end for

     /*if no number was swapped that means
      array is sorted now, break the loop.*/

      if(not swapped) then
         break
      end if

   end for

end procedure return list

実装

元のアルゴリズムとその即興の擬似コードで対処しなかったもう1つの問題は、反復ごとに最高値が配列の終わりに落ち着くことです。 したがって、次の反復には、既にソートされた要素を含める必要はありません。 この目的のために、実装では、ソート済みの値を回避するために内部ループを制限します。

Cプログラミング言語でのバブルソートの実装については、リンク：/data_structures_algorithms/bubble_sort_program_in_c [ここをクリック]をご覧ください。

データ構造とアルゴリズムの挿入ソート

これは、インプレース比較ベースのソートアルゴリズムです。 ここでは、常にソートされるサブリストが維持されます。 たとえば、配列の下部はソートされるように維持されます。 このソートされたサブリストに「挿入」される要素は、適切な場所を見つけてから、そこに挿入する必要があります。 したがって、名前は*挿入ソート*です。

配列が順番に検索され、ソートされていない項目が移動され、ソートされたサブリスト（同じ配列内）に挿入されます。 このアルゴリズムは、その平均および最悪の場合の複雑さがΟ（n ^ 2 ^）であるため、大きなデータセットには適していません。

挿入ソートの仕組み

この例では、ソートされていない配列を使用します。

Unsorted Array

挿入ソートは、最初の2つの要素を比較します。

挿入ソート

14と33の両方がすでに昇順であることがわかります。 今のところ、14はソートされたサブリストにあります。

挿入ソート

挿入ソートは先に進み、33と27を比較します。

挿入ソート

そして、33が正しい位置にないことがわかります。

挿入ソート

33と27を入れ替えます。 また、ソートされたサブリストのすべての要素をチェックします。 ここで、ソートされたサブリストには要素が1つしかなく、27は14より大きいことがわかります。 したがって、ソートされたサブリストは、スワップ後もソートされたままになります。

挿入ソート

今では、ソートされたサブリストに14と27があります。 次に、33と10を比較します。

挿入ソート

これらの値はソートされた順序ではありません。

挿入ソート

そこで、それらを交換します。

挿入ソート

ただし、スワッピングにより27と10はソートされません。

挿入ソート

したがって、それらも交換します。

挿入ソート

再び、14と10が未ソートの順序で見つかります。

挿入ソート

再び交換します。 3回目の反復の終わりまでに、4つのアイテムのサブリストがソートされます。

挿入ソート

このプロセスは、ソートされていないすべての値がソートされたサブリストでカバーされるまで続きます。 ここで、挿入ソートのプログラミングの側面をいくつか見てみましょう。

アルゴリズム

これで、このソート手法がどのように機能するかについての全体像が得られたので、挿入ソートを実現できる簡単なステップを導き出すことができます。 

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

疑似コード

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert

   for i = 1 to length(A) inclusive do:

     /*select value to be inserted*/
      valueToInsert = A[i]
      holePosition = i

     /*locate hole position for the element to be inserted */

      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while

     /*insert the number at hole position*/
      A[holePosition] = valueToInsert

   end for

end procedure

Cプログラミング言語での挿入ソートの実装については、リンク：/data_structures_algorithms/insertion_sort_program_in_c [ここをクリック]を参照してください。

データ構造とアルゴリズムの選択ソート

選択ソートは、単純なソートアルゴリズムです。 このソートアルゴリズムは、リストが2つの部分、左端のソート済み部分と右端の未ソート部分に分けられるインプレース比較ベースのアルゴリズムです。 最初は、ソートされた部分は空で、ソートされていない部分はリスト全体です。

ソートされていない配列から最小の要素が選択され、左端の要素と交換され、その要素がソートされた配列の一部になります。 このプロセスは、ソートされていない配列の境界を1要素右に移動し続けます。

このアルゴリズムは、その平均および最悪の場合の複雑さがΟ（n ^ 2 ^）であるため、大きなデータセットには適していません。ここで、 n はアイテムの数です。

選択ソートの仕組み

例として、次の配列を考えてみましょう。

Unsorted Array

ソートされたリストの最初の位置では、リスト全体が順番にスキャンされます。 現在14が格納されている最初の位置では、リスト全体を検索し、10が最低値であることがわかります。

選択ソート

したがって、14を10に置き換えます。 1回の反復10の後、たまたまリスト内の最小値がソートされたリストの最初の位置に表示されます。

選択ソート

33が存在する2番目の位置では、リストの残りの部分のスキャンを直線的に開始します。

選択ソート

14はリストの2番目に低い値であり、2番目に表示されるはずです。 これらの値を交換します。

選択ソート

2回の反復の後、2つの最小値がソートされた方法で先頭に配置されます。

選択ソート

同じプロセスが配列内の残りのアイテムに適用されます。

以下は、ソートプロセス全体の絵図です-

選択ソート

ここで、選択ソートのプログラミングの側面を学びましょう。

アルゴリズム

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

疑似コード

procedure selection sort
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
  /* set current element as minimum*/
      min = i

     /*check the element to be minimum*/

      for j = i&plus;1 to n
         if list[j] < list[min] then
            min = j;
         end if
      end for

     /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for

end procedure

Cプログラミング言語での選択ソートの実装については、リンク：/data_structures_algorithms/selection_sort_program_in_c [ここをクリック]をご覧ください。

データ構造-ソートアルゴリズムのマージ

マージソートは、分割統治技術に基づくソート技術です。 最悪の場合の時間の複雑さはΟ（n log n）であり、最も尊敬されるアルゴリズムの1つです。

マージソートは、最初に配列を等しい半分に分割してから、ソートされた方法でそれらを結合します。

マージソートの仕組み

マージソートを理解するために、次のようにソートされていない配列を取ります-

Unsorted Array

マージソートでは、アトミック値が達成されない限り、最初に配列全体が均等に半分に分割されることを知っています。 ここでは、8つのアイテムの配列がサイズ4の2つの配列に分割されていることがわかります。

ソート部門の統合

これは、元のアイテムの外観の順序を変更しません。 次に、これら2つの配列を半分に分割します。

ソート部門の統合

これらの配列をさらに分割し、これ以上分割できない原子値を達成します。

ソート部門の統合

今、私たちはそれらが分解されたのとまったく同じ方法でそれらを結合します。 これらのリストに記載されているカラーコードに注意してください。

最初に各リストの要素を比較し、次にそれらをソートされた方法で別のリストに結合します。 14と33がソートされた位置にあることがわかります。 27と10を比較し、2つの値のターゲットリストで最初に10を置き、次に27を置きます。 19と35の順序を変更しますが、42と44は順番に配置されます。

並べ替えの結合を結合

結合フェーズの次の反復では、2つのデータ値のリストを比較し、それらを検出されたデータ値のリストにマージして、すべてをソートされた順序にします。

並べ替えの結合を結合

最終的なマージの後、リストは次のようになります-

ソートのマージ

次に、マージソートのプログラミングの側面を学習します。

アルゴリズム

マージソートは、リストが分割できなくなるまで、リストを均等に分割し続けます。 定義上、リスト内の要素が1つだけの場合は、ソートされます。 次に、マージソートは、小さいリストを結合して、新しいリストもソートしたままにします。 

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

疑似コード

マージソート機能の擬似コードが表示されます。 アルゴリズムでは、2つの主要な機能-分割とマージを指摘しています。

マージソートは再帰で機能し、同じ方法で実装を確認します。 

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c

end procedure

Cプログラミング言語でのマージソートの実装については、リンク：/data_structures_algorithms/merge_sort_program_in_c [ここをクリック]をご覧ください。

データ構造とアルゴリズム-シェルソート

シェルソートは非常に効率的なソートアルゴリズムであり、挿入ソートアルゴリズムに基づいています。 このアルゴリズムは、より小さい値が右端にあり、左端に移動する必要がある場合、挿入ソートの場合のような大きなシフトを回避します。

このアルゴリズムは、最初にそれらをソートし、次に間隔の狭い要素をソートするために、広範囲に広がるエレメントで挿入ソートを使用します。 この間隔は*間隔*と呼ばれます。 この間隔は、クヌースの式に基づいて計算されます-

クヌースの式

h = h * 3 &plus; 1
where −
   h is interval with initial value 1

このアルゴリズムの平均および最悪の複雑さは、最もよく知られているギャップシーケンスに依存するため、このアルゴリズムは中規模のデータセットに対して非常に効率的です。nはアイテムの数です。 そして、最悪の場合のスペースの複雑さはO（n）です。

シェルソートの仕組み

次の例を考えて、シェルソートがどのように機能するかを考えてみましょう。 前の例で使用したのと同じ配列を使用します。 例と理解を容易にするために、4の間隔をとります。 4つの位置の間隔にあるすべての値の仮想サブリストを作成します。 ここで、これらの値は\ {35、14}、\ {33、19}、\ {42、27}および\ {10、44}です

シェルソート

各サブリストの値を比較し、（必要に応じて）元の配列で交換します。 このステップの後、新しい配列は次のようになります-

シェルソート

次に、間隔を1にすると、このギャップは2つのサブリストを生成します-\ {14、27、35、42}、\ {19、10、33、44}

シェルソート

必要に応じて、元の配列の値を比較して交換します。 このステップの後、配列は次のようになります-

シェルソート

最後に、値1の間隔を使用して残りの配列を並べ替えます。 シェルソートは、挿入ソートを使用して配列をソートします。

以下は、段階的な描写です-

シェルソート

残りの配列をソートするために必要なスワップは4つだけであることがわかります。

アルゴリズム

以下は、シェルソートのアルゴリズムです。 

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

疑似コード

以下は、シェルソートの擬似コードです。 

procedure shellSort()
   A : array of items

  /* calculate interval*/
   while interval < A.length/3 do:
      interval = interval * 3 + 1
   end while

   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

     /*select value to be inserted*/
      valueToInsert = A[outer]
      inner = outer;

        /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

     /*insert the number at hole position*/
      A[inner] = valueToInsert

      end for

  /* calculate interval*/
   interval = (interval -1)/3;

   end while

end procedure

Cプログラミング言語でのシェルソートの実装については、リンク：/data_structures_algorithms/shell_sort_program_in_c [ここをクリック]をご覧ください。

データ構造とアルゴリズム-クイックソート

クイックソートは非常に効率的なソートアルゴリズムであり、データの配列をより小さな配列に分割することに基づいています。 大きな配列は2つの配列に分割され、1つは指定された値よりも小さい値、たとえばピボットを保持し、別の配列はピボット値よりも大きい値を保持します。

クイックソートは配列を分割し、それ自体を2回再帰的に呼び出して、結果の2つのサブ配列をソートします。 このアルゴリズムは、平均サイズと最悪ケースの複雑度がそれぞれO（nLogn）とimage.png（n ^ 2 ^）であるため、大規模なデータセットに対して非常に効率的です。

クイックソートのパーティション

次のアニメーション表現は、配列内のピボット値を見つける方法を説明しています。

クイックソートパーティションアニメーション

ピボット値は、リストを2つの部分に分割します。 そして再帰的に、すべてのリストに要素が1つだけ含まれるまで、各サブリストのピボットを見つけます。

クイックソートピボットアルゴリズム

クイックソートでのパーティション分割の理解に基づいて、次のようなアルゴリズムの作成を試みます。 

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

クイックソートピボット擬似コード

上記のアルゴリズムの擬似コードは、次のように導出できます- 

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[&plus;&plus;leftPointer] < pivot do
        //do-nothing
      end while

      while rightPointer > 0 && A[--rightPointer] > pivot do
        //do-nothing
      end while

      if leftPointer >= rightPointer
         break
      else
         swap leftPointer,rightPointer
      end if

   end while

   swap leftPointer,right
   return leftPointer

end function

クイックソートアルゴリズム

ピボットアルゴリズムを再帰的に使用すると、パーティションが小さくなります。 その後、各パーティションはクイックソートのために処理されます。 次のようにクイックソートの再帰アルゴリズムを定義します- 

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

クイックソート擬似コード

それにもっと入るには、クイックソートアルゴリズムの擬似コードを見てみましょう- 

procedure quickSort(left, right)

   if right-left <= 0
      return
   else
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition&plus;1,right)
   end if

end procedure

Cプログラミング言語でのクイックソートの実装については、リンク：/data_structures_algorithms/quick_sort_program_in_c [ここをクリック]をご覧ください。

データ構造-グラフのデータ構造

グラフは、オブジェクトのいくつかのペアがリンクで接続されているオブジェクトのセットの図的表現です。 相互接続されたオブジェクトは、*頂点*と呼ばれるポイントで表され、頂点を接続するリンクは*エッジ*と呼ばれます。

正式には、グラフは*（V、E）のペアです。ここで、 *V は頂点のセットであり、 E は頂点のペアを接続するエッジのセットです。 次のグラフを見てください-

グラフの基本

上記のグラフでは、

V = \ {a、b、c、d、e}

E = \ {ab、ac、bd、cd、de}

グラフのデータ構造

数学的グラフはデータ構造で表現できます。 頂点の配列とエッジの2次元配列を使用してグラフを表現できます。 さらに進む前に、いくつかの重要な用語に慣れてみましょう-

  • 頂点-グラフの各ノードは頂点として表されます。 次の例では、ラベル付きの円は頂点を表します。 したがって、AからGは頂点です。 次の図に示すように、配列を使用してそれらを表すことができます。 ここで、Aはインデックス0で識別できます。 Bは、インデックス1などを使用して識別できます。
  • エッジ-エッジは、2つの頂点間のパスまたは2つの頂点間の線を表します。 次の例では、AからB、BからCなどの線はエッジを表しています。 次の図に示すように、2次元配列を使用して配列を表すことができます。 ここで、ABは行0、列1で1として、行1、列2でBCとして1として表され、他の組み合わせは0のままです。
  • 隣接-2つのノードまたは頂点は、エッジを介して互いに接続されている場合、隣接しています。 次の例では、BはAに隣接しており、CはBに隣接しています。
  • パス-パスは、2つの頂点間のエッジのシーケンスを表します。 次の例では、ABCDはAからDへのパスを表します。

グラフ

基本操作

以下は、グラフの基本的な主要な操作です-

  • 頂点の追加-グラフに頂点を追加します。
  • Add Edge -グラフの2つの頂点間にエッジを追加します。
  • Display Vertex -グラフの頂点を表示します。

グラフの詳細については、リンク：/graph_theory/index [グラフ理論のチュートリアル]をご覧ください。 今後の章でグラフの横断について学習します。

データ構造-深さ優先走査

深さ優先検索（DFS）アルゴリズムは、深さ方向にグラフを走査し、スタックを使用して、繰り返しで行き止まりが発生したときに、検索を開始する次の頂点を取得することを忘れないようにします。

深さ優先トラベサル

上記の例のように、DFSアルゴリズムは最初にSからA、D、G、E、Bを横断し、次にF、最後にCを横断します。 以下のルールを採用しています。

  • *ルール1 *-隣接する未訪問の頂点を訪問します。 訪問済みとしてマークします。 それを表示します。 スタックにプッシュします。
  • *ルール2 *-隣接する頂点が見つからない場合、スタックから頂点をポップアップします。 （スタックからすべての頂点がポップアップされますが、隣接する頂点はありません。）
  • *ルール3 *-スタックが空になるまでルール1とルール2を繰り返します。
Step Traversal Description
1 Depth First Search Step One Initialize the stack.
2 Depth First Search Step Two Mark S *as visited and put it onto the stack. Explore any unvisited adjacent node from S*. We have three nodes and we can pick any of them. For this example, we shall take the node in an alphabetical order.
3 Depth First Search Step Three Mark A *as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both S and D are adjacent to A *but we are concerned for unvisited nodes only.
4 Depth First Search Step Four Visit* D and mark it as visited and put onto the stack. Here, we have B and C nodes, which are adjacent to D *and both are unvisited. However, we shall again choose in an alphabetical order.
5 Depth First Search Step Five We choose* B*, mark it as visited and put onto the stack. Here B *does not have any unvisited adjacent node. So, we pop B *from the stack.
6 Depth First Search Step Six We check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find* D *to be on the top of the stack.
7 Depth First Search Step Seven Only unvisited adjacent node is from* D is C now. So we visit C*, mark it as visited and put it onto the stack. 
*C* には未訪問の隣接ノードがないため、未訪問の隣接ノードを持つノードが見つかるまでスタックをポップし続けます。 この場合、何も存在せず、スタックが空になるまでポップを続けます。

Cプログラミング言語でのこのアルゴリズムの実装について知るには、リンク：/data_structures_algorithms/depth_first_traversal_in_c [ここをクリック]をクリックしてください。

データ構造-幅優先走査

幅優先探索（BFS）アルゴリズムは、グラフを幅方向に移動し、キューを使用して、反復で行き止まりが発生したときに、次の頂点を取得して検索を開始することを忘れないようにします。

幅優先トラバーサル

上記の例のように、BFSアルゴリズムは、AからB、EからF、最初にC、GからDの順に移動します。 以下のルールを採用しています。

  • *ルール1 *-隣接する未訪問の頂点を訪問します。 訪問済みとしてマークします。 それを表示します。 キューに挿入します。
  • *ルール2 *-隣接する頂点が見つからない場合、キューから最初の頂点を削除します。
  • *ルール3 *-キューが空になるまでルール1とルール2を繰り返します。
Step Traversal Description
1 Breadth First Search Step One Initialize the queue.
2 Breadth First Search Step Two We start from visiting *S *(starting node), and mark it as visited.
3 Breadth First Search Step Three We then see an unvisited adjacent node from* S*. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.
4 Breadth First Search Step Four Next, the unvisited adjacent node from S *is B*. We mark it as visited and enqueue it.
5 Breadth First Search Step Five Next, the unvisited adjacent node from S *is C*. We mark it as visited and enqueue it.
6 Breadth First Search Step Six Now, S *is left with no unvisited adjacent nodes. So, we dequeue and find A*.
7 Breadth First Search Step Seven From A *we have D* as unvisited adjacent node. We mark it as visited and enqueue it.

この段階では、マークされていない（訪問されていない）ノードはありません。 ただし、アルゴリズムに従って、すべての未訪問ノードを取得するために、キューからの取り出しを続けます。 キューが空になると、プログラムは終了します。

Cプログラミング言語でのこのアルゴリズムの実装は、リンクすることができます：/data_structures_algorithms/breadth_first_traversal_in_c [ここに表示]。

データ構造とアルゴリズム-ツリー

ツリーは、エッジで接続されたノードを表します。 二分木または二分探索木について具体的に説明します。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。 二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。 検索はソートされた配列と同じくらい迅速で、挿入または削除操作はリンクされたリストと同じくらい速いので、バイナリツリーには順序付き配列とリンクされたリストの両方の利点があります。

バイナリツリー

重要な用語

以下は、ツリーに関する重要な用語です。

  • パス-パスは、ツリーのエッジに沿ったノードのシーケンスを指します。
  • ルート-ツリーの最上部のノードはルートと呼ばれます。 ツリーごとにルートは1つだけで、ルートノードから任意のノードへのパスは1つだけです。
  • 親-ルートノードを除くすべてのノードは、親と呼ばれるノードの上方に1つのエッジを持ちます。
  • 子-下のエッジで接続された特定のノードの下のノードは、その子ノードと呼ばれます。
  • リーフ-子ノードを持たないノードは、リーフノードと呼ばれます。
  • サブツリー-サブツリーはノードの子孫を表します。
  • 訪問-訪問は、制御がノード上にあるときにノードの値をチェックすることを指します。
  • 探索-探索とは、特定の順序でノードを通過することを意味します。
  • レベル-ノードのレベルは、ノードの生成を表します。 ルートノードがレベル0にある場合、その次の子ノードはレベル1に、孫はレベル2に、というように続きます。
  • キー-キーは、ノードの検索操作が実行されるノードの値を表します。

バイナリ検索ツリー表現

バイナリ検索ツリーは特別な動作を示します。 ノードの左の子の値は親の値より小さく、ノードの右の子の値は親の値より大きくなければなりません。

バイナリ検索ツリー

ノードオブジェクトを使用してツリーを実装し、参照を介してそれらを接続します。

ツリーノード

ツリーノードを記述するコードは、以下に示すものに似ています。 データ部分と、その左および右の子ノードへの参照があります。 

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

ツリーでは、すべてのノードが共通の構造を共有します。

BSTの基本操作

バイナリ検索ツリーのデータ構造で実行できる基本的な操作は次のとおりです-

  • 挿入-ツリーに要素を挿入/ツリーを作成します。
  • 検索-ツリー内の要素を検索します。
  • Preorder Traversal -事前順序でツリーを走査します。
  • Inorder Traversal -ツリーを順番に走査します。
  • Postorder Traversal -ポストオーダー方式でツリーを横断します。

この章では、ツリー構造の作成（挿入）とツリー内のデータ項目の検索について学習します。 次の章で、ツリートラバースの方法について学習します。

挿入操作

最初の挿入でツリーが作成されます。 その後、要素を挿入するときは常に、最初に適切な場所を見つけます。 ルートノードから検索を開始し、データがキー値より小さい場合は、左側のサブツリーの空の場所を検索してデータを挿入します。 それ以外の場合は、右側のサブツリーで空の場所を検索し、データを挿入します。

アルゴリズム

If root is NULL
   then create root node
return

If root exists then
   compare the data with node.data

   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile

   insert data

end If

実装

挿入関数の実装は次のようになります- 

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

  //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {
         parent = current;

        //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;

           //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }

        //go to right of the tree
         else {
            current = current->rightChild;

           //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}

検索操作

要素を検索するときはいつでも、ルートノードから検索を開始し、データがキー値よりも小さい場合は、左のサブツリーで要素を検索します。 それ以外の場合は、右のサブツリーで要素を検索します。 各ノードで同じアルゴリズムに従います。

アルゴリズム

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

      If data found
         return node
   endwhile

   return data not found

end if

このアルゴリズムの実装は次のようになります。 

struct node *search(int data) {
   struct node* current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data);

     //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
     //else go to right tree
      else {
         current = current->rightChild;
      }

     //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }
}

バイナリ検索ツリーデータ構造の実装については、リンクしてください：/data_structures_algorithms/tree_traversal_in_c [ここをクリック]。

データ構造とアルゴリズム-ツリートラバーサル

トラバーサルは、ツリーのすべてのノードを訪問するプロセスであり、それらの値も出力する場合があります。 すべてのノードはエッジ（リンク）を介して接続されているため、常にルート（ヘッド）ノードから開始します。 つまり、ツリー内のノードにランダムにアクセスすることはできません。 私たちがツリーを横断するために使用する3つの方法があります-

  • 順番通りのトラバーサル
  • 先行予約のトラバーサル
  • 注文後のトラバーサル

一般に、ツリーを走査して、ツリー内の特定のアイテムまたはキーを検索または検索するか、ツリーに含まれるすべての値を印刷します。

順番通りのトラバーサル

この走査方法では、左のサブツリーが最初に訪問され、次にルート、次に右のサブツリーが訪問されます。 すべてのノードがサブツリー自体を表す場合があることを常に覚えておく必要があります。

バイナリツリーが in-order で走査される場合、出力は昇順でソートされたキー値を生成します。

In Order Traversal 

*A* から開始し、順番にトラバーサルした後、その左側のサブツリー *B* に移動します。 *B* も順番に走査されます。 このプロセスは、すべてのノードが訪問されるまで続きます。 このツリーの順序走査の出力は次のようになります-
*_D→B→E→A→F→C→G_*

アルゴリズム

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

先行予約のトラバーサル

この走査方法では、ルートノードが最初に訪問され、次に左のサブツリー、最後に右のサブツリーが訪問されます。

事前注文トラバーサル 

*A* から開始し、予約注文のトラバーサルに続いて、まず *A* 自体にアクセスしてから、左のサブツリー *B* に移動します。 *B* も事前注文されます。 このプロセスは、すべてのノードが訪問されるまで続きます。 このツリーの事前順序走査の出力は次のようになります-
*_A→B→D→E→C→F→G_*

アルゴリズム

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

注文後のトラバーサル

このトラバーサル方式では、ルートノードが最後にアクセスされるため、名前が付けられます。 最初に左のサブツリー、次に右のサブツリー、最後にルートノードを走査します。

注文順のトラバース 

*A* から開始し、ポストオーダートラバーサルに続いて、最初に左側のサブツリー *B* にアクセスします。 *B* もポストオーダーで走査されます。 このプロセスは、すべてのノードが訪問されるまで続きます。 このツリーのポストオーダートラバーサルの出力は次のようになります-
*_D→E→B→F→G→C→A_*

アルゴリズム

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

ツリートラバースのC実装を確認するには、リンクしてください：/data_structures_algorithms/tree_traversal_in_c [ここをクリック]。

データ構造-バイナリ検索ツリー

バイナリ検索ツリー（BST）は、すべてのノードが下記のプロパティに従うツリーです-

  • ノードの左のサブツリーのキーは、親ノードのキー以下です。
  • ノードの右サブツリーには、親ノードのキーよりも大きいキーがあります。

したがって、BSTはすべてのサブツリーを2つのセグメントに分割します。左のサブツリーと右のサブツリーと定義することができます- 

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

表現

BSTは、BSTプロパティを維持するように配置されたノードのコレクションです。 各ノードにはキーと関連付けられた値があります。 検索中に、目的のキーがBSTのキーと比較され、見つかった場合は、関連付けられた値が取得されます。

以下は、BSTの図解です-

バイナリ検索ツリー

ルートノードキー（27）の左側のサブツリーには値の小さいキーがあり、右側のサブツリーには値の大きいキーがあることがわかります。

基本操作

以下は、ツリーの基本的な操作です-

  • 検索-ツリー内の要素を検索します。
  • 挿入-ツリーに要素を挿入します。
  • Pre-order Traversal -事前順序でツリーを走査します。
  • In-order Traversal -ツリーを順序どおりに走査します。
  • Post-order Traversal -ポストオーダー方式でツリーを横断します。

Node

いくつかのデータ、その左および右の子ノードへの参照を持つノードを定義します。 

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

検索操作

要素を検索するときは、必ずルートノードから検索を開始してください。 次に、データがキー値よりも小さい場合、左側のサブツリーで要素を検索します。 それ以外の場合は、右のサブツリーで要素を検索します。 各ノードで同じアルゴリズムに従います。

アルゴリズム

struct node *search(int data){
   struct node* current = root;
   printf("Visiting elements: ");

   while(current->data != data){

      if(current != NULL) {
         printf("%d ",current->data);

        //go to left tree
         if(current->data > data){
            current = current->leftChild;
         } //else go to right tree
         else {
            current = current->rightChild;
         }

        //not found
         if(current == NULL){
            return NULL;
         }
      }
   }

   return current;
}

挿入操作

要素を挿入するときは、まず適切な場所を見つけてください。 ルートノードから検索を開始し、データがキー値より小さい場合は、左側のサブツリーの空の場所を検索してデータを挿入します。 それ以外の場合は、右側のサブツリーで空の場所を検索し、データを挿入します。

アルゴリズム

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

  //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {
         parent = current;

        //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;
           //insert to the left

            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         } //go to right of the tree
         else {
            current = current->rightChild;

           //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}

データ構造とアルゴリズム-AVLツリー

バイナリ検索ツリーへの入力が並べ替えられた（昇順または降順）場合はどうなりますか？ それはこのようになります-

アンバランスBST

BSTの最悪の場合のパフォーマンスは線形検索アルゴリズム、つまりΟ（n）に最も近いことがわかります。 リアルタイムデータでは、データパターンとその頻度を予測することはできません。 そのため、既存のBSTのバランスをとる必要が生じます。

発明者 Adelson 、 Velski ＆ Landis 、* AVLツリー*は、高さのバランスをとるバイナリ検索ツリーにちなんで命名されました。 AVLツリーは、左右のサブツリーの高さをチェックし、差が1以下であることを確認します。 この違いは「バランス係数」と呼ばれます。

ここでは、最初のツリーのバランスが取れており、次の2つのツリーのバランスが取れていないことがわかります-

不平衡AVLツリー

2番目のツリーでは、 C の左側のサブツリーの高さは2で、右側のサブツリーの高さは0であるため、差は2です。 3番目のツリーでは、 A の右側のサブツリーの高さは2であり、左側は欠落しているため、0になり、差は2になります。 AVLツリーでは、差（バランスファクター）を1のみにすることができます。 

BalanceFactor = height(left-sutree) − height(right-sutree)

左と右のサブツリーの高さの差が1より大きい場合、ツリーはいくつかの回転手法を使用してバランスが取られます。

AVLローテーション

それ自体のバランスをとるために、AVLツリーは次の4種類の回転を実行することがあります-

  • 左回転
  • 右回転
  • 左右回転
  • 右回転

最初の2つの回転はシングル回転で、次の2つの回転はダブル回転です。 不均衡なツリーを作成するには、少なくとも高さ2のツリーが必要です。 この単純なツリーを使用して、それらを1つずつ理解しましょう。

左回転

ツリーが不均衡になった場合、ノードが右サブツリーの右サブツリーに挿入されると、単一の左回転を実行します-

左回転

この例では、ノードのAの右サブツリーの右サブツリーにノードが挿入されるため、ノード A は不均衡になりました。 A をBの左サブツリーにして左回転を実行します。

右回転

ノードが左サブツリーの左サブツリーに挿入されると、AVLツリーは不均衡になる可能性があります。 ツリーは右回転が必要です。

右回転

示されているように、不均衡なノードは、右回転を実行することにより、その左の子の右の子になります。

左右回転

ダブルローテーションは、既に説明したバージョンのローテーションのわずかに複雑なバージョンです。 それらをよりよく理解するには、回転中に実行される各アクションに注意する必要があります。 最初に、左から右への回転の実行方法を確認しましょう。 左右回転は、左回転とそれに続く右回転の組み合わせです。

State Action
Right Rotation A node has been inserted into the right subtree of the left subtree. This makes *C *an unbalanced node. These scenarios cause AVL tree to perform left-right rotation.
Left Rotation We first perform the left rotation on the left subtree of* C*. This makes A, the left subtree of B.
Left Rotation Node *C *is still unbalanced, however now, it is because of the left-subtree of the left-subtree.
Right Rotation We shall now right-rotate the tree, making* B the new root node of this subtree. C *now becomes the right subtree of its own left subtree.
Balanced Avl Tree The tree is now balanced.

右回転

2番目のタイプの二重回転は、右回転です。 これは、右回転とそれに続く左回転の組み合わせです。

State Action
Left Subtree of Right Subtree A node has been inserted into the left subtree of the right subtree. This makes* A*, an unbalanced node with balance factor 2.
Subtree Right Rotation First, we perform the right rotation along C *node, making C the right subtree of its own left subtree B*. Now, B *becomes the right subtree of A*.
Right Unbalanced Tree Node *A *is still unbalanced because of the right subtree of its right subtree and requires a left rotation.
Left Rotation A left rotation is performed by making* B the new root node of the subtree. A becomes the left subtree of its right subtree B*.
Balanced AVL Tree The tree is now balanced.

データ構造とアルゴリズム-スパニングツリー

スパニングツリーはグラフGのサブセットであり、すべての頂点が最小数のエッジで覆われています。 したがって、スパニングツリーにはサイクルがなく、切断できません。

この定義により、すべての接続された無向グラフGには少なくとも1つのスパニングツリーがあるという結論を導き出すことができます。 切断されたグラフには、すべての頂点にまたがることができないため、スパニングツリーがありません。

スパニングツリー

1つの完全なグラフから3つのスパニングツリーが見つかりました。 完全な無向グラフは、最大 n ^ n-2 ^ のスパニングツリーを持つことができます。ここで、 n はノードの数です。 上記の例では、 nは3 です。したがって、 3 ^ 3-2 ^ = 3 スパニングツリーが可能です。

スパニングツリーの一般的なプロパティ

1つのグラフが複数のスパニングツリーを持つことができることがわかりました。 以下は、グラフGに接続されたスパニングツリーのいくつかのプロパティです-

  • 連結グラフGは、複数のスパニングツリーを持つことができます。
  • グラフGのすべてのスパニングツリーは、同じ数のエッジと頂点を持ちます。
  • スパニングツリーにはサイクル（ループ）がありません。
  • スパニングツリーから1つのエッジを削除すると、グラフが切断されます。 スパニングツリーは*最小接続*です。
  • スパニングツリーに1つのエッジを追加すると、回線またはループが作成されます。 スパニングツリーは*最大非循環*です。

スパニングツリーの数学的特性

  • スパニングツリーには n-1 のエッジがあります。 n はノード（頂点）の数です。
  • 完全なグラフから、最大 e-n＆plus;を削除して1 エッジ、スパニングツリーを構築できます。
  • 完全なグラフには、最大 n ^ n-2 ^ 個のスパニングツリーを含めることができます。

したがって、スパニングツリーは接続されたグラフGのサブセットであり、切断されたグラフにはスパニングツリーがないと結論付けることができます。

スパニングツリーの応用

スパニングツリーは基本的に、グラフ内のすべてのノードを接続するための最小パスを見つけるために使用されます。 スパニングツリーの一般的なアプリケーションは-

  • 市民ネットワーク計画
  • コンピューターネットワークルーティングプロトコル
  • クラスター分析

小さな例を使ってこれを理解しましょう。 都市ネットワークは巨大なグラフであると考えてください。現在、電話回線を最小限の回線ですべての都市ノードに接続できるように配置することを計画しています。 これが、スパニングツリーの出番です。

最小スパニングツリー（MST）

重み付きグラフでは、最小スパニングツリーは、同じグラフの他のすべてのスパニングツリーよりも最小の重みを持つスパニングツリーです。 実際の状況では、この重みは、距離、輻輳、トラフィック負荷、またはエッジに示される任意の値として測定できます。

最小スパニングツリーアルゴリズム

ここでは、2つの最も重要なスパニングツリーアルゴリズムについて学習します-

  • リンク：/data_structures_algorithms/kruskals_spanning_tree_algorithm [Kruskal’s Algorithm]
  • リンク：/data_structures_algorithms/prims_spanning_tree_algorithm [Prim’s Algorithm]

どちらも貪欲なアルゴリズムです。

ヒープデータ構造

ヒープは、バランスの取れたバイナリツリーデータ構造の特殊なケースで、ルートノードキーがその子と比較され、それに応じて配置されます。 *α*に子ノード*β*がある場合-

key（α）≥key（β）

親の値が子の値より大きいため、このプロパティは Max Heap を生成します。 この基準に基づいて、ヒープは2つのタイプになります- 

For Input → 35 33 42 10 14 19 27 44 26 31
*Min-Heap* -ルートノードの値がその子のいずれか以下である場合。

最大ヒープの例 

*Max-Heap* -ルートノードの値がその子のいずれか以上である場合。

最大ヒープの例

両方のツリーは、同じ入力と到着順序を使用して構築されます。

最大ヒープ構築アルゴリズム

同じ例を使用して、最大ヒープがどのように作成されるかを示します。 最小ヒープを作成する手順は似ていますが、最大値ではなく最小値を使用します。

一度に1つの要素を挿入することにより、最大ヒープのアルゴリズムを導き出します。 ヒープは常にそのプロパティを維持する必要があります。 挿入中に、すでにヒープ化されたツリーにノードを挿入していることも想定しています。 

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

注-最小ヒープ構築アルゴリズムでは、親ノードの値が子ノードの値よりも小さくなると予想されます。

アニメーションの図でMax Heapの構造を理解しましょう。 前に使用したのと同じ入力サンプルを検討します。

最大ヒープアニメーションの例

最大ヒープ削除アルゴリズム

最大ヒープから削除するアルゴリズムを導き出しましょう。 最大（または最小）ヒープの削除は、常にルートで行われ、最大（または最小）値が削除されます。 

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

最大ヒープ削除アニメーションの例

データ構造-再帰の基本

一部のコンピュータープログラミング言語では、モジュールまたは関数が自分自身を呼び出すことができます。 この手法は、再帰として知られています。 再帰では、関数*α*はそれ自体を直接呼び出すか、元の関数*α*を呼び出す関数*β*を呼び出します。 関数*α*は、再帰関数と呼ばれます。

例-それ自体を呼び出す関数。 

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);
}

例-別の関数を呼び出して、それを再び呼び出す関数。 

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);
}
int function2(int value2) {
   function1(value2);
}

プロパティ

再帰関数はループのように無限に進むことができます。 再帰関数の無限実行を避けるために、再帰関数が持つ必要がある2つのプロパティがあります-

  • 基本条件-この条件が満たされると、関数がそれ自体の再帰呼び出しを停止するように、少なくとも1つの基本条件または条件が必要です。
  • プログレッシブアプローチ-再帰呼び出しは、再帰呼び出しが行われるたびに基本条件に近づくように進行する必要があります。

実装

多くのプログラミング言語は、 stacks を使用して再帰を実装しています。 一般に、関数（ caller ）が別の関数（ callee ）またはそれ自体を呼び出し先として呼び出すたびに、呼び出し元関数は実行制御を呼び出し先に渡します。 この転送プロセスには、呼び出し元から呼び出し先に渡されるデータも含まれる場合があります。

これは、呼び出し元の関数がその実行を一時的に中断し、実行制御が呼び出し先の関数から戻ったときに再開する必要があることを意味します。 ここで、呼び出し元関数は、それ自体を保留にする実行ポイントから正確に開始する必要があります。 また、作業していたのとまったく同じデータ値が必要です。 この目的のために、呼び出し側関数のアクティベーションレコード（またはスタックフレーム）が作成されます。

アクティベーションレコード

このアクティベーションレコードは、ローカル変数、仮パラメーター、戻りアドレス、および呼び出し元関数に渡されるすべての情報に関する情報を保持します。

再帰の分析

同じタスクを反復で実行できるため、再帰を使用する理由を議論するかもしれません。 最初の理由は、再帰はプログラムをより読みやすくし、最新の強化されたCPUシステムのために、再帰は反復よりも効率的です。

時間の複雑さ

反復の場合、時間の複雑さをカウントするために反復回数を取ります。 同様に、再帰の場合、すべてが一定であると仮定して、再帰呼び出しが行われている回数を把握しようとします。 関数の呼び出しはΟ（1）であるため、再帰呼び出しが（n）回行われると、再帰関数がΟ（n）になります。

スペースの複雑さ

スペースの複雑さは、モジュールの実行に必要な追加スペースの量としてカウントされます。 繰り返しの場合、コンパイラは余分なスペースをほとんど必要としません。 コンパイラは、反復で使用される変数の値を更新し続けます。 ただし、再帰の場合、システムは再帰呼び出しが行われるたびにアクティベーションレコードを保存する必要があります。 したがって、再帰関数の空間の複雑さは、反復を伴う関数の空間の複雑さよりも高くなると考えられます。

データ構造とアルゴリズム-ハノイの塔

ハノイの塔は、3つの塔（ペグ）で構​​成される数学的なパズルであり、複数のリングが描かれている-

ハノイの塔

これらのリングはサイズが異なり、昇順で積み重ねられます。 小さい方が大きい方の上に座っています。 ディスクの数が増えるパズルの他のバリエーションがありますが、タワーの数は同じままです。

規則

ミッションは、配列の順序に違反することなく、すべてのディスクを別のタワーに移動することです。 ハノイの塔のために従うべきいくつかのルールは-

  • 一度に1つのディスクのみをタワー間で移動できます。
  • 「トップ」ディスクのみを削除できます。
  • 小さなディスクの上に大きなディスクを置くことはできません。

以下は、ハノイの塔パズルを3つのディスクで解くアニメーション表現です。

ハノイの塔

n個のディスクを備えたハノイの塔パズルは、最小 2 ^ n ^ -1 ステップで解決できます。 このプレゼンテーションは、3個のディスクを使用したパズルが 2 ^ 3 ^-1 = 7 ステップを踏んだことを示しています。

アルゴリズム

ハノイの塔のアルゴリズムを作成するには、まず、たとえば1または2という少ないディスクでこの問題を解決する方法を学ぶ必要があります。 3つのタワーに名前、 source 、 destination および aux を付けます（ディスクの移動を支援するためだけです）。 ディスクが1つしかない場合、ソースペグからデスティネーションペグに簡単に移動できます。

2つのディスクがある場合-

  • 最初に、小さい（上部）ディスクを補助ペグに移動します。
  • 次に、大きい（下）ディスクを目的のペグに移動します。
  • 最後に、小さいディスクを補助ペグから目的のペグに移動します。

2つのディスクを備えたハノイの塔

そのため、現在、3枚以上のディスクでハノイの塔のアルゴリズムを設計する立場にあります。 ディスクのスタックを2つの部分に分割します。 最大のディスク（n ^ th ^ディスク）は1つの部分にあり、他のすべての（n-1）ディスクは2番目の部分にあります。

最終的な目的は、ディスクをソースからデスティネーションに n 移動し、他のすべての（n1）ディスクをそのディスクに配置することです。 与えられたすべてのディスクセットに対して同じ方法を再帰的に適用することを想像できます。

従うべき手順は次のとおりです- 

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

ハノイの塔の再帰アルゴリズムは、次のように駆動することができます- 

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest
   ELSE
      Hanoi(disk - 1, source, aux, dest)    //Step 1
      move disk from source to dest         //Step 2
      Hanoi(disk - 1, aux, dest, source)    //Step 3
   END IF

END Procedure
STOP

Cプログラミングでの実装を確認するには、リンク：/data_structures_algorithms/tower_of_hanoi_in_c [ここをクリック]。

データ構造とアルゴリズムフィボナッチ数列

フィボナッチ数列は、2つの前の数値を追加することにより、後続の数値を生成します。 フィボナッチ数列は、* F〜0〜＆F〜1〜*の2つの数字から始まります。 F〜0〜およびF〜1〜の初期値は、それぞれ0、1、または1、1になります。

フィボナッチ数列は次の条件を満たす- 

Fn = Fn-1 + Fn-2

したがって、フィボナッチ数列は次のようになります-

F〜8〜= 0 1 1 2 3 5 8 13

または、これ-

F〜8〜= 1 1 2 3 5 8 13 21

説明のために、F〜8〜のフィボナッチは次のように表示されます-

フィボナッチアニメーション

フィボナッチ反復アルゴリズム

まず、フィボナッチ数列の反復アルゴリズムのドラフトを試みます。 

Procedure Fibonacci(n)
   declare f0, f1, fib, loop

   set f0 to 0
   set f1 to 1

   display f0, f1

   for loop ← 1 to n

      fib ← f0 &plus; f1
      f0 ← f1
      f1 ← fib

      display fib
   end for

end procedure

Cプログラミング言語での上記のアルゴリズムの実装については、リンク：/data_structures_algorithms/fibonacci_iterative_program_in_c [ここをクリック]をクリックしてください。

フィボナッチ再帰アルゴリズム

再帰アルゴリズムのフィボナッチ数列を作成する方法を学びましょう。 再帰の基本基準。 

START
Procedure Fibonacci(n)
   declare f0, f1, fib, loop

   set f0 to 0
   set f1 to 1

   display f0, f1

   for loop ← 1 to n

      fib ← f0 &plus; f1
      f0 ← f1
      f1 ← fib

      display fib
   end for

END

上記のアルゴリズムのCプログラミング言語での実装を確認するには、リンク：/data_structures_algorithms/fibonacci_recursive_program_in_c [ここをクリック]をクリックしてください。 Data-structures-algorithms-questions-answers

「https://www.finddevguides.com/index.php?title=Data-structures-algorithms-quick-guide&oldid=78834」から取得
Powered by MediaWiki