1. 序章

このチュートリアルでは、いくつかの一般的で有用なデータ構造、つまりベクトル、配列リンクリストツリー、 グラフ、および[X154X ]スタックが表示されます。

私たちの目的は、データ構造の一般的なプログラミング言語に依存しない説明を提示し、それらの使用法を示すことです。

2. 配列

コンピュータサイエンスにおける重要なデータ構造は、配列、フィールドの連続セットです。

各フィールドには、メモリ内に指定されたサイズがあります。 フィールド自体は、たとえば、バイト、数値、固定サイズのデータ構造、またはより複雑なデータ構造へのポインタにすることができます。

連続する各フィールドに、最初に0で始まるインデックスを割り当てます。 n にフィールドのサイズを掛けて開始位置に追加することで、配列のnthフィールドにアクセスできます。

数値の1次元配列を表す配列で4番目のフィールドを見つける方法を見てみましょう。

コンピューティング言語では、4番目の要素はV(4)またはV[4]のような表記法で指定できます。

2.1. マトリックス

matrix は、2次元のフィールドセットを表す配列の特殊なケースです。

行列は配列の配列と考えることができます。

2次元の「最初の」配列の各フィールドは、「2番目の」配列を保持します。  最初の次元でフィールドの最初の配列にアクセスします。 2番目の次元を使用して、「2番目の」配列内の目的のフィールドを見つけます。

要素の配列として行列Mがあり、それぞれに5つの要素がある例を見てみましょう。 次の方法で、最初のベクトルの2番目の要素、つまり M(1,2)にアクセスできます。

行列をメモリ内の配列として表すと、次のようになります。

行列の開始に、ベクトルのサイズ 2 を加算して、最初のベクトルの2番目の数値にアクセスします。 この場合、配列フィールド自体は5つの数値の配列です。

2.2. 配列と行列の使用

配列は、コンピュータサイエンスの基本的なデータ構造です。 そしてその用途は無限です。

順序付けされているかどうかに関係なく、データ構造の任意のセットを配列として表すことができます。 数字、名前、都市、やるべき仕事など、同じオブジェクトのセットまたはリストがあるときはいつでも、それらを配列として表すことができます。

配列は、格納するもののリストまたはセットを保持します。たとえば、数値のリストがある場合、配列の各フィールドは数値の1つを保持します。

保存する内容も複雑になる可能性があります。 一連の従業員の連絡先情報のリストがあるとします。 配列の各フィールドは、特定の従業員を説明するデータ構造になります。

スプレッドシートは基本的にマトリックス形式の配列です。 2次元インデックスにアクセスすることにより、スプレッドシートの行と列にアクセスして操作します。

線形代数の適用を含む数値計算は、数値の配列として表されます。 アプリケーションは、ベクトルと行列の乗算に及び、線形非線形方程式統計、さらにはのデータを解きます。機械学習

3. グラフ

グラフは、もう1つの便利なデータ構造です。 それはグラフ理論に由来します。

グラフは、ノード(頂点とも呼ばれます)のセットであり、ノードを接続するエッジ-線で接続されています。

ノードとエッジの両方にプロパティを割り当てることができます。 グラフ理論の言葉で言えば、プロパティはcolorです。 たとえば、プロパティ「1」をノードに割り当てる場合、ノードの色は「1」であると言います。

エッジを方向付けすることができます。つまり、1つのノードを別のノードにポイントさせるか、両方のノードを互いにポイントするように設定できます。

以下に、4つのノードを持つグラフを示します。 2つのノードは、「Jill」と「Jack」のラベルで色付けされています。 他の2つのノードの色はありません。

3種類のエッジを作成しました。 「ジャック」から、矢印のある有向エッジと矢印のない無向エッジを作成しました。 「ジャック」と「ジル」の間に、両方向を指すノードを作成し、そのノードに「関連」という色のラベルを付けました。

特に、エッジはトラバーサルパターンを示すことができます。

たとえば、各ノードがWebサイトを表す場合、サイトAからサイトBへの有向エッジは、サイトAにサイトBへのリンクがあることを示している可能性があります。

有向エッジのグラフを使用して、あるサイトが別のサイトから到達可能であるかどうか、もしそうなら、そこに到達するためのクリック数が最も少ないかどうかを考えることができます。

3.1. 木

ツリーは特殊なタイプのグラフです。 グラフ理論では、ツリーはサイクルを持たないグラフ、つまり接続された非循環グラフです。

エッジを介してツリーをトラバースする場合、エッジを1回だけ使用し、既にアクセスしたノードには到達しません。

以下に、2つの異なる方法で同じグラフを示します。 描画方法に関係なく、サイクルなしのツリーのままです。

右側のツリーは、葉へのパスを持つトップノードまたはルートノードから始めて、ツリーを描画する一般的な方法を示しています。 葉はパスの終わりです:

ツリーのもう1つの重要な概念は、ノードの親です。 上のグラフでは、ノード2はノード5のです。

3.2. グラフ構造の表現

グラフのデータ構造を表す方法はいくつかあります。 グラフを表現するための多数の方法のうち、どれを選択するかは、グラフデータを処理および管理する方法によって異なります。

1つの表現はノードを中心にしています。ノードのセットとしてグラフを作成します。 各ノードには、そのノードを他のノードに接続する方法に関する情報を配置します。

たとえば、以前のツリーでノード1の構造の概要を説明できます。

  • ノード情報
    • ノードの色:1
  • エッジ情報
    • エッジ0:2に向けられた
    • エッジ1:3に向けられた
    • エッジ2:4に向けられた

別の表現はエッジに焦点を当てています。グラフはエッジのコレクションとして表示されます。 各エッジには、エッジの色とタイプ、および接続する2つのノードがあります。 エッジのノード情報は、ノード情報がどこにあるかを示すポインターまたはインデックスである可能性があります。

たとえば、ツリーのノード1とノード2の間のエッジの構造を概説できます。

  • エッジ情報
    • エッジタイプ:有向
    • エッジカラー:なし
  • ノード情報
    • ノード1情報へのポインタ/インデックス
    • ノード2情報へのポインタ/インデックス

グラフデータ構造の別の表現は隣接行列です。グラフにnノードがある場合、その隣接行列にはn行と列があります。

たとえば、グラフとその隣接行列を見てみましょう。

各行はノードの1つを表し、各列も同様です。 セルの1つ、たとえば行1と列4に値がある場合、ノード1とノード4の間にエッジがあります。 セルで異なる数値を使用して、そのエッジの重量を表すことができます。

この設定では、3つのタイプの関係を表すことができます。 A [i、j] を使用して、行iおよび列j。のマトリックス内のセルを表すことに注意してください。

まず、特定のセルが0の場合、たとえばA [i、j]の場合、ノードiとjの間にエッジはありません。 A [1,3] のゼロの値は、ノード1とノード3の間にエッジがないことを意味します。

2番、 特定のセルがA[i、j]でゼロ以外の場合、ノードiとノードの間にエッジがあります。 j。 これを有向エッジとして描画します。 A [3,2] には5の値があるため、ノード3とノード2の間に有向エッジがあることを意味します。

第3に、 A [i、j]とA [j、i]の両方のセルがゼロ以外の場合、前と同じようにノードiとjの間にエッジがありますが、今回は無向エッジを使用します。 A[1,4]A[4,1] には1の値があるため、ノード1と4の間に無向エッジがあることを意味します。

エッジのプロパティはその色であることを思い出して、少し単純化して、重み1のエッジには色がないと言うことに注意してください。したがって、ノード3からノード2までのエッジの色は5です。 、しかし、残りのすべてのエッジには色がありません。

3.3. ツリーとグラフの使用

セマンティックWebの重要な概念は、オントロジー、またはリンクトデータ語彙です。 このタイプの例では、グラフの色付きのノードは情報のエンティティであり、色付きの接続はそれらの関係を示します。 リソース記述フレームワーク(RDF)は、これらの関係がどのように表現されるかを形式化します。

たとえば、人々の間のRDF関係をグラフとして表すことができます。

人工知能検索アルゴリズムでは、問題の可能な解決策を検索します。

現在の検索位置は、問題の現在の「状態」であり、ノードとして表すことができます。

この状態から別の状態にトラバースする方法は、有向エッジで表すことができます。 エッジの色は、現在の状態を次の状態に変更する方法です。

以下に、ゲーム理論の例を示し、tic-tac-toeゲームの動きを示します。

私たちはゲームに勝つための最良の動きのセットを探しています。 各状態は、XとOの配置方法です。 Xには2つの勝利の道があることがわかります。

この例では、人工知能におけるグラフの重要性がわかります。 実際、人工知能の最初のプログラミング言語、つまりLISPについて言えることの基礎はグラフです。 厳密に言えば、 LISPの基本構造はリンクリストですが、後でツリーやグラフをリンクリストで作成できることがわかります。

グラフツリーは、代数式の解析と操作の便利な表現になります。 このアイデアは、ラムダ計算関数型プログラミングの基礎に由来しています。

以下の例では、単純な代数関数をグラフとして表す方法を確認できます。

化学、特に有機化学では、分子をグラフとして表すことができます。 色付きのノードは原子特性を持つ原子であり、エッジは原子間の結合です。 さらに、反応はグラフィック変換と見なすことができます。 さらに、化学反応のシステム全体は、化学反応ネットワークと見なすことができます。

ショ糖分子を3次元のグラフとして視覚化できます。

4. リンクリスト

プログラミングで一般的に役立つデータ構造のもう1つのセットは、リンクリストです。

リンクリストの基本要素は、2つのボックスを持つ要素です。1つはデータを持ち、もう1つは次の要素へのポインタを持ちます。

これらの要素を接続するには、基本的に3つの異なる可能性があります。

  • データのみ data ボックスには適切なデータがあり、nextボックスはnull(何も指していません)です。 これは「最後の」要素を表します。
  • リスト内のデータ data ボックスには情報があり、nextボックスには別の要素があります。
  • ポインター:データと次のボックスの両方が他の要素を指しています。 これは分岐を表します。

4.1. 配列とツリーのリンクリスト表現

このデータ構造は非常に柔軟です。

たとえば、連続する数字のセットをリンクリストとして表すことができます。

要素0から4はそれぞれ次の要素を指し、最後の要素5は何も指しません(ポインターとして null を持ちます)。

または、データボックス自体がポインタである場合は、任意のグラフを表すことができます。 data ボックスはノード情報であり、エッジは他の要素への次のポインターです。

前述のように、リンクリストは、1960年に開発された人工知能の第一言語であるLISPの基本構造です。 主なプログラミング言語がFORTRANのような数値の非再帰言語であったことを考えると、これは注目に値する成果です。

4.2. リンクリストの使用

使用するデータ構造の選択は、さまざまな要因によって異なります。

リンクリストと配列の両方が順序付きリストを表すことができることがわかります。 しかし、一般的な操作がこのリストに要素を挿入することである場合はどうなりますか? この操作の計算複雑さ、つまり所要時間はまったく異なります。

この点を、ベクトル表現とリンクリスト表現を使用して順序付きリストに数値を挿入する簡単な例で説明します。

配列に数値を挿入するには、最初にリストを割り当ててコピーを作成し、フィールドを追加する必要があります。

この操作の複雑さは、リストの長さによって異なります。 リストが大きくなるにつれて、このタスクを実行する時間も長くなります。 複雑さ表記では、これは O(n)です。

12個の数字の配列に余分な数字を挿入するプロセスを想像してみましょう。

ただし、リンクリストの場合、基本的な操作は、1つのポインターを新しい要素に移動することです。新しい要素のポインターをリストの残りの部分に設定します。

この操作は、リストの長さに依存しません。 リストがいくら大きくても、複雑さは同じです。 複雑さ表記では、これは O(1)です。

ここで、リンクリストとして表される配列に追加の要素を挿入するプロセスを想像してみましょう。

したがって、リンクリストを使用すると、計算量を大幅に節約できます。

5. スタックとキュー

スタックとキューは、オブジェクトをリストに入れる方法(またはプッシュ)と、オブジェクトを削除する順序(またはポップ)に関係するもう1つの便利なデータ構造のセットを表します。セット。

5.1. スタック

スタックは、たとえば本のスタックのように聞こえます。 オブジェクトをスタックにプッシュするたびに、そのオブジェクトは一番上に移動します。

本のスタックと同様に、スタックからオブジェクトをポップすると、それは上から来ます。 これを別の言い方で言うと、「後入れ先出し」LIFOです。

5つのオブジェクトをスタックにプッシュする方法と、配置した「最後の」オブジェクトが、ポップオフした「最初の」オブジェクトであることを確認しましょう。

5.2. キュー

待ち行列も、たとえば並んでいるなど、聞こえるとおりです。

オブジェクトをエンキューするたびに、そのオブジェクトはキューの後ろに追加されます。 オブジェクトをデキューすると、前面から取得します。 繰り返しますが、これを別の言い方で言うと、「先入れ先出し」(FIFO)です。

パイプラインにボールを追加する場合は、ボールをキューに入れます。 デキューする「最初の」ボールは、プロセスの開始時にキューに入れた最初のボールであることがわかります。

いくつかの追加作業を行うことで、特定のボールが優先キューの行の一部をスキップできるようにする方法を想像できます。

5.3. スタックとキューの使用

スタックとキューが同様の機能を持っていることがわかります。  たとえば、オブジェクトのセットが処理される順序を決定します。

スタックの一般的な使用法は「元に戻す」機能です。 アクションを実行すると、そのアクションはスタックの一番上に移動します。 そして、このアクションを「元に戻す」場合は、同じスタックの一番上から取得されます。

スタックのもう1つの一般的な使用法は、recursionです。 再帰呼び出しを行うときは、現在のコンテキストの状態をスタックの最上位に格納します。 再帰呼び出しから戻ると、スタックから最上位のコンテキストを取得して復元します。 たとえば、この図では、階乗を計算する再帰プログラムが、各再帰呼び出しの以前の呼び出し環境をどのように格納するかを示しています。 結果が返され、呼び出し元のステートメントに設定されていることがわかります。

タスクの分散について公平になりたいときはいつでもキューを使用できます。 たとえば、プリントアウトをプリンタに送信する場合です。 または、コンピューティングジョブをクラウドの中央処理装置に送信する場合。 やるべき仕事があるとき、それをキューの後ろに追加します。 仕事をする準備ができたら、前から次の仕事を選びます。

6. 概要

この記事では、プログラミングに役立ついくつかの一般的なデータ構造を紹介しました。

グラフなどのいくつかのデータ構造をいくつかの方法で表現しました。 また、構造間の相互関係を示す例を示しました。

また、配列やリンクリストなどのデータ構造の選択が、プロセスの複雑さに影響を与える可能性があることもわかりました。