我已经从一个包含 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);
}
}
谢谢你的时间。
最佳答案
我不喜欢这部分
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 之外的所有值会发生什么。它被插入到末尾,而不是在 this->back 之前。顺便说一句,您正在以相反的顺序插入相等的整数,它们被读取。对于整数来说,这无关紧要,但如果您插入了其他对象,它就可以了。我会将插入方法的代码更改为:
node* temp;
temp = this->front;
while(temp!=NULL)
{
if(temp->value > inValue)
{
insertBefore(inValue, temp);
return;
}
temp = temp->next;
}
insertBack(inValue);
关于c++ - 双链表插入排序Bug,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2726130/