introduction data structures c
C ++のデータ構造に関する入門チュートリアル。
「データ構造は、プログラム全体が効率的に機能できるように、プログラムが効率的かつ迅速にデータにアクセスするのに役立つデータの組織化されたコレクションとして定義できます。 「「
プログラミングの世界では、データが中心であり、すべてがデータを中心に展開していることを私たちは知っています。データの保存、検索、並べ替え、整理、アクセスなど、すべてのデータ操作を効率的に行う必要があります。そうしないと、プログラムは成功しません。
=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。
学習内容：
概要概要
動的なソリューションを構築するのに役立つ、データを保存する最も効率的な方法を見つける必要があります。データ構造は、そのようなソリューションの構築に役立ちます。
データを構造に編成または配置する際、配置がほぼ現実世界のオブジェクトを表すようにする必要があります。第二に、この配置は、誰でも簡単にアクセスして必要なときにいつでも処理できるように、十分に単純でなければなりません。
このシリーズでは、基本的なデータ構造と高度なデータ構造について詳しく学習します。また、データ構造に対して実行できるさまざまな検索および並べ替えの手法についても詳しく学習します。
このチュートリアルシリーズを学習した後、読者は各データ構造とそのプログラミングに精通する必要があります。
データ構造を扱うときに使用するいくつかの用語を見てみましょう。
例えば、特定の学生を連れて行きます。 生徒は、絵で表されているように、次の詳細を知ることができます。
- データ： 基本値です。上の図では、学生のロール番号をデータにすることができます。
- グループアイテム： これは、複数のサブアイテムを持つデータアイテムです。上の図では、Student_nameには名と姓があります。
- 記録： データ項目のコレクションです。上記の例では、学生のロール番号、名前、クラス、年齢、学年などのデータ項目が一緒にレコードを形成します。
- エンティティ： これはレコードのクラスです。上の図では、学生はエンティティです。
- 属性またはフィールド： エンティティのプロパティは属性と呼ばれ、各フィールドは属性を表します。
- ファイル： ファイルはレコードのコレクションです。上記の例では、学生エンティティは数千のレコードを持つことができます。したがって、ファイルにはこれらすべてのレコードが含まれます。
さまざまなデータ構造を使用するときに時々使用するため、読者はこれらすべての用語に注意する必要があります。
データ構造はプログラムの主要な構成要素であり、プログラマーとして、使用するデータ構造に注意する必要があります。使用する正確なデータ構造は、プログラミングに関する限り、最も難しい決定です。
プログラミングにおけるデータ構造の必要性について説明しましょう。
プログラミングにおけるデータ構造の必要性
データ量が増え続けると、アプリケーションはますます複雑になり、プログラマーがこのデータとソフトウェアを管理することが難しくなります。
通常、アプリケーションはいつでも次のハードルに直面する可能性があります。
＃1）大量のデータの検索： 大量のデータが処理および保存されているため、いつでも特定のデータを検索するためにプログラムが必要になる場合があります。データが大きすぎて適切に整理されていない場合、必要なデータを取得するのに長い時間がかかります。
データ構造を使用してデータを保存および整理すると、データの取得がより速く簡単になります。
＃2）処理速度： データがまとまっていないと、データの取得とアクセスに多くの時間が浪費されるため、処理速度が低下する可能性があります。
保存しながらデータ構造内でデータを適切に整理すれば、毎回データを取得して整理するなどの作業に時間を無駄にすることはありません。代わりに、データの処理に集中して、目的の出力を生成できます。
＃3）複数の同時リクエスト： 最近の多くのアプリケーションは、データを同時に要求する必要があります。これらの要求は、アプリケーションをスムーズに実行するために効率的に処理する必要があります。
データがランダムに保存されている場合、すべての同時リクエストを同時に処理することはできません。したがって、同時リクエストのターンアラウンドタイムを最小限に抑えるために、データを適切なデータ構造に配置することをお勧めします。
データ構造の分類
C ++で使用されるデータ構造は、次のように分類できます。
データ構造は、データを整理する方法です。したがって、示されているデータ構造を、プリミティブまたは標準のデータ構造と、非プリミティブまたはユーザー定義のデータ構造に分類できます。
C ++でサポートされているすべてのデータ型を見てきました。これはデータを整理する方法でもあるため、標準のデータ構造であると言えます。
他のデータ構造は非プリミティブであり、ユーザーはプログラムで使用する前にそれらを定義する必要があります。これらのユーザー定義のデータ構造は、線形データ構造と非線形データ構造にさらに分類されます。
線形データ構造
線形データ構造では、すべての要素が線形または順次に配置されます。線形データ構造の各要素には、先行要素（前の要素）と後続要素（次の要素）があります。
線形データ構造は、静的データ構造と動的データ構造にさらに分けられます。静的データ構造は通常、固定サイズであり、コンパイル時にサイズが宣言されると、変更できません。動的データ構造は、サイズを動的に変更し、それに対応することができます。
線形静的データ構造の最も一般的な例は配列です。
アレイ
配列は、同じタイプの要素の順次コレクションです。配列の各要素には、配列のインデックスまたは添え字と呼ばれる配列内の位置を使用してアクセスできます。配列の名前は、配列の最初の要素を指します。
上に示したのは、n個の要素の配列「a」です。要素には0からn-1までの番号が付けられています。配列のサイズ（この場合はn）は、配列の次元とも呼ばれます。上の図に示すように、配列の名前は配列の最初の要素を指しています。
配列は最も単純なデータ構造であり、添え字を使用して要素に直接アクセスできるため効率的です。配列の3番目の要素にアクセスする場合は、a (2)と言うだけです。
ただし、配列要素を追加または削除することは困難です。したがって、配列は、単純なアプリケーションまたは要素の追加/削除が不要なアプリケーションでのみ使用します。
一般的な線形動的データ構造は、リンクリスト、スタック、およびキューです。
リンクリスト
リンクリストはノードのコレクションです。各ノードには、データ要素と次のノードへのポインタが含まれています。ノードは動的に追加および削除できます。リンクリストは、各ノードが次の要素へのポインタのみを持つ単一リンクリストにすることができます。最後の要素では、次のポインタがnullに設定されます。
二重リンクリストでは、各ノードに2つのポインターがあり、1つは前のノードへ、もう1つは次のノードへのポインターです。最初のノードの場合、前のポインターはnullであり、最後のノードの場合、次のポインターはnullです。
上の図に示すように、リストの最初はヘッドと呼ばれ、リンクリストの最後はテールと呼ばれます。上に示したように、各ノードには次の要素へのポインタがあります。次のノードへのポインタを変更することで、要素を簡単に追加または削除できます。
スタック
スタックは線形データ構造であり、要素はスタックの「トップ」と呼ばれる一方の端からのみ追加または削除できます。このように、スタックはLIFO（後入れ先出し）タイプのメモリアクセスを示します。
上に示したように、スタック内の要素は常に一方の端で追加され、同じ端からも削除されます。これは、スタックの「トップ」と呼ばれます。要素が追加されると、その要素はスタックに押し下げられ、スタックの一番上が1つ増加します。
同様に、要素が削除されると、スタックの最上位がデクリメントされます。スタックが空の場合、スタックの最上位は-1に設定されます。スタックで実行される2つの主要な操作「プッシュ」と「ポップ」があります。
キュー
キューは、要素が「リア」と呼ばれる一方の端で追加され、「フロント」と呼ばれるもう一方の端から削除される、さらに別の線形データ構造です。キューは、FIFO（先入れ先出し）タイプのメモリアクセス方法を示します。
上の図は、リアエンドとフロントエンドのキューを示しています。キューが空の場合、リアポインタとフロントポインタは互いに一致します。
非線形データ構造
非線形データ構造では、データは順番に配置されるのではなく、非線形に配置されます。要素は、非線形配置で相互に接続されています。
非線形データ構造はツリーとグラフです。
Chrome用の無料ポップアップブロッカー
木
ツリーは、要素間に階層関係を持つ非線形のマルチレベルデータ構造です。ツリーの要素はノードと呼ばれます。
一番上のノードはツリーのルートと呼ばれます。ルートは1つ以上の子ノードを持つことができます。後続のノードには、1つ以上の子ノードを含めることもできます。子ノードを持たないノードはリーフノードと呼ばれます。
上の図では、6つのノードを持つツリーを示しています。これらの3つのノードのうち、リーフノードがあり、最上位の1つのノードがルートで、他のノードが子ノードです。ノードの数、子ノードなど、またはノード間の関係に応じて、さまざまなタイプのツリーがあります。
グラフ
グラフは、と呼ばれるノードのセットです。 頂点 と呼ばれるリンクによって互いに接続されています エッジ 。グラフの内部にサイクルを含めることができます。つまり、同じ頂点を特定のパスの開始点と終了点にすることができます。木は決して周期を持つことはできません。
上の図は無向グラフです。有向矢印を使用してエッジを表す有向グラフを作成することもできます。
データ構造の操作
すべてのデータ構造は、その要素に対してさまざまな操作を実行します。
これらはすべてのデータ構造に共通であり、次のようにリストされています。
- 検索： この操作は、特定の要素またはキーを検索するために実行されます。最も一般的な検索アルゴリズムは、シーケンシャル/リニア検索とバイナリ検索です。
- 並べ替え： 並べ替え操作では、データ構造内の要素を特定の順序で昇順または降順で配置します。データ構造に使用できるさまざまな並べ替えアルゴリズムがあります。それらの中で最も人気があるのは、クイックソート、選択ソート、マージソートなどです。
- 挿入： 挿入操作では、データ構造に要素を追加します。これは最も重要な操作であり、要素を追加した結果、配置が変更され、データ構造が損なわれないように注意する必要があります。
- 削除： 削除操作は、データ構造から要素を削除します。削除操作の場合も、挿入を考慮すべき条件と同じ条件が満たされます。
- トラバース： 構造内のすべての要素にアクセスすると、データ構造をトラバースすると言います。データ構造に対して特定の操作を実行するには、トラバースが必要です。
以降のトピックでは、最初に、データ構造に対して実行されるさまざまな検索および並べ替えの手法について学習します。
データ構造の利点
- 抽象化： 多くの場合、データ構造は抽象データ型として実装されます。ユーザーは、基盤となる実装について心配することなく、外部インターフェイスにのみアクセスします。したがって、データ構造は抽象化レイヤーを提供します。
- 効率： データを適切に編成すると、データに効率的にアクセスできるため、プログラムがより効率的になります。次に、要件に応じて適切なデータ構造を選択できます。
- 再利用性： 設計したデータ構造を再利用できます。それらはライブラリにコンパイルしてクライアントに配布することもできます。
結論
これで、データ構造の概要に関するこのチュートリアルを終了します。このチュートリアルでは、各データ構造を簡単に紹介しました。
以降のチュートリアルでは、さまざまな検索および並べ替えの手法とともに、データ構造について詳しく説明します。
=> 絶対C ++トレーニングシリーズについては、ここをクリックしてください。
推奨読書
- C ++データ型
- イラスト付きのC ++でのデータ構造のキュー
- プログラミングを排除するための2021年のトップ10データサイエンスツール
- ユーザー定義変数を使用したJMeterデータのパラメーター化
- データ収集戦略を備えた10以上の最高のデータ収集ツール
- 2021年にデータニーズを満たすための10以上の最高のデータガバナンスツール
- テストデータ管理用のIBMRational QualityManagerのデータプール機能
- イラスト付きのC ++でのスタックデータ構造