データ構造のリスト
はじめに
定義：
- データ：客観的な事柄を象徴的に表現した記号の総称で、コンピュータに入力して処理できるもの。
- データ要素：データの基本単位で、多くのデータ項目を含みます。
- データ項目：独立した意味を持ち、細分化できないデータの最小単位。
- データ・オブジェクト：同じ性質のデータ要素の集まりで、データのサブセット。
- Data structure［データ構造］：何らかの形で互いに関連づけられたデータ要素の集まり。
論理構造：データ要素間の論理的関係、データ構造がユーザに提示される方法 ・集合：データ要素間に「集合」に属するということ以外の関係はない ・線形構造：データ要素間に1対1の関係、ただし各ノードが前任者と後任者を持つ先頭ノードと末尾ノードを除く ・線形テーブル、順序テーブル、スタック、キュー：データ要素間に1対多の関係、ただし各ノードが最大1つの前任者と複数の後任者を持つ ・ツリー、バイナリツリー、キュー。線形構造：データ要素間の1対1の関係。ただし、各ノードが1つの前任者と1つの 後任者を持つ先頭ノードと末尾ノードを除く 木構造：データ要素間の1対多の関係。各ノードが複数の前任者と後任者を持つ グラフ構造：データ要素間の多対多の関係。各ノードが複数の前任者と後任者を持つ グラフ：連結グラフ、強連結グラフ、オイラーグラフ、密グラフ、疎グラフ グラフ構造：データ要素間の1対多の関係。各ノードが複数の前任者と後任者を持つ
記憶構造：データ要素とその相互関係がコンピュータのメモリに記憶される方法 ・逐次記憶構造：論理的に隣接するノードも物理的に連続して記憶される、多くは配列として実装 ・逐次テーブル：論理的に隣接するノードも物理的に連続して記憶される、多くは配列として実装 ・索引記憶構造：ノードは通常、ノードに関する情報とともに記憶され、ポインタフィールドのみを変更すればよい ・索引記憶構造：ノードは通常、ノードに関する情報とともに記憶され、ポインタフィールドのみを変更すればよい連鎖型ストレージ構造：論理的に隣接するノードが物理的に隣接している必要がない ・連鎖型テーブルは主にポインタで実装される 長所：挿入と削除が容易、ポインタフィールドを変更するだけでよい 短所：ストレージの使用率が低い、ランダムアクセスができない ・インデックス型ストレージ構造：通常、ノード情報と共にインデックステーブルが構築され、インデックスされたエントリは 長所：検索が高速、線形構造と組み合わせられる、ランダムアクセスが可能、挿入と削除はインデックステーブル内の対応するノードを移動するだけでよいノードの格納アドレスはバイナリツリーを参照 不利な点：スペース利用率が低い ハッシュ格納構造：ノードのデータのみが格納され、ノード間の論理構造は格納されず、検索するノードのキーワードがノードの格納アドレスの計算に使用される 利点：クエリが速い 不利な点：通常、データの高速検索や挿入が必要な場合にのみ適しています。
データに対する操作：データに適用される操作。
- データ型：同じ性質の値の集合と、一般的な用語のこのセットで定義された操作のセットは、データノードに実装されているプログラミング言語です。
- 非構造アトミック型：分解不可能な型、例えばC言語の基本型、ポインタ型、NULL型など。
- 構造型：その値はある構造に従っていくつかの構成要素で構成され、構成要素は構造化されたものであっても非構造化されたものであってもよい 付記：ある意味で、データ構造は「同じ構造を持つ値の集合」と見なすことができ、構造型はデータ構造とその上に定義された操作の集合と見なすことができる データ構造＝データデータ構造＝データ＋関係 データ型＝データ構造＋操作
- 抽象データ型：問題の数学的モデルから抽象化された論理データ構造と論理データ構造上の操作。コンピュータの具体的な記憶構造や、操作のアルゴリズム的な意義の具体的な実装は考慮せず、データ型の数学的抽象化にあります。
- 非構造アトミック型：分解不可能な型、例えばC言語の基本型、ポインタ型、NULL型など。
ADT複合体の例 {
データ・オブジェクト: D={e1, e2 | e1, e2すべて実数}
データ関係：R={<e1, e2> | e1は複素数の実部、e2は複素数の虚部である。}
基本操作：assignComplex(&z, v1, v2): 虚数と実数がee2である複素数zを構成する。
DestroyComplex(&z): 複素数zを破壊する
GerReal(z, &real): 実数変数で値の実数部を取得する
GetImag(z, &imag): imag変数を使用して虚部を得る
Add(z1, z2, &sum): sum変数を使って複素数zz2の和を求める
} ADT Complex
- アルゴリズム：特定の問題を解決するための一連のステップの記述 無限性、実現可能性、決定性、入力、出力 アルゴリズムの設計目標：正しさ、読みやすさ、使いやすさ、堅牢性、高効率、低ストレージ要件
時間の複雑さ：O(1)< />< />< />< />< />< />< />< />< />< />< />< />< />< />< />< /><
線形表
定義：
は、同じ特性を持つデータ要素の有限シーケンスです。
ADT List {
データ・オブジェクト: D={a(i) | 1<=i<=n, n>=0, a(i)はElemType型である。}
データ関係：R={<a(i), a(i+1)> | a(i), a(i+1) , i=1, ,n-1}
基本操作：省略
}
線形テーブルの逐次テーブル格納構造：
typedef struct {
ElemType data[MaxSizr];
int length;
} SQlist;
線形テーブルの単一連鎖ストレージ構造
typedef struct LNode {
ElemType data;
struct LNode *next;
} LinkList;
線形テーブルの二重連鎖記憶構造
typedef struct DNode {
ElemType data;
struct DNode *prior;
struct DNode *next;
} DLinkList;
- リンクリストの記憶構造に対する操作、静的リンクリスト、循環リンクリスト、もしあれば内部を確認、ヘッドノードを持つリンクリストと持たないリンクリストに対する操作、フォーカスの違い
- チェーン・テーブルの操作でノードを削除したり挿入したりするには、そのノードの前任者と後任者を見つける必要があります。
- 単一のリンクされたテーブルにヘッド・ノードを持つ目的は、ノードの挿入と削除のアルゴリズムを単純化することです。
- 循環テーブルと2重リンク・テーブルでは、テーブルの末尾のノード*pを決定する条件は、p->next==L
スタックとキュー
スタックの定義
は特殊なタイプの線形表で、後入れ先出し表としても知られています。
ADT Stack {
データ・オブジェクト: D={a(i) | 1<=i<=n, n>=0, a(i)はElemType型である。}
データ関係：R={<a(i), a(i+1)> | a(i), a(i+1) , i=1, ,n-1}
基本操作：省略
}
スタックの逐次記憶構造
typedef struct {
ElemType data[MaxSize];
int top;
} SqStack;
スタックの連鎖記憶構造
typedef struct linknode {
ElemType data;
linknode *next;
} LiStack;
スタック・トップ・ポインタは、その記憶構造に対する操作、各入力と出力のためにどのように変化しますか？算術式はどのように接尾辞式に変換されるのですか？接頭辞式はどうなりますか？
法則：スタックに特定の順序で、1から番号付けを開始するには、スタックの順序のうち、前面から背面への各要素は、要素のシーケンス番号よりも小さくなければならない要素のシーケンス番号の減少シーケンスを構成しています
1 2 3 4 1 4 3 2 正解 1 4 2 3 不正解
スタックに入れる a b c d スタックから出す a d c b スタックから出す a d b c
直交数：
追伸：以下の質問の等価性
- n 個の非同一要素をスタックに出力するシーケンスの数；
- n個の異なる要素からなる、異なる形態の二分木の数；
- 同じモルフォロジーを使用していない異なる要素のn個のシーケンスを持つバイナリツリーの数。
空のスタック条件 top == -1 満杯のスタック条件 top == MaxSize-1 トップ・ポインタは常に現在の要素を指します。
サフィックス式の口頭計算
中間式 "5+2×-8/2 "を接尾式に変換し、演算順に括弧"))-) "を加え、右括弧を左括弧の前の演算子に置き換え、左括弧を削除すると接尾式になります。"5216+×+82/-"
再帰的女王問題？迷宮問題？ハヌカの塔？フィボナッチ級数？非再帰は有効か？
チームの定義
は特殊な線形テーブルで、FIFOテーブルとしても知られています。
ADT Stack {
データ・オブジェクト: D={a(i) | 1<=i<=n, n>=0, a(i)はElemType型である。}
データ関係：R={<a(i), a(i+1)> | a(i), a(i+1) , i=1, ,n-1}
基本操作：省略
}
待ち行列の逐次テーブル記憶構造
typedef struct {
ElemType data[MaxSizr];
int front, rear;
} SqQueue;
循環待ち行列の記憶構造
typedef struct {
ElemType data[MaxSize];
int front, count;
} QuType;
待ち行列の連鎖記憶構造
typedef strcut qnode { typedef struct {
ElemType data; QNode * font;
struct qnode *next; QNode * rear;
} QNode; // チェーンチームのデータノードの定義 } LiQueue // チェーンチームの定義
その記憶構造に対する操作、報告された数の解答問題、迷路問題
逐次記憶構造：
非周期的キュー：
チーム空の状態：リア == フロント
チームフル状態：リア == MaxSize-1
初期状態：フロント == リア == -1
先頭と末尾のポインタは、キューの現在の先頭要素と末尾要素を指します。
エレメント数：リア-フロント
円形のキュー：
チーム空の状態：リア == フロント
チーム・フル状態: %MaxSize == front
初期状態：フロント==リア==0
先頭と末尾のポインタは、キューの現在の先頭要素と末尾要素を指します。
要素数: %MaxSize
流出
アッパーオーバーフロー：キューが一杯になってもまだキューに入ること。
下段オーバーフロー：キューが空でもキューから出る
偽のオーバーフロー: キューに空のスロットが存在しますが、 rear == MaxSize-1 によってキューが満杯であると判断されます。
連鎖記憶構造判定条件は連鎖リストと同じ
ツリーとバイナリーツリー
木の定義：
は、1つだけのルート・ノードを持つn個(n>=0)のノードの有限集合からなる非線形構造です。
ADT List {
データ・オブジェクト: D={a(i) | 1<=i<=n, n>=0, a(i)はElemType型である。}
データ関係：R={<a(i), a(j)> | a(i), a(j) , 1<=i<=n, 1<=j<=n, ここで、各要素は1つの先行ノードと0個以上の後続ノードを持つ。}基本操作：
;
}
木表現：木表現、ベン図、凹表現、括弧表現
自然：
樹種のノード数＝全ノード度の合計＋1
証明：木では、各ノードは1つだけ先行ノードを持つので、すべてのノードの次数と、先行ノードを持たないルートノードの次数の和が、木のすべてのノードになります。
m本の木のレベルiのノード数は最大m^ノード 証明：各ノードが満杯である場合、レベルiのノード数はレベルi+1のノード数のm倍。
高さ h の m 倍の木は、最大で / 個のノードを持つ 証明： この木が完全な m 倍の木であるとき
証明：木の高さをhとします。木の最初のh-1レベルがすべて満杯で、最後のレベルが満杯であってもなくてもよい場合、木は不等式[m^-1]/ < n <= [m^h-1]/ h =を満たす最小の高さを持ちます。⌈log(m)[n×+1]⌉
リーフノード: n = n(2) + 2×n(3) + + ×n(m-1) + 1
ツリー記憶構造：
双親ノード記憶構造：各ノードに、その双親ノードの位置を示す擬似ポインタが付加された逐次記憶構造で、ルートノードの擬似ポインタは-1に設定される。
typedef struct {
ElemType data;
int pos;
} STree[MaxSize];
ノードの親を見つけるのは簡単だが、子を見つけるには構造全体を走査する必要がある。
子チェーンの記憶構造
木の最大次数に応じて子ノード・ポインター・フィールドの数を設定することで、ノードごとに子ノード・ポインター・フィールドの数が増えてアルゴリズムが複雑になるという問題を解決できる。
typedef struct tnode {
ElemType data;
struct tnode *child[M];
} CTree;
この記憶構造は、面キュー2分木や4分木などの場合に適しているが、それ以外の木では記憶領域の無駄遣いである。
子兄弟連鎖の記憶構造
各ノードは3つのドメインで設計されている：値ドメイン、そのノードの最初の子ノードへのポインタ・ドメイン、そのノードの次の兄弟ノードへのポインタ・ドメイン。
typedef struct cbnode {
ElemType data;
struct cbnode child;
struct cbnode brother;
} CBTree;
記憶構造は木を2分木の記憶構造に変換するもので、木と2分木の間で簡単に実装できるのが最大の利点だが、2分木の親ノードを見つけるのが面倒で、ルート・ノードから探す必要がある。
バイナリーツリーの概念
定義：2進木とは、次数が2以上のノードが存在しない木構造のことで、2進木の部分木は左右にあり、順序を逆にすることはできません。
!!!完全2分木、完全2分木、2分木ソート木、ハフマン木、バランス2分木、B+木、B-木について詳しく!!!
自然：
- 空でない2分木の葉ノードの数 = 次数2 + 1のノード n(0) = n(2) + 1
- 空でない2分木のk番目のレベルは最大2^個のノードを持ちます。
- 高さ h のバイナリツリーは、最大で 2^h - 1 個のノードを持ちます。
- 1、2......、nと番号付けされた完全な二分木を階層的に走査すると、次の関係が得られます： a. i > 1のとき、ノードiの双子ノードは⌊i/2⌋と番号付けされます。b. 2iのとき、そうでなければ左の子ノードはありません c. 2i+1のとき、そうでなければ右の子ノードはありません d. ノードiが位置するレベルは、⌊log(2)⌋または⌊log(2)+1⌋のいずれかです。
- n個の異なるノードは、異なるC(n)/[カテラン数]を持つバイナリツリーを構築できます。
バイナリツリーのストレージ構造：
シーケンシャルストレージ構造：完全なバイナリツリーは、完全なバイナリツリーは、より適切な、ツリー内のノードのシリアル番号は、一意にスペースを節約するだけでなく、配列の添え字の使用は、ツリーと論理的関係内のノードの位置を決定するために、ノード間の論理的な関係を反映することができます。
連鎖記憶構造：n個のノードを含むバイナリ連鎖表で、n個のノードを持つ。+1ヌルポインタ
typedef struct bitnode {
ElemType data;
struct bitnode *lchild;
struct bitnode *rchild;
} BiTree;
バイナリツリーのトラバーサル
先行探索、中位探索、後行探索 Ps. これら3つの探索の再帰的・非再帰的アルゴリズムがわかっていれば、「先行＋中位／後行＋中位／階層＋中位」で二分木を一意に識別できます。
スレッド・バイナリー・ツリー
目的：ノードの前任者と後任者の検索を高速化します。
本質：非線形構造に対する線形化操作、バイナリーツリーは物理的な記憶構造である。
typedef struct threadnode {
ElemType data;
struct threadnode *lchild;
struct threadnode *rchild;
int ltag, rtag;
} ThreadNode;
ltag = 0 lchild領域はノードrtagの左子を示す。 = 0 rchild領域はノードの右の子を示す
= 1 lchild領域はノードの前任者を示す。 = 1 rchild領域はノードの後継を示す
質問です：
行順の手がかりバイナリツリーで、あるノードを先に走査したノードの先行ノードを見つけることができません。
ノードの親を知る方法がなく、バイナリーチェーンテーブルに親へのポインタがないため、後方キューのバイナリーツリーでノードの後方トラバーサルの後継を見つけることは不可能です。
木が与えられたとき、二分木は一意に決定でき、二分木から木または森への変換は一意 木の先行走査＝森の先行走査＝二分木の先行走査、木の後続走査＝森の中位走査＝二分木の中位走査
- ハフマンツリー：定義：ツリーのルートからパスの長さとノードの重みの積の任意のノードに、加重パスの長さを持つノードとして記録され、加重パスの長さを持つすべてのリーフノードの合計は、"分岐ツリー "の最小加重パスの長さがハフマンツリーと呼ばれるときに、加重パスの長さを持つツリーと呼ばれ、また、最適な分岐ツリーとして知られている接頭辞コード：どの符号も他の符号の接頭辞ではありません ハフマン木は各レベルに2つのノードがあり、ハフマン符号の0と1の数はその中のパスの数とみなされ、ハフマン符号のパスの数はその中のパスの数とみなされ、ハフマン木のパスの数はその中のパスの数とみなされます。
例：5文字の使用頻度に応じて設計されたハフマン符号は、00、100,101,110,111することはできません 理由：3のパス番号は4ノードを持って、2のパス番号を持つ2つのノードによって生成されなければならない、シーケンス内の2のパス番号を持つ別のノードがあり、2のパス番号を持つノードの総数が3ノードがあり、ハフマンツリーの定義を満たしていません。
Ps.次のすべてのツリーテーブルのルックアップは、挿入および削除操作では、テーブルのレコードを移動する必要がない、追加の時間のオーバーヘッドを減らすためにです。
Binary Sorted Tree: 定義: バイナリ・ルックアップ・ツリーとも呼ばれ、左サブツリーのノード値 < ルート・ノード値 < 右サブツリーのノード値、再帰的に各サブツリーがBSTであることが実現される BSTは動的集合として、ツリーの構造は通常一度には生成されず、ルックアップの過程でツリーがキーワードを持たないときに挿入され、その後再び挿入されること、挿入の順序が探索に成功したときにBSTの高さが最大になることが特徴。ルックアップに成功した場合はルックアップの平均長を計算し、ルックアップに失敗した場合はルックアップの平均長を計算）～O(n))
バランスバイナリツリー：目的：バイナリツリーの高さが急速に成長するのを回避し、バイナリソーティングツリーのパフォーマンスを向上させる 特徴：任意のノードの左右のサブツリーの高さの差は-1、0、1であり、AVLが調整されるたびに、挿入ノードに最も近いものの範囲外のバランス係数で調整されます。
最小ノード： N0 = 0, N1 = 1, N2 = 2, Nn = Nn-1 + Nn-2 + 1 最大ノード： 2^n - 1
Bツリー：定義：多重化平衡バイナリツリーとしても知られ、発信ファイルシステムを整理・管理するための非常に効果的なデータ構造です。 特徴：ツリー内のすべてのノードの子ノードの最大値をBツリーの順序と呼び、通常mで示されます：
- すべてのリーフノードは同じレイヤにあり、情報を持ちません。
- ツリーの各ノードは、最大m個のサブツリーを持ちます。
- ルートノードが終端ノードでない場合、ルートノードには少なくとも2つのサブツリーがあります。
- ルートノード以外の非リーフノードは、少なくとも⌈m/2⌉のサブツリーを持ちます。
- ルート以外の非リーフノードのキーワード数は⌈m/2⌉-1 <= n <= m-1
- 操作：追加、削除、変更、構築
B+ツリー：定義：上記の通り：
各分岐ノードは最大m個の部分木を持ちます。
ルートノードにはサブツリーがないか、少なくとも2つのサブツリーがあります。
ルート以外のブランチノードは、少なくとも⌈m/2⌉のサブツリーを持ちます。
n 個のキーワードを持つ n 個のノードを持つ n 個のサブツリーがあります。
すべてのリーフノードにはすべてのキーワードと対応するレコードへのポインタが含まれ、リーフノードのサイズはキーワード
順次リンク：すべての分岐ノードは、最大のキーワードとその子ノードへのポインタのみを各子ノードに含みます。
V. 数字
定義：
- グラフ：グラフGは、2つの集合V（頂点の有限の非空集合）とE（頂点の辺の有限集合）から構成され、G =と表記します。
- 無向グラフ：グラフGにおいて、集合Eは無順序
- 有向グラフ：グラフ G において、集合 E は順序付けられます。
- 完全グラフ：グラフのすべての2頂点間に辺が存在 完全無向グラフはn(n-1)/2の辺を持ち、完全有向グラフはn(n-1)の辺を持つ
- 端点と近傍：
- 頂点の次数： 無向グラフでは、頂点の辺の数をその点の次数と呼び、有向グラフはアウト度とイン度に分けられ、アウト度＋イン度＝次数 e個の辺を持つグラフでは、次数の和＝2＊e
- 部分グラフ：それぞれ部分集合である頂点と辺の集合からなるグラフ
- 経路と経路の長さ：グラフにおいて、頂点iから頂点jへの経路は頂点の並びであり、経路が通過する辺の数が経路の長さです。経路上のすべての頂点が異なる場合、経路は単純経路と呼ばれます。
- 木グラフ：任意の2つの頂点間に1つの経路のみを持つ無向連結グラフ n頂点の木グラフはちょうど1つの辺を持ちます。
- ループまたはリング：同じ点から始まり、同じ点で終わるパス 単純なパスのリングは、単純ループまたは単純リングと呼ばれます。
- 連結性、連結グラフ、連結成分： 無向グラフGにおいて、頂点iが頂点jへのパスを持っている場合、iからjは連結されていると言う； グラフ内の任意の2頂点が連結されている場合、Gは連結されていると言い、そうでない場合は非連結グラフ。
- 強連結グラフ、強連結成分：有向グラフGにおいて、任意の2つの頂点iとjが連結している場合、グラフGは強連結グラフであり、そうでない場合は非強連結グラフである；有向グラフGの極端に連結された部分グラフをGの強連結成分と呼ぶ 強連結グラフの強連結成分はそれ自身のみであり、非強連結グラフは複数の強連結成分を持つ
- 密なグラフ、疎なグラフ：グラフが完全グラフに近い場合は密なグラフと呼び、グラフに含まれる辺の数が少ない場合は疎なグラフと呼びます)
特性:
- グラフ中の次数iの頂点の数をn(i)とすると、無向連結グラフではn(0)=0。
- 無向連結グラフが n 個の頂点と e 個の辺を持ち、すべての頂点の次数が m より小さい場合、次式が成り立ちます：
- n = n(m) + ......+ n(2) + n(1) + n(0)
- すべての頂点の次数の和 = 2 * e
- すべての頂点の次数の和 = m * n(m) + ......+ 2 * n(2) + 1 * n(1)
グラフの保存
隣接行列
無向の密なグラフでよく使われる、行列の圧縮保存を使うことで容量を大幅に節約、辺の情報を保存 頂点の次数、次数、内次数、辺の数と頂点の数の関係、何が便利で何が不便か？
#define MaxVertexNum 100 // 最大頂点数
typedef char VertexType; // 頂点のデータ型
typedef int EdgeType; // 重み付きグラフの辺の重みのデータ型
typedef struct {
VertexType Vex[MaxVertexNum]; //
EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 隣接行列、サイドテーブル
int vexnum, arcnum; // 現在のグラフの頂点と弧の数
} MGraph;
特徴
無向グラフの隣接行列は対称行列であるため、通常、上三角行列はストレージに格納されます。
無向グラフの隣接行列の場合、i行目の0でない要素の数は、ちょうどi番目の頂点の次数
有向グラフの隣接行列において、i行目の0でない要素の数は、ちょうどi番目の頂点のアウトディグリーです。
グラフを隣接行列で保存すると、2つの頂点の間に辺があるかどうかを簡単に判断できますが、辺の数を調べるには行列全体を走査しなければなりません。
密なグラフは、隣接行列を使った保存に適しています。
隣接結合表
有向グラフでよく使われる、逐次表＋リンクリストを使って容量を大幅に節約、ノードの情報を格納 頂点の次数、次数、内次数、辺の数、頂点の数の関係をどう見るか、何が便利で何が不便か。
#define MaxVertexNum 100 // 最大頂点数 typedef struct ArcNode { // エッジテーブルノード
int adjvex; // この辺が指す頂点
struct ArcNode *next; // 次のエッジを指す
} ArcNode; typedef struct VNode { // 頂点テーブルノード
VertexType data;
ArcNode *first; // 頂点が指す最初の辺
} VNode, AdjList[MaxVertexNum]; typedef struct {
AdjList adjlist; //
int n, e; // グラフの頂点と辺の数
} AGraph;
特徴
無向グラフの場合、必要な記憶容量はO(|V| + 2|E|) 各辺が2回現れる; 有向グラフの場合、必要な記憶容量はO(|V| + |E|)
隣接表は疎な行列を格納するのに適しています。
グラフを隣接表で保存すると、任意の頂点のすべての隣接エッジを簡単に決定できますが、2点間にエッジがあるかどうかを決定するには、対応するノードを見つけるために別のノードにジャンプする必要があります。
有向グラフでは、隣接表の1行がその頂点のアウト度を表し、イン度を求めるには隣接表をトラバースする必要があります。
テーブルを構築する際のエッジノードのリンク順序は任意であり、テーブルを構築するアルゴリズムとエッジの入力順序に依存するため、隣接テーブル表現は一意ではありません。
連結リスト
有向グラフのための代替連鎖記憶構造
複数隣接行列 無向グラフの代替連鎖記憶構造
グラフの走査
幅優先走査
バイナリツリーに似た階層的なトラバーサル・アルゴリズム
深さ優先探索
バイナリツリー型事前探索アルゴリズム
最小スパニングツリー
ループのない無向グラフを樹形図と呼び、重み付きグラフでは、重みが最小の樹形図を最小スパニングツリーと呼びます。
Primmのアルゴリズム 毎回、現在の頂点から最も重みの小さい辺を選択して結合し、次の頂点でも同様に結合する頂点を選択する構成的なアルゴリズム。ループは許されず、結合できる頂点が他に存在しない場合は、n個の頂点が結合されるまで、前の頂点に戻って選択を行うという選択が行われます。 時間複雑度O(n^2)は辺の数に依存しないので、密なグラフに適しています。
クラスカルのアルゴリズム
重みの小さいエッジから始め、ループが形成された場合は2番目に小さいエッジを選択し、n-1個のエッジが追加されるまで、重みの大きい順に適切なエッジを選択して最小スパニングツリーを構築します。
時間複雑度O(e*log(2))が頂点木に依存しないため、疎なグラフに最適。
最短経路
ダイクストラアルゴリズム
シングルソースショートパスアルゴリズムとも呼ばれます：
頂点iを選び、頂点iから残りの頂点までの重みを配列dist[]に入れます；
頂点iからの重みが最も小さい頂点jが選択されます；
jから残りの頂点までの重みを計算；
残りの頂点に対するjの重みと、残りの頂点に対するiの重みを比較し、重みの方が小さければdist[]を更新；
すべての頂点が追加されるまで、上記の手順を繰り返します。
時間の複雑さはO(n^2)
フロイトのアルゴリズム
マルチソースショートパスアルゴリズムとしても知られています。
AOVネットと位相幾何学的順序付け 有向無サイクルグラフと呼ばれるループのない有向グラフで、頂点が位相幾何学的順序と呼ばれるものをAOVネットと呼びます 有向グラフの位相幾何学的順序を見つけるプロセスを位相幾何学的順序付けと呼びます： 1. 有向グラフから先行詞のない頂点を選んで出力する。3.残りのネットから入射率0を持つ頂点がなくなるまで繰り返す トポロジカル・ソートは、一意でないトポロジカル・シーケンスを生成し、その時間複雑度はO(n + e)です。
AOEネットとクリティカルパス
一般化表
定義：
一般化された表は、n個の要素からなる有限列、GL =
通常のプレゼンテーション
A = Aは空のテーブル、'#'は一般化されたテーブル要素を示さない、テーブル長は0、テーブルの深さは1、ヘッダーテーブルの終端はなし B = Bは、長さ1、深さ1の単一要素eのみを含む表。 C = ) Cは、長さ2、深さ2の1つのアトムと1つのサブテーブルを含むテーブルです。 D = = = , , )) Dは、長さ3、深さ3の3つのサブテーブルを含むテーブルです。 E = , , c)) Eは、長さ1、深さ4のサブテーブルを含むテーブル。 一般化された表の深さ：一般化された表に含まれる括弧の繰り返しの数。
テーブルのヘッダー：一般化されたテーブルの最初の要素a1はヘッダーと呼ばれます。
テール：一般化されたテーブルのヘッド以外の要素で構成される部分テーブルをテールと呼びます（例えば、Bのテールは、Dのテールは、））、テールは常に一般化されたテーブルです 追伸：フェッチテーブルヘッドの操作 head[GL] = a1、フェッチテーブルテールの操作 tail[GL] = a1、フェッチテーブルテールの操作 tail[GL] = a1。
一般化されたテーブルのストレージ構造：
一般化されたテーブルは、一般的にチェーンストレージ構造を使用し、メインの弟ストレージ構造は、ツリーとして一般化されたテーブルとして見ることができますし、バイナリツリーに従って格納するために
typedef struct GLNode {
int tag; // 0原子ノード; 1: テーブル/サブテーブル・ノード
struct GLNode *link; // 後続要素または兄弟要素へのポインタ
union {
ElemType data; // 原子の値
struct GLNode *sublist; // 最初の要素へのポインタ
} val;
} GLNode;
追伸：一般化表、配列、線形表の関係：
- 配列は、同じプロパティを持つ有限のデータ要素のシーケンスであり、各要素は一意の添え字で修飾されます。
- 一般化されたテーブルとは、有限個のデータ要素の並びのことで、各データ要素はアトムにもサブテーブルにもなり、要素は互いに線形関係にあります。
- 線形表とは、同じ特性と要素間の線形関係を持つ有限のデータ要素の集まり。
検索
ルックアップテーブルの操作は、通常以下のようなものです：
- 特定のデータ要素がルックアップテーブルに存在するかどうかを照会ます。
- 条件を満たす特定のデータ要素のさまざまな属性を取得します。
- ルックアップテーブルへのデータ要素の挿入
- ルックアップテーブルからの特定のデータ要素の削除
静的ルックアップテーブル
じゅんじょたんさく
線形検索とも呼ばれ、主に線形テーブルのキーワードの「順序付き」検索と「順序なし」検索に使用されます。
非順序ルックアップ・テーブルで成功したルックアップの平均長：/2 失敗したルックアップの平均長：
順序付きルックアップ・テーブルで成功したルックアップの平均長さ： /2 失敗したルックアップの平均長さ： n/
半折ルックアップはバイナリ・ルックアップとも呼ばれ、順序付きシーケンシャル・テーブルにのみ適用されます。
成功したルックアップの平均長さ：[log(2)
検索に失敗した場合の平均の長さ：
チャンクサーチ
すなわち、ブロック内では順序なし、ブロック間では順序あり、各ブロックの最大のキーワードは2番目のブロックのすべてのキーワードより小さく、インデックス・テーブルは各ブロックの最大のキーワードとそのブロックの開始テーブルで構成される。 長さnのルックアップテーブルは、s個のレコードからなるb個のブロックに一様に分割される。 ブロック内およびインデックス付きテーブルで逐次ルックアップを使用する場合：ルックアップに成功した場合の平均ルックアップ長：（s^2 + 2*S + n) / (2 * s) = sqrt(n)，最小値はsqrt+1 インデックス付きテーブルで半折ルックアップを使用する場合：ルックアップに成功した場合の平均ルックアップ長： ⌈log(b+1) + (s + 1) / 2
動的ルックアップテーブル
バイナリ並べ替えツリー検索
BツリーとB+ツリー
ルーズリーフ
ハッシュ関数としても知られ、ストレージアドレスは主にハッシュ関数によって構築されます：
直接アドレス指定法：H = a
剰余法：H(key) = key%p 通常pは最大の素数をとります。
数値解析：ハッシュアドレスとして、より均等な桁数のビットを選択します。
二乗法：キーワードの二乗の中央ビットをハッシュアドレスとします。
折りたたみ法：キーワードを同じビット数の複数の部分に分割し、それらの部分のスタックの合計をハッシュアドレスとします。
乱数法：H(key) = random(key)は、キーワードの長さが等しくない場合に使用すると良いでしょう。
アドレスの競合に対処するためのアプローチ：
オープンアドレス法：競合するハッシュアドレスを独立変数とし、何らかのハッシュ競合関数によって新しい空きハッシュアドレスを取得します。
- 線形プロービング法：H = +i)%m 0<=i<=m-1
- 2乗プロービング法：H = +d)%m d=d+i^2 0<=i<=m-1
- ダブルハッシュ: H = +i*H(key))%m
ハッシュテーブルの各セルには、対応する同義語の単一リンクテーブルの先頭へのポインタが格納されます。
充填係数：n/m（nは充填される要素の総数、mは次の要素の数である。%以下の番号) ハッシュテーブルの平均ルックアップ長は、テーブルのレコード数やテーブルの長さではなく、負荷係数の大きさに依存する。 _Ps.各手法の表をどのように埋めるか？マッチ検索に成功した平均数？失敗したルックアップの平均数は？_
内部ソート
並べ替えの安定性：並べ替えの対象となるテーブルの中に、同じキーワードを持つ要素が複数あり、並べ替え後も同じキーワードを持つ要素間の相対的な順序が変わらない場合、この並べ替えは安定であるといい、そうでない場合は不安定であるといいます。
L[]はテーブルを表し、L()はメタを表します。
挿入ソート：
このアイデアは、すべてのレコードが挿入されるまで、そのキーワードのサイズに従って、一度に1つのソートされるレコードを前の「ソートされた部分列」に挿入することです。
ダイレクトインサートソート
- L(i)がL[1......i-1]のどの位置kに挿入されているかを調べます。
- L[k......i-1]の全要素を1つ後ろにシフト。
- LをLにコピー
空間の複雑さ：一定数の補助ユニットのみ使用、O(1)
時間の複雑さ：O(n^2)
安定性：要素が挿入されるたびに、常に後ろから前に比較されて挿入されるため、要素の相対的な位置が変わることがなく、安定したソートです。
適用性：シーケンシャル・ストレージとチェーン・ストレージの場合
特徴：初期要素が逆順の場合に最も実行効率が悪くなり、正順に近いほど実行効率が良くなります。
ハーフ＆ハーフ挿入ソート
まず半分に折って、挿入する要素の位置を探します。
他の要素を均一に移動
への要素の挿入
空間の複雑さ：一定数の補助ユニットのみ使用、O(1)
時間の複雑さ：O(n^2)
安定性：安定した秩序
適用性：シーケンシャル・ストレージとチェーン・ストレージの場合
特徴：直接挿入ソートに基づいてのみ、キーワード比較の数を削減し、要素の移動の数は変更されません。
ヒルソーティング
nよりd(1)小さいステップをとり、テーブルのすべてのレコードをd(1)個のグループに分割します。
距離がd(1)の倍数であるレコードはすべて同じグループに入れられ、グループ間で直接挿入ソートが実行されます。
2番目のステップd(2) < d(1)を選び、上記の2つのステップを繰り返します。
dが1の値をとるまで続け、次に直接挿入ソートを行います。
空間の複雑さ：一定数の補助ユニットのみ使用、O(1)
時間の複雑さ：O（n^1.3）安定性：同じキーワードレコードが異なるサブテーブルに分割され、相対的な順序が変更され、不安定なソートに属する適用可能性：シーケンシャルストレージにのみ適用可能特徴：正順のシーケンスが最も効率的であるときにソートされるように、逆順は最悪です。
スワップソート
バブリングソート
- 最初の要素から始めて、隣り合う要素の値を前から順に2つずつ比較します。
- L[i-1]>L[i]の場合、2つの値を交換します。
- 2番目の要素から始め、上記の手順を繰り返します。
- 最後の2つの要素まで比較して、ソート終了
空間の複雑さ：使用するプットの数は一定で、O(1)
時間の複雑さ：O(n^2)
安定性：安定した秩序
適用性：シーケンシャル・ストレージとチェーン・ストレージの場合
特徴：配列される順番が近いほど、効率が高くなります。
ラピッドソーティング
パーティショニングの考え方に基づくバブリングソートの改良で、すべての内部ソートの中で最も平均性能が高いアルゴリズムです。
- 並べ替え対象表のベンチマーク・ピボットを選択し、並べ替え対象表をL[1......k-1]とL[k+1......n]に分割します。
- L[1......k-1]のすべての要素がL[k+1......n]の要素より小さくなるように、要素はピボットと常に比較され、最終的にピボットがL(k)
- クイックソートが終了すると、2つのパートそれぞれで新しいベースピボットが選択され、次のソートが実行されます。
- 各セクション内の要素が1つになるか、空っぽになるまで繰り返します。
空間の複雑さ：スタックを使用、最悪の場合O(n)、平均的な場合O(log(2)) 時間の複雑さ：分割アルゴリズムに関連、最悪の場合O(n^2)、最良の場合O(n*log(2)) 安定性：分割アルゴリズムでは、右の区間に2つの同じキーワードがある場合、クイックソートに移動すると相対的な順序が変わり、ソートが不安定になります。適用可能性：シーケンシャルなストレージにのみ適用可能 特徴：ランダムに分散しているほど効率が高く、順序が多いほど効率が低い。
選択ソート：
シンプルな選択ソート
- 配列を2つの部分L[0......i-1]順序付きとL[i......n-1]順序なしに分け、順序付き領域のキーワードはすべて順序なし領域のキーワードより小さい。
- 順序なし領域L[i......n-1]の中で最小のキーワードL(i)を選択。
- L(i)をL[0......i-1]に追加すると、L[0......i]は順序付きになります。
- キーワードがなくなるまで、この作業を繰り返します。
空間的複雑性： 一定数の補助ユニットのみが使用され、O(1) 時間的複雑性： O(n^2) 安定性： 不安定なソートに属し、サイズのために順序付けされていない領域の要素の相対的な位置は、順序付けされた領域で変更されます 適用性： 順序付けされたストレージと連鎖したリストに適用可能 特徴： ソート効率は、選択された最小のキーワードの比較であるたびに、比較の数が変化しないため、ソートされるデータに関連していません。
ヒープソート
キーワードが子ノードより小さくない各ノードは「大きなルートヒープ」と呼ばれ、「小さなルートヒープ」はその逆です。
- ソートされるキーワードの最初のシーケンスは、最初の順序なし領域である大きなトップヒープに構築されます；
- ヒープの一番上の要素L[1]と最後の要素L[n]を入れ替えると、この時点で新しい順序なし領域と新しい順序付き領域が得られ、L[1,2...n-1]<=L[n]を満たします；
- 交換後の新しいヒープの先頭R[1]はヒープの性質に反する可能性があるため、現在の順序なし領域を新しいヒープに調整し、L[1]を再び順序なし領域の最後の要素と交換して、新しい順序なし領域と新しい順序付き領域を得る必要があります。順序付き領域の要素数がn-1になるまでこの処理を繰り返すと、ソート処理全体が完了します。
空間計算量：インプレース・ソート、ヒープ用補助空間、O(1) 時間計算量：O(nlog(2)n) 適用性：シーケンシャル・ストレージ、チェーン・ストレージに最適 特徴：ソート効率はソートされるデータとは無関係であり、毎回確実に最小のキーワードが選択されます。
サブサンプション・ソート
シーケンスは長さ1のn個の順序テーブルと考え、各ラウンドで隣接する順序テーブルがマージされ、マージ処理中にソートされます。
空間の複雑さ：再帰を使用してO(n)
時間の複雑さ：O(nlog(2)n)
安定性：安定した選別
適用性：シーケンシャルストレージに最適
特徴：ソート効率はソートされるデータに依存せず、各ラウンドで生成される順序付き領域は必ずしも大域的に順序付けされたものではありません。
基本ソート：
キーワードのサイズを比較する代わりに、キーワードの各ビットの値に従ってソートします。
空間の複雑さ：再帰を用いたO(n+r)
時間の複雑さ：O(d(n+r))
安定性：安定した選別
適用：
特徴：各ラウンドで生成される順序付きゾーンは、必ずしもグローバルに順序付けされているわけではありません。
ヒルソート、直接挿入ソート、クイックソート、サブサンプションソートでは、大域的に順序付けられた領域は生成されません。
ソートアルゴリズム比較表：
