在雙向鏈表中插入排序

Question

我從頭開始在C++中創建一個列表，而不是使用STL列表函數。我的程序專爲用戶在列表中插入一個新項目（字符串）而設計，一次一個。這些項目應該在插入時進行排序，並且部分工作。用戶應該能夠向前和向後打印它們。

實例：

• 我插入：1，3，2 - 結果前方：1，2，3 - 向後：3，2,1
• 我插入1，3，2,4 - 結果向前：1，4，2，3 - 向後：3，2，4，1
• 我插入4，2，3 - 結果向前：2,3,4 - 向後：4,3,2
• 我插入4,2,3,1 - 結果向前：1,4向後：1,3重複直到程序崩潰

這些是幾個例子，我可以包括更多。我不能爲我的生活看到我的代碼有什麼問題。我從我認識的人那裏得到了很多偉大編程人員的幫助，但是他們看了幾個小時後卻看不到問題。我已經堅持了好幾天了，我只是看不到它。

這裏是我的代碼（註釋是在挪威，對不起！）：

的main.cpp

#include <iostream> 
#include <cstdlib> 
#include <string> 

using namespace std; 

//definerer noden 
struct node 
{ 
    string data; //det noden inneholder 
    node* next;  //nestepeker 
    node* prev;  //forrigepeker 
}; 

//definerer funksjonene 
bool isEmpty(node* first); 
char menu(); 
void insertAsFirstElement(node* &first, node* &end, string data); 
void insert(node* &first, node* &end, string data); 
void remove(node* &first, node* &end, string data); 
void showList(node* first); 
void printBackwards(node* end); 


//er noden tom? 
bool isEmpty(node* first) 
{ 
    if(first == NULL) 
     return true; 
    else 
     return false; 
} 


//sender valgskjermen til konsollen 
char menu() 
{ 
    char choice; 

    cout << "Welcome to LISTOMANIA 3000x! \n" << endl; 
    cout << "Press <1> to add an item" << endl; 
    cout << "Press <2> to remove item on top" << endl; 
    cout << "Press <3> to display the list forward" << endl; 
    cout << "Press <4> to display the list backwards" << endl; 
    cout << "Press <5> to exit" << endl; 
    cout << "\nInput: "; 

    cin >> choice; 

    return choice; 
} 


//hvis lista er tom, sett inn node som første element: 
void insertAsFirstElement(node* &first, node* &end, string data) 
{ 
    cout << "temp is first\n"; 
    node* temp = new node; 
    temp->data = data; 
    temp->next = NULL; 
    temp->prev = NULL; 
    first = temp; 
    end = temp; 
} 


//hvis lista ikke er tom, sett inn noden sortert: 
void insert(node* &first, node* &end, string data) 
{ 
    if(isEmpty(first)) 
    { 
     insertAsFirstElement(first, end, data); 
    } 
    else 
    { 
     node* temp = new node; 
     temp->data = data; 
     node* n = first; 

     while(n) 
     { 
      if(n->data > temp->data) 
      { 

       cout << "temp BEFORE n" << endl; 
       temp->prev = n->prev; 
       temp->next = n; 
       n->prev = temp; 

       if(temp->prev) 
       { 
        temp->prev->next = temp; 
       } 
       else 
       { 
        first = temp; 
       } 
      } 
      else if(n->data <= temp->data) 
      { 
       cout << "temp AFTER n" << endl; 
       //temp = new node; 
       //temp->data = data; 
       temp->prev = n; 
       temp->next = n->next; 
       n->next = temp; 

       if(temp->next) 
       { 
        temp->next->prev = temp; 
       } 
       else 
       { 
        end = temp; 
       } 
       break; 
      } 

      n = n->next; 
     } 
    } 
} 


//sletter valgt node 
void remove(node* &first, node* &end, string data) 
{ 
    string delItem; 
    node* temp;  

    if(isEmpty(first)) 
     cout << "\nNothing to delete, the list is empty!\n------------------------------------------------\n------------------------------------------------\n"; 
    else if(first == end) 
    { 
     cout << "\nYou removed <" << first->data << ">!" << endl; 
     delete first; 
     first = NULL; 
     end = NULL; 
     cout <<"------------------------------------------------\n------------------------------------------------\n"; 
    } 
    else 
    { 
     node* temp = first; 
     cout << "You removed <" << temp->data << ">!" << endl; 
     first = first->next; 
     delete temp; 
     cout <<"------------------------------------------------\n------------------------------------------------\n"; 

    } 
} 


//skriver ut listen alfabetisk 
void showList(node* first) 
{ 
    node * temp = first; 

    if(isEmpty(first)) 
    { 
     cout << "\nThe list is empty!\n"; 
    } 
    else 
    { 
     cout << "\nThe list contains: \n\n"; 
     while(temp != NULL) 
     { 
      cout << temp->data << endl; 
      temp = temp->next; 
     } 
    } 

    cout << "------------------------------------------------\n"; 
    cout << "------------------------------------------------\n"; 
} 


//skriver ut listen omvendt alfabetisk 
void printBackwards(node* end) 
{ 
    node * temp = end; 

    if(isEmpty(end)) 
    { 
     cout << "\nThe list is empty!\n"; 
    } 
    else 
    { 
     cout << "\nThe list contains: \n\n"; 
     while(temp != NULL) 
     { 
      cout << temp->data << endl; 
      temp = temp->prev; 
     } 
    } 

    cout << "------------------------------------------------\n"; 
    cout << "------------------------------------------------\n"; 
} 


//mainfunksjon 
int main() 
{ 
    node* first = NULL; 
    node* end = NULL; 
    char choice; 
    string data; 

    do 
    { 
     choice = menu(); 

     switch(choice) 
     { 
      case '1': cout <<"\nPlease add something to the list: "; 
         cin >> data; 
         insert(first, end, data); 
         cout << "------------------------------------------------\n------------------------------------------------\n"; 
         break; 
      case '2': remove(first, end, data); 
         break; 
      case '3': showList(first); 
         break; 
      case '4': printBackwards(end); 
         break; 
      case '5': cout << "\nSystem exit...\n"; 
         break; 
      default: cout << "\nInvalid input!\n------------------------------------------------\n------------------------------------------------\n"; 
     } 
    }while(choice != '5'); 

    return 0; 
} 

只是忽略連字符的線條，它們只是爲了使程序看起來更漂亮時，它運行。

請注意，我是初學者！除了我的問題之外，還可能有很多其他的錯誤。也忽略了remove功能，我還沒有得到這一問題尚未...我添加了註釋//1.this line和//2.this line拳頭一個被稱爲當temp<n所以你必須有一個節點比較temp

Answer 1

我從更多的人那裏得到了一些幫助，我們找到了解決辦法。這裏是我的insert溫控功能：

//hvis lista ikke er tom, sett inn noden sortert: 
void insert(node* &first, node* &end, string data) 
{ 
    if(isEmpty(first)) 
    { 
     insertAsFirstElement(first, end, data); 
    } 
    else 
    { 
     node* temp = new node; 
     temp->data = data; 
     temp->next = first; 
     temp->prev = NULL; 
     first->prev = temp; 
     first = temp; 
    } 

    //sortering 
    if(first != NULL) 
    { 
     node* current = first; 
     node* prev = NULL; 
     node* tempNode = NULL; 


     while(current->next != NULL) 
     { 
      tempNode = current->next; 

      //cout << "current: " << current->data << " tempNode: " << tempNode->data << endl; 

      if(current->data > tempNode->data) 
      { 
       //cout << "swapped " << "current: " << current->data << " tempNode: " << tempNode->data << endl; 
       swap(current->data, tempNode->data); 
      } 
      else 
      { 
       prev = current; 
       current = current->next; 
      } 
     } 
    } 
} 

這對數據進行排序，如果它是一個string，對數字的小錯誤，解釋爲string，可與將所有號碼的int來解決。

編輯： 與nubmers的這個錯誤根本不是一個錯誤。該列表認爲11小於5，但這是因爲每個輸入都被插入爲string。那麼，如果你認爲1 = a和2 = b，那麼它很有意義。所以如果你想讓它們按照邏輯順序進行排序，11> 5，你必須將所有數字轉換爲int。

Answer 2

檢查兩行n，第二個是temp>=n，因此您需要做的是將temp與下一個節點n進行比較。與我到目前爲止所說的很明顯，你必須刪除我所評論的這條線//4.you should remove this line : n = temp->next;這是導致你最後一個問題的原因。另外你還有一個錯誤，你必須刪除break;它會讓你列在排序的中間，所以你的排序從未完成，這是導致其他問題的原因。

while(n) 
{ 
    if(n->data > temp->data) 
    { 
     cout << "temp BEFORE n" << endl; 
     temp->prev = n->prev; 
     temp->next = n; 
     n->prev = temp; 

     if(temp->prev) 
     { 
      temp->prev->next = temp; 

     } 
     else 
     { 
      first = temp; 
     } 
     n = temp->prev; //1.This line 

    } 
    else if(n->data <= temp->data) 
    { 
     cout << "temp AFTER n" << endl; 
     //temp = new node; 
     //temp->data = data; 
     temp->prev = n; 
     temp->next = n->next; 
     n->next = temp; 

     if(temp->next) 
     { 
      temp->next->prev = temp; 
     } 
     else 
     { 
      end = temp; 
     } 
     n = temp->next;  //2.This line 
     //3.you should comment this line : break; 
    } 
    //4.you should remove this line : n = temp->next; 
}