双重链接列表插入排序错误

我已经从10000个文件的双向链接列表（从最高到最低）实施插入排序，并以相反的顺序输出到文件。双重链接列表插入排序错误

据我所知，我已经实现了这样一个程序，但我注意到在输出文件中，单个数字是不合适的。每个其他号码的顺序都是正确的。

不合格的数字是一个重复的数字，但这个数字的其他重复是正确的顺序。奇怪的是这个数字是不正确的。未分类号码也只有6个地方不同步。

我已经浏览了我的程序几天，不知道问题出在哪里，所以我转向你寻求帮助。

下面是有问题的代码，

（边注：？可我的问题由我自己被删除，而我的大学不thieve我的代码，如果没有它如何被删除）

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

谢谢你的时间。

来源

2010-04-28 House

您不能删除您的问题。完全通常的数据结构并不经常被盗用。 – Potatoswatter 2010-04-28 00:47:48

好的，谢谢，我想我的代码很防守。 – House 2010-04-28 00:56:28

为什么不使用标准模板库，这是非常好的。 – martsbradley 2010-04-28 19:32:19

我不喜欢这部分

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比所有的值越大，除了这个 - >后台>值会发生什么。它在最后插入，而不是在这之前。顺便说一句，你插入相反的顺序相等的整数，它们被读取。对于整数它并不重要，但如果您插入了其他对象，则可能会出现这种情况。我会将插入方法的代码更改为：

node* temp; 
temp = this->front; 
while(temp!=NULL) 
{ 
    if(temp->value > inValue) 
    { 
     insertBefore(inValue, temp); 
     return; 
    } 
    temp = temp->next; 
} 
insertBack(inValue);

来源

2010-04-28 20:10:33

干杯，我现在明白问题的原因。 – House 2010-04-29 08:42:19

只是一些言论。

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-28 00:55:47 Potatoswatter

感谢您提供一些改进代码的技巧，您的观点将围绕我将研究的环路终端进行。我不确定多个链接约定可能导致单个问题。谢谢。 – House 2010-04-28 01:03:44

双重链接列表插入排序错误

回答

相关问题