私はコンパイラクラスの理解を深めるために小さな問題を実装しようとしています。私は次のようにコンパイルするファイルの束を持っている、と仮定します：これは、次のような問題がある特定のファイルセットのコンパイル順を解決するためにどのアルゴリズムを使用しますか？
bは
cは
eが依存にF
Dのdependesに依存Cに依存して何に依存しますBに
fはしたがって、この場合には正常にコンパイルされるファイルのためのコンパイル順序が、F、C、B、D、Eで何
に依存します。私は自分のアルゴリズムを書いて、練習問題と同じように依存関係を出力したいと思っています。私はリンカが自動的にC++などでそれを行うことを知っていますが、これは単なる個人的な運動です。この問題を解決するにはどうしたらいいですか？私がかなり新しくなったので、アルゴリズム/読み取り値への参照は非常に高く評価されます。
@ajbのコメントに基づいて、素早くGoogle検索を行うと、Topological Sortingのウィキペディアの記事が表示されます。しかし、問題を表現するためにグラフを作成する手間を経なければならない場合は、実際にこれを行う簡単な方法があります。
まず、コンパイルするファイルごとに、ノードを作成します。次に、各ノードからその依存関係へのエッジを持ち、ファイルが依存関係を必要としない場合に特別なノードへのエッジを持ちます。それが完了したら、その特殊なノードからbreadth first searchでエッジを反転させてコンパイルするだけです。
循環依存性やそのジャズのいずれかを心配する必要がある場合は、はるかに複雑になりますが、まだ実行可能です。
あなたは文学のために求めているので、データ構造とアルゴリズムのすべての種類（どのような驚き！）第13章トポロジカル
私はCとC++で30年間プログラミングしてきました。ソースファイルをソートしてコンパイルする必要はありませんでした。ごめんなさい、申し訳ありませんが、これはナンセンスです。 –
@PeteBecker違いを生む言語があります。 OPは単に間違ったタグを使用している可能性があります。あるいは、他の言語をコンパイルするC++でコンパイラを書くことになっているかもしれません。私たちは彼らがOPのクラスでカバーしているものだけを知っているわけではないので、「これはナンセンスです」と結論づけるためのいくつかの不当な仮定をしなければならないと思います。 – ajb
@ajb - 質問がC++に関するものではない場合、C++にタグ付けするべきではありません。それがC++の場合は、ファイルのコンパイルに必要な順序はなく、トポロジカルなソートの提案はナンセンスです。 「OPは単に間違ったタグを使用しただけかもしれない」というのは、言い表せない言葉はもちろんのこと、「不当な前提」であるようです。 –
のグラフアルゴリズムを含む乗り越えてC++でのデータ構造とアルゴリズムという本がありますsort – ajb
"依存する"という意味に依存しますが、堅牢なコードがどのように書かれているかを "使用するコードを使用する"場合、コンパイルする順番は変わりません。リンカはそれらの依存関係を並べ替えます。 –
@PeteBeckerこれは、コンパイルするためのものを取得しようとしている誰かのためのOK答えとなります。しかし、彼はコンパイラクラスを取っていると言いました。コンパイラやリンカが何かを並べ替えることを知りたいと思うと思います。 – ajb