Wondershare EdrawMind
EdrawMindデータ構造
マインドマップギャラリー データ構造
- 4
データ構造
データ構造に関するマインド マップ。アルゴリズムの特性には、入力、出力、有限性、確実性、実現可能性が含まれます。このマップは、線形テーブル、ツリー、グラフの知識を共有します。
2023-06-21 10:48:44 に編集されました- おすすめ
- アウトライン
データ構造
基本的な考え方
アルゴリズム
アルゴリズムの特徴
入力
出力
有限性
確実
実現可能性
アルゴリズム設計要件
正しさ
可読性
堅牢性
高い時間効率と少ないストレージ容量
時間の複雑さ
空間の複雑さ
再帰
リニアテーブル
収納構造
順次ストレージ
チェーンストレージ
静的リンクリスト
配列で記述される
単一リスト
二重リンクリスト
循環リンクリスト
固定長配列ストレージを使用する場合、空の状況と満杯の状況を区別するために、一般に末尾ポインターに要素を含めることはできません (したがって、テーブルの長さは配列の長さより小さくなければなりません)
ヘッドポインタ
操作する
入れる
探す
静的ルックアップテーブル
二分探索
ハッシュテーブル（ハッシュテーブル）
ハッシュ関数の構築
デジタル分析
スクエア・ミディアム法
余りを残す除算メソッド
折り方
乱数法
競合の処理
公開演説法
ハッシュ関数方式
チェーンアドレス方式
パブリックオーバーフローメソッド
動的ルックアップテーブル
パフォーマンス分析
索引
密なインデックス
ブロックインデックス
転置インデックス
選別
基本的な並べ替え
バブルソート
挿入ソート
選択ソート
並べ替えを改善する
クイックソート
時間計算量前の係数はヒープソートの係数より小さい
ヒルソート
ヒープソート
大/小のトップパイル
マージソート
バケットソート
カウントソート
応用
多項式演算
スタック
応用
式の評価
接頭辞式
接尾語表現
計算する
スタックにプッシュされた数値を検出しました
演算子が見つかると、スタックの上位 2 つの要素に対する演算の結果がスタックにプッシュされます。
インフィックスをサフィックスに変換する
デジタル出力に出会う
オペレータが遭遇しました
優先順位がスタックの最上位よりも高い場合は、スタックにプッシュされます。
括弧の優先順位が最も低くなります
それ以外の場合は出力
左括弧が見つかったら、それをスタックに押し込みます
右括弧が見つかると、左括弧がスタックからポップされるまで、右括弧がスタックから順番にポップされます。
列
弦
パターンマッチング
単純なパターンマッチング
KMPパターンマッチング
次の配列
全体的な試合
木
収納構造
親の表現
子の表現
子供の兄弟の代表
分類
完全なバイナリツリー
すべてのブランチ ノードには左右のサブツリーがあります
完全な二分木
階層順のノードの番号付けは、完全なバイナリ ツリーの番号付けと同じです。
二分木
通常のツリーを二分木に変換
子の兄弟表記を使用する
左側の子ノード
最初の兄弟ノードは外側にあります
フォレストを二分木に変換する
共通の仮想ルート ノードを追加して、通常のツリーに変換し、次にバイナリ ツリーに変換します。
トラバース
事前順序、順序内トラバーサル、または中間順序および事後順序トラバーサルではツリーを決定できます (ただし、事前順序および事後順序トラバーサルでは決定できません)。
バイナリツリートラバーサル
優先順位
最初にルート ノードにアクセスし、次に左右のサブツリーをトラバースします。
中程度の
最初に左側のサブツリーをトラバースし、次にルート ノードにアクセスし、最後に右側のサブツリーをトラバースします。
あとがき
まず左右のサブツリーを走査し、次にルート ノードにアクセスします。
順序
ツリートラバース
最初のルートトラバーサル
プリオーダートラバーサルはバイナリツリー表現で使用できます
バックルートトラバーサル
インオーダートラバーサルはバイナリツリー表現で使用できます
森林横断
優先順位
中程度の
最適二分木（ハフマン木）
すべての重み付きパスと最小値
経路の長さ
ルートノードから指定ノードまでに渡されるノードの数 (= 層数 - 1)
重み付けされたパスの長さ
ノードの重みにパス長を掛けたもの
アルゴリズム
ノードは、小さいものから大きいものまで重みによって並べ替えられます。
最小の 2 つのノードを新しいノードの子ノードとして取り、新しいノードの重みは 2 つのノードの重みの合計になります。
新しいノードを追加し、残りのノードが 1 つだけになるまで上記のプロセスを繰り返します。
ハフマン符号化
文字エンコーディングが別の文字エンコーディングのプレフィックスになっていないことを確認する必要があります。
文字頻度を重み値として使用してハフマン木を構築する
ルート ノードからリーフまでのパス分岐に沿った 0 と 1 (左と右) のシーケンスとしてエンコードされます。
バイナリソートツリー
意味
左側のサブツリーが空でない場合、左側のサブツリー上のすべてのノードの値はルート ノードの値より小さくなります。
右のサブツリーが空でない場合、右のサブツリー上のすべてのノードの値はルート ノードの値より大きくなります。
左右のサブツリーもバイナリでソートされたツリーです。
バランス二分木 (AVL ツリー)
意味
各ノードの左のサブツリーと右のサブツリーの高さの差が 1 以下であるバイナリ ソート ツリー
バランス係数
左側のサブツリーの高さから右側のサブツリーの高さを引いた値
1、0、-1のみを指定できます
回転させる
最小の不均衡サブツリー (挿入されたノードに最も近く、バランス係数の絶対値が 1 より大きい) を選択します。
多方向探索ツリー (B ツリー)
赤黒い木
写真
収納構造
隣接行列
隣接リスト
相互リンクリスト
隣接複数リスト
エッジセット配列
トラバース
まず幅広さ
深さ優先
最小スパニングツリー
プリムのアルゴリズム
クラスカルアルゴリズム
最短経路
ダイクストラのアルゴリズム
フロイドアルゴリズム
有向非巡回グラフ (DAG)
トポロジカルソート
AOVネットワーク
クリティカルパス
AOEネットワーク