資料構造の意義

データを格納する構造.いろいろな種類がありますが、格納されている資料へのアクセス方法などに違いがあります.
学習資料構造の原因:
資料構造によっては、実施するプログラムの性能に応じて適切な資料構造を選択すべきであるという利点と欠点がある.プログラム内の資料を効率的に格納し、利用するために使用されます.
特定のアルゴリズムを実現するためには、適切なデータ構造を使用してこそ、良好な性能を得ることができる.

抽象データ型

ある資料とその資料の演算(動作)の数学的定義を意味する.しかし、この定義をどのように実現するかは明確に説明されていない.
抽象資料型の抽象という言葉の意味では不明確であることがわかる.

データ型

資料型はある資料を識別する方法とその資料に対する各種演算を提供する.

65の資料は直接数字を表すこともできるし、Unicodeで解釈した「A」を表すこともできる。 そのため、コンピュータがこの点を説明するには、資料のタイプを明確にしなければならない。 数字を表す資料型であれば四則演算は可能ですが、文字に四則演算は適用できません。

資料型は,ある資料を識別する方法を定義し,資料に適用する演算を決定する.
特定の分類に基づいて正確に資料を表現するために,定義と異議の体現は資料型といえる.

抽象データ型

抽象データ型の違いは,実施方法を明確に説明していないことである.
ボウルを抽象資料型と呼ぶなら、ボウルの中の資料と相応の連想の定義を含むべきだ.
器に食べ物を盛ったり、器の中の食べ物を食べたりするように、抽象的な資料型も資料を入れて演算することができます.しかし,資料へのアクセス方法は示されていない.
ここで,抽象資料型にどのように資料を格納し,どのように演算するかは,資料構造として明確に体現される.

整理する

抽象データ型:データとその演算が概念的に定義されている場合のみ 資料構造:具体的に資料を格納する方法と資料に適した演算を提供する

抽象的な資料型を具体的に体現した結果は資料型といえる.

配列と接続リスト

Pythonのリストと資料構造のリストは異なる概念であることに注意してください.

インベントリ

リストは、存在順序の1列の値を持つ抽象的な資料型です.

を選択します。 ≪参照|Browse|emdw≫:任意の場所の資料を参照します。 挿入:データを任意の場所に追加します。 削除:材料を任意の場所で削除します。

体現リストという抽象的な資料型の代表的な例は配列である.
麻布列に格納された値には、順序を表す番号(index)があります.

let array = [1,2,3,4,5,6]; //index: 0,1,2,3,4,5

配列→クエリー

配列配列は、配列内の特定の順序の値をクエリーするときに、効率的で迅速な演算を行うことができます.

配列→挿入

逆に、資料を追加する場合、新しい資料を追加するにつれて、資料の順序を変更する必要があるので、面倒です.
挿入演算では、追加した資料のスペースを空けるために、既存の資料が1つずつ圧縮されます.

配列→削除

挿入とは逆に、削除するインデックス内のデータが空になり、データが減少するため、空きを埋めるためにデータが一目瞭然に引き出される->並べられた資料が1部足りなくなったので、残りのスペースも取れました.

接続リスト

実装リストの資料構造では,代表的な他の資料構造が接続リストである.
配列は各データをインデックスで格納し、接続リストは複数のノードを格納するように実装される.
ノードにはデータとポインタがあります.データ自体が格納された値であり、ポインタは次のノードを指します.

接続リスト-ナビゲーション 接続リストがこの特性で特定の場所の資料を検索するのは面倒です。なぜなら,探したい資料を見つけるには,最初のノードから順にポインタによる移動と探索が必要であるからである.

したがって,接続リストで検索したデータの位置が開始点から遠いほど演算回数が多くなる.
接続リストの利点は、材料の追加と削除から見ることができます.

接続リスト-挿入

接続リストからノードを挿入する場合は、前のノードの前後のポインタ関係を解除してから、位置を追加する前のノードのポインタを新しいノードに設定し、新しいノードのポインタを前のノードが前のノードを指すように設定できます.

接続リスト-削除

削除するノードの前のノードのポインタが削除するノードを指している場合は、接続リストの削除を削除できます.
接続リストは、自分の次のノードを指す相対的な順序を表すため、この演算を行うことができる.

整列 利点:特定の場所でのリソースナビゲーションが容易 欠点:データの挿入と削除の効率が低い

接続リスト データの挿入と削除に有利 特定の場所でデータをナビゲートするのは面倒です

データ構造の実装方法

資料構造は抽象資料型に示す表現と演算方法を説明した.
オブジェクト向けプログラミングを例にとると,抽象データ型をインタフェースと見なし,データ構造をクラスと見なすことができる.

インタフェースとは?

オブジェクト構造で抽象メソッドのみを使用する設計クラス
実装部分が空のメソッドを抽象メソッドと呼び,継承クラスで実装する.
つまり、「リスト」インタフェースでは、挿入と削除のみがサポートされます.
実際のアクション部分は、継承リストの配列クラス、接続リストクラスで実現します.

Pythonインタフェースの例 class MyInterface(metalass=Xmeta):抽象クラスを作成するためのメタクラスを定義 @abstractmethod#抽象メソッドを表すコメント def func() : pass Javaなど他のオブジェクト向け言語とは異なり、Pythonはインタフェースの機能を直接サポートしていない。 したがって、上記のように表現しなければならない。

資料構造を作成する際、インタフェース継承のレベルは非常に優れている.
クラスが持つフィールドはデータに対応し、メソッドはデータの演算に適用できます.

データ構造の実施例 import queue q = queue.Queue() Pythonのベースライブラリでは、queueというデータ構造を実現するQueueクラスがあります。 キュー・データ構造を持つデータ・ストレージと演算方法のクラス。

コンテナとはリスト、チュートリアル、ディレクトリなどの1つ以上の要素を含むことができる資料型です.
内部継承Containerクラスのサブクラスに相当します.
たとえば、最も値の高い操作を返すコンテナには、次のような方法があります.

コンテナに整数を追加 コンテナから整数を削除 コンテナ内の整数の最大値を返します。

データ構造の実装

データ構造を利用して良い方法かどうかを判断するいくつかの基準は

コードが簡潔かどうか(メンテナンス/解釈が容易かどうか)

速(時間効率)

リソース(容量/メモリ効率)

の実施時間が短いほど(時間が経済的であるほど)、

どれくらい速いですか。

が実行するコマンドの数が少ないほど、所要時間が短くなる.

sum = 0 for i in range(30): sum = sum + 1 sum = 0 for i in range(300000): sum = sum + 1 上のコードの繰り返し回数は下のコードより少なく、時間を節約します。

時間の複雑さ

量子化アルゴリズムによる問題解決に要する時間の方法
通常、問題において与えられる最悪の場合(大O記号)に要する時間を表すために用いられる.

配列を使用する場合、最悪の場合、n個の要素をすべて左に挿入します。n個の要素がある場合、 *(n(n+1)/2の時間複雑度、最悪の場合。

接続リストを使用する場合、すべてのn要素を左側に挿入すると、前のノードの前にn個の最初のノードを作成して接続するだけで、O(n)の時間的複雑さがあります。

最後に,資料構造を学習する理由は,資料構造によって特性や動作方法が異なるため,作成するプログラムの目的を最も効果的に達成できる資料構造を用いるためである.

データ構造による問題解決

問題を把握する。(どのような内容が含まれているか、およびその内容の意味を決定します) データ構造を決定するために必要な機能。(この資料の使用方法について) 問題を効果的に解決する資料構造を設計し、使用する。（的確なリソース構造による問題解決）

資料を保存するのはどういう意味ですか。 これは、計画の意図に合致するデータ構造を使用して、効率的なパフォーマンスで実装することを意味します。