抽象データ型とは何ですか？
1. 概要
このチュートリアルでは、リスト、キュー、スタックの3つの一般的なデータ型について説明します。 次に、は、各ADTのバリエーション、基本的な操作、およびデータ構造を使用した実装戦略を示します。
2. ADTの概要
データ型は、変数が格納できる値の型を定義または分類するために使用されます。 さらに、これらの値で許可される可能な操作についても説明します。 たとえば、integerデータ型は整数値を格納できます。 整数で可能な演算には、加算、減算、乗算、モジュロが含まれます。
抽象データ型（ADT）は、データ型の概念またはモデルです。 ADTにより、ユーザーはそのデータ型がどのように実装されているかを気にする必要がありません。 さらに、ADTはデータ型の関数の実装も処理します。 ここで、ユーザーは各データ型で事前定義された関数を使用して、あらゆる操作に使用できるようになります。
一般に、ADTでは、ユーザーはその方法を開示せずに何をすべきかを知っています。 これらの種類のモデルは、データ項目と関連する操作の観点から定義されています。
すべてのプログラミング言語で、さまざまな方法とロジックを使用してADTを実装しています。 ただし、言語に関係なく、そのADTに対して定義されている関連するすべての操作を実行できます。 たとえば、Cでは、ADTは主に構造を使用して実装されます。 一方、C ++またはJAVAでは、classを使用して実装されます。 ただし、操作はすべての言語で共通です。
ADTは、一般的で重要なデータ型です。 一般に、ADTは数学的または論理的な概念であり、さまざまな言語を使用してさまざまなマシンに実装できます。 さらに、それらは非常に柔軟性があり、言語やマシンに依存しません。
ADTには主に次の3つのタイプがあります。
3. リストの紹介
リストは同じデータ型の順序付けられたコレクションです。さらに、リストには有限数の値が含まれます。 同じリストに異なるデータ型を保存することはできません。 ここで、順序付けされているということは、リストがソートされていることを意味するわけではありませんが、適切に索引付けされています。 したがって、リストの最初の要素の場所がわかっている場合は、リスト全体に対して任意の操作を実行できます。
arrayを使用してリストを簡単に実装できます。 ただし、メモリ管理は、配列を使用してリストを実装するための大きなタスクです。 すべてのプログラミング言語で、配列の固定サイズを宣言する必要があります。 また、配列に指定できる重要な最大サイズはありません。 したがって、配列を使用して実装すると、リストがオーバーフローする場合があります。 一方、保存するデータが少ないと、使用可能なメモリを効率的に利用できません。
この問題を解決するために、構造またはクラスを使用してリストを実装します。構造またはクラスは動的であるため、ランタイムリストにデータを追加するスコープがあります。
3.1. リストの種類
リストには次の3つのタイプがあります。
順序付きリスト内の要素の継承された特性を使用して、すべての要素を昇順または降順で格納します。 順序付きリストの例は、アルファベット順または数字順に並べられたリストです。
順序付けされていないリストでは、要素は要素の特性から任意の順序で並べ替えられません。 したがって、ユーザーの都合に合わせて要素の順序を並べます。
インデックス付きリストでは、要素が配置されますが、それらの数値位置はインデックスと呼ばれます。したがって、インデックスを使用してリストから要素にアクセスできます。
3.2. リスト上の操作
リストで実行できる操作について説明しましょう。
リストの基本的な操作は、リストが空かどうかの確認、ある位置への要素の挿入、ある位置からの要素の削除、リスト全体の読み取りです。関数を見てみましょう：、、、、。
この関数は、リストに要素があるかどうかに関する情報を提供します。 リストに要素がない場合、それはnullまたは空のリストです。
リスト内の特定の場所に要素を挿入するために使用します。 ここで、はリスト内の要素を挿入する位置を示します。
リストから要素を削除するには、関数を使用します。 ここでは、リスト内の要素を削除する位置を示します。
リストからすべての要素を読み取るために使用します。
3.3. リストの実装
次に、リストの実装に使用できるデータ構造について説明します。 ここでは、配列とリンクリストのデータ構造を使用してリストを実装する方法について説明します。
配列を使用したリストの実装の最初のステップは、固定サイズの配列を宣言することです。 この実装は、配列内にリストを格納します。 リスト内の要素との間のインデックスを作成します。 ここで、はリスト内の要素の数を示します。
配列の実装に関する主な問題は、事前にサイズを宣言する必要があることです。たとえば、長さの1次元配列を考えてみましょう。 配列のサイズがいっぱいの場合は、より大きなサイズの配列を作成する必要があります。 その後、前の配列が占有していたメモリを解放する必要があります。
今、このリストはいっぱいです。 したがって、さらに要素を追加する必要がある場合は、より大きな配列を作成してリストを格納する必要があります。
一般に、配列はリストの実装には適していません。 さらに、アレイを使用した挿入と削除にはコストがかかります。 また、リストのサイズが事前にわからない場合もあります。
リストを実装するための2番目の選択肢は、リンクリストのような動的データ構造を使用することです。 配列を使用して実装されたリストは単純ですが、メモリ管理には複雑です。 実行時にリストのサイズを増やすためのプロビジョニングはありません。
この例では、は最初のノードのアドレスを格納するポインタです。 さらに、アドレスを保持する必要がないため、背面のアドレスはnullになります。 最初のノードのアドレスがわかっている場合は、リストのすべての操作を実行できます。
各要素にはインデックスが関連付けられているため、リスト内の要素へのアクセスには一定の時間がかかります。 したがって、リストから任意の要素にアクセスするための時間計算量はです。 また、リストの最後からの要素の挿入と削除は、リストのサイズに依存しません。 したがって、要素の最後からの挿入と削除には一定の時間がかかります。
リストの先頭にある要素の挿入または削除には時間がかかる場合があります。 ここでは、リストの長さに比例してすべての要素をシフトする必要があります。 したがって、その場合、時間計算量はになります。
4. キューの概要
queue は線形ADTであり、一方の端で挿入を実行し、もう一方の端で削除を実行できるという制限があります。 FIFO（先入れ先出し）の原理で動作します。 したがって、キューから削除される最初の要素は、最初に追加される要素です。 キューに格納できるデータ型は1つだけです。
キューには両端があります。 一方の端はリアエンドと呼ばれ、そこからデータを挿入できます。 もう一方の端は、キューからデータを取り出すフロントエンドです。
4.1. キューの種類
キューを4つのタイプに分割します。
単純なキューは、キューADTの最も単純な形式です。 後端からデータを挿入し、前端から要素を削除します。 さらに、単純なキューはFIFOに厳密に従います。
循環キューでは、キューの最初の要素がキューの最後の要素を指しているため、循環構造になっています。 単純なキューよりも優れた方法でメモリを利用します。
priority queue という名前の特別なキューは、キュー内の各要素の優先度を格納します。 優先キューは、各要素に関連付けられた優先度に基づいて、削除および挿入操作を処理します。
両端キューがFIFOルールに準拠していません。リアエンドとフロントエンドの両方から要素を挿入および削除できます。
4.2. キューでの操作
キューの基本的な操作を見てみましょう。
ここでキューのいくつかの基本的な機能について説明します：。
この関数を使用して、キューが空かどうかを確認します。 この関数は、指定された値をキューに挿入します。 特定の場所に値を追加することはできません。
キューから要素を削除します。 挿入関数と同様に、キューから要素を削除することはできません。 キューの前面からのみ要素を削除できます。
キューからすべての要素を読み取ります。 キューの前から後ろにすべての値を読み取ります。
4.3. キューの実装
配列を使用したキューの実装は非常に簡単です。 FIFOの原則に固執する必要があります。 挿入操作と削除操作の両方がフロントエンドまたはリアエンドのどちらからでも許可されます。この実装では、配列に要素を挿入するたびに1つの要素をシフトする必要があります。 最初、配列が空の場合、背面はです。 キューに挿入される各要素を後端からシフトします。
リンクリストのデータ構造を使用してキューを実装することもできます。 この実装では、リンクリストを使用したリストの実装と同じように、データを格納して次のノードにリンクするノードがあります。 唯一の違いは、ここでは2つのポインターを使用していることです。 リアには、リンクリストに最後に挿入された要素のアドレスが格納されます。 一方、frontは、リンクリストに最初に挿入された要素のアドレスを格納します。
キューへの挿入と削除の時間計算量はです。 ただし、最悪の場合、特定のキュー内の要素を検索するには時間がかかります。
5. スタックの概要
スタックはライナーADTであり、同じ端からの要素の挿入と削除に制限があります。これは、最初のプレートが最後に取り出されるプレートとなるプレートの山を作るようなものです。 LIFO（後入れ先出し）の原理に基づいて動作します。次の1種類のデータのみを格納します。
スタックには、プッシュとポップの2つのコア操作があります。 プッシュ操作は、特定の要素をスタックの一番上に挿入します。 ポップ操作は、最後に追加された要素をスタックから削除します。
5.1. スタックの種類
スタックは、大きく2つのカテゴリに分類できます。
レジスタスタックは、一般的にCPU上のメモリ位置を指し、スタックの最上位領域にある要素のアドレスを格納します。 スタックと比較して少量のデータしか含まれていません。
メモリスタックは、メモリスタックと比較して大量のデータを格納するメモリの場所も指します。 メモリレジスタのスタックの深さは柔軟です。
5.2. スタックでの操作
スタックの4つの基本的な操作について説明します。
この関数は、スタックが空かどうかを確認するために使用されます。 この関数を使用して、特定の要素または値をスタックに挿入できます。
スタックからの削除操作を実行します。 スタック内のすべての要素を読み取るために、を使用できます。
5.3. スタックの実装
1次元配列を使用してスタックを実装できます。最初のステップは、配列のサイズを定義することです。 重要なのは、配列から要素を挿入または削除するために、LIFOの原則に従う必要があるということです。 さらに、データを格納するための特別な変数 を定義します。最初は、スタックが空のときはです。 スタックに要素を挿入するときはいつでも、最後に挿入された要素を格納します。
リンクリストを使用してスタックを実装できます。ここでは、メモリを動的に割り当てることができるため、実行時にスタックのサイズを増やすことができます。 最後に追加されたノードのアドレスを格納する変数へのポインターがあります。 スタックから要素を削除するには、リンクリストの前のノードを指すことにより、変数が指す要素を削除します。 最初に、スタックが空の場合、nullを指します。
スタックからの要素の挿入と削除の時間計算量はになります。 スタックから最後の要素を削除したい場合でも、時間計算量はになります。
6. 結論
このチュートリアルでは、リスト、キュー、スタックの3つの一般的なADTについて説明しました。 各ADTのバリエーションを紹介しました。 最後に、各ADTの基本的な操作と可能な実装についても説明しました。
