コンピューターのデータ構造とは何ですか?

データ構造は、コンピュータがデータを保存および整理するための方法です。相互に 1 つ以上の特定の関係を持つデータ要素のコレクションを指します。データの論理構造とデータの物理構造を研究します。データ間の相互関係を確認し、この構造に適切な操作を定義し、対応するアルゴリズムを設計し、これらの操作後に得られる新しい構造が元の構造タイプを維持していることを確認します。

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

データ構造

データ構造は、コンピューターがデータを保存および整理する方法です。データ構造とは、相互に 1 つ以上の特定の関係を持つデータ要素のコレクションを指します。多くの場合、データ構造を慎重に選択すると、操作効率やストレージ効率が向上します。データ構造は、多くの場合、効率的な検索アルゴリズムやインデックス付け技術に関連しています。

名詞の定義

データ構造とは、相互に 1 つ以上の関係を持つデータ要素のコレクション、およびデータ要素間の関係を指します。コレクション、それらの間の関係。
Data_Structure=(D,R)
として記録されます。ここで、D はデータ要素のセット、R はセット内のすべての要素間の関係の有限セットです。

(1) よく使われる構造

1. 配列：プログラミングにおいて、処理の便宜上、同じ型をまとめたものいくつかの変数は順序付けられた形式で編成されます。同様のデータ要素を順番に並べたものを配列と呼びます。 C 言語では、配列は構築されたデータ型です。配列は、基本データ型または構築型の複数の配列要素に分解できます。したがって、配列要素の種類に応じて、配列は数値配列、文字配列、ポインタ配列、構造体配列などのさまざまなカテゴリに分類できます。

2. スタック: これは、一端でのみ挿入および削除できる特殊な線形リストです。先入れ後出しの原則に従ってデータを格納します。最初に入力されたデータはスタックの一番下にプッシュされ、最後のデータはスタックの一番上に置かれます。データを読み取る必要がある場合、データはポップされます。スタックの先頭から（最後のデータが最初に読み出されます）。

3. キュー: テーブルの前端 (フロント) での削除操作とテーブルの後端 (後部) での挿入操作のみを許可する特殊な線形テーブル。挿入操作を実行する端はキューの末尾と呼ばれ、削除操作を実行する端はキューの先頭と呼ばれます。キューは、「先入れ先出し」または「後入れ後出し」の原則に従ってデータを整理します。キュー内に要素が存在しない場合、それは空のキューと呼ばれます。

4. リンク リスト: 物理ストレージ ユニット上の非連続かつ非順次のストレージ構造です。線形構造または非線形構造のいずれかを表すことができます。データ要素の論理順序は次のとおりです。リンク リストによるポインタのリンク順序。リンク リストは一連のノードで構成され (リンク リストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。各ノードは 2 つの部分で構成されます。1 つはデータ要素を格納するデータ フィールドで、もう 1 つは次のノードのアドレスを格納するポインタ フィールドです。

5. 木: n (n>0) 個のノードを含む有限集合 K であり、K には関係 N が定義されます。N は次の条件を満たします。 1) ノード K0 は 1 つだけあり、関係 N に対する先行ノードはありません。K0 はツリーのルート ノードと呼ばれます。ルートと呼ばれます。

(2) K0 を除き、K の各ノードにはリレーションシップ N の先行ノードが 1 つだけあります。

(3) K の各ノードは、関係 N に対して m 個の後続ノード (m>=0) を持つことができます。

6. グラフ: ノードの有限集合 V とエッジの集合 E で構成されます。このうち、木構造と区別するために、グラフ構造ではノードを頂点と呼ぶことが多く、エッジは頂点の順序対であり、2つの頂点の間にエッジがある場合、2つの頂点が隣接関係にあることを意味します。

7. ヒープ: コンピューター サイエンスでは、ヒープは特別なツリー データ構造であり、各ノードには値があります。通常、ヒープのデータ構造と呼ばれるものは、バイナリ ヒープを指します。ヒープの特徴は、ルート ノードが最小 (または最大) の値を持ち、ルート ノードの 2 つのサブツリーもヒープであることです。

8. ハッシュ テーブル (ハッシュ テーブルとも呼ばれます): 構造内に K に等しいキーを持つレコードがある場合、それは f(K) の格納場所に存在する必要があります。したがって、検索対象のレコードを比較することなく直接取得できます。この対応関係fをハッシュ関数(Hash function)といい、この考え方に基づいて作られたテーブルがハッシュテーブルです。

9. 8 つのソート アルゴリズム: ソート アルゴリズムは内部ソートと外部ソートに分けることができます。内部ソートはデータ レコードがメモリ内でソートされることですが、外部ソートはソートされたデータが非常に大きくて収容できないためです。レコードを並べ替えるには、並べ替えプロセス中に外部ストレージにアクセスする必要があります。一般的な内部ソート アルゴリズムには、挿入ソート、ヒル ソート、選択ソート、バブル ソート、マージ ソート、クイック ソート、ヒープ ソート、基数ソートなどがあります。

1. データの論理構造: データ要素間の論理的関係を反映するデータ構造を指します。論理的関係とは、データ要素間の前後の関係を指し、それらはデータ要素間の関係を指します。コンピュータ 保存場所は関係ありません。

論理構造には次のものが含まれます:

1) Set
データ構造内の要素間には、「同じセットに属している」という点以外の関係はありません。

2) 線形構造
データ構造内の要素は 1 対 1 の関係を持ちます;

3) ツリー構造
データ構造内の要素は 1 対多の関係を持ちます関係;

4) グラフィック構造

データ構造内の要素には多対多の関係があります。

2. データの物理構造: は、コンピュータの記憶領域におけるデータの論理構造の記憶形式を指します。
データの物理構造は、コンピューター内のデータ構造の表現 (イメージとも呼ばれます) であり、データ要素のマシン内表現と関係のマシン内表現が含まれます。具体的な実装方法にはシーケンス、リンク、インデックス付け、ハッシュ化などが含まれるため、データ構造は 1 つ以上のストレージ構造として表現できます。
データ要素のマシン内表現 (マッピング方法): データ要素は、バイナリ ビットのビット列によって表現されます。このビット列は通常ノードと呼ばれます。データ要素が複数のデータ項目で構成される場合、ビット列内の各データ項目に対応するサブビット列をデータ フィールドと呼びます。したがって、ノードはデータ要素のマシン内表現 (またはマシン内イメージ) です。関係のオンマシン表現 (マッピング方法): データ要素間の関係のマシン上表現は、シーケンシャル イメージと非シーケンシャル イメージに分けることができます。一般的に使用されるストレージ構造には、シーケンシャル ストレージ構造とチェーン ストレージ構造の 2 つがあります。シーケンシャル マップは、メモリ内の相対位置によってデータ要素間の論理関係を表します。非順次イメージは、要素の格納場所を示すポインターを使用して、データ要素間の論理関係を表します。

3. データ構造の操作

一般に、データ構造は、何らかの論理に従って編成されたデータ要素で構成されていると考えられています。の接続。データ要素間の論理的関係の記述は、データの論理構造と呼ばれます。データはコンピュータに格納されなければならず、データの格納構造は、コンピュータにおけるデータ構造とその表現の実装形式です。さらに、データ構造について議論するときは、このタイプのデータに対して実行される操作が意味があるかどうかについても議論する必要があります。論理データ構造には複数のストレージ構造を含めることができ、さまざまなストレージ構造がデータ処理の効率に影響します。

多くの種類のプログラムの設計において、データ構造の選択は設計上の基本的な考慮事項です。多くの大規模システムの構築経験から、システム導入の難易度やシステム構築の品質は、最適なデータ構造を選択するかどうかに大きく左右されることがわかります。多くの場合、データ構造が決まれば、アルゴリズムは簡単に得られます。場合によっては、状況が逆になり、特定のアルゴリズムに適合するデータ構造を選択します。いずれの場合も、適切なデータ構造を選択することが非常に重要です。
データ構造を選択したらアルゴリズムも決まります システム構築の鍵となるのはアルゴリズムではなくデータです。この洞察は多くのソフトウェア設計手法とプログラミング言語の出現につながり、オブジェクト指向プログラミング言語もその 1 つです。
コンピュータが特定の問題を解決する場合、通常は次の手順を実行する必要があります。まず、特定の問題から適切な数学モデルを抽出し、次にその数学モデルを解決するためのアルゴリズム (アルゴリズム) を設計し、最後にプログラムをコンパイルし、最終的な解決策が得られるまでテストと調整を行います。
数学的モデルの探索の本質は、問題を分析し、動作オブジェクトを抽出し、これらの動作オブジェクト間の関係を見つけて、それらを数学的言語で記述することです。人々がコンピューターを使用して数値計算の問題を処理する場合、使用される数学モデルは数式で記述されます。一般に、関係するオペランドは単純な整数、実数、論理データであるため、プログラマはデータの保存や編成よりもプログラミング スキルに主に焦点を当てます。しかし、コンピュータ応用のより多くの分野は「非数値計算問題」です。その数学モデルは数式ではなく、データ構造によって記述されます。このような問題を解決する鍵は、非数値計算問題を記述する適切なデータ構造を設計することです。 . 数値問題の数学モデルは、線形表、ツリー、グラフなどの構造によって記述されます。
コンピュータ アルゴリズムはデータの構造と密接に関係しています。アルゴリズムはすべて特定のデータ構造に依存しています。データ構造はアルゴリズムの選択と効率に直接関係しています。この操作はコンピュータによって実行され、対応する挿入、削除、および変更アルゴリズムの設計が必要になります。つまり、データ構造には、それぞれの構造タイプで定義されるさまざまな操作のアルゴリズムも与える必要があります。データ オブジェクトは、同じプロパティを持つデータ要素のコレクションであり、データのサブセットです。データ オブジェクトは有限または無限の場合があります。データ処理とは、データの検索、挿入、削除、結合、並べ替え、統計、単純な計算などの操作プロセスを指します。

(2) 構造分類

データ構造とは、同じデータ要素クラス内のデータ要素間の関係を指します。データ構造は、それぞれ論理構造、記憶構造（物理構造）、データ操作です。データの論理構造は、特定の問題から抽象化された数学的モデルです。データ要素の数学的特性とその関係を記述します。論理構造は単にデータ構造と呼ばれることもあります。論理構造は、コンピュータ ストレージ内のイメージであり、正式には (K, R) (または (D, S)) として定義されます。ここで、K はデータ要素の有限セット、R は K 上の関係の有限セットです。

データ要素間の関係のさまざまな特性に従って、通常、次の 4 つの基本的な構造タイプがあります。

⑴ セット構造。この構造体のデータ要素間の関係は「同じ集合に属する」ということになります。

⑵線形構造。この構造のデータ要素間には 1 対 1 の関係があります。

⑶ツリー構造。この構造のデータ要素間には 1 対多の関係があります

⑷グラフィック構造。この構造のデータ要素間には多対多の関係があり、ネットワーク構造とも呼ばれます。上で紹介したデータ構造の概念から、データ構造には 2 つの要素があることがわかります。 1 つはデータ要素のコレクションであり、もう 1 つは関係のコレクションです。正式には、データ構造は通常タプルで表すことができます。

データ構造の形式は次のように定義されます: データ構造はタプル: Data_Structure=(D, R)、ここで D はデータ要素の有限セット、R は D 上の関係の有限セットです。線形構造の特徴は、データ要素間に線形の関係があり、データ要素が「次々に配置される」ことです。線形テーブル内のデータ要素のタイプが同じであるか、線形テーブルは同じタイプのデータ要素で構成される線形構造です。実際の問題では線形テーブルの例が数多くあります。たとえば、学生ステータス情報テーブルは線形テーブルです。テーブル内のデータ要素のタイプは学生タイプです。文字列も線形テーブルです。データのタイプテーブル内の要素は文字タイプなどです。
線形テーブルは、最も単純かつ基本的で、最も一般的に使用される線形構造です。線形テーブルは、同じデータ型を持つ n (n>=0) 個のデータ要素の有限シーケンスであり、通常: (a1, a2,...ai-1, ai, ai 1,...an) として記録されます。ここで、 n はテーブルの長さであり、 n=0 の場合、それは空のリストと呼ばれます。順次保存と連鎖保存の2つの保存方法があり、主な基本操作は挿入、削除、検索です。

コンピュータ内のデータ構造の表現(イメージ)は、データの物理(記憶)構造と呼ばれます。これには、データ要素の表現と関係の表現が含まれます。データ要素間の関係には、逐次マッピングと非逐次マッピングという 2 つの異なる表現方法があり、したがって、2 つの異なる記憶構造、すなわち、逐次記憶構造と連鎖記憶構造が得られます。

シーケンシャルストレージ方式: 論理的に隣接するノードを物理的に隣接するストレージユニットに格納する方式であり、ノード間の論理関係がストレージユニットの隣接関係に反映されることから、このストレージ表現はシーケンシャルストレージ構造と呼ばれます。シーケンシャル ストレージ構造は最も基本的なストレージ表現方法であり、通常はプログラミング言語の配列を使用して実装されます。

リンク格納方式: 論理的に隣接するノードが物理的にも隣接している必要はなく、ノード間の論理関係は追加のポインタ フィールドによって表されます。結果として得られるストレージ表現は、連鎖ストレージ構造と呼ばれます。連鎖ストレージ構造は、通常、プログラミング言語のポインタ型を使用して実装されます。

インデックス ストレージ方式: ストレージ ノード情報の確立に加えて、追加のインデックス テーブルを使用して、ノードのアドレスを特定します。

ハッシュ格納方式: ノードのキーワードに基づいてノードの格納アドレスを直接計算します。

データ構造は、論理的に(論理構造:データ要素間の論理的な関係)、線形構造と非線形構造に分けることができます。線形構造の逐次記憶構造は逐次アクセス記憶構造であり、線形リストの連結記憶構造はランダムアクセス記憶構造である。線形テーブルがチェーン ストレージで表される場合、すべてのノード間のストレージ ユニット アドレスは連続的または不連続的になる可能性があります。論理構造は、データ要素自体に含まれる形式、内容、相対位置、ノードの数とは何の関係もありません。

(3) アルゴリズムの構造

アルゴリズムの設計はデータ (論理) 構造に依存し、アルゴリズムの実装はデータに依存します。使用されるストレージ構造に応じて。データの記憶構造は、本質的には、その論理構造をコンピュータのメモリ上に実現するものであり、データの論理構造を包括的に反映するために、メモリ上のデータのイメージには、データ要素間の情報とデータ要素間の情報という2つの側面が含まれます。間の関係。異なるデータ構造には、対応する演算があります。データ操作とは、データの論理構造に基づいて定義された、検索、挿入、削除、更新、並べ替えなどの操作アルゴリズムです。

データ構造は、データ型やデータ オブジェクトとは異なり、データ型のデータ オブジェクトを記述するだけでなく、データ オブジェクトの要素間の関係も記述します。

データ型は、値のコレクションと、この値セットに対して定義された一連の操作です。データ型は、アトミック型と構造型の 2 つのカテゴリに分類できます。一方、プログラミング言語では、すべてのデータは特定のデータ型に属します。型は、データの値の範囲、データの保存方法、および許可される操作を明示的または暗黙的に指定します。データ型は、プログラミングで実装されたデータ構造であると考えることができます。一方、プログラミング プロセス中に新しいデータ構造を導入する必要がある場合、データ ストレージ構造は常にプログラミング言語によって提供されるデータ型を使用して記述されます。コンピュータで表現されるデータの最小単位は、ビットと呼ばれる 2 進数の 1 ビットです。データ要素を表すために、複数のビットを組み合わせたビット列を使用しますが、このビット列は通常、要素またはノードと呼ばれます。データ要素が複数のデータ項目で構成される場合、ビット列内の各データ項目に対応するサブビット列をデータ フィールドと呼びます。要素またはノードは、コンピューター内のデータ要素のイメージとして見ることができます。

ソフトウェア システム フレームワークは、運用ではなくデータに基づいて構築される必要があります。抽象データ型を含むソフトウェア モジュールには、定義、表現、実装の 3 つの部分が含まれている必要があります。

すべてのデータ構造には、それに密接に関連した一連の操作が存在する必要があります。論理構造が同じでも演算の種類や回数が異なれば、データ構造の役割も異なります。

データ構造が異なれば操作セットも異なりますが、次の操作は不可欠です:

1. 構造の生成;
2. 構造の破壊;
3. 構造内で指定された条件を満たすデータ要素を検索します;
4. 新しいデータ要素を構造に挿入します;
5. 構造内の既存のデータ要素を削除します;
6. トラバース。

抽象データ型: 数学的モデルとそのモデル上で定義された一連の操作。抽象データ型は、実際にはこのデータ構造の定義です。それは、データの論理構造と、この構造に対する一連のアルゴリズムを定義するためです。抽象データ型は、(D、S、P) の 3 つの組み合わせで表すことができます。 D はデータ オブジェクト、S は D に対する関係のセット、P は D に対する基本操作のセットです。 ADT の定義は、ADT 抽象データ型名: {データ オブジェクト: (データ要素の集合)、データ関係: (データ関係タプルの組み合わせ)、基本演算: (演算関数のリスト)}; ADT 抽象データ型名; です。抽象データ型には 2 つの重要な特性があります。

データの抽象化: ADT を使用してプログラムによって処理されるエンティティを記述する場合、その本質的な特性、完了できる機能、および外部ユーザーとのインターフェイスに重点が置かれます (つまり、外部の世界がそれを使用する方法です）。

データのカプセル化: エンティティの外部特性を内部実装の詳細から分離し、内部実装の詳細を外部ユーザーから隠します。

データは情報の媒体であり、コンピューターによって認識、保存、処理されます。それはコンピュータプログラムによって処理される原材料であり、アプリケーションはあらゆる種類のデータを処理します。コンピュータ サイエンスにおいて、いわゆるデータはコンピュータ処理の対象であり、数値データまたは非数値データの場合があります。数値データとは、主に工学計算、科学計算、事務処理などで使用される整数、実数、複素数のことであり、非数値データには文字、テキスト、グラフィックス、画像、音声などが含まれます。

データ要素 (Data Element) はデータの基本単位です。さまざまな条件下では、データ要素は要素、ノード、頂点、レコードなどと呼ばれることもあります。例えば、学生情報検索システムにおける学生情報テーブルのレコードをデータ要素と呼びます。データ要素は、複数のデータ項目（データ項目）から構成される場合があり、たとえば、学業状況管理システムの学生情報テーブルの各データ要素は、学生記録です。データ項目としては、学籍番号、氏名、性別、出身地、生年月日、成績などが含まれます。これらのデータ項目は、データ処理の際に分割できない最小単位である「基本項目」と呼ばれる生徒の性別や出身地などの2種類に分類でき、もう1つは「組み合わせ項目」と呼ばれます。学生の成績など、数学、物理、化学などのより小さな用語に細分化することもできます。通常、実際の応用問題を解決する際には、各生徒の記録が基本単位としてアクセスされ、処理されます。

データ オブジェクト (データ オブジェクト) またはデータ要素クラス (データ要素クラス) は、同じプロパティを持つデータ要素のコレクションです。特定の問題では、データ要素はすべて同じプロパティを持ち (要素値は必ずしも等しいとは限りません)、同じデータ オブジェクト (データ要素クラス) に属し、データ要素はデータ要素クラスのインスタンスです。たとえば、交通勧告システムの交通ネットワークでは、すべての頂点がデータ要素クラスです。頂点 A と頂点 B はそれぞれ都市を表し、データ要素クラスの 2 つのインスタンスです。それらのデータ要素の値は A です。そしてB.データ構造とは、相互に 1 つ以上の関係を持つデータ要素のコレクションを指します。どのような問題においても、データ要素は孤立しているわけではなく、データ要素間には何らかの関係があり、このデータ要素間の関係を構造と呼びます。

関連知識の詳細については、FAQ 列をご覧ください。

以上がコンピューターのデータ構造とは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。