1

入力が空白になるまでユーザーから単語を取得するリンクされたリストを作成しようとしています。すべての単語が追加されるため、リストはアルファベット順に表示されます。ただし、最初のノードのみが出力されます。私が間違っていることはありますか？これが私が持っているものです（ヘッダーと宣言を除く）：

    //put in additional nodes until the input is blank
while(in != " "){
    cin >> in;
    newPtr->data = in;
    prevPtr->data = "";
    prevPtr->next = NULL;
    nextPtr = list;
    //shift the prevPtr and nextPtr until newPtr is alphabetically between them
    while(!(prevPtr->data<=in && nextPtr->data>in)){
        prevPtr = nextPtr;
        nextPtr = prevPtr->next;
    }
    //make newPtr point to the next node
    if(nextPtr != NULL){
        newPtr->next = nextPtr;
    }
    //make newPtr the "next" pointer of the previous node, if any
    if(prevPtr != NULL){
        prevPtr->next = newPtr;
    }
    //if there's nothing before newPtr, make it the first node
    else{
        list = newPtr;
    }
    printList(list);
};

}

4

2 に答える 2

1

何かが足りないのではないかと心配しているので、これをコメントとして投稿しますが、まだこれを行うことができないため、ここでは回答がありません:

std::listを使用できない理由は何ですか? 単語を挿入し、それが空でないかどうかを確認し、すぐに標準の並べ替えアルゴリズムを適用して(並べ替えられたオブジェクトの比較演算子に依存します)、出力することができます。高速で、コードは短くて読みやすく、車輪の再発明に時間を費やす必要はありません。

PS: 空の文字列をテストしたい場合は""、 ではなく" "である必要があると思います。

于 2012-10-16T22:56:51.767 に答える
0

ここには多くの問題があると思います。

最初の繰り返しの 1 つでは、prevPtr->data は何を指していますか? 何も指していないか、メモリに割り当てられていない場合は、まだ何も設定しないでください。

さらに、すべての反復で newPtr にメモリを割り当てる必要があります。そうしないと、リスト内の最後を指している場所のメモリ位置を上書きするだけです。

次に、prevPtr が何かを指していると仮定します。この while ループの 2 回目 (またはそれ以上) で、prevPtr がリスト (prevPtr = nextPtr) のさらに下に移動され、prevPtr->data = " " によってデータが消去されます。その要素。したがって、最初のノードとその後の一連のスペースを出力することができます。

ループが NULL の場合、nextPtr->data がジャンクを指しているため、ループの最初に list が NULL であるかどうかを確認する必要があります。リストのこの NULL チェックは、最初の要素のコーナー ケースになる可能性があります。

このようなことを試してみてください。テストする時間がありませんでしたが、正しい方向に進むはずです:

Node *list = NULL; 

while(in != " "){
    cin >> in;
    Node *newPtr = new Node();
    newPtr->data = in;
    newPtr->next = NULL;

    prevPtr = list;
    nextPtr = list;

    // Do we have an empty list
    if(list != NULL)
    {
        // Corner Case: First on the list
        if(newPtr->data <= prevPtr->data)
        {
            list = newPtr;
            newPtr->next = prevPtr;
        }
        else
        {
            // CASE: Somewhere between the first and the list
            while(nextPtr->next != NULL)
            {
                nextPtr = nextPtr->next;
                if(newPtr->data >= prevPtr->data && newPtr->data <= nextPtr->data)
                {
                    prevPtr->next = newPtr;
                    newPtr->next = nextPtr;
                    break;
                }
                prevPtr = prevPtr->next;
            }

            // Corner Case: end of list
            if(nextPtr->next == NULL)
            {
                nextPtr->next = newPtr;
            }
        }
    }
    else 
    {
        // Corner Case: We had an empty list
        list = newPtr;
    }
    printList(list);
于 2012-10-16T23:08:02.667 に答える