データ構造の一般化されたリスト
このセクションでは、一般化されたリストを表示します。一般化されたリストは次のように定義できます-
一般化されたリストLは、n個の要素の有限シーケンスです（n≥0）。要素eiは、アトム（単一要素）または別の一般化されたリストのいずれかです。アトムではない要素eiは、Lのサブリストになります。Lが（（A、B、C）、（（D、E）、F）、G）であるとします。ここで、Lにはサブリスト（A、B、C）、サブリスト（（D、E）、F）、およびアトムGの3つの要素があります。ここでもサブリスト（（D、E）、F）には2つの要素があります。サブリスト（D、E）およびアトムF。
C ++では、以下のような一般化リスト構造を定義できます-
class GeneralizedListNode{
private:
GeneralizedListNode *next;
bool tag;
union{
char data;
GeneralizedListNode *down;
};
}; したがって、タグがtrueの場合、ノードによって表される要素はサブリストです。ダウンは、サブリストの最初のノードを指します。タグがfalseの場合、要素はアトムです。次のポインタは、リスト内の次の要素を指します。リストは次のようになります。
-
データ構造における適応型マージとソート
アダプティブマージソート アダプティブマージソートは、ソートされたサブリストのマージソートを実行します。ただし、最初のサブリストのサイズは、サイズ1のサブリストではなく、要素のリスト間の順序の存在に依存します。たとえば、図のリストについて考えてみます。 2つのソートされたサブリストで構成されています。 要素16、15、14、13を含むサブリスト1。 要素9、10、11、12のサブリスト2。 サブリスト1はソートされていますが、逆の順序になっています。したがって、サブリスト1は、図に示すように逆になります。 サブリストが見つかると、マージプロセスが
-
データ構造の隣接リスト
グラフは非線形のデータ構造です。これは、ノードを使用したデータと、エッジを使用したそれらの関係を表します。グラフGには2つのセクションがあります。頂点とエッジ。頂点はセットVを使用して表され、エッジはセットEとして表されます。したがって、グラフ表記はG（V、E）です。アイデアを得るための1つの例を見てみましょう。 このグラフには、5つの頂点と5つのエッジがあります。エッジが方向付けられます。例として、頂点BとDを接続するエッジを選択した場合、ソース頂点はBで、デスティネーションはDです。したがって、BをDに移動することはできますが、DからBに移動することはできません。 グラフは非線形