ソートを実装しています。プログラムは、ASCII 文字を含むテキスト ファイルから読み取ります。スペースで区切られた行ごとに 2 つの要素があります。入力が「a b」であるとします。これは、a と b の優先関係を定義し、「a は b の前に発生する必要がある」と述べています。
したがって、ファイルが
ab 直流 BD
出力は
a b d c
リンクされたリストを 2 つ作成しました
bigList: 一意の要素を保存する (count前の要素を追跡する)smallList: 前の要素を格納する私のコードが何をするかの要約
上記の入力のように、ファイル内のすべての要素を実際に出力します。私の出力は
a b b d d c
私はCプログラミングが初めてで、何が間違っているのか教えてください。
トポロジカルソートについてはよくわかりませんが、賢明なコメントを残すには十分知っていると思います。誰でもこの応答を自由に編集する必要があります。
この実装にはいくつかの問題があります。Cに関連するものもあれば、アルゴリズムに関連するものもあるので、一度に1つずつ見ていきましょう。
問題の定義。 トポロジカルソートは、実際、有向グラフの要素の優先順位として定義されています。ただし、この文だけでは問題を完全に定義することはできません。具体的には、トポロジカルソートは、指定されたソース頂点で始まるグラフの要素の優先順位です。例として、次の有向グラフがあるとします。
a -> b
b -> c
c -> a
頂点から始める場合a、トポロジカル順序はである必要があります{a, b, c}。頂点から始める場合c、トポロジカル順序はである必要があります{c, a, b}。したがって、問題の定義は、ソース頂点がないと意味がありません。そのような頂点の1つの選択肢は、それを指すエッジがないグラフの頂点である可能性があります。つまり、すべての入射エッジは出力エッジです。
覚えておくべきもう1つのことは、グラフの接続性です。他の頂点から任意の頂点に到達できるとは限りません。したがって、そのようなアルゴリズムを実装するときは覚えておく価値があります。
優れたデータ構造は、優れたアルゴリズムの鍵です。有向グラフで物事を並べ替える場合、最善の策は、有向グラフのデータ構造を作成することです。これには、Nodeデータ構造とデータ構造の作成が含まれEdgeます。隣接リストを検索することをお勧めします。このようなデータ構造が整ったら、グラフ上で幅優先探索を実行するだけで、適切な結果としてトポロジの優先順位を取得できます。
隣接リストを実装する場合でも、すべての要素を1か所に保存する必要があります。リンクリストは、挿入するのに一定の時間がかかり（データの並べ替えを想定）、1つを検索するのに直線的な時間がかかるため、通常、これを行うのに最適な方法ではありません。それは最適ではありません。@ David RFが示唆したように、赤黒木とAVL木が進むべき道です。ただし、この最適化からは始めません。正常に機能するアルゴリズムがある限り、ストレージデータ構造をいつでも改善できます。結局のところ、リンクリストと検索ツリーへのインターフェイスは同じです。
適切なアルゴリズムを使用すれば、アルゴリズムは高速になります。私は実際にはトポロジーの種類を扱ったことがないので、すべての複雑さとすべてのエッジケースを知りません。だが！従来のノードエッジデータ構造を使用した幅優先検索でこれを行う場合（エッジはノード内で暗黙的に定義できることに注意してください）、検索自体は幅優先検索を使用して線形時間を取る必要があります。
私はあなたのアルゴリズムを読み通しました、そして私はあなたの大きなリストと小さなリストの概念を完全に理解していないことを認めなければなりません。あいまいな名前は実際には役に立ちません。おそらくそれはどこかに隠れている単一の小さなバグで仕事をしますが、それはあまり読みやすくありません。たぶん、他の誰かがあなたの現在の実装についてコメントすることができます。