アルゴリズムレッスン
1637 ワード
STACK
FIRST IN LAST OUT
LAST IN FIRST OUT
PUSHいっぱい?OVERFLOW
空いてるのPOP?UNDERFLOW
->メモリ上のOVERFLOW UNDERFLOWと考えられます.
QUEUE
FIRST IN FIRST OUT
LAST IN LAST OUT
キューサイズHEAD、TAILの位置によってはキューが空いていますが、入れない瞬間もあります.スペースの使用効率が低下しています.
->したがってループQUEを使用します.
->depuue dexとこれ.
実際、headは常に0に保たれており、popのたびにデータを引き寄せることができ、時間的複雑さの問題が多く発生します.
GRAPH(非線形)
G(V,E)
V:頂点
E:幹線
...現実世界の多くの構造をモデリングできるフレームワーク.
図形の分類方法
1.方向の有無
有向図、無方向図(有向図、無方向図)
ウェイトマップ
用語
CYCLE
頂点から幹線に沿って再び自分に戻ることができれば、CYCLEグラフです.
接続図:すべての頂点を直線で接続する図
グラフィックの表示方法
隣接マトリクスの使用->2 D配列2 Dはいれつ
隣接リストの使用->ベクトル
少し複雑な場合は、隣接するテーブルを使用したほうがいいです.
隣接リストには、ノード内のすべての隣接ノードが含まれます.
隣接するリストと配列の表現に注意してください.方向性があり、ありません.
重みがない場合は、1(接続)0(非接続)と表示されます.
幹線に重みがある場合、隣接マトリクスは重み値でテーブルに埋め込まれます.
隣接リストでは、(頂点、重み)で表されます.
C++ベースのVECTORデータ可用性:アレイと同様
幹線に重みがある場合は、構造体などを使用できます.
#include <vertor>
(JAVAにはC++のVECTOR機能はありません…)TREE(非線形)
ループレス接続図
ツリーの直径
ツリー内の任意の2つのノード間の距離の最短値.
ツリーの整流
一般ツリー、バイナリツリー、完全バイナリツリー
このJin Treeは一番よく使われています!
AVl,red-back,生成ツリーの3種類も追加されている.
binary search tree
いつも自分を基準にして、左の値は小さくて、右の値は大きいです.
早いけど.
バランスが良ければ、早いけど.
非均衡は実は遅い.
木の表現
グラフのように
しかし、子供と親を分けるともっと便利です.
maxHeap:rootが最大値
minHeap:ルートの最大値
木の回り
前衛中尉バックツアー(帰航用)
Reference
この問題について(アルゴリズムレッスン), 我々は、より多くの情報をここで見つけました https://velog.io/@chamgrace/알고리즘-강의テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol