雙重鏈接列表插入排序錯誤

我已經從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

雙重鏈接列表插入排序錯誤

回答

相關問題