データ構造の簡単なメモ

データ構造
定義＃テイギ＃
現実的に大量で複雑な問題を特定のデータ型と特定のストレージ構造でメインメモリ(メモリ)に保存する方法と、その上である機能(例えば、ある要素を検索し、ある要素を削除し、対応する要素をソートする)を実現するために実行される対応する操作をアルゴリズムと呼ぶ方法です.
データ構造は、データストレージを専門に研究する問題です.データの格納には,個体の格納と個体関係の格納の2つの側面がある.アルゴリズムは、データを格納する操作です.

データ構造=個体と個体の関係

アルゴリズム=格納オブジェクトの動作

測定アルゴリズムの基準

時間複雑度:実行するイベント

ではなく、プログラムが実行する回数を推定する.

空間複雑度:アルゴリズム実行中に使用されるメモリの最大

難易度

丈夫性

せんけいこうぞう
すべてのノードを1本の線で通す
はいれつ
配列とは
要素タイプが同じで、サイズが等しい
配列の長所と短所:ストレージ要素の効率が非常に高い
欠点:配列の長さがブロック連続のメモリブロック挿入削除要素を必要とする効率が低いことを事前に知らなければならない.
チェーンテーブル(ディスクリートストレージ)
定義＃テイギ＃
n個のノードは離散的に割り当てられ、互いにポインタで接続され、各ノードには1つの前駆ノードしかなく、各ノードには1つの後続ノードしかなく、第1回の点には前駆ノードがなく、見られない点には後続ノードがない.

ヘッダノード:最初の有効ノード

テールノード:最後の有効ノード

ヘッダノード:最初の有効ノードの前のノードでは、ヘッダノードには有効データが格納されておらず、ヘッダノードの目的は主にチェーンテーブルの操作を容易にするためである

.

ヘッダポインタ:ヘッダノードを指すポインタ変数

テールポインタ:テールノードを指すポインタ変数

チェーンテーブルを決定するにはいくつかのパラメータが必要です
ヘッダポインタだけでチェーンテーブルの他のすべてのパラメータを推定できます
ぶんかつ

単鎖表

双方向チェーンテーブル:各ノードに2つのポインタドメイン

がある

ループチェーンテーブル:他のすべてのノード

を任意のノードで見つけることができます.

非循環チェーンテーブル

アルゴリズム#アルゴリズム#

を巡る

検索

クリア

破壊

長さ

を求める

ソート

削除ノード

挿入ノード

アルゴリズム:狭義のアルゴリズムはデータの記憶方式と密接に関連しており、広義のアルゴリズムはデータの記憶方式とは無関係である.
汎用型:ある技術を利用して達成した効果は異なる記憶方式であり、実行する操作は同じである.
チェーンテーブルのメリットとデメリット
利点:スペースが制限されていない削除要素の挿入が速いという欠点:ストレージ速度が遅い
線形構造の2つの一般的な応用---スタック
定義＃テイギ＃
「先進的な後出」を実現できるストレージ構造で、スタックは箱に似ている.
ぶんかつ

静的スタック

ダイナミックスタック

アルゴリズム#アルゴリズム#

インスタック

出桟

適用

関数呼び出し

割り込み

式評価

メモリ割付

バッファ処理

迷宮

線形構造の2つの一般的な応用---キュー
定義＃テイギ＃
「先進的な先出し」を実現できるストレージ構造
ぶんかつ

チェーンキュー(チェーンテーブル実装)

静的キュー(配列実装)

静的キューは通常、ループキューでなければなりません.
ループキュー
1.静的キュー抑止かループキューでなければならない
静的キューがデキューされ続けると、キュー特性が「先進先出」であるため、ヘッダが前方に移動し続け、キュー内のアドレスが1回しか使用できない(偽オーバーフロー)ため、ループキューが導入される.
2.ループキューにはいくつかのパラメータ決定が必要
义齿
1).キュー初期化frontおよびrearの値はいずれも0 2)である.キュー非空frontは、キューの最初の要素rearがキューの最後の有効要素である次の要素3を表す.キューが空のfrontとrearの値は等しいが、必ずしもゼロではない
3.循環キューエンキュー擬似アルゴリズム
rear=(rear+1)%配列の長さ
4.循環キュー一覧キュー擬似アルゴリズム
front=(front+1)%配列の長さ
5.循環キューが空か
frontとrearの値が等しい場合、キューは空になります.
6.ループキューはフル(rear+1)%配列長ですか?=front
キューの適用
時間に関連するすべての操作はキューに関連しています.
再帰
定義＃テイギ＃
1つの関数が直接または間接的に自分を呼び出す
例を挙げる

階乗

合計

ハノータ

迷宮

再帰的に満たす3つの条件

再帰には明確な終了条件が必要である

この関数が処理するデータ規模は、

減少する必要がある.

この変換は解けなければならない

再帰とサイクル
再帰:理解しやすく、速度が遅く、記憶空間が大きい循環:理解しにくく、速度が速く、記憶空間が小さい
再帰の基本思想
ある規模のnのことを完成するには、彼のn-1の規模を借りて完成しなければならない.
ツリー
定義＃テイギ＃
ルートと呼ばれるノードが1つしかなく、互いに交差しないサブツリーがいくつかあり、これらのサブツリー自体もツリーです.ツリーはノードとエッジで構成され、各ノードには親ノードが1つしかありませんが、複数のサブノードを持つことができますが、ルートノードには親ノードがありません.
深度しんど:ルートノードから最下層ノードまでのレイヤ数リーフノード:サブノードがないノード非終端ノード:実際には非リーフノード度:サブノードの個数
ぶんかつ
一般的なツリー:任意のノードのサブノードの数は制限されません.ツリー:任意のノードのサブノードの数は最大2つしかありません.サブノードの位置は変更できません.森:n互いに交差しないツリーの集合
きおく
ツリーストレージ: ： ，

の利点:あるノードの親ノードと子ノード

を検索する

欠点:メモリ容量が大きい

一般ツリーのストレージ

両親表示法:親ノードの便利さを求める

子供表示法:サブノードの便利さを求める

親と子の表現:親ノードと子ノードを求めるのは便利だが、操作は不便だ

子供兄弟表現法(二叉木表現法):1つの普通の木を二叉木に変換して格納(任意のノードの左ポインタドメインが彼の最初の子供を指し、右ポインタドメインが次の兄弟を指し、この条件を満たす限り、1つの普通の木を二叉木に変換することができるようにする)

.
普通の木が転化した二叉木には右の木がないに違いない.
森のストレージ

まず森を二叉樹に変換し、二叉樹(各樹を前の兄弟とする)

に格納する.
操作
二叉木
ぶんかつ

一般二叉木

フルツリー:ツリーの層数を増やすことなく、もう1つのノードを追加できないツリー

.

完全二叉木:満二叉木の最下層の最も右側の連続するいくつかのノードを削除するだけで、形成された二叉木

ツリー操作
遍歴する

先序遍歴:

ルートノードにアクセスし、左サブツリーにアクセスし、右サブツリーにアクセスします.

中序遍歴

中順アクセス左サブツリー再アクセスルートノード中順アクセス右サブツリー

後序は

を遍歴する.
左サブツリーにアクセスした後、右サブツリーにアクセスしてルートノードにアクセス
既知の2つの遍歴シーケンスは元のツリーを求めます
元のツリーは、シーケンスと中シーケンス、または中シーケンスと後続によって喜んで復元されますが、シーケンスと後続によって元のツリーは復元されません.
適用

ツリーデータベース内のデータ組織の重要な形式

オペレーティングシステムの子親プロセスの関係自体は、ツリー

です.

オブジェクト言語におけるクラス向けの統合関係自体がツリー

である.

ヘフマンツリー