Дважды связанный список Ошибка сортировки вставки

Question

Я внедрил сортировку вставки в список двойных ссылок (от наивысшего к наименьшему) из файла из 10 000 целых чисел и вывод в файл в обратном порядке.

Насколько я знаю, я реализовал такую ​​программу, однако, я заметил, что в файле ouput один номер неуместен. Каждый другой номер находится в правильном порядке.

Число неуместно - это повторяющееся число, но другие повторы этого числа находятся в правильном порядке. Просто странно, как это число неправильно помещено. Кроме того, несортированный номер находится всего в 6 местах.

Я просматривал свою программу в течение нескольких дней, не представляя, где проблема, поэтому я обращаюсь к вам за помощью.

Ниже приведен код, о котором идет речь,

(примечание стороны:? Может ли мой вопрос будет удален сам, а мои колледжи DonT воруют мой код, если не так, как он может быть удален)

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->> бэк значение. Он вставлен в конце вместо этого -> назад. Кстати, вы вставляете равные целые числа в обратном порядке, они читаются. Для целых чисел это не имеет значения, но может быть, если вы вставили другие объекты. Я бы изменил код метода вставки:

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, но не оба, как условие завершения цикла.

---

Мое предположение было бы, что некоторое несоответствие между несколькими конвенциями увязывания вызывает странствующее значение, чтобы проталкивается в середину списка.