データ構造とアルゴリズム(一)——関連概念
3887 ワード
誘引子
Algorithms+Data Structures=Prograams(アルゴリズム＋データ構造＝プログラム)
プログラム設計には、アルゴリズム、データ構造、プログラミング言語の3つの部分が含まれています.アルゴリズムは問題を解くためのプロセス記述であり、データ構造は、要求された問題を解決するためのデータの記憶とアルゴリズムポリシーの実現をサポートしています.
データ構造は何を研究しますか?
データ構造はデータ間の関係を研究し、与えられたデータに対して可能な動作を研究し、データをどのように組織するかによってこれらの動作を効率的に実現することができる.
関連概念:
データ:データは客観的事物の符号表現であり、情報の担体である.
データ要素:データ要素はデータセットの中の一つの個体で、コンピュータプログラムの加工処理の基本単位です.
データ項目:データ要素は複数のデータ項目から構成されます.
データオブジェクト:同じ性質を持つデータ要素のセット.
データ構造:構造のあるデータ要素のセット.データ構造は4元のグループで表すことができます.Structure=(D,L,S,O)
D(Data):データ要素の限定セットは、記憶と操作の対象です.
L(Logical Structure):データ要素セットDにおけるデータ要素間の客観的な存在関係の有限セットを論理構造と呼ぶ.
S(Strage Structure):データ要素セットDとデータ要素の間の関係セットLは、コンピュータ内の記憶表現であり、記憶構造または物理構造と呼ばれる.
O(Operation):データ要素セットDに規定されている操作のセットです.演算とも呼ばれます.データ構造の基本的な操作は、通常、データ構造の作成と廃棄、データ要素の検索、挿入、削除、遍歴、ソートなどがあります.
＊二元(D,R)とも定義されていますが、D(Data)はデータ要素の限定セットであり、R(Relationsip)はDにおけるデータ要素間の客観的な存在関係の限定セットです.
論理構造:データ要素の間に客観的に存在する関係は、データがコンピュータにどのように記憶されているかに関係なく、通常はデータの論理構造をデータ構造と略称する.
論理構造の区分(一) I.線形構造:あり、最初と一つの端末の結点のみであり、すべての結点は最大で一つの直接前のめりと一つの直接後継者のみである. 例えば、線形表、スタック、キュー、列 II.非線形構造:一つの結点は複数の直接的な前のめりと直接的な後継があるかもしれない. 例えば、木、図などです.
論理構造の区分(二) I.セット:構造中のデータ要素は同じタイプに属する以外、他の関係はありません. II.線形構造:構造中のデータ要素の間に一対一の関係がある. III.ツリー構造:構造中のデータ要素の間にペア以上の関係がある. IV.図のような構造(網状構造):構造中のデータ要素の間に複数対の関係が存在する.
記憶構造:データの記憶構造は物理構造とも呼ばれ、データ構造の中の要素の表示と要素間関係の表現を含む、コンピュータにおけるデータ構造の記憶表現を指す.
記憶構造の区分:
I.順次記憶構造:論理的に隣接する要素を物理構造の隣接する記憶手段に記憶する.データ要素のメモリ内の相対的な位置によってデータ要素間の論理関係を表します.
II.チェーン記憶構造:データ要素にアドレス領域または補助構造を追加し、データ要素間の関係を保存するために使用します.データ要素のアドレスを示すポインタによって、データ要素間の論理関係を表します.論理的に隣接する要素がメモリ内の位置にも隣接していることは要求されません.プログラム設計言語におけるポインタタイプまたはインデックス構造によってしばしば実現されます.
III.ハッシュ格納構造:ハッシュ構造とも呼ばれる.キーワードを直接計算することによって、データ要素の格納位置が得られる.データ要素に対する記憶と検索は、キーワードを直接計算することによって得られる.
注:同じ論理構造は、異なる記憶構造を使用して実装することができます.記憶構造の選択は、アルゴリズムの実現とアルゴリズムの時間と空間要求を主に考慮します.様々な基本的な記憶構造は、単独で使用することも、組み合わせて使用することもできます.
データタイプと抽象データタイプ
データ構造はプログラム言語自体が実現したデータ構造と理解できます.高度なプログラミング言語では、データの種類は原子型と構造型に分けられます.原子型は、Cの全体型、文字型、浮動小数点型など、複数のデータ型に再分解できないデータタイプです.二重精度型などのデータタイプであり、構造タイプは複数のデータタイプに分解できるデータタイプであり、その成分は原子タイプであっても良いし、構造タイプであっても良い.
抽象的なデータタイプ(Abstract Data Type)は、一般的にデータ要素、データ要素間の関係、および操作の3つの要素を含み、ADT=(D,R,O)と表します. Dはデータオブジェクト、RはDの関係セット、OはDの基本操作セットです.
抽象性:定義と分離を実現します.定義する時はデータタイプの数学的抽象的な特性だけを考慮して、実現する時はこれらのデータ要素の表現とその操作の実現の詳細を提供します.
拡張可能性:コンピュータにおいて定義され実装された基本的なデータタイプに限定されず、ユーザは、ADTによって既存のデータタイプで未実現のデータタイプを拡張することができる.
Eg:銀行口座の問題の抽象的なデータタイプの定義:
Algorithms+Data Structures=Prograams(アルゴリズム＋データ構造＝プログラム)
プログラム設計には、アルゴリズム、データ構造、プログラミング言語の3つの部分が含まれています.アルゴリズムは問題を解くためのプロセス記述であり、データ構造は、要求された問題を解決するためのデータの記憶とアルゴリズムポリシーの実現をサポートしています.
データ構造は何を研究しますか?
データ構造はデータ間の関係を研究し、与えられたデータに対して可能な動作を研究し、データをどのように組織するかによってこれらの動作を効率的に実現することができる.
関連概念:
データ:データは客観的事物の符号表現であり、情報の担体である.
データ要素:データ要素はデータセットの中の一つの個体で、コンピュータプログラムの加工処理の基本単位です.
データ項目:データ要素は複数のデータ項目から構成されます.
データオブジェクト:同じ性質を持つデータ要素のセット.
データ構造:構造のあるデータ要素のセット.データ構造は4元のグループで表すことができます.Structure=(D,L,S,O)
D(Data):データ要素の限定セットは、記憶と操作の対象です.
L(Logical Structure):データ要素セットDにおけるデータ要素間の客観的な存在関係の有限セットを論理構造と呼ぶ.
S(Strage Structure):データ要素セットDとデータ要素の間の関係セットLは、コンピュータ内の記憶表現であり、記憶構造または物理構造と呼ばれる.
O(Operation):データ要素セットDに規定されている操作のセットです.演算とも呼ばれます.データ構造の基本的な操作は、通常、データ構造の作成と廃棄、データ要素の検索、挿入、削除、遍歴、ソートなどがあります.
＊二元(D,R)とも定義されていますが、D(Data)はデータ要素の限定セットであり、R(Relationsip)はDにおけるデータ要素間の客観的な存在関係の限定セットです.
論理構造:データ要素の間に客観的に存在する関係は、データがコンピュータにどのように記憶されているかに関係なく、通常はデータの論理構造をデータ構造と略称する.
論理構造の区分(一) I.線形構造:あり、最初と一つの端末の結点のみであり、すべての結点は最大で一つの直接前のめりと一つの直接後継者のみである. 例えば、線形表、スタック、キュー、列 II.非線形構造:一つの結点は複数の直接的な前のめりと直接的な後継があるかもしれない. 例えば、木、図などです.
論理構造の区分(二) I.セット:構造中のデータ要素は同じタイプに属する以外、他の関係はありません. II.線形構造:構造中のデータ要素の間に一対一の関係がある. III.ツリー構造:構造中のデータ要素の間にペア以上の関係がある. IV.図のような構造(網状構造):構造中のデータ要素の間に複数対の関係が存在する.
記憶構造:データの記憶構造は物理構造とも呼ばれ、データ構造の中の要素の表示と要素間関係の表現を含む、コンピュータにおけるデータ構造の記憶表現を指す.
記憶構造の区分:
I.順次記憶構造:論理的に隣接する要素を物理構造の隣接する記憶手段に記憶する.データ要素のメモリ内の相対的な位置によってデータ要素間の論理関係を表します.
II.チェーン記憶構造:データ要素にアドレス領域または補助構造を追加し、データ要素間の関係を保存するために使用します.データ要素のアドレスを示すポインタによって、データ要素間の論理関係を表します.論理的に隣接する要素がメモリ内の位置にも隣接していることは要求されません.プログラム設計言語におけるポインタタイプまたはインデックス構造によってしばしば実現されます.
III.ハッシュ格納構造:ハッシュ構造とも呼ばれる.キーワードを直接計算することによって、データ要素の格納位置が得られる.データ要素に対する記憶と検索は、キーワードを直接計算することによって得られる.
注:同じ論理構造は、異なる記憶構造を使用して実装することができます.記憶構造の選択は、アルゴリズムの実現とアルゴリズムの時間と空間要求を主に考慮します.様々な基本的な記憶構造は、単独で使用することも、組み合わせて使用することもできます.
データタイプと抽象データタイプ
データ構造はプログラム言語自体が実現したデータ構造と理解できます.高度なプログラミング言語では、データの種類は原子型と構造型に分けられます.原子型は、Cの全体型、文字型、浮動小数点型など、複数のデータ型に再分解できないデータタイプです.二重精度型などのデータタイプであり、構造タイプは複数のデータタイプに分解できるデータタイプであり、その成分は原子タイプであっても良いし、構造タイプであっても良い.
抽象的なデータタイプ(Abstract Data Type)は、一般的にデータ要素、データ要素間の関係、および操作の3つの要素を含み、ADT=(D,R,O)と表します. Dはデータオブジェクト、RはDの関係セット、OはDの基本操作セットです.
抽象性:定義と分離を実現します.定義する時はデータタイプの数学的抽象的な特性だけを考慮して、実現する時はこれらのデータ要素の表現とその操作の実現の詳細を提供します.
拡張可能性:コンピュータにおいて定義され実装された基本的なデータタイプに限定されず、ユーザは、ADTによって既存のデータタイプで未実現のデータタイプを拡張することができる.
Eg:銀行口座の問題の抽象的なデータタイプの定義:
ADT BankAccount{
/* ： String,int float ，
*/
String ownerName; //
int accountNumber; //
float balance; //
/* ： , */
/* ： 7 */
String getOwnerName(); //
int getAccountNumber(); //
float getBalance(); //
String openAccount(String newName); //
void cancelAccount(int newNum); //
float deposit(float anAmount); //
float withdraw(float anAmount); //
}ADT BankAccount
．
：
I. ： ， ．
II. ： ， ， ， ．
III. ： ， ．
IV. ： ， ．
：
I. ： ， ．
II. ： ， ， ．
III. ： ． ， ， ．
IV. ： ， ， ．
・