0

私はコロラド メサ大学の csci の学生です。部門長は、リンクされたリストの根拠のある方法を教えています。

struct nodeType
{
    int id;
    nodeType *link;
};

void createList(nodeType *&head, nodetype *&tail)
{
    head = new nodetype;
    tail = new nodetype;
    head->id=-1; //some initialize value
    head->link=tail;
    tail->link=NULL;
}

void insertList(nodeType *&head, nodeType *&tail)
{
    nodetype *knew,*prior, *next;
    knew = new nodetype;

    knew ->name = name

    prior = head;
    next = head->link;
    while(next != tail && knew->id > next->id)
    {
        prior = next;
        next = next->link;
    }

    prior->link = knew;
    knew->link = next;
}

彼女は明白な理由でこれを教えています。接地されたヘッドとテールを使用すると、上記の関数を呼び出してから挿入する方が簡単です。次に、これらの 2 つのノード内のすべてのデータを追加する関数を記述します。ヘッドを削除しないため、削除関数を記述するときは少し簡単です。またはテール、したがって、リストを失い、ガベージを作成するのが難しくなります。

私のアルゴリズムの教授は、「現実世界で」リストに遭遇する他のすべての場所では、根拠のないリストの方が優れていると言っています。STL やインターネットを使用する他の言語では、頭と尾を実装するリスト関数は見つかりません。

教授が現実世界と考えているものではなく、実際の現実世界でのプログラミングの準備をしたいだけなので、私の質問は次のとおりです。両方を念頭に置いて各問題？

この確執を解決するために時間を割いていただき、ありがとうございます。

4

1 に答える 1

0

「現実の世界」では、他のプログラマーが設計、実装、最適化、およびテストしたリストを使用しますが、それが「根拠のある」ものかどうかはわかりません。これは実装の詳細にすぎないためです。

アルゴリズムのコースから学ぶべき重要なことは次のとおりです。

  • 性能特性。リンクリストまたはベクトルのランダムアクセスは高速ですか? より速い追加？最初の要素のより速い除去? 適切なコンテナーを使用することは、時期尚早の最適化ではありません。

  • デバッガーを使用してコードをステップ実行する必要がある場合でも、非常に混乱しないように、さまざまな実装スタイルを十分に確認してください。リストの終わりのテストが true を返すのを見たが、次のノード ポインターが NULL でない場合、これまで「根拠のある」リストの実装を見たことがない場合は、おそらく本当に混乱するでしょう。

于 2012-02-06T23:16:04.297 に答える