2

10,000 intのファイルからダブルリンクリスト（最高から最低）に挿入ソートを実装し、逆の順序でファイルに出力しました。

私の知る限り、私はそのようなプログラムを実装しましたが、出力ファイルで気づいたのですが、1つの番号が適切ではありません。他のすべての番号は正しい順序です。

場違いの番号は繰り返し番号ですが、この番号の他の繰り返しは正しい順序になっています。この番号が間違って配置されているのは奇妙なことです。また、ソートされていない番号は、同期していない6つの場所だけです。

私は何日もプログラムを調べてきましたが、問題がどこにあるのかわからないので、助けを求めます。

以下は問題のコードです、

（補足：私の質問は自分で削除できますか？むしろ私の大学は私のコードを盗むことはありませんが、そうでない場合はどうすれば削除できますか？）

    void DLLIntStorage::insertBefore(int inValue, node *nodeB)
{
    node *newNode;
    newNode = new node();
    newNode->prev = nodeB->prev;
    newNode->next = nodeB;
    newNode->value = inValue;

    if(nodeB->prev==NULL)
    {
        this->front = newNode;
    }
    else
    {
        nodeB->prev->next = newNode;
    }
    nodeB->prev = newNode;
}
void DLLIntStorage::insertAfter(int inValue, node *nodeB)
{
    node *newNode;
    newNode = new node();
    newNode->next = nodeB->next;
    newNode->prev = nodeB;
    newNode->value = inValue;

    if(nodeB->next == NULL)
    {
        this->back = newNode;
    }
    else
    {
        nodeB->next->prev = newNode;
    }   
    nodeB->next = newNode;
}
void DLLIntStorage::insertFront(int inValue)
{   
    node *newNode;
    if(this->front == NULL)
    {
        newNode = new node();
        this->front = newNode;
        this->back = newNode;
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->value = inValue;
    }
    else
    {
        insertBefore(inValue, this->front);
    }

}   
void DLLIntStorage::insertBack(int inValue)
{   
    if(this->back == NULL)
    {
        insertFront(inValue);
    }
    else
    {
        insertAfter(inValue, this->back);
    }
}

ifstream& operator>> (ifstream &in, DLLIntStorage &obj)
{   
    int readInt, counter = 0;               

    while(!in.eof())
    {
        if(counter==dataLength) //stops at 10,000
        {
            break;
        }   

        in >> readInt;

        if(obj.front != NULL )
        {   
            obj.insertion(readInt);         
        }
        else
        {
            obj.insertBack(readInt);
        }
        counter++;
    }       
    return in;
}
void DLLIntStorage::insertion(int inValue)
{
    node* temp;
    temp = this->front;

    if(temp->value >= inValue)
    {
        insertFront(inValue);
        return;
    }
    else
    {       
        while(temp->next!=NULL && temp!=this->back)
        {
            if(temp->value >= inValue)
            {
                insertBefore(inValue, temp);
                return;
            }
            temp = temp->next;
        }
    }

    if(temp == this->back)
    {
        insertBack(inValue);
    }
}

お時間をいただきありがとうございます。

4

2 に答える 2

0

この部分が気に入らない

else
{       
    while(temp->next!=NULL && temp!=this->back)
    {
        if(temp->value >= inValue)
        {
            insertBefore(inValue, temp);
            return;
        }
        temp = temp->next;
    }
}

if(temp == this->back)
{
    insertBack(inValue);
}

inValue が this->back->value 以外のすべての値よりも大きい場合に何が起こるか想像してみてください。この前→後ろではなく、最後に挿入されます。ちなみに、同じ整数を逆順に挿入していると、読み込まれます。整数の場合はそれほど重要ではありませんが、他のオブジェクトを挿入した場合は問題になる可能性があります。挿入メソッドのコードを次のように変更します。

node* temp;
temp = this->front;
while(temp!=NULL)
{
    if(temp->value > inValue)
    {
        insertBefore(inValue, temp);
        return;
    }
    temp = temp->next;
}
insertBack(inValue);
于 2010-04-28T20:10:33.817 に答える
0

いくつかのコメント。

while(!in.eof())

これにより、ループの内部で EOF エラーが発生するのを止めることはできません。あなたがしたい

while ( in >> readInt )

また、

if(this->front == NULL)

と

void DLLIntStorage::insertion(int inValue)
{
    node* temp;
    temp = this->front;

    if(temp->value >= inValue)

混ぜるな。フロントは NULL にすることも、することもできません。同様に、ループ終了条件としてtemp->next!=NULLまたはのどちらを使用するかを決定する必要がありますが、両方を使用する必要はありません。temp!=this->back

私の推測では、複数のリンク規則間の不一致により、誤った値がリストの中央に押し込まれていると思われます。

于 2010-04-28T00:55:47.650 に答える