双链表插入排序错误

Question

我已经在 10,000 个整数的文件的双链接列表（从最高到最低）中实现了插入排序，并以相反的顺序输出到文件。

据我所知，我已经实现了这样一个程序，但是我注意到在输出文件中，有一个数字不合适。所有其他数字均按正确顺序排列。

不在位置的数字是重复的数字，但该数字的其他重复顺序都是正确的。奇怪的是这个数字是如何错误放置的。另外，未排序的数字只有 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);
    }
}

谢谢您的时间。

Answer 1

我不喜欢这部分

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);

Answer 2

只是一些评论。

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 作为循环终止条件，但不能同时使用两者。

---

我的猜测是，多个链接约定之间的一些不一致导致错误的值被推到列表的中间。